Re: [RFC 4/4] Documentation/scheduler/sched-deadline.txt: add some references

[Henrik Austad <henrik@austad.us>]

On Thu, Apr 09, 2015 at 12:05:54PM +0200, Luca Abeni wrote:
> Hi Henrik,

> [..]
> >>+ where U_max = max_i {WCET_i / P_i}[10]. Notice that for U_max = 1,
> >>+ M - (M - 1) · U_max becomes M - M + 1 = 1 and this schedulability condition
> >>+ just confirms the Dhall's effect. A more complete survey of the literature
> >>+ about schedulability tests for multi-processor real-time scheduling can be
> >>+ found in [11].
> >>+
> >>+ As seen, enforcing that the total utilisation is smaller than M does not
> >>+ guarantee that global EDF schedules the tasks without missing any deadline
> >>+ (in other words, global EDF is not an optimal scheduling algorithm). However,
> >>+ a total utilisation smaller than M is enough to guarantee that non real-time
> >>+ tasks are not starved and that the tardiness of real-time tasks has an upper
> >>+ bound[12] (as previously noticed). Different bounds on the maximum tardiness
> >>+ experienced by real-time tasks have been developed in various papers[13,14],
> >>+ but the theoretical result that is important for SCHED_DEADLINE is that if
> >>+ the total utilisation is smaller or equal than M then the response times of
> >>+ the tasks are limited.
> >>+
> >>+ Finally, it is important to understand the relationship between the
> >>+ scheduling deadlines assigned by SCHED_DEADLINE and the tasks' deadlines
> >>+ described above (which represent the real temporal constraints of the task).
> >
> >What about simething like
> >
> >"
> >Finally, it is important to understand the relationship between the
> >scheduling deadlines assigned by SCHED_DEADLINE and the tasks' deadlines
> >described above.
> >
> >The task itself supplies a _relative_ deadline, i.e. an offset after the
> >release of the task at which point it must be complete whereas
> >SCHED_DEADLINE assigns an _absolute_ deadline (a specific point in time) on
> >the form
> >
> >      D_i = r_i + d_i
> >"
> >Or somesuch? I may be overdoing this.
> This is not the point I wanted to make... Absolute deadlines (equal to r + D)
> have been previously defined in the document for real-time tasks too.
> The difference between SCHED_DEADLINE's deadlines and tasks' deadlines is not
> "absolute vs relative". The difference is that SCHED_DEADLINE cannot know the
> "real" tasks' deadlines, so it uses "scheduling deadlines" that are generated
> according to the CBS rules (described in Section 2).

Ah, fair point, I was indeed too hasty. Thanks for clearing that up though!

> Now, if a task is developed according to the Liu&Layland model (does not block
> before the end of the job) and the SCHED_DEADLINE parameters are properly assigned
> (runtime >= WCET, period <= P) then the task's absolute deadlines and the scheduling
> deadlines coincides, so it is possible to guarantee the respect of the task's temporal
> constraints.
> This is the tricky (and confusing :) thing about SCHED_DEADLINE.
> I'll see if I can reword this paragraph to make it more clear.

Right! Assuming a spherical cow in vacuum etc etc. You're right of course, 
disregard my ramblings.

-- 
Henrik Austad