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

["xiaofeng.yan" <xiaofeng.yan@huawei.com>]

On 2014/6/19 17:13, Luca Abeni wrote:
> 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...
>
>
Thanks for giving me your solution. I will take a look at it and modify 
it in our scene later.

Thanks
Yan
>
>                 Luca
>
> .
>