DMARC-Filter: OpenDMARC Filter v1.3.2 mx1.redhat.com 76231C04B948
Reply-To: xlpang@redhat.com
Subject: Re: [PATCH] sched/deadline: Throttle a constrained task activated if
 overflow
References: <1491816131-20268-1-git-send-email-xlpang@redhat.com>
 <4d24b94c-1e57-b82c-ff0f-099157ba5526@redhat.com>
 <58EC6F63.4070708@redhat.com> <58EC8065.6030806@redhat.com>
 <541883c2-a8bb-0b03-0987-292ee8b2b25e@redhat.com>
To: Daniel Bristot de Oliveira <bristot@redhat.com>, xlpang@redhat.com,
        linux-kernel@vger.kernel.org
Cc: Peter Zijlstra <peterz@infradead.org>, Juri Lelli <juri.lelli@arm.com>,
        Ingo Molnar <mingo@redhat.com>,
        Luca Abeni <luca.abeni@santannapisa.it>,
        Steven Rostedt <rostedt@goodmis.org>,
        Tommaso Cucinotta <tommaso.cucinotta@sssup.it>,
        =?UTF-8?Q?R=c3=b4mulo_Silva_de_Oliveira?= 
        <romulo.deoliveira@ufsc.br>,
        Mathieu Poirier <mathieu.poirier@linaro.org>
From: Xunlei Pang <xpang@redhat.com>
Message-ID: <58ED8C1D.9080402@redhat.com>
Date: Wed, 12 Apr 2017 10:08:29 +0800
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:38.0) Gecko/20100101
 Thunderbird/38.2.0
MIME-Version: 1.0
In-Reply-To: <541883c2-a8bb-0b03-0987-292ee8b2b25e@redhat.com>
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 7bit
Sender: linux-kernel-owner@vger.kernel.org
Content-Length: 6437
Lines: 137

