sched/deadline: Avoid dl_server boosting with expired deadline

[RFC PATCH] sched/deadline: Avoid dl_server boosting with expired deadline

Posted by Gabriele Monaco 4 months ago

Recent changes to the deadline server leave it running when the system
is idle. If the system is idle for longer than the dl_server period and
the first scheduling occurs after a fair task wakes up, the algorithm
picks the server as the earliest deadline (in the past) and that boosts
the fair task that just woke up while:
 * the deadline is in the past
 * the server consumed all its runtime (in background)
 * there is no starvation (idle for about a period)

Prevent the server from boosting a task when the deadline is in the
past. Instead, replenish a new period and start the server as deferred.

Fixes: 4ae8d9aa9f9d ("sched/deadline: Fix dl_server getting stuck")
To: Juri Lelli <juri.lelli@redhat.com>
Cc: Clark Williams <williams@redhat.com>
Signed-off-by: Gabriele Monaco <gmonaco@redhat.com>
---

This behaviour was observed using the RV monitors in [1] and the patch
was validated on an adapted version of the models. The models are not
exhaustively validating the dl_server behaviour.

[1] - https://lore.kernel.org/lkml/20250919140954.104920-21-gmonaco@redhat.com

 kernel/sched/deadline.c | 11 +++++++++++
 1 file changed, 11 insertions(+)

diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
index 72c1f72463c7..b3e3d506a18d 100644
--- a/kernel/sched/deadline.c
+++ b/kernel/sched/deadline.c
@@ -2371,6 +2371,17 @@ static struct task_struct *__pick_task_dl(struct rq *rq)
 			dl_server_stop(dl_se);
 			goto again;
 		}
