[PATCH] sched/deadline: Remove redundant code replenishing runtime

[PATCH] sched/deadline: Remove redundant code replenishing runtime

[Byungchul Park]

For a task passing its deadline while !rq, it will be replenished
in the following path because dl_se->deadline < rq_lock.

   enqueue_dl_entity(ENQUEUE_WAKEUP)
      update_dl_entity

Therefore, code replenishing it in the timer callback in the case is
unnecessary. This is not for enhancing performance but just for removing
a redundant code.

Signed-off-by: Byungchul Park <byungchul.park@lge.com>
---
 kernel/sched/deadline.c | 4 +---
 1 file changed, 1 insertion(+), 3 deletions(-)

diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
index 27737f3..9c77696 100644
--- a/kernel/sched/deadline.c
+++ b/kernel/sched/deadline.c
@@ -624,10 +624,8 @@ static enum hrtimer_restart dl_task_timer(struct hrtimer *timer)
 	 * We can be both throttled and !queued. Replenish the counter
 	 * but do not enqueue -- wait for our wakeup to do that.
 	 */
-	if (!task_on_rq_queued(p)) {
-		replenish_dl_entity(dl_se, dl_se);
+	if (!task_on_rq_queued(p))
 		goto unlock;
-	}
 
 #ifdef CONFIG_SMP
 	if (unlikely(!rq->online)) {
-- 
1.9.1

Re: [PATCH] sched/deadline: Remove redundant code replenishing runtime

[Juri Lelli]

Hi,

On 10/02/17 18:11, Byungchul Park wrote:
> For a task passing its deadline while !rq, it will be replenished
> in the following path because dl_se->deadline < rq_lock.
> 
>    enqueue_dl_entity(ENQUEUE_WAKEUP)
>       update_dl_entity
> 
> Therefore, code replenishing it in the timer callback in the case is
> unnecessary. This is not for enhancing performance but just for removing
> a redundant code.
> 
> Signed-off-by: Byungchul Park <byungchul.park@lge.com>
> ---
>  kernel/sched/deadline.c | 4 +---
>  1 file changed, 1 insertion(+), 3 deletions(-)
> 
> diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
> index 27737f3..9c77696 100644
> --- a/kernel/sched/deadline.c
> +++ b/kernel/sched/deadline.c
> @@ -624,10 +624,8 @@ static enum hrtimer_restart dl_task_timer(struct hrtimer *timer)
>  	 * We can be both throttled and !queued. Replenish the counter
>  	 * but do not enqueue -- wait for our wakeup to do that.
>  	 */
> -	if (!task_on_rq_queued(p)) {
> -		replenish_dl_entity(dl_se, dl_se);

I think we actually want to replenish and set the next deadline at this
point of time, not the one that we get when the task will eventually wake up.

Best,

- Juri

Re: [PATCH] sched/deadline: Remove redundant code replenishing runtime

[Byungchul Park]

On Fri, Feb 10, 2017 at 01:39:33PM +0000, Juri Lelli wrote:
> Hi,
> 
> On 10/02/17 18:11, Byungchul Park wrote:
> > For a task passing its deadline while !rq, it will be replenished
> > in the following path because dl_se->deadline < rq_lock.
> > 
> >    enqueue_dl_entity(ENQUEUE_WAKEUP)
> >       update_dl_entity
> > 
> > Therefore, code replenishing it in the timer callback in the case is
> > unnecessary. This is not for enhancing performance but just for removing
> > a redundant code.
> > 
> > Signed-off-by: Byungchul Park <byungchul.park@lge.com>
> > ---
> >  kernel/sched/deadline.c | 4 +---
> >  1 file changed, 1 insertion(+), 3 deletions(-)
> > 
> > diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
> > index 27737f3..9c77696 100644
> > --- a/kernel/sched/deadline.c
> > +++ b/kernel/sched/deadline.c
> > @@ -624,10 +624,8 @@ static enum hrtimer_restart dl_task_timer(struct hrtimer *timer)
> >  	 * We can be both throttled and !queued. Replenish the counter
> >  	 * but do not enqueue -- wait for our wakeup to do that.
> >  	 */
> > -	if (!task_on_rq_queued(p)) {
> > -		replenish_dl_entity(dl_se, dl_se);
> 
> I think we actually want to replenish and set the next deadline at this
> point of time, not the one that we get when the task will eventually wake up.

Hello juri,

But I wonder if it's meaningful to set a next deadline for a 'sleeping
task', which, rather, could be worse because its bandwidth might be
distorted at the time it's woken up.

IMHO, it's neat to set its deadline and runtime when being woken up, in
the case already passed its deadline. Am I wrong?

Thank you,
Byungchul

Re: [PATCH] sched/deadline: Remove redundant code replenishing runtime

[Byungchul Park]

On Mon, Feb 13, 2017 at 11:30:09AM +0900, Byungchul Park wrote:
> On Fri, Feb 10, 2017 at 01:39:33PM +0000, Juri Lelli wrote:
> > Hi,
> > 
> > On 10/02/17 18:11, Byungchul Park wrote:
> > > For a task passing its deadline while !rq, it will be replenished
> > > in the following path because dl_se->deadline < rq_lock.
> > > 
> > >    enqueue_dl_entity(ENQUEUE_WAKEUP)
> > >       update_dl_entity
> > > 
> > > Therefore, code replenishing it in the timer callback in the case is
> > > unnecessary. This is not for enhancing performance but just for removing
> > > a redundant code.
> > > 
> > > Signed-off-by: Byungchul Park <byungchul.park@lge.com>
> > > ---
> > >  kernel/sched/deadline.c | 4 +---
> > >  1 file changed, 1 insertion(+), 3 deletions(-)
> > > 
> > > diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
> > > index 27737f3..9c77696 100644
> > > --- a/kernel/sched/deadline.c
> > > +++ b/kernel/sched/deadline.c
> > > @@ -624,10 +624,8 @@ static enum hrtimer_restart dl_task_timer(struct hrtimer *timer)
> > >  	 * We can be both throttled and !queued. Replenish the counter
> > >  	 * but do not enqueue -- wait for our wakeup to do that.
> > >  	 */
> > > -	if (!task_on_rq_queued(p)) {
> > > -		replenish_dl_entity(dl_se, dl_se);
> > 
> > I think we actually want to replenish and set the next deadline at this
> > point of time, not the one that we get when the task will eventually wake up.
> 
> Hello juri,
> 
> But I wonder if it's meaningful to set a next deadline for a 'sleeping
> task', which, rather, could be worse because its bandwidth might be
> distorted at the time it's woken up.
> 
> IMHO, it's neat to set its deadline and runtime when being woken up, in
> the case already passed its deadline. Am I wrong?

And I found that dl_entity_overflow() returns true and replenishes the
task unconditionally in update_dl_entity() again when the task is woken
up, because 'runtime / (deadline - t) > dl_runtime / dl_period' is true.

In other words, replenishing the sleeping task in timer callback is
totally unnecessary and redundant work.

> 
> Thank you,
> Byungchul

Re: [PATCH] sched/deadline: Remove redundant code replenishing runtime

[Juri Lelli]

[+Luca]

On 13/02/17 13:29, Byungchul Park wrote:
> On Mon, Feb 13, 2017 at 11:30:09AM +0900, Byungchul Park wrote:
> > On Fri, Feb 10, 2017 at 01:39:33PM +0000, Juri Lelli wrote:
> > > Hi,
> > > 
> > > On 10/02/17 18:11, Byungchul Park wrote:
> > > > For a task passing its deadline while !rq, it will be replenished
> > > > in the following path because dl_se->deadline < rq_lock.
> > > > 
> > > >    enqueue_dl_entity(ENQUEUE_WAKEUP)
> > > >       update_dl_entity
> > > > 
> > > > Therefore, code replenishing it in the timer callback in the case is
> > > > unnecessary. This is not for enhancing performance but just for removing
> > > > a redundant code.
> > > > 
> > > > Signed-off-by: Byungchul Park <byungchul.park@lge.com>
> > > > ---
> > > >  kernel/sched/deadline.c | 4 +---
> > > >  1 file changed, 1 insertion(+), 3 deletions(-)
> > > > 
> > > > diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
> > > > index 27737f3..9c77696 100644
> > > > --- a/kernel/sched/deadline.c
> > > > +++ b/kernel/sched/deadline.c
> > > > @@ -624,10 +624,8 @@ static enum hrtimer_restart dl_task_timer(struct hrtimer *timer)
> > > >  	 * We can be both throttled and !queued. Replenish the counter
> > > >  	 * but do not enqueue -- wait for our wakeup to do that.
> > > >  	 */
> > > > -	if (!task_on_rq_queued(p)) {
> > > > -		replenish_dl_entity(dl_se, dl_se);
> > > 
> > > I think we actually want to replenish and set the next deadline at this
> > > point of time, not the one that we get when the task will eventually wake up.
> > 
> > Hello juri,
> > 
> > But I wonder if it's meaningful to set a next deadline for a 'sleeping
> > task', which, rather, could be worse because its bandwidth might be
> > distorted at the time it's woken up.
> > 

What you mean by 'distorted'. AFAIU, we just want to replenish when
needed. The instant of time when the task will eventually wake up it is
something we cannot rely upon, and could introduce errors.

IIUC, your situation looks like the below

   oooo|-------------------vxxx^ooo
       |                   |   |
       |                   |   |
    sleep/throttle         |   |
                     r. timer  |
   		           wakeup

The task gets throttled while going to sleep, when the replenishment
timer fires you are proposing we do nothing and we actually replenishing
using the wakeup rq_clock() as reference. My worry is that, by doing so,
we make the task potentially loose some of its bandwidth, as we will
have lost some time (the 3 x-es in the diagram above) when calculating
its next dynamic deadline. 

> > IMHO, it's neat to set its deadline and runtime when being woken up, in
> > the case already passed its deadline. Am I wrong?
> 
> And I found that dl_entity_overflow() returns true and replenishes the
> task unconditionally in update_dl_entity() again when the task is woken
> up, because 'runtime / (deadline - t) > dl_runtime / dl_period' is true.
> 

Why 'unconditionally'? It will postpone and replenish if the task is
going to overflow, if not, it will keep its runtime and deadline we set
when the replenishment timer fired.

Re: [PATCH] sched/deadline: Remove redundant code replenishing runtime

[Byungchul Park]

On Mon, Feb 13, 2017 at 03:24:55PM +0000, Juri Lelli wrote:
> > > > I think we actually want to replenish and set the next deadline at this
> > > > point of time, not the one that we get when the task will eventually wake up.
> > > 
> > > Hello juri,
> > > 
> > > But I wonder if it's meaningful to set a next deadline for a 'sleeping
> > > task', which, rather, could be worse because its bandwidth might be
> > > distorted at the time it's woken up.
> > > 
> 
> What you mean by 'distorted'. AFAIU, we just want to replenish when
> needed. The instant of time when the task will eventually wake up it is
> something we cannot rely upon, and could introduce errors.
> 
> IIUC, your situation looks like the below

Exactly.

> 
>    oooo|-------------------vxxx^ooo
>        |                   |   |
>        |                   |   |
>     sleep/throttle         |   |
>                      r. timer  |
>    		           wakeup

Sorry for bothering you..

> The task gets throttled while going to sleep, when the replenishment
> timer fires you are proposing we do nothing and we actually replenishing
> using the wakeup rq_clock() as reference. My worry is that, by doing so,
> we make the task potentially loose some of its bandwidth, as we will
> have lost some time (the 3 x-es in the diagram above) when calculating
> its next dynamic deadline.

I meant, when we decide whether it's overflowed in dl_entiry_overflow(),
'right' might be smaller than 'left' because 't' is the time the 3 x-es
already passed.

Of course, here I assumed that runtime ~= 0 and deadline ~= rq_clock
when it was throttled, if scheduler works nicely.

> > > IMHO, it's neat to set its deadline and runtime when being woken up, in
> > > the case already passed its deadline. Am I wrong?
> > 
> > And I found that dl_entity_overflow() returns true and replenishes the
> > task unconditionally in update_dl_entity() again when the task is woken
> > up, because 'runtime / (deadline - t) > dl_runtime / dl_period' is true.
> > 
> 
> Why 'unconditionally'? It will postpone and replenish if the task is

Not exactly 'unconditially' if my assumption is broken. Sorry for
choosing a word that is not careful.

> going to overflow, if not, it will keep its runtime and deadline we set

I meant the task will be almost always considered 'overflow', as I
explained above. So it will be overwritten again when waking up the task
than keep what we set in timer callback.

> when the replenishment timer fired.

Re: [PATCH] sched/deadline: Remove redundant code replenishing runtime

[Byungchul Park]

On Tue, Feb 14, 2017 at 08:42:43AM +0900, Byungchul Park wrote:
> On Mon, Feb 13, 2017 at 03:24:55PM +0000, Juri Lelli wrote:
> > > > > I think we actually want to replenish and set the next deadline at this
> > > > > point of time, not the one that we get when the task will eventually wake up.
> > > > 
> > > > Hello juri,
> > > > 
> > > > But I wonder if it's meaningful to set a next deadline for a 'sleeping
> > > > task', which, rather, could be worse because its bandwidth might be
> > > > distorted at the time it's woken up.
> > > > 
> > 
> > What you mean by 'distorted'. AFAIU, we just want to replenish when
> > needed. The instant of time when the task will eventually wake up it is
> > something we cannot rely upon, and could introduce errors.
> > 
> > IIUC, your situation looks like the below
> 
> Exactly.
> 
> > 
> >    oooo|-------------------vxxx^ooo
> >        |                   |   |
> >        |                   |   |
> >     sleep/throttle         |   |
> >                      r. timer  |
> >    		           wakeup
> 
> Sorry for bothering you..
> 
> > The task gets throttled while going to sleep, when the replenishment
> > timer fires you are proposing we do nothing and we actually replenishing
> > using the wakeup rq_clock() as reference. My worry is that, by doing so,
> > we make the task potentially loose some of its bandwidth, as we will
> > have lost some time (the 3 x-es in the diagram above) when calculating
> > its next dynamic deadline.
> 
> I meant, when we decide whether it's overflowed in dl_entiry_overflow(),
> 'right' might be smaller than 'left' because 't' is the time the 3 x-es
> already passed.
> 
> Of course, here I assumed that runtime ~= 0 and deadline ~= rq_clock
> when it was throttled, if scheduler works nicely.
> 
> > > > IMHO, it's neat to set its deadline and runtime when being woken up, in
> > > > the case already passed its deadline. Am I wrong?
> > > 
> > > And I found that dl_entity_overflow() returns true and replenishes the
> > > task unconditionally in update_dl_entity() again when the task is woken
> > > up, because 'runtime / (deadline - t) > dl_runtime / dl_period' is true.
> > > 
> > 
> > Why 'unconditionally'? It will postpone and replenish if the task is
> 
> Not exactly 'unconditially' if my assumption is broken. Sorry for
> choosing a word that is not careful.
> 
> > going to overflow, if not, it will keep its runtime and deadline we set
> 
> I meant the task will be almost always considered 'overflow', as I
> explained above. So it will be overwritten again when waking up the task
> than keep what we set in timer callback.

I don't want to argue strongly, keeping current code unchanged is ok.
I just wanted to say it will be replenished twice in most cases if:

   1. The task was throttled and passed its deadline while sleeping.

Of course, it also depends on how much negative runtime it had when
throttled. Sorry for bothering you and thanks for explaining it.

Re: [PATCH] sched/deadline: Remove redundant code replenishing runtime

[Juri Lelli]

On 14/02/17 11:06, Byungchul Park wrote:
> On Tue, Feb 14, 2017 at 08:42:43AM +0900, Byungchul Park wrote:
> > On Mon, Feb 13, 2017 at 03:24:55PM +0000, Juri Lelli wrote:
> > > > > > I think we actually want to replenish and set the next deadline at this
> > > > > > point of time, not the one that we get when the task will eventually wake up.
> > > > > 
> > > > > Hello juri,
> > > > > 
> > > > > But I wonder if it's meaningful to set a next deadline for a 'sleeping
> > > > > task', which, rather, could be worse because its bandwidth might be
> > > > > distorted at the time it's woken up.
> > > > > 
> > > 
> > > What you mean by 'distorted'. AFAIU, we just want to replenish when
> > > needed. The instant of time when the task will eventually wake up it is
> > > something we cannot rely upon, and could introduce errors.
> > > 
> > > IIUC, your situation looks like the below
> > 
> > Exactly.
> > 
> > > 
> > >    oooo|-------------------vxxx^ooo
> > >        |                   |   |
> > >        |                   |   |
> > >     sleep/throttle         |   |
> > >                      r. timer  |
> > >    		           wakeup
> > 
> > Sorry for bothering you..
> > 
> > > The task gets throttled while going to sleep, when the replenishment
> > > timer fires you are proposing we do nothing and we actually replenishing
> > > using the wakeup rq_clock() as reference. My worry is that, by doing so,
> > > we make the task potentially loose some of its bandwidth, as we will
> > > have lost some time (the 3 x-es in the diagram above) when calculating
> > > its next dynamic deadline.
> > 
> > I meant, when we decide whether it's overflowed in dl_entiry_overflow(),
> > 'right' might be smaller than 'left' because 't' is the time the 3 x-es
> > already passed.
> > 
> > Of course, here I assumed that runtime ~= 0 and deadline ~= rq_clock
> > when it was throttled, if scheduler works nicely.
> > 
> > > > > IMHO, it's neat to set its deadline and runtime when being woken up, in
> > > > > the case already passed its deadline. Am I wrong?
> > > > 
> > > > And I found that dl_entity_overflow() returns true and replenishes the
> > > > task unconditionally in update_dl_entity() again when the task is woken
> > > > up, because 'runtime / (deadline - t) > dl_runtime / dl_period' is true.
> > > > 
> > > 
> > > Why 'unconditionally'? It will postpone and replenish if the task is
> > 
> > Not exactly 'unconditially' if my assumption is broken. Sorry for
> > choosing a word that is not careful.
> > 
> > > going to overflow, if not, it will keep its runtime and deadline we set
> > 
> > I meant the task will be almost always considered 'overflow', as I
> > explained above. So it will be overwritten again when waking up the task
> > than keep what we set in timer callback.
> 
> I don't want to argue strongly, keeping current code unchanged is ok.
> I just wanted to say it will be replenished twice in most cases if:
> 
>    1. The task was throttled and passed its deadline while sleeping.
> 
> Of course, it also depends on how much negative runtime it had when
> throttled. Sorry for bothering you and thanks for explaining it.

No bothering at all! Thanks for raising a potential problem, but I guess
we need to be correct 100% of the times, without trying to optimize for
the most common case.

Best,

- Juri