Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1755542AbbESHZr (ORCPT ); Tue, 19 May 2015 03:25:47 -0400 Received: from terminus.zytor.com ([198.137.202.10]:60625 "EHLO terminus.zytor.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753855AbbESHZm (ORCPT ); Tue, 19 May 2015 03:25:42 -0400 Date: Tue, 19 May 2015 00:25:07 -0700 From: tip-bot for Luca Abeni Message-ID: Cc: linux-kernel@vger.kernel.org, peterz@infradead.org, luca.abeni@unitn.it, mingo@kernel.org, tglx@linutronix.de, torvalds@linux-foundation.org, hpa@zytor.com Reply-To: peterz@infradead.org, linux-kernel@vger.kernel.org, tglx@linutronix.de, hpa@zytor.com, torvalds@linux-foundation.org, luca.abeni@unitn.it, mingo@kernel.org In-Reply-To: <1431954032-16473-7-git-send-email-luca.abeni@unitn.it> References: <1431954032-16473-7-git-send-email-luca.abeni@unitn.it> To: linux-tip-commits@vger.kernel.org Subject: [tip:sched/core] sched/dl/Documentation: Add some notes on EDF schedulability Git-Commit-ID: e0deda8142a60e4a39d5ba2ea47294a851b4309a X-Mailer: tip-git-log-daemon Robot-ID: Robot-Unsubscribe: Contact to get blacklisted from these emails MIME-Version: 1.0 Content-Transfer-Encoding: 8bit Content-Type: text/plain; charset=UTF-8 Content-Disposition: inline Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 5883 Lines: 106 Commit-ID: e0deda8142a60e4a39d5ba2ea47294a851b4309a Gitweb: http://git.kernel.org/tip/e0deda8142a60e4a39d5ba2ea47294a851b4309a Author: Luca Abeni AuthorDate: Mon, 18 May 2015 15:00:29 +0200 Committer: Ingo Molnar CommitDate: Tue, 19 May 2015 08:39:20 +0200 sched/dl/Documentation: Add some notes on EDF schedulability Add a short discussion about sufficient and necessary schedulability tests, and add 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. Signed-off-by: Luca Abeni Signed-off-by: Peter Zijlstra (Intel) Cc: Linus Torvalds Cc: Peter Zijlstra Cc: Thomas Gleixner Cc: henrik@austad.us Cc: juri.lelli@gmail.com Cc: raistlin@linux.it Link: http://lkml.kernel.org/r/1431954032-16473-7-git-send-email-luca.abeni@unitn.it Signed-off-by: Ingo Molnar --- Documentation/scheduler/sched-deadline.txt | 45 ++++++++++++++++++++++++++++-- 1 file changed, 42 insertions(+), 3 deletions(-) diff --git a/Documentation/scheduler/sched-deadline.txt b/Documentation/scheduler/sched-deadline.txt index c794ebf..bd4123b 100644 --- a/Documentation/scheduler/sched-deadline.txt +++ b/Documentation/scheduler/sched-deadline.txt @@ -137,6 +137,9 @@ 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 utilization 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. @@ -170,9 +173,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 utilization 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' utilizations. On multiprocessor systems with global EDF scheduling (non partitioned systems), a sufficient test for schedulability can not be based on the @@ -206,6 +235,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 ======================= -- 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/