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