Re: [PATCH] sched/deadline: Throttle a constrained task activated if overflow

[Xunlei Pang <xpang@redhat.com>]

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;
        }
 }