Re: [PATCH] sched/deadline: Add sched_dl documentation

[Henrik Austad <henrik@austad.us>]

On Mon, Jan 20, 2014 at 02:39:29PM +0100, Luca Abeni wrote:
> Hi all,
> 
> On 01/20/2014 02:16 PM, Henrik Austad wrote:
> [...]
> >>>>+ The typical -deadline task is composed of a computation phase (instance)
> >>>>+ which is activated on a periodic or sporadic fashion. The expected (maximum)
> >>>>+ duration of such computation is called the task's runtime; the time interval
> >>>>+ by which each instance needs to be completed is called the task's relative
> >>>>+ deadline. The task's absolute deadline is dynamically calculated as the
> >>>>+ time instant a task (or, more properly) activates plus the relative
> >>>>+ deadline.
> >>>
> >>>activates - released?
> >>>
> >>
> >>I'd keep (modifying a bit):
> >>
> >>"time instant a task activates plus the relative deadline."
> >>
> >>This is probably the nearest thing to what is implemented that we can say
> >>(without entering into the theory too much), a task that "activates" can mean
> >>that it is first released, enqueued, woken-up, etc.
> >
> >So, if we look at release (yes, I'm avoiding activates for a little while)
> >as the time at the *beginning* of a new period, then, and only then should
> >the *absolute* deadline be computed.
> >
> >If you den move on to use 'activate' as a term for when a task becomes
> >eligble to run, then 'release' becomes a subset of 'activate', and you
> >should only compute the absolute deadline at that time. Did that make
> >sense?

> I think things are a little bit complex here, because there are 2 different
> "deadlines" we can think about:
> - the "jobs deadlines" (the absolute job deadline can be computed at job
>   arrival, as the arrival time + the relative deadline). These are generally
>   used for performance metrics, to see if a job is respecting its timing
>   constraints or not
>
> - the "scheduling deadlines", which are the ones used by the scheduler to
>   schedule the tasks. These are computed at tasks' wake-up time - notice that
>   for self-suspending jobs there can be wake-up times that are not job arrival
>   times. And are assigned according to the rules described in the CBS paper.
>
> I think this can easily become very confusing, so I currently have no concrete
> proposals for improving the documentation... But I wanted to point out that
> things here are more complex than in the "traditional" real-time task model.

Traditional real-time as in the current real-time model used in Linux, or 
traditional as in EDF terminology used by Liu & Layland?

> Maybe a solution could be to simply describe scheduling deadlines (which are
> what sched_deadline uses) without going into the details of jobs' deadlines.

Huh?

We definately need a short dictionary. In fact, I'd like to have a 
paragraph describing what deadline driven scheduling is.

For instance, I'm getting *Really* confused wrt to arrival time - you seem 
to wrap several types of arrival into the same name,  yet treat it 
differently.

- arrival: when a job gets ready to run for the first time
- arrival: when a job unblocks on some resource

Or did I misunderstand?

So, the terminology I'm used to, an attempt to write up something to 
clear up the terminology and establish common grounds. Please 
edit/elaborate or shoot down as appropriate:

"""
N. Crashcourse in deadline-terminology:

In a system, we typically look at a set of tasks. In Linux-kernel 
terminology, a particular task is normally a thread. When a thread is 
ready to run, we say that a *job* of that task is running. It is 
perhaps easiest to grasp this if one think only of periodic tasks, i.e. a 
thread that need to run for 2ms every 10ms. Normally, we want one job to 
finish before a new (of the same task) start, which implies that the 
deadline for this task is also 10ms. Once this is clear, expanding one's 
mind to aperiodic and/or sporadic tasks is easier.

* Periodic task: a task that needs to run for a while every N us.
* Sporadic task: a tasks that needs tor un for a while at most every N us 
  (jobs start no closer than N us apart)
* Aperiodic task: a task that have no particular period, but once 
  released, needs to complete before a given deadline.

* Set of all deadline-tasks in the system: \tau
* One particluar task: \tau_i
* The j'th job of task i: \tau_{i,j}
* The (relative) deadline of task i: D_i
* The (periodic, relative) release time of task i: R_i
* Required execution time a tasks's job needs to complete. C_i
* Absolute release-time, the time when a new job is ready (when a thread is 
  woken up for a new period).
* The absolute deadline of a job, the actual point in time where a job 
  needs to be finished. This is what the scheduler looks at when it picks 
  the next thread to run.

We can now construct a 3-tuple describing a perioic and sporadic tasks: 

          (C_i, R_i, D_i).

These 3 items is what you can use to describe your task to the scheduler.
"""

> So, the document could avoid talking about instances (or jobs), and can say
> that a task is guaranteed to receive "runtime" time units every "period" time
> units (and these "runtime" time units are available within "deadline" time
> units from the beginning of the period). Every time the task wakes up, the
> scheduler computes a scheduling deadline consistent with this constraint,
> and tasks are scheduled using EDF on these scheduling deadlines.
> Every time "runtime" time units are consumed in a period, the scheduling
> deadline is postponed by a period.

What is wrong with using the CORRECT TERMINOLOGY? People looking at using 
sched_deadline _need_ to understand what a _deadline_ scheduler is.

If the only goal of sched_deadline is to act as a bandwidth-gauge, then 
fine, but *I* want to use sched_deadline for systems that HAVE DEADLINES. I 
do NOT want to mess around with mapping deadlines to priorities in order to 
meet my deadlines. I suspect others would like to use sched_deadline for 
the same.

> This is of course an approximative description, but I think it can give an
> intuitive idea of how the scheduler works, and about the meaning of the three
> scheduling parameters.

Look, I'm not in favour of turning sched_deadline.txt into an academic 
paper, but it is clear that we need to establish a baseline here, and then 
we need to include tasks, instances/jobs, deadline, arrival/release and so 
on.

-- 
Henrik Austad