Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S932989AbbDJKV7 (ORCPT ); Fri, 10 Apr 2015 06:21:59 -0400 Received: from mail2.unitn.it ([193.205.194.22]:56942 "EHLO mail2.unitn.it" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1754539AbbDJKUL (ORCPT ); Fri, 10 Apr 2015 06:20:11 -0400 From: Luca Abeni To: 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, Luca Abeni Subject: [PATCH 5/8] Documentation/scheduler/sched-deadline.txt: Some notes on EDF schedulability Date: Fri, 10 Apr 2015 12:19:52 +0200 Message-Id: <1428661195-9609-6-git-send-email-luca.abeni@unitn.it> X-Mailer: git-send-email 1.7.9.5 In-Reply-To: <1428661195-9609-1-git-send-email-luca.abeni@unitn.it> References: <1428661195-9609-1-git-send-email-luca.abeni@unitn.it> Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 5246 Lines: 92 Add a short discussion about sufficient and necessary schedulability tests, and a simple example showing that if D_i != P_i then density based tests are only sufficient. Also add some references to scientific papers on schedulability tests for EDF that are both necessary and sufficient, and on their computational complexity. --- Documentation/scheduler/sched-deadline.txt | 46 +++++++++++++++++++++++++--- 1 file changed, 42 insertions(+), 4 deletions(-) diff --git a/Documentation/scheduler/sched-deadline.txt b/Documentation/scheduler/sched-deadline.txt index c52e635..9663d53 100644 --- a/Documentation/scheduler/sched-deadline.txt +++ b/Documentation/scheduler/sched-deadline.txt @@ -137,10 +137,12 @@ CONTENTS A real-time task can be periodic with period P if r_{j+1} = r_j + P, or sporadic with minimum inter-arrival time P is r_{j+1} >= r_j + P. Finally, d_j = r_j + D, where D is the task's relative deadline. + Summing up, a real-time task can be described as + Task = (WCET, D, P) + The utilisation of a real-time task is defined as the ratio between its WCET and its period (or minimum inter-arrival time), and represents the fraction of CPU time needed to execute the task. - If the total utilisation U=sum(WCET_i/P_i) is larger than M (with M equal to the number of CPUs), then the scheduler is unable to respect all the deadlines. @@ -170,9 +172,35 @@ CONTENTS of the tasks running on such a CPU is smaller or equal than 1. If D_i != P_i for some task, then it is possible to define the density of a task as WCET_i/min{D_i,P_i}, and EDF is able to respect all the deadlines - of all the tasks running on a CPU if the sum sum(WCET_i/min{D_i,P_i}) of the - densities of the tasks running on such a CPU is smaller or equal than 1 - (notice that this condition is only sufficient, and not necessary). + of all the tasks running on a CPU if the sum of the densities of the tasks + running on such a CPU is smaller or equal than 1: + sum(WCET_i / min{D_i, P_i}) <= 1 + It is important to notice that this condition is only sufficient, and not + necessary: there are task sets that are schedulable, but do not respect the + condition. For example, consider the task set {Task_1,Task_2} composed by + Task_1=(50ms,50ms,100ms) and Task_2=(10ms,100ms,100ms). + EDF is clearly able to schedule the two tasks without missing any deadline + (Task_1 is scheduled as soon as it is released, and finishes just in time + to respect its deadline; Task_2 is scheduled immediately after Task_1, hence + its response time cannot be larger than 50ms + 10ms = 60ms) even if + 50 / min{50,100} + 10 / min{100, 100} = 50 / 50 + 10 / 100 = 1.1 + Of course it is possible to test the exact schedulability of tasks with + D_i != P_i (checking a condition that is both sufficient and necessary), + but this cannot be done by comparing the total utilisation or density with + a constant. Instead, the so called "processor demand" approach can be used, + computing the total amount of CPU time h(t) needed by all the tasks to + respect all of their deadlines in a time interval of size t, and comparing + such a time with the interval size t. If h(t) is smaller than t (that is, + the amount of time needed by the tasks in a time interval of size t is + smaller than the size of the interval) for all the possible values of t, then + EDF is able to schedule the tasks respecting all of their deadlines. Since + performing this check for all possible values of t is impossible, it has been + proven[4,5,6] that it is sufficient to perform the test for values of t + between 0 and a maximum value L. The cited papers contain all of the + mathematical details and explain how to compute h(t) and L. + In any case, this kind of analysis is too complex as well as too + time-consuming to be performed on-line. Hence, as explained in Section + 4 Linux uses an admission test based on the tasks' utilisations. On multiprocessor systems with global EDF scheduling (non partitioned systems), a sufficient test for schedulability can not be based on the @@ -206,6 +234,16 @@ CONTENTS Symposium, 1998. http://retis.sssup.it/~giorgio/paps/1998/rtss98-cbs.pdf 3 - L. Abeni. Server Mechanisms for Multimedia Applications. ReTiS Lab Technical Report. http://disi.unitn.it/~abeni/tr-98-01.pdf + 4 - J. Y. Leung and M.L. Merril. A Note on Preemptive Scheduling of + Periodic, Real-Time Tasks. Information Processing Letters, vol. 11, + no. 3, pp. 115-118, 1980. + 5 - S. K. Baruah, A. K. Mok and L. E. Rosier. Preemptively Scheduling + Hard-Real-Time Sporadic Tasks on One Processor. Proceedings of the + 11th IEEE Real-time Systems Symposium, 1990. + 6 - S. K. Baruah, L. E. Rosier and R. R. Howell. Algorithms and Complexity + Concerning the Preemptive Scheduling of Periodic Real-Time tasks on + One Processor. Real-Time Systems Journal, vol. 4, no. 2, pp 301-324, + 1990. 4. Bandwidth management ======================= -- 1.7.9.5 -- 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/