SCHED_DEADLINE server infrastructure

[ dl_server do not account for rt ]

kernel/sched/deadline.c +0 -0

index 541d547e1019..1d7b96ca9011 100644
@@ -1382,6 +1382,13 @@ static void update_curr_dl_se(struct rq *rq, struct sched_dl_entity *dl_se, s64
 			resched_curr(rq);
 	}
 

Quoted 9 lines · Daniel Bristot de Oliveira

[ dl_server do not account for rt ]

kernel/sched/deadline.c +0 -0

index 541d547e1019..1d7b96ca9011 100644
@@ -1382,6 +1382,13 @@ static void update_curr_dl_se(struct rq *rq, struct sched_dl_entity *dl_se, s64
 			resched_curr(rq);
 	}
 

kernel/sched/deadline.c static void update_curr_dl_se(struct rq *rq, struct sched_dl_entity *dl_se, s64 · line 1394

Quoted 10 lines

kernel/sched/deadline.c +7 -0

+	/*
+	 * The fair server (sole dl_server) does not account for real-time
+	 * workload because it is running fair work.
+	 */
+	if (dl_server(dl_se))
+		return;
+
 	/*
 	 * Because -- for now -- we share the rt bandwidth, we need to
 	 * account our runtime there too, otherwise actual rt tasks

Should we perhaps write this like so?

	if (dl_se == &rq->fair_server)
		return;

Quoted 13 lines · Daniel Bristot de Oliveira

kernel/sched/fair.c +2 -0

index b15f7f376a67..399237cd9f59 100644
@@ -1201,6 +1201,8 @@ static void update_curr(struct cfs_rq *cfs_rq)
 		account_group_exec_runtime(curtask, delta_exec);
 		if (curtask->server)
 			dl_server_update(curtask->server, delta_exec);
+		else
+			dl_server_update(&rq_of(cfs_rq)->fair_server, delta_exec);
 	}
 
 	account_cfs_rq_runtime(cfs_rq, delta_exec);

kernel/sched/fair.c +0 -2

@@ -1195,8 +1196,17 @@ static void update_curr(struct cfs_rq *c
 	update_deadline(cfs_rq, curr);
 	update_min_vruntime(cfs_rq);
 
-	if (entity_is_task(curr))
-		update_curr_task(task_of(curr), delta_exec);

kernel/sched/fair.c +1 -0

+	}
 
 	account_cfs_rq_runtime(cfs_rq, delta_exec);
 }

Among the motivations for the DL servers is the real-time throttling mechanism. This mechanism works by throttling the rt_rq after running for a long period without leaving space for fair tasks.

The base dl server avoids this problem by boosting fair tasks instead of throttling the rt_rq. The point is that it boosts without waiting for potential starvation, causing some non-intuitive cases.

For example, an IRQ dispatches two tasks on an idle system, a fair and an RT. The DL server will be activated, running the fair task before the RT one. This problem can be avoided by deferring the dl server activation.

By setting the zerolax option, the dl_server will dispatch an SCHED_DEADLINE reservation with replenished runtime, but throttled.

The dl_timer will be set for (period - runtime) ns from start time. Thus boosting the fair rq on its 0-laxity time with respect to rt_rq.

If the fair scheduler has the opportunity to run while waiting for zerolax time, the dl server runtime will be consumed. If the runtime is completely consumed before the zerolax time, the server will be replenished while still in a throttled state. Then, the dl_timer will be reset to the new zerolax time

If the fair server reaches the zerolax time without consuming its runtime, the server will be boosted, following CBS rules (thus without breaking SCHED_DEADLINE).

Signed-off-by Daniel Bristot de Oliveira <[email protected]>

---
 include/linux/sched.h   |   2 +
 kernel/sched/deadline.c | 100 +++++++++++++++++++++++++++++++++++++++-
 kernel/sched/fair.c     |   3 ++
 3 files changed, 103 insertions(+), 2 deletions(-)

include/linux/sched.h +2 -0

index 5ac1f252e136..56e53e6fd5a0 100644
@@ -660,6 +660,8 @@ struct sched_dl_entity {
        unsigned int                    dl_non_contending : 1;
        unsigned int                    dl_overrun        : 1;
        unsigned int                    dl_server         : 1;
+       unsigned int                    dl_zerolax        : 1;
+       unsigned int                    dl_zerolax_armed  : 1;
 
        /*
         * Bandwidth enforcement timer. Each -deadline task has its

kernel/sched/deadline.c +39 -0

index 1d7b96ca9011..69ee1fbd60e4 100644
@@ -772,6 +772,14 @@ static inline void replenish_dl_new_period(struct sched_dl_entity *dl_se,
        /* for non-boosted task, pi_of(dl_se) == dl_se */
        dl_se->deadline = rq_clock(rq) + pi_of(dl_se)->dl_deadline;
        dl_se->runtime = pi_of(dl_se)->dl_runtime;
+
+       /*
+        * If it is a zerolax reservation, throttle it.
+        */
+       if (dl_se->dl_zerolax) {
+               dl_se->dl_throttled = 1;
+               dl_se->dl_zerolax_armed = 1;
+       }
 }
 
 /*

@@ -828,6 +836,7 @@ static inline void setup_new_dl_entity(struct sched_dl_entity *dl_se)
  * could happen are, typically, a entity voluntarily trying to overcome its
  * runtime, or it just underestimated it during sched_setattr().
  */
+static int start_dl_timer(struct sched_dl_entity *dl_se);
 static void replenish_dl_entity(struct sched_dl_entity *dl_se)
 {
        struct dl_rq *dl_rq = dl_rq_of_se(dl_se);

@@ -874,6 +883,28 @@ static void replenish_dl_entity(struct sched_dl_entity *dl_se)
                dl_se->dl_yielded = 0;
        if (dl_se->dl_throttled)
                dl_se->dl_throttled = 0;
+
+       /*
+        * If this is the replenishment of a zerolax reservation,
+        * clear the flag and return.
+        */
+       if (dl_se->dl_zerolax_armed) {
+               dl_se->dl_zerolax_armed = 0;
+               return;
+       }
+
+       /*
+        * A this point, if the zerolax server is not armed, and the deadline
+        * is in the future, throttle the server and arm the zerolax timer.
+        */
+       if (dl_se->dl_zerolax &&
+           dl_time_before(dl_se->deadline - dl_se->runtime, rq_clock(rq))) {
+               if (!is_dl_boosted(dl_se)) {
+                       dl_se->dl_zerolax_armed = 1;
+                       dl_se->dl_throttled = 1;
+                       start_dl_timer(dl_se);
+               }
+       }
 }
 
 /*

@@ -1024,6 +1055,13 @@ static void update_dl_entity(struct sched_dl_entity *dl_se)
                }
 
                replenish_dl_new_period(dl_se, rq);
+       } else if (dl_server(dl_se) && dl_se->dl_zerolax) {
+               /*
+                * The server can still use its previous deadline, so throttle
+                * and arm the zero-laxity timer.
+                */
+               dl_se->dl_zerolax_armed = 1;
+               dl_se->dl_throttled = 1;
        }
 }
 

@@ -1056,8 +1094,20 @@ static int start_dl_timer(struct sched_dl_entity *dl_se)
         * We want the timer to fire at the deadline, but considering
         * that it is actually coming from rq->clock and not from
         * hrtimer's time base reading.
+        *

Hi Daniel,

Quoted 126 lines · Daniel Bristot de Oliveira

Among the motivations for the DL servers is the real-time throttling mechanism. This mechanism works by throttling the rt_rq after running for a long period without leaving space for fair tasks.

The base dl server avoids this problem by boosting fair tasks instead of throttling the rt_rq. The point is that it boosts without waiting for potential starvation, causing some non-intuitive cases.

For example, an IRQ dispatches two tasks on an idle system, a fair and an RT. The DL server will be activated, running the fair task before the RT one. This problem can be avoided by deferring the dl server activation.

By setting the zerolax option, the dl_server will dispatch an SCHED_DEADLINE reservation with replenished runtime, but throttled.

