Re: [RFD] sched/deadline: EDF dynamic quota design
From: xiaofeng.yan
Date: Thu Jun 19 2014 - 22:30:45 EST
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
.
--
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/