Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S964830AbbDIJOD (ORCPT ); Thu, 9 Apr 2015 05:14:03 -0400 Received: from mail2.unitn.it ([193.205.194.22]:54004 "EHLO mail2.unitn.it" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S932757AbbDIJNy (ORCPT ); Thu, 9 Apr 2015 05:13:54 -0400 Message-ID: <552642CF.7090405@unitn.it> Date: Thu, 09 Apr 2015 11:13:51 +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: Juri Lelli , Luca Abeni , "peterz@infradead.org" CC: "henrik@austad.us" , "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> <55263732.1040702@arm.com> In-Reply-To: <55263732.1040702@arm.com> 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: 7513 Lines: 137 Hi Juri, thanks for the review! I am fixing these issues locally. Thanks, Luca On 04/09/2015 10:24 AM, Juri Lelli wrote: > On 08/04/15 12:59, 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. >> + For example, consider a M tasks {Task_1,...Task_M} scheduled on M - 1 > ^ > s/a// >> + 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 > ^ > and equal to P-1: > > It seemed confusing to me as it is right now. > >> + (Task_M) has period, relative deadline and worst case execution time >> + equal to P: P_M=D_M=WCET_M=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 >> + 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]. >> + 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 >> + 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). >> + 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 >> ======================= >> > -- 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/