[PATCH] sched: remove starvation in check_preempt_equal_prio()

[PATCH] sched: remove starvation in check_preempt_equal_prio()

[Hillf Danton]

If there are pushable tasks and they are high enough in priority, in which
case task p is covered, the current could keep holding its CPU.

Even if current task has to release its CPU, requeuing task p could result in
starvation of tasks that are of same priority and have been waiting on RQ for
a couple of hours:/

Signed-off-by: Hillf Danton <dhillf@gmail.com>
---

--- tip-git/kernel/sched_rt.c	Sun May 22 20:12:01 2011
+++ sched_rt.c	Tue May 24 21:01:51 2011
@@ -1028,24 +1028,23 @@ select_task_rq_rt(struct task_struct *p,
 	return cpu;
 }

+static struct task_struct *pick_next_pushable_task(struct rq *);
+
 static void check_preempt_equal_prio(struct rq *rq, struct task_struct *p)
 {
-	if (rq->curr->rt.nr_cpus_allowed == 1)
-		return;
-
-	if (p->rt.nr_cpus_allowed != 1
-	    && cpupri_find(&rq->rd->cpupri, p, NULL))
+	if (rq->curr->rt.nr_cpus_allowed > 1) {
+		struct task_struct *push = pick_next_pushable_task(rq);
+		/*
+		 * Though curr is pushable, if there are other pushable tasks,
+		 * we keep curr busy.
+		 */
+		if (push && !(push->prio > p->prio))
+			return;
+	} else
 		return;

-	if (!cpupri_find(&rq->rd->cpupri, rq->curr, NULL))
-		return;
-
-	/*
-	 * There appears to be other cpus that can accept
-	 * current and none to run 'p', so lets reschedule
-	 * to try and push current away:
-	 */
-	requeue_task_rt(rq, p, 1);
+	/* yield curr */
+	requeue_task_rt(rq, rq->curr, 0);
 	resched_task(rq->curr);
 }

@@ -1091,7 +1090,7 @@ static struct sched_rt_entity *pick_next
 	BUG_ON(idx >= MAX_RT_PRIO);

 	queue = array->queue + idx;
-	next = list_entry(queue->next, struct sched_rt_entity, run_list);
+	next = list_first_entry(queue, struct sched_rt_entity, run_list);

 	return next;
 }

Re: [PATCH] sched: remove starvation in check_preempt_equal_prio()

[Steven Rostedt]

On Tue, 2011-05-24 at 21:34 +0800, Hillf Danton wrote:
> If there are pushable tasks and they are high enough in priority, in which
> case task p is covered, the current could keep holding its CPU.
> 
> Even if current task has to release its CPU, requeuing task p could result in
> starvation of tasks that are of same priority and have been waiting on RQ for
> a couple of hours:/

Can you explain this better? Sounds like you are describing the
definition of FIFO. You are *not* suppose to preempt a FIFO task just
because another task of equal priority woke up on its run queue.

Yes, if you queue two FIFO tasks of the same priority on the same run
queue, and one runs for hours without calling schedule. The other one
will have to wait.

-- Steve


> 
> Signed-off-by: Hillf Danton <dhillf@gmail.com>
> ---
> 
> --- tip-git/kernel/sched_rt.c	Sun May 22 20:12:01 2011
> +++ sched_rt.c	Tue May 24 21:01:51 2011
> @@ -1028,24 +1028,23 @@ select_task_rq_rt(struct task_struct *p,
>  	return cpu;
>  }
> 
> +static struct task_struct *pick_next_pushable_task(struct rq *);
> +
>  static void check_preempt_equal_prio(struct rq *rq, struct task_struct *p)
>  {
> -	if (rq->curr->rt.nr_cpus_allowed == 1)
> -		return;
> -
> -	if (p->rt.nr_cpus_allowed != 1
> -	    && cpupri_find(&rq->rd->cpupri, p, NULL))
> +	if (rq->curr->rt.nr_cpus_allowed > 1) {
> +		struct task_struct *push = pick_next_pushable_task(rq);
> +		/*
> +		 * Though curr is pushable, if there are other pushable tasks,
> +		 * we keep curr busy.
> +		 */
> +		if (push && !(push->prio > p->prio))
> +			return;
> +	} else
>  		return;
> 
> -	if (!cpupri_find(&rq->rd->cpupri, rq->curr, NULL))
> -		return;
> -
> -	/*
> -	 * There appears to be other cpus that can accept
> -	 * current and none to run 'p', so lets reschedule
> -	 * to try and push current away:
> -	 */
> -	requeue_task_rt(rq, p, 1);
> +	/* yield curr */
> +	requeue_task_rt(rq, rq->curr, 0);
>  	resched_task(rq->curr);
>  }
> 
> @@ -1091,7 +1090,7 @@ static struct sched_rt_entity *pick_next
>  	BUG_ON(idx >= MAX_RT_PRIO);
> 
>  	queue = array->queue + idx;
> -	next = list_entry(queue->next, struct sched_rt_entity, run_list);
> +	next = list_first_entry(queue, struct sched_rt_entity, run_list);
> 
>  	return next;
>  }

