Date: Thu, 9 Apr 2015 11:39:08 +0200
From: Henrik Austad <henrik@austad.us>
To: Luca Abeni <lucabe72@gmail.com>
Cc: peterz@infradead.org, juri.lelli@gmail.com, raistlin@linux.it,
        mingo@kernel.org, linux-kernel@vger.kernel.org,
        linux-doc@vger.kernel.org, Luca Abeni <luca.abeni@unitn.it>
Subject: Re: [RFC 4/4] Documentation/scheduler/sched-deadline.txt: add some
 references
Message-ID: <20150409093908.GB10954@sisyphus.home.austad.us>
References: <1428494380-1917-1-git-send-email-luca.abeni@unitn.it>
 <1428494380-1917-5-git-send-email-luca.abeni@unitn.it>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Disposition: inline
Content-Transfer-Encoding: 8bit
In-Reply-To: <1428494380-1917-5-git-send-email-luca.abeni@unitn.it>
User-Agent: Mutt/1.5.21 (2010-09-15)
Sender: linux-kernel-owner@vger.kernel.org
Content-Length: 8490
Lines: 176

On Wed, Apr 08, 2015 at 01:59:40PM +0200, Luca Abeni wrote:
> Add a description of the Dhall's effect, some discussion about
> schedulability tests for global EDF, and references to real-time literature,
> ---
>  Documentation/scheduler/sched-deadline.txt |   81 ++++++++++++++++++++++++----
>  1 file changed, 71 insertions(+), 10 deletions(-)
> 
> diff --git a/Documentation/scheduler/sched-deadline.txt b/Documentation/scheduler/sched-deadline.txt
> index ffaf95f..da5a8d7 100644
> --- a/Documentation/scheduler/sched-deadline.txt
> +++ b/Documentation/scheduler/sched-deadline.txt
> @@ -160,7 +160,8 @@ CONTENTS
>   maximum tardiness of each task is smaller or equal than
>  	((M − 1) · WCET_max − WCET_min)/(M − (M − 2) · U_max) + WCET_max
>   where WCET_max = max_i{WCET_i} is the maximum WCET, WCET_min=min_i{WCET_i}
> - is the minimum WCET, and U_max = max_i{WCET_i/P_i} is the maximum utilisation.
> + is the minimum WCET, and U_max = max_i{WCET_i/P_i} is the maximum
> + utilisation[12].
>  
>   If M=1 (uniprocessor system), or in case of partitioned scheduling (each
>   real-time task is statically assigned to one and only one CPU), it is
> @@ -202,15 +203,52 @@ CONTENTS
>  
>   On multiprocessor systems with global EDF scheduling (non partitioned
>   systems), a sufficient test for schedulability can not be based on the
> - utilisations (it can be shown that task sets with utilisations slightly
> - larger than 1 can miss deadlines regardless of the number of CPUs M).
> - However, as previously stated, enforcing that the total utilisation is 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.
> -
> - SCHED_DEADLINE can be used to schedule real-time tasks guaranteeing that
> - the jobs' deadlines of a task are respected. In order to do this, a task
> - must be scheduled by setting:
> + utilisations or densities: it can be shown that even if D_i = P_i task
> + sets with utilisations slightly larger than 1 can miss deadlines regardless
> + of the number of CPUs.

+ \newline (add som breathing space)

> + For example, consider a M tasks {Task_1,...Task_M} scheduled on M - 1

Please consider rewriting this to

"Consinder a set of M+1 tasks on a system with M CPUs [...]"

As 'M' is normally used to denote the number of cores available and it is 
much easier to grasp the context of "<some number> + 1" rather than "<some 
number - 1"-CPUs.

> + CPUs, with the first M - 1 tasks having a small worst case execution time
> + WCET_i=e and period equal to relative deadline P_i=D_i=P-1. The last task

