On Mon, Jan 27, 2014 at 01:30:42PM +0100, Luca Abeni wrote: > Hi Henrik, > > On 01/27/2014 12:53 PM, Henrik Austad wrote: > [...] > >>+ In more details, the CBS algorithm assigns scheduling deadlines to > >>+ tasks in the following way: > >>+ > >>+ - Each SCHED_DEADLINE task is characterised by the "runtime", > >>+ "deadline", and "period" parameters; > >>+ > >>+ - The state of the task is described by a "scheduling deadline", and > >>+ a "current runtime". These two parameters are initially set to 0; > >>+ > >>+ - When a SCHED_DEADLINE task wakes up (becomes ready for execution), > >>+ the scheduler checks if > >>+ > >>+ current runtime runtime > >>+ ---------------------------------- > ---------------- > >>+ scheduling deadline - current time period > >>+ > >>+ then, if the scheduling deadline is smaller than the current time, or > >>+ this condition is verified, the scheduling deadline and the > >>+ current budget are re-initialised as > > > >Current runtime: time spent running _this_ period? or is _remaining_ > >runtime this period? I get the feeling it's the latter. > > > >So, roughly, it is the ration > > > > remaining_runtime / relative_time_to_deadline > > > >which needs to be greater than the assigned CPU bandwidth, and if so, the > >budget should be replensihed? > > > >Shouldn't there be something about not refilling the budget before a new > >period has started? > Uh... Maybe the description above can be improved :) > Do you think that using "remaining runtime" instead of "current runtime" > would help? If yes, I'll make this change. Yes, in my vocabularly, "remaining" != "current" :), so changing to 'remaining runtime' would be nice. > Also, I see that some of your questions are answered by some items below... Yes, but I left the comments to indicate that the order was a bit confusing. > Do you think that changing the order of the items in the presentation would > improve the readability? If you suggest a better ordering, I'll try to > rewrite the algorithm's description according to it. Could be, at least the ratio-caclulation was a bit confusing until I'd read the entire section. My preferred order (I've just cut'n'pased from the original email here) + - The state of the task is described by a "scheduling deadline", and + a "current runtime". These two parameters are initially set to 0; + + - Each SCHED_DEADLINE task is characterised by the "runtime", + "deadline", and "period" parameters; + + - When a SCHED_DEADLINE task executes for an amount of time t, its + current runtime is decreased as + + current runtime = current runtime - t + + (technically, the runtime is decreased at every tick, or when the + task is descheduled / preempted); + + - When the current runtime becomes less or equal than 0, the task is + said to be "throttled" (also known as "depleted" in real-time literature) + and cannot be scheduled until its scheduling deadline. The "replenishment + time" for this task (see next item) is set to be equal to the current + value of the scheduling deadline; + + - When the current time is equal to the replenishment time of a + throttled task, the scheduling deadline and the current runtime are + updated as + + scheduling deadline = scheduling deadline + period + current runtime = current runtime + runtime + - When a SCHED_DEADLINE task wakes up (becomes ready for execution), + the scheduler checks if + + current runtime runtime + ---------------------------------- > ---------------- + scheduling deadline - current time period + + then, if the scheduling deadline is smaller than the current time, or + this condition is verified, the scheduling deadline and the + current budget are re-initialised as + + scheduling deadline = current time + deadline + current runtime = runtime + + otherwise, the scheduling deadline and the current runtime are + left unchanged; + Emphasis on -my- preferred order. :) Either way, I'm quite happy with this documentation-update, this is just nitpick :) -- Henrik Austad
Attachment:
signature.asc
Description: Digital signature
