periods and deadlines in SCHED_DEADLINE
in [Kernel]
|
Prev: [PATCH 09/11] Removing dead SERIAL_BFIN_{HARD_, }CTSRTS
Next: Badness at fs/sysfs/symlink.c:82 during qeth initalization
From: Raistlin on 9 Jul 2010 10:40 Hi all, So, talking to Peter and Thomas at the OSPERT workshop in Brussels [1], the so called "sporaidic task model" came out many many times! Such model comprises three parameters: wcet (or better budget or better runtime :-D), deadline and period, where obviously deadline and period could be different. However, SCHED_DEADLINE, since now, is using just deadline, assuming that period is always equal to it. Now, Peter said something about starting using period as well, but we didn't have the time to discuss about that. Ironically, I got just a couple of days before _the_same_ feature request by Harald from Ericsson (in Cc), asking the very same thing. So, this mail is to try to find a consensus (or just to gather your opinions) on how to include this feature in the scheduler. Since I'm about to release a new version, I would like, if possible, to take these requests into account... Here's the issue: - using periods for calculating the tasks' bandwidth and then using deadlines for scheduling the tasks is going to work, but the admission control test that you would need for ensuring anybody will make its deadline is waaay more complex than Sum_i(BW_i)<1, even for uniprocessors/partitionig. That one instead would gives you just a very basic guarantee that the design in not completely broken (formally, I think I should say it is only a necessary condition :-)). Therefore, here it is my proposal: - if the programmer specify both period and deadline, I act as above, running the _only_necessary_ test in the kernel, assuming that userspace performed some other kind of (correct!) admission test by its own, or that it is cool with missing some deadlines... What do you think? - do you think it could be useful to have a different syscall to deal with the period parameter (if it's different from deadline), e.g., something useful to make the task periodic as you have (if I remember well) in Xenomai or RTAI? If you think it's worth doing that, do you think the task_wait_interval() syscall that we already added could/should do the job? Basically, from the scheduling point of view, what it could happen is that I'm still _NOT_ going to allow a task with runtime Q_i, deadline D_i and period P_i to use more bandwidth than Q_i/P_i, I'm still using D for scheduling but the passing of the simple in-kernel admission test Sum_i(Q_i/P_i)<1 won't guarantee that the task will always finish its jobs before D. Please, if you find this interesting provide me with your comments, otherwise, excuse me for bothering. :-) Thanks and regards, Dario [1] http://www.artist-embedded.org/artist/Overview,1909.html -- <<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(a)ekiga.net / dario.faggioli(a)jabber.org
From: Peter Zijlstra on 9 Jul 2010 10:40 On Fri, 2010-07-09 at 15:38 +0200, Raistlin wrote: > > Therefore, here it is my proposal: > - if the programmer specify both period and deadline, I act as above, > running the _only_necessary_ test in the kernel, assuming that > userspace performed some other kind of (correct!) admission test by > its own, or that it is cool with missing some deadlines... What do > you think? It would be good to provide room in the interface to improve upon this situation. One thing we could do, although this would make the proposed scheduler a wee bit more complex, is split between hard and soft realtime. Only accept P==rel_D for hard, and schedule the soft tasks in the hard slack or something like that. That way we can later extend the hard admission tests to accept more. -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo(a)vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
From: Bjoern Brandenburg on 9 Jul 2010 11:40 On Jul 9, 2010, at 4:18 PM, Peter Zijlstra wrote: > On Fri, 2010-07-09 at 15:38 +0200, Raistlin wrote: > >> - using periods for calculating the tasks' bandwidth and then using >> deadlines for scheduling the tasks is going to work, but the >> admission control test that you would need for ensuring anybody >> will make its deadline is waaay more complex than Sum_i(BW_i)<1, even >> for uniprocessors/partitionig. That one instead would gives you just >> a very basic guarantee that the design in not completely broken >> (formally, I think I should say it is only a necessary >> condition :-)). > > Happen to have a paper handy that explains all this in a concise way? > Sounds confusing, but this is actually not that complicated. - If the period exceeds the deadline of a task, then it is said to have a constrained deadline, and is said to be a constrained task. - The density of a task is the ratio budget/min(period, relative deadline). The density of a task is at most its utilization (budget/period). - There exists a simple *sufficient* (but not necessary) test for uniprocessor EDF for constrained tasks: if the sum of all task densities is at most one (on each processor), then all jobs will meet their deadlines. (Of course, this assumes that the budget is only replenished at the beginning at each period and does not take self-suspensions due to I/O etc. into account.) - More accurate tests exist. A very recent paper (presented this Wednesday at ECRTS) by Masrur et al. provides a summary of the state of the art and a new constant-time admissions test. Constant-Time Admission Control for Partitioned EDF Alejandro Masrur, Samarjit Chakraborty, and Georg F�rber Proc. ECRTS 2010, pp 34-43 ftp://ftp.rcs.ei.tum.de/pub/papers/rtsg/edffast.pdf As a side note, almost all global EDF hard real-time admission tests can handle tasks with constrained deadlines transparently. However, as far as I can tell, they do not apply to SCHED_DEADLINE. - Bj�rn PS: My responses will be delayed, I'm off to the airport... -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo(a)vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
From: Peter Zijlstra on 9 Jul 2010 12:40 On Fri, 2010-07-09 at 16:51 +0200, Bjoern Brandenburg wrote: > On Jul 9, 2010, at 4:18 PM, Peter Zijlstra wrote: > > > On Fri, 2010-07-09 at 15:38 +0200, Raistlin wrote: > > > >> - using periods for calculating the tasks' bandwidth and then using > >> deadlines for scheduling the tasks is going to work, but the > >> admission control test that you would need for ensuring anybody > >> will make its deadline is waaay more complex than Sum_i(BW_i)<1, even > >> for uniprocessors/partitionig. That one instead would gives you just > >> a very basic guarantee that the design in not completely broken > >> (formally, I think I should say it is only a necessary > >> condition :-)). > > > > Happen to have a paper handy that explains all this in a concise way? > > > > Sounds confusing, but this is actually not that complicated. Indeed, reading the referenced paper did clear things up, thanks! I think the easiest path for now would indeed be to split between hard and soft rt tasks, and limit hard to d==p, and later worry about supporting d<p for hard. It will very much depend on how we're going to go about doing things with that 'load-balancer' thingy anyway. The idea is that we approximate G-EDF by moving tasks around, but Dario told me the admission tests are still assuming P-EDF. Add to that the interesting problems of task affinity and we might soon all have a head-ache ;-) One thing we can do is limit the task affinity to either 1 cpu or all cpus in the load-balance domain. Since there don't yet exist any applications we can disallow things to make life easier. If we only allow pinned tasks and free tasks, splitting the admission test in two would suffice I think, if keep one per-cpu utilization measure and use the maximum of these over all cpus to start the global utilization measure, things ought to work out. If we do hard and soft independenty, we would need to split those into 2 again, resulting in 4 sets of measures. -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo(a)vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
From: Raistlin on 10 Jul 2010 03:10
On Fri, 2010-07-09 at 16:51 +0200, Bjoern Brandenburg wrote: > > Happen to have a paper handy that explains all this in a concise way? > > > > Sounds confusing, but this is actually not that complicated. > > - If the period exceeds the deadline of a task, then it is said to have a constrained deadline, and is said to be a constrained task. > > - The density of a task is the ratio budget/min(period, relative deadline). The density of a task is at most its utilization (budget/period). > > - There exists a simple *sufficient* (but not necessary) test for uniprocessor EDF for constrained tasks: if the sum of all task densities is at most one (on each processor), then all jobs will meet their deadlines. (Of course, this assumes that the budget is only replenished at the beginning at each period and does not take self-suspensions due to I/O etc. into account.) > Right, I think Bjoern made it much more clear than how you can find it in many of the existing papers! :-) Just to make a simple UP example, if you have two tasks with the following parameters (where T_i=(C_i, P_i, D_i)): T_1 = (4, 10, 5) T_2 = (4, 10, 5) Then the test Sum_i(C_i/P_i)<1 will say "go!" (4/10+4/10<1), but one of the tasks can miss its deadline by 3 time units in the worst case (if, and if yes which one, depends on the order with witch they arrive). Using D_i instead of P_i in the test will make things better in this case (4/5+4/5>1 ==> "no go!"), but its overly pessimistic (i.e., only sufficient). In fact for this task set: T_1 = (1, 10, 2) T_2 = (2, 20, 4) T_3 = (3, 50, 6) which has small utilization (Sum_i(C_i/P_i)=.26) and *is schedulable*, even if 1/2+2/4+3/6=1.5>1. Hope this helped in clarifying things even more! :-D Btw, another nice survey about schedulability tests for global EDF I know (and you'll forgive me if I point you to something from my institution :-)) is this http://retis.sssup.it/~marko/papers/ICPP09.pdf. > As a side note, almost all global EDF hard real-time admission tests can handle tasks with constrained deadlines transparently. However, as far as I can tell, they do not apply to SCHED_DEADLINE. > This is the only part I am not sure I got... Can you explain me what do you mena by "they do not apply" ? > PS: My responses will be delayed, I'm off to the airport... > Yep, so will be mine one, including this one! :-P Thanks and regards, Dario -- <<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(a)ekiga.net / dario.faggioli(a)jabber.org |