The dl_timer will be set for (period - runtime) ns from start time. Thus boosting the fair rq on its 0-laxity time with respect to rt_rq.

If the fair scheduler has the opportunity to run while waiting for zerolax time, the dl server runtime will be consumed. If the runtime is completely consumed before the zerolax time, the server will be replenished while still in a throttled state. Then, the dl_timer will be reset to the new zerolax time

If the fair server reaches the zerolax time without consuming its runtime, the server will be boosted, following CBS rules (thus without breaking SCHED_DEADLINE).

Signed-off-by Daniel Bristot de Oliveira <[email protected]>

---
 include/linux/sched.h   |   2 +
 kernel/sched/deadline.c | 100 +++++++++++++++++++++++++++++++++++++++-
 kernel/sched/fair.c     |   3 ++
 3 files changed, 103 insertions(+), 2 deletions(-)

include/linux/sched.h +2 -0

index 5ac1f252e136..56e53e6fd5a0 100644
@@ -660,6 +660,8 @@ struct sched_dl_entity {
        unsigned int                    dl_non_contending : 1;
        unsigned int                    dl_overrun        : 1;
        unsigned int                    dl_server         : 1;
+       unsigned int                    dl_zerolax        : 1;
+       unsigned int                    dl_zerolax_armed  : 1;
 
        /*
         * Bandwidth enforcement timer. Each -deadline task has its

kernel/sched/deadline.c +39 -0

index 1d7b96ca9011..69ee1fbd60e4 100644
@@ -772,6 +772,14 @@ static inline void replenish_dl_new_period(struct sched_dl_entity *dl_se,
        /* for non-boosted task, pi_of(dl_se) == dl_se */
        dl_se->deadline = rq_clock(rq) + pi_of(dl_se)->dl_deadline;
        dl_se->runtime = pi_of(dl_se)->dl_runtime;
+
+       /*
+        * If it is a zerolax reservation, throttle it.
+        */
+       if (dl_se->dl_zerolax) {
+               dl_se->dl_throttled = 1;
+               dl_se->dl_zerolax_armed = 1;
+       }
 }
 
 /*

@@ -828,6 +836,7 @@ static inline void setup_new_dl_entity(struct sched_dl_entity *dl_se)
  * could happen are, typically, a entity voluntarily trying to overcome its
  * runtime, or it just underestimated it during sched_setattr().
  */
+static int start_dl_timer(struct sched_dl_entity *dl_se);
 static void replenish_dl_entity(struct sched_dl_entity *dl_se)
 {
        struct dl_rq *dl_rq = dl_rq_of_se(dl_se);

@@ -874,6 +883,28 @@ static void replenish_dl_entity(struct sched_dl_entity *dl_se)
                dl_se->dl_yielded = 0;
        if (dl_se->dl_throttled)
                dl_se->dl_throttled = 0;
+
+       /*
+        * If this is the replenishment of a zerolax reservation,
+        * clear the flag and return.
+        */
+       if (dl_se->dl_zerolax_armed) {
+               dl_se->dl_zerolax_armed = 0;
+               return;
+       }
+
+       /*
+        * A this point, if the zerolax server is not armed, and the deadline
+        * is in the future, throttle the server and arm the zerolax timer.
+        */
+       if (dl_se->dl_zerolax &&
+           dl_time_before(dl_se->deadline - dl_se->runtime, rq_clock(rq))) {
+               if (!is_dl_boosted(dl_se)) {
+                       dl_se->dl_zerolax_armed = 1;
+                       dl_se->dl_throttled = 1;
+                       start_dl_timer(dl_se);
+               }
+       }
 }
 
 /*

@@ -1024,6 +1055,13 @@ static void update_dl_entity(struct sched_dl_entity *dl_se)
                }
 
                replenish_dl_new_period(dl_se, rq);
+       } else if (dl_server(dl_se) && dl_se->dl_zerolax) {
+               /*
+                * The server can still use its previous deadline, so throttle
+                * and arm the zero-laxity timer.
+                */
+               dl_se->dl_zerolax_armed = 1;
+               dl_se->dl_throttled = 1;
        }
 }
 

@@ -1056,8 +1094,20 @@ static int start_dl_timer(struct sched_dl_entity *dl_se)
         * We want the timer to fire at the deadline, but considering
         * that it is actually coming from rq->clock and not from
         * hrtimer's time base reading.
+        *

kernel/sched/deadline.c static int start_dl_timer(struct sched_dl_entity *dl_se) · line 1106

Quoted 10 lines

kernel/sched/deadline.c +8 -1

+        * The zerolax reservation will have its timer set to the
+        * deadline - runtime. At that point, the CBS rule will decide
+        * if the current deadline can be used, or if a replenishment
+        * is required to avoid add too much pressure on the system
+        * (current u > U).
         */
-       act = ns_to_ktime(dl_next_period(dl_se));
+       if (dl_se->dl_zerolax_armed) {
+               WARN_ON_ONCE(!dl_se->dl_throttled);
+               act = ns_to_ktime(dl_se->deadline - dl_se->runtime);

Just a question, here if dl_se->deadline - dl_se->runtime is large, then does that mean that server activation will be much more into the future? So say I want to give CFS 30%, then it will take 70% of the period before CFS preempts RT thus "starving" CFS for this duration. I think that's Ok for smaller periods and runtimes, though.

I think it does reserve the amount of required CFS bandwidth so it is probably OK, though it is perhaps letting RT run more initially (say if CFS tasks are not CPU bound and occasionally wake up, they will always be hit by the 70% latency AFAICS which may be large for large periods and small runtimes).

Quoted 148 lines · Joel Fernandes

Hi Daniel,

Quoted 126 lines · Daniel Bristot de Oliveira

Among the motivations for the DL servers is the real-time throttling mechanism. This mechanism works by throttling the rt_rq after running for a long period without leaving space for fair tasks.

The base dl server avoids this problem by boosting fair tasks instead of throttling the rt_rq. The point is that it boosts without waiting for potential starvation, causing some non-intuitive cases.

For example, an IRQ dispatches two tasks on an idle system, a fair and an RT. The DL server will be activated, running the fair task before the RT one. This problem can be avoided by deferring the dl server activation.

By setting the zerolax option, the dl_server will dispatch an SCHED_DEADLINE reservation with replenished runtime, but throttled.

The dl_timer will be set for (period - runtime) ns from start time. Thus boosting the fair rq on its 0-laxity time with respect to rt_rq.

If the fair scheduler has the opportunity to run while waiting for zerolax time, the dl server runtime will be consumed. If the runtime is completely consumed before the zerolax time, the server will be replenished while still in a throttled state. Then, the dl_timer will be reset to the new zerolax time

If the fair server reaches the zerolax time without consuming its runtime, the server will be boosted, following CBS rules (thus without breaking SCHED_DEADLINE).

Signed-off-by Daniel Bristot de Oliveira <[email protected]>

---
 include/linux/sched.h   |   2 +
 kernel/sched/deadline.c | 100 +++++++++++++++++++++++++++++++++++++++-
 kernel/sched/fair.c     |   3 ++
 3 files changed, 103 insertions(+), 2 deletions(-)

include/linux/sched.h +2 -0

index 5ac1f252e136..56e53e6fd5a0 100644
@@ -660,6 +660,8 @@ struct sched_dl_entity {
        unsigned int                    dl_non_contending : 1;
        unsigned int                    dl_overrun        : 1;
        unsigned int                    dl_server         : 1;
+       unsigned int                    dl_zerolax        : 1;
+       unsigned int                    dl_zerolax_armed  : 1;
 
        /*
         * Bandwidth enforcement timer. Each -deadline task has its

kernel/sched/deadline.c +39 -0

index 1d7b96ca9011..69ee1fbd60e4 100644
@@ -772,6 +772,14 @@ static inline void replenish_dl_new_period(struct sched_dl_entity *dl_se,
        /* for non-boosted task, pi_of(dl_se) == dl_se */
        dl_se->deadline = rq_clock(rq) + pi_of(dl_se)->dl_deadline;
        dl_se->runtime = pi_of(dl_se)->dl_runtime;
+
+       /*
+        * If it is a zerolax reservation, throttle it.
+        */
+       if (dl_se->dl_zerolax) {
+               dl_se->dl_throttled = 1;
+               dl_se->dl_zerolax_armed = 1;
+       }
 }
 
 /*

@@ -828,6 +836,7 @@ static inline void setup_new_dl_entity(struct sched_dl_entity *dl_se)
  * could happen are, typically, a entity voluntarily trying to overcome its
  * runtime, or it just underestimated it during sched_setattr().
  */
+static int start_dl_timer(struct sched_dl_entity *dl_se);
 static void replenish_dl_entity(struct sched_dl_entity *dl_se)
 {
        struct dl_rq *dl_rq = dl_rq_of_se(dl_se);

@@ -874,6 +883,28 @@ static void replenish_dl_entity(struct sched_dl_entity *dl_se)
                dl_se->dl_yielded = 0;
        if (dl_se->dl_throttled)
                dl_se->dl_throttled = 0;
+
+       /*
+        * If this is the replenishment of a zerolax reservation,
+        * clear the flag and return.
+        */
+       if (dl_se->dl_zerolax_armed) {
+               dl_se->dl_zerolax_armed = 0;
+               return;
+       }
+
+       /*
+        * A this point, if the zerolax server is not armed, and the deadline
+        * is in the future, throttle the server and arm the zerolax timer.
+        */
+       if (dl_se->dl_zerolax &&
+           dl_time_before(dl_se->deadline - dl_se->runtime, rq_clock(rq))) {
+               if (!is_dl_boosted(dl_se)) {
+                       dl_se->dl_zerolax_armed = 1;
+                       dl_se->dl_throttled = 1;
+                       start_dl_timer(dl_se);
+               }
+       }
 }
 
 /*

@@ -1024,6 +1055,13 @@ static void update_dl_entity(struct sched_dl_entity *dl_se)
                }
 
                replenish_dl_new_period(dl_se, rq);
+       } else if (dl_server(dl_se) && dl_se->dl_zerolax) {
+               /*
+                * The server can still use its previous deadline, so throttle
+                * and arm the zero-laxity timer.
+                */
+               dl_se->dl_zerolax_armed = 1;
+               dl_se->dl_throttled = 1;
        }
 }
 

