New RT Task Balancing -v3
Subsystems (3)
Steven Rostedt
reviewerv3 cover New RT Task Balancing -v3
[
Changes since V2:
Updated to git tree 8c0863403f109a43d7000b4646da4818220d501f
This version also contains patches from Gregory Haskins.
Actually brought back the global RT overload bitmask. The reason is that it should be seldom written to. The RT overload bitmask is only set when more than one RT task is scheduled to run on the same runqueue. This event should not happen often. The other methods of trying to get rid of the global cpumask had issues of its own.
Also to avoid overloading the runqueue, a check is made before an RT task is actually scheduled to a runqueue to see if it would be better to place that woken RT task onto another runqueue if the current runqueue is currently running another RT task. Even if the currently running RT task is of lower priority than the one waking up. We still try to move the woken RT task to another runqueue if possible.
The reason is that RT tasks behave different than normal tasks. Preempting a normal task to run a RT task to keep its cache hot is fine, because the preempted non-RT task may wait on that same runqueue to run again unless the migration thread comes along and pulls it off.
RT tasks behave differently. If one is preempted, it makes an active effort to continue to run. So by having a high priority task preempt a lower priority RT task, that lower RT task will then quickly try to run on another runqueue. This will cause that lower RT task to replace its nice hot cache (and TLB) with a completely cold one. This is for the hope that the new high priority RT task will keep its cache hot.
Remeber that this high priority RT task was just woken up. So it may likely have been sleeping for several milliseconds, and will end up with a cold cache anyway. RT tasks run till they voluntarily stop, or are preempted by a higher priority task. This means that it is unlikely that the woken RT task will have a hot cache to wake up to. So pushing off a lower RT task is just killing its cache for no good reason.
]
Currently in mainline the balancing of multiple RT threads is quite broken. That is to say that a high priority thread that is scheduled on a CPU with a higher priority thread, may need to unnecessarily wait while it can easily run on another CPU that's running a lower priority thread.
Balancing (or migrating) tasks in general is an art. Lots of considerations must be taken into account. Cache lines, NUMA and more. This is true with general processes which expect high through put and migration can be done in batch. But when it comes to RT tasks, we really need to put them off to a CPU that they can run on as soon as possible. Even if it means a bit of cache line flushing.
Right now an RT task can wait several milliseconds before it gets scheduled to run. And perhaps even longer. The migration thread is not fast enough to take care of RT tasks.
To demonstrate this, I wrote a simple test.
http://rostedt.homelinux.com/rt/rt-migrate-test.c
(gcc -o rt-migrate-test rt-migrate-test.c -lpthread)
This test expects a parameter to pass in the number of threads to create. If you add the '-c' option (check) it will terminate if the test fails one of the iterations. If you add this, pass in +1 threads.
For example, on a 4 way box, I used
rt-migrate-test -c 5
What this test does is to create the number of threads specified (in this case 5). Each thread is set as an RT FIFO task starting at a specified prio (default 2) and each thread being one priority higher. So with this example the 5 threads created are at priorities 2, 3, 4, 5, and 6.
The parent thread sets its priority to one higher than the highest of the children (this example 7). It uses pthread_barrier_wait to synchronize the threads. Then it takes a time stamp and starts all the threads. The threads when woken up take a time stamp and compares it to the parent thread to see how long it took to be awoken. It then runs for an interval (20ms default) in a busy loop. The busy loop ends when it reaches the interval delta from the start time stamp. So if it is preempted, it may not actually run for the full interval. This is expected behavior of the test.
The numbers recorded are the delta from the thread's time stamp from the parent time stamp. The number of iterations it ran the busy loop for, and the delta from a thread time stamp taken at the end of the loop to the parent time stamp.
Sometimes a lower priority task might wake up before a higher priority, but this is OK, as long as the higher priority process gets the CPU when it is awoken.
At the end of the test, the iteration data is printed to stdout. If a higher priority task had to wait for a lower one to finish running, then this is considered a failure. Here's an example of the output from a run against git commit 4fa4d23fa20de67df919030c1216295664866ad7.
1: 36 33 20041 39 33
len: 20036 20033 40041 20039 20033
loops: 167789 167693 227167 167829 167814
On iteration 1 (starts at 0) the third task started at 20ms after the parent woke it up. We can see here that the first two tasks ran to completion before the higher priority task was even able to start. That is a 20ms latency for the higher priority task!!!
So people who think that their audio would lose most latencies by upping the priority, may be in for a surprise. Since some kernel threads (like the migration thread itself) may cause this latency.
To solve this issue, I've changed the RT task balancing from a passive method (migration thread) to an active method. This new method is to actively push or pull RT tasks when they are woken up or scheduled.
On wake up of a task if it is an RT task, and there's already an RT task of higher priority running on its runqueue, we initiate a push_rt_tasks algorithm. This algorithm looks at the highest non-running RT task and tries to find a CPU where it can run on. It only migrates the RT task if it finds a CPU (of lowest priority) where the RT task can run on and can preempt the currently running task on that CPU. We continue pushing RT tasks until we can't push anymore.
If a RT task fails to be migrated we stop the pushing. This is possible because we are always looking at the highest priority RT task on the run queue. And if it can't migrate, then most likely the lower RT tasks can not either.
There is one case that is not covered by this patch set. That is that when the highest priority non running RT task has its CPU affinity in such a way that it can not preempt any tasks on the CPUs running on CPUs of its affinity. But a lower priority task has a larger affinity to CPUs that it can run on. This is a case where the lower priority task will not be migrated to those CPUS (although those CPUs may pull that task). Currently this patch set ignores this scenario.
Another case where we push RT tasks is in the finish_task_switch. This is done since the running RT task can not be migrated while it is running. So if an RT task is preempted by a higher priority RT task, we can migrate the RT task being preempted at that moment.
We also actively pull RT tasks. Whenever a runqueue is about to lower its priority (schedule a lower priority task) a check is done to see if that runqueue can pull RT tasks to it to run instead. A search is made of all overloaded runqueues (runqueues with more than one RT task scheduled on it) and checked to see if they have an RT task that can run on the runqueue (affinity matches) and is of higher priority than the task the runqueue is about to schedule. The pull algorithm pulls all RT tasks that match this case.
With this patch set, I ran the rt-migrate-test over night in a while loop with the -c option (which terminates upon failure) and it passed over 6500 tests (each doing 50 wakeups each).
Here's an example of the output from the patched kernel. This is just to explain it a bit more.
1: 20060 61 55 56 61
len: 40060 20061 20055 20056 20061
loops: 227255 146050 168104 145965 168144
2: 40 46 31 35 42
len: 20040 20046 20031 20035 20042
loops: 28 167769 167781 167668 167804
The first iteration (really 2cd, since we start at zero), is a typical run. The lowest prio task didn't start executing until the other 4 tasks finished and gave up the CPU.
The second iteration seems at first like a failure. But this is actually fine. The lowest priority task just happen to schedule onto a CPU before the higher priority tasks were woken up. But as you can see from this example, the higher priority tasks still were able to get scheduled right away and in doing so preempted the lower priority task. This can be seen by the number of loops that the lower priority task was able to complete. Only 28. This is because the busy loop terminates when the time stamp reaches the time interval (20ms here) from the start time stamp. Since the lower priority task was able to sneak in and start, it's time stamp was low. So after it got preempted, and rescheduled, it was already past the run time interval so it simply ended the loop.
Finally, the CFS RT balancing had to be removed in order for this to work. Testing showed that the CFS RT balancing would actually pull RT tasks from runqueues already assigned to the proper runqueues, and again cause latencies. With this new approach, the CFS RT balancing is not needed, and I suggest that these patches replace the current CFS RT balancing.
Also, let me stress, that I made a great attempt to have this cause as little overhead (practically none) to the non RT cases. Most of these algorithms only take place when more than one RT task is scheduled on the same runqueue.
Special thanks goes to Gregory Haskins for his advice and back and forth on IRC with ideas. Although I didn't use his actual patches (his were against -rt) it did help me clean up some of my code. Also, thanks go to Ingo Molnar himself for taking some ideas from his RT balance code in the -rt patch.
Comments welcomed!
-- Steve
Steven Rostedt
reviewerPATCH v3 1/17 Add rt_nr_running accounting
This patch adds accounting to keep track of the number of RT tasks running on a runqueue. This information will be used in later patches.
--- kernel/sched.c | 1 + kernel/sched_rt.c | 17 +++++++++++++++++ 2 files changed, 18 insertions(+)
kernel/sched.c +1 -0
@@ -266,6 +266,7 @@ struct rt_rq {struct rt_prio_array active;int rt_load_balance_idx;struct list_head *rt_load_balance_head, *rt_load_balance_curr; +unsigned long rt_nr_running; };/*
kernel/sched_rt.c +17 -0
@@ -25,12 +25,27 @@ static void update_curr_rt(struct rq *rq curr->se.exec_start = rq->clock; } +static inline void inc_rt_tasks (struct task_struct *p,struct rq *rq) +{ +WARN_ON (!rt_task (p)); + rq->rt.rt_nr_running++; +} + +static inline void dec_rt_tasks (struct task_struct *p,struct rq *rq) +{ +WARN_ON (!rt_task (p)); +WARN_ON (!rq->rt.rt_nr_running); + rq->rt.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;list_add_tail (&p->run_list, array->queue + p->prio);__set_bit (p->prio, array->bitmap); + +inc_rt_tasks (p, rq); }/*
@@ -45,6 +60,8 @@ static void dequeue_task_rt(struct rq *rlist_del (&p->run_list);if (list_empty (array->queue + p->prio))__clear_bit (p->prio, array->bitmap); + +dec_rt_tasks (p, rq); }/*
Steven Rostedt
reviewerPATCH v3 2/17 track highest prio queued on runqueue
In reply to Steven RostedtThis 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 | 3 +++ kernel/sched_rt.c | 18 ++++++++++++++++++ 2 files changed, 21 insertions(+)
kernel/sched.c +3 -0
@@ -267,6 +267,8 @@ struct rt_rq {int rt_load_balance_idx;struct list_head *rt_load_balance_head, *rt_load_balance_curr;unsigned long rt_nr_running; +/* highest queued rt task prio */ +int highest_prio; };/*
@@ -6776,6 +6778,7 @@ void __init sched_init(void) rq->cpu = i; rq->migration_thread =NULL ;INIT_LIST_HEAD (&rq->migration_queue); + rq->rt.highest_prio =MAX_RT_PRIO ;#endif atomic_set (&rq->nr_iowait,0 );
kernel/sched_rt.c +18 -0
@@ -29,6 +29,10 @@ static inline void inc_rt_tasks(struct t {WARN_ON (!rt_task (p)); rq->rt.rt_nr_running++; +#ifdef CONFIG_SMP +if (p->prio < rq->rt.highest_prio) + rq->rt.highest_prio = p->prio; +#endif /* CONFIG_SMP */ }static inline void dec_rt_tasks (struct task_struct *p,struct rq *rq)
@@ -36,6 +40,20 @@ static inline void dec_rt_tasks(struct tWARN_ON (!rt_task (p));WARN_ON (!rq->rt.rt_nr_running); rq->rt.rt_nr_running--; +#ifdef CONFIG_SMP +if (rq->rt.rt_nr_running) { +struct rt_prio_array *array; + +WARN_ON (p->prio < rq->rt.highest_prio); +if (p->prio == rq->rt.highest_prio) { +/* recalculate */ + array = &rq->rt.active; + rq->rt.highest_prio = +sched_find_first_bit (array->bitmap); + }/* otherwise leave rq->highest prio alone */ + }else + rq->rt.highest_prio =MAX_RT_PRIO ; +#endif /* CONFIG_SMP */ }static void enqueue_task_rt (struct rq *rq,struct task_struct *p,int wakeup)
Steven Rostedt
reviewerPATCH v3 3/17 push RT tasks
In reply to Steven RostedtThis patch adds an algorithm to push extra RT tasks off a run queue to other CPU runqueues.
When more than one RT task is added to a run queue, this algorithm takes an assertive approach to push the RT tasks that are not running onto other run queues that have lower priority. The way this works is that the highest RT task that is not running is looked at and we examine the runqueues on the CPUS for that tasks affinity mask. We find the runqueue with the lowest prio in the CPU affinity of the picked task, and if it is lower in prio than the picked task, we push the task onto that CPU runqueue.
We continue pushing RT tasks off the current runqueue until we don't push any more. The algorithm stops when the next highest RT task can't preempt any other processes on other CPUS.
TODO: The algorithm may stop when there are still RT tasks that can be
migrated. Specifically, if the highest non running RT task CPU affinity is restricted to CPUs that are running higher priority tasks, there may be a lower priority task queued that has an affinity with a CPU that is running a lower priority task that it could be migrated to. This patch set does not address this issue.
Note: checkpatch reveals two over 80 character instances. I'm not sure
that breaking them up will help visually, so I left them as is.
--- kernel/sched.c | 8 + kernel/sched_rt.c | 223 +++++++++++++++++++++++++++++++++++++++++++++++++++++- 2 files changed, 229 insertions(+), 2 deletions(-)
kernel/sched.c +7 -1
@@ -1877,6 +1877,8 @@ static void finish_task_switch(struct rq prev_state = prev->state;finish_arch_switch (prev);finish_lock_switch (rq, prev); +schedule_tail_balance_rt (rq); +fire_sched_in_preempt_notifiers (current);if (mm)mmdrop (mm);
@@ -2110,11 +2112,13 @@ static void double_rq_unlock(struct rq */* * double_lock_balance - lock the busiest runqueue, this_rq is locked already. */ -static void double_lock_balance (struct rq *this_rq,struct rq *busiest) +static int double_lock_balance (struct rq *this_rq,struct rq *busiest) __releases(this_rq->lock) __acquires(busiest->lock) __acquires(this_rq->lock) { +int ret =0 ; +if (unlikely (!irqs_disabled ())) {/* printk() doesn't work good under rq->lock */ spin_unlock (&this_rq->lock);
@@ -2125,9 +2129,11 @@ static void double_lock_balance(struct rspin_unlock (&this_rq->lock);spin_lock (&busiest->lock);spin_lock (&this_rq->lock); + ret =1 ; }else spin_lock (&busiest->lock); } +return ret; }/*
kernel/sched_rt.c +222 -1
235 lines not on this page · raw message
Steven Rostedt
reviewerPATCH v3 4/17 RT overloaded runqueues accounting
In reply to Steven RostedtThis patch adds an RT overload accounting system. When a runqueue has more than one RT task queued, it is marked as overloaded. That is that it is a candidate to have RT tasks pulled from it.
--- kernel/sched_rt.c | 36 ++++++++++++++++++++++++++++++++++++ 1 file changed, 36 insertions(+)
kernel/sched_rt.c +36 -0
@@ -3,6 +3,38 @@* policies) */ +#ifdef CONFIG_SMP +static cpumask_t rt_overload_mask; +static atomic_t rto_count; +static inline int rt_overloaded (void ) +{ +return atomic_read (&rto_count); +} +static inline cpumask_t *rt_overload (void ) +{ +return &rt_overload_mask; +} +static inline void rt_set_overload (struct rq *rq) +{ +cpu_set (rq->cpu, rt_overload_mask); +/* +* Make sure the mask is visible before we set +* the overload count. That is checked to determine +* if we should look at the mask. It would be a shame +* if we looked at the mask, but the mask was not +* updated yet. +*/ +wmb (); +atomic_inc (&rto_count); +} +static inline void rt_clear_overload (struct rq *rq) +{ +/* the order here really doesn't matter */ +atomic_dec (&rto_count); +cpu_clear (rq->cpu, rt_overload_mask); +} +#endif /* CONFIG_SMP */ +/* * Update the current task's runtime statistics. Skip current tasks that * are not in our scheduling class.
@@ -32,6 +64,8 @@ static inline void inc_rt_tasks(struct t#ifdef CONFIG_SMP if (p->prio < rq->rt.highest_prio) rq->rt.highest_prio = p->prio; +if (rq->rt.rt_nr_running >1 ) +rt_set_overload (rq);#endif /* CONFIG_SMP */ }
@@ -53,6 +87,8 @@ static inline void dec_rt_tasks(struct t } /* otherwise leave rq->highest prio alone */ }else rq->rt.highest_prio =MAX_RT_PRIO ; +if (rq->rt.rt_nr_running <2 ) +rt_clear_overload (rq);#endif /* CONFIG_SMP */ }
Steven Rostedt
reviewerPATCH v3 5/17 pull RT tasks
In reply to Steven RostedtThis 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.
--- kernel/sched.c | 2 kernel/sched_rt.c | 196 ++++++++++++++++++++++++++++++++++++++++++++++++++---- 2 files changed, 187 insertions(+), 11 deletions(-)
kernel/sched.c +2 -0
@@ -3646,6 +3646,8 @@ need_resched_nonpreemptible: switch_count = &prev->nvcsw; } +schedule_balance_rt (rq, prev); +if (unlikely (!rq->nr_running))idle_balance (cpu, rq);
kernel/sched_rt.c +185 -11
251 lines not on this page · raw message
Steven Rostedt
reviewerPATCH v3 6/17 wake up balance RT
In reply to Steven RostedtThis patch adds pushing of overloaded RT tasks from a runqueue that is having tasks (most likely RT tasks) added to the run queue.
TODO: We don't cover the case of waking of new RT tasks (yet).
--- kernel/sched.c | 3 +++ kernel/sched_rt.c | 10 ++++++++++ 2 files changed, 13 insertions(+)
kernel/sched_rt.c +10 -0
@@ -562,6 +562,15 @@ static void schedule_tail_balance_rt(str } } + +static void wakeup_balance_rt (struct rq *rq,struct task_struct *p) +{ +if (unlikely (rt_task (p)) && + !task_running (rq, p) && + (p->prio >= rq->curr->prio)) +push_rt_tasks (rq); +} +/* * Load-balancing iterator. Note: while the runqueue stays locked * during the whole iteration, the current task might be
@@ -669,6 +678,7 @@ move_one_task_rt(struct rq *this_rq, int#else /* CONFIG_SMP */ # define schedule_tail_balance_rt (rq) do { } while (0)# define schedule_balance_rt (rq, prev) do { } while (0) +# define wakeup_balance_rt (rq, p) do { } while (0)#endif /* CONFIG_SMP */ static void task_tick_rt (struct rq *rq,struct task_struct *p)
kernel/sched.c +3 -0
@@ -22,6 +22,8 @@* by Peter Williams * 2007-05-06 Interactivity improvements to CFS by Mike Galbraith * 2007-07-01 Group scheduling enhancements by Srivatsa Vaddagiri +* 2007-10-22 RT overload balancing by Steven Rostedt +* (with thanks to Gregory Haskins) */ #include <linux/mm.h>
@@ -1635,6 +1637,7 @@ out_activate: out_running: p->state =TASK_RUNNING ; +wakeup_balance_rt (rq, p); out:task_rq_unlock (rq, &flags);
Steven Rostedt
reviewerPATCH v3 7/17 disable CFS RT load balancing.
In reply to Steven RostedtSince we now take an active approach to load balancing, we don't need to balance RT tasks via CFS. In fact, this code was found to pull RT tasks away from CPUS that the active movement performed, resulting in large latencies.
--- kernel/sched_rt.c | 95 ++---------------------------------------------------- 1 file changed, 4 insertions(+), 91 deletions(-)
kernel/sched_rt.c +4 -91
@@ -571,109 +571,22 @@ static void wakeup_balance_rt(struct rq push_rt_tasks(rq); } -/* -* Load-balancing iterator. Note: while the runqueue stays locked -* during the whole iteration, the current task might be -* dequeued so the iterator has to be dequeue-safe. Here we -* achieve that by always pre-iterating before returning -* the current task: -*/ -static struct task_struct *load_balance_start_rt (void *arg) -{ -struct rq *rq = arg; -struct rt_prio_array *array = &rq->rt.active; -struct list_head *head, *curr; -struct task_struct *p; -int idx; - - idx =sched_find_first_bit (array->bitmap); -if (idx >=MAX_RT_PRIO ) -return NULL ; - - head = array->queue + idx; - curr = head->prev; - - p = list_entry(curr, struct task_struct, run_list); - - curr = curr->prev; - - rq->rt.rt_load_balance_idx = idx; - rq->rt.rt_load_balance_head = head; - rq->rt.rt_load_balance_curr = curr; - -return p; -} - -static struct task_struct *load_balance_next_rt (void *arg) -{ -struct rq *rq = arg; -struct rt_prio_array *array = &rq->rt.active; -struct list_head *head, *curr; -struct task_struct *p; -int idx; - - idx = rq->rt.rt_load_balance_idx; - head = rq->rt.rt_load_balance_head; - curr = rq->rt.rt_load_balance_curr; - -/* -* If we arrived back to the head again then -* iterate to the next queue (if any): -*/ -if (unlikely (head == curr)) { -int next_idx =find_next_bit (array->bitmap,MAX_RT_PRIO , idx+1 ); - -if (next_idx >=MAX_RT_PRIO ) -return NULL ; - - idx = next_idx; - head = array->queue + idx; - curr = head->prev; - - rq->rt.rt_load_balance_idx = idx; - rq->rt.rt_load_balance_head = head; - } - - p = list_entry(curr, struct task_struct, run_list); - - curr = curr->prev; - - rq->rt.rt_load_balance_curr = curr; - -return p; -} -static unsigned long load_balance_rt (struct rq *this_rq,int this_cpu,struct rq *busiest,unsigned long max_load_move,struct sched_domain *sd,enum cpu_idle_type idle,int *all_pinned,int *this_best_prio) { -struct rq_iterator rt_rq_iterator; - - rt_rq_iterator.start = load_balance_start_rt; - rt_rq_iterator.next = load_balance_next_rt; -/* pass 'busiest' rq argument into -* load_balance_[start|next]_rt iterators -*/ - rt_rq_iterator.arg = busiest; - -return balance_tasks (this_rq, this_cpu, busiest, max_load_move, sd, - idle, all_pinned, this_best_prio, &rt_rq_iterator); +/* don't touch RT tasks */ +return 0 ; }static int move_one_task_rt (struct rq *this_rq,int this_cpu,struct rq *busiest,struct sched_domain *sd,enum cpu_idle_type idle) { -struct rq_iterator rt_rq_iterator; - - rt_rq_iterator.start = load_balance_start_rt; - rt_rq_iterator.next = load_balance_next_rt; - rt_rq_iterator.arg = busiest; - -return iter_move_one_task (this_rq, this_cpu, busiest, sd, idle, - &rt_rq_iterator); +/* don't touch RT tasks */ +return 0 ; }#else /* CONFIG_SMP */ # define schedule_tail_balance_rt (rq) do { } while (0)
Steven Rostedt
reviewerPATCH v3 8/17 Cache cpus_allowed weight for optimizing migration
In reply to Steven RostedtFrom: Gregory Haskins <[email protected]>
Some RT tasks (particularly kthreads) are bound to one specific CPU. It is fairly common for two or more bound tasks to get queued up at the same time. Consider, for instance, softirq_timer and softirq_sched. A timer goes off in an ISR which schedules softirq_thread to run at RT50. Then the timer handler determines that it's time to smp-rebalance the system so it schedules softirq_sched to run. So we are in a situation where we have two RT50 tasks queued, and the system will go into rt-overload condition to request other CPUs for help.
This causes two problems in the current code:
1) If a high-priority bound task and a low-priority unbounded task queue up behind the running task, we will fail to ever relocate the unbounded task because we terminate the search on the first unmovable task.
2) We spend precious futile cycles in the fast-path trying to pull overloaded tasks over. It is therefore optimial to strive to avoid the overhead all together if we can cheaply detect the condition before overload even occurs.
This patch tries to achieve this optimization by utilizing the hamming weight of the task->cpus_allowed mask. A weight of 1 indicates that the task cannot be migrated. We will then utilize this information to skip non-migratable tasks and to eliminate uncessary rebalance attempts.
We introduce a per-rq variable to count the number of migratable tasks that are currently running. We only go into overload if we have more than one rt task, AND at least one of them is migratable.
In addition, we introduce a per-task variable to cache the cpus_allowed weight, since the hamming calculation is probably relatively expensive. We only update the cached value when the mask is updated which should be relatively infrequent, especially compared to scheduling frequency in the fast path.
---
include/linux/init_task.h | 1 include/linux/sched.h | 2 + kernel/fork.c | 1 kernel/sched.c | 9 +++++++- kernel/sched_rt.c | 50 +++++++++++++++++++++++++++++++++++++++++----- 5 files changed, 57 insertions(+), 6 deletions(-)
include/linux/sched.h +2 -0
@@ -843,6 +843,7 @@ struct sched_class {void (*set_curr_task) (struct rq *rq);void (*task_tick) (struct rq *rq,struct task_struct *p);void (*task_new) (struct rq *rq,struct task_struct *p); +void (*set_cpus_allowed)(struct task_struct *p,cpumask_t newmask); };struct load_weight {
@@ -952,6 +953,7 @@ struct task_struct {unsigned int policy;cpumask_t cpus_allowed; +int nr_cpus_allowed;unsigned int time_slice;#if defined(CONFIG_SCHEDSTATS ) || defined(CONFIG_TASK_DELAY_ACCT )
kernel/fork.c +1 -0
@@ -1237,6 +1237,7 @@ static struct task_struct *copy_process(* parent's CPU). This avoids alot of nasty races. */ p->cpus_allowed = current->cpus_allowed; + p->nr_cpus_allowed = current->nr_cpus_allowed;if (unlikely (!cpu_isset (task_cpu (p), p->cpus_allowed) || !cpu_online (task_cpu (p))))set_task_cpu (p,smp_processor_id ());
kernel/sched.c +8 -1
@@ -269,6 +269,7 @@ struct rt_rq {int rt_load_balance_idx;struct list_head *rt_load_balance_head, *rt_load_balance_curr;unsigned long rt_nr_running; +unsigned long rt_nr_migratory;/* highest queued rt task prio */ int highest_prio; };
@@ -5070,7 +5071,13 @@ int set_cpus_allowed(struct task_struct goto out; } - p->cpus_allowed = new_mask; +if (p->sched_class->set_cpus_allowed) + p->sched_class->set_cpus_allowed (p, new_mask); +else { + p->cpus_allowed = new_mask; + p->nr_cpus_allowed =cpus_weight (new_mask); + } +/* Can the task run on the task's current CPU? If so, we're done */ if (cpu_isset (task_cpu (p), new_mask)) goto out;
kernel/sched_rt.c +45 -5
86 lines not on this page · raw message
include/linux/init_task.h +1 -0
@@ -130,6 +130,7 @@ extern struct group_info init_groups; .normal_prio = MAX_PRIO-20, \ .policy = SCHED_NORMAL, \ .cpus_allowed = CPU_MASK_ALL, \ + .nr_cpus_allowed = NR_CPUS, \ .mm = NULL, \ .active_mm = &init_mm, \ .run_list = LIST_HEAD_INIT(tsk.run_list), \
Steven Rostedt
reviewerPATCH v3 9/17 Consistency cleanup for this_rq usage
In reply to Steven RostedtFrom: Gregory Haskins <[email protected]>
"this_rq" is normally used to denote the RQ on the current cpu (i.e. "cpu_rq(this_cpu)"). So clean up the usage of this_rq to be more consistent with the rest of the code.
---
kernel/sched_rt.c | 44 ++++++++++++++++++++++---------------------- 1 file changed, 22 insertions(+), 22 deletions(-)
kernel/sched_rt.c +22 -22
@@ -253,7 +253,7 @@ static struct task_struct *pick_next_hig/* Will lock the rq it finds */ static struct rq *find_lock_lowest_rq (struct task_struct *task, -struct rq *this_rq) +struct rq *rq) {struct rq *lowest_rq =NULL ;cpumask_t cpu_mask;
@@ -267,21 +267,21 @@ static struct rq *find_lock_lowest_rq(st* Scan each rq for the lowest prio. */ for_each_cpu_mask (cpu, cpu_mask) { -struct rq *rq = &per_cpu (runqueues, cpu); +struct rq *curr_rq = &per_cpu (runqueues, cpu); -if (cpu == this_rq->cpu) +if (cpu == rq->cpu)continue ;/* We look for lowest RT prio or non-rt CPU */ -if (rq->rt.highest_prio >=MAX_RT_PRIO ) { - lowest_rq = rq; +if (curr_rq->rt.highest_prio >=MAX_RT_PRIO ) { + lowest_rq = curr_rq;break ; }/* no locking for now */ -if (rq->rt.highest_prio > task->prio && - (!lowest_rq || rq->rt.highest_prio > lowest_rq->rt.highest_prio)) { - lowest_rq = rq; +if (curr_rq->rt.highest_prio > task->prio && + (!lowest_rq || curr_rq->rt.highest_prio > lowest_rq->rt.highest_prio)) { + lowest_rq = curr_rq; } }
@@ -289,16 +289,16 @@ static struct rq *find_lock_lowest_rq(stbreak ;/* if the prio of this runqueue changed, try again */ -if (double_lock_balance (this_rq, lowest_rq)) { +if (double_lock_balance (rq, lowest_rq)) {/* * We had to unlock the run queue. In * the mean time, task could have * migrated already or had its affinity changed. * Also make sure that it wasn't scheduled on its rq. */ -if (unlikely (task_rq (task) != this_rq || +if (unlikely (task_rq (task) != rq || !cpu_isset (lowest_rq->cpu, task->cpus_allowed) || -task_running (this_rq, task) || +task_running (rq, task) || !task->se.on_rq)) {spin_unlock (&lowest_rq->lock); lowest_rq =NULL ;
@@ -323,21 +323,21 @@ static struct rq *find_lock_lowest_rq(st* running task can migrate over to a CPU that is running a task * of lesser priority. */ -static int push_rt_task (struct rq *this_rq) +static int push_rt_task (struct rq *rq) {struct task_struct *next_task;struct rq *lowest_rq;int ret =0 ;int paranoid =RT_MAX_TRIES ; -assert_spin_locked (&this_rq->lock); +assert_spin_locked (&rq->lock); - next_task =pick_next_highest_task_rt (this_rq,-1 ); + next_task =pick_next_highest_task_rt (rq,-1 );if (!next_task)return 0 ; retry: -if (unlikely (next_task == this_rq->curr)) { +if (unlikely (next_task == rq->curr)) {WARN_ON (1 );return 0 ; }
@@ -347,24 +347,24 @@ static int push_rt_task(struct rq *this_* higher priority than current. If that's the case * just reschedule current. */ -if (unlikely (next_task->prio < this_rq->curr->prio)) { -resched_task (this_rq->curr); +if (unlikely (next_task->prio < rq->curr->prio)) { +resched_task (rq->curr);return 0 ; } -/* We might release this_rq lock */ +/* We might release rq lock */ get_task_struct (next_task);/* find_lock_lowest_rq locks the rq if found */ - lowest_rq =find_lock_lowest_rq (next_task, this_rq); + lowest_rq =find_lock_lowest_rq (next_task, rq);if (!lowest_rq) {struct task_struct *task;/* -* find lock_lowest_rq releases this_rq->lock +* find lock_lowest_rq releases rq->lock * so it is possible that next_task has changed. * If it has, then try again. */ - task =pick_next_highest_task_rt (this_rq,-1 ); + task =pick_next_highest_task_rt (rq,-1 );if (unlikely (task != next_task) && task && paranoid--) {put_task_struct (next_task); next_task = task;
@@ -375,7 +375,7 @@ static int push_rt_task(struct rq *this_assert_spin_locked (&lowest_rq->lock); -deactivate_task (this_rq, next_task,0 ); +deactivate_task (rq, next_task,0 );set_task_cpu (next_task, lowest_rq->cpu);activate_task (lowest_rq, next_task,0 );
Steven Rostedt
reviewerPATCH v3 10/17 Remove some CFS specific code from the wakeup path of RT tasks
In reply to Steven RostedtFrom: Gregory Haskins <[email protected]>
The current wake-up code path tries to determine if it can optimize the wake-up to "this_cpu" by computing load calculations. The problem is that these calculations are only relevant to CFS tasks where load is king. For RT tasks, priority is king. So the load calculation is completely wasted bandwidth.
Therefore, we create a new sched_class interface to help with pre-wakeup routing decisions and move the load calculation as a function of CFS task's class.
---
include/linux/sched.h | 1 kernel/sched.c | 144 +++--------------------------------------------- kernel/sched_fair.c | 132 ++++++++++++++++++++++++++++++++++++++++++++ kernel/sched_idletask.c | 9 +++ kernel/sched_rt.c | 8 ++ 5 files changed, 159 insertions(+), 135 deletions(-)
include/linux/sched.h +1 -0
@@ -823,6 +823,7 @@ struct sched_class {void (*enqueue_task) (struct rq *rq,struct task_struct *p,int wakeup);void (*dequeue_task) (struct rq *rq,struct task_struct *p,int sleep);void (*yield_task) (struct rq *rq); +int (*select_task_rq)(struct task_struct *p,int sync);void (*check_preempt_curr) (struct rq *rq,struct task_struct *p);
kernel/sched.c +9 -135
178 lines not on this page · raw message
kernel/sched_fair.c +132 -0
144 lines not on this page · raw message
kernel/sched_idletask.c +9 -0
@@ -5,6 +5,12 @@* handled in sched_fair.c) */ +#ifdef CONFIG_SMP +static int select_task_rq_idle (struct task_struct *p,int sync) +{ +return task_cpu (p);/* IDLE tasks as never migrated */ +} +#endif /* CONFIG_SMP */ /* * Idle tasks are unconditionally rescheduled: */
@@ -72,6 +78,9 @@ const struct sched_class idle_sched_clas/* dequeue is not valid, we print a debug message there: */ .dequeue_task = dequeue_task_idle, +#ifdef CONFIG_SMP + .select_task_rq = select_task_rq_idle, +#endif /* CONFIG_SMP */ .check_preempt_curr = check_preempt_curr_idle,
kernel/sched_rt.c +8 -0
@@ -41,6 +41,11 @@ static void update_rt_migration(struct r else rt_clear_overload(rq); } + +static int select_task_rq_rt (struct task_struct *p,int sync) +{ +return task_cpu (p); +}#endif /* CONFIG_SMP */ /*
@@ -669,6 +674,9 @@ const struct sched_class rt_sched_class .enqueue_task = enqueue_task_rt, .dequeue_task = dequeue_task_rt, .yield_task = yield_task_rt, +#ifdef CONFIG_SMP + .select_task_rq = select_task_rq_rt, +#endif /* CONFIG_SMP */ .check_preempt_curr = check_preempt_curr_rt,
Re: [PATCH v3 10/17] Remove some CFS specific code from the wakeup path of RT tasks
Quoted 1 line
Quoted 1 line
Quoted 1 line
On Sat, Nov 17, 2007 at 1:21 AM, in message
<[email protected]>, Steven Rostedt <[email protected]>
Quoted 25 lines · wrote:
(quoted diff) +0
-25-/* - * wake_idle() will wake a task on an idle cpu if task->cpu is - * not idle and an idle cpu is available. The span of cpus to - * search starts with cpus closest then further out as needed, - * so we always favor a closer, idle cpu. - * - * Returns the CPU we should wake onto. - */ -#if defined(ARCH_HAS_SCHED_WAKE_IDLE) -static int wake_idle(int cpu, struct task_struct *p) -{ - cpumask_t tmp; - struct sched_domain *sd; - int i; - - /* - * If it is idle, then it is the best cpu to run this task. - * - * This cpu is also the best, if it has more than one task already. - * Siblings must be also busy(in most cases) as they didn't already - * pickup the extra load from this cpu and hence we need not check - * sibling runqueue info. This will avoid the checks and cache miss - * penalities associated with that. - */ - if (idle_cpu(cpu) || cpu_rq(cpu)->nr_running > 1)
Review
Quoted 10 lines
(quoted diff) +0
-10- return cpu; - - for_each_domain(cpu, sd) { - if (sd->flags & SD_WAKE_IDLE) { - cpus_and(tmp, sd->span, p->cpus_allowed); - for_each_cpu_mask(i, tmp) { - if (idle_cpu(i)) { - if (i != task_cpu(p)) { - schedstat_inc(p, - se.nr_wakeups_idle);
^^^^^^^^^^^^^^^^^^^^^
[...]
Quoted 28 lines
kernel/sched_fair.c +22
-0@@ -564,6 +564,137 @@ dequeue_entity(struct cfs_rq *cfs_rq, st }/* +* wake_idle() will wake a task on an idle cpu if task->cpu is +* not idle and an idle cpu is available. The span of cpus to +* search starts with cpus closest then further out as needed, +* so we always favor a closer, idle cpu. +* +* Returns the CPU we should wake onto. +*/ +#if defined(ARCH_HAS_SCHED_WAKE_IDLE ) +static int wake_idle (int cpu,struct task_struct *p) +{ +cpumask_t tmp; +struct sched_domain *sd; +int i; + +/* +* If it is idle, then it is the best cpu to run this task. +* +* This cpu is also the best, if it has more than one task already. +* Siblings must be also busy(in most cases) as they didn't already +* pickup the extra load from this cpu and hence we need not check +* sibling runqueue info. This will avoid the checks and cache miss +* penalities associated with that.
kernel/sched_fair.c dequeue_entity(struct cfs_rq *cfs_rq, st · line 598
Quoted 10 lines
kernel/sched_fair.c +10
-0+*/ +if (idle_cpu (cpu) ||cpu_rq (cpu)->nr_running >1 ) +return cpu; + +for_each_domain (cpu, sd) { +if (sd->flags &SD_WAKE_IDLE ) { +cpus_and (tmp, sd->span, p->cpus_allowed); +for_each_cpu_mask (i, tmp) { +if (idle_cpu (i)) +return i;
^^^^^^^^^^^^^^^^
Looks like some stuff that was added in 24 was inadvertently lost in the move when you merged the patches up from 23.1-rt11. The attached patch is updated to move the new logic as well.
Regards,
-Greg
RT: Remove some CFS specific code from the wakeup path of RT tasks
From: Gregory Haskins <[email protected]>
The current wake-up code path tries to determine if it can optimize the wake-up to "this_cpu" by computing load calculations. The problem is that these calculations are only relevant to CFS tasks where load is king. For RT tasks, priority is king. So the load calculation is completely wasted bandwidth.
Therefore, we create a new sched_class interface to help with pre-wakeup routing decisions and move the load calculation as a function of CFS task's class.
---
include/linux/sched.h | 1 kernel/sched.c | 167 ++++++++--------------------------------------- kernel/sched_fair.c | 148 ++++++++++++++++++++++++++++++++++++++++++ kernel/sched_idletask.c | 9 +++ kernel/sched_rt.c | 10 +++ 5 files changed, 195 insertions(+), 140 deletions(-)
include/linux/sched.h +1 -0
@@ -823,6 +823,7 @@ struct sched_class {void (*enqueue_task) (struct rq *rq,struct task_struct *p,int wakeup);void (*dequeue_task) (struct rq *rq,struct task_struct *p,int sleep);void (*yield_task) (struct rq *rq); +int (*select_task_rq)(struct task_struct *p,int sync);void (*check_preempt_curr) (struct rq *rq,struct task_struct *p);
kernel/sched.c +27 -140
209 lines not on this page · raw message
kernel/sched_fair.c +148 -0
160 lines not on this page · raw message
kernel/sched_idletask.c +9 -0
@@ -5,6 +5,12 @@* handled in sched_fair.c) */ +#ifdef CONFIG_SMP +static int select_task_rq_idle (struct task_struct *p,int sync) +{ +return task_cpu (p);/* IDLE tasks as never migrated */ +} +#endif /* CONFIG_SMP */ /* * Idle tasks are unconditionally rescheduled: */
@@ -72,6 +78,9 @@ const struct sched_class idle_sched_class = {/* dequeue is not valid, we print a debug message there: */ .dequeue_task = dequeue_task_idle, +#ifdef CONFIG_SMP + .select_task_rq = select_task_rq_idle, +#endif /* CONFIG_SMP */ .check_preempt_curr = check_preempt_curr_idle,
kernel/sched_rt.c +10 -0
@@ -147,6 +147,13 @@ yield_task_rt(struct rq *rq)requeue_task_rt (rq, rq->curr); } +#ifdef CONFIG_SMP +static int select_task_rq_rt (struct task_struct *p,int sync) +{ +return task_cpu (p); +} +#endif /* CONFIG_SMP */ +/* * Preempt the current task with a newly woken task if needed: */
@@ -669,6 +676,9 @@ const struct sched_class rt_sched_class = { .enqueue_task = enqueue_task_rt, .dequeue_task = dequeue_task_rt, .yield_task = yield_task_rt, +#ifdef CONFIG_SMP + .select_task_rq = select_task_rq_rt, +#endif /* CONFIG_SMP */ .check_preempt_curr = check_preempt_curr_rt,
Steven Rostedt
reviewerRe: [PATCH v3 10/17] Remove some CFS specific code from the wakeup path of RT tasks
Quoted 16 lines · Gregory Haskins
Quoted 1 line
Quoted 1 line
Quoted 1 line
On Sat, Nov 17, 2007 at 1:21 AM, in message
<[email protected]>, Steven Rostedt <[email protected]>
kernel/sched_fair.c static void yield_task_fair(struct rq *rq) · line 868
Quoted 10 lines · wrote:
kernel/sched_fair.c +10
-0+*/ +if (idle_cpu (cpu) ||cpu_rq (cpu)->nr_running >1 ) +return cpu; + +for_each_domain (cpu, sd) { +if (sd->flags &SD_WAKE_IDLE ) { +cpus_and (tmp, sd->span, p->cpus_allowed); +for_each_cpu_mask (i, tmp) { +if (idle_cpu (i)) +return i;^^^^^^^^^^^^^^^^
Quoted 2 lines
Looks like some stuff that was added in 24 was inadvertently lost in the move when you merged the patches up from 23.1-rt11. The attached patch is updated to move the new logic as well.
Doh! Good catch. Will rework on Monday.
-- Steve
Steven Rostedt
reviewerPATCH v3 11/17 RT: Break out the search function
In reply to Steven RostedtFrom: Gregory Haskins <[email protected]>
Isolate the search logic into a function so that it can be used later in places other than find_locked_lowest_rq().
---
kernel/sched_rt.c | 62 ++++++++++++++++++++++++++++++++---------------------- 1 file changed, 37 insertions(+), 25 deletions(-)
kernel/sched_rt.c +37 -25
@@ -256,43 +256,55 @@ static struct task_struct *pick_next_higreturn next; } -/* Will lock the rq it finds */ -static struct rq *find_lock_lowest_rq (struct task_struct *task, -struct rq *rq) +static int find_lowest_rq (struct task_struct *task) { -struct rq *lowest_rq =NULL ; -cpumask_t cpu_mask;int cpu; -int tries; +cpumask_t cpu_mask; +struct rq *lowest_rq =NULL ;cpus_and (cpu_mask, cpu_online_map, task->cpus_allowed); -for (tries =0 ; tries <RT_MAX_TRIES ; tries++) { -/* -* Scan each rq for the lowest prio. -*/ -for_each_cpu_mask (cpu, cpu_mask) { -struct rq *curr_rq = &per_cpu (runqueues, cpu); +/* +* Scan each rq for the lowest prio. +*/ +for_each_cpu_mask (cpu, cpu_mask) { +struct rq *rq =cpu_rq (cpu); -if (cpu == rq->cpu) -continue ; +if (cpu == rq->cpu) +continue ; -/* We look for lowest RT prio or non-rt CPU */ -if (curr_rq->rt.highest_prio >=MAX_RT_PRIO ) { - lowest_rq = curr_rq; -break ; - } +/* We look for lowest RT prio or non-rt CPU */ +if (rq->rt.highest_prio >=MAX_RT_PRIO ) { + lowest_rq = rq; +break ; + } -/* no locking for now */ -if (curr_rq->rt.highest_prio > task->prio && - (!lowest_rq || curr_rq->rt.highest_prio > lowest_rq->rt.highest_prio)) { - lowest_rq = curr_rq; - } +/* no locking for now */ +if (rq->rt.highest_prio > task->prio && + (!lowest_rq || rq->rt.highest_prio > lowest_rq->rt.highest_prio)) { + lowest_rq = rq; } + } + +return lowest_rq ? lowest_rq->cpu :-1 ; +} + +/* Will lock the rq it finds */ +static struct rq *find_lock_lowest_rq (struct task_struct *task, +struct rq *rq) +{ +struct rq *lowest_rq =NULL ; +int cpu; +int tries; + +for (tries =0 ; tries <RT_MAX_TRIES ; tries++) { + cpu =find_lowest_rq (task); -if (!lowest_rq) +if (cpu ==-1 )break ; + lowest_rq =cpu_rq (cpu); +/* if the prio of this runqueue changed, try again */ if (double_lock_balance (rq, lowest_rq)) {/*
Steven Rostedt
reviewerPATCH v3 12/17 Allow current_cpu to be included in search
In reply to Steven RostedtFrom: Gregory Haskins <[email protected]>
It doesn't hurt if we allow the current CPU to be included in the search. We will just simply skip it later if the current CPU turns out to be the lowest.
We will use this later in the series
---
kernel/sched_rt.c | 5 +---- 1 file changed, 1 insertion(+), 4 deletions(-)
kernel/sched_rt.c +1 -4
@@ -270,9 +270,6 @@ static int find_lowest_rq(struct task_stfor_each_cpu_mask (cpu, cpu_mask) {struct rq *rq =cpu_rq (cpu); -if (cpu == rq->cpu) -continue ; -/* We look for lowest RT prio or non-rt CPU */ if (rq->rt.highest_prio >=MAX_RT_PRIO ) { lowest_rq = rq;
@@ -300,7 +297,7 @@ static struct rq *find_lock_lowest_rq(stfor (tries =0 ; tries <RT_MAX_TRIES ; tries++) { cpu =find_lowest_rq (task); -if (cpu ==-1 ) +if ((cpu ==-1 ) || (cpu == rq->cpu))break ; lowest_rq =cpu_rq (cpu);
Steven Rostedt
reviewerPATCH v3 13/17 RT: Pre-route RT tasks on wakeup
In reply to Steven RostedtFrom: Gregory Haskins <[email protected]>
In the original patch series that Steven Rostedt and I worked on together, we both took different approaches to low-priority wakeup path. I utilized "pre-routing" (push the task away to a less important RQ before activating) approach, while Steve utilized a "post-routing" approach. The advantage of my approach is that you avoid the overhead of a wasted activate/deactivate cycle and peripherally related burdens. The advantage of Steve's method is that it neatly solves an issue preventing a "pull" optimization from being deployed.
In the end, we ended up deploying Steve's idea. But it later dawned on me that we could get the best of both worlds by deploying both ideas together, albeit slightly modified.
The idea is simple: Use a "light-weight" lookup for pre-routing, since we only need to approximate a good home for the task. And we also retain the post-routing push logic to clean up any inaccuracies caused by a condition of "priority mistargeting" caused by the lightweight lookup. Most of the time, the pre-routing should work and yield lower overhead. In the cases where it doesnt, the post-router will bat cleanup.
---
kernel/sched_rt.c | 19 +++++++++++++++++++ 1 file changed, 19 insertions(+)
kernel/sched_rt.c +19 -0
@@ -42,8 +42,27 @@ static void update_rt_migration(struct r rt_clear_overload(rq); } +static int find_lowest_rq (struct task_struct *task); +static int select_task_rq_rt (struct task_struct *p,int sync) { +struct rq *rq =task_rq (p); + +/* +* If the task will not preempt the RQ, try to find a better RQ +* before we even activate the task +*/ +if ((p->prio >= rq->rt.highest_prio) + && (p->nr_cpus_allowed >1 )) { +int cpu =find_lowest_rq (p); + +return (cpu ==-1 ) ?task_cpu (p) : cpu; + } + +/* +* Otherwise, just let it ride on the affined RQ and the +* post-schedule router will push the preempted task away +*/ return task_cpu (p); }#endif /* CONFIG_SMP */
Steven Rostedt
reviewerPATCH v3 14/17 Optimize our cpu selection based on topology
In reply to Steven RostedtFrom: Gregory Haskins <[email protected]>
The current code base assumes a relatively flat CPU/core topology and will route RT tasks to any CPU fairly equally. In the real world, there are various toplogies and affinities that govern where a task is best suited to run with the smallest amount of overhead. NUMA and multi-core CPUs are prime examples of topologies that can impact cache performance.
Fortunately, linux is already structured to represent these topologies via the sched_domains interface. So we change our RT router to consult a combination of topology and affinity policy to best place tasks during migration.
---
kernel/sched.c | 1 kernel/sched_rt.c | 99 +++++++++++++++++++++++++++++++++++++++++++++++------- 2 files changed, 88 insertions(+), 12 deletions(-)
kernel/sched.c +1 -0
@@ -24,6 +24,7 @@* 2007-07-01 Group scheduling enhancements by Srivatsa Vaddagiri * 2007-10-22 RT overload balancing by Steven Rostedt * (with thanks to Gregory Haskins) +* 2007-11-05 RT migration/wakeup tuning by Gregory Haskins */ #include <linux/mm.h>
kernel/sched_rt.c +87 -12
121 lines not on this page · raw message
Steven Rostedt
reviewerPATCH v3 15/17 RT: Optimize rebalancing
In reply to Steven RostedtFrom: Gregory Haskins <[email protected]>
We have logic to detect whether the system has migratable tasks, but we are not using it when deciding whether to push tasks away. So we add support for considering this new information.
---
kernel/sched.c | 2 ++ kernel/sched_rt.c | 10 ++++++++-- 2 files changed, 10 insertions(+), 2 deletions(-)
kernel/sched.c +2 -0
@@ -273,6 +273,7 @@ struct rt_rq {unsigned long rt_nr_migratory;/* highest queued rt task prio */ int highest_prio; +int overloaded; };/*
@@ -6672,6 +6673,7 @@ void __init sched_init(void) rq->migration_thread =NULL ;INIT_LIST_HEAD (&rq->migration_queue); rq->rt.highest_prio =MAX_RT_PRIO ; + rq->rt.overloaded =0 ;#endif atomic_set (&rq->nr_iowait,0 );
kernel/sched_rt.c +8 -2
@@ -16,6 +16,7 @@ static inline cpumask_t *rt_overload(voi }static inline void rt_set_overload (struct rq *rq) { + rq->rt.overloaded =1 ;cpu_set (rq->cpu, rt_overload_mask);/* * Make sure the mask is visible before we set
@@ -30,6 +31,7 @@ static inline void rt_set_overload(strucstatic inline void rt_clear_overload (struct rq *rq) {/* the order here really doesn't matter */ + rq->rt.overloaded =0 ;atomic_dec (&rto_count);cpu_clear (rq->cpu, rt_overload_mask); }
@@ -440,6 +442,9 @@ static int push_rt_task(struct rq *rq)assert_spin_locked (&rq->lock); +if (!rq->rt.overloaded) +return 0 ; + next_task =pick_next_highest_task_rt (rq,-1 );if (!next_task)return 0 ;
@@ -676,7 +681,7 @@ static void schedule_tail_balance_rt(str* the lock was owned by prev, we need to release it * first via finish_lock_switch and then reaquire it here. */ -if (unlikely (rq->rt.rt_nr_running >1 )) { +if (unlikely (rq->rt.overloaded)) {spin_lock_irq (&rq->lock);push_rt_tasks (rq);spin_unlock_irq (&rq->lock);
@@ -688,7 +693,8 @@ static void wakeup_balance_rt(struct rq {if (unlikely (rt_task (p)) && !task_running (rq, p) && - (p->prio >= rq->curr->prio)) + (p->prio >= rq->rt.highest_prio) && + rq->rt.overloaded)push_rt_tasks (rq); }
Steven Rostedt
reviewerPATCH v3 16/17 Fix schedstat handling
In reply to Steven RostedtGregory Haskins RT balancing broke sched domains.
This is a fix to allow it to still work.
--- include/linux/sched.h | 3 ++- kernel/sched.c | 17 ++++++++++++++--- kernel/sched_fair.c | 19 ++++++++++++++----- kernel/sched_idletask.c | 3 ++- kernel/sched_rt.c | 3 ++- 5 files changed, 34 insertions(+), 11 deletions(-)
kernel/sched.c +14 -3
@@ -1453,6 +1453,7 @@ static int try_to_wake_up(struct task_stunsigned long flags;long old_state;struct rq *rq; +struct sched_domain *this_sd =NULL ;#ifdef CONFIG_SMP int new_cpu;#endif
@@ -1476,10 +1477,20 @@ static int try_to_wake_up(struct task_stschedstat_inc (rq, ttwu_count);if (cpu == this_cpu)schedstat_inc (rq, ttwu_local); -else -schedstat_inc (rq->sd, ttwu_wake_remote); +else { +#ifdef CONFIG_SCHEDSTATS +struct sched_domain *sd; +for_each_domain (this_cpu, sd) { +if (cpu_isset (cpu, sd->span)) { +schedstat_inc (sd, ttwu_wake_remote); + this_sd = sd; +break ; + } + } +#endif /* CONFIG_SCHEDSTATES */ + } - new_cpu = p->sched_class->select_task_rq (p, sync); + new_cpu = p->sched_class->select_task_rq (p, this_sd, sync);if (new_cpu != cpu) {set_task_cpu (p, new_cpu);
include/linux/sched.h +2 -1
@@ -823,7 +823,8 @@ struct sched_class {void (*enqueue_task) (struct rq *rq,struct task_struct *p,int wakeup);void (*dequeue_task) (struct rq *rq,struct task_struct *p,int sleep);void (*yield_task) (struct rq *rq); -int (*select_task_rq)(struct task_struct *p,int sync); +int (*select_task_rq)(struct task_struct *p, +struct sched_domain *sd,int sync);void (*check_preempt_curr) (struct rq *rq,struct task_struct *p);
kernel/sched_fair.c +14 -5
@@ -611,11 +611,12 @@ static inline int wake_idle(int cpu, str#endif #ifdef CONFIG_SMP -static int select_task_rq_fair (struct task_struct *p,int sync) +static int select_task_rq_fair (struct task_struct *p, +struct sched_domain *this_sd,int sync) {int cpu, this_cpu;struct rq *rq; -struct sched_domain *sd, *this_sd =NULL ; +struct sched_domain *sd;int new_cpu; cpu =task_cpu (p);
@@ -623,15 +624,23 @@ static int select_task_rq_fair(struct ta this_cpu =smp_processor_id (); new_cpu = cpu; +if (cpu == this_cpu ||unlikely (!cpu_isset (this_cpu, p->cpus_allowed))) + goto out_set_cpu; + +#ifndef CONFIG_SCHEDSTATS +/* +* If SCHEDSTATS is configured, then this_sd would +* have already been determined. +*/ for_each_domain (this_cpu, sd) {if (cpu_isset (cpu, sd->span)) { this_sd = sd;break ; } } - -if (unlikely (!cpu_isset (this_cpu, p->cpus_allowed))) - goto out_set_cpu; +#else + (void )sd;/* unused */ +#endif /* CONFIG_SCHEDSTATS */ /* * Check for affine wakeup and passive balancing possibilities.
kernel/sched_idletask.c +2 -1
@@ -6,7 +6,8 @@*/ #ifdef CONFIG_SMP -static int select_task_rq_idle (struct task_struct *p,int sync) +static int select_task_rq_idle (struct task_struct *p, +struct sched_domain *sd,int sync) {return task_cpu (p);/* IDLE tasks as never migrated */ }
kernel/sched_rt.c +2 -1
@@ -46,7 +46,8 @@ static void update_rt_migration(struct rstatic int find_lowest_rq (struct task_struct *task); -static int select_task_rq_rt (struct task_struct *p,int sync) +static int select_task_rq_rt (struct task_struct *p, +struct sched_domain *sd,int sync) {struct rq *rq =task_rq (p);
Re: [PATCH v3 16/17] Fix schedstat handling
Quoted 1 line
Quoted 1 line
Quoted 1 line
On Sat, Nov 17, 2007 at 1:21 AM, in message
<[email protected]>, Steven Rostedt <[email protected]>
Quoted 1 line · wrote:
Gregory Haskins RT balancing broke sched domains.
Doh! (though you mean s/domains/stats ;)
Quoted 35 lines
This is a fix to allow it to still work.
Signed-off-by Steven Rostedt <[email protected]>--- include/linux/sched.h | 3 ++- kernel/sched.c | 17 ++++++++++++++--- kernel/sched_fair.c | 19 ++++++++++++++----- kernel/sched_idletask.c | 3 ++- kernel/sched_rt.c | 3 ++- 5 files changed, 34 insertions(+), 11 deletions(-)Index:
linux-compile.git/kernel/sched.c
===================================================================kernel/sched.c +6
-2@@ -1453,6 +1453,7 @@ static int try_to_wake_up(struct task_stunsigned long flags;long old_state;struct rq *rq; +struct sched_domain *this_sd =NULL ;#ifdef CONFIG_SMP int new_cpu;#endif @@ -1476,10 +1477,20 @@ static int try_to_wake_up(struct task_stschedstat_inc (rq, ttwu_count);if (cpu == this_cpu)schedstat_inc (rq, ttwu_local); -else -schedstat_inc (rq->sd, ttwu_wake_remote); +else { +#ifdef CONFIG_SCHEDSTATS +struct sched_domain *sd; +for_each_domain (this_cpu, sd) { +if (cpu_isset (cpu, sd->span)) {
kernel/sched.c static int try_to_wake_up(struct task_st · line 1493
Quoted 10 lines
kernel/sched.c +8
-1+schedstat_inc (sd, ttwu_wake_remote); + this_sd = sd; + break; + } + } +#endif /* CONFIG_SCHEDSTATES */ + } - new_cpu = p->sched_class->select_task_rq (p, sync); + new_cpu = p->sched_class->select_task_rq (p, this_sd, sync);
I like this optimization, but I am thinking that the location of the stat update is now no longer relevant. It should potentially go *after* the select_task_rq() so that we pick the sched_domain of the actual wake target, not the historical affinity. If that is accurate, I'm sure you can finagle this optimization to work in that scenario too, but it will take a little re-work.
Quoted 94 lines
kernel/sched.c +0
-0if (new_cpu != cpu) {set_task_cpu (p, new_cpu);Index:
linux-compile.git/include/linux/sched.h
===================================================================include/linux/sched.h +2
-1@@ -823,7 +823,8 @@ struct sched_class {void (*enqueue_task) (struct rq *rq,struct task_struct *p,int wakeup);void (*dequeue_task) (struct rq *rq,struct task_struct *p,int sleep);void (*yield_task) (struct rq *rq); -int (*select_task_rq)(struct task_struct *p,int sync); +int (*select_task_rq)(struct task_struct *p, +struct sched_domain *sd,int sync);void (*check_preempt_curr) (struct rq *rq,struct task_struct *p);Index:
linux-compile.git/kernel/sched_fair.c
===================================================================kernel/sched_fair.c +14
-5@@ -611,11 +611,12 @@ static inline int wake_idle(int cpu, str#endif #ifdef CONFIG_SMP -static int select_task_rq_fair (struct task_struct *p,int sync) +static int select_task_rq_fair (struct task_struct *p, +struct sched_domain *this_sd,int sync) {int cpu, this_cpu;struct rq *rq; -struct sched_domain *sd, *this_sd =NULL ; +struct sched_domain *sd;int new_cpu; cpu =task_cpu (p);@@ -623,15 +624,23 @@ static int select_task_rq_fair(struct ta this_cpu =smp_processor_id (); new_cpu = cpu; +if (cpu == this_cpu ||unlikely (!cpu_isset (this_cpu, p->cpus_allowed))) + goto out_set_cpu; + +#ifndef CONFIG_SCHEDSTATS +/* +* If SCHEDSTATS is configured, then this_sd would +* have already been determined. +*/ for_each_domain (this_cpu, sd) {if (cpu_isset (cpu, sd->span)) { this_sd = sd;break ; } } - -if (unlikely (!cpu_isset (this_cpu, p->cpus_allowed))) - goto out_set_cpu; +#else + (void )sd;/* unused */ +#endif /* CONFIG_SCHEDSTATS */ /* * Check for affine wakeup and passive balancing possibilities. Index:
linux-compile.git/kernel/sched_idletask.c
===================================================================
---linux-compile.git.orig/kernel/sched_idletask.c2007-11-17 00:15:57.000000000
-0500
+++linux-compile.git/kernel/sched_idletask.c2007-11-17 00:15:57.000000000 -0500kernel/sched_fair.c +2
-1@@ -6,7 +6,8 @@*/ #ifdef CONFIG_SMP -static int select_task_rq_idle (struct task_struct *p,int sync) +static int select_task_rq_idle (struct task_struct *p, +struct sched_domain *sd,int sync) {return task_cpu (p);/* IDLE tasks as never migrated */ }Index:
linux-compile.git/kernel/sched_rt.c
===================================================================kernel/sched_rt.c +2
-1@@ -46,7 +46,8 @@ static void update_rt_migration(struct rstatic int find_lowest_rq (struct task_struct *task); -static int select_task_rq_rt (struct task_struct *p,int sync) +static int select_task_rq_rt (struct task_struct *p, +struct sched_domain *sd,int sync) {struct rq *rq =task_rq (p);Signature · 1 line
--
Steven Rostedt
reviewerRe: [PATCH v3 16/17] Fix schedstat handling
Quoted 6 lines · Gregory Haskins
Quoted 1 line
Quoted 1 line
Quoted 1 line
On Sat, Nov 17, 2007 at 1:21 AM, in message
<[email protected]>, Steven Rostedt <[email protected]>
Quoted 1 line · wrote:
Gregory Haskins RT balancing broke sched domains.
Doh! (though you mean s/domains/stats ;)
Heh, indeed.
Quoted 44 lines
Quoted 44 lines
This is a fix to allow it to still work.
Signed-off-by Steven Rostedt <[email protected]>--- include/linux/sched.h | 3 ++- kernel/sched.c | 17 ++++++++++++++--- kernel/sched_fair.c | 19 ++++++++++++++----- kernel/sched_idletask.c | 3 ++- kernel/sched_rt.c | 3 ++- 5 files changed, 34 insertions(+), 11 deletions(-)Index:
linux-compile.git/kernel/sched.c
===================================================================kernel/sched.c +13
-2@@ -1453,6 +1453,7 @@ static int try_to_wake_up(struct task_stunsigned long flags;long old_state;struct rq *rq; +struct sched_domain *this_sd =NULL ;#ifdef CONFIG_SMP int new_cpu;#endif @@ -1476,10 +1477,20 @@ static int try_to_wake_up(struct task_stschedstat_inc (rq, ttwu_count);if (cpu == this_cpu)schedstat_inc (rq, ttwu_local); -else -schedstat_inc (rq->sd, ttwu_wake_remote); +else { +#ifdef CONFIG_SCHEDSTATS +struct sched_domain *sd; +for_each_domain (this_cpu, sd) { +if (cpu_isset (cpu, sd->span)) { +schedstat_inc (sd, ttwu_wake_remote); + this_sd = sd; +break ; + } + } +#endif /* CONFIG_SCHEDSTATES */ + }
Quoted 4 lines
kernel/sched.c static int try_to_wake_up(struct task_st · line 1493
Quoted 2 lines
kernel/sched.c +1
-1- new_cpu = p->sched_class->select_task_rq (p, sync); + new_cpu = p->sched_class->select_task_rq (p, this_sd, sync);I like this optimization, but I am thinking that the location of the stat update is now no longer relevant. It should potentially go *after* the
select_task_rq()so that we pick thesched_domainof the actual wake target, not the historical affinity. If that is accurate, I'm sure you can finagle this optimization to work in that scenario too, but it will take a little re-work.
Yeah, I can take a deep look. This was written late at night, so I need to spend more "awake" hours on it.
-- Steve
Steven Rostedt
reviewerPATCH v3 17/17 --- kernel/sched_rt.c | 20 ++++++++++++++++---- 1 file changed, 16 insertions(+), 4 deletions(-)
In reply to Steven Rostedtkernel/sched_rt.c +16 -4
@@ -52,11 +52,23 @@ static int select_task_rq_rt(struct taskstruct rq *rq =task_rq (p);/* -* If the task will not preempt the RQ, try to find a better RQ -* before we even activate the task +* If the current task is an RT task, then +* try to see if we can wake this RT task up on another +* runqueue. Otherwise simply start this RT task +* on its current runqueue. +* +* We want to avoid overloading runqueues. Even if +* the RT task is of higher priority than the current RT task. +* RT tasks behave differently than other tasks. If +* one gets preempted, we try to push it off to another queue. +* So trying to keep a preempting RT task on the same +* cache hot CPU will force the running RT task to +* a cold CPU. So we waste all the cache for the lower +* RT task in hopes of saving some of a RT task +* that is just being woken and probably will have +* cold cache anyway. */ -if ((p->prio >= rq->rt.highest_prio) - && (p->nr_cpus_allowed >1 )) { +if (unlikely (rt_task (rq->curr))) {int cpu =find_lowest_rq (p);return (cpu ==-1 ) ?task_cpu (p) : cpu;
Steven Rostedt
reviewerRe: [PATCH v3 17/17] (Avoid overload)
Sorry! I forgot to put in a prologue for this patch.
Here it is.
====
This patch changes the searching for a run queue by a waking RT task to try to pick another runqueue if the currently running task is an RT task.
The reason is that RT tasks behave different than normal tasks. Preempting a normal task to run a RT task to keep its cache hot is fine, because the preempted non-RT task may wait on that same runqueue to run again unless the migration thread comes along and pulls it off.
RT tasks behave differently. If one is preempted, it makes an active effort to continue to run. So by having a high priority task preempt a lower priority RT task, that lower RT task will then quickly try to run on another runqueue. This will cause that lower RT task to replace its nice hot cache (and TLB) with a completely cold one. This is for the hope that the new high priority RT task will keep
its cache hot.
Remeber that this high priority RT task was just woken up. So it may likely have been sleeping for several milliseconds, and will end up with a cold cache anyway. RT tasks run till they voluntarily stop, or are preempted by a higher priority task. This means that it is unlikely that the woken RT task will have a hot cache to wake up to. So pushing off a lower RT task is just killing its cache for no good reason.
--- kernel/sched_rt.c | 20 ++++++++++++++++---- 1 file changed, 16 insertions(+), 4 deletions(-)
kernel/sched_rt.c +16 -4
@@ -52,11 +52,23 @@ static int select_task_rq_rt(struct taskstruct rq *rq =task_rq (p);/* -* If the task will not preempt the RQ, try to find a better RQ -* before we even activate the task +* If the current task is an RT task, then +* try to see if we can wake this RT task up on another +* runqueue. Otherwise simply start this RT task +* on its current runqueue. +* +* We want to avoid overloading runqueues. Even if +* the RT task is of higher priority than the current RT task. +* RT tasks behave differently than other tasks. If +* one gets preempted, we try to push it off to another queue. +* So trying to keep a preempting RT task on the same +* cache hot CPU will force the running RT task to +* a cold CPU. So we waste all the cache for the lower +* RT task in hopes of saving some of a RT task +* that is just being woken and probably will have +* cold cache anyway. */ -if ((p->prio >= rq->rt.highest_prio) - && (p->nr_cpus_allowed >1 )) { +if (unlikely (rt_task (rq->curr))) {int cpu =find_lowest_rq (p);return (cpu ==-1 ) ?task_cpu (p) : cpu;
Re: [PATCH v3 17/17] (Avoid overload)
Quoted 1 line
Quoted 1 line
Quoted 1 line
On Sat, Nov 17, 2007 at 1:33 AM, in message
<[email protected]>, Steven Rostedt <[email protected]>
Quoted 25 lines · wrote:
Sorry! I forgot to put in a prologue for this patch.
Here it is.
====
This patch changes the searching for a run queue by a waking RT task to try to pick another runqueue if the currently running task is an RT task.
The reason is that RT tasks behave different than normal tasks. Preempting a normal task to run a RT task to keep its cache hot is fine, because the preempted non-RT task may wait on that same runqueue to run again unless the migration thread comes along and pulls it off.
RT tasks behave differently. If one is preempted, it makes an active effort to continue to run. So by having a high priority task preempt a lower priority RT task, that lower RT task will then quickly try to run on another runqueue. This will cause that lower RT task to replace its nice hot cache (and TLB) with a completely cold one. This is for the hope that the new high priority RT task will keep
its cache hot.
Quoted 7 lines
Remeber that this high priority RT task was just woken up. So it may likely have been sleeping for several milliseconds, and will end up with a cold cache anyway. RT tasks run till they voluntarily stop, or are preempted by a higher priority task. This means that it is unlikely that the woken RT task will have a hot cache to wake up to. So pushing off a lower RT task is just killing its cache for no good reason.
You make some excellent points here. Out of curiosity, have you tried a comparison to see if it helps?
-Greg
Steven Rostedt
reviewerRe: [PATCH v3 17/17] (Avoid overload)
Quoted 28 lines · Gregory Haskins
Quoted 20 lines
Quoted 1 line
Quoted 1 line
On Sat, Nov 17, 2007 at 1:33 AM, in message
This patch changes the searching for a run queue by a waking RT task to try to pick another runqueue if the currently running task is an RT task.
The reason is that RT tasks behave different than normal tasks. Preempting a normal task to run a RT task to keep its cache hot is fine, because the preempted non-RT task may wait on that same runqueue to run again unless the migration thread comes along and pulls it off.
RT tasks behave differently. If one is preempted, it makes an active effort to continue to run. So by having a high priority task preempt a lower priority RT task, that lower RT task will then quickly try to run on another runqueue. This will cause that lower RT task to replace its nice hot cache (and TLB) with a completely cold one. This is for the hope that the new high priority RT task will keep
its cache hot.Quoted 7 lines
Remeber that this high priority RT task was just woken up. So it may likely have been sleeping for several milliseconds, and will end up with a cold cache anyway. RT tasks run till they voluntarily stop, or are preempted by a higher priority task. This means that it is unlikely that the woken RT task will have a hot cache to wake up to. So pushing off a lower RT task is just killing its cache for no good reason.
Quoted 1 line
You make some excellent points here. Out of curiosity, have you tried a comparison to see if it helps?
hehe, I was waiting for the "where's the numbers". Right now I don't have them. Mainly because I don't have boxes with more that 4 CPUs on them. And 4 really doesn't make much of a difference.
If others out there would like to test, I'll write up a couple of versions of this code and that way we can really get numbers for them.
Or perhaps someone would like to send me a 16way box. Although my wife would kill me. ;-)
Hmm, I'm sure I can get to our lab and run some tests too.
-- Steve
Re: [PATCH v3 17/17] (Avoid overload)
In reply to Steven RostedtQuoted 1 line
Quoted 1 line
Quoted 1 line
On Sat, Nov 17, 2007 at 1:33 AM, in message
<[email protected]>, Steven Rostedt <[email protected]>
kernel/sched_rt.c static int select_task_rq_rt(struct task · line 74
Quoted 6 lines · wrote:
kernel/sched_rt.c +1
-2-if ((p->prio >= rq->rt.highest_prio) - && (p->nr_cpus_allowed >1 )) { +if (unlikely (rt_task (rq->curr))) {int cpu =find_lowest_rq (p);return (cpu ==-1 ) ?task_cpu (p) : cpu;
We probably should leave the "p->nr_cpus_allowed > 1" in the conditional since it doesn't make sense to look if the task can't go anywhere.
-Greg
PATCH 1/1 RT: restore the migratable conditional
(This applies to the end of Steven's "v3" series
http://lkml.org/lkml/2007/11/17/10)
----------
We don't need to bother searching if the task cannot be migrated
---
kernel/sched_rt.c | 3 ++- 1 files changed, 2 insertions(+), 1 deletions(-)
kernel/sched_rt.c +2 -1
@@ -173,7 +173,8 @@ static int select_task_rq_rt(struct task_struct *p, int sync)* that is just being woken and probably will have * cold cache anyway. */ -if (unlikely (rt_task (rq->curr))) { +if (unlikely (rt_task (rq->curr)) && + (p->nr_cpus_allowed >1 )) {int cpu =find_lowest_rq (p);return (cpu ==-1 ) ?task_cpu (p) : cpu;
Quoted 1 line · Steven Rostedt
Comments welcomed!
Looks very cool. I was a little apprehensive about the active synchronous migration/moving runqueues but you seem to have more than proved your point :-)
Jon.