Re: [PATCH] sched: remove starvation in check_preempt_equal_prio()

[Hillf Danton]

On Tue, May 24, 2011 at 9:45 PM, Steven Rostedt <rostedt@goodmis.org> wrote:
> On Tue, 2011-05-24 at 21:34 +0800, Hillf Danton wrote:
>> If there are pushable tasks and they are high enough in priority, in which
>> case task p is covered, the current could keep holding its CPU.
>>
>> Even if current task has to release its CPU, requeuing task p could result in
>> starvation of tasks that are of same priority and have been waiting on RQ for
>> a couple of hours:/
>
> Can you explain this better? Sounds like you are describing the
> definition of FIFO. You are *not* suppose to preempt a FIFO task just

I dont want to redefine FIFO, but starvation needs attention, since
the woken task is already off RQ, and its position on RQ is reshuffled.

thanks
          Hillf
> because another task of equal priority woke up on its run queue.
>
> Yes, if you queue two FIFO tasks of the same priority on the same run
> queue, and one runs for hours without calling schedule. The other one
> will have to wait.
>
> -- Steve
>
>
>>
>> Signed-off-by: Hillf Danton <dhillf@gmail.com>
>> ---
>>
>> --- tip-git/kernel/sched_rt.c Sun May 22 20:12:01 2011
>> +++ sched_rt.c        Tue May 24 21:01:51 2011
>> @@ -1028,24 +1028,23 @@ select_task_rq_rt(struct task_struct *p,
>>       return cpu;
>>  }
>>
>> +static struct task_struct *pick_next_pushable_task(struct rq *);
>> +
>>  static void check_preempt_equal_prio(struct rq *rq, struct task_struct *p)
>>  {
>> -     if (rq->curr->rt.nr_cpus_allowed == 1)
>> -             return;
>> -
>> -     if (p->rt.nr_cpus_allowed != 1
>> -         && cpupri_find(&rq->rd->cpupri, p, NULL))
>> +     if (rq->curr->rt.nr_cpus_allowed > 1) {
>> +             struct task_struct *push = pick_next_pushable_task(rq);
>> +             /*
>> +              * Though curr is pushable, if there are other pushable tasks,
>> +              * we keep curr busy.
>> +              */
>> +             if (push && !(push->prio > p->prio))
>> +                     return;
>> +     } else
>>               return;
>>
>> -     if (!cpupri_find(&rq->rd->cpupri, rq->curr, NULL))
>> -             return;
>> -
>> -     /*
>> -      * There appears to be other cpus that can accept
>> -      * current and none to run 'p', so lets reschedule
>> -      * to try and push current away:
>> -      */
>> -     requeue_task_rt(rq, p, 1);
>> +     /* yield curr */
>> +     requeue_task_rt(rq, rq->curr, 0);
>>       resched_task(rq->curr);
>>  }
>>
>> @@ -1091,7 +1090,7 @@ static struct sched_rt_entity *pick_next
>>       BUG_ON(idx >= MAX_RT_PRIO);
>>
>>       queue = array->queue + idx;
>> -     next = list_entry(queue->next, struct sched_rt_entity, run_list);
>> +     next = list_first_entry(queue, struct sched_rt_entity, run_list);
>>
>>       return next;
>>  }
>
>
>

Re: [PATCH] sched: remove starvation in check_preempt_equal_prio()

[Steven Rostedt]

