Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > linux.kernel > #1586663 > unrolled thread
| Started by | Byungchul Park <byungchul.park@lge.com> |
|---|---|
| First post | 2017-02-23 07:20 +0100 |
| Last post | 2017-03-01 06:30 +0100 |
| Articles | 6 — 2 participants |
Back to article view | Back to linux.kernel
[PATCH v3] sched/deadline: Change the time to replenish runtime for sleep tasks Byungchul Park <byungchul.park@lge.com> - 2017-02-23 07:20 +0100
Re: [PATCH v3] sched/deadline: Change the time to replenish runtime for sleep tasks Byungchul Park <byungchul.park@lge.com> - 2017-02-23 11:20 +0100
Re: [PATCH v3] sched/deadline: Change the time to replenish runtime for sleep tasks Juri Lelli <juri.lelli@arm.com> - 2017-02-28 12:40 +0100
Re: [PATCH v3] sched/deadline: Change the time to replenish runtime for sleep tasks Byungchul Park <byungchul.park@lge.com> - 2017-02-28 14:20 +0100
Re: [PATCH v3] sched/deadline: Change the time to replenish runtime for sleep tasks Juri Lelli <juri.lelli@arm.com> - 2017-02-28 18:50 +0100
Re: [PATCH v3] sched/deadline: Change the time to replenish runtime for sleep tasks Byungchul Park <byungchul.park@lge.com> - 2017-03-01 06:30 +0100
| From | Byungchul Park <byungchul.park@lge.com> |
|---|---|
| Date | 2017-02-23 07:20 +0100 |
| Subject | [PATCH v3] sched/deadline: Change the time to replenish runtime for sleep tasks |
| Message-ID | <tdUUW-5HO-9@gated-at.bofh.it> |
Let's consider the following example.
timeline : o...................o.........o.......o..o
^ ^ ^ ^ ^
| | | | |
start | | | |
original runtime | | |
sleep with (-)runtime | |
original deadline |
wake up
When this task is woken up, a negative runtime should be considered,
which means that the task should get penalized when assigning runtime,
becasue it already spent more than expected. Current code handles this
by replenishing a runtime in hrtimer callback for deadline. But this
approach has room for improvement:
It will be replenished twice unnecessarily if the task sleeps for
long time so that the deadline, assigned in the hrtimer callback,
also passed. In other words, one happens in the callback and the
other happens in update_dl_entiry() when waking it up.
So force to replenish it for sleep tasks when waking it up.
Signed-off-by: Byungchul Park <byungchul.park@lge.com>
---
kernel/sched/deadline.c | 13 ++++++-------
1 file changed, 6 insertions(+), 7 deletions(-)
diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
index 27737f3..cb43ce9 100644
--- a/kernel/sched/deadline.c
+++ b/kernel/sched/deadline.c
@@ -498,8 +498,9 @@ static void update_dl_entity(struct sched_dl_entity *dl_se,
struct dl_rq *dl_rq = dl_rq_of_se(dl_se);
struct rq *rq = rq_of_dl_rq(dl_rq);
- if (dl_time_before(dl_se->deadline, rq_clock(rq)) ||
- dl_entity_overflow(dl_se, pi_se, rq_clock(rq))) {
+ if (dl_time_before(dl_se->deadline, rq_clock(rq)))
+ replenish_dl_entity(dl_se, pi_se);
+ else if (dl_entity_overflow(dl_se, pi_se, rq_clock(rq))) {
dl_se->deadline = rq_clock(rq) + pi_se->dl_deadline;
dl_se->runtime = pi_se->dl_runtime;
}
@@ -621,13 +622,11 @@ static enum hrtimer_restart dl_task_timer(struct hrtimer *timer)
* __dequeue_task_dl()
* prev->on_rq = 0;
*
- * We can be both throttled and !queued. Replenish the counter
- * but do not enqueue -- wait for our wakeup to do that.
+ * We can be both throttled and !queued. Wait for our wakeup to
+ * replenish runtime and enqueue p.
*/
- 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
[toc] | [next] | [standalone]
| From | Byungchul Park <byungchul.park@lge.com> |
|---|---|
| Date | 2017-02-23 11:20 +0100 |
| Subject | Re: [PATCH v3] sched/deadline: Change the time to replenish runtime for sleep tasks |
| Message-ID | <tdYFb-8jU-3@gated-at.bofh.it> |
| In reply to | #1586663 |
On Thu, Feb 23, 2017 at 03:14:59PM +0900, Byungchul Park wrote:
> Let's consider the following example.
>
> timeline : o...................o.........o.......o..o
> ^ ^ ^ ^ ^
> | | | | |
> start | | | |
> original runtime | | |
> sleep with (-)runtime | |
> original deadline |
> wake up
>
> When this task is woken up, a negative runtime should be considered,
> which means that the task should get penalized when assigning runtime,
> becasue it already spent more than expected. Current code handles this
> by replenishing a runtime in hrtimer callback for deadline. But this
> approach has room for improvement:
>
> It will be replenished twice unnecessarily if the task sleeps for
> long time so that the deadline, assigned in the hrtimer callback,
> also passed. In other words, one happens in the callback and the
> other happens in update_dl_entiry() when waking it up.
>
> So force to replenish it for sleep tasks when waking it up.
To be honest, I think this patch is more valuable when used with
removing unnecessary hrtimer interrupt for deadline control, but
not that much without it.
I just wonder what you think.
>
> Signed-off-by: Byungchul Park <byungchul.park@lge.com>
> ---
> kernel/sched/deadline.c | 13 ++++++-------
> 1 file changed, 6 insertions(+), 7 deletions(-)
>
> diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
> index 27737f3..cb43ce9 100644
> --- a/kernel/sched/deadline.c
> +++ b/kernel/sched/deadline.c
> @@ -498,8 +498,9 @@ static void update_dl_entity(struct sched_dl_entity *dl_se,
> struct dl_rq *dl_rq = dl_rq_of_se(dl_se);
> struct rq *rq = rq_of_dl_rq(dl_rq);
>
> - if (dl_time_before(dl_se->deadline, rq_clock(rq)) ||
> - dl_entity_overflow(dl_se, pi_se, rq_clock(rq))) {
> + if (dl_time_before(dl_se->deadline, rq_clock(rq)))
> + replenish_dl_entity(dl_se, pi_se);
> + else if (dl_entity_overflow(dl_se, pi_se, rq_clock(rq))) {
> dl_se->deadline = rq_clock(rq) + pi_se->dl_deadline;
> dl_se->runtime = pi_se->dl_runtime;
> }
> @@ -621,13 +622,11 @@ static enum hrtimer_restart dl_task_timer(struct hrtimer *timer)
> * __dequeue_task_dl()
> * prev->on_rq = 0;
> *
> - * We can be both throttled and !queued. Replenish the counter
> - * but do not enqueue -- wait for our wakeup to do that.
> + * We can be both throttled and !queued. Wait for our wakeup to
> + * replenish runtime and enqueue p.
> */
> - 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
[toc] | [prev] | [next] | [standalone]
| From | Juri Lelli <juri.lelli@arm.com> |
|---|---|
| Date | 2017-02-28 12:40 +0100 |
| Subject | Re: [PATCH v3] sched/deadline: Change the time to replenish runtime for sleep tasks |
| Message-ID | <tfOil-3OY-3@gated-at.bofh.it> |
| In reply to | #1586663 |
Hi,
On 23/02/17 15:14, Byungchul Park wrote:
> Let's consider the following example.
>
> timeline : o...................o.........o.......o..o
> ^ ^ ^ ^ ^
> | | | | |
> start | | | |
> original runtime | | |
> sleep with (-)runtime | |
> original deadline |
> wake up
>
> When this task is woken up, a negative runtime should be considered,
> which means that the task should get penalized when assigning runtime,
> becasue it already spent more than expected. Current code handles this
> by replenishing a runtime in hrtimer callback for deadline. But this
> approach has room for improvement:
>
> It will be replenished twice unnecessarily if the task sleeps for
> long time so that the deadline, assigned in the hrtimer callback,
> also passed. In other words, one happens in the callback and the
> other happens in update_dl_entiry() when waking it up.
>
> So force to replenish it for sleep tasks when waking it up.
>
> Signed-off-by: Byungchul Park <byungchul.park@lge.com>
> ---
> kernel/sched/deadline.c | 13 ++++++-------
> 1 file changed, 6 insertions(+), 7 deletions(-)
>
> diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
> index 27737f3..cb43ce9 100644
> --- a/kernel/sched/deadline.c
> +++ b/kernel/sched/deadline.c
> @@ -498,8 +498,9 @@ static void update_dl_entity(struct sched_dl_entity *dl_se,
> struct dl_rq *dl_rq = dl_rq_of_se(dl_se);
> struct rq *rq = rq_of_dl_rq(dl_rq);
>
> - if (dl_time_before(dl_se->deadline, rq_clock(rq)) ||
> - dl_entity_overflow(dl_se, pi_se, rq_clock(rq))) {
> + if (dl_time_before(dl_se->deadline, rq_clock(rq)))
> + replenish_dl_entity(dl_se, pi_se);
> + else if (dl_entity_overflow(dl_se, pi_se, rq_clock(rq))) {
> dl_se->deadline = rq_clock(rq) + pi_se->dl_deadline;
> dl_se->runtime = pi_se->dl_runtime;
> }
> @@ -621,13 +622,11 @@ static enum hrtimer_restart dl_task_timer(struct hrtimer *timer)
> * __dequeue_task_dl()
> * prev->on_rq = 0;
> *
> - * We can be both throttled and !queued. Replenish the counter
> - * but do not enqueue -- wait for our wakeup to do that.
> + * We can be both throttled and !queued. Wait for our wakeup to
> + * replenish runtime and enqueue p.
> */
> - if (!task_on_rq_queued(p)) {
> - replenish_dl_entity(dl_se, dl_se);
Hasn't this patch the same problem we discussed a couple of weeks ago?
https://marc.info/?l=linux-kernel&m=148699950802995
Thanks,
- Juri
[toc] | [prev] | [next] | [standalone]
| From | Byungchul Park <byungchul.park@lge.com> |
|---|---|
| Date | 2017-02-28 14:20 +0100 |
| Subject | Re: [PATCH v3] sched/deadline: Change the time to replenish runtime for sleep tasks |
| Message-ID | <tfPR9-4Up-43@gated-at.bofh.it> |
| In reply to | #1589373 |
On Tue, Feb 28, 2017 at 11:35:15AM +0000, Juri Lelli wrote:
> Hi,
>
> On 23/02/17 15:14, Byungchul Park wrote:
> > Let's consider the following example.
> >
> > timeline : o...................o.........o.......o..o
> > ^ ^ ^ ^ ^
> > | | | | |
> > start | | | |
> > original runtime | | |
> > sleep with (-)runtime | |
> > original deadline |
> > wake up
> >
> > When this task is woken up, a negative runtime should be considered,
> > which means that the task should get penalized when assigning runtime,
> > becasue it already spent more than expected. Current code handles this
> > by replenishing a runtime in hrtimer callback for deadline. But this
> > approach has room for improvement:
> >
> > It will be replenished twice unnecessarily if the task sleeps for
> > long time so that the deadline, assigned in the hrtimer callback,
> > also passed. In other words, one happens in the callback and the
> > other happens in update_dl_entiry() when waking it up.
> >
> > So force to replenish it for sleep tasks when waking it up.
> >
> > Signed-off-by: Byungchul Park <byungchul.park@lge.com>
> > ---
> > kernel/sched/deadline.c | 13 ++++++-------
> > 1 file changed, 6 insertions(+), 7 deletions(-)
> >
> > diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
> > index 27737f3..cb43ce9 100644
> > --- a/kernel/sched/deadline.c
> > +++ b/kernel/sched/deadline.c
> > @@ -498,8 +498,9 @@ static void update_dl_entity(struct sched_dl_entity *dl_se,
> > struct dl_rq *dl_rq = dl_rq_of_se(dl_se);
> > struct rq *rq = rq_of_dl_rq(dl_rq);
> >
> > - if (dl_time_before(dl_se->deadline, rq_clock(rq)) ||
> > - dl_entity_overflow(dl_se, pi_se, rq_clock(rq))) {
> > + if (dl_time_before(dl_se->deadline, rq_clock(rq)))
> > + replenish_dl_entity(dl_se, pi_se);
> > + else if (dl_entity_overflow(dl_se, pi_se, rq_clock(rq))) {
> > dl_se->deadline = rq_clock(rq) + pi_se->dl_deadline;
> > dl_se->runtime = pi_se->dl_runtime;
> > }
> > @@ -621,13 +622,11 @@ static enum hrtimer_restart dl_task_timer(struct hrtimer *timer)
> > * __dequeue_task_dl()
> > * prev->on_rq = 0;
> > *
> > - * We can be both throttled and !queued. Replenish the counter
> > - * but do not enqueue -- wait for our wakeup to do that.
> > + * We can be both throttled and !queued. Wait for our wakeup to
> > + * replenish runtime and enqueue p.
> > */
> > - if (!task_on_rq_queued(p)) {
> > - replenish_dl_entity(dl_se, dl_se);
>
> Hasn't this patch the same problem we discussed a couple of weeks ago?
No. This patch solves the problem by calling replenish_dl_entity() when
a dl task is woken up.
The problem was that it cannot consider negative runtime if we replenish
the task when it's woken up. So I made replenish_dl_entity() called even
on wake-up path, instead of simple assignment.
IMHO, this patch avoids double-replenishing properly, but adds additional
condition on wake-up path to acheive it. To be honest, I don't think it's
worth as I expected.
Thank you,
Byungchul
>
> https://marc.info/?l=linux-kernel&m=148699950802995
>
> Thanks,
>
> - Juri
[toc] | [prev] | [next] | [standalone]
| From | Juri Lelli <juri.lelli@arm.com> |
|---|---|
| Date | 2017-02-28 18:50 +0100 |
| Subject | Re: [PATCH v3] sched/deadline: Change the time to replenish runtime for sleep tasks |
| Message-ID | <tfU4q-7JC-21@gated-at.bofh.it> |
| In reply to | #1589440 |
On 28/02/17 22:09, Byungchul Park wrote:
> On Tue, Feb 28, 2017 at 11:35:15AM +0000, Juri Lelli wrote:
> > Hi,
> >
> > On 23/02/17 15:14, Byungchul Park wrote:
> > > Let's consider the following example.
> > >
> > > timeline : o...................o.........o.......o..o
> > > ^ ^ ^ ^ ^
> > > | | | | |
> > > start | | | |
> > > original runtime | | |
> > > sleep with (-)runtime | |
> > > original deadline |
> > > wake up
> > >
> > > When this task is woken up, a negative runtime should be considered,
> > > which means that the task should get penalized when assigning runtime,
> > > becasue it already spent more than expected. Current code handles this
> > > by replenishing a runtime in hrtimer callback for deadline. But this
> > > approach has room for improvement:
> > >
> > > It will be replenished twice unnecessarily if the task sleeps for
> > > long time so that the deadline, assigned in the hrtimer callback,
> > > also passed. In other words, one happens in the callback and the
> > > other happens in update_dl_entiry() when waking it up.
> > >
> > > So force to replenish it for sleep tasks when waking it up.
> > >
> > > Signed-off-by: Byungchul Park <byungchul.park@lge.com>
> > > ---
> > > kernel/sched/deadline.c | 13 ++++++-------
> > > 1 file changed, 6 insertions(+), 7 deletions(-)
> > >
> > > diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
> > > index 27737f3..cb43ce9 100644
> > > --- a/kernel/sched/deadline.c
> > > +++ b/kernel/sched/deadline.c
> > > @@ -498,8 +498,9 @@ static void update_dl_entity(struct sched_dl_entity *dl_se,
> > > struct dl_rq *dl_rq = dl_rq_of_se(dl_se);
> > > struct rq *rq = rq_of_dl_rq(dl_rq);
> > >
> > > - if (dl_time_before(dl_se->deadline, rq_clock(rq)) ||
> > > - dl_entity_overflow(dl_se, pi_se, rq_clock(rq))) {
> > > + if (dl_time_before(dl_se->deadline, rq_clock(rq)))
> > > + replenish_dl_entity(dl_se, pi_se);
> > > + else if (dl_entity_overflow(dl_se, pi_se, rq_clock(rq))) {
> > > dl_se->deadline = rq_clock(rq) + pi_se->dl_deadline;
> > > dl_se->runtime = pi_se->dl_runtime;
> > > }
> > > @@ -621,13 +622,11 @@ static enum hrtimer_restart dl_task_timer(struct hrtimer *timer)
> > > * __dequeue_task_dl()
> > > * prev->on_rq = 0;
> > > *
> > > - * We can be both throttled and !queued. Replenish the counter
> > > - * but do not enqueue -- wait for our wakeup to do that.
> > > + * We can be both throttled and !queued. Wait for our wakeup to
> > > + * replenish runtime and enqueue p.
> > > */
> > > - if (!task_on_rq_queued(p)) {
> > > - replenish_dl_entity(dl_se, dl_se);
> >
> > Hasn't this patch the same problem we discussed a couple of weeks ago?
>
> No. This patch solves the problem by calling replenish_dl_entity() when
> a dl task is woken up.
>
So, if the task was throttled in the "going to sleep" path we set the
replenishment timer to fire at your "original deadline" instant of time
above. Now, 3 things can happen I guess:
- task wakes up before the replenishment timer ("original deadline")
-> it is throttled, so we do nothing
- task wakes up after the replenishment timer
-> we replenished it in the timer callback (which considers negative
runtime from previous execution)
+ deadline should be in the future
+ dl_entity shouldn't overflow
+ we don't touch its parameters, but we simply enqueue it back on dl_rq
- task wakes up even after the deadline it has got from previous
replenishment expired
-> we assign to him completely new parameters, but since he didn't
use the previous runtime at all, this should be fine I guess
What am I still missing? :)
> The problem was that it cannot consider negative runtime if we replenish
> the task when it's woken up. So I made replenish_dl_entity() called even
> on wake-up path, instead of simple assignment.
>
> IMHO, this patch avoids double-replenishing properly, but adds additional
> condition on wake-up path to acheive it. To be honest, I don't think it's
> worth as I expected.
>
> Thank you,
> Byungchul
>
> >
> > https://marc.info/?l=linux-kernel&m=148699950802995
> >
> > Thanks,
> >
> > - Juri
[toc] | [prev] | [next] | [standalone]
| From | Byungchul Park <byungchul.park@lge.com> |
|---|---|
| Date | 2017-03-01 06:30 +0100 |
| Subject | Re: [PATCH v3] sched/deadline: Change the time to replenish runtime for sleep tasks |
| Message-ID | <tg4ZQ-6FG-3@gated-at.bofh.it> |
| In reply to | #1589655 |
On Tue, Feb 28, 2017 at 05:47:53PM +0000, Juri Lelli wrote:
> > > > Let's consider the following example.
> > > >
> > > > timeline : o...................o.........o.......o..o
> > > > ^ ^ ^ ^ ^
> > > > | | | | |
> > > > start | | | |
> > > > original runtime | | |
> > > > sleep with (-)runtime | |
> > > > original deadline |
> > > > wake up
> > > >
> > > > When this task is woken up, a negative runtime should be considered,
> > > > which means that the task should get penalized when assigning runtime,
> > > > becasue it already spent more than expected. Current code handles this
> > > > by replenishing a runtime in hrtimer callback for deadline. But this
> > > > approach has room for improvement:
> > > >
> > > > It will be replenished twice unnecessarily if the task sleeps for
> > > > long time so that the deadline, assigned in the hrtimer callback,
> > > > also passed. In other words, one happens in the callback and the
> > > > other happens in update_dl_entiry() when waking it up.
> > > >
> > > > So force to replenish it for sleep tasks when waking it up.
> > > >
> > > > Signed-off-by: Byungchul Park <byungchul.park@lge.com>
> > > > ---
...
> So, if the task was throttled in the "going to sleep" path we set the
> replenishment timer to fire at your "original deadline" instant of time
Hi,
Precisely speaking, we set the timer if the task was throttled, no
matter whether it's in the 'going to sleep' path or not. IWO, the timer
is set even in the path. And I want to say it's unnecessary.
> above. Now, 3 things can happen I guess:
>
> - task wakes up before the replenishment timer ("original deadline")
> -> it is throttled, so we do nothing
>
> - task wakes up after the replenishment timer
> -> we replenished it in the timer callback (which considers negative
> runtime from previous execution)
> + deadline should be in the future
> + dl_entity shouldn't overflow
> + we don't touch its parameters, but we simply enqueue it back on dl_rq
>
> - task wakes up even after the deadline it has got from previous
> replenishment expired
> -> we assign to him completely new parameters, but since he didn't
> use the previous runtime at all, this should be fine I guess
Exactly same as what I thought. I agree that current code works properly.
However, the code has room for improvement because tasks being throttled
in 'going to sleep' path do not need to set additional timer.
To be honest, I also tried to remove setting timer in the case, but it
makes code a bit cluttered because I should handle the your first case
above, that means I should add a proper timer on the wake-up path if
necessary.
The try would be worthy if avoiding unnecessary timer is more important
than making code cluttered. But I did not include the try since I'm not
sure. What do you think about that? Which one is more important between
avoiding unnecessary timer and avoiding making code cluttered?
Thank you,
Byungchul
>
> What am I still missing? :)
>
> > The problem was that it cannot consider negative runtime if we replenish
> > the task when it's woken up. So I made replenish_dl_entity() called even
> > on wake-up path, instead of simple assignment.
> >
> > IMHO, this patch avoids double-replenishing properly, but adds additional
> > condition on wake-up path to acheive it. To be honest, I don't think it's
> > worth as I expected.
> >
> > Thank you,
> > Byungchul
> >
> > >
> > > https://marc.info/?l=linux-kernel&m=148699950802995
> > >
> > > Thanks,
> > >
> > > - Juri
[toc] | [prev] | [standalone]
Back to top | Article view | linux.kernel
csiph-web