+		/*
+		 * If the CPU was idle for long enough time and wakes up
+		 * because of a fair task, the dl_server may run after its
+		 * period elapsed. Replenish a new period as deferred, since we
+		 * are clearly not handling starvation here.
+		 */
+		if (dl_time_before(dl_se->deadline, rq_clock(rq))) {
+			dl_se->dl_defer_running = 0;
+			replenish_dl_new_period(dl_se, rq);
+			goto again;
+		}
 		rq->dl_server = dl_se;
 	} else {
 		p = dl_task_of(dl_se);

base-commit: e5f0a698b34ed76002dc5cff3804a61c80233a7a
-- 
2.51.0

Re: [RFC PATCH] sched/deadline: Avoid dl_server boosting with expired deadline

Posted by Peter Zijlstra 3 months, 3 weeks ago

On Tue, Oct 07, 2025 at 02:29:04PM +0200, Gabriele Monaco wrote:
> Recent changes to the deadline server leave it running when the system
> is idle. If the system is idle for longer than the dl_server period and
> the first scheduling occurs after a fair task wakes up, the algorithm
> picks the server as the earliest deadline (in the past) and that boosts
> the fair task that just woke up while:
>  * the deadline is in the past
>  * the server consumed all its runtime (in background)
>  * there is no starvation (idle for about a period)
> 
> Prevent the server from boosting a task when the deadline is in the
> past. Instead, replenish a new period and start the server as deferred.
> 
> Fixes: 4ae8d9aa9f9d ("sched/deadline: Fix dl_server getting stuck")
> To: Juri Lelli <juri.lelli@redhat.com>
> Cc: Clark Williams <williams@redhat.com>
> Signed-off-by: Gabriele Monaco <gmonaco@redhat.com>
> ---
> 
> This behaviour was observed using the RV monitors in [1] and the patch
> was validated on an adapted version of the models. The models are not
> exhaustively validating the dl_server behaviour.
> 
> [1] - https://lore.kernel.org/lkml/20250919140954.104920-21-gmonaco@redhat.com
> 
>  kernel/sched/deadline.c | 11 +++++++++++
>  1 file changed, 11 insertions(+)
> 
> diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
> index 72c1f72463c7..b3e3d506a18d 100644
> --- a/kernel/sched/deadline.c
> +++ b/kernel/sched/deadline.c
> @@ -2371,6 +2371,17 @@ static struct task_struct *__pick_task_dl(struct rq *rq)
>  			dl_server_stop(dl_se);
>  			goto again;
>  		}
> +		/*
> +		 * If the CPU was idle for long enough time and wakes up
> +		 * because of a fair task, the dl_server may run after its
> +		 * period elapsed. Replenish a new period as deferred, since we
> +		 * are clearly not handling starvation here.
> +		 */
> +		if (dl_time_before(dl_se->deadline, rq_clock(rq))) {
> +			dl_se->dl_defer_running = 0;
> +			replenish_dl_new_period(dl_se, rq);
> +			goto again;
> +		}
>  		rq->dl_server = dl_se;
>  	} else {
>  		p = dl_task_of(dl_se);
> 

I'm a bit confused, should not enqueue ensure deadline is in the future?
And if it doesn't shouldn't we fix the enqueue path somewhere?

Re: [RFC PATCH] sched/deadline: Avoid dl_server boosting with expired deadline

Posted by Gabriele Monaco 3 months, 3 weeks ago

On Tue, 2025-10-14 at 11:54 +0200, Peter Zijlstra wrote:
> On Tue, Oct 07, 2025 at 02:29:04PM +0200, Gabriele Monaco wrote:
> > Recent changes to the deadline server leave it running when the system
> > is idle. If the system is idle for longer than the dl_server period and
> > the first scheduling occurs after a fair task wakes up, the algorithm
> > picks the server as the earliest deadline (in the past) and that boosts
> > the fair task that just woke up while:
> >  * the deadline is in the past
> >  * the server consumed all its runtime (in background)
> >  * there is no starvation (idle for about a period)
> > 
> > Prevent the server from boosting a task when the deadline is in the
> > past. Instead, replenish a new period and start the server as deferred.
> 
> I'm a bit confused, should not enqueue ensure deadline is in the future?
> And if it doesn't shouldn't we fix the enqueue path somewhere?

Enqueue of a deadline task should handle the case, here the CPU is idle and the
deadline server did not stop yet (and won't until the next schedule, if I'm not
mistaken).
The following enqueue of a fair task triggers a schedule where the server (no
longer deferred) boosts the task straight away.

Now the only check for deadline is in pick_next_dl_entity, where the earliest
one is chosen, despite being in the past.

Do you mean to check for deadline when enqueueing the fair task too? I believe
again nothing happens here because the server is still up.

Does it make sense or am I missing something?

Re: [RFC PATCH] sched/deadline: Avoid dl_server boosting with expired deadline

Posted by Peter Zijlstra 3 months, 3 weeks ago

On Tue, Oct 14, 2025 at 12:05:06PM +0200, Gabriele Monaco wrote:
> On Tue, 2025-10-14 at 11:54 +0200, Peter Zijlstra wrote:
> > On Tue, Oct 07, 2025 at 02:29:04PM +0200, Gabriele Monaco wrote:
> > > Recent changes to the deadline server leave it running when the system
> > > is idle. If the system is idle for longer than the dl_server period and
> > > the first scheduling occurs after a fair task wakes up, the algorithm
> > > picks the server as the earliest deadline (in the past) and that boosts
> > > the fair task that just woke up while:
> > >  * the deadline is in the past
> > >  * the server consumed all its runtime (in background)
> > >  * there is no starvation (idle for about a period)
> > > 
> > > Prevent the server from boosting a task when the deadline is in the
> > > past. Instead, replenish a new period and start the server as deferred.
> > 
> > I'm a bit confused, should not enqueue ensure deadline is in the future?
> > And if it doesn't shouldn't we fix the enqueue path somewhere?
> 
> Enqueue of a deadline task should handle the case, here the CPU is idle and the
> deadline server did not stop yet (and won't until the next schedule, if I'm not
> mistaken).
> The following enqueue of a fair task triggers a schedule where the server (no
> longer deferred) boosts the task straight away.
> 
> Now the only check for deadline is in pick_next_dl_entity, where the earliest
> one is chosen, despite being in the past.
> 
> Do you mean to check for deadline when enqueueing the fair task too? I believe
> again nothing happens here because the server is still up.
> 
> Does it make sense or am I missing something?

Lets be confused together :-)