Normally, 'e' is used to denote an _arbitrarily_ small value, and I suspect 
that this is indeed the case here as well (you're going to describe 
Dhall's effect, right?). Perhaps make that point explicit?

     T_i = {P_i, e, P_i}

> + (Task_M) has period, relative deadline and worst case execution time
> + equal to P: P_M=D_M=WCET_M=P. 

      T_M = {P, P, P}


> + If all the tasks activate at the
> + same time t, global EDF schedules the first M - 1 tasks first (because
> + their absolute deadlines are equal to t + P - 1, hence they are smaller
> + than the absolute deadline of Task_M, which is t + P). As a result, Task_M
> + can be scheduled only at time t + e, and will finish at time t + e + P,
> + after its absolute deadline t + P. The total utilisation of the task set
                                ^^^^^^
 Drop this, the text is full of equations as it is.

> + is (M - 1) · e / (P - 1) + P / P = (M - 1) · e / (P - 1) + 1, and for
> + small values of e this can become very close to 1. This is known as "Dhall's
> + effect"[7].

This gives the impression that 'e' must be constant, but all it really 
means is that e is an 'arbitrarily small value which can be *almost* 0' and 
that they will be picked _before_ the heavy task by EDF.

> + More complex schedulability tests for global EDF have been developed in
> + real-time literature[8,9], but they are not based on a simple comparison
> + between total utilisation (or density) and a fixed constant. If all tasks
> + have D_i = P_i, a sufficient schedulability condition can be expressed in
> + a simple way:
> +	sum_i WCET_i / P_i <= M - (M - 1) · U_max

sum_i; as stated in another comment, just juse 'sum' (IMHO)

> + 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.

> + If an admission test is used to guarantee that the scheduling deadlines are
> + respected, then SCHED_DEADLINE can be used to schedule real-time tasks
> + guaranteeing that the jobs' deadlines of a task are respected.
> + In order to do this, a task must be scheduled by setting:
>  
>    - runtime >= WCET
>    - deadline = D
> @@ -242,6 +280,29 @@ CONTENTS
>        Concerning the Preemptive Scheduling of Periodic Real-Time tasks on
>        One Processor. Real-Time Systems Journal, vol. 4, no. 2, pp 301-324,
>        1990.
> +  7 - S. J. Dhall and C. L. Liu. On a real-time scheduling problem. Operations
> +      research, vol. 26, no. 1, pp 127-140, 1978.
> +  8 - T. Baker. Multiprocessor EDF and Deadline Monotonic Schedulability
> +      Analysis. Proceedings of the 24th IEEE Real-Time Systems Symposium, 2003.
> +  9 - T. Baker. An Analysis of EDF Schedulability on a Multiprocessor.
> +      IEEE Transactions on Parallel and Distributed Systems, vol. 16, no. 8,
> +      pp 760-768, 2005.
> +  10 - J. Goossens, S. Funk and S. Baruah, Priority-Driven Scheduling of
> +       Periodic Task Systems on Multiprocessors. Real-Time Systems Journal,
> +       vol. 25, no. 2–3, pp. 187–205, 2003.
> +  11 - R. Davis and A. Burns. A Survey of Hard Real-Time Scheduling for
> +       Multiprocessor Systems. ACM Computing Surveys, vol. 43, no. 4, 2011.
> +       http://www-users.cs.york.ac.uk/~robdavis/papers/MPSurveyv5.0.pdf
> +  12 - U. C. Devi and J. H. Anderson. Tardiness Bounds under Global EDF
> +       Scheduling on a Multiprocessor. Real-Time Systems Journal, vol. 32,
> +       no. 2, pp 133-189, 2008.
> +  13 - P. Valente and G. Lipari. An Upper Bound to the Lateness of Soft
> +       Real-Time Tasks Scheduled by EDF on Multiprocessors. Proceedings of
> +       the 26th IEEE Real-Time Systems Symposium, 2005.
> +  14 - J. Erickson, U. Devi and S. Baruah. Improved tardiness bounds for
> +       Global EDF. Proceedings of the 22nd Euromicro Conference on
> +       Real-Time Systems, 2010.
> +
>  
>  4. Bandwidth management
>  =======================
> -- 
> 1.7.9.5
> 

-- 
Henrik Austad
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/