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: Harald Gustafsson on 11 Jul 2010 01:50 2010/7/10 Raistlin <raistlin(a)linux.it>: > Indeed. I think things might be done step by step, relaxing the > constraints as long as we find better solutions. Yes, I definitely think the step by step approach is best here. So that eventually its possible to use hard deadline RT also for more complex task activation patterns. >> > Embedded people can of course easily hack in whatever they well fancy, >> > and adding the 'yes_I_really_want_this_anyway' flag or even taking out >> > admission control all together is something the GPL allows them to do. >> >> Not an option I would like to pursue, it should be possible to get a >> working solution without this. >> > Yeah, I see your point and agree with it. Btw, I think that, even in the > configuration described by Peter, if you --as an embedded system > engineer-- have the full control of your device/product, you can avoid > having any hard-rt task. Then, if you only have soft ones, you'll get > the benefit of having the possibility of setting D!=P without suffering > of any interference... Am I right? Yes, this is exactly what I mean. As long as the interface gives the user control to be able to demote a task to soft RT even if the admission control could allow it into the hard RT policy. Then later when we have managed to include more complex admission controls into the kernel, the system designer could when his system setup is handled move over to always use hard RT. This would also mean that people would start using the DL scheduler and having a motivation of improving the admission control, because it is preferred to have the benefit of reliable isolation between tasks. > I think this could be a viable solution, at least until we have > something better to relax assumptions on the schedulability test for > hard tasks, isn't it? Yes, I agree. Regards, Harald -- 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 11 Jul 2010 02:20 On Jul 10, 2010, at 9:50 AM, Raistlin wrote: >> >> What are the exact semantics of this extra proposed syscall? >> > Right now, it is: > task_wait_interval(t) --> "wake me up at the first instant after t when > you can give me my full runtime" > >> What exactly are the benefits over not having it, and simply rely on the >> task to not wake up more often, but if it does have it run into the lack >> of budget and sort it that way? >> > What you're saying obviously will always work, and it is actually a > quite common usage pattern (we use it like that a lot! :-)). > > The new syscall might help when it is important for a task to > synchronize with the budget provisioning mechanism. It might be > uncommon, but there could be situations --more in hard than in soft > scenarios-- where you want to be sure that you're next job (and all the > subsequent ones, if you behave well) will get its full runtime, even if > this means waiting a little bit. Isn't this basically sched_yield? Don't run me now, give lower-priority work a chance to complete, let me run again when my budget is replenished. Otherwise, what are the semantics of sched_yield under EDF? Cycle through equal-deadline jobs? Given sporadic task activations, this is probably not very useful. - Bj�rn -- 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 11 Jul 2010 02:50 On Jul 10, 2010, at 9:08 AM, Raistlin wrote: >> >> 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" ? I was under the impression that the kernel implementation is a P-EDF implementation. Now it seems to me that it is in fact a "P-EDF with frequent migrations" implementation. I'd be hesitant to just assume that it "approximates G-EDF" sufficiently well to apply any of the published G-EDF tests. - Bj�rn --- Bj�rn B. Brandenburg Ph.D. Student Dept. of Computer Science University of North Carolina at Chapel Hill http://www.cs.unc.edu/~bbb -- 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 11 Jul 2010 03:40 On Jul 10, 2010, at 10:08 PM, Harald Gustafsson wrote: > 2010/7/10 Peter Zijlstra <peterz(a)infradead.org> >> >> >> That is a very delicate point, the whole reason SCHED_FIFO and friends >> suck so much is that they don't provide any kind of isolation, and thus, >> as an Operating-System abstraction they're an utter failure. >> >> If you take out admission control you end up with a similar situation. > > OK, I see your point, and I also want to keep the isolation, its just > that I thought that the complexity might be too large to be accepted > by mainline. Let's work towards a solution with good admission > control, i.e. having more complex admission control to handle this. > >> In general the sporadic task model schedulers don't need to be >> privileged because it does provide isolation. But the moment you allow >> by-passing the admission control everything goes out the window. So even >> a simple privileged flag telling the admission control to stuff it would >> render the whole system unusable, you'd have to start failing everything >> not having that flag, simply because the admission control is rendered >> useless. > > Yes, thats true if you have any truly hard RT tasks in the system. > Could we have a way of making tasks with deadline=period also go into > the soft deadline RT policy and not just always run before any > deadline<period tasks? Maybe utilizing the flags field. In this way we > rather demote all tasks than elevate some tasks above other tasks, and > then the system designer could make sure that only using hard RT when > needed (and supported by the admission control). Since the fact that > it can be easily admission controlled is maybe not a sufficient fact > for making the user want to have it as a hard RT task, running before > tasks needing complex admission control. Also, without such notion the > behavior might change with new kernel releases when the admission > control is developed i.e suddenly some tasks will be scheduled as hard > that was previously scheduled as soft deadline RT. Trying to infer whether a task is "hard" or "soft" from task parameters is not a good idea, IMO. It's much better to make this an explicit part of the task model that is configured via sched_setparam. By default, tasks should be marked "soft" (this leaves more wiggle room to the kernel); users who care can change the flag to "hard". Taking a step back, I think the problem here is that we are trying to shove too many concepts and properties into a single scheduler. Hard (no tardiness) is different from soft (bounded tardiness) is different from global is different from partitioned. From my point of view, it makes no sense to support hard deadlines under G-EDF (this is backed up by our schedulability studies [1]). Hard deadlines are best served by a P-EDF implementation (that only migrates on task creation/admission). Also, it makes little sense to worry about supporting both hard and soft in a P-EDF implementation. Just schedule everything by its deadline and both hard and soft tasks will be fine (if the admissions test was passed). In my opinion, it is much more useful to have a two-level scheduling framework: a truly partitioned EDF implementation at the top level to support "hard" tasks, and a truly global EDF implementation at the second level for "soft" tasks, with the property that the second level implementation is only invoked if the first level is idle. This nicely matches Linux's scheduling class hierarchy. This leaves the question how to avoid starving the second level if the first level has "large" budgets (e.g., wcet 1 hour, period 2 hours), but this can be done with some additional budget tracking and job slicing. This is explained in detail in [2] (please forgive me for promoting my own work, but I think it is relevant). Here is what I think could work for the first iteration: 1) Set period, relative deadline, budget, and the hard-soft-flag with set_schedparam. 2) For hard tasks, the kernel finds the CPU with the lowest total utilization that is marked in the affinity masks and that passes a P-EDF admissions test. 3) Hard tasks are scheduled by a P-EDF implementation as described in [2]. 4) For soft tasks, the kernel requires that _all_ CPUs are marked in the affinity mask. 5) Soft tasks are scheduled with G-EDF as described in [2]. Under this approach, both the P-EDF and G-EDF scheduling classes become simpler to implement since they only deal with one kind of task. In particular, load balancing under P-EDF is only required at admissions time, the kernel is not required to infer anything, and the policy is well-defined and predictable, and manual partitioning is available for "hard" tasks. I assume that this works across 2-8 cores with shared caches, but (of course) G-EDF is not going to scale to largish numbers of cores and NUMA platforms. Thus, in later iterations 4) should be relaxed to allow clustered EDF. If, however, you are more interested in supporting both hard and soft under a single G-EDF scheduler, then I recommend taking a look at [3]. - Bj�rn [1] A. Bastoni, B. Brandenburg, and J. Anderson, An Empirical Comparison of Global, Partitioned, and Clustered Multiprocessor Real-Time Schedulers, in submission, May 2010. http://www.cs.unc.edu/~anderson/papers/rtss10c.pdf [2] B. Brandenburg and J. Anderson, Integrating Hard/Soft Real-Time Tasks and Best-Effort Jobs on Multiprocessors, Proceedings of the 19th Euromicro Conference on Real-Time Systems, pp. 61-70, July 2007. http://www.cs.unc.edu/~anderson/papers/ecrts07b.pdf [3] H. Leontyev and J. Anderson, A Unified Hard/Soft Real-Time Schedulability Test for Global EDF Multiprocessor Scheduling, Proceedings of the 29th IEEE Real-Time Systems Symposium, pp. 375-384, December 2008. http://www.cs.unc.edu/~anderson/papers/rtss08a.pdf --- Bj�rn B. Brandenburg Ph.D. Student Dept. of Computer Science University of North Carolina at Chapel Hill http://www.cs.unc.edu/~bbb -- 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: Harald Gustafsson on 12 Jul 2010 06:30
2010/7/11 Bjoern Brandenburg <bbb(a)email.unc.edu>: > Trying to infer whether a task is "hard" or "soft" from task parameters is not a good idea, IMO. It's much better to make this an explicit part of the task model that is configured via sched_setparam. By default, tasks should be marked "soft" (this leaves more wiggle room to the kernel); users who care can change the flag to "hard". Yes, this was along the lines of my suggestions also. > Taking a step back, I think the problem here is that we are trying to shove too many concepts and properties into a single scheduler. Hard (no tardiness) is different from soft (bounded tardiness) is different from global is different from partitioned. > > From my point of view, it makes no sense to support hard deadlines under G-EDF (this is backed up by our schedulability studies [1]). Hard deadlines are best served by a P-EDF implementation (that only migrates on task creation/admission). > > Also, it makes little sense to worry about supporting both hard and soft in a P-EDF implementation. Just schedule everything by its deadline and both hard and soft tasks will be fine (if the admissions test was passed). > > In my opinion, it is much more useful to have a two-level scheduling framework: a truly partitioned EDF implementation at the top level to support "hard" tasks, and a truly global EDF implementation at the second level for "soft" tasks, with the property that the second level implementation is only invoked if the first level is idle. This nicely matches Linux's scheduling class hierarchy. Would this prevent soft RT tasks to be pinned to a specific CPU, i.e. have an affinity set of one CPU? I'm asking since we would like to use soft deadline RT (bounded tardiness, e.g. with relative deadlines short than periods), but with threads set to run on a specific CPU. This is due to that we do an analysis on data dependencies etc in user space applications (or offline) and distribute jobs among threads on each CPU. At the same time we would like the isolation between parallel running such applications and other CPU activities. I'm not saying that all soft RT needs to be pinned or that some such tasks can't be made to meet hard admission control but we would need the possibility. If I would need to priorities between soft deadline RT and CPU affinity, soft deadline RT would win, since it is still quite likely that the tasks get scheduled on individual cores when needed. When you say truly global EDF implementation does that mean the scheduler only considers relative deadline and may "migrate" a thread among all the CPUs at each scheduling instance, disregarding cache effects, power management (e.g. waking an idle core), etc? Or can these things be factored into the relative deadlines (maybe they already are by the user)? /Harald -- 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/ |