Skip to contentSkip to conversation

Don't account time after deadline twice

PATCH In review Zhihui Zhang 3 participants 5 messages Jun 30, 2014 – Jul 4, 2014 1 message not in the archive Scheduler

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 Don't account time after deadline twice

Unless we want to double-penalize an overrun task, the time after the deadline and before the current time is already accounted in the negative dl_se->runtime value. So we can leave it as is in the case of dmiss && rorun.

---
 kernel/sched/deadline.c | 6 ++----
 1 file changed, 2 insertions(+), 4 deletions(-)
kernel/sched/deadline.c +2 -4
index fc4f98b1..67df0d6 100644
@@ -579,10 +579,8 @@ int dl_runtime_exceeded(struct rq *rq, struct sched_dl_entity *dl_se)
 	 * the next instance. Thus, if we do not account that, we are
 	 * stealing bandwidth from the system at each deadline miss!
 	 */
-	if (dmiss) {
-		dl_se->runtime = rorun ? dl_se->runtime : 0;
-		dl_se->runtime -= rq_clock(rq) - dl_se->deadline;
-	}
+	if (dmiss && !rorun)
+		dl_se->runtime = dl_se->deadline - rq_clock(rq);
 
 	return 1;
 }
Signature · 1 line
1.8.1.2
maintainer
#1 lore raw
Quoted 3 lines · Zhihui Zhang

Unless we want to double-penalize an overrun task, the time after the deadline and before the current time is already accounted in the negative dl_se->runtime value. So we can leave it as is in the case of dmiss && rorun.

Juri?

Quoted 25 lines
---
 kernel/sched/deadline.c | 6 ++----
 1 file changed, 2 insertions(+), 4 deletions(-)
kernel/sched/deadline.c +2 -4
index fc4f98b1..67df0d6 100644
@@ -579,10 +579,8 @@ int dl_runtime_exceeded(struct rq *rq, struct sched_dl_entity *dl_se)
 	 * the next instance. Thus, if we do not account that, we are
 	 * stealing bandwidth from the system at each deadline miss!
 	 */
-	if (dmiss) {
-		dl_se->runtime = rorun ? dl_se->runtime : 0;
-		dl_se->runtime -= rq_clock(rq) - dl_se->deadline;
-	}
+	if (dmiss && !rorun)
+		dl_se->runtime = dl_se->deadline - rq_clock(rq);
 
 	return 1;
 }
Signature · 1 line
1.8.1.2
#2 lore raw
Quoted 12 lines · On Tue, 1 Jul 2014 15:08:16 +0200 Peter Zijlstra <[email protected]> wrote:
Quoted 3 lines · Zhihui Zhang

Unless we want to double-penalize an overrun task, the time after the deadline and before the current time is already accounted in the negative dl_se->runtime value. So we can leave it as is in the case of dmiss && rorun.

Juri?

Quoted 5 lines
---
 kernel/sched/deadline.c | 6 ++----
 1 file changed, 2 insertions(+), 4 deletions(-)
Quoted 10 lines

kernel/sched/deadline.c int dl_runtime_exceeded(struct rq *rq, struct sched_dl_entity *dl_se) · line 583

Quoted 10 lines
kernel/sched/deadline.c +0 -2
index fc4f98b1..67df0d6 100644
@@ -579,10 +579,8 @@ int dl_runtime_exceeded(struct rq *rq, struct sched_dl_entity *dl_se)
 	 * the next instance. Thus, if we do not account that, we are
 	 * stealing bandwidth from the system at each deadline miss!
 	 */
-	if (dmiss) {
-		dl_se->runtime = rorun ? dl_se->runtime : 0;

If we didn't return 0 before, we are going to throttle (or replenish) the entity, and you want runtime to be <=0. So, this is needed.

Quoted 2 lines

kernel/sched/deadline.c int dl_runtime_exceeded(struct rq *rq, struct sched_dl_entity *dl_se) · line 585

Quoted 2 lines
kernel/sched/deadline.c +0 -2
-		dl_se->runtime -= rq_clock(rq) - dl_se->deadline;
-	}

A little pessimism in some cases, due to the fact that we use both rq_clock and rq_clock_task (for the budget).

Thanks,

- Juri

Quoted 8 lines
Quoted 8 lines
kernel/sched/deadline.c +2 -0
+	if (dmiss && !rorun)
+		dl_se->runtime = dl_se->deadline - rq_clock(rq);
 
 	return 1;
 }
Signature · 1 line
1.8.1.2

A message that is not in the archive (sent off-list or not yet received): CADFvMYKzpihC3GLwNFZW0KCrZQY5FDSH5EQd4iLmHLK+hauDWA@mail.gmail.com

#4 lore raw
Quoted 2 lines · On Wed, 2 Jul 2014 19:44:04 -0400 Zhihui Zhang <[email protected]> wrote:

My point is that rq_clock(rq) - dl_se->deadline is already part of dl_se->runtime, which is decremented before calling dl_runtime_exceeded().

But, we decrement dl_se->runtime looking at rq_clock_task(rq), that is in general <= rq_clock(rq), that we use to handle deadlines. So, if we do like you suggest, in some cases we could end up stealing some bandwidth from the system. Indeed, we prefer some pessimism here.

Thanks,

- Juri

Quoted 63 lines

So the following line is not needed in the case of both overrun and missing deadline:

    dl_se->runtime -= rq_clock(rq) - dl_se->deadline;

Or did I miss anything?

thanks,

Quoted 51 lines · Juri Lelli
Quoted 2 lines · On Tue, 1 Jul 2014 15:08:16 +0200 Peter Zijlstra <[email protected]> wrote:
Quoted 1 line · Zhihui Zhang

Unless we want to double-penalize an overrun task, the time after the

