sched/deadline: Fixes for constrained deadline tasks
v2 cover sched/deadline: Fixes for constrained deadline tasks
While reading sched deadline code, I find out that a constrained deadline task could be replenished before the next period if activated after the deadline, opening the window to run for more than Q/P. The patch [2] explains and fixes this problem.
Furthermore, while fixing this issue, I found that the replenishment timer was being fired at the deadline of the task. This works fine for implicit deadline tasks (deadline == period) because the deadline is at the same point in time of the next period. But that is not true for constrained deadline tasks (deadline < period). This problem is not as visible as the first because the runtime leakage takes place only in the second activation. Next activations receive the correct bandwidth. However, after the 2nd activation, tasks are activated in the (period - dl_deadline) instant, which is before the expected activation. This problem is explained in the fix description as well.
Changes from V1:
- Fix a broken comment style.
- Fixes dl_is_constrained():
A constrained deadline task has dl_deadline < dl_period; so
"dl_runtime < dl_period"; s/runtime/deadline/
Daniel Bristot de Oliveira (2):
sched/deadline: Replenishment timer should fire in the next period sched/deadline: Throttle a constrained deadline task activated after
the deadline
kernel/sched/deadline.c | 54 +++++++++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 52 insertions(+), 2 deletions(-)
Signature · 1 line
2.9.3
PATCH v2 1/2 sched/deadline: Replenishment timer should fire in the next period
Currently, the replenishment timer is set to fire at the deadline of a task. Although that works for implicit deadline tasks because the deadline is equals to the begin of the next period, that is not correct for constrained deadline tasks (deadline < period).
For instance:
f.c:
--------------- %< ---------------
int main (void)
{
for(;;);
}--------------- >% ---------------
# gcc -o f f.c
# trace-cmd record -e sched:sched_switch \
-e syscalls:sys_exit_sched_setattr \
chrt -d --sched-runtime 490000000 \
--sched-deadline 500000000 \
--sched-period 1000000000 0 ./f # trace-cmd report | grep "{pid of ./f}"After setting parameters, the task is replenished and continue running until being throttled.
f-11295 [003] 13322.113776: sys_exit_sched_setattr: 0x0
The task is throttled after running 492318 ms, as expected.
f-11295 [003] 13322.606094: sched_switch: f:11295 [-1] R ==> \ watchdog/3:32 [0]
But then, the task is replenished 500719 ms after the first replenishment:
<idle>-0 [003] 13322.614495: sched_switch: swapper/3:0 [120] R \ ==> f:11295 [-1]
Running for 490277 ms:
f-11295 [003] 13323.104772: sched_switch: f:11295 [-1] R ==> \ swapper/3:0 [120]
Hence, in the first period, the task runs 2 * runtime, and that is a bug.
During the first replenishment, the next deadline is set one period away. So the runtime / period starts to be respected. However, as the second replenishment took place in the wrong instant, the next replenishment will also be held in a wrong instant of time. Rather than occurring in the nth period away from the first activation, it is taking place in the (nth period - relative deadline).
--- kernel/sched/deadline.c | 9 +++++++-- 1 file changed, 7 insertions(+), 2 deletions(-)
kernel/sched/deadline.c +7 -2
@@ -505,10 +505,15 @@ static void update_dl_entity(struct sched_dl_entity *dl_se, } } +static inline u64 dl_next_period (struct sched_dl_entity *dl_se) +{ +return dl_se->deadline - dl_se->dl_deadline + dl_se->dl_period; +} +/* * If the entity depleted all its runtime, and if we want it to sleep * while waiting for some new execution time to become available, we -* set the bandwidth enforcement timer to the replenishment instant +* set the bandwidth replenishment timer to the replenishment instant * and try to activate it. * * Notice that it is important for the caller to know if the timer
@@ -530,7 +535,7 @@ static int start_dl_timer(struct task_struct *p)* that it is actually coming from rq->clock and not from * hrtimer's time base reading. */ - act =ns_to_ktime (dl_se->deadline); + act =ns_to_ktime (dl_next_period (dl_se)); now =hrtimer_cb_get_time (timer); delta =ktime_to_ns (now) -rq_clock (rq); act =ktime_add_ns (act, delta);
Signature · 1 line
2.9.3
PATCH v2 2/2 sched/deadline: Throttle a constrained deadline task activated after the deadline
In reply to Daniel Bristot de OliveiraDuring the activation, CBS checks if it can reuse the current task's runtime and period. If the deadline of the task is in the past, CBS cannot use the runtime, and so it replenishes the task. This rule works fine for implicit deadline tasks (deadline == period), and the CBS was designed for implicit deadline tasks. However, a task with constrained deadline (deadine < period) might be awakened after the deadline, but before the next period. In this case, replenishing the task would allow it to run for runtime / deadline. As in this case deadline < period, CBS enables a task to run for more than the runtime / period. In a very load system, this can cause the domino effect, making other tasks to miss their deadlines.
To avoid this problem, in the activation of a constrained deadline task after the deadline but before the next period, throttle the task and set the replenishing timer to the begin of the next period, unless it is boosted.
Reproducer:
--------------- %< ---------------
int main (int argc, char **argv)
{
int ret;
int flags = 0;
unsigned long l = 0;
struct timespec ts;
struct sched_attr attr;
memset(&attr, 0, sizeof(attr));
attr.size = sizeof(attr);
attr.sched_policy = SCHED_DEADLINE;
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 */
ret = sched_setattr(0, &attr, flags);
if (ret < 0) {
perror("sched_setattr");
exit(-1);
}
for(;;) {
/* XXX: you may need to adjust the loop */
for (l = 0; l < 150000; l++);
/*
* The ideia is to go to sleep right before the deadline
* and then wake up before the next period to receive
* a new replenishment.
*/
nanosleep(&ts, NULL);
}
exit(0); }
--------------- >% ---------------
On my box, this reproducer uses almost 50% of the CPU time, which is obviously wrong for a task with 2/2000 reservation.
--- kernel/sched/deadline.c | 45 +++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 45 insertions(+)
kernel/sched/deadline.c +45 -0
@@ -694,6 +694,37 @@ void init_dl_task_timer(struct sched_dl_entity *dl_se) timer->function = dl_task_timer; } +/* +* During the activation, CBS checks if it can reuse the current task's +* runtime and period. If the deadline of the task is in the past, CBS +* cannot use the runtime, and so it replenishes the task. This rule +* works fine for implicit deadline tasks (deadline == period), and the +* CBS was designed for implicit deadline tasks. However, a task with +* constrained deadline (deadine < period) might be awakened after the +* deadline, but before the next period. In this case, replenishing the +* task would allow it to run for runtime / deadline. As in this case +* deadline < period, CBS enables a task to run for more than the +* runtime / period. In a very load system, this can cause the domino +* effect, making other tasks to miss their deadlines. +* +* To avoid this problem, in the activation of a constrained deadline +* task after the deadline but before the next period, throttle the +* task and set the replenishing timer to the begin of the next period, +* unless it is boosted. +*/ +static inline void dl_check_constrained_dl (struct sched_dl_entity *dl_se) +{ +struct task_struct *p =dl_task_of (dl_se); +struct rq *rq =rq_of_dl_rq (dl_rq_of_se (dl_se)); + +if (dl_time_before (dl_se->deadline,rq_clock (rq)) && +dl_time_before (rq_clock (rq),dl_next_period (dl_se))) { +if (unlikely (dl_se->dl_boosted || !start_dl_timer (p))) +return ; + dl_se->dl_throttled =1 ; + } +} +static int dl_runtime_exceeded (struct sched_dl_entity *dl_se) {
@@ -927,6 +958,11 @@ static void dequeue_dl_entity(struct sched_dl_entity *dl_se)__dequeue_dl_entity (dl_se); } +static inline bool dl_is_constrained (struct sched_dl_entity *dl_se) +{ +return dl_se->dl_deadline < dl_se->dl_period; +} +static void enqueue_task_dl (struct rq *rq,struct task_struct *p,int flags) {struct task_struct *pi_task =rt_mutex_get_top_task (p);
@@ -953,6 +989,15 @@ static void enqueue_task_dl(struct rq *rq, struct task_struct *p, int flags) }/* +* Check if a constrained deadline task was activated +* after the deadline but before the next period. +* If that is the case, the task will be throttled and +* the replenishment timer will be set to the next period. +*/ +if (!pi_se->dl_throttled &&dl_is_constrained (pi_se)) +dl_check_constrained_dl (pi_se); + +/* * If p is throttled, we do nothing. In fact, if it exhausted * its budget it needs a replenishment and, since it now is on * its rq, the bandwidth timer callback (which clearly has not
Signature · 1 line
2.9.3
Re: [PATCH V2 2/2] sched/deadline: Throttle a constrained deadline task activated after the deadline
Quoted 4 lines · Daniel Bristot de Oliveira
To avoid this problem, in the activation of a constrained deadline task after the deadline but before the next period, throttle the task and set the replenishing timer to the begin of the next period, unless it is boosted.
my only comment is that, by throttling on (dl < wakeuptime < period), we force the app to sync its activation time with the kernel, and the cbs doesn't self-sync anymore with the app own periodicity, which is what normally happens with dl=period. With dl=period, we loose the cbs self-sync and we force the app to sync with the kernel periodic timer only if we use explicitly yield(), but now this becomes also implicit just if we set dl<period.
Quoted 4 lines
attr.sched_policy = SCHED_DEADLINE; 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 */
...
Quoted 2 lines
On my box, this reproducer uses almost 50% of the CPU time, which is obviously wrong for a task with 2/2000 reservation.
just a note here: in this example of runtime=deadline=2ms, shall we rely on a utilization-based test, then we should assume the task is taking 100%. More precise tests for EDF with deadline<period would properly count the 1998ms/2000ms free space, instead.
my2c,
T.
Signature · 4 lines
Tommaso Cucinotta, Computer Engineering PhD Associate Professor at the Real-Time Systems Laboratory (ReTiS) Scuola Superiore Sant'Anna, Pisa, Italy http://retis.sssup.it/people/tommaso
Re: [PATCH V2 2/2] sched/deadline: Throttle a constrained deadline task activated after the deadline
Quoted 6 lines · Tommaso Cucinotta
Quoted 4 lines · Daniel Bristot de Oliveira
To avoid this problem, in the activation of a constrained deadline task after the deadline but before the next period, throttle the task and set the replenishing timer to the begin of the next period, unless it is boosted.
Quoted 7 lines
my only comment is that, by throttling on (dl < wakeuptime < period), we force the app to sync its activation time with the kernel, and the cbs doesn't self-sync anymore with the app own periodicity, which is what normally happens with dl=period. With dl=period, we loose the cbs self-sync and we force the app to sync with the kernel periodic timer only if we use explicitly
yield(), but now this becomes also implicit just if we set dl<period.
I see your point. However, that will happen only if, for some external fact or imprecision, the task wakes up with a minimum inter-arrival time smaller than the dl_period. In such case, IMHO the user must be aware of the miss behavior or imprecision of the task/method which activates the task and set an appropriate/safer smaller dl_period.
Furthermore, (correct me if I am wrong...) CBS will self-sync implicit deadline tasks which did not consume all its previous runtime. Because, if the runtime was consumed, the wake-up will fall in the same case I am making constrained tasks to fall - the task will be throttled until the next replenishment, after the next period.
The idea is to simulate sched_yield(). By suspending itself further than the deadline, the task either has timing problems, or it wants to suspend itself until the next activation, like calling sched_yeild(), but allowing itself to be sporadic (to be activated after the minimum inter-arrival time).
Quoted 5 lines
Quoted 5 lines
attr.sched_policy = SCHED_DEADLINE; 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 */
Quoted 8 lines
...
Quoted 2 lines
On my box, this reproducer uses almost 50% of the CPU time, which is obviously wrong for a task with 2/2000 reservation.
just a note here: in this example of runtime=deadline=2ms, shall we rely on a utilization-based test, then we should assume the task is taking 100%. More precise tests for EDF with deadline<period would properly count the 1998ms/2000ms free space, instead.
Yeah, it is taking 100% for runtime/deadline. But the admission is runtime/period, so it will pass. The idea of runtime=deadline is to avoid the task being throttled. If the task is throttle we would not be able to demonstrate this bug. Anyway, we can set runtime = (0.95 * deadline), it will also reproduce the problem, as long as the task is put to sleep before being throttled.
Thanks!
-- Daniel
Re: [PATCH V2 2/2] sched/deadline: Throttle a constrained deadline task activated after the deadline
In reply to Daniel Bristot de OliveiraQuoted 64 lines · On Mon, 13 Feb 2017 20:05:58 +0100 Daniel Bristot de Oliveira…
During the activation, CBS checks if it can reuse the current task's runtime and period. If the deadline of the task is in the past, CBS cannot use the runtime, and so it replenishes the task. This rule works fine for implicit deadline tasks (deadline == period), and the CBS was designed for implicit deadline tasks. However, a task with constrained deadline (deadine < period) might be awakened after the deadline, but before the next period. In this case, replenishing the task would allow it to run for runtime / deadline. As in this case deadline < period, CBS enables a task to run for more than the runtime / period. In a very load system, this can cause the domino effect, making other tasks to miss their deadlines.
To avoid this problem, in the activation of a constrained deadline task after the deadline but before the next period, throttle the task and set the replenishing timer to the begin of the next period, unless it is boosted.
Reproducer:
--------------- %< ---------------
int main (int argc, char **argv){ int ret; int flags = 0; unsigned long l = 0; struct timespec ts; struct sched_attr attr; memset(&attr, 0, sizeof(attr)); attr.size = sizeof(attr); attr.sched_policy = SCHED_DEADLINE; 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 */ ret = sched_setattr(0, &attr, flags); if (ret < 0) { perror("sched_setattr"); exit(-1); } for(;;) { /* XXX: you may need to adjust the loop */ for (l = 0; l < 150000; l++); /* * The ideia is to go to sleep right before the deadline * and then wake up before the next period to receive * a new replenishment. */ nanosleep(&ts, NULL); } exit(0);}
--------------- >% ---------------On my box, this reproducer uses almost 50% of the CPU time, which is obviously wrong for a task with 2/2000 reservation.
Quoted 11 lines
Signed-off-by Daniel Bristot de Oliveira <[email protected]>Cc Ingo Molnar <[email protected]>Cc Peter Zijlstra <[email protected]>Cc Juri Lelli <[email protected]>Cc Tommaso Cucinotta <[email protected]>Cc Luca Abeni <[email protected]>Cc Steven Rostedt <[email protected]>Cc Mike Galbraith <[email protected]>Cc Romulo Silva de Oliveira <[email protected]>
-- Steve
Steven Rostedt (VMware)
reviewer[PATCH 3/2] sched/deadline: Use deadline instead of period when calculating overflow
In reply to Daniel Bristot de OliveiraI was testing Daniel's changes with his test case, and tweaked it a little. Instead of having the runtime equal to the deadline, I increased the deadline ten fold.
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 */
To make it more interesting, I changed it to:
attr.sched_runtime = 2 * 1000 * 1000; /* 2 ms */ attr.sched_deadline = 20 * 1000 * 1000; /* 20 ms */ attr.sched_period = 2 * 1000 * 1000 * 1000; /* 2 s */
The results were rather surprising. The behavior that Daniel's patch was fixing came back. The task started using much more than .1% of the CPU. More like 20%.
Looking into this I found that it was due to the dl_entity_overflow() constantly returning true. That's because it uses the relative period against relative runtime vs the absolute deadline against absolute runtime.
runtime / (deadline - t) > dl_runtime / dl_period
There's even a comment mentioning this, and saying that when relative deadline equals relative period, that the equation is the same as using deadline instead of period. That comment is backwards! What we really want is:
runtime / (deadline - t) > dl_runtime / dl_deadline
We care about if the runtime can make its deadline, not its period. And then we can say "when the deadline equals the period, the equation is the same as using dl_period instead of dl_deadline".
After correcting this, now when the task gets enqueued, it can throttle correctly, and Daniel's fix to the throttling of sleeping deadline tasks works even when the runtime and deadline are not the same.
---
kernel/sched/deadline.c +4 -4
@@ -445,13 +445,13 @@ static void replenish_dl_entity(struct s* * This function returns true if: * -* runtime / (deadline - t) > dl_runtime / dl_period , +* runtime / (deadline - t) > dl_runtime / dl_deadline , * * IOW we can't recycle current parameters. * -* Notice that the bandwidth check is done against the period. For +* Notice that the bandwidth check is done against the deadline. For * task with deadline equal to period this is the same of using -* dl_deadline instead of dl_period in the equation above. +* dl_period instead of dl_deadline in the equation above. */ static bool dl_entity_overflow (struct sched_dl_entity *dl_se,struct sched_dl_entity *pi_se,u64 t)
@@ -476,7 +476,7 @@ static bool dl_entity_overflow(struct sc* of anything below microseconds resolution is actually fiction * (but still we want to give the user that illusion >;). */ - left = (pi_se->dl_period >>DL_SCALE ) * (dl_se->runtime >>DL_SCALE ); + left = (pi_se->dl_deadline >>DL_SCALE ) * (dl_se->runtime >>DL_SCALE ); right = ((dl_se->deadline - t) >>DL_SCALE ) * (pi_se->dl_runtime >>DL_SCALE );
Re: [PATCH 3/2] sched/deadline: Use deadline instead of period when calculating overflow
Hi Steven,
Quoted 21 lines · On Tue, 14 Feb 2017 14:28:48 -0500 "Steven Rostedt (VMware)"…
I was testing Daniel's changes with his test case, and tweaked it a little. Instead of having the runtime equal to the deadline, I increased the deadline ten fold.
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 */To make it more interesting, I changed it to:
attr.sched_runtime = 2 * 1000 * 1000; /* 2ms */ attr.sched_deadline = 20 * 1000 * 1000; /* 20 ms
*/ attr.sched_period = 2 * 1000 * 1000 * 1000; /* 2 s */The results were rather surprising. The behavior that Daniel's patch was fixing came back. The task started using much more than .1% of the CPU. More like 20%.
Quoted 6 lines
Looking into this I found that it was due to the
dl_entity_overflow()constantly returning true. That's because it uses the relative period against relative runtime vs the absolute deadline against absolute runtime.runtime / (deadline - t) >
dl_runtime/dl_period
I agree that there is an inconsistency here (again, using equations from the "period=deadline" case with a relative deadline different from period).
I am not sure about the correct fix (wouldn't
"runtime / (deadline - t) > dl_runtime / dl_deadline" allow the task to use a fraction of CPU time equal to dl_runtime / dl_deadline?)
The current code is clearly wrong (as shown by Daniel), but I do not understand how the current check can allow the task to consume more than dl_runtime / dl_period... I need some more time to think about this issue.
Luca
Quoted 51 lines
There's even a comment mentioning this, and saying that when relative deadline equals relative period, that the equation is the same as using deadline instead of period. That comment is backwards! What we really want is:
runtime / (deadline - t) >
dl_runtime/dl_deadlineWe care about if the runtime can make its deadline, not its period. And then we can say "when the deadline equals the period, the equation is the same as using
dl_periodinstead ofdl_deadline".After correcting this, now when the task gets enqueued, it can throttle correctly, and Daniel's fix to the throttling of sleeping deadline tasks works even when the runtime and deadline are not the same.
Signed-off-by Steven Rostedt (VMware) <[email protected]>---
Index:linux-trace.git/kernel/sched/deadline.c
===================================================================kernel/sched/deadline.c +3
-3@@ -445,13 +445,13 @@ static void replenish_dl_entity(struct s* * This function returns true if: * -* runtime / (deadline - t) > dl_runtime / dl_period , +* runtime / (deadline - t) > dl_runtime / dl_deadline , * * IOW we can't recycle current parameters. * -* Notice that the bandwidth check is done against the period. For +* Notice that the bandwidth check is done against the deadline. For * task with deadline equal to period this is the same of using -* dl_deadline instead of dl_period in the equation above. +* dl_period instead of dl_deadline in the equation above. */ static bool dl_entity_overflow (struct sched_dl_entity *dl_se,struct sched_dl_entity *pi_se,u64 t)@@ -476,7 +476,7 @@ static bool dl_entity_overflow(struct sc* of anything below microseconds resolution is actually fiction
kernel/sched/deadline.c +0
-1* (but still we want to give the user that illusion >;). */ - left = (pi_se->dl_period >> DL_SCALE) * (dl_se->runtime >>
DL_SCALE);kernel/sched/deadline.c +1
-0+ left = (pi_se->dl_deadline >> DL_SCALE) * (dl_se->runtime >>
DL_SCALE); right = ((dl_se->deadline- t) >>DL_SCALE) *
(pi_se->dl_runtime>>DL_SCALE);
Steven Rostedt
reviewerRe: [PATCH 3/2] sched/deadline: Use deadline instead of period when calculating overflow
Quoted 37 lines · On Tue, 14 Feb 2017 23:49:26 +0100 luca abeni <[email protected]>…
Hi Steven,
Quoted 21 lines · On Tue, 14 Feb 2017 14:28:48 -0500 "Steven Rostedt (VMware)"…
I was testing Daniel's changes with his test case, and tweaked it a little. Instead of having the runtime equal to the deadline, I increased the deadline ten fold.
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 */To make it more interesting, I changed it to:
attr.sched_runtime = 2 * 1000 * 1000; /* 2ms */ attr.sched_deadline = 20 * 1000 * 1000; /* 20 ms
*/ attr.sched_period = 2 * 1000 * 1000 * 1000; /* 2 s */The results were rather surprising. The behavior that Daniel's patch was fixing came back. The task started using much more than .1% of the CPU. More like 20%.
Quoted 6 lines
Looking into this I found that it was due to the
dl_entity_overflow()constantly returning true. That's because it uses the relative period against relative runtime vs the absolute deadline against absolute runtime.runtime / (deadline - t) >
dl_runtime/dl_periodI agree that there is an inconsistency here (again, using equations from the "period=deadline" case with a relative deadline different from period).
Quoted 9 lines
I am not sure about the correct fix (wouldn't
"runtime / (deadline - t) >dl_runtime/dl_deadline" allow the task to use a fraction of CPU time equal todl_runtime/dl_deadline?)The current code is clearly wrong (as shown by Daniel), but I do not understand how the current check can allow the task to consume more than
dl_runtime/dl_period... I need some more time to think about this issue.
This is in dl_entity_overflow() which is called by update_dl_entity() which has this:
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;
}The comments in this code state:
* The policy here is that we update the deadline of the entity only if:
* - the current deadline is in the past,
* - using the remaining runtime with the current deadline would make
* the entity exceed its bandwidth.
That second comment is saying that when this task woke up, if the percentage left to run will exceed its bandwidth with the rest of the system then reset its deadline and its runtime.
What happens in the current logic, is that overflow() check says, when the deadline is much smaller than the period, "yeah, we're going to exceed our percentage!" so give us more, even though it wont exceed its percentage if we compared runtime with deadline.
The relative-runtime / relative-period is a tiny percentage, which does not reflect the percentage that the task is allowed to have before the deadline is hit. The tasks bandwidth should be calculated by the relative-runtime / relative-deadline, as runtime <= deadline <= period, and the runtime should happen within the deadline.
When the task wakes up, it currently looks at how much time is left absolute-deadline - t, and compares it to the amount of runtime left. The percentage allowed should still be compared with the percentage between relative-runtime and relative-deadline. The relative-period or even absolute-period, should have no influence in this decision.
-- Steve
Re: [PATCH 3/2] sched/deadline: Use deadline instead of period when calculating overflow
Hi Steven,
On Tue, 14 Feb 2017 19:14:17 -0500
Steven Rostedt <[email protected]> wrote:
[...]
Quoted 29 lines
Quoted 10 lines
I am not sure about the correct fix (wouldn't "runtime / (deadline - t) >
dl_runtime/dl_deadline" allow the task to use a fraction of CPU time equal todl_runtime/dl_deadline?)The current code is clearly wrong (as shown by Daniel), but I do not understand how the current check can allow the task to consume more than
dl_runtime/dl_period... I need some more time to think about this issue.This is in
dl_entity_overflow()which is called byupdate_dl_entity()which has this: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; }The comments in this code state:
* The policy here is that we update the deadline of the entity only
if:
* - the current deadline is in the past,
* - using the remaining runtime with the current deadline would make
* the entity exceed its bandwidth.
Quoted 3 lines
That second comment is saying that when this task woke up, if the percentage left to run will exceed its bandwidth with the rest of the system then reset its deadline and its runtime.
Right; this is the problem. When the relative deadline is different from the period, the term "bandwidth" is ambiguous... We can consider the utilisation (maximum runtime / period), or the density (maximum runtime / relative deadline). In some sense, the two approaches are both correct (if we use density, we are more pessimistic but we try to respect deadlines in a hard way; if we use utilisation, we allow more tasks to be admitted but we can only provide bounded tardiness).
What the current code is doing is to mix the two approaches (resulting in a wrong runtime/deadline assignment).
Quoted 11 lines
What happens in the current logic, is that
overflow()check says, when the deadline is much smaller than the period, "yeah, we're going to exceed our percentage!" so give us more, even though it wont exceed its percentage if we compared runtime with deadline.The relative-runtime / relative-period is a tiny percentage, which does not reflect the percentage that the task is allowed to have before the deadline is hit. The tasks bandwidth should be calculated by the relative-runtime / relative-deadline, as runtime <= deadline <= period, and the runtime should happen within the deadline.
Quoted 5 lines
When the task wakes up, it currently looks at how much time is left absolute-deadline - t, and compares it to the amount of runtime left. The percentage allowed should still be compared with the percentage between relative-runtime and relative-deadline. The relative-period or even absolute-period, should have no influence in this decision.
Ok, thanks; I think I can now see why this can result in a task consuming more than the reserved utilisation. I still need some time to convince me that "runtime / (deadline - t) > dl_runtime / dl_deadline" is the correct check to use (in this case, shouldn't we also change the admission test to use densities instead of utilisations?)
Thanks,
Luca
Re: [PATCH 3/2] sched/deadline: Use deadline instead of period when calculating overflow
Hi,
Quoted 66 lines · Luca Abeni
Hi Steven,
On Tue, 14 Feb 2017 19:14:17 -0500
Steven Rostedt <[email protected]> wrote:
[...]Quoted 29 lines
Quoted 10 lines
I am not sure about the correct fix (wouldn't "runtime / (deadline - t) >
dl_runtime/dl_deadline" allow the task to use a fraction of CPU time equal todl_runtime/dl_deadline?)The current code is clearly wrong (as shown by Daniel), but I do not understand how the current check can allow the task to consume more than
dl_runtime/dl_period... I need some more time to think about this issue.This is in
dl_entity_overflow()which is called byupdate_dl_entity()which has this: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; }The comments in this code state:
* The policy here is that we update the deadline of the entity only
if:
* - the current deadline is in the past,
* - using the remaining runtime with the current deadline would make
* the entity exceed its bandwidth.Quoted 3 lines
That second comment is saying that when this task woke up, if the percentage left to run will exceed its bandwidth with the rest of the system then reset its deadline and its runtime.
Right; this is the problem. When the relative deadline is different from the period, the term "bandwidth" is ambiguous... We can consider the utilisation (maximum runtime / period), or the density (maximum runtime / relative deadline). In some sense, the two approaches are both correct (if we use density, we are more pessimistic but we try to respect deadlines in a hard way; if we use utilisation, we allow more tasks to be admitted but we can only provide bounded tardiness).
What the current code is doing is to mix the two approaches (resulting in a wrong runtime/deadline assignment).
Quoted 11 lines
What happens in the current logic, is that
overflow()check says, when the deadline is much smaller than the period, "yeah, we're going to exceed our percentage!" so give us more, even though it wont exceed its percentage if we compared runtime with deadline.The relative-runtime / relative-period is a tiny percentage, which does not reflect the percentage that the task is allowed to have before the deadline is hit. The tasks bandwidth should be calculated by the relative-runtime / relative-deadline, as runtime <= deadline <= period, and the runtime should happen within the deadline.
Quoted 5 lines
When the task wakes up, it currently looks at how much time is left absolute-deadline - t, and compares it to the amount of runtime left. The percentage allowed should still be compared with the percentage between relative-runtime and relative-deadline. The relative-period or even absolute-period, should have no influence in this decision.
Quoted 6 lines
Ok, thanks; I think I can now see why this can result in a task consuming more than the reserved utilisation. I still need some time to convince me that "runtime / (deadline - t) >
dl_runtime/dl_deadline" is the correct check to use (in this case, shouldn't we also change the admission test to use densities instead of utilisations?)
Right, this is what I was wondering as well, as dl_overflow() currently looks at the period. And I also have some recollection of this discussion happening already in the past, unfortunately it was not on the list.
That discussion started with the following patch
--->8---
Quoted 1 line
From
6cd9b6f3c2b9f144828aa09ad2a355b00a153348Mon Sep 17 00:00:00 2001
From: Juri Lelli <[email protected]>
Date: Fri, 4 Sep 2015 15:41:42 +0100
Subject: [PATCH] sched/core: fix SCHED_DEADLINE admission control
As Documentation/sched/sched-deadline.txt says, a new task can pass through admission control if sum(WCET_i / min{D_i, P_i}) <= 1. However, if the user specifies both sched_period and sched_deadline, we actually check that sum(WCET_i / P_i) <= 1; and this is a less restrictive check w.r.t. the former.
Fix this by always using sched_deadline parameter to compute new_bw, as we also impose that runtime <= deadline <= period (if period != 0) and deadline != 0.
--- kernel/sched/core.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-)
kernel/sched/core.c +2 -2
@@ -2302,9 +2302,9 @@ static int dl_overflow(struct task_struct *p, int policy, {struct dl_bw *dl_b =dl_bw_of (task_cpu (p)); -u64 period = attr->sched_period ?: attr->sched_deadline; +u64 deadline = attr->sched_deadline;u64 runtime = attr->sched_runtime; -u64 new_bw =dl_policy (policy) ?to_ratio (period, runtime) :0 ; +u64 new_bw =dl_policy (policy) ?to_ratio (deadline, runtime) :0 ;int cpus, err =-1 ;if (new_bw == p->dl.dl_bw)
--->8---
that we then dediced not to propose since (note that these are just my memories of the dicussion, so everything it's up for further discussion, also in light of the problem highlighted by Daniel)
- SCHED_DEADLINE, as the documentation says, does AC using utilization
- it is however true that a sufficient (but not necessary) test on UP for D_i != P_i cases is the one of my patch above
- we have agreed in the past that the kernel should only check that we don't cause "overload" in the system (which is still the case if we consider utilizations), not "hard schedulability"
- also because on SMP systems "sum(WCET_i / min{D_i, P_i}) <= M" doesn't guarantee much more than the test base on P_i only (there not seem to be many/any papers around considering the D_i != P_i case on SMP actually)
- basically the patch above would only matter for the UP/partitioned cases
Thoughts?
Thanks,
- Juri
Peter Zijlstra
maintainerRe: [PATCH 3/2] sched/deadline: Use deadline instead of period when calculating overflow
Quoted 17 lines · Juri Lelli
that we then dediced not to propose since (note that these are just my memories of the dicussion, so everything it's up for further discussion, also in light of the problem highlighted by Daniel)
-
SCHED_DEADLINE, as the documentation says, does AC using utilization
- it is however true that a sufficient (but not necessary) test on UP forD_i!=P_icases is the one of my patch above
- we have agreed in the past that the kernel should only check that we don't cause "overload" in the system (which is still the case if we consider utilizations), not "hard schedulability"
- also because on SMP systems "sum(WCET_i / min{D_i, P_i})<= M" doesn't guarantee much more than the test base onP_ionly (there not seem to be many/any papers around considering theD_i!=P_icase on SMP actually)
- basically the patch above would only matter for the UP/partitioned cases
Quoted 1 line
Thoughts?
I think that this makes sense. Keep the kernel AC such that the working set is 'recoverable' was I think the word Tommaso used last time.
I've been meaning to play with his suggested AC for arbitrary affinities but haven't managed to find time yet. My biggest attraction to that is that it would allow de-coupling it from the root_domain thingy and side-step the problems we currently have with that.
Re: [PATCH 3/2] sched/deadline: Use deadline instead of period when calculating overflow
In reply to Juri LelliHi Juri,
On Wed, 15 Feb 2017 10:29:19 +0000
Juri Lelli <[email protected]> wrote:
[...]
Quoted 13 lines
Quoted 6 lines
Ok, thanks; I think I can now see why this can result in a task consuming more than the reserved utilisation. I still need some time to convince me that "runtime / (deadline - t) >
dl_runtime/dl_deadline" is the correct check to use (in this case, shouldn't we also change the admission test to use densities instead of utilisations?)Right, this is what I was wondering as well, as
dl_overflow()currently looks at the period. And I also have some recollection of this discussion happening already in the past, unfortunately it was not on the list.That discussion started with the following patch
[...]
Quoted 11 lines
that we then dediced not to propose since (note that these are just my memories of the dicussion, so everything it's up for further discussion, also in light of the problem highlighted by Daniel)
-
SCHED_DEADLINE, as the documentation says, does AC using
utilization
- it is however true that a sufficient (but not necessary) test on
UP forD_i!=P_icases is the one of my patch above
- we have agreed in the past that the kernel should only check that
we don't cause "overload" in the system (which is still the case if we
consider utilizations), not "hard schedulability"
I remember a similar discussion; I think the decision about what to do depends on what are the requirements: hard deadline guarantees (but in this case global EDF is just a bad choice) or tardines no overload guarantees?
My understanding was that the kernel guarantees that deadline tasks will not starve non-deadline tasks, and that there is an upper bound for the tardiness experienced by deadline tasks. If this understanding is correct, then the current admission test is ok. But if I misunderstood the purpose of the kernel admission test, then maybe your patch is ok.
Then, it is important to keep the admission test consistent with the checks performed in dl_entity_overflow() (but whatever we decide to do, dl_entity_overflow() should be fixed).
Luca
Quoted 12 lines
- also because on SMP systems "
sum(WCET_i / min{D_i, P_i})<= M" doesn't guarantee much more than the test base onP_ionly (there
not seem to be many/any papers around considering theD_i!=P_icase on SMP actually)
- basically the patch above would only matter for the UP/partitioned casesThoughts?
Thanks,
- Juri
Re: [PATCH 3/2] sched/deadline: Use deadline instead of period when calculating overflow
Quoted 42 lines · Luca Abeni
Hi Juri,
On Wed, 15 Feb 2017 10:29:19 +0000
Juri Lelli <[email protected]> wrote:
[...]Quoted 13 lines
Quoted 6 lines
Ok, thanks; I think I can now see why this can result in a task consuming more than the reserved utilisation. I still need some time to convince me that "runtime / (deadline - t) >
dl_runtime/dl_deadline" is the correct check to use (in this case, shouldn't we also change the admission test to use densities instead of utilisations?)Right, this is what I was wondering as well, as
dl_overflow()currently looks at the period. And I also have some recollection of this discussion happening already in the past, unfortunately it was not on the list.That discussion started with the following patch
[...]
Quoted 11 lines
that we then dediced not to propose since (note that these are just my memories of the dicussion, so everything it's up for further discussion, also in light of the problem highlighted by Daniel)
-
SCHED_DEADLINE, as the documentation says, does AC using
utilization
- it is however true that a sufficient (but not necessary) test on
UP forD_i!=P_icases is the one of my patch above
- we have agreed in the past that the kernel should only check that
we don't cause "overload" in the system (which is still the case if we
consider utilizations), not "hard schedulability"I remember a similar discussion; I think the decision about what to do depends on what are the requirements: hard deadline guarantees (but in this case global EDF is just a bad choice) or tardines no overload guarantees?
My understanding was that the kernel guarantees that deadline tasks will not starve non-deadline tasks, and that there is an upper bound for the tardiness experienced by deadline tasks. If this understanding is correct, then the current admission test is ok. But if I misunderstood the purpose of the kernel admission test, then maybe your patch is ok.
Quoted 4 lines
Then, it is important to keep the admission test consistent with the checks performed in
dl_entity_overflow()(but whatever we decide to do,dl_entity_overflow()should be fixed).
I'm sorry, but I'm a bit lost. :(
Why do you say 'whatever we decide to do'?
In my understanding:
- if we decide AC shouldn't change (as we care about not-starving others and having bounded tardiness), then I'd say dl_entity_overflow shouldn't change as well, since it's using dl_runtime/dl_period as 'static bandwidth' (as AC does)
- if we instead move to use densities when doing AC (dl_runtime/dl_ deadline), I think we should also change the check in dl_entity_ overflow, as Steve is proposing
- in both cases Daniel's fixes look sensible to have
Where am I wrong? :)
Actually, another thing that we noticed, talking on IRC with Peter, is that we seem to be replenishing differently on different occasions:
- on wakeup (if overflowing) we do
dl_se->deadline = rq_clock(rq) + pi_se->dl_deadline; dl_se->runtime = pi_se->dl_runtime;
- when the replenishment timer fires (un-thottle and with runtime < 0)
dl_se->deadline += pi_se->dl_period; dl_se->runtime += pi_se->dl_runtime;
Isn't this problematic as well?
Thanks,
- Juri
Re: [PATCH 3/2] sched/deadline: Use deadline instead of period when calculating overflow
Quoted 51 lines · On Wed, 15 Feb 2017 12:59:25 +0000 Juri Lelli <[email protected]> wrote:
Quoted 43 lines · Luca Abeni
Hi Juri,
On Wed, 15 Feb 2017 10:29:19 +0000
Juri Lelli <[email protected]> wrote:
[...]Quoted 13 lines
Quoted 6 lines
Ok, thanks; I think I can now see why this can result in a task consuming more than the reserved utilisation. I still need some time to convince me that "runtime / (deadline - t) >
dl_runtime/dl_deadline" is the correct check to use (in this case, shouldn't we also change the admission test to use densities instead of utilisations?)Right, this is what I was wondering as well, as
dl_overflow()currently looks at the period. And I also have some recollection of this discussion happening already in the past, unfortunately it was not on the list.That discussion started with the following patch
[...]
Quoted 5 lines
that we then dediced not to propose since (note that these are just my memories of the dicussion, so everything it's up for further discussion, also in light of the problem highlighted by Daniel)
Quoted 7 lines
-
SCHED_DEADLINE, as the documentation says, does AC using
utilization
- it is however true that a sufficient (but not necessary) test
on UP forD_i!=P_icases is the one of my patch above
- we have agreed in the past that the kernel should only check
that we don't cause "overload" in the system (which is still the case if we consider utilizations), not "hard schedulability"I remember a similar discussion; I think the decision about what to do depends on what are the requirements: hard deadline guarantees (but in this case global EDF is just a bad choice) or tardines no overload guarantees?
My understanding was that the kernel guarantees that deadline tasks will not starve non-deadline tasks, and that there is an upper bound for the tardiness experienced by deadline tasks. If this understanding is correct, then the current admission test is ok. But if I misunderstood the purpose of the kernel admission test, then maybe your patch is ok.
Quoted 4 lines
Then, it is important to keep the admission test consistent with the checks performed in
dl_entity_overflow()(but whatever we decide to do,dl_entity_overflow()should be fixed).I'm sorry, but I'm a bit lost. :(
Quoted 8 lines
Why do you say 'whatever we decide to do'?
In my understanding:
- if we decide AC shouldn't change (as we care about not-starving others and having bounded tardiness), then I'd say
dl_entity_overflowshouldn't change as well, since it's using dl_runtime/dl_period as 'static bandwidth' (as AC does)
Yes, but it is comparing dl_runtime/dl_period with runtime/(deadline-t), mixing different things. I still need to think more about this, but I think it should either compare runtime/(deadline-t) with dl_runtime/dl_deadline or runtime/(end_of_reservation_period-t) with dl_runtime/dl_period... Otherwise we risk to have issues as shown by Daniel and Steven.
Quoted 5 lines
- if we instead move to use densities when doing AC (dl_runtime/dl_ deadline), I think we should also change the check in
dl_entity_overflow, as Steve is proposing- in both cases Daniel's fixes look sensible to have
Yes, Daniel's fixes fix a possible DoS, so they should go in... Then, we can decide how to improve the situation.
Quoted 11 lines
Where am I wrong? :)
Actually, another thing that we noticed, talking on IRC with Peter, is that we seem to be replenishing differently on different occasions:
- on wakeup (if overflowing) we do
dl_se->deadline = rq_clock(rq) + pi_se->dl_deadline; dl_se->runtime = pi_se->dl_runtime;
Quoted 7 lines
- when the replenishment timer fires (un-thottle and with runtime <
0)dl_se->deadline += pi_se->dl_period; dl_se->runtime += pi_se->dl_runtime;Isn't this problematic as well?
I _think_ this is correct, because they are two different things: in the first case, we generate a new scheduling deadline starting from current time (so, the deadline must be computed based on the relative deadline); in the second case, we postpone an existing scheduling deadline (so, it must be postponed by one period)[*]... No? Or am I misunderstanding the issue you saw?
Thanks,
Luca
[*] Notice that with Daniel's fix the replenishment timer fires at the end of the reservation period (or, at the beginning of a new reservation period). So, "current time + dl_deadline" is about equal to "deadline + period" (but using "current time + dl_deadline" would generate larger deadlines if the timer fires later than expected).
Re: [PATCH 3/2] sched/deadline: Use deadline instead of period when calculating overflow
Quoted 63 lines · Luca Abeni
Quoted 51 lines · On Wed, 15 Feb 2017 12:59:25 +0000 Juri Lelli <[email protected]> wrote:
Quoted 43 lines · Luca Abeni
Hi Juri,
On Wed, 15 Feb 2017 10:29:19 +0000
Juri Lelli <[email protected]> wrote:
[...]Quoted 13 lines
Quoted 6 lines
Ok, thanks; I think I can now see why this can result in a task consuming more than the reserved utilisation. I still need some time to convince me that "runtime / (deadline - t) >
dl_runtime/dl_deadline" is the correct check to use (in this case, shouldn't we also change the admission test to use densities instead of utilisations?)Right, this is what I was wondering as well, as
dl_overflow()currently looks at the period. And I also have some recollection of this discussion happening already in the past, unfortunately it was not on the list.That discussion started with the following patch
[...]
Quoted 5 lines
that we then dediced not to propose since (note that these are just my memories of the dicussion, so everything it's up for further discussion, also in light of the problem highlighted by Daniel)
Quoted 7 lines
-
SCHED_DEADLINE, as the documentation says, does AC using
utilization
- it is however true that a sufficient (but not necessary) test
on UP forD_i!=P_icases is the one of my patch above
- we have agreed in the past that the kernel should only check
that we don't cause "overload" in the system (which is still the case if we consider utilizations), not "hard schedulability"I remember a similar discussion; I think the decision about what to do depends on what are the requirements: hard deadline guarantees (but in this case global EDF is just a bad choice) or tardines no overload guarantees?
My understanding was that the kernel guarantees that deadline tasks will not starve non-deadline tasks, and that there is an upper bound for the tardiness experienced by deadline tasks. If this understanding is correct, then the current admission test is ok. But if I misunderstood the purpose of the kernel admission test, then maybe your patch is ok.
Quoted 4 lines
Then, it is important to keep the admission test consistent with the checks performed in
dl_entity_overflow()(but whatever we decide to do,dl_entity_overflow()should be fixed).I'm sorry, but I'm a bit lost. :(
Quoted 8 lines
Why do you say 'whatever we decide to do'?
In my understanding:
- if we decide AC shouldn't change (as we care about not-starving others and having bounded tardiness), then I'd say
dl_entity_overflowshouldn't change as well, since it's using dl_runtime/dl_period as 'static bandwidth' (as AC does)
Quoted 6 lines
Yes, but it is comparing dl_runtime/dl_period with runtime/(deadline-t), mixing different things. I still need to think more about this, but I think it should either compare runtime/(deadline-t) with dl_runtime/dl_deadline or runtime/(end_of_reservation_period-t) with dl_runtime/dl_period... Otherwise we risk to have issues as shown by Daniel and Steven.
OK.
Quoted 27 lines
Quoted 7 lines
- if we instead move to use densities when doing AC (dl_runtime/dl_ deadline), I think we should also change the check in
dl_entity_overflow, as Steve is proposing- in both cases Daniel's fixes look sensible to have
Yes, Daniel's fixes fix a possible DoS, so they should go in... Then, we can decide how to improve the situation.
Quoted 17 lines
Where am I wrong? :)
Actually, another thing that we noticed, talking on IRC with Peter, is that we seem to be replenishing differently on different occasions:
- on wakeup (if overflowing) we do
dl_se->deadline = rq_clock(rq) + pi_se->dl_deadline; dl_se->runtime = pi_se->dl_runtime;- when the replenishment timer fires (un-thottle and with runtime <
0)dl_se->deadline += pi_se->dl_period; dl_se->runtime += pi_se->dl_runtime;
Quoted 8 lines
Quoted 1 line
Isn't this problematic as well?
I _think_ this is correct, because they are two different things: in the first case, we generate a new scheduling deadline starting from current time (so, the deadline must be computed based on the relative deadline); in the second case, we postpone an existing scheduling deadline (so, it must be postponed by one period)[*]... No? Or am I misunderstanding the issue you saw?
No, what you are saying makes sense, we don't actually have a problem.
Re: [PATCH 3/2] sched/deadline: Use deadline instead of period when calculating overflow
In reply to Juri LelliQuoted 2 lines · Juri Lelli
Actually, another thing that we noticed, talking on IRC with Peter, is that we seem to be replenishing differently on different occasions:
When a task is awakened (not by the replenishment timer), it is not possible to know if the absolute deadline var stores the absolute deadline of activation which took place in the instant (current time) - dl_period.
Therefore, assuming the next deadline is one dl_deadline away from now is correct.
IOW: that is a sporadic activation - the task is activated after at least minimum inter-arrival time between activation/replenishment:
Quoted 4 lines
- on wakeup (if overflowing) we do
dl_se->deadline = rq_clock(rq) + pi_se->dl_deadline; dl_se->runtime = pi_se->dl_runtime;
In the replenishment timer, it is known that the absolute deadline instant of the previous activation is in the deadline var. So putting the absolute deadline one dl_period away is correct [1].
Another point is that this case avoids creating time drift due to latencies. For instance, in the case of a 1 ms delay of the timer (interrupts disabled?), the wakeup replenishment would push the absolute a relative deadline + 1 ms away from the previous deadline.
IOW: the replenishment timer makes the periodic case - a fixed time offset from the previous activation/replenishment.
Quoted 4 lines
- when the replenishment timer fires (un-thottle and with runtime < 0)
dl_se->deadline += pi_se->dl_period; dl_se->runtime += pi_se->dl_runtime;
So I think it is correct. Am I missing something?
[1] For the sake of completeness:
- dl_se->deadline = Absolute deadline
- dl_se->dl_deadline = Relative deadline
the next absolute deadline is at:
dl_se->deadline = dl_next_period(dl_se) + dl_se->dl_deadline;
as dl_next_period(dl_se) is:
dl_se->deadline - dl_se->dl_deadline + dl_se->dl_period;
the next deadline is at:
dl_se->deadline = dl_se->deadline - dl_se->dl_deadline + dl_se->dl_period + dl_se->dl_deadline
Which can be simplified to:
dl_se->deadline = dl_se->deadline += pi_se->dl_period;
because we have (- dl_se->dl_deadline) + dl_se->dl_deadline.
-- Daniel
Re: [PATCH 3/2] sched/deadline: Use deadline instead of period when calculating overflow
Quoted 1 line · Daniel Bristot de Oliveira
dl_se->deadline=dl_se->deadline+=pi_se->dl_period;
ops, it should be:
dl_se->deadline = dl_se->deadline + pi_se->dl_period;
Steven Rostedt
reviewerRe: [PATCH 3/2] sched/deadline: Use deadline instead of period when calculating overflow
Quoted 6 lines · On Wed, 15 Feb 2017 14:42:42 +0100 Daniel Bristot de Oliveira…
Quoted 1 line · Daniel Bristot de Oliveira
dl_se->deadline=dl_se->deadline+=pi_se->dl_period;ops, it should be:
dl_se->deadline=dl_se->deadline+pi_se->dl_period;
or
dl_se->deadline += pi_se->dl_period;
;-)
-- Steve
Re: [PATCH 3/2] sched/deadline: Use deadline instead of period when calculating overflow
In reply to Daniel Bristot de OliveiraQuoted 33 lines · Daniel Bristot de Oliveira
Quoted 2 lines · Juri Lelli
Actually, another thing that we noticed, talking on IRC with Peter, is that we seem to be replenishing differently on different occasions:
When a task is awakened (not by the replenishment timer), it is not possible to know if the absolute deadline var stores the absolute deadline of activation which took place in the instant (current time) -
dl_period.Therefore, assuming the next deadline is one
dl_deadlineaway from now is correct.IOW: that is a sporadic activation - the task is activated after at least minimum inter-arrival time between activation/replenishment:
Quoted 4 lines
- on wakeup (if overflowing) we do
dl_se->deadline = rq_clock(rq) + pi_se->dl_deadline; dl_se->runtime = pi_se->dl_runtime;In the replenishment timer, it is known that the absolute deadline instant of the previous activation is in the deadline var. So putting the absolute deadline one
dl_periodaway is correct [1].Another point is that this case avoids creating time drift due to latencies. For instance, in the case of a 1 ms delay of the timer (interrupts disabled?), the wakeup replenishment would push the absolute a relative deadline + 1 ms away from the previous deadline.
IOW: the replenishment timer makes the periodic case - a fixed time offset from the previous activation/replenishment.
Quoted 7 lines
Quoted 4 lines
- when the replenishment timer fires (un-thottle and with runtime < 0)
dl_se->deadline += pi_se->dl_period; dl_se->runtime += pi_se->dl_runtime;So I think it is correct. Am I missing something?
Nope, you are right, no problems here.
Thanks,
- Juri
Re: [PATCH 3/2] sched/deadline: Use deadline instead of period when calculating overflow
In reply to Daniel Bristot de OliveiraQuoted 3 lines · Daniel Bristot de Oliveira
[1] For the sake of completeness:
-dl_se->deadline= Absolute deadline
-dl_se->dl_deadline= Relative deadline
Daniel's note [1] reminds me that, would it be worth a rename of these, for the sake of clarity, e.g.:
-) abs_deadline vs rel_deadline
-) runtime_left vs runtime_tot
or similar :-) ?
T.
Steven Rostedt
reviewerRe: [PATCH 3/2] sched/deadline: Use deadline instead of period when calculating overflow
Quoted 8 lines · On Thu, 16 Feb 2017 17:36:07 +0100 Tommaso Cucinotta…
Quoted 3 lines · Daniel Bristot de Oliveira
[1] For the sake of completeness:
-dl_se->deadline= Absolute deadline
-dl_se->dl_deadline= Relative deadlineDaniel's note [1] reminds me that, would it be worth a rename of these, for the sake of clarity, e.g.:
(quoted diff) +0
-2-) abs_deadline vs rel_deadline -) runtime_left vs runtime_totor similar :-) ?
+1 as I seem to get confused by it too.
-- Steve