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
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
