Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1755559AbbESH0K (ORCPT ); Tue, 19 May 2015 03:26:10 -0400 Received: from terminus.zytor.com ([198.137.202.10]:60657 "EHLO terminus.zytor.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1754624AbbESH0H (ORCPT ); Tue, 19 May 2015 03:26:07 -0400 Date: Tue, 19 May 2015 00:25:27 -0700 From: tip-bot for Luca Abeni Message-ID: Cc: tglx@linutronix.de, hpa@zytor.com, luca.abeni@unitn.it, linux-kernel@vger.kernel.org, mingo@kernel.org, peterz@infradead.org, torvalds@linux-foundation.org Reply-To: mingo@kernel.org, peterz@infradead.org, torvalds@linux-foundation.org, tglx@linutronix.de, hpa@zytor.com, luca.abeni@unitn.it, linux-kernel@vger.kernel.org In-Reply-To: <1431954032-16473-8-git-send-email-luca.abeni@unitn.it> References: <1431954032-16473-8-git-send-email-luca.abeni@unitn.it> To: linux-tip-commits@vger.kernel.org Subject: [tip:sched/core] sched/dl/Documentation: Add some references Git-Commit-ID: 134136c4b730c1a4830a8b74e2717d858291361b 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: 7118 Lines: 130 Commit-ID: 134136c4b730c1a4830a8b74e2717d858291361b Gitweb: http://git.kernel.org/tip/134136c4b730c1a4830a8b74e2717d858291361b Author: Luca Abeni AuthorDate: Mon, 18 May 2015 15:00:30 +0200 Committer: Ingo Molnar CommitDate: Tue, 19 May 2015 08:39:21 +0200 sched/dl/Documentation: Add some references Add a description of the Dhall's effect, some discussion about schedulability tests for global EDF, and references to real-time literature. 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-8-git-send-email-luca.abeni@unitn.it Signed-off-by: Ingo Molnar --- Documentation/scheduler/sched-deadline.txt | 73 +++++++++++++++++++++++++++--- 1 file changed, 67 insertions(+), 6 deletions(-) diff --git a/Documentation/scheduler/sched-deadline.txt b/Documentation/scheduler/sched-deadline.txt index bd4123b..984a01d 100644 --- a/Documentation/scheduler/sched-deadline.txt +++ b/Documentation/scheduler/sched-deadline.txt @@ -163,7 +163,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{WCET_i} is the maximum WCET, WCET_min=min{WCET_i} - is the minimum WCET, and U_max = max{WCET_i/P_i} is the maximum utilization. + is the minimum WCET, and U_max = max{WCET_i/P_i} is the maximum + utilization[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 @@ -205,11 +206,48 @@ CONTENTS On multiprocessor systems with global EDF scheduling (non partitioned systems), a sufficient test for schedulability can not be based on the - utilizations (it can be shown that task sets with utilizations slightly - larger than 1 can miss deadlines regardless of the number of CPUs M). - However, as previously stated, enforcing that the total utilization 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. + utilizations or densities: it can be shown that even if D_i = P_i task + sets with utilizations slightly larger than 1 can miss deadlines regardless + of the number of CPUs. + + Consider a set {Task_1,...Task_{M+1}} of M+1 tasks on a system with M + CPUs, with the first task Task_1=(P,P,P) having period, relative deadline + and WCET equal to P. The remaining M tasks Task_i=(e,P-1,P-1) have an + arbitrarily small worst case execution time (indicated as "e" here) and a + period smaller than the one of the first task. Hence, if all the tasks + activate at the same time t, global EDF schedules these M tasks first + (because their absolute deadlines are equal to t + P - 1, hence they are + smaller than the absolute deadline of Task_1, which is t + P). As a + result, Task_1 can be scheduled only at time t + e, and will finish at + time t + e + P, after its absolute deadline. The total utilization of the + task set is U = M · e / (P - 1) + P / P = M · 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]. Note: the example in the original paper by Dhall has been + slightly simplified here (for example, Dhall more correctly computed + lim_{e->0}U). + + 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 utilization (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(WCET_i / P_i) <= M - (M - 1) · U_max + where U_max = max{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 utilization 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 utilization 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 noted). 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 utilization is smaller or equal than M then the response times of + the tasks are limited. 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 @@ -245,6 +283,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/