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

From: Luca Abeni
Date: Thu Jun 19 2014 - 05:13:50 EST


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@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/