Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S935226AbbDIKGY (ORCPT ); Thu, 9 Apr 2015 06:06:24 -0400 Received: from mail2.unitn.it ([193.205.194.22]:58388 "EHLO mail2.unitn.it" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S933160AbbDIKF7 (ORCPT ); Thu, 9 Apr 2015 06:05:59 -0400 Message-ID: <55264F02.20501@unitn.it> Date: Thu, 09 Apr 2015 12:05:54 +0200 From: Luca Abeni User-Agent: Mozilla/5.0 (X11; Linux i686; rv:31.0) Gecko/20100101 Thunderbird/31.6.0 MIME-Version: 1.0 To: Henrik Austad CC: peterz@infradead.org, juri.lelli@gmail.com, raistlin@linux.it, mingo@kernel.org, linux-kernel@vger.kernel.org, linux-doc@vger.kernel.org Subject: Re: [RFC 4/4] Documentation/scheduler/sched-deadline.txt: add some references References: <1428494380-1917-1-git-send-email-luca.abeni@unitn.it> <1428494380-1917-5-git-send-email-luca.abeni@unitn.it> <20150409093908.GB10954@sisyphus.home.austad.us> In-Reply-To: <20150409093908.GB10954@sisyphus.home.austad.us> Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 6902 Lines: 149 Hi Henrik, On 04/09/2015 11:39 AM, Henrik Austad wrote: [...] >> - 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) Ok > >> + 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 " + 1" rather than " number - 1"-CPUs. Yes, this is what I originally wrote (and is the example I teach to students: http://disi.unitn.it/~abeni/RTOS/multiprocessor.pdf, slide 7). But then I re-read the original paper, and I see Dhall used m tasks (and n CPUs, just to confuse people :). So I rewrote the example in this way... Also because in this way the last task is Task_M, instead of Task_{M+1} which would make the notation more complex (because of the _{M+1}). But I can rewrite using M+1 tasks and M 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 Right. This was a \epsilon in the original paper (actually, Dhall used 2\epsilon and I decided to simplify things a little bit). > (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} Ok >> + 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. Ok > >> + 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' Right. The original paper uses "\lim_{\epsilon -> 0} ...", but I decided to simplify the description (maybe I oversimplified?). A constant and small e should be ok to give an intuition of Dhall's effect: if e becomes very small, the utilisation becomes very near to 1. But if you think this confuses the reader, I can add a note about \lim_{e -> 0} > and that they will be picked _before_ the heavy task by EDF. Right. This is because these tasks have period (and relative deadline) equal to P-1. >> + 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) Ok; if other people agree, I'll add a patch to the patchset to convert all the "sum_" into "sum". >> + 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). 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. Thanks, Luca -- 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/