2 * Real-Time Scheduling Class (mapped to the SCHED_FIFO and SCHED_RR
7 static cpumask_t rt_overload_mask;
8 static atomic_t rto_count;
9 static inline int rt_overloaded(void)
11 return atomic_read(&rto_count);
13 static inline cpumask_t *rt_overload(void)
15 return &rt_overload_mask;
17 static inline void rt_set_overload(struct rq *rq)
19 cpu_set(rq->cpu, rt_overload_mask);
21 * Make sure the mask is visible before we set
22 * the overload count. That is checked to determine
23 * if we should look at the mask. It would be a shame
24 * if we looked at the mask, but the mask was not
28 atomic_inc(&rto_count);
30 static inline void rt_clear_overload(struct rq *rq)
32 /* the order here really doesn't matter */
33 atomic_dec(&rto_count);
34 cpu_clear(rq->cpu, rt_overload_mask);
36 #endif /* CONFIG_SMP */
39 * Update the current task's runtime statistics. Skip current tasks that
40 * are not in our scheduling class.
42 static void update_curr_rt(struct rq *rq)
44 struct task_struct *curr = rq->curr;
47 if (!task_has_rt_policy(curr))
50 delta_exec = rq->clock - curr->se.exec_start;
51 if (unlikely((s64)delta_exec < 0))
54 schedstat_set(curr->se.exec_max, max(curr->se.exec_max, delta_exec));
56 curr->se.sum_exec_runtime += delta_exec;
57 curr->se.exec_start = rq->clock;
58 cpuacct_charge(curr, delta_exec);
61 static inline void inc_rt_tasks(struct task_struct *p, struct rq *rq)
64 rq->rt.rt_nr_running++;
66 if (p->prio < rq->rt.highest_prio)
67 rq->rt.highest_prio = p->prio;
68 if (rq->rt.rt_nr_running > 1)
70 #endif /* CONFIG_SMP */
73 static inline void dec_rt_tasks(struct task_struct *p, struct rq *rq)
76 WARN_ON(!rq->rt.rt_nr_running);
77 rq->rt.rt_nr_running--;
79 if (rq->rt.rt_nr_running) {
80 struct rt_prio_array *array;
82 WARN_ON(p->prio < rq->rt.highest_prio);
83 if (p->prio == rq->rt.highest_prio) {
85 array = &rq->rt.active;
87 sched_find_first_bit(array->bitmap);
88 } /* otherwise leave rq->highest prio alone */
90 rq->rt.highest_prio = MAX_RT_PRIO;
91 if (rq->rt.rt_nr_running < 2)
92 rt_clear_overload(rq);
93 #endif /* CONFIG_SMP */
96 static void enqueue_task_rt(struct rq *rq, struct task_struct *p, int wakeup)
98 struct rt_prio_array *array = &rq->rt.active;
100 list_add_tail(&p->run_list, array->queue + p->prio);
101 __set_bit(p->prio, array->bitmap);
102 inc_cpu_load(rq, p->se.load.weight);
108 * Adding/removing a task to/from a priority array:
110 static void dequeue_task_rt(struct rq *rq, struct task_struct *p, int sleep)
112 struct rt_prio_array *array = &rq->rt.active;
116 list_del(&p->run_list);
117 if (list_empty(array->queue + p->prio))
118 __clear_bit(p->prio, array->bitmap);
119 dec_cpu_load(rq, p->se.load.weight);
125 * Put task to the end of the run list without the overhead of dequeue
126 * followed by enqueue.
128 static void requeue_task_rt(struct rq *rq, struct task_struct *p)
130 struct rt_prio_array *array = &rq->rt.active;
132 list_move_tail(&p->run_list, array->queue + p->prio);
136 yield_task_rt(struct rq *rq)
138 requeue_task_rt(rq, rq->curr);
142 * Preempt the current task with a newly woken task if needed:
144 static void check_preempt_curr_rt(struct rq *rq, struct task_struct *p)
146 if (p->prio < rq->curr->prio)
147 resched_task(rq->curr);
150 static struct task_struct *pick_next_task_rt(struct rq *rq)
152 struct rt_prio_array *array = &rq->rt.active;
153 struct task_struct *next;
154 struct list_head *queue;
157 idx = sched_find_first_bit(array->bitmap);
158 if (idx >= MAX_RT_PRIO)
161 queue = array->queue + idx;
162 next = list_entry(queue->next, struct task_struct, run_list);
164 next->se.exec_start = rq->clock;
169 static void put_prev_task_rt(struct rq *rq, struct task_struct *p)
172 p->se.exec_start = 0;
176 /* Only try algorithms three times */
177 #define RT_MAX_TRIES 3
179 static int double_lock_balance(struct rq *this_rq, struct rq *busiest);
180 static void deactivate_task(struct rq *rq, struct task_struct *p, int sleep);
182 /* Return the second highest RT task, NULL otherwise */
183 static struct task_struct *pick_next_highest_task_rt(struct rq *rq)
185 struct rt_prio_array *array = &rq->rt.active;
186 struct task_struct *next;
187 struct list_head *queue;
190 assert_spin_locked(&rq->lock);
192 if (likely(rq->rt.rt_nr_running < 2))
195 idx = sched_find_first_bit(array->bitmap);
196 if (unlikely(idx >= MAX_RT_PRIO)) {
197 WARN_ON(1); /* rt_nr_running is bad */
201 queue = array->queue + idx;
202 next = list_entry(queue->next, struct task_struct, run_list);
203 if (unlikely(next != rq->curr))
206 if (queue->next->next != queue) {
208 next = list_entry(queue->next->next, struct task_struct, run_list);
212 /* slower, but more flexible */
213 idx = find_next_bit(array->bitmap, MAX_RT_PRIO, idx+1);
214 if (unlikely(idx >= MAX_RT_PRIO)) {
215 WARN_ON(1); /* rt_nr_running was 2 and above! */
219 queue = array->queue + idx;
220 next = list_entry(queue->next, struct task_struct, run_list);
225 static DEFINE_PER_CPU(cpumask_t, local_cpu_mask);
227 /* Will lock the rq it finds */
228 static struct rq *find_lock_lowest_rq(struct task_struct *task,
231 struct rq *lowest_rq = NULL;
234 cpumask_t *cpu_mask = &__get_cpu_var(local_cpu_mask);
236 cpus_and(*cpu_mask, cpu_online_map, task->cpus_allowed);
238 for (tries = 0; tries < RT_MAX_TRIES; tries++) {
240 * Scan each rq for the lowest prio.
242 for_each_cpu_mask(cpu, *cpu_mask) {
243 struct rq *rq = &per_cpu(runqueues, cpu);
245 if (cpu == this_rq->cpu)
248 /* We look for lowest RT prio or non-rt CPU */
249 if (rq->rt.highest_prio >= MAX_RT_PRIO) {
254 /* no locking for now */
255 if (rq->rt.highest_prio > task->prio &&
256 (!lowest_rq || rq->rt.highest_prio > lowest_rq->rt.highest_prio)) {
264 /* if the prio of this runqueue changed, try again */
265 if (double_lock_balance(this_rq, lowest_rq)) {
267 * We had to unlock the run queue. In
268 * the mean time, task could have
269 * migrated already or had its affinity changed.
270 * Also make sure that it wasn't scheduled on its rq.
272 if (unlikely(task_rq(task) != this_rq ||
273 !cpu_isset(lowest_rq->cpu, task->cpus_allowed) ||
274 task_running(this_rq, task) ||
276 spin_unlock(&lowest_rq->lock);
282 /* If this rq is still suitable use it. */
283 if (lowest_rq->rt.highest_prio > task->prio)
287 spin_unlock(&lowest_rq->lock);
295 * If the current CPU has more than one RT task, see if the non
296 * running task can migrate over to a CPU that is running a task
297 * of lesser priority.
299 static int push_rt_task(struct rq *this_rq)
301 struct task_struct *next_task;
302 struct rq *lowest_rq;
304 int paranoid = RT_MAX_TRIES;
306 assert_spin_locked(&this_rq->lock);
308 next_task = pick_next_highest_task_rt(this_rq);
313 if (unlikely(next_task == this_rq->curr))
317 * It's possible that the next_task slipped in of
318 * higher priority than current. If that's the case
319 * just reschedule current.
321 if (unlikely(next_task->prio < this_rq->curr->prio)) {
322 resched_task(this_rq->curr);
326 /* We might release this_rq lock */
327 get_task_struct(next_task);
329 /* find_lock_lowest_rq locks the rq if found */
330 lowest_rq = find_lock_lowest_rq(next_task, this_rq);
332 struct task_struct *task;
334 * find lock_lowest_rq releases this_rq->lock
335 * so it is possible that next_task has changed.
336 * If it has, then try again.
338 task = pick_next_highest_task_rt(this_rq);
339 if (unlikely(task != next_task) && task && paranoid--) {
340 put_task_struct(next_task);
347 assert_spin_locked(&lowest_rq->lock);
349 deactivate_task(this_rq, next_task, 0);
350 set_task_cpu(next_task, lowest_rq->cpu);
351 activate_task(lowest_rq, next_task, 0);
353 resched_task(lowest_rq->curr);
355 spin_unlock(&lowest_rq->lock);
359 put_task_struct(next_task);
365 * TODO: Currently we just use the second highest prio task on
366 * the queue, and stop when it can't migrate (or there's
367 * no more RT tasks). There may be a case where a lower
368 * priority RT task has a different affinity than the
369 * higher RT task. In this case the lower RT task could
370 * possibly be able to migrate where as the higher priority
371 * RT task could not. We currently ignore this issue.
372 * Enhancements are welcome!
374 static void push_rt_tasks(struct rq *rq)
376 /* push_rt_task will return true if it moved an RT */
377 while (push_rt_task(rq))
381 static void schedule_tail_balance_rt(struct rq *rq)
384 * If we have more than one rt_task queued, then
385 * see if we can push the other rt_tasks off to other CPUS.
386 * Note we may release the rq lock, and since
387 * the lock was owned by prev, we need to release it
388 * first via finish_lock_switch and then reaquire it here.
390 if (unlikely(rq->rt.rt_nr_running > 1)) {
391 spin_lock_irq(&rq->lock);
393 spin_unlock_irq(&rq->lock);
398 * Load-balancing iterator. Note: while the runqueue stays locked
399 * during the whole iteration, the current task might be
400 * dequeued so the iterator has to be dequeue-safe. Here we
401 * achieve that by always pre-iterating before returning
404 static struct task_struct *load_balance_start_rt(void *arg)
407 struct rt_prio_array *array = &rq->rt.active;
408 struct list_head *head, *curr;
409 struct task_struct *p;
412 idx = sched_find_first_bit(array->bitmap);
413 if (idx >= MAX_RT_PRIO)
416 head = array->queue + idx;
419 p = list_entry(curr, struct task_struct, run_list);
423 rq->rt.rt_load_balance_idx = idx;
424 rq->rt.rt_load_balance_head = head;
425 rq->rt.rt_load_balance_curr = curr;
430 static struct task_struct *load_balance_next_rt(void *arg)
433 struct rt_prio_array *array = &rq->rt.active;
434 struct list_head *head, *curr;
435 struct task_struct *p;
438 idx = rq->rt.rt_load_balance_idx;
439 head = rq->rt.rt_load_balance_head;
440 curr = rq->rt.rt_load_balance_curr;
443 * If we arrived back to the head again then
444 * iterate to the next queue (if any):
446 if (unlikely(head == curr)) {
447 int next_idx = find_next_bit(array->bitmap, MAX_RT_PRIO, idx+1);
449 if (next_idx >= MAX_RT_PRIO)
453 head = array->queue + idx;
456 rq->rt.rt_load_balance_idx = idx;
457 rq->rt.rt_load_balance_head = head;
460 p = list_entry(curr, struct task_struct, run_list);
464 rq->rt.rt_load_balance_curr = curr;
470 load_balance_rt(struct rq *this_rq, int this_cpu, struct rq *busiest,
471 unsigned long max_load_move,
472 struct sched_domain *sd, enum cpu_idle_type idle,
473 int *all_pinned, int *this_best_prio)
475 struct rq_iterator rt_rq_iterator;
477 rt_rq_iterator.start = load_balance_start_rt;
478 rt_rq_iterator.next = load_balance_next_rt;
479 /* pass 'busiest' rq argument into
480 * load_balance_[start|next]_rt iterators
482 rt_rq_iterator.arg = busiest;
484 return balance_tasks(this_rq, this_cpu, busiest, max_load_move, sd,
485 idle, all_pinned, this_best_prio, &rt_rq_iterator);
489 move_one_task_rt(struct rq *this_rq, int this_cpu, struct rq *busiest,
490 struct sched_domain *sd, enum cpu_idle_type idle)
492 struct rq_iterator rt_rq_iterator;
494 rt_rq_iterator.start = load_balance_start_rt;
495 rt_rq_iterator.next = load_balance_next_rt;
496 rt_rq_iterator.arg = busiest;
498 return iter_move_one_task(this_rq, this_cpu, busiest, sd, idle,
501 #else /* CONFIG_SMP */
502 # define schedule_tail_balance_rt(rq) do { } while (0)
503 #endif /* CONFIG_SMP */
505 static void task_tick_rt(struct rq *rq, struct task_struct *p)
510 * RR tasks need a special form of timeslice management.
511 * FIFO tasks have no timeslices.
513 if (p->policy != SCHED_RR)
519 p->time_slice = DEF_TIMESLICE;
522 * Requeue to the end of queue if we are not the only element
525 if (p->run_list.prev != p->run_list.next) {
526 requeue_task_rt(rq, p);
527 set_tsk_need_resched(p);
531 static void set_curr_task_rt(struct rq *rq)
533 struct task_struct *p = rq->curr;
535 p->se.exec_start = rq->clock;
538 const struct sched_class rt_sched_class = {
539 .next = &fair_sched_class,
540 .enqueue_task = enqueue_task_rt,
541 .dequeue_task = dequeue_task_rt,
542 .yield_task = yield_task_rt,
544 .check_preempt_curr = check_preempt_curr_rt,
546 .pick_next_task = pick_next_task_rt,
547 .put_prev_task = put_prev_task_rt,
550 .load_balance = load_balance_rt,
551 .move_one_task = move_one_task_rt,
554 .set_curr_task = set_curr_task_rt,
555 .task_tick = task_tick_rt,