Re: BFS 420: cleanup in tick handling

Re: BFS 420: cleanup in tick handling

[Martin]

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@vger.kernel.org
> 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.

Re: BFS 420: cleanup in tick handling

[Hillf Danton]

Hi Martin

On Sun, May 20, 2012 at 5:01 PM, Martin <marogge@onlinehome.de> 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.

Re: BFS 420: cleanup in tick handling

[Hillf Danton]

On Tue, May 22, 2012 at 9:45 PM, Chen <hi3766691@gmail.com> 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?

Re: BFS 420: cleanup in tick handling

[Hillf Danton]

On Tue, May 22, 2012 at 10:00 PM, Chen <hi3766691@gmail.com> wrote:
>
> 在 2012-5-22 下午9:50，"Hillf Danton" <dhillf@gmail.com>写道：
>>
>> On Tue, May 22, 2012 at 9:45 PM, Chen <hi3766691@gmail.com> 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.

Re: BFS 420: cleanup in tick handling

[Hillf Danton]

On Tue, May 22, 2012 at 10:07 PM, Chen <hi3766691@gmail.com> wrote:
>
> 在 2012-5-22 下午10:04，"Hillf Danton" <dhillf@gmail.com>写道：
>
>
>>
>> On Tue, May 22, 2012 at 10:00 PM, Chen <hi3766691@gmail.com> wrote:
>> >
>> > 在 2012-5-22 下午9:50，"Hillf Danton" <dhillf@gmail.com>写道：
>> >>
>> >> On Tue, May 22, 2012 at 9:45 PM, Chen <hi3766691@gmail.com> 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?

Re: BFS 420: cleanup in tick handling

[Hillf Danton]

On Tue, May 22, 2012 at 10:00 PM, Chen <hi3766691@gmail.com> wrote:
>
> 在 2012-5-22 下午9:50，"Hillf Danton" <dhillf@gmail.com>写道：
>>
>> On Tue, May 22, 2012 at 9:45 PM, Chen <hi3766691@gmail.com> 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

Re: BFS 420: cleanup in tick handling

[Hillf Danton]

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 */
--