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 include/linux/sched.h | 4
68 kernel/sched_bfs.c | 466 +++++++++++++++++++++-------------
70 4 files changed, 293 insertions(+), 183 deletions(-)
72 Index: linux-2.6.35-bfs/include/linux/sched.h
73 ===================================================================
74 --- linux-2.6.35-bfs.orig/include/linux/sched.h 2010-09-25 08:18:08.792894602 +1000
75 +++ linux-2.6.35-bfs/include/linux/sched.h 2010-09-25 08:20:25.822886826 +1000
76 @@ -1118,7 +1118,7 @@ struct task_struct {
77 int prio, static_prio, normal_prio;
78 unsigned int rt_priority;
79 #ifdef CONFIG_SCHED_BFS
80 - int time_slice, first_time_slice;
81 - unsigned long deadline;
84 struct list_head run_list;
86 @@ -1547,7 +1547,7 @@ static inline void tsk_cpus_current(stru
88 static inline void print_scheduler_version(void)
90 - printk(KERN_INFO"BFS CPU scheduler v0.330 by Con Kolivas ported by ToAsTcfh.\n");
91 + printk(KERN_INFO"BFS CPU scheduler v0.350 by Con Kolivas ported by ToAsTcfh.\n");
94 static inline int iso_task(struct task_struct *p)
95 Index: linux-2.6.35-bfs/kernel/sched_bfs.c
96 ===================================================================
97 --- linux-2.6.35-bfs.orig/kernel/sched_bfs.c 2010-09-25 08:18:08.804894864 +1000
98 +++ linux-2.6.35-bfs/kernel/sched_bfs.c 2010-09-25 08:20:25.827886935 +1000
100 #define MAX_USER_PRIO (USER_PRIO(MAX_PRIO))
101 #define SCHED_PRIO(p) ((p)+MAX_RT_PRIO)
103 -/* Some helpers for converting to/from various scales.*/
105 + * Some helpers for converting to/from various scales. Use shifts to get
106 + * approximate multiples of ten for less overhead.
108 #define JIFFIES_TO_NS(TIME) ((TIME) * (1000000000 / HZ))
109 -#define MS_TO_NS(TIME) ((TIME) * 1000000)
110 -#define MS_TO_US(TIME) ((TIME) * 1000)
111 +#define HALF_JIFFY_NS (1000000000 / HZ / 2)
112 +#define HALF_JIFFY_US (1000000 / HZ / 2)
113 +#define MS_TO_NS(TIME) ((TIME) << 20)
114 +#define MS_TO_US(TIME) ((TIME) << 10)
115 +#define NS_TO_MS(TIME) ((TIME) >> 20)
116 +#define NS_TO_US(TIME) ((TIME) >> 10)
118 +#define RESCHED_US (100) /* Reschedule if less than this many us left */
121 * This is the time all tasks within the same priority round robin.
122 @@ -140,8 +149,9 @@ static inline unsigned long timeslice(vo
126 - * The global runqueue data that all CPUs work off. All data is protected
128 + * The global runqueue data that all CPUs work off. Data is protected either
129 + * by the global grq lock, or the discrete lock that precedes the data in this
134 @@ -150,17 +160,17 @@ struct global_rq {
135 unsigned long long nr_switches;
136 struct list_head queue[PRIO_LIMIT];
137 DECLARE_BITMAP(prio_bitmap, PRIO_LIMIT + 1);
139 - int iso_refractory;
141 unsigned long qnr; /* queued not running */
142 cpumask_t cpu_idle_map;
145 -#if BITS_PER_LONG < 64
146 - unsigned long jiffies;
149 + /* Nanosecond jiffies */
152 + raw_spinlock_t iso_lock;
154 + int iso_refractory;
157 /* There can be only one */
158 @@ -176,8 +186,8 @@ struct rq {
160 unsigned char in_nohz_recently;
162 + struct task_struct *last_task;
164 - unsigned int skip_clock_update;
166 struct task_struct *curr, *idle;
167 struct mm_struct *prev_mm;
168 @@ -213,9 +223,11 @@ struct rq {
169 /* See if all cache siblings are idle */
170 cpumask_t cache_siblings;
172 + u64 last_niffy; /* Last time this RQ updated grq.niffies */
174 + u64 clock, old_clock, last_tick;
178 #ifdef CONFIG_SCHEDSTATS
181 @@ -290,12 +290,4 @@ struct root_domain {
182 static struct root_domain def_root_domain;
185 -static inline int cpu_of(struct rq *rq)
194 @@ -310,17 +313,65 @@ static inline int cpu_of(struct rq *rq)
195 #define for_each_domain(cpu, __sd) \
196 for (__sd = rcu_dereference_check_sched_domain(cpu_rq(cpu)->sd); __sd; __sd = __sd->parent)
198 +static inline void update_rq_clock(struct rq *rq);
201 #define cpu_rq(cpu) (&per_cpu(runqueues, (cpu)))
202 #define this_rq() (&__get_cpu_var(runqueues))
203 #define task_rq(p) cpu_rq(task_cpu(p))
204 #define cpu_curr(cpu) (cpu_rq(cpu)->curr)
205 +static inline int cpu_of(struct rq *rq)
211 + * Niffies are a globally increasing nanosecond counter. Whenever a runqueue
212 + * clock is updated with the grq.lock held, it is an opportunity to update the
213 + * niffies value. Any CPU can update it by adding how much its clock has
214 + * increased since it last updated niffies, minus any added niffies by other
217 +static inline void update_clocks(struct rq *rq)
221 + update_rq_clock(rq);
222 + ndiff = rq->clock - rq->old_clock;
223 + /* old_clock is only updated when we are updating niffies */
224 + rq->old_clock = rq->clock;
225 + ndiff -= grq.niffies - rq->last_niffy;
227 + * Sanity check should sched_clock return bogus values or be limited to
228 + * just jiffy resolution. Some time will always have passed.
230 + if (unlikely(ndiff < 1 || ndiff > MS_TO_NS(rr_interval)))
232 + grq.niffies += ndiff;
233 + rq->last_niffy = grq.niffies;
235 #else /* CONFIG_SMP */
236 static struct rq *uprq;
237 #define cpu_rq(cpu) (uprq)
238 #define this_rq() (uprq)
239 #define task_rq(p) (uprq)
240 #define cpu_curr(cpu) ((uprq)->curr)
241 +static inline int cpu_of(struct rq *rq)
246 +static inline void update_clocks(struct rq *rq)
250 + update_rq_clock(rq);
251 + ndiff = rq->clock - rq->old_clock;
252 + rq->old_clock = rq->clock;
253 + if (unlikely(ndiff < 1 || ndiff > MS_TO_US(rr_interval)))
255 + grq.niffies += ndiff;
258 #define raw_rq() (&__raw_get_cpu_var(runqueues))
260 @@ -335,13 +386,13 @@ static struct rq *uprq;
263 * All common locking functions performed on grq.lock. rq->clock is local to
264 - * the cpu accessing it so it can be modified just with interrupts disabled,
265 - * but looking up task_rq must be done under grq.lock to be safe.
266 + * the CPU accessing it so it can be modified just with interrupts disabled
267 + * when we're not updating niffies.
268 + * Looking up task_rq must be done under grq.lock to be safe.
270 -static inline void update_rq_clock(struct rq *rq)
271 +static inline void update_rq_clock(struct rq *rq)
273 - if (!rq->skip_clock_update)
274 - rq->clock = sched_clock_cpu(cpu_of(rq));
275 + rq->clock = sched_clock_cpu(cpu_of(rq));
278 static inline int task_running(struct task_struct *p)
279 @@ -370,8 +421,8 @@ static inline void grq_lock_irq(void)
280 static inline void time_lock_grq(struct rq *rq)
283 - update_rq_clock(rq);
288 static inline void grq_unlock_irq(void)
289 @@ -405,7 +456,7 @@ static inline struct rq
292 struct rq *rq = task_grq_lock(p, flags);
293 - update_rq_clock(rq);
298 @@ -420,7 +471,7 @@ static inline void time_task_grq_lock_ir
301 struct rq *rq = task_grq_lock_irq(p);
302 - update_rq_clock(rq);
306 static inline void task_grq_unlock_irq(void)
307 @@ -515,33 +566,6 @@ static inline void finish_lock_switch(st
309 #endif /* __ARCH_WANT_UNLOCKED_CTXSW */
312 - * In order to have a monotonic clock that does not wrap we have a 64 bit
313 - * unsigned long that's protected by grq.lock used in place of jiffies on
316 -#if BITS_PER_LONG < 64
317 -static inline void update_gjiffies(void)
319 - if (grq.jiffies != jiffies) {
321 - grq.jiffies = jiffies;
327 -#define gjiffies (grq.jiffies_64)
329 -#else /* BITS_PER_LONG < 64 */
330 -static inline void update_gjiffies(void)
334 -#define gjiffies jiffies
336 -#endif /* BITS_PER_LONG < 64 */
338 static inline int deadline_before(u64 deadline, u64 time)
340 return (deadline < time);
341 @@ -574,17 +598,6 @@ static void dequeue_task(struct task_str
345 - * When a task is freshly forked, the first_time_slice flag is set to say
346 - * it has taken time_slice from its parent and if it exits on this first
347 - * time_slice it can return its time_slice back to the parent.
349 -static inline void reset_first_time_slice(struct task_struct *p)
351 - if (unlikely(p->first_time_slice))
352 - p->first_time_slice = 0;
356 * To determine if it's safe for a task of SCHED_IDLEPRIO to actually run as
357 * an idle task, we ensure none of the following conditions are met.
359 @@ -646,11 +659,11 @@ static inline int task_prio_ratio(struct
361 * task_timeslice - all tasks of all priorities get the exact same timeslice
362 * length. CPU distribution is handled by giving different deadlines to
363 - * tasks of different priorities.
364 + * tasks of different priorities. Use 128 as the base value for fast shifts.
366 static inline int task_timeslice(struct task_struct *p)
368 - return (rr_interval * task_prio_ratio(p) / 100);
369 + return (rr_interval * task_prio_ratio(p) / 128);
373 @@ -702,6 +715,15 @@ static int suitable_idle_cpus(struct tas
375 static void resched_task(struct task_struct *p);
378 + * last_task stores the last non-idle task scheduled on the local rq for
379 + * cache warmth testing.
381 +static inline void set_last_task(struct rq *rq, struct task_struct *p)
386 #define CPUIDLE_CACHE_BUSY (1)
387 #define CPUIDLE_DIFF_CPU (2)
388 #define CPUIDLE_THREAD_BUSY (4)
389 @@ -724,6 +746,9 @@ static void resched_task(struct task_str
390 * Other node, other CPU, idle cache, idle threads.
391 * Other node, other CPU, busy cache, idle threads.
392 * Other node, other CPU, busy threads.
394 + * If p was the last task running on this rq, then regardless of where
395 + * it has been running since then, it is cache warm on this rq.
397 static void resched_best_idle(struct task_struct *p)
399 @@ -756,11 +781,14 @@ static void resched_best_idle(struct tas
400 tmp_rq = cpu_rq(cpu_tmp);
402 if (rq->cpu_locality[cpu_tmp]) {
403 + /* Check rq->last_task hasn't been dereferenced */
404 + if (rq->last_task && p != rq->last_task) {
406 - if (rq->cpu_locality[cpu_tmp] > 1)
407 - ranking |= CPUIDLE_DIFF_NODE;
408 + if (rq->cpu_locality[cpu_tmp] > 1)
409 + ranking |= CPUIDLE_DIFF_NODE;
411 - ranking |= CPUIDLE_DIFF_CPU;
412 + ranking |= CPUIDLE_DIFF_CPU;
415 #ifdef CONFIG_SCHED_MC
416 if (!(tmp_rq->cache_idle(cpu_tmp)))
417 @@ -802,6 +830,11 @@ static inline void resched_suitable_idle
419 cache_distance(struct rq *task_rq, struct rq *rq, struct task_struct *p)
421 + /* Check rq->last_task hasn't been dereferenced */
422 + if (likely(rq->last_task)) {
423 + if (rq->last_task == p)
426 return rq->cpu_locality[cpu_of(task_rq)] * task_timeslice(p);
428 #else /* CONFIG_SMP */
429 @@ -840,6 +873,10 @@ cache_distance(struct rq *task_rq, struc
434 +static inline void set_last_task(struct rq *rq, struct task_struct *p)
437 #endif /* CONFIG_SMP */
440 @@ -887,7 +924,7 @@ static int effective_prio(struct task_st
442 static void activate_task(struct task_struct *p, struct rq *rq)
444 - update_rq_clock(rq);
448 * Sleep time is in units of nanosecs, so shift by 20 to get a
449 @@ -1157,8 +1194,28 @@ EXPORT_SYMBOL_GPL(kick_process);
452 #define rq_idle(rq) ((rq)->rq_prio == PRIO_LIMIT)
453 -#define task_idle(p) ((p)->prio == PRIO_LIMIT)
456 + * RT tasks preempt purely on priority. SCHED_NORMAL tasks preempt on the
457 + * basis of earlier deadlines. SCHED_IDLEPRIO don't preempt anything else or
458 + * between themselves, they cooperatively multitask. An idle rq scores as
459 + * prio PRIO_LIMIT so it is always preempted.
462 +can_preempt(struct task_struct *p, int prio, unsigned long deadline,
463 + unsigned int policy)
465 + /* Better static priority RT task or better policy preemption */
466 + if (p->prio < prio)
468 + if (p->prio > prio)
470 + /* SCHED_NORMAL, BATCH and ISO will preempt based on deadline */
471 + if (!deadline_before(p->deadline, deadline))
476 #ifdef CONFIG_HOTPLUG_CPU
478 * Check to see if there is a task that is affined only to offline CPUs but
479 @@ -1178,14 +1235,20 @@ static inline int online_cpus(struct tas
483 - * RT tasks preempt purely on priority. SCHED_NORMAL tasks preempt on the
484 - * basis of earlier deadlines. SCHED_BATCH, ISO and IDLEPRIO don't preempt
485 - * between themselves, they cooperatively multitask. An idle rq scores as
486 - * prio PRIO_LIMIT so it is always preempted. latest_deadline and
487 - * highest_prio_rq are initialised only to silence the compiler. When
488 - * all else is equal, still prefer this_rq.
489 + * Check to see if p can run on cpu, and if not, whether there are any online
490 + * CPUs it can run on instead.
492 +static inline int needs_other_cpu(struct task_struct *p, int cpu)
494 + if (unlikely(!cpu_isset(cpu, p->cpus_allowed) && online_cpus(p)))
500 + * latest_deadline and highest_prio_rq are initialised only to silence the
501 + * compiler. When all else is equal, still prefer this_rq.
504 static void try_preempt(struct task_struct *p, struct rq *this_rq)
506 struct rq *highest_prio_rq = this_rq;
507 @@ -1193,6 +1256,10 @@ static void try_preempt(struct task_stru
511 + /* IDLEPRIO tasks never preempt anything */
512 + if (p->policy == SCHED_IDLEPRIO)
515 if (suitable_idle_cpus(p)) {
516 resched_best_idle(p);
518 @@ -1219,30 +1286,32 @@ static void try_preempt(struct task_stru
519 offset_deadline = rq->rq_deadline -
520 cache_distance(this_rq, rq, p);
522 - if (rq_prio > highest_prio ||
523 - (deadline_after(offset_deadline, latest_deadline) ||
524 - (offset_deadline == latest_deadline && this_rq == rq))) {
525 + if (rq_prio > highest_prio || (rq_prio == highest_prio &&
526 + deadline_after(offset_deadline, latest_deadline))) {
527 latest_deadline = offset_deadline;
528 highest_prio = rq_prio;
529 highest_prio_rq = rq;
533 - if (p->prio > highest_prio || (p->prio == highest_prio &&
534 - p->policy == SCHED_NORMAL &&
535 - !deadline_before(p->deadline, latest_deadline)))
536 + if (!can_preempt(p, highest_prio, highest_prio_rq->rq_deadline,
537 + highest_prio_rq->rq_policy))
540 - /* p gets to preempt highest_prio_rq->curr */
541 resched_task(highest_prio_rq->curr);
542 - highest_prio_rq->skip_clock_update = 1;
544 #else /* CONFIG_SMP */
545 +static inline int needs_other_cpu(struct task_struct *p, int cpu)
550 static void try_preempt(struct task_struct *p, struct rq *this_rq)
552 - if (p->prio < uprq->rq_prio ||
553 - (p->prio == uprq->rq_prio && p->policy == SCHED_NORMAL &&
554 - deadline_before(p->deadline, uprq->rq_deadline)))
555 + if (p->policy == SCHED_IDLEPRIO)
557 + if (can_preempt(p, uprq->rq_prio, uprq->rq_deadline,
559 resched_task(uprq->curr);
561 #endif /* CONFIG_SMP */
562 @@ -1352,12 +1421,15 @@ int wake_up_state(struct task_struct *p,
563 return try_to_wake_up(p, state, 0);
566 +static void time_slice_expired(struct task_struct *p);
569 * Perform scheduler related setup for a newly forked process p.
570 * p is forked by current.
572 void sched_fork(struct task_struct *p, int clone_flags)
574 + struct task_struct *curr;
578 @@ -1396,10 +1468,11 @@ void sched_fork(struct task_struct *p, i
579 p->sched_reset_on_fork = 0;
584 * Make sure we do not leak PI boosting priority to the child.
586 - p->prio = current->normal_prio;
587 + p->prio = curr->normal_prio;
589 INIT_LIST_HEAD(&p->run_list);
590 #if defined(CONFIG_SCHEDSTATS) || defined(CONFIG_TASK_DELAY_ACCT)
591 @@ -1420,18 +1493,26 @@ void sched_fork(struct task_struct *p, i
592 * total amount of pending timeslices in the system doesn't change,
593 * resulting in more scheduling fairness. If it's negative, it won't
594 * matter since that's the same as being 0. current's time_slice is
595 - * actually in rq_time_slice when it's running.
596 + * actually in rq_time_slice when it's running, as is its last_ran
597 + * value. rq->rq_deadline is only modified within schedule() so it
598 + * is always equal to current->deadline.
600 - rq = task_grq_lock_irq(current);
601 - if (likely(rq->rq_time_slice > 0)) {
602 + rq = task_grq_lock_irq(curr);
603 + if (likely(rq->rq_time_slice >= RESCHED_US * 2)) {
604 rq->rq_time_slice /= 2;
605 + p->time_slice = rq->rq_time_slice;
608 - * The remainder of the first timeslice might be recovered by
609 - * the parent if the child exits early enough.
610 + * Forking task has run out of timeslice. Reschedule it and
611 + * start its child with a new time slice and deadline. The
612 + * child will end up running first because its deadline will
613 + * be slightly earlier.
615 - p->first_time_slice = 1;
616 + rq->rq_time_slice = 0;
617 + set_tsk_need_resched(curr);
618 + time_slice_expired(p);
620 - p->time_slice = rq->rq_time_slice;
621 + p->last_ran = rq->rq_last_ran;
622 task_grq_unlock_irq();
625 @@ -1470,40 +1551,9 @@ void wake_up_new_task(struct task_struct
626 task_grq_unlock(&flags);
630 - * Potentially available exiting-child timeslices are
631 - * retrieved here - this way the parent does not get
632 - * penalised for creating too many threads.
634 - * (this cannot be used to 'generate' timeslices
635 - * artificially, because any timeslice recovered here
636 - * was given away by the parent in the first place.)
638 +/* Nothing to do here */
639 void sched_exit(struct task_struct *p)
641 - struct task_struct *parent;
642 - unsigned long flags;
645 - if (unlikely(p->first_time_slice)) {
646 - int *par_tslice, *p_tslice;
648 - parent = p->parent;
649 - par_tslice = &parent->time_slice;
650 - p_tslice = &p->time_slice;
652 - rq = task_grq_lock(parent, &flags);
653 - /* The real time_slice of the "curr" task is on the rq var.*/
655 - p_tslice = &rq->rq_time_slice;
656 - else if (parent == task_rq(parent)->curr)
657 - par_tslice = &rq->rq_time_slice;
659 - *par_tslice += *p_tslice;
660 - if (unlikely(*par_tslice > timeslice()))
661 - *par_tslice = timeslice();
662 - task_grq_unlock(&flags);
666 #ifdef CONFIG_PREEMPT_NOTIFIERS
667 @@ -1981,7 +2031,7 @@ update_cpu_clock(struct rq *rq, struct t
668 else if (unlikely(time_diff > JIFFIES_TO_NS(1)))
669 time_diff = JIFFIES_TO_NS(1);
671 - rq->rq_time_slice -= time_diff / 1000;
672 + rq->rq_time_slice -= NS_TO_US(time_diff);
674 rq->rq_last_ran = rq->timekeep_clock = rq->clock;
676 @@ -1997,7 +2047,7 @@ static u64 do_task_delta_exec(struct tas
680 - update_rq_clock(rq);
682 ns = rq->clock - rq->rq_last_ran;
683 if (unlikely((s64)ns < 0))
685 @@ -2171,10 +2221,22 @@ void account_idle_ticks(unsigned long ti
689 +static inline void grq_iso_lock(void)
690 + __acquires(grq.iso_lock)
692 + raw_spin_lock(&grq.iso_lock);
695 +static inline void grq_iso_unlock(void)
696 + __releases(grq.iso_lock)
698 + raw_spin_unlock(&grq.iso_lock);
702 * Functions to test for when SCHED_ISO tasks have used their allocated
703 * quota as real time scheduling and convert them back to SCHED_NORMAL.
704 - * Where possible, the data is tested lockless, to avoid grabbing grq_lock
705 + * Where possible, the data is tested lockless, to avoid grabbing iso_lock
706 * because the occasional inaccurate result won't matter. However the
707 * tick data is only ever modified under lock. iso_refractory is only simply
708 * set to 0 or 1 so it's not worth grabbing the lock yet again for that.
709 @@ -2209,21 +2271,21 @@ static unsigned int test_ret_isorefracto
711 static void iso_tick(void)
715 grq.iso_ticks += 100;
720 /* No SCHED_ISO task was running so decrease rq->iso_ticks */
721 static inline void no_iso_tick(void)
726 grq.iso_ticks -= grq.iso_ticks / ISO_PERIOD + 1;
727 if (unlikely(grq.iso_refractory && grq.iso_ticks <
728 ISO_PERIOD * (sched_iso_cpu * 115 / 128)))
729 clear_iso_refractory();
735 @@ -2262,10 +2324,23 @@ static void task_running_tick(struct rq
738 /* SCHED_FIFO tasks never run out of timeslice. */
739 - if (rq_idle(rq) || rq->rq_time_slice > 0 || rq->rq_policy == SCHED_FIFO)
740 + if (rq->rq_policy == SCHED_FIFO)
743 + * Tasks that were scheduled in the first half of a tick are not
744 + * allowed to run into the 2nd half of the next tick if they will
745 + * run out of time slice in the interim. Otherwise, if they have
746 + * less than 100us of time slice left they will be rescheduled.
749 + if (rq->rq_time_slice > HALF_JIFFY_US)
752 + rq->rq_time_slice = 0;
753 + } else if (rq->rq_time_slice >= RESCHED_US)
756 - /* p->time_slice <= 0. We only modify task_struct under grq lock */
757 + /* p->time_slice < RESCHED_US. We only modify task_struct under grq lock */
761 @@ -2286,13 +2361,14 @@ void scheduler_tick(void)
762 struct rq *rq = cpu_rq(cpu);
765 + /* grq lock not grabbed, so only update rq clock */
767 update_cpu_clock(rq, rq->curr, 1);
770 task_running_tick(rq);
773 + rq->last_tick = rq->clock;
774 perf_event_task_tick(rq->curr);
777 @@ -2354,7 +2430,7 @@ EXPORT_SYMBOL(sub_preempt_count);
781 - * Deadline is "now" in gjiffies + (offset by priority). Setting the deadline
782 + * Deadline is "now" in niffies + (offset by priority). Setting the deadline
783 * is the key to everything. It distributes cpu fairly amongst tasks of the
784 * same nice value, it proportions cpu according to nice level, it means the
785 * task that last woke up the longest ago has the earliest deadline, thus
786 @@ -2364,7 +2440,7 @@ EXPORT_SYMBOL(sub_preempt_count);
788 static inline int prio_deadline_diff(int user_prio)
790 - return (prio_ratios[user_prio] * rr_interval * HZ / (1000 * 100)) ? : 1;
791 + return (prio_ratios[user_prio] * rr_interval * (MS_TO_NS(1) / 128));
794 static inline int task_deadline_diff(struct task_struct *p)
795 @@ -2377,25 +2453,33 @@ static inline int static_deadline_diff(i
796 return prio_deadline_diff(USER_PRIO(static_prio));
799 -static inline int longest_deadline_diff(void)
800 +static inline int ms_longest_deadline_diff(void)
802 - return prio_deadline_diff(39);
803 + return NS_TO_MS(prio_deadline_diff(39));
807 * The time_slice is only refilled when it is empty and that is when we set a
810 -static inline void time_slice_expired(struct task_struct *p)
811 +static void time_slice_expired(struct task_struct *p)
813 - reset_first_time_slice(p);
814 p->time_slice = timeslice();
815 - p->deadline = gjiffies + task_deadline_diff(p);
816 + p->deadline = grq.niffies + task_deadline_diff(p);
820 + * Timeslices below RESCHED_US are considered as good as expired as there's no
821 + * point rescheduling when there's so little time left. SCHED_BATCH tasks
822 + * have been flagged be not latency sensitive and likely to be fully CPU
823 + * bound so every time they're rescheduled they have their time_slice
824 + * refilled, but get a new later deadline to have little effect on
825 + * SCHED_NORMAL tasks.
828 static inline void check_deadline(struct task_struct *p)
830 - if (p->time_slice <= 0)
831 + if (p->time_slice < RESCHED_US || batch_task(p))
832 time_slice_expired(p);
835 @@ -2433,7 +2517,7 @@ retry:
836 queue = grq.queue + idx;
837 list_for_each_entry(p, queue, run_list) {
838 /* Make sure cpu affinity is ok */
839 - if (online_cpus(p) && !cpu_isset(cpu, p->cpus_allowed))
840 + if (needs_other_cpu(p, cpu))
842 if (idx < MAX_RT_PRIO) {
843 /* We found an rt task */
844 @@ -2560,12 +2644,14 @@ need_resched_nonpreemptible:
846 schedule_debug(prev);
848 - local_irq_disable();
849 - update_rq_clock(rq);
852 update_cpu_clock(rq, prev, 0);
853 - rq->skip_clock_update = 0;
854 + if (rq->clock - rq->last_tick > HALF_JIFFY_NS)
860 clear_tsk_need_resched(prev);
862 if (prev->state && !(preempt_count() & PREEMPT_ACTIVE)) {
863 @@ -2581,36 +2667,54 @@ need_resched_nonpreemptible:
864 prev->time_slice = rq->rq_time_slice;
865 prev->deadline = rq->rq_deadline;
866 check_deadline(prev);
867 - return_task(prev, deactivate);
868 - /* Task changed affinity off this cpu */
869 - if (unlikely(!cpus_intersects(prev->cpus_allowed,
870 - cpumask_of_cpu(cpu)))) {
871 - if (online_cpus(prev))
872 + prev->last_ran = rq->clock;
874 + /* Task changed affinity off this CPU */
875 + if (needs_other_cpu(prev, cpu))
876 + resched_suitable_idle(prev);
877 + else if (!deactivate) {
878 + if (!queued_notrunning()) {
880 + * We now know prev is the only thing that is
881 + * awaiting CPU so we can bypass rechecking for
882 + * the earliest deadline task and just run it
886 + goto rerun_prev_unlocked;
889 + * If prev got kicked off by a task that has to
890 + * run on this CPU for affinity reasons then
891 + * there may be an idle CPU it can go to.
893 resched_suitable_idle(prev);
896 + return_task(prev, deactivate);
899 - if (likely(queued_notrunning())) {
900 - next = earliest_deadline_task(rq, idle);
902 + if (unlikely(!queued_notrunning())) {
904 + * This CPU is now truly idle as opposed to when idle is
905 + * scheduled as a high priority task in its own right.
908 schedstat_inc(rq, sched_goidle);
912 - prefetch_stack(next);
914 - if (task_idle(next))
915 set_cpuidle_map(cpu);
918 + next = earliest_deadline_task(rq, idle);
920 + prefetch_stack(next);
921 clear_cpuidle_map(cpu);
923 - prev->last_ran = rq->clock;
926 if (likely(prev != next)) {
927 sched_info_switch(prev, next);
928 perf_event_task_sched_out(prev, next);
931 + set_last_task(rq, prev);
932 set_rq_task(rq, next);
935 @@ -2629,6 +2733,7 @@ need_resched_nonpreemptible:
939 +rerun_prev_unlocked:
940 if (unlikely(reacquire_kernel_lock(current) < 0)) {
942 switch_count = &prev->nivcsw;
943 @@ -3324,8 +3429,9 @@ int task_prio(const struct task_struct *
947 - delta = p->deadline - gjiffies;
948 - delta = delta * 40 / longest_deadline_diff();
949 + /* Convert to ms to avoid overflows */
950 + delta = NS_TO_MS(p->deadline - grq.niffies);
951 + delta = delta * 40 / ms_longest_deadline_diff();
952 if (delta > 0 && delta <= 80)
954 if (idleprio_task(p))
955 @@ -3533,7 +3639,7 @@ recheck:
956 raw_spin_unlock_irqrestore(&p->pi_lock, flags);
959 - update_rq_clock(rq);
961 p->sched_reset_on_fork = reset_on_fork;
963 queued = task_queued(p);
964 @@ -4835,7 +4941,7 @@ migration_call(struct notifier_block *nf
965 __setscheduler(idle, rq, SCHED_NORMAL, 0);
966 idle->prio = PRIO_LIMIT;
967 set_rq_task(rq, idle);
968 - update_rq_clock(rq);
973 @@ -6531,12 +6637,14 @@ void __init sched_init(void)
977 - prio_ratios[0] = 100;
978 + prio_ratios[0] = 128;
979 for (i = 1 ; i < PRIO_RANGE ; i++)
980 prio_ratios[i] = prio_ratios[i - 1] * 11 / 10;
982 raw_spin_lock_init(&grq.lock);
983 grq.nr_running = grq.nr_uninterruptible = grq.nr_switches = 0;
985 + raw_spin_lock_init(&grq.iso_lock);
986 grq.iso_ticks = grq.iso_refractory = 0;
988 init_defrootdomain();
989 @@ -6549,7 +6657,9 @@ void __init sched_init(void)
991 rq->user_pc = rq->nice_pc = rq->softirq_pc = rq->system_pc =
992 rq->iowait_pc = rq->idle_pc = 0;
995 + rq->last_niffy = 0;
999 Index: linux-2.6.35-bfs/kernel/sysctl.c
1000 ===================================================================
1001 --- linux-2.6.35-bfs.orig/kernel/sysctl.c 2010-09-25 08:18:30.147361076 +1000
1002 +++ linux-2.6.35-bfs/kernel/sysctl.c 2010-09-25 08:20:25.823886848 +1000
1003 @@ -119,7 +119,7 @@ static int __maybe_unused one_hundred =
1004 #ifdef CONFIG_SCHED_BFS
1005 extern int rr_interval;
1006 extern int sched_iso_cpu;
1007 -static int __read_mostly five_thousand = 5000;
1008 +static int __read_mostly one_thousand = 1000;
1010 #ifdef CONFIG_PRINTK
1011 static int ten_thousand = 10000;
1012 @@ -794,7 +794,7 @@ static struct ctl_table kern_table[] = {
1014 .proc_handler = &proc_dointvec_minmax,
1016 - .extra2 = &five_thousand,
1017 + .extra2 = &one_thousand,
1020 .procname = "iso_cpu",