Re: [PATCH] DRTL kernel 2.6.32-rc3 : SCHED_EDF, DI RT-Mutex,Deadline Based Interrupt Handlers
Date: Sun Oct 25 2009 - 04:46:28 EST
On Thu, 2009-10-22 at 20:12 +0530, Soumya K S wrote:
> Hi Dario,
> we needed a deadline based scheduler for DRTL and we zeroed
> in upon SCHED_EDF. We see that the threads here are fairly new too :-P
Yes, we are not far from the starting point as well... :-)
> > Nice, from here, it seemed we were working on very similar things, and I
> > was wondering if we could somehow collaborate... :-)
> Sure! That would be good :)
So... I looked at the code and, even if the aim of our two projects are
quite the same, our implementations are very different.
The main difference is the bandwidth reservation thing.
I strongly think that, on a system like Linux, it should be very
important to have --at least as a possibility-- the following features:
- tasks can request for a guaranteed runtime over some time interval
- admission test should guarantee no oversubscription
- bandwidth enforcing must avoid reciprocal tasks interferences.
Maybe we can make the second and third configurable/optional (already
thought about that, and it should be quite easy), but they need to be
there, at least to avoid extending the interface again when we'll
realize they'll needed! :-P
I don't know how much you, and other people here, are familiar with such
idea... We implemented it using one of the many existing algorithm. I
can give you pointers to papers and other implementations of it if
To keep it short and practical, you can think at it as something similar
to what MacOS-X (and I think Solaris) already have --and actively use,
e.g., for the Jack Audio Connection Kit-- and call
THREAD_TIME_CONSTRAINT (very poor docs, I think, but it gives the big
Moreover, as Peter pointed out, coming out with an interface which is
too much tightly tied to EDF, or to any other specific algorithm,
wouldn't be the best idea. What would happen if somewhere in the future
we decide to change from the EDF algorithm to some other deadline based
That's why we changed the name and the interface from _EDF/_edf (yep, it
has been our first choice too! :-P) to _DEADLINE/_deadline, and that's
why I think we should continue striving for even more
Obviously, also SMP has to be there! :-P
We have it in fully partitioned right now, but I'll become global (with
support for cpu-affinity) in very short time I hope (Juri, from ReTiS
Lab in Pisa is already working on it).
For rt-mutexes/deadline inheritance, the big issue is that, it works if
you only have EDF, but with a "bandwidth aware scheduler", you need
something more, which is why we don't have it yet... However, I think it
could be a nice starting point.
Finally, I like the idea of deadline IRQ handling and I think it would
be worth to mind it some more. :-)
> > Even from the implementation point of view, I see you didn't used a new
> > scheduling class.
> A simple system where there a few real-time tasks and a few non-real
> time tasks, the timelines can be architected out for each real-time
> task in the system. In such a case, given the RT bandwidth in the
> system, the task with the lowest deadline gets to be scheduled first
> till it is there in the system.
> In short, for such simple systems, we shifted the burden of admission
> control to the architect and kept close to the existing code.
Well, I kind of agree on both, _iff_ you're target is _only_ such small
embedded systems. However, my very humble opinion is that, on Linux, you
need something more general and, since we are talking about real-time,
as much predictable and analyzable as you can get... And I think a
separate scheduling class would be better suited for this. What do you
> > I'm right in the opposite situation, I've got SMP (partitioned for now,
> > but we're working on migrations) and also CGROUPS support, but we are
> > still wondering how deadline (or something more sophisticated, like
> > bandwidth) inheritance could work in such a case...
> That's right, we are still working on SMP and hope there are no
> scalability issues in this patch w.r.t SMP.
Well, I don't know. I guess achieving something similar to what we
already have now (partitioned SMP) should not be impossible even with
your approach... But if you want something different, such has global
(EDF) scheduling, where task can migrate among CPUs according to their
affinity, would but a major headache!! :-O
> > Do you already have any numbers or testcase? I have some (well, a few!)
> > of them... I'll try to find the time to give it a try to your patch with
> > them...
> We have tested Co-operative context switch time, Pre-emptive context
> switch time and Interrupt Latency, all of them are of ~130us for
Mmm... I'm not sure I see why and how your patch should affect context
switches duration... However, do you have the testcases for such tests?
<<This happens because I choose it to happen!>> (Raistlin Majere)
Dario Faggioli, ReTiS Lab, Scuola Superiore Sant'Anna, Pisa (Italy)
http://blog.linux.it/raistlin / raistlin@xxxxxxxxx /
Description: This is a digitally signed message part