deadline

Quoted 1 line
Quoted 1 line

and before the current time is already accounted in the negative

dl_se->runtime

Quoted 9 lines
Quoted 1 line

value. So we can leave it as is in the case of dmiss && rorun.

Juri?

Quoted 5 lines
---
 kernel/sched/deadline.c | 6 ++----
 1 file changed, 2 insertions(+), 4 deletions(-)
Quoted 5 lines

kernel/sched/deadline.c int dl_runtime_exceeded(struct rq *rq, struct

Quoted 5 lines
kernel/sched/deadline.c +0 -0
index fc4f98b1..67df0d6 100644
@@ -579,10 +579,8 @@ int dl_runtime_exceeded(struct rq *rq, struct

sched_dl_entity *dl_se)

Quoted 5 lines

kernel/sched/deadline.c int dl_runtime_exceeded(struct rq *rq, struct sched_dl_entity *dl_se) · line 583

Quoted 5 lines
kernel/sched/deadline.c +0 -2
     * the next instance. Thus, if we do not account that, we are
     * stealing bandwidth from the system at each deadline miss!
     */
-   if (dmiss) {
-           dl_se->runtime = rorun ? dl_se->runtime : 0;

If we didn't return 0 before, we are going to throttle (or replenish) the entity, and you want runtime to be <=0. So, this is needed.

Quoted 2 lines

kernel/sched/deadline.c int dl_runtime_exceeded(struct rq *rq, struct sched_dl_entity *dl_se) · line 585

Quoted 2 lines
kernel/sched/deadline.c +0 -2
-           dl_se->runtime -= rq_clock(rq) - dl_se->deadline;
-   }

A little pessimism in some cases, due to the fact that we use both rq_clock and rq_clock_task (for the budget).

Thanks,

- Juri

Quoted 8 lines
Quoted 8 lines
kernel/sched/deadline.c +2 -1
+   if (dmiss && !rorun)
+           dl_se->runtime = dl_se->deadline - rq_clock(rq);
 
    return 1;
 }
--

1.8.1.2

#5 lore raw

We calculate difference between two readings of a clock to see how much time has elapsed. Part of the time between rq_clock(rq) - dl_se->deadline can indeed be accounted for by reading a different clock
(i.e., rq_clock_task()) if the task was running during the period. And that is how dl_se->runtime is obtained. After all, both clocks are running independently, right? Furthermore, the caller of dl_runtime_exceeded() will still use rq_clock() and dl_se->deadline to determine if we throttle or replenish. Anyway, I have failed to see any steal of time. Could you please give a concrete example (perhaps with numbers)?

thanks,

-Zhihui

Quoted 78 lines · Juri Lelli
Quoted 2 lines · On Wed, 2 Jul 2014 19:44:04 -0400 Zhihui Zhang <[email protected]> wrote:

My point is that rq_clock(rq) - dl_se->deadline is already part of dl_se->runtime, which is decremented before calling dl_runtime_exceeded().

But, we decrement dl_se->runtime looking at rq_clock_task(rq), that is in general <= rq_clock(rq), that we use to handle deadlines. So, if we do like you suggest, in some cases we could end up stealing some bandwidth from the system. Indeed, we prefer some pessimism here.

Thanks,

- Juri

Quoted 63 lines

So the following line is not needed in the case of both overrun and missing deadline:

    dl_se->runtime -= rq_clock(rq) - dl_se->deadline;

Or did I miss anything?

thanks,

Quoted 51 lines · Juri Lelli
Quoted 2 lines · On Tue, 1 Jul 2014 15:08:16 +0200 Peter Zijlstra <[email protected]> wrote:
Quoted 1 line · Zhihui Zhang

Unless we want to double-penalize an overrun task, the time after the

deadline

Quoted 1 line
Quoted 1 line

and before the current time is already accounted in the negative

dl_se->runtime

Quoted 9 lines
Quoted 1 line

value. So we can leave it as is in the case of dmiss && rorun.

Juri?

Quoted 5 lines
---
 kernel/sched/deadline.c | 6 ++----
 1 file changed, 2 insertions(+), 4 deletions(-)
Quoted 5 lines

kernel/sched/deadline.c int dl_runtime_exceeded(struct rq *rq, struct

Quoted 5 lines
kernel/sched/deadline.c +0 -0
index fc4f98b1..67df0d6 100644
@@ -579,10 +579,8 @@ int dl_runtime_exceeded(struct rq *rq, struct

sched_dl_entity *dl_se)

Quoted 5 lines

kernel/sched/deadline.c int dl_runtime_exceeded(struct rq *rq, struct sched_dl_entity *dl_se) · line 583

Quoted 5 lines
kernel/sched/deadline.c +0 -2
     * the next instance. Thus, if we do not account that, we are
     * stealing bandwidth from the system at each deadline miss!
     */
-   if (dmiss) {
-           dl_se->runtime = rorun ? dl_se->runtime : 0;

If we didn't return 0 before, we are going to throttle (or replenish) the entity, and you want runtime to be <=0. So, this is needed.

Quoted 2 lines

kernel/sched/deadline.c int dl_runtime_exceeded(struct rq *rq, struct sched_dl_entity *dl_se) · line 585

Quoted 2 lines
kernel/sched/deadline.c +0 -2
-           dl_se->runtime -= rq_clock(rq) - dl_se->deadline;
-   }

A little pessimism in some cases, due to the fact that we use both rq_clock and rq_clock_task (for the budget).

Thanks,

- Juri

Quoted 8 lines
Quoted 8 lines
kernel/sched/deadline.c +2 -1
+   if (dmiss && !rorun)
+           dl_se->runtime = dl_se->deadline - rq_clock(rq);
 
    return 1;
 }
--

1.8.1.2