On 04/11/2017 at 05:24 PM, Daniel Bristot de Oliveira wrote:
> On 04/11/2017 09:06 AM, Xunlei Pang wrote:
>> On 04/11/2017 at 01:53 PM, Xunlei Pang wrote:
>>> On 04/11/2017 at 04:47 AM, Daniel Bristot de Oliveira wrote:
>>>> On 04/10/2017 11:22 AM, Xunlei Pang wrote:
>>>>> I was testing Daniel's changes with his test case in the commit
>>>>> df8eac8cafce ("sched/deadline: Throttle a constrained deadline
>>>>> task activated after the deadline"), and tweaked it a little.
>>>>>
>>>>> Instead of having the runtime equal to the deadline, I tweaked
>>>>> runtime, deadline and sleep value to ensure every time it calls
>>>>> dl_check_constrained_dl() with "dl_se->deadline > rq_clock(rq)"
>>>>> as well as true dl_entity_overflow(), so it does replenishing
>>>>> every wake up in update_dl_entity(), and break its bandwidth.
>>>>>
>>>>> Daniel's test case had:
>>>>> attr.sched_runtime = 2 * 1000 * 1000; /* 2 ms */
>>>>> attr.sched_deadline = 2 * 1000 * 1000; /* 2 ms*/
>>>>> attr.sched_period = 2 * 1000 * 1000 * 1000; /* 2 s */
>>>>> ts.tv_sec = 0;
>>>>> ts.tv_nsec = 2000 * 1000; /* 2 ms */
>>>>>
>>>>> I changed it to:
>>>>> attr.sched_runtime = 5 * 1000 * 1000; /* 5 ms */
>>>>> attr.sched_deadline = 7 * 1000 * 1000; /* 7 ms */
>>>>> attr.sched_period = 1 * 1000 * 1000 * 1000; /* 1 s */
>>>>> ts.tv_sec = 0;
>>>>> ts.tv_nsec = 1000 * 1000; /* 1 ms */
>>>>>
>>>>> The change above can result in over 25% of the CPU on my machine.
>>>>>
>>>>> In order to avoid the beakage, we improve dl_check_constrained_dl()
>>>>> to prevent dl tasks from being activated until the next period if it
>>>>> runs out of bandwidth of the current period.
>>>> The problem now is that, with your patch, we will throttle the task
>>>> with some possible runtime. Moreover, the task did not brake any
>>>> rule, like being awakened after the deadline - the user-space is not
>>>> misbehaving.
>>>>
>>>> That is +- what the reproducer is doing when using your patch,
>>>> (I put some trace_printk when noticing the overflow in the wakeup).
>>>>
>>>>           <idle>-0     [007] d.h.  1505.066439: enqueue_task_dl: my current runtime is 3657361 and the deadline is 4613027 from now 
>>>>           <idle>-0     [007] d.h.  1505.066439: enqueue_task_dl: 	my dl_runtime is 5000000
>>>>
>>>> and so the task will be throttled with 3657361 ns runtime available.
>>>>
>>>> As we can see, it is really breaking the density:
>>>>
>>>> 5ms / 7ms (.714285) < 3657361 / 4613027 (.792833)
>>>>
>>>> Well, it is not breaking that much. Trying to be less pessimist, we can
>>>> compute a new runtime with following equation:
>>>>
>>>> runtime = (dl_runtime / dl_deadline) * (deadline - now)
>>>>
>>>> That is, a runtime which fits in the task's density.
>>> This is a good point, to make the best use of remaining deadline, let me think more.
>> I don't know if this will make things more complicated, we can see in update_dl_entity():
>>    if (dl_time_before(dl_se->deadline, rq_clock(rq)) ||
>>         dl_entity_overflow(dl_se, pi_se, rq_clock(rq))) {
>>         dl_se->deadline = rq_clock(rq) + pi_se->dl_deadline;
>>         dl_se->runtime = pi_se->dl_runtime;
>>     }
>>
>> Looks like we have similar issue for non-constrained tasks in case of true dl_entity_overflow(), although
>> its deadline is promoted(BTW, I think when overflow it should be dl_se->deadline += pi_se->dl_deadline?),
>> the previous runtime is discarded, we may need to apply the same runtime truncating logic on it as well
>> if we want to truncate runtime.
> For implicit deadline, the density is equals to the utilization.
> So things here are less pessimistic, and we are using the same
> rule for overflow and admission.
>
> If you push "dl_se->deadline += pi_se->dl_deadline", you will give
>
> runtime / (deadline - now) + period.
>
> runtime.
>
> As the deadline is in the future, (the !dl_time_before(dl_se->deadline,
> rq_clock(rq)), then (deadline - now) + period > period. Therefore, the
> next period will receive less than runtime / period & the task will
> receive a lower priority - a farther deadline.

Yes, I think I got your meaning, thanks for the detailed explanation.
This is indeed an issue, that's why I suggested to do truncate here as well.

But in the current implementation, promote deadline to "clock + pi_se->dl_deadline",
will cause overlapping between periods, kind of like
    [    period n   ]
                  [   period n+1 ]
the overlapped time window is (deadline -now), is this a problem?

>
> Well, we could not to truncate the runtime, but than we would carry
> things from the past. If the task self-suspended for a long
> period, the sum of the residual runtime + runtime could give
> a higher utilization than Q/P.
>
> Moreover, the current rule provides a guarantee that Tommaso likes.
> The CBS self-adjusts the period in the case of a timing drift of the
> external "event" that activates the task, without breaking Q/P.
>
> (He can explain more about it....)

Anyway implicit deadline has the same issue, image in update_dl_entity() when "deadline > rq_clock"
and true dl_entity_overflow(), it can run part of dl_se->runtime within (dl_se->deadline - rq_clock), no?
what do you think we truncate runtime in the common update_dl_entity()? Like:

diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
index a2ce590..e92aad6 100644
--- a/kernel/sched/deadline.c
+++ b/kernel/sched/deadline.c
@@ -497,11 +497,21 @@ static void update_dl_entity(struct sched_dl_entity *dl_se,
 {
        struct dl_rq *dl_rq = dl_rq_of_se(dl_se);
        struct rq *rq = rq_of_dl_rq(dl_rq);
+       u64 clock = rq_clock(rq);
 
-       if (dl_time_before(dl_se->deadline, rq_clock(rq)) ||
-           dl_entity_overflow(dl_se, pi_se, rq_clock(rq))) {
-               dl_se->deadline = rq_clock(rq) + pi_se->dl_deadline;
+       if (!dl_time_before(clock, dl_se->deadline)) {
+               dl_se->deadline = clock + pi_se->dl_deadline;
                dl_se->runtime = pi_se->dl_runtime;
+               return;
+       }
+
+       /* Truncate the runtime to fit the density in the current period after overflow. */
+       if (dl_entity_overflow(dl_se, pi_se, clock)) {
+               unsigned long ratio;
+
+               /* TODO: save the quotient in a variable like dl_se->dl_bw */
+               ratio = to_ratio(pi_se->dl_deadline, pi_se->dl_runtime);
+               dl_se->runtime = (ratio * (dl_se->deadline - clock)) >> 20;
        }
 }