So dl_server is active, but machine is otherwise idle, this means
dl_server_timer is pending, right?

This timer is in one of two states:

 - waiting for replenish; which will trigger and switch to 0-laxity.
 - waiting for 0-laxity

So that 0-laxity case is the interesting one; when the machine really is
idle, no fair tasks will run and its runtime budget will not get
depleted. Therefore, once we hit 0-laxity, it will do
enqueue_dl_entity(dl_se, ENQUEUE_REPLENISH).

This enqueue should ensure dl_se->deadline is in the future, right?

Anyway, we run this deadline entity (there ain't nothing else to do
anyway), and it finds there aren't any fair tasks, it does
dl_server_stop().

Then, if a fair takes wakes (nr_running: 0->1) and dl_server isn't
active, we do dl_server_start(), which in turn does enqueue_dl_entity().
Now this enqueue is supposed to check if the dl_entity can still run;
does it still have time left in its current period, if not, its
replenish timer time.

So where exactly does the fair task start, and result in dl_se being
on_rq such that dl_deadline is in the past? That sounds like an enqueue
problem to me.

Re: [RFC PATCH] sched/deadline: Avoid dl_server boosting with expired deadline

Posted by Gabriele Monaco 3 months, 3 weeks ago

On Tue, 2025-10-07 at 14:29 +0200, Gabriele Monaco wrote:
> Recent changes to the deadline server leave it running when the system
> is idle. If the system is idle for longer than the dl_server period and
> the first scheduling occurs after a fair task wakes up, the algorithm
> picks the server as the earliest deadline (in the past) and that boosts
> the fair task that just woke up while:
>  * the deadline is in the past
>  * the server consumed all its runtime (in background)
>  * there is no starvation (idle for about a period)
> 
> Prevent the server from boosting a task when the deadline is in the
> past. Instead, replenish a new period and start the server as deferred.

Peter, Juri, what do you think about this change and "issue" with the server
boosting after idle?

Thanks,
Gabriele

> 
> Fixes: 4ae8d9aa9f9d ("sched/deadline: Fix dl_server getting stuck")
> To: Juri Lelli <juri.lelli@redhat.com>
> Cc: Clark Williams <williams@redhat.com>
> Signed-off-by: Gabriele Monaco <gmonaco@redhat.com>
> ---
> 
> This behaviour was observed using the RV monitors in [1] and the patch
> was validated on an adapted version of the models. The models are not
> exhaustively validating the dl_server behaviour.
> 
> [1] - https://lore.kernel.org/lkml/20250919140954.104920-21-gmonaco@redhat.com
> 
>  kernel/sched/deadline.c | 11 +++++++++++
>  1 file changed, 11 insertions(+)
> 
> diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
> index 72c1f72463c7..b3e3d506a18d 100644
> --- a/kernel/sched/deadline.c
> +++ b/kernel/sched/deadline.c
> @@ -2371,6 +2371,17 @@ static struct task_struct *__pick_task_dl(struct rq
> *rq)
>   dl_server_stop(dl_se);
>   goto again;
>   }
> + /*
> + * If the CPU was idle for long enough time and wakes up
> + * because of a fair task, the dl_server may run after its
> + * period elapsed. Replenish a new period as deferred, since we
> + * are clearly not handling starvation here.
> + */
> + if (dl_time_before(dl_se->deadline, rq_clock(rq))) {
> + dl_se->dl_defer_running = 0;
> + replenish_dl_new_period(dl_se, rq);
> + goto again;
> + }
>   rq->dl_server = dl_se;
>   } else {
>   p = dl_task_of(dl_se);
> 
> base-commit: e5f0a698b34ed76002dc5cff3804a61c80233a7a