On Tue, 2011-05-24 at 22:11 +0800, Hillf Danton wrote:
> On Tue, May 24, 2011 at 9:45 PM, Steven Rostedt <rostedt@goodmis.org> wrote:
> > On Tue, 2011-05-24 at 21:34 +0800, Hillf Danton wrote:
> >> If there are pushable tasks and they are high enough in priority, in which
> >> case task p is covered, the current could keep holding its CPU.
> >>
> >> Even if current task has to release its CPU, requeuing task p could result in
> >> starvation of tasks that are of same priority and have been waiting on RQ for
> >> a couple of hours:/
> >
> > Can you explain this better? Sounds like you are describing the
> > definition of FIFO. You are *not* suppose to preempt a FIFO task just
> 
> I dont want to redefine FIFO, but starvation needs attention, since
> the woken task is already off RQ, and its position on RQ is reshuffled.

Does this happen because your other patch doesn't do the work at wake up
anymore? That is, you require a schedule of the high prio task?

There should be no starvation if the currently woken RT task can
migrate, as it should simply go to another rq.

-- Steve

Re: [PATCH] sched: remove starvation in check_preempt_equal_prio()

[Peter Zijlstra]

On Tue, 2011-05-24 at 21:34 +0800, Hillf Danton wrote:
> If there are pushable tasks and they are high enough in priority, in which
> case task p is covered, the current could keep holding its CPU.

-ENOPARSE.. 

> Even if current task has to release its CPU, requeuing task p could result in
> starvation of tasks that are of same priority and have been waiting on RQ for
> a couple of hours:/ 

Starvation of the same priority tasks is a perfectly valid situation for
SCHED_FIFO, also, your changelog fails to mention what you propose to do
about it.

Re: [PATCH] sched: remove starvation in check_preempt_equal_prio()

[Hillf Danton]

On Tue, May 24, 2011 at 9:47 PM, Peter Zijlstra <peterz@infradead.org> wrote:
> On Tue, 2011-05-24 at 21:34 +0800, Hillf Danton wrote:
>> If there are pushable tasks and they are high enough in priority, in which
>> case task p is covered, the current could keep holding its CPU.
>
> -ENOPARSE..
>

Here the priority is same, then pushing task p off has little difference from
pushing any other pushable.

>> Even if current task has to release its CPU, requeuing task p could result in
>> starvation of tasks that are of same priority and have been waiting on RQ for
>> a couple of hours:/
>
> Starvation of the same priority tasks is a perfectly valid situation for
> SCHED_FIFO, also, your changelog fails to mention what you propose to do
> about it.
>
I did get curr requeued, and task_woken_rt() could do what I want.

If you change ENOPARSE to PARSE, I will change task_woken_rt accordingly.

thanks
          Hillf

Re: [PATCH] sched: remove starvation in check_preempt_equal_prio()

[Steven Rostedt]

On Tue, 2011-05-24 at 22:01 +0800, Hillf Danton wrote:
> On Tue, May 24, 2011 at 9:47 PM, Peter Zijlstra <peterz@infradead.org> wrote:
> > On Tue, 2011-05-24 at 21:34 +0800, Hillf Danton wrote:
> >> If there are pushable tasks and they are high enough in priority, in which
> >> case task p is covered, the current could keep holding its CPU.
> >
> > -ENOPARSE..
> >
> 
> Here the priority is same, then pushing task p off has little difference from
> pushing any other pushable.

If task p is currently running and is a FIFO task, you do not push it
off for another task of same prio.

> 
> >> Even if current task has to release its CPU, requeuing task p could result in
> >> starvation of tasks that are of same priority and have been waiting on RQ for
> >> a couple of hours:/
> >
> > Starvation of the same priority tasks is a perfectly valid situation for
> > SCHED_FIFO, also, your changelog fails to mention what you propose to do
> > about it.
> >
> I did get curr requeued, and task_woken_rt() could do what I want.
> 
> If you change ENOPARSE to PARSE, I will change task_woken_rt accordingly.

I'm not sure I can change to PARSE yet.

-- Steve

Re: [PATCH] sched: remove starvation in check_preempt_equal_prio()

[Hillf Danton]

On Tue, May 24, 2011 at 10:24 PM, Steven Rostedt <rostedt@goodmis.org> wrote:
> On Tue, 2011-05-24 at 22:01 +0800, Hillf Danton wrote:
>> On Tue, May 24, 2011 at 9:47 PM, Peter Zijlstra <peterz@infradead.org> wrote:
>> > On Tue, 2011-05-24 at 21:34 +0800, Hillf Danton wrote:
>> >> If there are pushable tasks and they are high enough in priority, in which
>> >> case task p is covered, the current could keep holding its CPU.
>> >
>> > -ENOPARSE..
>> >
>>
>> Here the priority is same, then pushing task p off has little difference from
>> pushing any other pushable.
>
> If task p is currently running and is a FIFO task, you do not push it
> off for another task of same prio.
>
If it is one of the current principles in RT schedule, the patch has
to be dropped.

