1 - Major overhaul of queued changes.
3 - Microoptimise multiplications/divisions to be shifts where suitable.
5 - Change ISO calculations to have their own lock so as to not grab the grq
6 lock during a scheduler tick.
8 - Change all deadline accounting to use nanosecond values.
10 - Introduce local niffies variable which is updated from any runqueue using the
11 TSC clock whenever the grq lock is taken. Use niffies to compare deadlines to.
12 This will give much more granular deadlines when jiffies are low resolution
13 such as 100Hz, and rarely will tasks have the same deadlines now.
15 - Drop the "skip_clock_update" concept as we update the niffies each time we
16 update the rq clocks, thus we want to update it more often.
20 - Bypass rechecking deadline when we know that prev will run again in schedule.
22 - Check to see if prev can run on an idle CPU when being descheduled as may
23 happen when a task must use a certain CPU for affinity reasons.
25 - Decrease maximum rr_interval possible to 1000 (one second) as there is no
26 demonstrable advantage to higher values, and may overflow with other changes
29 - Check for when tasks are scheduled within a tick to see if they're in the
30 1st or 2nd half of the tick. Use this to decide how far into last tick a task
31 can run. This will make the greatest difference on lower Hz values with small
34 - Change the test for exhausted time slice to 100us as rescheduling with less
35 time available than this will either greatly overrun its quota or reschedule
38 - Change SCHED_BATCH tasks to refill timeslices and reset deadline every time
39 they're descheduled as they've been flagged as latency insensitive, likely
40 fully CPU bound tasks. This should decrease the impact running batch tasks
43 - Microoptimise before context switch in schedule()
45 - Add a local last_task variable to each runqueue which keeps a copy of the
46 last non-idle task that ran on this CPU. Use this value to determine that a
47 task is still cache warm on this CPU even if it has run elsewhere in the
48 meantime. This improves throughput on relatively idle systems with >2 logical
51 - Remove the first_time_slice concept as it wasn't contributing on any
52 meaningful level but was adding to overhead, especially on sched_exit.
54 - Check that when a task forks and loses timeslice to its child that it isn't
55 due to be descheduled and ensure that a child inherits the proper variables
56 from its parent across fork.
58 - Fix try_preempt which may have been picking a higher priority runqueue on
59 SMP if it had a later deadline. Remove the test for equal deadline as
60 nanosecond deadline resolution means this will never happen.
62 - Random other minor cleanups.
67 Documentation/scheduler/sched-BFS.txt | 2
68 include/linux/sched.h | 4
69 kernel/sched_bfs.c | 466 +++++++++++++++++++++-------------
71 4 files changed, 293 insertions(+), 183 deletions(-)
73 Index: linux-2.6.35-bfs/Documentation/scheduler/sched-BFS.txt
74 ===================================================================
75 --- linux-2.6.35-bfs.orig/Documentation/scheduler/sched-BFS.txt 2010-09-25 08:18:30.134360792 +1000
76 +++ linux-2.6.35-bfs/Documentation/scheduler/sched-BFS.txt 2010-09-25 08:20:25.830887001 +1000
77 @@ -257,7 +257,7 @@ uniprocessor machine, and automatically
78 multiprocessor machines. The reasoning behind increasing the value on more CPUs
79 is that the effective latency is decreased by virtue of there being more CPUs on
80 BFS (for reasons explained above), and increasing the value allows for less
81 -cache contention and more throughput. Valid values are from 1 to 5000
82 +cache contention and more throughput. Valid values are from 1 to 1000
83 Decreasing the value will decrease latencies at the cost of decreasing
84 throughput, while increasing it will improve throughput, but at the cost of
85 worsening latencies. The accuracy of the rr interval is limited by HZ resolution
86 Index: linux-2.6.35-bfs/include/linux/sched.h
87 ===================================================================
88 --- linux-2.6.35-bfs.orig/include/linux/sched.h 2010-09-25 08:18:08.792894602 +1000
89 +++ linux-2.6.35-bfs/include/linux/sched.h 2010-09-25 08:20:25.822886826 +1000
90 @@ -1197,7 +1197,7 @@ struct task_struct {
91 int prio, static_prio, normal_prio;
92 unsigned int rt_priority;
93 #ifdef CONFIG_SCHED_BFS
94 - int time_slice, first_time_slice;
97 struct list_head run_list;
99 @@ -1547,7 +1547,7 @@ static inline void tsk_cpus_current(stru
101 static inline void print_scheduler_version(void)
103 - printk(KERN_INFO"BFS CPU scheduler v0.330 by Con Kolivas.\n");
104 + printk(KERN_INFO"BFS CPU scheduler v0.350 by Con Kolivas.\n");
107 static inline int iso_task(struct task_struct *p)
108 Index: linux-2.6.35-bfs/kernel/sched_bfs.c
109 ===================================================================
110 --- linux-2.6.35-bfs.orig/kernel/sched_bfs.c 2010-09-25 08:18:08.804894864 +1000
111 +++ linux-2.6.35-bfs/kernel/sched_bfs.c 2010-09-25 08:20:25.827886935 +1000
112 @@ -106,10 +106,19 @@
113 #define MAX_USER_PRIO (USER_PRIO(MAX_PRIO))
114 #define SCHED_PRIO(p) ((p)+MAX_RT_PRIO)
116 -/* Some helpers for converting to/from various scales.*/
118 + * Some helpers for converting to/from various scales. Use shifts to get
119 + * approximate multiples of ten for less overhead.
121 #define JIFFIES_TO_NS(TIME) ((TIME) * (1000000000 / HZ))
122 -#define MS_TO_NS(TIME) ((TIME) * 1000000)
123 -#define MS_TO_US(TIME) ((TIME) * 1000)
124 +#define HALF_JIFFY_NS (1000000000 / HZ / 2)
125 +#define HALF_JIFFY_US (1000000 / HZ / 2)
126 +#define MS_TO_NS(TIME) ((TIME) << 20)
127 +#define MS_TO_US(TIME) ((TIME) << 10)
128 +#define NS_TO_MS(TIME) ((TIME) >> 20)
129 +#define NS_TO_US(TIME) ((TIME) >> 10)
131 +#define RESCHED_US (100) /* Reschedule if less than this many us left */
134 * This is the time all tasks within the same priority round robin.
135 @@ -140,8 +149,9 @@ static inline unsigned long timeslice(vo
139 - * The global runqueue data that all CPUs work off. All data is protected
141 + * The global runqueue data that all CPUs work off. Data is protected either
142 + * by the global grq lock, or the discrete lock that precedes the data in this
147 @@ -150,17 +160,17 @@ struct global_rq {
148 unsigned long long nr_switches;
149 struct list_head queue[PRIO_LIMIT];
150 DECLARE_BITMAP(prio_bitmap, PRIO_LIMIT + 1);
152 - int iso_refractory;
154 unsigned long qnr; /* queued not running */
155 cpumask_t cpu_idle_map;
158 -#if BITS_PER_LONG < 64
159 - unsigned long jiffies;
162 + /* Nanosecond jiffies */
165 + raw_spinlock_t iso_lock;
167 + int iso_refractory;
170 /* There can be only one */
171 @@ -176,8 +186,8 @@ struct rq {
173 unsigned char in_nohz_recently;
175 + struct task_struct *last_task;
177 - unsigned int skip_clock_update;
179 struct task_struct *curr, *idle;
180 struct mm_struct *prev_mm;
181 @@ -213,9 +223,11 @@ struct rq {
182 /* See if all cache siblings are idle */
183 cpumask_t cache_siblings;
185 + u64 last_niffy; /* Last time this RQ updated grq.niffies */
187 + u64 clock, old_clock, last_tick;
191 #ifdef CONFIG_SCHEDSTATS
194 @@ -286,15 +298,6 @@ struct root_domain {
195 static struct root_domain def_root_domain;
198 -static inline int cpu_of(struct rq *rq)
207 #define rcu_dereference_check_sched_domain(p) \
208 rcu_dereference_check((p), \
209 rcu_read_lock_sched_held() || \
210 @@ -310,17 +313,65 @@ static inline int cpu_of(struct rq *rq)
211 #define for_each_domain(cpu, __sd) \
212 for (__sd = rcu_dereference_check_sched_domain(cpu_rq(cpu)->sd); __sd; __sd = __sd->parent)
214 +static inline void update_rq_clock(struct rq *rq);
217 #define cpu_rq(cpu) (&per_cpu(runqueues, (cpu)))
218 #define this_rq() (&__get_cpu_var(runqueues))
219 #define task_rq(p) cpu_rq(task_cpu(p))
220 #define cpu_curr(cpu) (cpu_rq(cpu)->curr)
221 +static inline int cpu_of(struct rq *rq)
227 + * Niffies are a globally increasing nanosecond counter. Whenever a runqueue
228 + * clock is updated with the grq.lock held, it is an opportunity to update the
229 + * niffies value. Any CPU can update it by adding how much its clock has
230 + * increased since it last updated niffies, minus any added niffies by other
233 +static inline void update_clocks(struct rq *rq)
237 + update_rq_clock(rq);
238 + ndiff = rq->clock - rq->old_clock;
239 + /* old_clock is only updated when we are updating niffies */
240 + rq->old_clock = rq->clock;
241 + ndiff -= grq.niffies - rq->last_niffy;
243 + * Sanity check should sched_clock return bogus values or be limited to
244 + * just jiffy resolution. Some time will always have passed.
246 + if (unlikely(ndiff < 1 || ndiff > MS_TO_NS(rr_interval)))
248 + grq.niffies += ndiff;
249 + rq->last_niffy = grq.niffies;
251 #else /* CONFIG_SMP */
252 static struct rq *uprq;
253 #define cpu_rq(cpu) (uprq)
254 #define this_rq() (uprq)
255 #define task_rq(p) (uprq)
256 #define cpu_curr(cpu) ((uprq)->curr)
257 +static inline int cpu_of(struct rq *rq)
262 +static inline void update_clocks(struct rq *rq)
266 + update_rq_clock(rq);
267 + ndiff = rq->clock - rq->old_clock;
268 + rq->old_clock = rq->clock;
269 + if (unlikely(ndiff < 1 || ndiff > MS_TO_US(rr_interval)))
271 + grq.niffies += ndiff;
274 #define raw_rq() (&__raw_get_cpu_var(runqueues))
276 @@ -335,13 +386,13 @@ static struct rq *uprq;
279 * All common locking functions performed on grq.lock. rq->clock is local to
280 - * the cpu accessing it so it can be modified just with interrupts disabled,
281 - * but looking up task_rq must be done under grq.lock to be safe.
282 + * the CPU accessing it so it can be modified just with interrupts disabled
283 + * when we're not updating niffies.
284 + * Looking up task_rq must be done under grq.lock to be safe.
286 -inline void update_rq_clock(struct rq *rq)
287 +static inline void update_rq_clock(struct rq *rq)
289 - if (!rq->skip_clock_update)
290 - rq->clock = sched_clock_cpu(cpu_of(rq));
291 + rq->clock = sched_clock_cpu(cpu_of(rq));
294 static inline int task_running(struct task_struct *p)
295 @@ -370,8 +421,8 @@ static inline void grq_lock_irq(void)
296 static inline void time_lock_grq(struct rq *rq)
299 - update_rq_clock(rq);
304 static inline void grq_unlock_irq(void)
305 @@ -405,7 +456,7 @@ static inline struct rq
308 struct rq *rq = task_grq_lock(p, flags);
309 - update_rq_clock(rq);
314 @@ -420,7 +471,7 @@ static inline void time_task_grq_lock_ir
317 struct rq *rq = task_grq_lock_irq(p);
318 - update_rq_clock(rq);
322 static inline void task_grq_unlock_irq(void)
323 @@ -515,33 +566,6 @@ static inline void finish_lock_switch(st
325 #endif /* __ARCH_WANT_UNLOCKED_CTXSW */
328 - * In order to have a monotonic clock that does not wrap we have a 64 bit
329 - * unsigned long that's protected by grq.lock used in place of jiffies on
332 -#if BITS_PER_LONG < 64
333 -static inline void update_gjiffies(void)
335 - if (grq.jiffies != jiffies) {
337 - grq.jiffies = jiffies;
343 -#define gjiffies (grq.jiffies_64)
345 -#else /* BITS_PER_LONG < 64 */
346 -static inline void update_gjiffies(void)
350 -#define gjiffies jiffies
352 -#endif /* BITS_PER_LONG < 64 */
354 static inline int deadline_before(u64 deadline, u64 time)
356 return (deadline < time);
357 @@ -574,17 +598,6 @@ static void dequeue_task(struct task_str
361 - * When a task is freshly forked, the first_time_slice flag is set to say
362 - * it has taken time_slice from its parent and if it exits on this first
363 - * time_slice it can return its time_slice back to the parent.
365 -static inline void reset_first_time_slice(struct task_struct *p)
367 - if (unlikely(p->first_time_slice))
368 - p->first_time_slice = 0;
372 * To determine if it's safe for a task of SCHED_IDLEPRIO to actually run as
373 * an idle task, we ensure none of the following conditions are met.
375 @@ -646,11 +659,11 @@ static inline int task_prio_ratio(struct
377 * task_timeslice - all tasks of all priorities get the exact same timeslice
378 * length. CPU distribution is handled by giving different deadlines to
379 - * tasks of different priorities.
380 + * tasks of different priorities. Use 128 as the base value for fast shifts.
382 static inline int task_timeslice(struct task_struct *p)
384 - return (rr_interval * task_prio_ratio(p) / 100);
385 + return (rr_interval * task_prio_ratio(p) / 128);
389 @@ -702,6 +715,15 @@ static int suitable_idle_cpus(struct tas
391 static void resched_task(struct task_struct *p);
394 + * last_task stores the last non-idle task scheduled on the local rq for
395 + * cache warmth testing.
397 +static inline void set_last_task(struct rq *rq, struct task_struct *p)
402 #define CPUIDLE_CACHE_BUSY (1)
403 #define CPUIDLE_DIFF_CPU (2)
404 #define CPUIDLE_THREAD_BUSY (4)
405 @@ -724,6 +746,9 @@ static void resched_task(struct task_str
406 * Other node, other CPU, idle cache, idle threads.
407 * Other node, other CPU, busy cache, idle threads.
408 * Other node, other CPU, busy threads.
410 + * If p was the last task running on this rq, then regardless of where
411 + * it has been running since then, it is cache warm on this rq.
413 static void resched_best_idle(struct task_struct *p)
415 @@ -756,11 +781,14 @@ static void resched_best_idle(struct tas
416 tmp_rq = cpu_rq(cpu_tmp);
418 if (rq->cpu_locality[cpu_tmp]) {
419 + /* Check rq->last_task hasn't been dereferenced */
420 + if (rq->last_task && p != rq->last_task) {
422 - if (rq->cpu_locality[cpu_tmp] > 1)
423 - ranking |= CPUIDLE_DIFF_NODE;
424 + if (rq->cpu_locality[cpu_tmp] > 1)
425 + ranking |= CPUIDLE_DIFF_NODE;
427 - ranking |= CPUIDLE_DIFF_CPU;
428 + ranking |= CPUIDLE_DIFF_CPU;
431 #ifdef CONFIG_SCHED_MC
432 if (!(tmp_rq->cache_idle(cpu_tmp)))
433 @@ -802,6 +830,11 @@ static inline void resched_suitable_idle
435 cache_distance(struct rq *task_rq, struct rq *rq, struct task_struct *p)
437 + /* Check rq->last_task hasn't been dereferenced */
438 + if (likely(rq->last_task)) {
439 + if (rq->last_task == p)
442 return rq->cpu_locality[cpu_of(task_rq)] * task_timeslice(p);
444 #else /* CONFIG_SMP */
445 @@ -840,6 +873,10 @@ cache_distance(struct rq *task_rq, struc
450 +static inline void set_last_task(struct rq *rq, struct task_struct *p)
453 #endif /* CONFIG_SMP */
456 @@ -887,7 +924,7 @@ static int effective_prio(struct task_st
458 static void activate_task(struct task_struct *p, struct rq *rq)
460 - update_rq_clock(rq);
464 * Sleep time is in units of nanosecs, so shift by 20 to get a
465 @@ -1157,8 +1194,28 @@ EXPORT_SYMBOL_GPL(kick_process);
468 #define rq_idle(rq) ((rq)->rq_prio == PRIO_LIMIT)
469 -#define task_idle(p) ((p)->prio == PRIO_LIMIT)
472 + * RT tasks preempt purely on priority. SCHED_NORMAL tasks preempt on the
473 + * basis of earlier deadlines. SCHED_IDLEPRIO don't preempt anything else or
474 + * between themselves, they cooperatively multitask. An idle rq scores as
475 + * prio PRIO_LIMIT so it is always preempted.
478 +can_preempt(struct task_struct *p, int prio, unsigned long deadline,
479 + unsigned int policy)
481 + /* Better static priority RT task or better policy preemption */
482 + if (p->prio < prio)
484 + if (p->prio > prio)
486 + /* SCHED_NORMAL, BATCH and ISO will preempt based on deadline */
487 + if (!deadline_before(p->deadline, deadline))
492 #ifdef CONFIG_HOTPLUG_CPU
494 * Check to see if there is a task that is affined only to offline CPUs but
495 @@ -1178,14 +1235,20 @@ static inline int online_cpus(struct tas
499 - * RT tasks preempt purely on priority. SCHED_NORMAL tasks preempt on the
500 - * basis of earlier deadlines. SCHED_BATCH, ISO and IDLEPRIO don't preempt
501 - * between themselves, they cooperatively multitask. An idle rq scores as
502 - * prio PRIO_LIMIT so it is always preempted. latest_deadline and
503 - * highest_prio_rq are initialised only to silence the compiler. When
504 - * all else is equal, still prefer this_rq.
505 + * Check to see if p can run on cpu, and if not, whether there are any online
506 + * CPUs it can run on instead.
508 +static inline int needs_other_cpu(struct task_struct *p, int cpu)
510 + if (unlikely(!cpu_isset(cpu, p->cpus_allowed) && online_cpus(p)))
516 + * latest_deadline and highest_prio_rq are initialised only to silence the
517 + * compiler. When all else is equal, still prefer this_rq.
520 static void try_preempt(struct task_struct *p, struct rq *this_rq)
522 struct rq *highest_prio_rq = this_rq;
523 @@ -1193,6 +1256,10 @@ static void try_preempt(struct task_stru
527 + /* IDLEPRIO tasks never preempt anything */
528 + if (p->policy == SCHED_IDLEPRIO)
531 if (suitable_idle_cpus(p)) {
532 resched_best_idle(p);
534 @@ -1219,30 +1286,32 @@ static void try_preempt(struct task_stru
535 offset_deadline = rq->rq_deadline -
536 cache_distance(this_rq, rq, p);
538 - if (rq_prio > highest_prio ||
539 - (deadline_after(offset_deadline, latest_deadline) ||
540 - (offset_deadline == latest_deadline && this_rq == rq))) {
541 + if (rq_prio > highest_prio || (rq_prio == highest_prio &&
542 + deadline_after(offset_deadline, latest_deadline))) {
543 latest_deadline = offset_deadline;
544 highest_prio = rq_prio;
545 highest_prio_rq = rq;
549 - if (p->prio > highest_prio || (p->prio == highest_prio &&
550 - p->policy == SCHED_NORMAL &&
551 - !deadline_before(p->deadline, latest_deadline)))
552 + if (!can_preempt(p, highest_prio, highest_prio_rq->rq_deadline,
553 + highest_prio_rq->rq_policy))
556 - /* p gets to preempt highest_prio_rq->curr */
557 resched_task(highest_prio_rq->curr);
558 - highest_prio_rq->skip_clock_update = 1;
560 #else /* CONFIG_SMP */
561 +static inline int needs_other_cpu(struct task_struct *p, int cpu)
566 static void try_preempt(struct task_struct *p, struct rq *this_rq)
568 - if (p->prio < uprq->rq_prio ||
569 - (p->prio == uprq->rq_prio && p->policy == SCHED_NORMAL &&
570 - deadline_before(p->deadline, uprq->rq_deadline)))
571 + if (p->policy == SCHED_IDLEPRIO)
573 + if (can_preempt(p, uprq->rq_prio, uprq->rq_deadline,
575 resched_task(uprq->curr);
577 #endif /* CONFIG_SMP */
578 @@ -1352,12 +1421,15 @@ int wake_up_state(struct task_struct *p,
579 return try_to_wake_up(p, state, 0);
582 +static void time_slice_expired(struct task_struct *p);
585 * Perform scheduler related setup for a newly forked process p.
586 * p is forked by current.
588 void sched_fork(struct task_struct *p, int clone_flags)
590 + struct task_struct *curr;
594 @@ -1396,10 +1468,11 @@ void sched_fork(struct task_struct *p, i
595 p->sched_reset_on_fork = 0;
600 * Make sure we do not leak PI boosting priority to the child.
602 - p->prio = current->normal_prio;
603 + p->prio = curr->normal_prio;
605 INIT_LIST_HEAD(&p->run_list);
606 #if defined(CONFIG_SCHEDSTATS) || defined(CONFIG_TASK_DELAY_ACCT)
607 @@ -1420,18 +1493,26 @@ void sched_fork(struct task_struct *p, i
608 * total amount of pending timeslices in the system doesn't change,
609 * resulting in more scheduling fairness. If it's negative, it won't
610 * matter since that's the same as being 0. current's time_slice is
611 - * actually in rq_time_slice when it's running.
612 + * actually in rq_time_slice when it's running, as is its last_ran
613 + * value. rq->rq_deadline is only modified within schedule() so it
614 + * is always equal to current->deadline.
616 - rq = task_grq_lock_irq(current);
617 - if (likely(rq->rq_time_slice > 0)) {
618 + rq = task_grq_lock_irq(curr);
619 + if (likely(rq->rq_time_slice >= RESCHED_US * 2)) {
620 rq->rq_time_slice /= 2;
621 + p->time_slice = rq->rq_time_slice;
624 - * The remainder of the first timeslice might be recovered by
625 - * the parent if the child exits early enough.
626 + * Forking task has run out of timeslice. Reschedule it and
627 + * start its child with a new time slice and deadline. The
628 + * child will end up running first because its deadline will
629 + * be slightly earlier.
631 - p->first_time_slice = 1;
632 + rq->rq_time_slice = 0;
633 + set_tsk_need_resched(curr);
634 + time_slice_expired(p);
636 - p->time_slice = rq->rq_time_slice;
637 + p->last_ran = rq->rq_last_ran;
638 task_grq_unlock_irq();
641 @@ -1470,40 +1551,9 @@ void wake_up_new_task(struct task_struct
642 task_grq_unlock(&flags);
646 - * Potentially available exiting-child timeslices are
647 - * retrieved here - this way the parent does not get
648 - * penalised for creating too many threads.
650 - * (this cannot be used to 'generate' timeslices
651 - * artificially, because any timeslice recovered here
652 - * was given away by the parent in the first place.)
654 +/* Nothing to do here */
655 void sched_exit(struct task_struct *p)
657 - struct task_struct *parent;
658 - unsigned long flags;
661 - if (unlikely(p->first_time_slice)) {
662 - int *par_tslice, *p_tslice;
664 - parent = p->parent;
665 - par_tslice = &parent->time_slice;
666 - p_tslice = &p->time_slice;
668 - rq = task_grq_lock(parent, &flags);
669 - /* The real time_slice of the "curr" task is on the rq var.*/
671 - p_tslice = &rq->rq_time_slice;
672 - else if (parent == task_rq(parent)->curr)
673 - par_tslice = &rq->rq_time_slice;
675 - *par_tslice += *p_tslice;
676 - if (unlikely(*par_tslice > timeslice()))
677 - *par_tslice = timeslice();
678 - task_grq_unlock(&flags);
682 #ifdef CONFIG_PREEMPT_NOTIFIERS
683 @@ -1981,7 +2031,7 @@ update_cpu_clock(struct rq *rq, struct t
684 else if (unlikely(time_diff > JIFFIES_TO_NS(1)))
685 time_diff = JIFFIES_TO_NS(1);
687 - rq->rq_time_slice -= time_diff / 1000;
688 + rq->rq_time_slice -= NS_TO_US(time_diff);
690 rq->rq_last_ran = rq->timekeep_clock = rq->clock;
692 @@ -1997,7 +2047,7 @@ static u64 do_task_delta_exec(struct tas
696 - update_rq_clock(rq);
698 ns = rq->clock - rq->rq_last_ran;
699 if (unlikely((s64)ns < 0))
701 @@ -2171,10 +2221,22 @@ void account_idle_ticks(unsigned long ti
705 +static inline void grq_iso_lock(void)
706 + __acquires(grq.iso_lock)
708 + raw_spin_lock(&grq.iso_lock);
711 +static inline void grq_iso_unlock(void)
712 + __releases(grq.iso_lock)
714 + raw_spin_unlock(&grq.iso_lock);
718 * Functions to test for when SCHED_ISO tasks have used their allocated
719 * quota as real time scheduling and convert them back to SCHED_NORMAL.
720 - * Where possible, the data is tested lockless, to avoid grabbing grq_lock
721 + * Where possible, the data is tested lockless, to avoid grabbing iso_lock
722 * because the occasional inaccurate result won't matter. However the
723 * tick data is only ever modified under lock. iso_refractory is only simply
724 * set to 0 or 1 so it's not worth grabbing the lock yet again for that.
725 @@ -2209,21 +2271,21 @@ static unsigned int test_ret_isorefracto
727 static void iso_tick(void)
731 grq.iso_ticks += 100;
736 /* No SCHED_ISO task was running so decrease rq->iso_ticks */
737 static inline void no_iso_tick(void)
742 grq.iso_ticks -= grq.iso_ticks / ISO_PERIOD + 1;
743 if (unlikely(grq.iso_refractory && grq.iso_ticks <
744 ISO_PERIOD * (sched_iso_cpu * 115 / 128)))
745 clear_iso_refractory();
751 @@ -2262,10 +2324,23 @@ static void task_running_tick(struct rq
754 /* SCHED_FIFO tasks never run out of timeslice. */
755 - if (rq_idle(rq) || rq->rq_time_slice > 0 || rq->rq_policy == SCHED_FIFO)
756 + if (rq->rq_policy == SCHED_FIFO)
759 + * Tasks that were scheduled in the first half of a tick are not
760 + * allowed to run into the 2nd half of the next tick if they will
761 + * run out of time slice in the interim. Otherwise, if they have
762 + * less than 100us of time slice left they will be rescheduled.
765 + if (rq->rq_time_slice > HALF_JIFFY_US)
768 + rq->rq_time_slice = 0;
769 + } else if (rq->rq_time_slice >= RESCHED_US)
772 - /* p->time_slice <= 0. We only modify task_struct under grq lock */
773 + /* p->time_slice < RESCHED_US. We only modify task_struct under grq lock */
777 @@ -2286,13 +2361,14 @@ void scheduler_tick(void)
778 struct rq *rq = cpu_rq(cpu);
781 + /* grq lock not grabbed, so only update rq clock */
783 update_cpu_clock(rq, rq->curr, 1);
786 task_running_tick(rq);
789 + rq->last_tick = rq->clock;
790 perf_event_task_tick(rq->curr);
793 @@ -2354,7 +2430,7 @@ EXPORT_SYMBOL(sub_preempt_count);
797 - * Deadline is "now" in gjiffies + (offset by priority). Setting the deadline
798 + * Deadline is "now" in niffies + (offset by priority). Setting the deadline
799 * is the key to everything. It distributes cpu fairly amongst tasks of the
800 * same nice value, it proportions cpu according to nice level, it means the
801 * task that last woke up the longest ago has the earliest deadline, thus
802 @@ -2364,7 +2440,7 @@ EXPORT_SYMBOL(sub_preempt_count);
804 static inline int prio_deadline_diff(int user_prio)
806 - return (prio_ratios[user_prio] * rr_interval * HZ / (1000 * 100)) ? : 1;
807 + return (prio_ratios[user_prio] * rr_interval * (MS_TO_NS(1) / 128));
810 static inline int task_deadline_diff(struct task_struct *p)
811 @@ -2377,25 +2453,33 @@ static inline int static_deadline_diff(i
812 return prio_deadline_diff(USER_PRIO(static_prio));
815 -static inline int longest_deadline_diff(void)
816 +static inline int ms_longest_deadline_diff(void)
818 - return prio_deadline_diff(39);
819 + return NS_TO_MS(prio_deadline_diff(39));
823 * The time_slice is only refilled when it is empty and that is when we set a
826 -static inline void time_slice_expired(struct task_struct *p)
827 +static void time_slice_expired(struct task_struct *p)
829 - reset_first_time_slice(p);
830 p->time_slice = timeslice();
831 - p->deadline = gjiffies + task_deadline_diff(p);
832 + p->deadline = grq.niffies + task_deadline_diff(p);
836 + * Timeslices below RESCHED_US are considered as good as expired as there's no
837 + * point rescheduling when there's so little time left. SCHED_BATCH tasks
838 + * have been flagged be not latency sensitive and likely to be fully CPU
839 + * bound so every time they're rescheduled they have their time_slice
840 + * refilled, but get a new later deadline to have little effect on
841 + * SCHED_NORMAL tasks.
844 static inline void check_deadline(struct task_struct *p)
846 - if (p->time_slice <= 0)
847 + if (p->time_slice < RESCHED_US || batch_task(p))
848 time_slice_expired(p);
851 @@ -2433,7 +2517,7 @@ retry:
852 queue = grq.queue + idx;
853 list_for_each_entry(p, queue, run_list) {
854 /* Make sure cpu affinity is ok */
855 - if (online_cpus(p) && !cpu_isset(cpu, p->cpus_allowed))
856 + if (needs_other_cpu(p, cpu))
858 if (idx < MAX_RT_PRIO) {
859 /* We found an rt task */
860 @@ -2560,12 +2644,14 @@ need_resched_nonpreemptible:
862 schedule_debug(prev);
864 - local_irq_disable();
865 - update_rq_clock(rq);
868 update_cpu_clock(rq, prev, 0);
869 - rq->skip_clock_update = 0;
870 + if (rq->clock - rq->last_tick > HALF_JIFFY_NS)
876 clear_tsk_need_resched(prev);
878 if (prev->state && !(preempt_count() & PREEMPT_ACTIVE)) {
879 @@ -2581,36 +2667,54 @@ need_resched_nonpreemptible:
880 prev->time_slice = rq->rq_time_slice;
881 prev->deadline = rq->rq_deadline;
882 check_deadline(prev);
883 - return_task(prev, deactivate);
884 - /* Task changed affinity off this cpu */
885 - if (unlikely(!cpus_intersects(prev->cpus_allowed,
886 - cpumask_of_cpu(cpu)))) {
887 - if (online_cpus(prev))
888 + prev->last_ran = rq->clock;
890 + /* Task changed affinity off this CPU */
891 + if (needs_other_cpu(prev, cpu))
892 + resched_suitable_idle(prev);
893 + else if (!deactivate) {
894 + if (!queued_notrunning()) {
896 + * We now know prev is the only thing that is
897 + * awaiting CPU so we can bypass rechecking for
898 + * the earliest deadline task and just run it
902 + goto rerun_prev_unlocked;
905 + * If prev got kicked off by a task that has to
906 + * run on this CPU for affinity reasons then
907 + * there may be an idle CPU it can go to.
909 resched_suitable_idle(prev);
912 + return_task(prev, deactivate);
915 - if (likely(queued_notrunning())) {
916 - next = earliest_deadline_task(rq, idle);
918 + if (unlikely(!queued_notrunning())) {
920 + * This CPU is now truly idle as opposed to when idle is
921 + * scheduled as a high priority task in its own right.
924 schedstat_inc(rq, sched_goidle);
928 - prefetch_stack(next);
930 - if (task_idle(next))
931 set_cpuidle_map(cpu);
934 + next = earliest_deadline_task(rq, idle);
936 + prefetch_stack(next);
937 clear_cpuidle_map(cpu);
939 - prev->last_ran = rq->clock;
942 if (likely(prev != next)) {
943 sched_info_switch(prev, next);
944 perf_event_task_sched_out(prev, next);
947 + set_last_task(rq, prev);
948 set_rq_task(rq, next);
951 @@ -2629,6 +2733,7 @@ need_resched_nonpreemptible:
955 +rerun_prev_unlocked:
956 if (unlikely(reacquire_kernel_lock(current) < 0)) {
958 switch_count = &prev->nivcsw;
959 @@ -3324,8 +3429,9 @@ int task_prio(const struct task_struct *
963 - delta = p->deadline - gjiffies;
964 - delta = delta * 40 / longest_deadline_diff();
965 + /* Convert to ms to avoid overflows */
966 + delta = NS_TO_MS(p->deadline - grq.niffies);
967 + delta = delta * 40 / ms_longest_deadline_diff();
968 if (delta > 0 && delta <= 80)
970 if (idleprio_task(p))
971 @@ -3533,7 +3639,7 @@ recheck:
972 raw_spin_unlock_irqrestore(&p->pi_lock, flags);
975 - update_rq_clock(rq);
977 p->sched_reset_on_fork = reset_on_fork;
979 queued = task_queued(p);
980 @@ -4835,7 +4941,7 @@ migration_call(struct notifier_block *nf
981 __setscheduler(idle, rq, SCHED_NORMAL, 0);
982 idle->prio = PRIO_LIMIT;
983 set_rq_task(rq, idle);
984 - update_rq_clock(rq);
989 @@ -6531,12 +6637,14 @@ void __init sched_init(void)
993 - prio_ratios[0] = 100;
994 + prio_ratios[0] = 128;
995 for (i = 1 ; i < PRIO_RANGE ; i++)
996 prio_ratios[i] = prio_ratios[i - 1] * 11 / 10;
998 raw_spin_lock_init(&grq.lock);
999 grq.nr_running = grq.nr_uninterruptible = grq.nr_switches = 0;
1001 + raw_spin_lock_init(&grq.iso_lock);
1002 grq.iso_ticks = grq.iso_refractory = 0;
1004 init_defrootdomain();
1005 @@ -6549,7 +6657,9 @@ void __init sched_init(void)
1007 rq->user_pc = rq->nice_pc = rq->softirq_pc = rq->system_pc =
1008 rq->iowait_pc = rq->idle_pc = 0;
1011 + rq->last_niffy = 0;
1015 Index: linux-2.6.35-bfs/kernel/sysctl.c
1016 ===================================================================
1017 --- linux-2.6.35-bfs.orig/kernel/sysctl.c 2010-09-25 08:18:30.147361076 +1000
1018 +++ linux-2.6.35-bfs/kernel/sysctl.c 2010-09-25 08:20:25.823886848 +1000
1019 @@ -119,7 +119,7 @@ static int __maybe_unused one_hundred =
1020 #ifdef CONFIG_SCHED_BFS
1021 extern int rr_interval;
1022 extern int sched_iso_cpu;
1023 -static int __read_mostly five_thousand = 5000;
1024 +static int __read_mostly one_thousand = 1000;
1026 #ifdef CONFIG_PRINTK
1027 static int ten_thousand = 10000;
1028 @@ -794,7 +794,7 @@ static struct ctl_table kern_table[] = {
1030 .proc_handler = &proc_dointvec_minmax,
1032 - .extra2 = &five_thousand,
1033 + .extra2 = &one_thousand,
1036 .procname = "iso_cpu",