@@ -1056,8 +1094,20 @@ static int start_dl_timer(struct sched_dl_entity *dl_se)
         * We want the timer to fire at the deadline, but considering
         * that it is actually coming from rq->clock and not from
         * hrtimer's time base reading.
+        *

kernel/sched/deadline.c static int start_dl_timer(struct sched_dl_entity *dl_se) · line 1106

Quoted 10 lines

kernel/sched/deadline.c +8 -1

+        * The zerolax reservation will have its timer set to the
+        * deadline - runtime. At that point, the CBS rule will decide
+        * if the current deadline can be used, or if a replenishment
+        * is required to avoid add too much pressure on the system
+        * (current u > U).
         */
-       act = ns_to_ktime(dl_next_period(dl_se));
+       if (dl_se->dl_zerolax_armed) {
+               WARN_ON_ONCE(!dl_se->dl_throttled);
+               act = ns_to_ktime(dl_se->deadline - dl_se->runtime);

Just a question, here if dl_se->deadline - dl_se->runtime is large, then does that mean that server activation will be much more into the future? So say I want to give CFS 30%, then it will take 70% of the period before CFS preempts RT thus "starving" CFS for this duration. I think that's Ok for smaller periods and runtimes, though.

Quoted 6 lines

I think it does reserve the amount of required CFS bandwidth so it is probably OK, though it is perhaps letting RT run more initially (say if CFS tasks are not CPU bound and occasionally wake up, they will always be hit by the 70% latency AFAICS which may be large for large periods and small runtimes).

One more consideration I guess is, because the server is throttled till 0-laxity time, it is possible that if CFS sleeps even a bit (after the DL-server is unthrottled), then it will be pushed out to a full current deadline + period due to CBS. In such a situation, if CFS-server is the only DL task running, it might starve RT for a bit more time.

Example, say CFS runtime is 0.3s and period is 1s. At 0.7s, 0-laxity timer fires. CFS runs for 0.29s, then sleeps for 0.005s and wakes up at 0.295s (its remaining runtime is 0.01s at this point which is < the "time till deadline" of 0.005s). Now the runtime of the CFS-server will be replenished to the full 3s (due to CBS) and the deadline pushed out. The end result is the total runtime that the CFS-server actually gets is 0.0595s (though yes it did sleep for 5ms in between, still that's tiny -- say if it briefly blocked on a kernel mutex).

Quoted 164 lines · Joel Fernandes

Quoted 148 lines · Joel Fernandes

Hi Daniel,

Quoted 126 lines · Daniel Bristot de Oliveira

Among the motivations for the DL servers is the real-time throttling mechanism. This mechanism works by throttling the rt_rq after running for a long period without leaving space for fair tasks.

The base dl server avoids this problem by boosting fair tasks instead of throttling the rt_rq. The point is that it boosts without waiting for potential starvation, causing some non-intuitive cases.

For example, an IRQ dispatches two tasks on an idle system, a fair and an RT. The DL server will be activated, running the fair task before the RT one. This problem can be avoided by deferring the dl server activation.

By setting the zerolax option, the dl_server will dispatch an SCHED_DEADLINE reservation with replenished runtime, but throttled.

The dl_timer will be set for (period - runtime) ns from start time. Thus boosting the fair rq on its 0-laxity time with respect to rt_rq.

If the fair scheduler has the opportunity to run while waiting for zerolax time, the dl server runtime will be consumed. If the runtime is completely consumed before the zerolax time, the server will be replenished while still in a throttled state. Then, the dl_timer will be reset to the new zerolax time

If the fair server reaches the zerolax time without consuming its runtime, the server will be boosted, following CBS rules (thus without breaking SCHED_DEADLINE).

Signed-off-by Daniel Bristot de Oliveira <[email protected]>

---
 include/linux/sched.h   |   2 +
 kernel/sched/deadline.c | 100 +++++++++++++++++++++++++++++++++++++++-
 kernel/sched/fair.c     |   3 ++
 3 files changed, 103 insertions(+), 2 deletions(-)

include/linux/sched.h +2 -0

index 5ac1f252e136..56e53e6fd5a0 100644
@@ -660,6 +660,8 @@ struct sched_dl_entity {
        unsigned int                    dl_non_contending : 1;
        unsigned int                    dl_overrun        : 1;
        unsigned int                    dl_server         : 1;
+       unsigned int                    dl_zerolax        : 1;
+       unsigned int                    dl_zerolax_armed  : 1;
 
        /*
         * Bandwidth enforcement timer. Each -deadline task has its

kernel/sched/deadline.c +39 -0

index 1d7b96ca9011..69ee1fbd60e4 100644
@@ -772,6 +772,14 @@ static inline void replenish_dl_new_period(struct sched_dl_entity *dl_se,
        /* for non-boosted task, pi_of(dl_se) == dl_se */
        dl_se->deadline = rq_clock(rq) + pi_of(dl_se)->dl_deadline;
        dl_se->runtime = pi_of(dl_se)->dl_runtime;
+
+       /*
+        * If it is a zerolax reservation, throttle it.
+        */
+       if (dl_se->dl_zerolax) {
+               dl_se->dl_throttled = 1;
+               dl_se->dl_zerolax_armed = 1;
+       }
 }
 
 /*

@@ -828,6 +836,7 @@ static inline void setup_new_dl_entity(struct sched_dl_entity *dl_se)
  * could happen are, typically, a entity voluntarily trying to overcome its
  * runtime, or it just underestimated it during sched_setattr().
  */
+static int start_dl_timer(struct sched_dl_entity *dl_se);
 static void replenish_dl_entity(struct sched_dl_entity *dl_se)
 {
        struct dl_rq *dl_rq = dl_rq_of_se(dl_se);

@@ -874,6 +883,28 @@ static void replenish_dl_entity(struct sched_dl_entity *dl_se)
                dl_se->dl_yielded = 0;
        if (dl_se->dl_throttled)
                dl_se->dl_throttled = 0;
+
+       /*
+        * If this is the replenishment of a zerolax reservation,
+        * clear the flag and return.
+        */
+       if (dl_se->dl_zerolax_armed) {
+               dl_se->dl_zerolax_armed = 0;
+               return;
+       }
+
+       /*
+        * A this point, if the zerolax server is not armed, and the deadline
+        * is in the future, throttle the server and arm the zerolax timer.
+        */
+       if (dl_se->dl_zerolax &&
+           dl_time_before(dl_se->deadline - dl_se->runtime, rq_clock(rq))) {
+               if (!is_dl_boosted(dl_se)) {
+                       dl_se->dl_zerolax_armed = 1;
+                       dl_se->dl_throttled = 1;
+                       start_dl_timer(dl_se);
+               }
+       }
 }
 
 /*

@@ -1024,6 +1055,13 @@ static void update_dl_entity(struct sched_dl_entity *dl_se)
                }
 
                replenish_dl_new_period(dl_se, rq);
+       } else if (dl_server(dl_se) && dl_se->dl_zerolax) {
+               /*
+                * The server can still use its previous deadline, so throttle
+                * and arm the zero-laxity timer.
+                */
+               dl_se->dl_zerolax_armed = 1;
+               dl_se->dl_throttled = 1;
        }
 }
 

