This patch adds the algorithm to pull tasks from RT overloaded runqueues. 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. Signed-off-by: Steven Rostedt --- kernel/sched.c | 8 ++ kernel/sched_rt.c | 161 +++++++++++++++++++++++++++++++++++++++++++++++++----- 2 files changed, 157 insertions(+), 12 deletions(-) Index: linux-test.git/kernel/sched.c =================================================================== --- linux-test.git.orig/kernel/sched.c 2007-10-19 12:34:46.000000000 -0400 +++ linux-test.git/kernel/sched.c 2007-10-19 12:36:05.000000000 -0400 @@ -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; @@ -3614,6 +3621,7 @@ need_resched_nonpreemptible: if (unlikely(!rq->nr_running)) idle_balance(cpu, rq); + schedule_balance_rt(rq, prev); prev->sched_class->put_prev_task(rq, prev); next = pick_next_task(rq, prev); Index: linux-test.git/kernel/sched_rt.c =================================================================== --- linux-test.git.orig/kernel/sched_rt.c 2007-10-19 12:36:02.000000000 -0400 +++ linux-test.git/kernel/sched_rt.c 2007-10-19 12:36:05.000000000 -0400 @@ -158,8 +158,17 @@ static inline void rq_prio_remove_task(s } } +static int pick_rt_task(struct rq *rq, struct task_struct *p, int cpu) +{ + if (!task_running(rq, p) && + (cpu < 0 || cpu_isset(cpu, p->cpus_allowed))) + return 1; + return 0; +} + /* Return the second highest RT task, NULL otherwise */ -static struct task_struct *pick_next_highest_task_rt(struct rq *rq) +static struct task_struct *pick_next_highest_task_rt(struct rq *rq, + int cpu) { struct rt_prio_array *array = &rq->rt.active; struct task_struct *next; @@ -178,26 +187,36 @@ static struct task_struct *pick_next_hig } queue = array->queue + idx; + BUG_ON(list_empty(queue)); + next = list_entry(queue->next, struct task_struct, run_list); - if (unlikely(next != rq->curr)) - return next; + if (unlikely(pick_rt_task(rq, next, cpu))) + goto out; if (queue->next->next != queue) { /* same prio task */ next = list_entry(queue->next->next, struct task_struct, run_list); - return next; + if (pick_rt_task(rq, next, cpu)) + goto out; } + retry: /* slower, but more flexible */ idx = find_next_bit(array->bitmap, MAX_RT_PRIO, idx+1); - if (unlikely(idx >= MAX_RT_PRIO)) { - WARN_ON(1); /* rt_nr_running was 2 and above! */ + if (unlikely(idx >= MAX_RT_PRIO)) return NULL; - } queue = array->queue + idx; - next = list_entry(queue->next, struct task_struct, run_list); + BUG_ON(list_empty(queue)); + + list_for_each_entry(next, queue, run_list) { + if (pick_rt_task(rq, next, cpu)) + goto out; + } + + goto retry; + out: return next; } @@ -286,13 +305,15 @@ static int push_rt_task(struct rq *this_ assert_spin_locked(&this_rq->lock); - next_task = pick_next_highest_task_rt(this_rq); + next_task = pick_next_highest_task_rt(this_rq, -1); if (!next_task) return 0; retry: - if (unlikely(next_task == this_rq->curr)) + if (unlikely(next_task == this_rq->curr)) { + WARN_ON(1); return 0; + } /* * It's possible that the next_task slipped in of @@ -316,7 +337,7 @@ static int push_rt_task(struct rq *this_ * so it is possible that next_task has changed. * If it has, then try again. */ - task = pick_next_highest_task_rt(this_rq); + task = pick_next_highest_task_rt(this_rq, -1); if (unlikely(task != next_task) && task && paranoid--) { put_task_struct(next_task); next_task = task; @@ -361,6 +382,121 @@ static void push_rt_tasks(struct rq *rq) ; } +static int pull_rt_task(struct rq *this_rq) +{ + struct task_struct *next; + 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; + + next = pick_next_task_rt(this_rq); + + for_each_cpu_mask(cpu, rto_cpumask) { + if (this_cpu == cpu) + continue; + + src_rq = cpu_rq(cpu); + if (src_rq->rt_nr_running <= 1) + continue; + + /* + * We can potentially drop this_rq's lock in + * double_lock_balance, and another CPU could + * steal our next task - hence we must cause + * the caller to recalculate the next task + * in that case: + */ + if (double_lock_balance(this_rq, src_rq)) { + struct task_struct *old_next = next; + next = pick_next_task_rt(this_rq); + if (next != old_next) + ret = 1; + } + + /* + * Are there still pullable RT tasks? + */ + if (src_rq->rt_nr_running <= 1) { + spin_unlock(&src_rq->lock); + continue; + } + + p = pick_next_highest_task_rt(src_rq, this_cpu); + + /* + * Do we have an RT task that preempts + * the to-be-scheduled task? + */ + if (p && (!next || (p->prio < next->prio))) { + WARN_ON(p == src_rq->curr); + WARN_ON(!p->se.on_rq); + + /* + * There's a chance that p is higher in priority + * than what's currently running on its cpu. + * This is just that p is wakeing up and hasn't + * had a chance to schedule. We only pull + * p if it is lower in priority than the + * current task on the run queue or + * this_rq next task is lower in prio than + * the current task on that rq. + */ + if (p->prio < src_rq->curr->prio || + (next && next->prio < src_rq->curr->prio)) + goto bail; + + ret = 1; + + deactivate_task(src_rq, p, 0); + set_task_cpu(p, this_cpu); + activate_task(this_rq, p, 0); + /* + * We continue with the search, just in + * case there's an even higher prio task + * in another runqueue. (low likelyhood + * but possible) + */ + + /* + * Update next so that we won't pick a task + * on another cpu with a priority lower (or equal) + * than the one we just picked. + */ + next = p; + + } + bail: + spin_unlock(&src_rq->lock); + } + + return ret; +} + +static void schedule_balance_rt(struct rq *rq, + struct task_struct *prev) +{ + struct rt_prio_array *array; + int next_prio; + + /* Try to pull RT tasks here if we lower this rq's prio */ + if (unlikely(rt_task(prev))) { + next_prio = MAX_RT_PRIO; + if (rq->rt_nr_running) { + array = &rq->rt.active; + next_prio = sched_find_first_bit(array->bitmap); + } + if (next_prio > prev->prio) + pull_rt_task(rq); + } +} + static void schedule_tail_balance_rt(struct rq *rq) { /* @@ -377,7 +513,8 @@ static void schedule_tail_balance_rt(str } } #else /* CONFIG_SMP */ -# define schedule_tail_balance_rt(rq) do { } while (0) +# define schedule_balance_rt(rq) do { } while (0) +# define schedule_tail_balance_rt(rq) do { } while (0) #endif /* CONFIG_SMP */ static void put_prev_task_rt(struct rq *rq, struct task_struct *p) -- - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/