Message-ID: <552642CF.7090405@unitn.it>
Date:	Thu, 09 Apr 2015 11:13:51 +0200
From:	Luca Abeni <luca.abeni@...tn.it>
To:	Juri Lelli <juri.lelli@....com>, Luca Abeni <lucabe72@...il.com>,
	"peterz@...radead.org" <peterz@...radead.org>
CC:	"henrik@...tad.us" <henrik@...tad.us>,
	"juri.lelli@...il.com" <juri.lelli@...il.com>,
	"raistlin@...ux.it" <raistlin@...ux.it>,
	"mingo@...nel.org" <mingo@...nel.org>,
	"linux-kernel@...r.kernel.org" <linux-kernel@...r.kernel.org>,
	"linux-doc@...r.kernel.org" <linux-doc@...r.kernel.org>
Subject: Re: [RFC 4/4] Documentation/scheduler/sched-deadline.txt: add some
 references

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@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Powered by blists - more mailing lists