linux-kernel - Re: [RFD] sched/deadline: EDF dynamic quota design

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>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <53A2A9BD.3070107@unitn.it>
Date:	Thu, 19 Jun 2014 11:13:33 +0200
From:	Luca Abeni <luca.abeni@...tn.it>
To:	"xiaofeng.yan" <xiaofeng.yan@...wei.com>
CC:	Henrik Austad <henrik@...tad.us>,
	Juri Lelli <juri.lelli@...il.com>,
	Peter Zijlstra <peterz@...radead.org>,
	Ingo Molnar <mingo@...hat.com>, duzhiping.du@...wei.com,
	xiaofeng.yan2012@...il.com, raistlin@...ux.it, tkhai@...dex.ru,
	harald.gustafsson@...csson.com, linux-kernel@...r.kernel.org
Subject: Re: [RFD] sched/deadline: EDF dynamic quota design

On 06/18/2014 09:01 AM, xiaofeng.yan wrote:
[...]
>>>> I also had an implementation of the GRUB algorithm (based on a modification
>>>> of my old CBS scheduler for Linux), but the computational complexity of the
>>>> algorithm was too high. That's why I never proposed to merge it in SCHED_DEADLINE.
>>>> But maybe there can be some trade-off between the "exact compliance with the
>>>> GRUB algorithm" and implementation efficiency that can make it acceptable...
>>>>
>>>>
>>> Has these  codes been opened about the implementation in some community or not ?
>> The old GRUB scheduler for Linux was used for some experiments published in a paper
>> at RTLWS 2007, and of course the code was open-source (released under GPL).
>> It required a patch for the Linux kernel (I used a 2.6.something kernel) which allowed
>> to load the scheduler as a kernel module (yes, I know this is the wrong way to go...
>> But implementing it like this was simpler :).
>> That is very old code... I probably still have it somewhere, but I have to search
>> for it. If someone is interested, I can try to search (the story of the user-space
>> daemon for adaptive reservations is similar: I released it as open-source years ago...
>> If anyone is interested I can search for this code too)
>>
>>
>>                 Luca
>>
> I'm glad that you reply this email.  yes, I'm so interesting about your solution.  In fact , there are scenarios
> in our product.  Could you send me a link if you have?  I can test your solution in our scene if you like.
Ok, so I found my old code for the CBS scheduler with GRUB modifications.
You can get it from here: http://disi.unitn.it/~abeni/old-cbs-scheduler.tgz

Please note that:
1) This is old code (for 2.6.x kernels), written before SCHED_DEADLINE development
    was started
2) The scheduler architecture is completely different respect to the current one,
    but the basic scheduling algorithm implemented by my old scheduler is the same
    one implemented by SCHED_DEADLINE (but I did not implement multi-processor support :)
3) You can have a look at the modifications needed to implement GRUB by simply grepping
    for "GRUB" in the source code. Basically, the algorithm is implemented by:
    1) Implementing a state machine to keep track of the current state of a task (is it
       using its reserved fraction of CPU time, did it already use such a fraction of CPU
       time, or is it not using any CPU time?). This is done by adding a "state" field in
       "cbs_struct", and properly updating it in cbs.c
    2) Keeping track of the total fraction of CPU time used by the active tasks. See the "U"
       variable in cbs.c (in a modern scheduler, it should probably become a field in the
       runqueue structure)
    3) Modifying the rule used to update the runtime. For a "standard" CBS without CPU
       reclaiming (the one implemented by SCHED_DEADLINE), if a task executes for an amount
       of time "delta" its runtime must be decreased by delta. For GRUB, it must be decreased
       by "delta" mutliplied by U. See "account()" in cbs.c.
       The "trick" is in properly updating U (and this is done using the state machine
       mentioned above)

Summing up, this code is not directly usable, but it shows you what needs to be done in
order to implement the GRUB mechanism for CPU reclaiming in a CBS scheduler...



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