On Fri, Oct 31, 2008 at 10:03:52AM +0100, Peter Zijlstra wrote:
Ah, ok, I thought introducing new syscalls was *really* frowned upon.
True.
As a start, that is the approach at least I would like to take. Once you have a
proven, functional EDF on a single core, you can extend that to handle several
cores, if you really want to.
Well, I have a simple solution to that to ;)
Well, not really. I mean, to be optimal, you should also consider WCET, but
then, that's really not interesting as IMHO that's the userspace-programmer's
responsibility. If the user wants to add tasks that sum up to 210% utilization,
it's really not much we can do anyway. You certainly wouldn't want the kernel to
stop accepting new jobs.
So, keep the kernel logic as simple as possible and move the job to the user.
By keeping the kernel logic simple - we make the job easier for the end-users. A
very complex EDF-scheduler will make the testing very difficult.
If, on the other hand, we *know* that the scheduler is not optimal, but that it
behaves in a predictable manner, the end users have a simpler task of finding
out why something bad happened.
Because, no matter *what* you do, and *how* you implement it, with *whatever*
features, there will be cases when things fall apart, and having a simple,
predictable scheduler will be necessary to figure it out.
No, we do not. Or, at least not at the same time (see below)
I didn't mean to rip the whole fifo/rr out of the kernel, but adding a switch at
compile-time so that you could choose *either* normal, static RT *or* EDF. Then
we could, at least for the first few versions, have it depend on !SMP to avoid
the whole SMP-non-optimal-mess.
yes, that would certainly be a problem. But, if we can configure in either EDF
or FIFO/RR, adding this to the kernel-rt-threads should be possible.
well, periods is not that difficult. Basically you treat everything as
asynchronus events and put them in the runqueue when they become runnable. And
the application itself should set a relative deadline via the syscall to tell
the kernel "when I become runnable, I must finish before time_now +
rel_deadline"
RT-tasks that runs forever will certainly be a problem, but what about something
like mark it as soft/firm and for every time a deadline is missed, have the
trigger function set a new deadline? It would mean you have to rewrite a whole
lot of apps though.
I'm not going to map anything anywhere. EDF is very different from priority
based scheduling and we should try to map something back (as priorities,
strictly speaking, are a set of deadlines analyzed and mapped to priorities
sothat the deadlines are met).
Well, then you suddenly introduce priorities to the deadlines, and that is not
good. A hard task is not more important than a soft, but the effect of missing
the deadline is. If the schedule is infeasible, it really doesn't matter what
you do, as you will miss deadlines, and if you prioritize hard tasks, you will
end up starving firm and soft
Before you go on and tell me how wrong I am, note that I don't disagree with
you, I think choosing hrt before the others, is the best solution from an
implementation point of view.
But, and pardon my ignorance, will an EDF-scheduler be intersting for such a
large system? From what I've gathered, small systems are the ones that could
benefit from an EDF as you can analyze and predict behaviour, and then, since
EDF is optimal, tune the CPU-freq down and still know that things will work.
Some embedded people can probably provide a lot better input here than me, as
this is just a general idea I snapped up 'somewhere' (where somewhere is an
element of the set of all places I've been the last 6 months).
Do you know about any pratical attempts on this, and what kind of result that
produced?
Yes, but should the kernel do the schedulability test? Or should the ball be
passed on to userspace? To analyze the schedulability, you would need the worst
case execution time (WCET) of the process, and if the kernel/scheduler should
start trying to estimate that...
So, as a start, why not just 'ignore' WCET in the first versions, and that can
be added later on, if necessary.
Or, have the task run with minimal deadline, and then set to TASK_INTERRUPTIBLE,
use a timer to awaken it again in a short time, run it, yield and so on. Make a
periodic tick that will preempt whatever task that's running?
A lot of good points, and I certainly see your side of it. However (and yes, I
have to argue a bit more ;)), I don't think an EDF-scheduler should contain a
lot of features.
If you want to use the EDF, why not give the user a list of consequenses like
- Only a single core
- No other RT-scheduler, if other userspace program breaks, so be it, the user
has been warned.
- Best effort only
- Provide handlers for a given set of signals that will be sent to any
application missing a deadline
- no cpu-scaling
- ... keep going, basically strip away every piece of dynamic behaviour and
complex scheduling code
henrik
--
