lkml.org 
[lkml]   [2007]   [Oct]   [19]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
Patch in this message
/
Date
From
Subject[patch 6/8] pull RT tasks
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 <rostedt@goodmis.org>

---
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/

\
 
 \ /
  Last update: 2007-10-19 20:49    [W:0.113 / U:0.616 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site