thanks
          Hillf

Re: [PATCH] sched: remove starvation in check_preempt_equal_prio()

[Steven Rostedt]

On Tue, 2011-05-24 at 22:33 +0800, Hillf Danton wrote:
> On Tue, May 24, 2011 at 10:24 PM, Steven Rostedt <rostedt@goodmis.org> wrote:
> > On Tue, 2011-05-24 at 22:01 +0800, Hillf Danton wrote:
> >> On Tue, May 24, 2011 at 9:47 PM, Peter Zijlstra <peterz@infradead.org> wrote:
> >> > On Tue, 2011-05-24 at 21:34 +0800, Hillf Danton wrote:
> >> >> If there are pushable tasks and they are high enough in priority, in which
> >> >> case task p is covered, the current could keep holding its CPU.
> >> >
> >> > -ENOPARSE..
> >> >
> >>
> >> Here the priority is same, then pushing task p off has little difference from
> >> pushing any other pushable.
> >
> > If task p is currently running and is a FIFO task, you do not push it
> > off for another task of same prio.
> >
> If it is one of the current principles in RT schedule, the patch has
> to be dropped.
> 

Yes, that is the definition of FIFO (First In First Out). The tasks that
get to the CPU first run till they voluntarily schedule away, or are
preempted by an even high priority task. Tasks of the same priority must
wait till the previous task has finished.

-- Steve

Re: [PATCH] sched: remove starvation in check_preempt_equal_prio()

[Hillf Danton]

On Tue, May 24, 2011 at 10:46 PM, Steven Rostedt <rostedt@goodmis.org> wrote:
> On Tue, 2011-05-24 at 22:33 +0800, Hillf Danton wrote:
>> On Tue, May 24, 2011 at 10:24 PM, Steven Rostedt <rostedt@goodmis.org> wrote:
>> > On Tue, 2011-05-24 at 22:01 +0800, Hillf Danton wrote:
>> >> On Tue, May 24, 2011 at 9:47 PM, Peter Zijlstra <peterz@infradead.org> wrote:
>> >> > On Tue, 2011-05-24 at 21:34 +0800, Hillf Danton wrote:
>> >> >> If there are pushable tasks and they are high enough in priority, in which
>> >> >> case task p is covered, the current could keep holding its CPU.
>> >> >
>> >> > -ENOPARSE..
>> >> >
>> >>
>> >> Here the priority is same, then pushing task p off has little difference from
>> >> pushing any other pushable.
>> >
>> > If task p is currently running and is a FIFO task, you do not push it
>> > off for another task of same prio.
>> >
>> If it is one of the current principles in RT schedule, the patch has
>> to be dropped.
>>
>
> Yes, that is the definition of FIFO (First In First Out). The tasks that
> get to the CPU first run till they voluntarily schedule away, or are
> preempted by an even high priority task. Tasks of the same priority must
> wait till the previous task has finished.
>

Though I dont know who is the author of pusher, I like it, and the comments
related to it. The patch is a try to take advantage of pusher to
relive starvation
a bit, but failed.

thanks all comments.

Hillf

Re: [PATCH] sched: remove starvation in check_preempt_equal_prio()

[Hillf Danton]

On Tue, May 24, 2011 at 10:46 PM, Steven Rostedt <rostedt@goodmis.org> wrote:
> On Tue, 2011-05-24 at 22:33 +0800, Hillf Danton wrote:
>> On Tue, May 24, 2011 at 10:24 PM, Steven Rostedt <rostedt@goodmis.org> wrote:
>> > On Tue, 2011-05-24 at 22:01 +0800, Hillf Danton wrote:
>> >> On Tue, May 24, 2011 at 9:47 PM, Peter Zijlstra <peterz@infradead.org> wrote:
>> >> > On Tue, 2011-05-24 at 21:34 +0800, Hillf Danton wrote:
>> >> >> If there are pushable tasks and they are high enough in priority, in which
>> >> >> case task p is covered, the current could keep holding its CPU.
>> >> >
>> >> > -ENOPARSE..
>> >> >
>> >>
>> >> Here the priority is same, then pushing task p off has little difference from
>> >> pushing any other pushable.
>> >
>> > If task p is currently running and is a FIFO task, you do not push it
>> > off for another task of same prio.
>> >
>> If it is one of the current principles in RT schedule, the patch has
>> to be dropped.
>>
>
> Yes, that is the definition of FIFO (First In First Out). The tasks that
> get to the CPU first run till they voluntarily schedule away, or are
> preempted by an even high priority task. Tasks of the same priority must
> wait till the previous task has finished.
>