@@ -1056,8 +1094,20 @@ static int start_dl_timer(struct sched_dl_entity *dl_se)
         * We want the timer to fire at the deadline, but considering
         * that it is actually coming from rq->clock and not from
         * hrtimer's time base reading.
+        *

kernel/sched/deadline.c static int start_dl_timer(struct sched_dl_entity *dl_se) · line 1106

Quoted 10 lines

kernel/sched/deadline.c +8 -1

+        * The zerolax reservation will have its timer set to the
+        * deadline - runtime. At that point, the CBS rule will decide
+        * if the current deadline can be used, or if a replenishment
+        * is required to avoid add too much pressure on the system
+        * (current u > U).
         */
-       act = ns_to_ktime(dl_next_period(dl_se));
+       if (dl_se->dl_zerolax_armed) {
+               WARN_ON_ONCE(!dl_se->dl_throttled);
+               act = ns_to_ktime(dl_se->deadline - dl_se->runtime);

Just a question, here if dl_se->deadline - dl_se->runtime is large, then does that mean that server activation will be much more into the future? So say I want to give CFS 30%, then it will take 70% of the period before CFS preempts RT thus "starving" CFS for this duration. I think that's Ok for smaller periods and runtimes, though.

Quoted 6 lines

I think it does reserve the amount of required CFS bandwidth so it is probably OK, though it is perhaps letting RT run more initially (say if CFS tasks are not CPU bound and occasionally wake up, they will always be hit by the 70% latency AFAICS which may be large for large periods and small runtimes).

One more consideration I guess is, because the server is throttled till 0-laxity time, it is possible that if CFS sleeps even a bit (after the DL-server is unthrottled), then it will be pushed out to a full current deadline + period due to CBS. In such a situation, if CFS-server is the only DL task running, it might starve RT for a bit more time.

Quoted 8 lines

Example, say CFS runtime is 0.3s and period is 1s. At 0.7s, 0-laxity timer fires. CFS runs for 0.29s, then sleeps for 0.005s and wakes up at 0.295s (its remaining runtime is 0.01s at this point which is < the "time till deadline" of 0.005s). Now the runtime of the CFS-server will be replenished to the full 3s (due to CBS) and the deadline pushed out. The end result is the total runtime that the CFS-server actually gets is 0.0595s (though yes it did sleep for 5ms in between, still that's tiny -- say if it briefly blocked on a kernel mutex).

Blah, I got lost in decimal points. Here's the example again:

Say CFS-server runtime is 0.3s and period is 1s.

At 0.7s, 0-laxity timer fires. CFS runs for 0.29s, then sleeps for 0.005s and wakes up at 0.295s (its remaining runtime is 0.01s at this point which is < the "time till deadline" of 0.005s)

Now the runtime of the CFS-server will be replenished to the full 0.3s (due to CBS) and the deadline
pushed out.

The end result is, the total runtime that the CFS-server actually gets is 0.595s (though yes it did sleep for 5ms in between, still that's tiny -- say if it briefly blocked on a kernel mutex). That's almost double the allocated runtime.

This is just theoretical and I have yet to see if it is actually an issue in practice.

Thanks.

Quoted 24 lines

Quoted 7 lines

One more consideration I guess is, because the server is throttled till 0-laxity time, it is possible that if CFS sleeps even a bit (after the DL-server is unthrottled), then it will be pushed out to a full current deadline + period due to CBS. In such a situation, if CFS-server is the only DL task running, it might starve RT for a bit more time.

Quoted 8 lines

Example, say CFS runtime is 0.3s and period is 1s. At 0.7s, 0-laxity timer fires. CFS runs for 0.29s, then sleeps for 0.005s and wakes up at 0.295s (its remaining runtime is 0.01s at this point which is < the "time till deadline" of 0.005s). Now the runtime of the CFS-server will be replenished to the full 3s (due to CBS) and the deadline pushed out. The end result is the total runtime that the CFS-server actually gets is 0.0595s (though yes it did sleep for 5ms in between, still that's tiny -- say if it briefly blocked on a kernel mutex).

Blah, I got lost in decimal points. Here's the example again:

Say CFS-server runtime is 0.3s and period is 1s.

At 0.7s, 0-laxity timer fires. CFS runs for 0.29s, then sleeps for 0.005s and wakes up at 0.295s (its remaining runtime is 0.01s at this point which is < the "time till deadline" of 0.005s)

Quoted 8 lines

Now the runtime of the CFS-server will be replenished to the full 0.3s (due to CBS) and the deadline
pushed out.

The end result is, the total runtime that the CFS-server actually gets is 0.595s (though yes it did sleep for 5ms in between, still that's tiny -- say if it briefly blocked on a kernel mutex). That's almost double the allocated runtime.

I think I got what you mean, and I think I took for granted that we were doing overload control on the replenishment, but it seems that we are not..

I just got back from a doct appt, I will do a proper reply later today.

Say CFS-server runtime is 0.3s and period is 1s.

At 0.7s, 0-laxity timer fires. CFS runs for 0.29s, then sleeps for 0.005s and wakes up at 0.295s (its remaining runtime is 0.01s at this point which is < the "time till deadline" of 0.005s)

Now the runtime of the CFS-server will be replenished to the full 0.3s (due to CBS) and the deadline
pushed out.

The end result is, the total runtime that the CFS-server actually gets is 0.595s (though yes it did sleep for 5ms in between, still that's tiny -- say if it briefly blocked on a kernel mutex). That's almost double the allocated runtime.

This is just theoretical and I have yet to see if it is actually an issue in practice.

Let me see if I understand what you are asking. By pushing the execution of the CFS-server to the end of its period, if it it was briefly blocked and was not able to consume all of its zerolax time, its bandwidth gets refreshed. Then it can run again, basically doubling its total time.

But this is basically saying that it ran for its runtime at the start of one period and at the beginning of another, right?

Is that an issue? The CFS-server is still just consuming it's time per period. That means that an RT tasks was starving the system that much to push it forward too much anyway. I wonder if we just document this behavior, if that would be enough?

I ran my migrate[1] program which I use to test RT migration, and it kicks

And ran my userspin[2] program. And recorded it with:

I'll also test this without any of the patches first.

Quoted 10 lines · On Mon, 6 Nov 2023 16:37:32 -0500 Joel Fernandes <[email protected]> wrote:

Say CFS-server runtime is 0.3s and period is 1s.

At 0.7s, 0-laxity timer fires. CFS runs for 0.29s, then sleeps for 0.005s and wakes up at 0.295s (its remaining runtime is 0.01s at this point which is < the "time till deadline" of 0.005s)

Now the runtime of the CFS-server will be replenished to the full 0.3s (due to CBS) and the deadline
pushed out.

Quoted 7 lines

The end result is, the total runtime that the CFS-server actually gets is 0.595s (though yes it did sleep for 5ms in between, still that's tiny -- say if it briefly blocked on a kernel mutex). That's almost double the allocated runtime.

This is just theoretical and I have yet to see if it is actually an issue in practice.

Let me see if I understand what you are asking. By pushing the execution of the CFS-server to the end of its period, if it it was briefly blocked and was not able to consume all of its zerolax time, its bandwidth gets refreshed. Then it can run again, basically doubling its total time.

But this is basically saying that it ran for its runtime at the start of one period and at the beginning of another, right?

Is that an issue? The CFS-server is still just consuming it's time per period. That means that an RT tasks was starving the system that much to push it forward too much anyway. I wonder if we just document this behavior, if that would be enough?

The code is not doing what I intended because I thought it was doing overload control on the replenishment, but it is not (my bad).

Quoted 4 lines

The code is not doing what I intended because I thought it was doing overload control on the replenishment, but it is not (my bad).

I am still testing but... it is missing something like this (famous last words).

kernel/sched/deadline.c +8 -0

index 1092ca8892e0..6e2d21c47a04 100644
@@ -842,6 +842,8 @@ static inline void setup_new_dl_entity(struct sched_dl_entity *dl_se)
  * runtime, or it just underestimated it during sched_setattr().
  */
 static int start_dl_timer(struct sched_dl_entity *dl_se);
+static bool dl_entity_overflow(struct sched_dl_entity *dl_se, u64 t);
+
 static void replenish_dl_entity(struct sched_dl_entity *dl_se)
 {
        struct dl_rq *dl_rq = dl_rq_of_se(dl_se);

@@ -852,9 +854,18 @@ static void replenish_dl_entity(struct sched_dl_entity *dl_se)
        /*
         * This could be the case for a !-dl task that is boosted.
         * Just go with full inherited parameters.
+        *
+        * Or, it could be the case of a zerolax reservation that
+        * was not able to consume its runtime in background and
+        * reached this point with current u > U.
+        *
+        * In both cases, set a new period.
         */

Hi Daniel,

Quoted 39 lines · Daniel Bristot de Oliveira

Quoted 4 lines

The code is not doing what I intended because I thought it was doing overload control on the replenishment, but it is not (my bad).

I am still testing but... it is missing something like this (famous last words).

kernel/sched/deadline.c +13 -2

index 1092ca8892e0..6e2d21c47a04 100644
@@ -842,6 +842,8 @@ static inline void setup_new_dl_entity(struct sched_dl_entity *dl_se)
  * runtime, or it just underestimated it during sched_setattr().
  */
 static int start_dl_timer(struct sched_dl_entity *dl_se);
+static bool dl_entity_overflow(struct sched_dl_entity *dl_se, u64 t);
+
 static void replenish_dl_entity(struct sched_dl_entity *dl_se)
 {
        struct dl_rq *dl_rq = dl_rq_of_se(dl_se);

@@ -852,9 +854,18 @@ static void replenish_dl_entity(struct sched_dl_entity *dl_se)
        /*
         * This could be the case for a !-dl task that is boosted.
         * Just go with full inherited parameters.
+        *
+        * Or, it could be the case of a zerolax reservation that
+        * was not able to consume its runtime in background and
+        * reached this point with current u > U.
+        *
+        * In both cases, set a new period.
         */
-       if (dl_se->dl_deadline == 0)
-               replenish_dl_new_period(dl_se, rq);
+       if (dl_se->dl_deadline == 0 ||
+               (dl_se->dl_zerolax_armed && dl_entity_overflow(dl_se, rq_clock(rq)))) {
+                       dl_se->deadline = rq_clock(rq) + pi_of(dl_se)->dl_deadline;
+                       dl_se->runtime = pi_of(dl_se)->dl_runtime;
+       }
 

kernel/sched/deadline.c static void replenish_dl_entity(struct sched_dl_entity *dl_se) · line 871

Quoted 2 lines

kernel/sched/deadline.c +0 -0

        if (dl_se->dl_yielded && dl_se->runtime > 0)
                dl_se->runtime = 0;

I was wondering does this mean GRUB needs to be enabled? Otherwise I can see that "runtime / (deadline - t) > dl_runtime / dl_deadline" will be true almost all the time due to the constraint of executing at the 0-lax time.

Because at the 0-lax time, AFAICS this will be 100% > 30% (say if CFS has a 30% reservation).

And I think even if GRUB is enabled, it is possible other DL task may have reserved bandwidth.

Or is there a subtlety that makes that not possible?

thanks,

- Joel

Quoted 43 lines · Joel Fernandes

Hi Daniel,

Quoted 39 lines · Daniel Bristot de Oliveira

Quoted 4 lines

The code is not doing what I intended because I thought it was doing overload control on the replenishment, but it is not (my bad).

I am still testing but... it is missing something like this (famous last words).

kernel/sched/deadline.c +13 -2

index 1092ca8892e0..6e2d21c47a04 100644
@@ -842,6 +842,8 @@ static inline void setup_new_dl_entity(struct sched_dl_entity *dl_se)
  * runtime, or it just underestimated it during sched_setattr().
  */
 static int start_dl_timer(struct sched_dl_entity *dl_se);
+static bool dl_entity_overflow(struct sched_dl_entity *dl_se, u64 t);
+
 static void replenish_dl_entity(struct sched_dl_entity *dl_se)
 {
        struct dl_rq *dl_rq = dl_rq_of_se(dl_se);

@@ -852,9 +854,18 @@ static void replenish_dl_entity(struct sched_dl_entity *dl_se)
        /*
         * This could be the case for a !-dl task that is boosted.
         * Just go with full inherited parameters.
+        *
+        * Or, it could be the case of a zerolax reservation that
+        * was not able to consume its runtime in background and
+        * reached this point with current u > U.
+        *
+        * In both cases, set a new period.
         */
-       if (dl_se->dl_deadline == 0)
-               replenish_dl_new_period(dl_se, rq);
+       if (dl_se->dl_deadline == 0 ||
+               (dl_se->dl_zerolax_armed && dl_entity_overflow(dl_se, rq_clock(rq)))) {
+                       dl_se->deadline = rq_clock(rq) + pi_of(dl_se)->dl_deadline;
+                       dl_se->runtime = pi_of(dl_se)->dl_runtime;
+       }
 

Quoted 7 lines

kernel/sched/deadline.c static void replenish_dl_entity(struct sched_dl_entity *dl_se) · line 871

Quoted 2 lines

kernel/sched/deadline.c +0 -0

        if (dl_se->dl_yielded && dl_se->runtime > 0)
                dl_se->runtime = 0;

I was wondering does this mean GRUB needs to be enabled? Otherwise I can see that "runtime / (deadline - t) > dl_runtime / dl_deadline" will be true almost all the time due to the constraint of executing at the 0-lax time.

No grub needed. It will only happen if the fair server did not have any chance to run.

If it happens, it is not a problem, see that timeline I replied in the previous email.

We do not want a zerolax scheduler, because it breaks everything else. It is a deferred EDF, that looking from wall clock, composes an "zerolaxish" timeline.

Quoted 3 lines

The code is not doing what I intended because I thought it was doing overload control on the replenishment, but it is not (my bad).

I am still testing but... it is missing something like this (famous last words).

kernel/sched/deadline.c +8 -0

index 1092ca8892e0..6e2d21c47a04 100644
@@ -842,6 +842,8 @@ static inline void setup_new_dl_entity(struct sched_dl_entity *dl_se)
  * runtime, or it just underestimated it during sched_setattr().
  */
 static int start_dl_timer(struct sched_dl_entity *dl_se);
+static bool dl_entity_overflow(struct sched_dl_entity *dl_se, u64 t);
+
 static void replenish_dl_entity(struct sched_dl_entity *dl_se)
 {
 	struct dl_rq *dl_rq = dl_rq_of_se(dl_se);

@@ -852,9 +854,18 @@ static void replenish_dl_entity(struct sched_dl_entity *dl_se)
 	/*
 	 * This could be the case for a !-dl task that is boosted.
 	 * Just go with full inherited parameters.
+	 *
+	 * Or, it could be the case of a zerolax reservation that
+	 * was not able to consume its runtime in background and
+	 * reached this point with current u > U.
+	 *
+	 * In both cases, set a new period.
 	 */

Should we rather not cap the runtime, something like so?

---

kernel/sched/deadline.c +3 -1

index 58b542bf2893..1453a2cd0680 100644
@@ -829,10 +829,12 @@ static inline void setup_new_dl_entity(struct sched_dl_entity *dl_se)
  */
 static void replenish_dl_entity(struct sched_dl_entity *dl_se)
 {
+	struct sched_dl_entity *pi_se = pi_of(dl_se);
 	struct dl_rq *dl_rq = dl_rq_of_se(dl_se);
 	struct rq *rq = rq_of_dl_rq(dl_rq);
+	u64 dl_runtime = pi_se->dl_runtime;
 
-	WARN_ON_ONCE(pi_of(dl_se)->dl_runtime <= 0);
+	WARN_ON_ONCE(dl_runtime <= 0);
 
 	/*
 	 * This could be the case for a !-dl task that is boosted.

@@ -851,10 +853,13 @@ static void replenish_dl_entity(struct sched_dl_entity *dl_se)
 	 * arbitrary large.
 	 */

kernel/sched/deadline.c +0 -0

 	/*
 	 * At this point, the deadline really should be "in
 	 * the future" with respect to rq->clock. If it's

kernel/sched/deadline.c static inline void setup_new_dl_entity(struct sched_dl_entity *dl_se) · line 830

Quoted 8 lines

---

kernel/sched/deadline.c +0 -0

index 58b542bf2893..1453a2cd0680 100644
@@ -829,10 +829,12 @@ static inline void setup_new_dl_entity(struct sched_dl_entity *dl_se)
  */
 static void replenish_dl_entity(struct sched_dl_entity *dl_se)>>  {

Quoted 5 lines

kernel/sched/deadline.c +2 -0

+	struct sched_dl_entity *pi_se = pi_of(dl_se);
 	struct dl_rq *dl_rq = dl_rq_of_se(dl_se);
 	struct rq *rq = rq_of_dl_rq(dl_rq);
+	u64 dl_runtime = pi_se->dl_runtime;
 

kernel/sched/deadline.c static void replenish_dl_entity(struct sched_dl_entity *dl_se) · line 854

Quoted 8 lines

kernel/sched/deadline.c +1 -1

-	WARN_ON_ONCE(pi_of(dl_se)->dl_runtime <= 0);
+	WARN_ON_ONCE(dl_runtime <= 0);
 
 	/*
 	 * This could be the case for a !-dl task that is boosted.

@@ -851,10 +853,13 @@ static void replenish_dl_entity(struct sched_dl_entity *dl_se)
 	 * arbitrary large.
 	 */

kernel/sched/deadline.c static void replenish_dl_entity(struct sched_dl_entity *dl_se) · line 858

Quoted 6 lines

kernel/sched/deadline.c +2 -2

 	while (dl_se->runtime <= 0) {
-		dl_se->deadline += pi_of(dl_se)->dl_period;
-		dl_se->runtime += pi_of(dl_se)->dl_runtime;
+		dl_se->deadline += pi_se->dl_period;
+		dl_se->runtime += dl_runtime;
 	}

kernel/sched/deadline.c static void replenish_dl_entity(struct sched_dl_entity *dl_se) · line 862

Quoted 3 lines

kernel/sched/deadline.c +3 -0

+	if (dl_se->zerolax && dl_se->runtime > dl_runtime)
+		dl_se->runtime = dl_runtime;
+

This should ofcourse go in the if (dl_se->dl_zerolax_armed) branch a little down from here.

Because the above also causes period drift, which we do not want.

Should we rather not cap the runtime, something like so?

Because the above also causes period drift, which we do not want.

Quoted 38 lines · Daniel Bristot de Oliveira

Quoted 3 lines

The code is not doing what I intended because I thought it was doing overload control on the replenishment, but it is not (my bad).

I am still testing but... it is missing something like this (famous last words).

kernel/sched/deadline.c +13 -2

index 1092ca8892e0..6e2d21c47a04 100644
@@ -842,6 +842,8 @@ static inline void setup_new_dl_entity(struct sched_dl_entity *dl_se)
  * runtime, or it just underestimated it during sched_setattr().
  */
 static int start_dl_timer(struct sched_dl_entity *dl_se);
+static bool dl_entity_overflow(struct sched_dl_entity *dl_se, u64 t);
+
 static void replenish_dl_entity(struct sched_dl_entity *dl_se)
 {
 	struct dl_rq *dl_rq = dl_rq_of_se(dl_se);

@@ -852,9 +854,18 @@ static void replenish_dl_entity(struct sched_dl_entity *dl_se)
 	/*
 	 * This could be the case for a !-dl task that is boosted.
 	 * Just go with full inherited parameters.
+	 *
+	 * Or, it could be the case of a zerolax reservation that
+	 * was not able to consume its runtime in background and
+	 * reached this point with current u > U.
+	 *
+	 * In both cases, set a new period.
 	 */
-	if (dl_se->dl_deadline == 0)
-		replenish_dl_new_period(dl_se, rq);
+	if (dl_se->dl_deadline == 0 ||
+		(dl_se->dl_zerolax_armed && dl_entity_overflow(dl_se, rq_clock(rq)))) {
+			dl_se->deadline = rq_clock(rq) + pi_of(dl_se)->dl_deadline;
+			dl_se->runtime = pi_of(dl_se)->dl_runtime;
+	}
 

kernel/sched/deadline.c static void replenish_dl_entity(struct sched_dl_entity *dl_se) · line 871

Quoted 2 lines

kernel/sched/deadline.c +0 -0

 	if (dl_se->dl_yielded && dl_se->runtime > 0)
 		dl_se->runtime = 0;

Should we rather not cap the runtime, something like so?

Because the above also causes period drift, which we do not want.

---

kernel/sched/deadline.c +3 -1

index 58b542bf2893..1453a2cd0680 100644
@@ -829,10 +829,12 @@ static inline void setup_new_dl_entity(struct sched_dl_entity *dl_se)
  */
 static void replenish_dl_entity(struct sched_dl_entity *dl_se)
 {
+	struct sched_dl_entity *pi_se = pi_of(dl_se);
 	struct dl_rq *dl_rq = dl_rq_of_se(dl_se);
 	struct rq *rq = rq_of_dl_rq(dl_rq);
+	u64 dl_runtime = pi_se->dl_runtime;
 
-	WARN_ON_ONCE(pi_of(dl_se)->dl_runtime <= 0);
+	WARN_ON_ONCE(dl_runtime <= 0);
 
 	/*
 	 * This could be the case for a !-dl task that is boosted.

@@ -851,10 +853,13 @@ static void replenish_dl_entity(struct sched_dl_entity *dl_se)
 	 * arbitrary large.
 	 */

kernel/sched/deadline.c static void replenish_dl_entity(struct sched_dl_entity *dl_se) · line 862

Quoted 3 lines

kernel/sched/deadline.c +3 -0

+	if (dl_se->zerolax && dl_se->runtime > dl_runtime)
+		dl_se->runtime = dl_runtime;
+

Anyway, I have the impression that this breaks EDF/CBS, as we are letting the dl_server run with full dl_runtime w/o postponing the period (essentially an u = 1 reservation until runtime is depleted).

Quoted 15 lines · On Mon, 6 Nov 2023 16:37:32 -0500 Joel Fernandes <[email protected]> wrote:

Say CFS-server runtime is 0.3s and period is 1s.

At 0.7s, 0-laxity timer fires. CFS runs for 0.29s, then sleeps for 0.005s and wakes up at 0.295s (its remaining runtime is 0.01s at this point which is < the "time till deadline" of 0.005s)

Now the runtime of the CFS-server will be replenished to the full 0.3s (due to CBS) and the deadline
pushed out.

The end result is, the total runtime that the CFS-server actually gets is 0.595s (though yes it did sleep for 5ms in between, still that's tiny -- say if it briefly blocked on a kernel mutex). That's almost double the allocated runtime.

Quoted 2 lines

This is just theoretical and I have yet to see if it is actually an issue in practice.

Let me see if I understand what you are asking. By pushing the execution of the CFS-server to the end of its period, if it it was briefly blocked and was not able to consume all of its zerolax time, its bandwidth gets refreshed. Then it can run again, basically doubling its total time.

But this is basically saying that it ran for its runtime at the start of one period and at the beginning of another, right?

Hi Daniel,

Quoted 134 lines · Daniel Bristot de Oliveira

Among the motivations for the DL servers is the real-time throttling mechanism. This mechanism works by throttling the rt_rq after running for a long period without leaving space for fair tasks.

The base dl server avoids this problem by boosting fair tasks instead of throttling the rt_rq. The point is that it boosts without waiting for potential starvation, causing some non-intuitive cases.

For example, an IRQ dispatches two tasks on an idle system, a fair and an RT. The DL server will be activated, running the fair task before the RT one. This problem can be avoided by deferring the dl server activation.

By setting the zerolax option, the dl_server will dispatch an SCHED_DEADLINE reservation with replenished runtime, but throttled.

The dl_timer will be set for (period - runtime) ns from start time. Thus boosting the fair rq on its 0-laxity time with respect to rt_rq.

If the fair scheduler has the opportunity to run while waiting for zerolax time, the dl server runtime will be consumed. If the runtime is completely consumed before the zerolax time, the server will be replenished while still in a throttled state. Then, the dl_timer will be reset to the new zerolax time

If the fair server reaches the zerolax time without consuming its runtime, the server will be boosted, following CBS rules (thus without breaking SCHED_DEADLINE).

Signed-off-by Daniel Bristot de Oliveira <[email protected]>

---
 include/linux/sched.h   |   2 +
 kernel/sched/deadline.c | 100 +++++++++++++++++++++++++++++++++++++++-
 kernel/sched/fair.c     |   3 ++
 3 files changed, 103 insertions(+), 2 deletions(-)

include/linux/sched.h +2 -0

index 5ac1f252e136..56e53e6fd5a0 100644
@@ -660,6 +660,8 @@ struct sched_dl_entity {
        unsigned int                    dl_non_contending : 1;
        unsigned int                    dl_overrun        : 1;
        unsigned int                    dl_server         : 1;
+       unsigned int                    dl_zerolax        : 1;
+       unsigned int                    dl_zerolax_armed  : 1;
 
        /*
         * Bandwidth enforcement timer. Each -deadline task has its

kernel/sched/deadline.c +45 -1

index 1d7b96ca9011..69ee1fbd60e4 100644
@@ -772,6 +772,14 @@ static inline void replenish_dl_new_period(struct sched_dl_entity *dl_se,
        /* for non-boosted task, pi_of(dl_se) == dl_se */
        dl_se->deadline = rq_clock(rq) + pi_of(dl_se)->dl_deadline;
        dl_se->runtime = pi_of(dl_se)->dl_runtime;
+
+       /*
+        * If it is a zerolax reservation, throttle it.
+        */
+       if (dl_se->dl_zerolax) {
+               dl_se->dl_throttled = 1;
+               dl_se->dl_zerolax_armed = 1;
+       }
 }
 
 /*

@@ -828,6 +836,7 @@ static inline void setup_new_dl_entity(struct sched_dl_entity *dl_se)
  * could happen are, typically, a entity voluntarily trying to overcome its
  * runtime, or it just underestimated it during sched_setattr().
  */
+static int start_dl_timer(struct sched_dl_entity *dl_se);
 static void replenish_dl_entity(struct sched_dl_entity *dl_se)
 {
        struct dl_rq *dl_rq = dl_rq_of_se(dl_se);

@@ -874,6 +883,28 @@ static void replenish_dl_entity(struct sched_dl_entity *dl_se)
                dl_se->dl_yielded = 0;
        if (dl_se->dl_throttled)
                dl_se->dl_throttled = 0;
+
+       /*
+        * If this is the replenishment of a zerolax reservation,
+        * clear the flag and return.
+        */
+       if (dl_se->dl_zerolax_armed) {
+               dl_se->dl_zerolax_armed = 0;
+               return;
+       }
+
+       /*
+        * A this point, if the zerolax server is not armed, and the deadline
+        * is in the future, throttle the server and arm the zerolax timer.
+        */
+       if (dl_se->dl_zerolax &&
+           dl_time_before(dl_se->deadline - dl_se->runtime, rq_clock(rq))) {
+               if (!is_dl_boosted(dl_se)) {
+                       dl_se->dl_zerolax_armed = 1;
+                       dl_se->dl_throttled = 1;
+                       start_dl_timer(dl_se);
+               }
+       }
 }
 
 /*

@@ -1024,6 +1055,13 @@ static void update_dl_entity(struct sched_dl_entity *dl_se)
                }
 
                replenish_dl_new_period(dl_se, rq);
+       } else if (dl_server(dl_se) && dl_se->dl_zerolax) {
+               /*
+                * The server can still use its previous deadline, so throttle
+                * and arm the zero-laxity timer.
+                */
+               dl_se->dl_zerolax_armed = 1;
+               dl_se->dl_throttled = 1;
        }
 }
 

@@ -1056,8 +1094,20 @@ static int start_dl_timer(struct sched_dl_entity *dl_se)
         * We want the timer to fire at the deadline, but considering
         * that it is actually coming from rq->clock and not from
         * hrtimer's time base reading.
+        *
+        * The zerolax reservation will have its timer set to the
+        * deadline - runtime. At that point, the CBS rule will decide
+        * if the current deadline can be used, or if a replenishment
+        * is required to avoid add too much pressure on the system
+        * (current u > U).
         */
-       act = ns_to_ktime(dl_next_period(dl_se));
+       if (dl_se->dl_zerolax_armed) {

kernel/sched/deadline.c static int start_dl_timer(struct sched_dl_entity *dl_se) · line 1106

Quoted 2 lines

kernel/sched/deadline.c +2 -0

+               WARN_ON_ONCE(!dl_se->dl_throttled);
+               act = ns_to_ktime(dl_se->deadline - dl_se->runtime);

Just a question, here if dl_se->deadline - dl_se->runtime is large, then does that mean that server activation will be much more into the future? So say I want to give CFS 30%, then it will take 70% of the period before CFS preempts RT thus "starving" CFS for this duration. I think that's Ok for smaller periods and runtimes, though.

- Joel

Among the motivations for the DL servers is the real-time throttling mechanism. This mechanism works by throttling the rt_rq after running for a long period without leaving space for fair tasks.

The base dl server avoids this problem by boosting fair tasks instead of throttling the rt_rq. The point is that it boosts without waiting for potential starvation, causing some non-intuitive cases.

For example, an IRQ dispatches two tasks on an idle system, a fair and an RT. The DL server will be activated, running the fair task before the RT one. This problem can be avoided by deferring the dl server activation.

By setting the zerolax option, the dl_server will dispatch an SCHED_DEADLINE reservation with replenished runtime, but throttled.

The dl_timer will be set for (period - runtime) ns from start time. Thus boosting the fair rq on its 0-laxity time with respect to rt_rq.

If the fair scheduler has the opportunity to run while waiting for zerolax time, the dl server runtime will be consumed. If the runtime is completely consumed before the zerolax time, the server will be replenished while still in a throttled state. Then, the dl_timer will be reset to the new zerolax time

If the fair server reaches the zerolax time without consuming its runtime, the server will be boosted, following CBS rules (thus without breaking SCHED_DEADLINE).

Signed-off-by Daniel Bristot de Oliveira <[email protected]>

Quoted 26 lines · Daniel Bristot de Oliveira

Among the motivations for the DL servers is the real-time throttling mechanism. This mechanism works by throttling the rt_rq after running for a long period without leaving space for fair tasks.

The base dl server avoids this problem by boosting fair tasks instead of throttling the rt_rq. The point is that it boosts without waiting for potential starvation, causing some non-intuitive cases.

For example, an IRQ dispatches two tasks on an idle system, a fair and an RT. The DL server will be activated, running the fair task before the RT one. This problem can be avoided by deferring the dl server activation.

By setting the zerolax option, the dl_server will dispatch an SCHED_DEADLINE reservation with replenished runtime, but throttled.

The dl_timer will be set for (period - runtime) ns from start time. Thus boosting the fair rq on its 0-laxity time with respect to rt_rq.

If the fair scheduler has the opportunity to run while waiting for zerolax time, the dl server runtime will be consumed. If the runtime is completely consumed before the zerolax time, the server will be replenished while still in a throttled state. Then, the dl_timer will be reset to the new zerolax time

Quoted 3 lines

If the fair server reaches the zerolax time without consuming its runtime, the server will be boosted, following CBS rules (thus without breaking SCHED_DEADLINE).

Quoted 1 line

Signed-off-by Daniel Bristot de Oliveira <[email protected]>

Hi, Daniel,
We have one additional patch (other than the 15 I just sent).

3 more working days for the next 3 weeks, I thought I might as well reply inline here since it might be unnecessary to resend all 15 patches so soon just for the one new addition below. I am replying to this patch here, because the new patch is related (to 0-laxity). But once I am back from holiday, I can resend it with the set I have unless you've applied it.

So, Vineeth and me came up with a patch below to "max cap" the DL server 0-lax time (max cap is default off keeping the regular behavior). This is needed to guarantee bandwidth for periodic CFS runners/sleepers.

The example usecase is:

Consider DL server params 25ms / 50ms.

Consider CFS task with duty cycle of 25ms / 76ms (run 25ms sleep 51ms).

run 25ms run 25ms
_______ _______
| | sleep 51 | | sleep 51
-|------|-------|---------|---------|-------|----------|--------|------> t
0 25 50 101 126 151 202 227
\ 0-lax / \ 0-lax /

Here the 0-lax addition in the original v5's zero-lax patch causes lesser bandwidth.

So the task runs 50ms every 227ms, instead of 50ms every 152ms.

A simple unit test confirms the issue, and it is fixed by Vineeth's patch below:

Please take a look at the patch below (applies only to v5.15 but Vineeth is rebase on mainline as we speak), thanks.

-----8<--------
From: Vineeth Pillai (Google) <[email protected]>
Subject: [PATCH] sched/deadline/dlserver: sysctl for dlserver maxdefer time

Inorder to avoid dlserver preempting RT tasks when it wakes up, dlserver is throttled(deferred) until zero lax time. This is the farthest time before deadline where dlserver can meet its deadline.

Zero lax time causes cfs tasks with sleep/run pattern where the cfs tasks doesn't get the bandwidth promised by dlserver. So introduce a sysctl for limiting the defer time of dlserver.

Suggested-by Joel Fernandes (Google) <[email protected]>

Signed-off-by Vineeth Pillai (Google) <[email protected]>

---
 include/linux/sched/sysctl.h | 2 ++
 kernel/sched/deadline.c      | 6 ++++++
 kernel/sysctl.c              | 7 +++++++
 3 files changed, 15 insertions(+)

include/linux/sched/sysctl.h +1 -0

index 4939e6128840..a27fba6fe0ab 100644
@@ -41,6 +41,8 @@ extern unsigned int sysctl_iowait_apply_ticks;
 extern unsigned int sysctl_sched_dl_period_max;
 extern unsigned int sysctl_sched_dl_period_min;
 +extern unsigned int sysctl_sched_dlserver_maxdefer_ms;
+
 #ifdef CONFIG_UCLAMP_TASK
 extern unsigned int sysctl_sched_uclamp_util_min;
 extern unsigned int sysctl_sched_uclamp_util_max;

kernel/sched/deadline.c +0 -0

index d638cc5b45c7..69c9fd80a67d 100644

Quoted 16 lines · Joel Fernandes

Quoted 13 lines · Daniel Bristot de Oliveira

Among the motivations for the DL servers is the real-time throttling mechanism. This mechanism works by throttling the rt_rq after running for a long period without leaving space for fair tasks.

The base dl server avoids this problem by boosting fair tasks instead of throttling the rt_rq. The point is that it boosts without waiting for potential starvation, causing some non-intuitive cases.

For example, an IRQ dispatches two tasks on an idle system, a fair and an RT. The DL server will be activated, running the fair task before the RT one. This problem can be avoided by deferring the dl server activation.

Quoted 5 lines

Quoted 5 lines

By setting the zerolax option, the dl_server will dispatch an SCHED_DEADLINE reservation with replenished runtime, but throttled.

The dl_timer will be set for (period - runtime) ns from start time. Thus boosting the fair rq on its 0-laxity time with respect to

Quoted 5 lines

Quoted 5 lines

rt_rq.

If the fair scheduler has the opportunity to run while waiting for zerolax time, the dl server runtime will be consumed. If the runtime is completely consumed before the zerolax time, the

Quoted 6 lines

Quoted 6 lines

server will be replenished while still in a throttled state. Then, the dl_timer will be reset to the new zerolax time

If the fair server reaches the zerolax time without consuming its runtime, the server will be boosted, following CBS rules (thus without breaking SCHED_DEADLINE).

notice: at this point in history, the term zero-laxity was removed from the latest code we have, the term was moved to defer server... I will remove from the long in the next time I send it.

Quoted 4 lines

Quoted 1 line

Signed-off-by Daniel Bristot de Oliveira <[email protected]>

Hi, Daniel,
We have one additional patch (other than the 15 I just sent).

Those 15 are the next thing I will review... I was working in the merge window.

Since I have just

Quoted 5 lines

3 more working days for the next 3 weeks, I thought I might as well reply inline here since it might be unnecessary to resend all 15 patches so soon just for the one new addition below. I am replying to this patch here, because the new patch is related (to 0-laxity). But once I am back from holiday, I can resend it with the set I have unless you've applied it.

before starting... in three weeks, we will be very far still from any attempt to ping Peter & ingo to ask if they could think about putting us into a queue.

Have fun :-)

as I explained at LPC.. and in chat... there is no "0-laxity", and repeating it only creates more confusion.

Let's use a deferred server... a regular deadline
reservation with deferred starting time at (now + period - runtime), and at that point il will receive a new deadline one period away - (not one runtime away).

There will always be a person reading these emails and echoing the wrong things... using 0-lax/0-laxity term here is a lose-lose.

Quoted 3 lines

So, Vineeth and me came up with a patch below to "max cap" the DL server 0-lax time (max cap is default off keeping the regular behavior). This is needed to guarantee bandwidth for periodic CFS runners/sleepers.

Another point... "guarantee bandwidth"... the bandwith is provided under certain conditions. If the conditions are not respected, the guarantee a dl reservation will provide is that the task will not put a utilization higher than the one requested, so yes, a dl reservation can and will enforce a lower utilization if the task does not respect the conditions. Also, if the reservation is ready, but no task is ready...

Quoted 5 lines

The example usecase is:

Consider DL server params 25ms / 50ms.

Consider CFS task with duty cycle of 25ms / 76ms (run 25ms sleep 51ms).

define duty... like, runtime 25, period 76? sleeps for 51 relative to a starting time or not?

there are some holes in your explanation, it is tricky to reply inline for these cases... I am continuing but....

Quoted 7 lines

run 25ms run 25ms
_______ _______
| | sleep 51 | | sleep 51
-|------|-------|---------|---------|-------|----------|--------|------> t
0 25 50 101 126 151 202 227
\ 0-lax / \ 0-lax /