Login | Register For Free | Help
Search for: (Advanced)

Mailing List Archive: Linux: Kernel

Re: BFS 420: cleanup in tick handling

 

 

Linux kernel RSS feed   Index | Next | Previous | View Threaded


dhillf at gmail

May 19, 2012, 12:23 AM

Post #1 of 7 (94 views)
Permalink
Re: BFS 420: cleanup in tick handling

The cpu on stack is not needed, so remove it.

--- a/kernel/sched/bfs.c Mon May 14 20:50:38 2012
+++ b/kernel/sched/bfs.c Sat May 19 15:18:24 2012
@@ -2822,8 +2822,7 @@ void wake_up_idle_cpu(int cpu);
*/
void scheduler_tick(void)
{
- int cpu __maybe_unused = smp_processor_id();
- struct rq *rq = cpu_rq(cpu);
+ struct rq *rq = this_rq();

sched_clock_tick();
/* grq lock not grabbed, so only update rq clock */
--
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo [at] vger
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/


marogge at onlinehome

May 20, 2012, 2:01 AM

Post #2 of 7 (85 views)
Permalink
Re: BFS 420: cleanup in tick handling [In reply to]

On 05/19/2012 09:30 AM, Hillf Danton wrote:
> The cpu on stack is not needed, so remove it.
>
> --- a/kernel/sched/bfs.c Mon May 14 20:50:38 2012
> +++ b/kernel/sched/bfs.c Sat May 19 15:18:24 2012
> @@ -2822,8 +2822,7 @@ void wake_up_idle_cpu(int cpu);
> */
> void scheduler_tick(void)
> {
> - int cpu __maybe_unused = smp_processor_id();
> - struct rq *rq = cpu_rq(cpu);
> + struct rq *rq = this_rq();
>
> sched_clock_tick();
> /* grq lock not grabbed, so only update rq clock */
> --
> --
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo [at] vger
> More majordomo info at http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at http://www.tux.org/lkml/

Hillf, I noticed you posting a few patches to BFS recently. Just wanted
to make you aware that there is a certain erm communication issue
between the kernel maintainers and the author of BFS. Since he is busy
in real life you should contact him directly or cc him. See tail -1
Documentation/scheduler/sched-BFS.txt for email.
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo [at] vger
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/


dhillf at gmail

May 22, 2012, 5:42 AM

Post #3 of 7 (84 views)
Permalink
Re: BFS 420: cleanup in tick handling [In reply to]

Hi Martin

On Sun, May 20, 2012 at 5:01 PM, Martin <marogge [at] onlinehome> wrote:
> Hillf, I noticed you posting a few patches to BFS recently. Just wanted to
> make you aware that there is a certain erm communication issue between the

Would you please feel free to elaborate on the issue, btw?
I'd stop posting, yes?

> kernel maintainers and the author of BFS. Since he is busy in real life you
> should contact him directly or cc him. See tail -1

Fine, lets disturb less.

> Documentation/scheduler/sched-BFS.txt for email.
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo [at] vger
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/


dhillf at gmail

May 22, 2012, 6:50 AM

Post #4 of 7 (83 views)
Permalink
Re: BFS 420: cleanup in tick handling [In reply to]

On Tue, May 22, 2012 at 9:45 PM, Chen <hi3766691 [at] gmail> wrote:
> Actually the lowest deadline task selection algorithm now BFS used is O(n).
> I have already had an idea to enhance the lowest deadline task selection
> algorithm to O(1)

Would you please announce it on LKML?
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo [at] vger
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/


dhillf at gmail

May 22, 2012, 7:04 AM

Post #5 of 7 (85 views)
Permalink
Re: BFS 420: cleanup in tick handling [In reply to]

On Tue, May 22, 2012 at 10:00 PM, Chen <hi3766691 [at] gmail> wrote:
>
> 在 2012-5-22 下午9:50,"Hillf Danton" <dhillf [at] gmail>写道:
>>
>> On Tue, May 22, 2012 at 9:45 PM, Chen <hi3766691 [at] gmail> wrote:
>> > Actually the lowest deadline task selection algorithm now BFS used is
>> > O(n).
>> > I have already had an idea to enhance the lowest deadline task selection
>> > algorithm to O(1)
>>
>> Would you please announce it on LKML?
>
> First of all let me talk how to do it .We can use 40 list_head instead of
> the single list for time sharing scheduling policy.
> Then for task selection we will select the task from these 40
> list_head(actually not 40, just decide by next_sched_bit), then make a
> comparsion of these tasks(actually in the worse case we just need to do 40
> times of comparsion) and pick the lowest task. If a task wake, it would be
> the first node of (queue + p->prio). If a task run out of its timeslice, it
> will become the last node of(queue + p->prio). This is a concept of BFS
> deadline presort algorithm and the time complexity is O(1)

Thank you for shedding light, I will study it soon.
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo [at] vger
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/


dhillf at gmail

May 22, 2012, 7:09 AM

Post #6 of 7 (80 views)
Permalink
Re: BFS 420: cleanup in tick handling [In reply to]

On Tue, May 22, 2012 at 10:07 PM, Chen <hi3766691 [at] gmail> wrote:
>
> 在 2012-5-22 下午10:04,"Hillf Danton" <dhillf [at] gmail>写道:
>
>
>>
>> On Tue, May 22, 2012 at 10:00 PM, Chen <hi3766691 [at] gmail> wrote:
>> >
>> > 在 2012-5-22 下午9:50,"Hillf Danton" <dhillf [at] gmail>写道:
>> >>
>> >> On Tue, May 22, 2012 at 9:45 PM, Chen <hi3766691 [at] gmail> wrote:
>> >> > Actually the lowest deadline task selection algorithm now BFS used is
>> >> > O(n).
>> >> > I have already had an idea to enhance the lowest deadline task
>> >> > selection
>> >> > algorithm to O(1)
>> >>
>> >> Would you please announce it on LKML?
>> >
>> > First of all let me talk how to do it .We can use 40 list_head instead
>> > of
>> > the single list for time sharing scheduling policy.
>> > Then for task selection we will select the task from these 40
>> > list_head(actually not 40, just decide by next_sched_bit), then make a
>> > comparsion of these tasks(actually in the worse case we just need to do
>> > 40
>> > times of comparsion) and pick the lowest task. If a task wake, it would
>> > be
>> > the first node of (queue + p->prio). If a task run out of its timeslice,
>> > it
>> > will become the last node of(queue + p->prio). This is a concept of BFS
>> > deadline presort algorithm and the time complexity is O(1)
>>
>> Thank you for shedding light, I will study it soon.
> If you are free could you also help me to maintain my cpu scheduler, thanks.
> . :-)
No promise but try my best, ok?
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo [at] vger
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/


dhillf at gmail

May 23, 2012, 6:28 AM

Post #7 of 7 (82 views)
Permalink
Re: BFS 420: cleanup in tick handling [In reply to]

On Tue, May 22, 2012 at 10:00 PM, Chen <hi3766691 [at] gmail> wrote:
>
> 在 2012-5-22 下午9:50,"Hillf Danton" <dhillf [at] gmail>写道:
>>
>> On Tue, May 22, 2012 at 9:45 PM, Chen <hi3766691 [at] gmail> wrote:
>> > Actually the lowest deadline task selection algorithm now BFS used is
>> > O(n).
>> > I have already had an idea to enhance the lowest deadline task selection
>> > algorithm to O(1)
>>
>> Would you please announce it on LKML?
>
> First of all let me talk how to do it .We can use 40 list_head instead of
> the single list for time sharing scheduling policy.
> Then for task selection we will select the task from these 40
> list_head(actually not 40, just decide by next_sched_bit), then make a
> comparsion of these tasks(actually in the worse case we just need to do 40
> times of comparsion) and pick the lowest task.

If task is selected from one of the 40 lists by comparing deadline, then it is
not fair scheduling, since no chance to select tasks on other lists.

Plus you have to comparing CPUs allowed with a given CPU, that said,
O(1) is impossible, right?

> If a task wake, it would be
> the first node of (queue + p->prio). If a task run out of its timeslice, it
> will become the last node of(queue + p->prio). This is a concept of BFS
> deadline presort algorithm and the time complexity is O(1)

On other hand, I dont think O(1) is important, simply because if it is O(1)
when dequeuing, it is not O(1) at all when enqueuing.

btw, you spend time maintaining RIFS, why?
-hd
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo [at] vger
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

Linux kernel RSS feed   Index | Next | Previous | View Threaded
 
 


Interested in having your list archived? Contact Gossamer Threads
 
  Web Applications & Managed Hosting Powered by Gossamer Threads Inc.