Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1640232

Re: [PATCH v2 2/3] sched/deadline: Throttle the task when missing its deadline

Show all headers | View raw

On 05/12/2017 at 01:57 PM, luca abeni wrote:
> Hi again,
>
> (sorry for the previous email; I replied from gmail and I did not
> realize I was sending it in html).
>
>
> On Fri, 12 May 2017 11:32:08 +0800
> Xunlei Pang <xlpang@redhat.com> wrote:
>
>> dl_runtime_exceeded() only checks negative runtime, actually
>> when the current deadline past, we should start a new period
>> and zero out the remaining runtime as well.
> In this case, I think global EDF wants to allow the task to run with
> its remaining runtime even also missing a deadline, so I think this
> change is not correct.
> (when using global EDF, tasks scheduled on multiple CPUs can miss their
> deadlines... Setting the runtime to 0 as soon as a deadline is missed
> would break global EDF scheduling)

Hi Luca,

Thanks for the comment, looks like I neglected the theoretical analysis.

Cited from Documentation/scheduler/sched-deadline.txt:
 "As a matter of fact, in this case it is possible to provide an upper bound
 for tardiness (defined as the maximum between 0 and the difference
 between the finishing time of a job and its absolute deadline).
 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_m
 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[12]."

And
 "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."

Do you mean there is some tardiness allowed in theory(global EDF is not an
optimal scheduling algorithm), thus missed deadline is allowed for global EDF?

>
> Which kind of issue is this patch fixing? If it is something you saw
> with deadline-constrained tasks, maybe you can add a check for
> deadline!=period?

No, It's an issue(I thought so back then) during making the last patch.

Regards,
Xunlei

>
> 				Luca
>> This patch improves dl_runtime_exceeded() to achieve that.
>>
>> Fixes: 269ad8015a6b ("sched/deadline: Avoid double-accounting in case
>> of missed deadlines") Cc: Luca Abeni <luca.abeni@unitn.it>
>> Signed-off-by: Xunlei Pang <xlpang@redhat.com>
>> ---
>>  kernel/sched/deadline.c | 9 +++++++--
>>  1 file changed, 7 insertions(+), 2 deletions(-)
>>
>> diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
>> index d3d291e..5691149 100644
>> --- a/kernel/sched/deadline.c
>> +++ b/kernel/sched/deadline.c
>> @@ -729,8 +729,13 @@ static inline void
>> dl_check_constrained_dl(struct sched_dl_entity *dl_se) }
>>  
>>  static
>> -int dl_runtime_exceeded(struct sched_dl_entity *dl_se)
>> +int dl_runtime_exceeded(struct rq *rq, struct sched_dl_entity *dl_se)
>>  {
>> +	bool dmiss = dl_time_before(dl_se->deadline, rq_clock(rq));
>> +
>> +	if (dmiss && dl_se->runtime > 0)
>> +		dl_se->runtime = 0;
>> +
>>  	return (dl_se->runtime <= 0);
>>  }
>>  
>> @@ -781,7 +786,7 @@ static void update_curr_dl(struct rq *rq)
>>  	dl_se->runtime -= delta_exec;
>>  
>>  throttle:
>> -	if (dl_runtime_exceeded(dl_se) || dl_se->dl_yielded) {
>> +	if (dl_runtime_exceeded(rq, dl_se) || dl_se->dl_yielded) {
>>  		dl_se->dl_throttled = 1;
>>  		__dequeue_task_dl(rq, curr, 0);
>>  		if (unlikely(dl_se->dl_boosted
>> || !start_dl_timer(curr)))

Back to linux.kernel | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

[PATCH v2 2/3] sched/deadline: Throttle the task when missing its deadline Xunlei Pang <xlpang@redhat.com> - 2017-05-12 05:40 +0200
  Re: [PATCH v2 2/3] sched/deadline: Throttle the task when missing  its deadline luca abeni <luca.abeni@santannapisa.it> - 2017-05-12 08:00 +0200
    Re: [PATCH v2 2/3] sched/deadline: Throttle the task when missing its  deadline Xunlei Pang <xpang@redhat.com> - 2017-05-12 09:00 +0200
      Re: [PATCH v2 2/3] sched/deadline: Throttle the task when missing  its deadline luca abeni <luca.abeni@santannapisa.it> - 2017-05-12 09:10 +0200
        Re: [PATCH v2 2/3] sched/deadline: Throttle the task when missing its  deadline Xunlei Pang <xpang@redhat.com> - 2017-05-12 09:20 +0200
          Re: [PATCH v2 2/3] sched/deadline: Throttle the task when missing  its deadline luca abeni <luca.abeni@santannapisa.it> - 2017-05-12 23:00 +0200
            Re: [PATCH v2 2/3] sched/deadline: Throttle the task when missing its  deadline Xunlei Pang <xpang@redhat.com> - 2017-05-15 05:50 +0200

csiph-web