On 2014/6/17 16:01, Luca Abeni wrote:
Hi,
On 06/17/2014 04:43 AM, xiaofeng.yan wrote:
[...]
The basic ideas are (warning! This is an over-simplification of the
algorithm! :)
- You assign runtime and period to each SCHED_DEADLINE task as usual
- Each task is guaranteed to receive its runtime every period
- You can also define a maximum fraction Umax of the CPU time that the
SCHED_DEADLINE tasks can use. Note that Umax _must_ be larger or
equal
than sum_i runtime_i / period_i
(note: in the original GRUB paper, only one CPU is considered, and
Umax is
set equal to 1)
- If the tasks are consuming less than Umax, then the scheduling
algorithm
allows them to use more runtime (but not less than the guaranteed
runtime_i)
in order to use up to Umax.
This is achieved by modifying the rule used to decrease the
runtime: in
SCHED_DEADLINE, if a task executes for a time delta, its runtime
is decreased
by delta; using GRUB, it would be decreased by a smaller amount of
time
(computed based on Umax, on the active SCHED_DEADLINE tasks, etc...).
This requires to implement some kind of state machine (the details
are in
the GRUB paper)
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.
Thanks
Yan
--
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/
