linux-kernel - Re: BFS 420: cleanup in tick handling

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [day] [month] [year] [list]

Message-ID: <CAJd=RBA++ayxZ807Lbm=ACPhFMWgtnBn2R-FLh1=zVVC2kNhGQ@mail.gmail.com>
Date:	Wed, 23 May 2012 21:28:33 +0800
From:	Hillf Danton <dhillf@...il.com>
To:	Chen <hi3766691@...il.com>, LKML <linux-kernel@...r.kernel.org>
Subject: Re: BFS 420: cleanup in tick handling

On Tue, May 22, 2012 at 10:00 PM, Chen <hi3766691@...il.com> wrote:
>
> 在 2012-5-22 下午9:50，"Hillf Danton" <dhillf@...il.com>写道：
>>
>> On Tue, May 22, 2012 at 9:45 PM, Chen <hi3766691@...il.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
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/