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

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:   Fri, 12 May 2017 14:53:33 +0800
From:   Xunlei Pang <xpang@...hat.com>
To:     luca abeni <luca.abeni@...tannapisa.it>,
        Xunlei Pang <xlpang@...hat.com>
Cc:     linux-kernel@...r.kernel.org,
        Peter Zijlstra <peterz@...radead.org>,
        Juri Lelli <juri.lelli@....com>,
        Ingo Molnar <mingo@...hat.com>,
        Steven Rostedt <rostedt@...dmis.org>,
        Daniel Bristot de Oliveira <bristot@...hat.com>,
        Luca Abeni <luca.abeni@...tn.it>
Subject: Re: [PATCH v2 2/3] sched/deadline: Throttle the task when missing its
 deadline

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@...hat.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@...tn.it>
>> Signed-off-by: Xunlei Pang <xlpang@...hat.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)))