New RT Task Balancing

kernel/sched.c 2007-10-19 12:33:09.000000000 -0400 renamed from kernel/sched.c 2007-10-19 12:32:39.000000000 -0400 +12 -0

+static inline void inc_rt_tasks(struct task_struct *p, struct rq *rq)
+{
+       if (rt_task(p))
+               rq->rt_nr_running++;
+}
+
+static inline void dec_rt_tasks(struct task_struct *p, struct rq *rq)
+{
+       if (rt_task(p)) {
+               WARN_ON(!rq->rt_nr_running);
+               rq->rt_nr_running--;
+       }

Quoted 9 lines · Steven Rostedt

[ ... ]
Index: linux-test.git/kernel/sched.c
===================================================================

kernel/sched.c 2007-10-19 12:33:09.000000000 -0400 renamed from kernel/sched.c 2007-10-19 12:32:39.000000000 -0400 +0 -0

@@ -300,6 +300,8 @@ struct rq {
         */
        unsigned long nr_uninterruptible;
 

kernel/sched.c 2007-10-19 12:33:09.000000000 -0400 struct rq { · line 303

Quoted 1 line

kernel/sched.c 2007-10-19 12:33:09.000000000 -0400 renamed from kernel/sched.c 2007-10-19 12:32:39.000000000 -0400 +1 -0

+       unsigned long rt_nr_running;

could it be a part of the 'struct rt_rq' instead?

Quoted 20 lines

kernel/sched.c 2007-10-19 12:33:09.000000000 -0400 renamed from kernel/sched.c 2007-10-19 12:32:39.000000000 -0400 +14 -0

+static inline void inc_rt_tasks(struct task_struct *p, struct rq *rq)
+{
+       if (rt_task(p))
+               rq->rt_nr_running++;
+}
+
+static inline void dec_rt_tasks(struct task_struct *p, struct rq *rq)
+{
+       if (rt_task(p)) {
+               WARN_ON(!rq->rt_nr_running);
+               rq->rt_nr_running--;
+       }
+}
+
 static void enqueue_task_rt(struct rq *rq, struct task_struct *p, int wakeup)
 {
        struct rt_prio_array *array = &rq->rt.active;

kernel/sched.c 2007-10-19 12:33:09.000000000 -0400

Quoted 4 lines

        list_add_tail(&p->run_list, array->queue + p->prio);
        __set_bit(p->prio, array->bitmap);

kernel/sched.c 2007-10-19 12:33:09.000000000 -0400 renamed from kernel/sched.c 2007-10-19 12:32:39.000000000 -0400 +2 -0

+
+       inc_rt_tasks(p, rq);

why do you need the rt_task(p) check in {inc,dec}_rt_tasks() ?

{enqueue,dequeue}_task_rt() seem to be the only callers and they will crash (or corrupt memory) anyway in the case of ! rt_task(p) (sure, this case would mean something is broken somewhere wrt sched_class handling).

This patch adds accounting to each runqueue to keep track of the highest prio task queued on the run queue. We only care about RT tasks, so if the run queue does not contain any active RT tasks its priority will be considered MAX_RT_PRIO.

This information will be used for later patches.

kernel/sched.c +5 -0

@@ -972,6 +974,8 @@ static void activate_task(struct rq *rq,
 
 	enqueue_task(rq, p, wakeup);
 	inc_nr_running(p, rq);
+
+	rq_prio_add_task(rq, p);
 }
 
 /*

@@ -984,6 +988,8 @@ static void deactivate_task(struct rq *r
 
 	dequeue_task(rq, p, sleep);
 	dec_nr_running(p, rq);
+
+	rq_prio_remove_task(rq, p);
 }
 
 /**

@@ -6619,6 +6625,7 @@ void __init sched_init(void)
 		rq->cpu = i;
 		rq->migration_thread = NULL;
 		INIT_LIST_HEAD(&rq->migration_queue);
+		rq->highest_prio = MAX_RT_PRIO;
 #endif
 		atomic_set(&rq->nr_iowait, 0);
 

Index: linux-test.git/kernel/sched_rt.c
===================================================================

kernel/sched_rt.c +15 -0

@@ -110,6 +110,31 @@ static struct task_struct *pick_next_tas
 	return next;
 }
 
+#ifdef CONFIG_SMP
+static inline void rq_prio_add_task(struct rq *rq, struct task_struct *p)
+{
+	if (unlikely(rt_task(p)) && p->prio < rq->highest_prio)
+		rq->highest_prio = p->prio;
+}
+
+static inline void rq_prio_remove_task(struct rq *rq, struct task_struct *p)
+{
+	struct rt_prio_array *array;
+
+	if (unlikely(rt_task(p))) {
+		if (rq->rt_nr_running) {
+			if (p->prio >= rq->highest_prio) {
+				/* recalculate */

plain text document attachment (add-rq-highest-prio.patch) This patch adds accounting to each runqueue to keep track of the highest prio task queued on the run queue. We only care about RT tasks, so if the run queue does not contain any active RT tasks its priority will be considered MAX_RT_PRIO.

This information will be used for later patches.

Signed-off-by Steven Rostedt <[email protected]>

---
 kernel/sched.c    |    7 +++++++
 kernel/sched_rt.c |   25 +++++++++++++++++++++++++
 2 files changed, 32 insertions(+)

Index: linux-test.git/kernel/sched.c
===================================================================

kernel/sched.c +2 -0

@@ -324,6 +324,8 @@ struct rq {
 	int push_cpu;
 	/* cpu of this runqueue: */
 	int cpu;
+	/* highest queued rt task prio */
+	int highest_prio;
 
 	struct task_struct *migration_thread;
 	struct list_head migration_queue;

kernel/sched.c +1 -0

 }
 
 /**

@@ -6619,6 +6625,7 @@ void __init sched_init(void)
 		rq->cpu = i;
 		rq->migration_thread = NULL;
 		INIT_LIST_HEAD(&rq->migration_queue);
+		rq->highest_prio = MAX_RT_PRIO;
 #endif
 		atomic_set(&rq->nr_iowait, 0);
 

Index: linux-test.git/kernel/sched_rt.c
===================================================================

kernel/sched_rt.c +4 -0

@@ -110,6 +110,31 @@ static struct task_struct *pick_next_tas
 	return next;
 }
 
+#ifdef CONFIG_SMP
+static inline void rq_prio_add_task(struct rq *rq, struct task_struct *p)
+{
+	if (unlikely(rt_task(p)) && p->prio < rq->highest_prio)

kernel/sched_rt.c +11 -0

+				/* recalculate */
+				array = &rq->rt.active;
+				rq->highest_prio =
+					sched_find_first_bit(array->bitmap);
+			} /* otherwise leave rq->highest prio alone */
+		} else
+			rq->highest_prio = MAX_RT_PRIO;
+	}
+}
+#endif /* CONFIG_SMP */
+
 static void put_prev_task_rt(struct rq *rq, struct task_struct *p)
 {
 	update_curr_rt(rq);

Quoted 5 lines

kernel/sched.c +0 -0

 	struct task_struct *migration_thread;
 	struct list_head migration_queue;

@@ -972,6 +974,8 @@ static void activate_task(struct rq *rq,
 

kernel/sched.c static void activate_task(struct rq *rq, · line 979

Quoted 5 lines

kernel/sched.c +2 -0

 	enqueue_task(rq, p, wakeup);
 	inc_nr_running(p, rq);
+
+	rq_prio_add_task(rq, p);
 }

We are better off doing this in enqueue_task() or PI boosting will fail to alter the prio of the RQ.

kernel/sched.c static void deactivate_task(struct rq *r · line 992

Quoted 9 lines

kernel/sched.c +2 -0

 /*

@@ -984,6 +988,8 @@ static void deactivate_task(struct rq *r
 
 	dequeue_task(rq, p, sleep);
 	dec_nr_running(p, rq);
+
+	rq_prio_remove_task(rq, p);

Ditto for dequeue_task()

Quoted 24 lines

kernel/sched.c +1 -0

 }
 
 /**

@@ -6619,6 +6625,7 @@ void __init sched_init(void)
 		rq->cpu = i;
 		rq->migration_thread = NULL;
 		INIT_LIST_HEAD(&rq->migration_queue);
+		rq->highest_prio = MAX_RT_PRIO;
 #endif
 		atomic_set(&rq->nr_iowait, 0);
 

Index: linux-test.git/kernel/sched_rt.c
===================================================================

kernel/sched_rt.c +4 -0

@@ -110,6 +110,31 @@ static struct task_struct *pick_next_tas
 	return next;
 }
 
+#ifdef CONFIG_SMP
+static inline void rq_prio_add_task(struct rq *rq, struct task_struct *p)
+{
+	if (unlikely(rt_task(p)) && p->prio < rq->highest_prio)

kernel/sched_rt.c static struct task_struct *pick_next_tas · line 126

Quoted 10 lines

kernel/sched_rt.c +10 -0

+		rq->highest_prio = p->prio;
+}
+
+static inline void rq_prio_remove_task(struct rq *rq, struct task_struct *p)
+{
+	struct rt_prio_array *array;
+
+	if (unlikely(rt_task(p))) {
+		if (rq->rt_nr_running) {
+			if (p->prio >= rq->highest_prio) {

<= ?

We only need to recalc if the task being removed was the highest prio (or higher, if that were possible but it shouldnt be).

I think this logic will technically work as-is because every task is

always >= highest in a properly accounted system, so you will just simply recalc for every remove. But I do like the optimization that you were trying to add.

So for the paranoid:

				BUG_ON(p->prio < rq->highest_prio);
				if (p->prio == rq->highest_prio) {
					/* recalc */
				}

[ ... ]

kernel/sched.c 2007-10-19 12:34:32.000000000 -0400 renamed from kernel/sched.c 2007-10-19 12:33:09.000000000 -0400 +2 -0

@@ -972,6 +974,8 @@ static void activate_task(struct rq *rq,
 
        enqueue_task(rq, p, wakeup);
        inc_nr_running(p, rq);
+
+       rq_prio_add_task(rq, p);
 }
 
 /*

kernel/sched.c 2007-10-19 12:34:32.000000000 -0400 renamed from kernel/sched.c 2007-10-19 12:33:09.000000000 -0400 +14 -0

+static inline void rq_prio_add_task(struct rq *rq, struct task_struct *p)
+{
+       if (unlikely(rt_task(p)) && p->prio < rq->highest_prio)
+               rq->highest_prio = p->prio;
+}
+
+static inline void rq_prio_remove_task(struct rq *rq, struct task_struct *p)
+{
+       struct rt_prio_array *array;
+
+       if (unlikely(rt_task(p))) {
+               if (rq->rt_nr_running) {
+                       if (p->prio >= rq->highest_prio) {
+                               /* recalculate */

Quoted 2 lines · Steven Rostedt

[ ... ]

===================================================================

kernel/sched.c 2007-10-19 12:34:32.000000000 -0400 struct rq { · line 328

Quoted 8 lines

kernel/sched.c 2007-10-19 12:34:32.000000000 -0400 renamed from kernel/sched.c 2007-10-19 12:33:09.000000000 -0400 +2 -0

@@ -324,6 +324,8 @@ struct rq {
        int push_cpu;
        /* cpu of this runqueue: */
        int cpu;
+       /* highest queued rt task prio */
+       int highest_prio;

again, could it be moved to 'struct rt_rq' ?
(so we want to cache it as we don't want to trash more per-cpu bytes calling smth like
if (!rt_nr_running) sched_find_first_bit() from other CPUs)

Quoted 13 lines

kernel/sched.c 2007-10-19 12:34:32.000000000 -0400 renamed from kernel/sched.c 2007-10-19 12:33:09.000000000 -0400 +2 -0

@@ -972,6 +974,8 @@ static void activate_task(struct rq *rq,
 
        enqueue_task(rq, p, wakeup);
        inc_nr_running(p, rq);
+
+       rq_prio_add_task(rq, p);
 }
 
 /*

@@ -984,6 +988,8 @@ static void deactivate_task(struct rq *r
 

kernel/sched.c 2007-10-19 12:34:32.000000000 -0400 static void deactivate_task(struct rq *r · line 993

Quoted 5 lines

kernel/sched.c 2007-10-19 12:34:32.000000000 -0400 renamed from kernel/sched.c 2007-10-19 12:33:09.000000000 -0400 +2 -0

        dequeue_task(rq, p, sleep);
        dec_nr_running(p, rq);
+
+       rq_prio_remove_task(rq, p);
 }

{enqueue,dequeue}_task_rt() would be more appropriate places.

Quoted 16 lines

kernel/sched.c 2007-10-19 12:34:32.000000000 -0400 renamed from kernel/sched.c 2007-10-19 12:33:09.000000000 -0400 +14 -0

+static inline void rq_prio_add_task(struct rq *rq, struct task_struct *p)
+{
+       if (unlikely(rt_task(p)) && p->prio < rq->highest_prio)
+               rq->highest_prio = p->prio;
+}
+
+static inline void rq_prio_remove_task(struct rq *rq, struct task_struct *p)
+{
+       struct rt_prio_array *array;
+
+       if (unlikely(rt_task(p))) {
+               if (rq->rt_nr_running) {
+                       if (p->prio >= rq->highest_prio) {
+                               /* recalculate */

kernel/sched.c 2007-10-19 12:34:32.000000000 -0400 static void deactivate_task(struct rq *r

Quoted 10 lines

kernel/sched.c 2007-10-19 12:34:32.000000000 -0400 renamed from kernel/sched.c 2007-10-19 12:33:09.000000000 -0400 +10 -0

+                               array = &rq->rt.active;
+                               rq->highest_prio =
+                                       sched_find_first_bit(array->bitmap);
+                       } /* otherwise leave rq->highest prio alone */
+               } else
+                       rq->highest_prio = MAX_RT_PRIO;
+       }
+}
+#endif /* CONFIG_SMP */
+

(just a few thoughts)

we call sched_find_first_bit() in pick_next_task_rt() in the case when rt_nr_running != 0.

So if we can tolerate the 'latency' of updating the 'highest_prio' == the interval of time between deactivate_task() and pick_next_task() in schedule() then rq_prio_remove_task() would just need to do a single thing:

/* No more RT tasks: */
if (!rt_nr_running)

        highest_prio = MAX_RT_PRIO;

and then,

static struct task_struct *pick_next_task_rt(struct rq *rq)

{
        struct rt_prio_array *array = &rq->rt.active;
        struct task_struct *next;
        struct list_head *queue;
        int idx;

(quoted diff) +1 -1

-        idx = sched_find_first_bit(array->bitmap);
+       rq->highest_prio = idx = sched_find_first_bit(array->bitmap);
 
[ ... ]

additionally, if we can tolerate the 'latency' (of updating highest_prio) == the worst case scheduling latency, then rq_prio_add_task() is not necessary at all.

plain text document attachment (rt-balance-pull-tasks.patch)

kernel/sched_rt.c +3 -0

+static int pull_rt_task(struct rq *this_rq)
+{
+	struct task_struct *next;

kernel/sched_rt.c +5 -0

+	next = pick_next_task_rt(this_rq);
+
+	for_each_cpu_mask(cpu, rto_cpumask) {
+		if (this_cpu == cpu)
+			continue;

kernel/sched_rt.c +4 -0

+	}
+
+	return ret;
+}

Quoted 5 lines · Steven Rostedt

plain text document attachment (rt-balance-pull-tasks.patch)

kernel/sched_rt.c +3 -0

+static int pull_rt_task(struct rq *this_rq)
+{
+	struct task_struct *next;

kernel/sched_rt.c static void push_rt_tasks(struct rq *rq) · line 397

Quoted 10 lines

kernel/sched_rt.c +10 -0

+	struct task_struct *p;
+	struct rq *src_rq;
+	int this_cpu = this_rq->cpu;
+	int cpu;
+	int ret = 0;
+
+	assert_spin_locked(&this_rq->lock);
+
+	if (likely(!atomic_read(&rt_overload)))
+		return 0;

This seems to be the only usage of rt_overload. I'm not sure its worth keeping it around for this.

Quoted 5 lines

kernel/sched_rt.c +5 -0

+	next = pick_next_task_rt(this_rq);
+
+	for_each_cpu_mask(cpu, rto_cpumask) {
+		if (this_cpu == cpu)
+			continue;

...

Quoted 4 lines

kernel/sched_rt.c +4 -0

+	}
+
+	return ret;
+}

Quoted 6 lines

kernel/sched_rt.c static void push_rt_tasks(struct rq *rq) · line 397

Quoted 3 lines

kernel/sched_rt.c +3 -0

+
+	if (likely(!atomic_read(&rt_overload)))
+		return 0;

This seems to be the only usage of rt_overload. I'm not sure its worth keeping it around for this.

Ingo just brought up a good point. With large smp (where large is >64) this will all suck chunks.

rt_overload will bounce around the system, and the rto_cpumask updates might already hurt.

The idea would be to do this per cpuset, these naturally limit the migraiton posibilities of tasks and would thus be the natural locality to break this data structure.

When a pull RT is initiated, all overloaded runqueues are examined for a RT task that is higher in prio than the highest prio task queued on the target runqueue. If another runqueue holds a RT task that is of higher prio than the highest prio task on the target runqueue is found it is pulled to the target runqueue.

[ ... ]

Hi Steven,

Quoted 5 lines

When a pull RT is initiated, all overloaded runqueues are examined for a RT task that is higher in prio than the highest prio task queued on the target runqueue. If another runqueue holds a RT task that is of higher prio than the highest prio task on the target runqueue is found it is pulled to the target runqueue.

I think, 2 things should be accomplished here :

(1) be sure to pull the _highest_ prio task ;

i.e. the _highest_ prio task amongst all runnable (but not running) RT tasks across all the run-queues which is capable of running on this_cpu ;

(2) don't pull more than 1 task at once.

that said, just pull the highest prio task and run it.

---

why (2)? Just to avoid situations when tasks are being pulled/pushed back and forth between run-queues.

Let's say we have 4 cpu system:

0:  task(10) , task(92)
1:  task(10), task(91)
2:  task(10), task(90)
3:  task(10)

when task(10) on cpu#3 is inactive, we pull task(92), task(91), task(90) and then run task(90)... in the mean time, some of cpu[0..2] becomes inactive and pull task(91) and task(92) back and run them... that may repeat again and again depending on when/how long task(10) run on their corresponding cpus...

so it seems to me that the more optimal behavior would be "don't pull more than you can run at the moment -- that's 1".

to this goal, something like find_lock_highest_rq() would be necessary.

and I guess, {get,put}_task_struct() should be used in pull_rt_task() for the 'next' in a similar way as it's done in push_rt_task() .

[ ... ]

kernel/sched.c +7 -0

@@ -2927,6 +2927,13 @@ static void idle_balance(int this_cpu, s
        int pulled_task = -1;
        unsigned long next_balance = jiffies + HZ;
 
+       /*
+        * pull_rt_task returns true if the run queue changed.
+        * But this does not mean we have a task to run.
+        */
+       if (unlikely(pull_rt_task(this_rq)) && this_rq->nr_running)
+               return;
+
        for_each_domain(this_cpu, sd) {
                unsigned long interval;
 

Quoted 17 lines · Steven Rostedt

[ ... ]

kernel/sched.c +7 -0

@@ -2927,6 +2927,13 @@ static void idle_balance(int this_cpu, s
        int pulled_task = -1;
        unsigned long next_balance = jiffies + HZ;
 
+       /*
+        * pull_rt_task returns true if the run queue changed.
+        * But this does not mean we have a task to run.
+        */
+       if (unlikely(pull_rt_task(this_rq)) && this_rq->nr_running)
+               return;
+
        for_each_domain(this_cpu, sd) {
                unsigned long interval;
 

kernel/sched.c need_resched_nonpreemptible: · line 3624

Quoted 4 lines

kernel/sched.c +1 -0

@@ -3614,6 +3621,7 @@ need_resched_nonpreemptible:
        if (unlikely(!rq->nr_running))
                idle_balance(cpu, rq);
 
+       schedule_balance_rt(rq, prev);

we do pull_rt_task() in idle_balance() so, I think, there is no need to do it twice.
i.e.

         if (unlikely(!rq->nr_running))
                 idle_balance(cpu, rq);

(quoted diff) +2 -0

+       else
+               schedule_balance_rt(rq, prev);

hum?

moreover (continuing my previous idea on "don't pull more than 1 task at once"), I wonder whether you really see cases when more than 1 task have been successfully _pushed_ over to other run-queues at once...

I'd expect the push/pull algorithm to naturally avoid such a possibility. Let's say we have a few RT tasks on our run-queue that are currently runnable (but not running)... the question is 'why do they still here?'

(1) because the previous attempt to _push_ them failed;
(2) because they were not _pulled_ from other run-queues.

both cases should mean that other run-queues have tasks with higher prios running at the moment.

yes, there is a tiny window in schedule() between deactivate_task() [ which can make this run-queue to look like we can push over to it ] and idle_balance() -> pull_rt_task() _or_ schedule_balance_rt() -> pull_rt_task() [ where this run-queue will try to pull tasks on its own ]

_but_ the run-queue is locked in this case so we wait in double_lock_balance() (from push_rt_task()) and run into the competition with 'src_rq' (which is currently in the 'tiny window' as described above trying to run pull_rt_task()) for getting both self_rq and src_rq locks...

this way, push_rt_task() always knows the task to be pushed (so it can be a bit optimized) --- as it's either a newly woken up RT task with (p->prio > rq->curr->prio) _or_ a preempted RT task (so we know 'task' for both cases).

To sum it up, I think that the pull/push algorithm should be able to naturally accomplish the proper job pushing/pulling 1 task at once (as described above)... any additional actions are just overhead or there is some problem with the algorithm (ah well, or with my understanding :-/ )

On wakeup, we can wake up several RT tasks (as my test case does) and if we only push one task, then the other tasks may not migrate over to the other run queues. I logged this happening in my tests.

-- Steve

Hi Steven,

agreed with your comments in the previous message. Indeed, I missed some points.

Quoted 3 lines

On wakeup, we can wake up several RT tasks (as my test case does) and if we only push one task, then the other tasks may not migrate over to the other run queues. I logged this happening in my tests.

I guess, what may happen is that while we are running push_rt_tasks() on CPU-k (say, as a result on try_to_wake_up(task_1))
and as this_rq->lock may get released (in double_lock_balance()) , we may get in a 'race'
with try_to_wake_up(task_2) from (another) CPU-m.
It places a woken up task on the same run-queue (for which push_rt_task() is already running on CPU-k) and, actually, run push_rt_task() for the same rq again!

So it may happen that both task_1 and task_2 will be pushed from the same CPU...

Do you see an error in my description? (it's a late hour so I can miss something again ... sure, otherwise I'm almost perfect :-/ ) Can it correlate with what you have observed in your tests?

Otherwise, there is 1:1 relation : push_rt_task() is called for every new (single) task activated by try_to_wake_up() and for a preempted task... so it's not like a few tasks are placed on the run-queue and then push_rt_tasks() is called once.

btw., if this scenario may take place... maybe it would make sense to have something like RTLB_INPROGRESS/PENDING and to avoid competing push_rt_tasks() calls for the same 'rq' from different CPUs? (although, there can be some disadvantages here as well. e.g. we would likely need to remove 'max 3 tasks at once' limit and get, theoretically, unbounded time spent in push_rt_tasks() on a single CPU).