Re: BFS 420: cleanup in tick handling

[Hillf Danton]

On Tue, May 22, 2012 at 10:00 PM, Chen <hi3766691@xxxxxxxxx> wrote:
>
> å 2012-5-22 äå9:50ï"Hillf Danton" <dhillf@xxxxxxxxx>åéï
>>
>> On Tue, May 22, 2012 at 9:45 PM, Chen <hi3766691@xxxxxxxxx> 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@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/