Then I try to fix the violation of FIFO, my thought is like below:

---
Subject: [PATCH] sched: fix the violation of SCHED_FIFO in
check_preempt_equal_prio()

Starvation of the same priority tasks is a perfectly valid situation for
SCHED_FIFO.

If task p is currently running and is a FIFO task, you do not push it
off for another task of same prio.
Yes, that is the definition of FIFO (First In First Out). The tasks that
get to the CPU first run till they voluntarily schedule away, or are
preempted by an even high priority task. Tasks of the same priority must
wait till the previous task has finished.

Signed-off-by: Hillf Danton <dhillf@gmail.com>
---

--- tip-git/include/linux/sched.h	Sat May 14 15:21:53 2011
+++ sched.h	Wed May 25 21:24:22 2011
@@ -1159,7 +1159,7 @@ struct sched_rt_entity {
 	unsigned long timeout;
 	unsigned int time_slice;
 	int nr_cpus_allowed;
-
+	struct rq *last_rq;
 	struct sched_rt_entity *back;
 #ifdef CONFIG_RT_GROUP_SCHED
 	struct sched_rt_entity	*parent;
--- tip-git/kernel/sched_rt.c	Sun May 22 20:12:01 2011
+++ sched_rt.c	Wed May 25 21:41:02 2011
@@ -933,6 +933,7 @@ static void dequeue_task_rt(struct rq *r
 {
 	struct sched_rt_entity *rt_se = &p->rt;

+	rt_se->last_rq = rq;
 	update_curr_rt(rq);
 	dequeue_rt_entity(rt_se);

@@ -1030,6 +1031,13 @@ select_task_rq_rt(struct task_struct *p,

 static void check_preempt_equal_prio(struct rq *rq, struct task_struct *p)
 {
+	if (p->rt.last_rq == rq)
+		/*
+		 * if task is not newcomer,
+		 * simply preempt current for the sake of SCHED_FIFO.
+		 */
+		goto sched;
+
 	if (rq->curr->rt.nr_cpus_allowed == 1)
 		return;

@@ -1045,6 +1053,7 @@ static void check_preempt_equal_prio(str
 	 * current and none to run 'p', so lets reschedule
 	 * to try and push current away:
 	 */
+sched:
 	requeue_task_rt(rq, p, 1);
 	resched_task(rq->curr);
 }

Re: [PATCH] sched: remove starvation in check_preempt_equal_prio()

[Steven Rostedt]

On Wed, 2011-05-25 at 22:00 +0800, Hillf Danton wrote:

> >
> > Yes, that is the definition of FIFO (First In First Out). The tasks that
> > get to the CPU first run till they voluntarily schedule away, or are
> > preempted by an even high priority task. Tasks of the same priority must
> > wait till the previous task has finished.
> >
> 
> Then I try to fix the violation of FIFO, my thought is like below:
> 
> ---
> Subject: [PATCH] sched: fix the violation of SCHED_FIFO in
> check_preempt_equal_prio()
> 
> Starvation of the same priority tasks is a perfectly valid situation for
> SCHED_FIFO.
> 
> If task p is currently running and is a FIFO task, you do not push it
> off for another task of same prio.
> Yes, that is the definition of FIFO (First In First Out). The tasks that
> get to the CPU first run till they voluntarily schedule away, or are
> preempted by an even high priority task. Tasks of the same priority must
> wait till the previous task has finished.
> 

No, no, no!

I'm sorry if you misunderstood me. When I said 'finished', I did not
mean that it was truly finished and the process has exited. I simply
meant that finished meant that it scheduled away. Done for the time
being.

Thus, if a task is running of one priority, another task of same
priority will *not* preempt it. If that task schedules for whatever
reason, the next task of same priority will then run, and the first one
will now have to wait for it to schedule away. That is FIFO.

Now we do break this semantic a bit for SMP. If the current task that is
running can be migrated to another CPU, and the one that wakes up is of
same priority but is pinned to this CPU. If we can migrate the running
task to another CPU (another CPU has a lower prio process running), then
we will migrate that task to let the woken task run.

But this is not really preempting the running task, it is more "moving"
it. But there's no real guarantees to what RT tasks do on SMP, so we are
fine.

-- Steve