Messages in this thread | | | Date | Wed, 11 Apr 2012 23:13:02 +0100 | From | Tommaso Cucinotta <> | Subject | Re: [PATCH 08/16] sched: add period support for -deadline tasks. |
| |
Il 11/04/2012 21:32, Steven Rostedt ha scritto: > On Fri, 2012-04-06 at 09:14 +0200, Juri Lelli wrote: > >> @@ -293,7 +293,11 @@ static void replenish_dl_entity(struct sched_dl_entity *dl_se) >> * assigned (function returns true if it can). >> * >> * For this to hold, we must check if: >> - * runtime / (deadline - t)< dl_runtime / dl_deadline . >> + * runtime / (deadline - t)< dl_runtime / dl_period . >> + * >> + * Notice that the bandwidth check is done against the period. For >> + * task with deadline equal to period this is the same of using >> + * dl_deadline instead of dl_period in the equation above. > First, it seems that the function returns true if: > > dl_runtime / dl_period< runtime / (deadline - t) > > > I'm a little confused by this. We are comparing the ratio of runtime > left and deadline left, to the ratio of total runtime to period. > > I'm actually confused by this premise anyway. What's the purpose of > comparing the ratio? If runtime< (deadline - t) wouldn't it not be able > to complete anyway? Or are we thinking that the runtime will be > interrupted proportionally by other tasks?
That's a well-known property of the CBS scheduling algorithm: the "unblock rule" says that, when a task wakes up, if the residual budget over residual deadline fits within the allocated "bandwidth", then we can keep the current (abs) deadline and residual budget without disrupting the schedulability of the system (i.e., ability of other admitted tasks to meet their deadlines). Otherwise, we should reset the status, i.e., refill budget and set the deadline a period in the future, because keeping the current abs deadline of the task would result in breaking guarantees promised to other tasks. Imagine a task going to sleep and waking too close to its deadline: its deadline would be the closest in the system, and it wouldn't allow anyone else to run. However, if its residual budget is also big, then this is going to not allow anyone to run for too much. Now, when doing the classical easy admission test for single-CPU EDF (sum of budgets over periods <= 1), we hadn't accounted for such a scenario with tasks blocking (which can actually be accounted for by using far more complex tests knowing for how long each task will block etc.). However, using the CBS, we can keep the easy test and add the simple cut-off rule at task wake-up which adds "temporal isolation", i.e., the capability to not disrupt others' guarantees if I sleep for too much. Said this, I guess/hope the rule is implemented right :-)
For a formal proof, I think you can refer to the Abeni's paper(s):
-) Integrating Multimedia Applications in Hard Real-Time Systems, RTSS '98 www.cis.upenn.edu/~lee/01cis642/papers/AB98.pdf
which redirects on the Technical Report: -) Server Mechanisms for Multimedia Applications
Hope this helps,
T.
-- Tommaso Cucinotta, Computer Engineering PhD, Researcher ReTiS Lab, Scuola Superiore Sant'Anna, Pisa, Italy Tel +39 050 882 024, Fax +39 050 882 003 http://retis.sssup.it/people/tommaso
| |