Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1755531AbbESHZX (ORCPT ); Tue, 19 May 2015 03:25:23 -0400 Received: from terminus.zytor.com ([198.137.202.10]:60615 "EHLO terminus.zytor.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1754762AbbESHZT (ORCPT ); Tue, 19 May 2015 03:25:19 -0400 Date: Tue, 19 May 2015 00:24:49 -0700 From: tip-bot for Luca Abeni Message-ID: Cc: torvalds@linux-foundation.org, mingo@kernel.org, luca.abeni@unitn.it, tglx@linutronix.de, peterz@infradead.org, linux-kernel@vger.kernel.org, hpa@zytor.com Reply-To: luca.abeni@unitn.it, tglx@linutronix.de, mingo@kernel.org, torvalds@linux-foundation.org, hpa@zytor.com, linux-kernel@vger.kernel.org, peterz@infradead.org In-Reply-To: <1431954032-16473-6-git-send-email-luca.abeni@unitn.it> References: <1431954032-16473-6-git-send-email-luca.abeni@unitn.it> To: linux-tip-commits@vger.kernel.org Subject: [tip:sched/core] sched/dl/Documentation: Clarify indexing notation Git-Commit-ID: c2a684930fce07f19d1a52d7bbe7474fe64fde31 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: 3850 Lines: 73 Commit-ID: c2a684930fce07f19d1a52d7bbe7474fe64fde31 Gitweb: http://git.kernel.org/tip/c2a684930fce07f19d1a52d7bbe7474fe64fde31 Author: Luca Abeni AuthorDate: Mon, 18 May 2015 15:00:28 +0200 Committer: Ingo Molnar CommitDate: Tue, 19 May 2015 08:39:20 +0200 sched/dl/Documentation: Clarify indexing notation The "_i" index is used in this document to to denote a particular task, so "sum_i", "max_i" and "min_i" might be confusing. 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-6-git-send-email-luca.abeni@unitn.it Signed-off-by: Ingo Molnar --- Documentation/scheduler/sched-deadline.txt | 10 +++++----- 1 file changed, 5 insertions(+), 5 deletions(-) diff --git a/Documentation/scheduler/sched-deadline.txt b/Documentation/scheduler/sched-deadline.txt index 73ef489..c794ebf 100644 --- a/Documentation/scheduler/sched-deadline.txt +++ b/Documentation/scheduler/sched-deadline.txt @@ -133,7 +133,7 @@ CONTENTS arrival time r_j (the time when the job starts), an amount of computation time c_j needed to finish the job, and a job absolute deadline d_j, which is the time within which the job should be finished. The maximum execution - time max_j{c_j} is called "Worst Case Execution Time" (WCET) for the task. + time max{c_j} is called "Worst Case Execution Time" (WCET) for the task. 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. @@ -141,7 +141,7 @@ CONTENTS WCET and its period (or minimum inter-arrival time), and represents the fraction of CPU time needed to execute the task. - If the total utilization sum_i(WCET_i/P_i) is larger than M (with M equal + If the total utilization 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. Note that total utilization is defined as the sum of the utilizations @@ -159,8 +159,8 @@ CONTENTS More precisely, it can be proven that using a global EDF scheduler the 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 utilization. + 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. 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 @@ -170,7 +170,7 @@ 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_i WCET_i/min{D_i,P_i} of the + 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). -- 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/