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: kernel-2.6.28/include/linux/sched.h
73 ===================================================================
74 --- kernel-2.6.28.orig/include/linux/sched.h
75 +++ kernel-2.6.28/include/linux/sched.h
76 @@ -1121,8 +1121,8 @@ 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 u64 sched_time; /* sched_clock time spent running */
87 @@ -1426,7 +1426,7 @@ static inline void tsk_cpus_current(stru
89 static inline void print_scheduler_version(void)
91 - printk(KERN_INFO"BFS CPU scheduler v0.330 by Con Kolivas ported by ToAsTcfh.\n");
92 + printk(KERN_INFO"BFS CPU scheduler v0.350 by Con Kolivas ported by ToAsTcfh.\n");
95 static inline int iso_task(struct task_struct *p)
96 Index: kernel-2.6.28/kernel/sched_bfs.c
97 ===================================================================
98 --- kernel-2.6.28.orig/kernel/sched_bfs.c
99 +++ kernel-2.6.28/kernel/sched_bfs.c
100 @@ -102,10 +102,19 @@
101 #define MAX_USER_PRIO (USER_PRIO(MAX_PRIO))
102 #define SCHED_PRIO(p) ((p)+MAX_RT_PRIO)
104 -/* Some helpers for converting to/from various scales.*/
106 + * Some helpers for converting to/from various scales. Use shifts to get
107 + * approximate multiples of ten for less overhead.
109 #define JIFFIES_TO_NS(TIME) ((TIME) * (1000000000 / HZ))
110 -#define MS_TO_NS(TIME) ((TIME) * 1000000)
111 -#define MS_TO_US(TIME) ((TIME) * 1000)
112 +#define HALF_JIFFY_NS (1000000000 / HZ / 2)
113 +#define HALF_JIFFY_US (1000000 / HZ / 2)
114 +#define MS_TO_NS(TIME) ((TIME) << 20)
115 +#define MS_TO_US(TIME) ((TIME) << 10)
116 +#define NS_TO_MS(TIME) ((TIME) >> 20)
117 +#define NS_TO_US(TIME) ((TIME) >> 10)
119 +#define RESCHED_US (100) /* Reschedule if less than this many us left */
123 @@ -157,8 +166,9 @@ static inline unsigned long timeslice(vo
127 - * The global runqueue data that all CPUs work off. All data is protected
129 + * The global runqueue data that all CPUs work off. Data is protected either
130 + * by the global grq lock, or the discrete lock that precedes the data in this
135 @@ -167,17 +177,17 @@ struct global_rq {
136 unsigned long long nr_switches;
137 struct list_head queue[PRIO_LIMIT];
138 DECLARE_BITMAP(prio_bitmap, PRIO_LIMIT + 1);
140 - int iso_refractory;
142 unsigned long qnr; /* queued not running */
143 cpumask_t cpu_idle_map;
146 -#if BITS_PER_LONG < 64
147 - unsigned long jiffies;
150 + /* Nanosecond jiffies */
153 + spinlock_t iso_lock;
155 + int iso_refractory;
158 /* There can be only one */
159 @@ -192,8 +202,8 @@ struct rq {
161 unsigned char in_nohz_recently;
163 + struct task_struct *last_task;
165 - unsigned int skip_clock_update;
167 struct task_struct *curr, *idle;
168 struct mm_struct *prev_mm;
169 @@ -229,9 +239,11 @@ struct rq {
170 /* See if all cache siblings are idle */
171 cpumask_t cache_siblings;
173 + u64 last_niffy; /* Last time this RQ updated grq.niffies */
175 + u64 clock, old_clock, last_tick;
179 #ifdef CONFIG_SCHEDSTATS
182 @@ -290,14 +302,6 @@ struct root_domain {
183 static struct root_domain def_root_domain;
186 -static inline int cpu_of(struct rq *rq)
196 * The domain tree (rq->sd) is protected by RCU's quiescent state transition.
197 @@ -309,17 +313,65 @@ static inline int cpu_of(struct rq *rq)
198 #define for_each_domain(cpu, __sd) \
199 for (__sd = rcu_dereference(cpu_rq(cpu)->sd); __sd; __sd = __sd->parent)
201 +static inline void update_rq_clock(struct rq *rq);
204 #define cpu_rq(cpu) (&per_cpu(runqueues, (cpu)))
205 #define this_rq() (&__get_cpu_var(runqueues))
206 #define task_rq(p) cpu_rq(task_cpu(p))
207 #define cpu_curr(cpu) (cpu_rq(cpu)->curr)
208 +static inline int cpu_of(struct rq *rq)
214 + * Niffies are a globally increasing nanosecond counter. Whenever a runqueue
215 + * clock is updated with the grq.lock held, it is an opportunity to update the
216 + * niffies value. Any CPU can update it by adding how much its clock has
217 + * increased since it last updated niffies, minus any added niffies by other
220 +static inline void update_clocks(struct rq *rq)
224 + update_rq_clock(rq);
225 + ndiff = rq->clock - rq->old_clock;
226 + /* old_clock is only updated when we are updating niffies */
227 + rq->old_clock = rq->clock;
228 + ndiff -= grq.niffies - rq->last_niffy;
230 + * Sanity check should sched_clock return bogus values or be limited to
231 + * just jiffy resolution. Some time will always have passed.
233 + if (unlikely(ndiff < 1 || ndiff > MS_TO_NS(rr_interval)))
235 + grq.niffies += ndiff;
236 + rq->last_niffy = grq.niffies;
238 #else /* CONFIG_SMP */
239 static struct rq *uprq;
240 #define cpu_rq(cpu) (uprq)
241 #define this_rq() (uprq)
242 #define task_rq(p) (uprq)
243 #define cpu_curr(cpu) ((uprq)->curr)
244 +static inline int cpu_of(struct rq *rq)
249 +static inline void update_clocks(struct rq *rq)
253 + update_rq_clock(rq);
254 + ndiff = rq->clock - rq->old_clock;
255 + rq->old_clock = rq->clock;
256 + if (unlikely(ndiff < 1 || ndiff > MS_TO_US(rr_interval)))
258 + grq.niffies += ndiff;
262 #include "sched_stats.h"
263 @@ -333,13 +385,13 @@ static struct rq *uprq;
266 * All common locking functions performed on grq.lock. rq->clock is local to
267 - * the cpu accessing it so it can be modified just with interrupts disabled,
268 - * but looking up task_rq must be done under grq.lock to be safe.
269 + * the CPU accessing it so it can be modified just with interrupts disabled
270 + * when we're not updating niffies.
271 + * Looking up task_rq must be done under grq.lock to be safe.
273 static inline void update_rq_clock(struct rq *rq)
275 - if (!rq->skip_clock_update)
276 - rq->clock = sched_clock_cpu(cpu_of(rq));
277 + rq->clock = sched_clock_cpu(cpu_of(rq));
280 static inline int task_running(struct task_struct *p)
281 @@ -368,8 +420,8 @@ static inline void grq_lock_irq(void)
282 static inline void time_lock_grq(struct rq *rq)
285 - update_rq_clock(rq);
290 static inline void grq_unlock_irq(void)
291 @@ -403,7 +455,7 @@ static inline struct rq
294 struct rq *rq = task_grq_lock(p, flags);
295 - update_rq_clock(rq);
300 @@ -418,7 +470,7 @@ static inline void time_task_grq_lock_ir
303 struct rq *rq = task_grq_lock_irq(p);
304 - update_rq_clock(rq);
308 static inline void task_grq_unlock_irq(void)
309 @@ -513,33 +565,6 @@ static inline void finish_lock_switch(st
311 #endif /* __ARCH_WANT_UNLOCKED_CTXSW */
314 - * In order to have a monotonic clock that does not wrap we have a 64 bit
315 - * unsigned long that's protected by grq.lock used in place of jiffies on
318 -#if BITS_PER_LONG < 64
319 -static inline void update_gjiffies(void)
321 - if (grq.jiffies != jiffies) {
323 - grq.jiffies = jiffies;
329 -#define gjiffies (grq.jiffies_64)
331 -#else /* BITS_PER_LONG < 64 */
332 -static inline void update_gjiffies(void)
336 -#define gjiffies jiffies
338 -#endif /* BITS_PER_LONG < 64 */
340 static inline int deadline_before(u64 deadline, u64 time)
342 return (deadline < time);
343 @@ -572,17 +597,6 @@ static void dequeue_task(struct task_str
347 - * When a task is freshly forked, the first_time_slice flag is set to say
348 - * it has taken time_slice from its parent and if it exits on this first
349 - * time_slice it can return its time_slice back to the parent.
351 -static inline void reset_first_time_slice(struct task_struct *p)
353 - if (unlikely(p->first_time_slice))
354 - p->first_time_slice = 0;
358 * To determine if it's safe for a task of SCHED_IDLEPRIO to actually run as
359 * an idle task, we ensure none of the following conditions are met.
361 @@ -644,11 +658,11 @@ static inline int task_prio_ratio(struct
363 * task_timeslice - all tasks of all priorities get the exact same timeslice
364 * length. CPU distribution is handled by giving different deadlines to
365 - * tasks of different priorities.
366 + * tasks of different priorities. Use 128 as the base value for fast shifts.
368 static inline int task_timeslice(struct task_struct *p)
370 - return (rr_interval * task_prio_ratio(p) / 100);
371 + return (rr_interval * task_prio_ratio(p) / 128);
375 @@ -700,6 +714,15 @@ static int suitable_idle_cpus(struct tas
377 static void resched_task(struct task_struct *p);
380 + * last_task stores the last non-idle task scheduled on the local rq for
381 + * cache warmth testing.
383 +static inline void set_last_task(struct rq *rq, struct task_struct *p)
388 #define CPUIDLE_CACHE_BUSY (1)
389 #define CPUIDLE_DIFF_CPU (2)
390 #define CPUIDLE_THREAD_BUSY (4)
391 @@ -722,6 +745,9 @@ static void resched_task(struct task_str
392 * Other node, other CPU, idle cache, idle threads.
393 * Other node, other CPU, busy cache, idle threads.
394 * Other node, other CPU, busy threads.
396 + * If p was the last task running on this rq, then regardless of where
397 + * it has been running since then, it is cache warm on this rq.
399 static void resched_best_idle(struct task_struct *p)
401 @@ -754,11 +780,14 @@ static void resched_best_idle(struct tas
402 tmp_rq = cpu_rq(cpu_tmp);
404 if (rq->cpu_locality[cpu_tmp]) {
405 + /* Check rq->last_task hasn't been dereferenced */
406 + if (rq->last_task && p != rq->last_task) {
408 - if (rq->cpu_locality[cpu_tmp] > 1)
409 - ranking |= CPUIDLE_DIFF_NODE;
410 + if (rq->cpu_locality[cpu_tmp] > 1)
411 + ranking |= CPUIDLE_DIFF_NODE;
413 - ranking |= CPUIDLE_DIFF_CPU;
414 + ranking |= CPUIDLE_DIFF_CPU;
417 #ifdef CONFIG_SCHED_MC
418 if (!(tmp_rq->cache_idle(cpu_tmp)))
419 @@ -800,6 +829,11 @@ static inline void resched_suitable_idle
421 cache_distance(struct rq *task_rq, struct rq *rq, struct task_struct *p)
423 + /* Check rq->last_task hasn't been dereferenced */
424 + if (likely(rq->last_task)) {
425 + if (rq->last_task == p)
428 return rq->cpu_locality[cpu_of(task_rq)] * task_timeslice(p);
430 #else /* CONFIG_SMP */
431 @@ -839,6 +873,10 @@ cache_distance(struct rq *task_rq, struc
436 +static inline void set_last_task(struct rq *rq, struct task_struct *p)
439 #endif /* CONFIG_SMP */
442 @@ -886,7 +924,7 @@ static int effective_prio(struct task_st
444 static void activate_task(struct task_struct *p, struct rq *rq)
446 - update_rq_clock(rq);
450 * Sleep time is in units of nanosecs, so shift by 20 to get a
451 @@ -1157,8 +1195,28 @@ void kick_process(struct task_struct *p)
454 #define rq_idle(rq) ((rq)->rq_prio == PRIO_LIMIT)
455 -#define task_idle(p) ((p)->prio == PRIO_LIMIT)
458 + * RT tasks preempt purely on priority. SCHED_NORMAL tasks preempt on the
459 + * basis of earlier deadlines. SCHED_IDLEPRIO don't preempt anything else or
460 + * between themselves, they cooperatively multitask. An idle rq scores as
461 + * prio PRIO_LIMIT so it is always preempted.
464 +can_preempt(struct task_struct *p, int prio, unsigned long deadline,
465 + unsigned int policy)
467 + /* Better static priority RT task or better policy preemption */
468 + if (p->prio < prio)
470 + if (p->prio > prio)
472 + /* SCHED_NORMAL, BATCH and ISO will preempt based on deadline */
473 + if (!deadline_before(p->deadline, deadline))
478 #ifdef CONFIG_HOTPLUG_CPU
480 * Check to see if there is a task that is affined only to offline CPUs but
481 @@ -1179,14 +1237,20 @@ static inline int online_cpus(struct tas
485 - * RT tasks preempt purely on priority. SCHED_NORMAL tasks preempt on the
486 - * basis of earlier deadlines. SCHED_BATCH, ISO and IDLEPRIO don't preempt
487 - * between themselves, they cooperatively multitask. An idle rq scores as
488 - * prio PRIO_LIMIT so it is always preempted. latest_deadline and
489 - * highest_prio_rq are initialised only to silence the compiler. When
490 - * all else is equal, still prefer this_rq.
491 + * Check to see if p can run on cpu, and if not, whether there are any online
492 + * CPUs it can run on instead.
494 +static inline int needs_other_cpu(struct task_struct *p, int cpu)
496 + if (unlikely(!cpu_isset(cpu, p->cpus_allowed) && online_cpus(p)))
502 + * latest_deadline and highest_prio_rq are initialised only to silence the
503 + * compiler. When all else is equal, still prefer this_rq.
506 static void try_preempt(struct task_struct *p, struct rq *this_rq)
508 struct rq *highest_prio_rq = this_rq;
509 @@ -1194,6 +1258,10 @@ static void try_preempt(struct task_stru
513 + /* IDLEPRIO tasks never preempt anything */
514 + if (p->policy == SCHED_IDLEPRIO)
517 if (suitable_idle_cpus(p)) {
518 resched_best_idle(p);
520 @@ -1220,30 +1288,32 @@ static void try_preempt(struct task_stru
521 offset_deadline = rq->rq_deadline -
522 cache_distance(this_rq, rq, p);
524 - if (rq_prio > highest_prio ||
525 - (deadline_after(offset_deadline, latest_deadline) ||
526 - (offset_deadline == latest_deadline && this_rq == rq))) {
527 + if (rq_prio > highest_prio || (rq_prio == highest_prio &&
528 + deadline_after(offset_deadline, latest_deadline))) {
529 latest_deadline = offset_deadline;
530 highest_prio = rq_prio;
531 highest_prio_rq = rq;
535 - if (p->prio > highest_prio || (p->prio == highest_prio &&
536 - p->policy == SCHED_NORMAL &&
537 - !deadline_before(p->deadline, latest_deadline)))
538 + if (!can_preempt(p, highest_prio, highest_prio_rq->rq_deadline,
539 + highest_prio_rq->rq_policy))
542 - /* p gets to preempt highest_prio_rq->curr */
543 resched_task(highest_prio_rq->curr);
544 - highest_prio_rq->skip_clock_update = 1;
546 #else /* CONFIG_SMP */
547 +static inline int needs_other_cpu(struct task_struct *p, int cpu)
552 static void try_preempt(struct task_struct *p, struct rq *this_rq)
554 - if (p->prio < uprq->rq_prio ||
555 - (p->prio == uprq->rq_prio && p->policy == SCHED_NORMAL &&
556 - deadline_before(p->deadline, uprq->rq_deadline)))
557 + if (p->policy == SCHED_IDLEPRIO)
559 + if (can_preempt(p, uprq->rq_prio, uprq->rq_deadline,
561 resched_task(uprq->curr);
563 #endif /* CONFIG_SMP */
564 @@ -1331,12 +1401,15 @@ int wake_up_state(struct task_struct *p,
565 return try_to_wake_up(p, state, 0);
568 +static void time_slice_expired(struct task_struct *p);
571 * Perform scheduler related setup for a newly forked process p.
572 * p is forked by current.
574 void sched_fork(struct task_struct *p, int clone_flags)
576 + struct task_struct *curr;
580 @@ -1376,10 +1449,11 @@ void sched_fork(struct task_struct *p, i
581 p->sched_reset_on_fork = 0;
586 * Make sure we do not leak PI boosting priority to the child:
588 - p->prio = current->normal_prio;
589 + p->prio = curr->normal_prio;
591 INIT_LIST_HEAD(&p->run_list);
592 #if defined(CONFIG_SCHEDSTATS) || defined(CONFIG_TASK_DELAY_ACCT)
593 @@ -1400,18 +1474,26 @@ void sched_fork(struct task_struct *p, i
594 * total amount of pending timeslices in the system doesn't change,
595 * resulting in more scheduling fairness. If it's negative, it won't
596 * matter since that's the same as being 0. current's time_slice is
597 - * actually in rq_time_slice when it's running.
598 + * actually in rq_time_slice when it's running, as is its last_ran
599 + * value. rq->rq_deadline is only modified within schedule() so it
600 + * is always equal to current->deadline.
602 - rq = task_grq_lock_irq(current);
603 - if (likely(rq->rq_time_slice > 0)) {
604 + rq = task_grq_lock_irq(curr);
605 + if (likely(rq->rq_time_slice >= RESCHED_US * 2)) {
606 rq->rq_time_slice /= 2;
607 + p->time_slice = rq->rq_time_slice;
610 - * The remainder of the first timeslice might be recovered by
611 - * the parent if the child exits early enough.
612 + * Forking task has run out of timeslice. Reschedule it and
613 + * start its child with a new time slice and deadline. The
614 + * child will end up running first because its deadline will
615 + * be slightly earlier.
617 - p->first_time_slice = 1;
618 + rq->rq_time_slice = 0;
619 + set_tsk_need_resched(curr);
620 + time_slice_expired(p);
622 - p->time_slice = rq->rq_time_slice;
623 + p->last_ran = rq->rq_last_ran;
624 task_grq_unlock_irq();
627 @@ -1452,40 +1534,9 @@ void wake_up_new_task(struct task_struct
628 task_grq_unlock(&flags);
632 - * Potentially available exiting-child timeslices are
633 - * retrieved here - this way the parent does not get
634 - * penalised for creating too many threads.
636 - * (this cannot be used to 'generate' timeslices
637 - * artificially, because any timeslice recovered here
638 - * was given away by the parent in the first place.)
640 +/* Nothing to do here */
641 void sched_exit(struct task_struct *p)
643 - struct task_struct *parent;
644 - unsigned long flags;
647 - if (unlikely(p->first_time_slice)) {
648 - int *par_tslice, *p_tslice;
650 - parent = p->parent;
651 - par_tslice = &parent->time_slice;
652 - p_tslice = &p->time_slice;
654 - rq = task_grq_lock(parent, &flags);
655 - /* The real time_slice of the "curr" task is on the rq var.*/
657 - p_tslice = &rq->rq_time_slice;
658 - else if (parent == task_rq(parent)->curr)
659 - par_tslice = &rq->rq_time_slice;
661 - *par_tslice += *p_tslice;
662 - if (unlikely(*par_tslice > timeslice()))
663 - *par_tslice = timeslice();
664 - task_grq_unlock(&flags);
668 #ifdef CONFIG_PREEMPT_NOTIFIERS
669 @@ -1900,7 +1951,7 @@ update_cpu_clock(struct rq *rq, struct t
670 else if (unlikely(time_diff > JIFFIES_TO_NS(1)))
671 time_diff = JIFFIES_TO_NS(1);
673 - rq->rq_time_slice -= time_diff / 1000;
674 + rq->rq_time_slice -= NS_TO_US(time_diff);
676 rq->rq_last_ran = rq->timekeep_clock = rq->clock;
678 @@ -1916,7 +1967,7 @@ static u64 do_task_delta_exec(struct tas
682 - update_rq_clock(rq);
684 ns = rq->clock - rq->rq_last_ran;
685 if (unlikely((s64)ns < 0))
687 @@ -2090,10 +2141,22 @@ void account_idle_ticks(unsigned long ti
691 +static inline void grq_iso_lock(void)
692 + __acquires(grq.iso_lock)
694 + spin_lock(&grq.iso_lock);
697 +static inline void grq_iso_unlock(void)
698 + __releases(grq.iso_lock)
700 + spin_unlock(&grq.iso_lock);
704 * Functions to test for when SCHED_ISO tasks have used their allocated
705 * quota as real time scheduling and convert them back to SCHED_NORMAL.
706 - * Where possible, the data is tested lockless, to avoid grabbing grq_lock
707 + * Where possible, the data is tested lockless, to avoid grabbing iso_lock
708 * because the occasional inaccurate result won't matter. However the
709 * tick data is only ever modified under lock. iso_refractory is only simply
710 * set to 0 or 1 so it's not worth grabbing the lock yet again for that.
711 @@ -2128,21 +2191,21 @@ static unsigned int test_ret_isorefracto
713 static void iso_tick(void)
717 grq.iso_ticks += 100;
722 /* No SCHED_ISO task was running so decrease rq->iso_ticks */
723 static inline void no_iso_tick(void)
728 grq.iso_ticks -= grq.iso_ticks / ISO_PERIOD + 1;
729 if (unlikely(grq.iso_refractory && grq.iso_ticks <
730 ISO_PERIOD * (sched_iso_cpu * 115 / 128)))
731 clear_iso_refractory();
737 @@ -2181,10 +2244,23 @@ static void task_running_tick(struct rq
740 /* SCHED_FIFO tasks never run out of timeslice. */
741 - if (rq_idle(rq) || rq->rq_time_slice > 0 || rq->rq_policy == SCHED_FIFO)
742 + if (rq->rq_policy == SCHED_FIFO)
745 + * Tasks that were scheduled in the first half of a tick are not
746 + * allowed to run into the 2nd half of the next tick if they will
747 + * run out of time slice in the interim. Otherwise, if they have
748 + * less than 100us of time slice left they will be rescheduled.
751 + if (rq->rq_time_slice > HALF_JIFFY_US)
754 + rq->rq_time_slice = 0;
755 + } else if (rq->rq_time_slice >= RESCHED_US)
758 - /* p->time_slice <= 0. We only modify task_struct under grq lock */
759 + /* p->time_slice < RESCHED_US. We only modify task_struct under grq lock */
763 @@ -2205,13 +2281,14 @@ void scheduler_tick(void)
764 struct rq *rq = cpu_rq(cpu);
767 + /* grq lock not grabbed, so only update rq clock */
769 update_cpu_clock(rq, rq->curr, 1);
772 task_running_tick(rq);
775 + rq->last_tick = rq->clock;
778 #if defined(CONFIG_PREEMPT) && (defined(CONFIG_DEBUG_PREEMPT) || \
779 @@ -2273,7 +2350,7 @@ EXPORT_SYMBOL(sub_preempt_count);
783 - * Deadline is "now" in gjiffies + (offset by priority). Setting the deadline
784 + * Deadline is "now" in niffies + (offset by priority). Setting the deadline
785 * is the key to everything. It distributes cpu fairly amongst tasks of the
786 * same nice value, it proportions cpu according to nice level, it means the
787 * task that last woke up the longest ago has the earliest deadline, thus
788 @@ -2283,7 +2360,7 @@ EXPORT_SYMBOL(sub_preempt_count);
790 static inline int prio_deadline_diff(int user_prio)
792 - return (prio_ratios[user_prio] * rr_interval * HZ / (1000 * 100)) ? : 1;
793 + return (prio_ratios[user_prio] * rr_interval * (MS_TO_NS(1) / 128));
796 static inline int task_deadline_diff(struct task_struct *p)
797 @@ -2296,25 +2373,33 @@ static inline int static_deadline_diff(i
798 return prio_deadline_diff(USER_PRIO(static_prio));
801 -static inline int longest_deadline_diff(void)
802 +static inline int ms_longest_deadline_diff(void)
804 - return prio_deadline_diff(39);
805 + return NS_TO_MS(prio_deadline_diff(39));
809 * The time_slice is only refilled when it is empty and that is when we set a
812 -static inline void time_slice_expired(struct task_struct *p)
813 +static void time_slice_expired(struct task_struct *p)
815 - reset_first_time_slice(p);
816 p->time_slice = timeslice();
817 - p->deadline = gjiffies + task_deadline_diff(p);
818 + p->deadline = grq.niffies + task_deadline_diff(p);
822 + * Timeslices below RESCHED_US are considered as good as expired as there's no
823 + * point rescheduling when there's so little time left. SCHED_BATCH tasks
824 + * have been flagged be not latency sensitive and likely to be fully CPU
825 + * bound so every time they're rescheduled they have their time_slice
826 + * refilled, but get a new later deadline to have little effect on
827 + * SCHED_NORMAL tasks.
830 static inline void check_deadline(struct task_struct *p)
832 - if (p->time_slice <= 0)
833 + if (p->time_slice < RESCHED_US || batch_task(p))
834 time_slice_expired(p);
837 @@ -2352,7 +2437,7 @@ retry:
838 queue = grq.queue + idx;
839 list_for_each_entry(p, queue, run_list) {
840 /* Make sure cpu affinity is ok */
841 - if (online_cpus(p) && !cpu_isset(cpu, p->cpus_allowed))
842 + if (needs_other_cpu(p, cpu))
844 if (idx < MAX_RT_PRIO) {
845 /* We found an rt task */
846 @@ -2479,12 +2564,14 @@ need_resched_nonpreemptible:
848 schedule_debug(prev);
850 - local_irq_disable();
851 - update_rq_clock(rq);
854 update_cpu_clock(rq, prev, 0);
855 - rq->skip_clock_update = 0;
856 + if (rq->clock - rq->last_tick > HALF_JIFFY_NS)
862 clear_tsk_need_resched(prev);
864 if (prev->state && !(preempt_count() & PREEMPT_ACTIVE)) {
865 @@ -2500,35 +2587,53 @@ need_resched_nonpreemptible:
866 prev->time_slice = rq->rq_time_slice;
867 prev->deadline = rq->rq_deadline;
868 check_deadline(prev);
869 - return_task(prev, deactivate);
870 - /* Task changed affinity off this cpu */
871 - if (unlikely(!cpus_intersects(prev->cpus_allowed,
872 - cpumask_of_cpu(cpu)))) {
873 - if (online_cpus(prev))
874 + prev->last_ran = rq->clock;
876 + /* Task changed affinity off this CPU */
877 + if (needs_other_cpu(prev, cpu))
878 + resched_suitable_idle(prev);
879 + else if (!deactivate) {
880 + if (!queued_notrunning()) {
882 + * We now know prev is the only thing that is
883 + * awaiting CPU so we can bypass rechecking for
884 + * the earliest deadline task and just run it
888 + goto rerun_prev_unlocked;
891 + * If prev got kicked off by a task that has to
892 + * run on this CPU for affinity reasons then
893 + * there may be an idle CPU it can go to.
895 resched_suitable_idle(prev);
898 + return_task(prev, deactivate);
901 - if (likely(queued_notrunning())) {
902 - next = earliest_deadline_task(rq, idle);
904 + if (unlikely(!queued_notrunning())) {
906 + * This CPU is now truly idle as opposed to when idle is
907 + * scheduled as a high priority task in its own right.
910 schedstat_inc(rq, sched_goidle);
914 - prefetch_stack(next);
916 - if (task_idle(next))
917 set_cpuidle_map(cpu);
920 + next = earliest_deadline_task(rq, idle);
922 + prefetch_stack(next);
923 clear_cpuidle_map(cpu);
925 - prev->last_ran = rq->clock;
928 if (likely(prev != next)) {
929 sched_info_switch(prev, next);
932 + set_last_task(rq, prev);
933 set_rq_task(rq, next);
936 @@ -2547,10 +2652,15 @@ need_resched_nonpreemptible:
940 - if (unlikely(reacquire_kernel_lock(current) < 0))
941 +rerun_prev_unlocked:
942 + if (unlikely(reacquire_kernel_lock(current) < 0)) {
944 + switch_count = &prev->nivcsw;
945 goto need_resched_nonpreemptible;
948 preempt_enable_no_resched();
949 - if (unlikely(test_thread_flag(TIF_NEED_RESCHED)))
950 + if (need_resched())
953 EXPORT_SYMBOL(schedule);
954 @@ -3066,8 +3176,9 @@ int task_prio(const struct task_struct *
958 - delta = p->deadline - gjiffies;
959 - delta = delta * 40 / longest_deadline_diff();
960 + /* Convert to ms to avoid overflows */
961 + delta = NS_TO_MS(p->deadline - grq.niffies);
962 + delta = delta * 40 / ms_longest_deadline_diff();
963 if (delta > 0 && delta <= 80)
965 if (idleprio_task(p))
966 @@ -3266,7 +3377,7 @@ recheck:
967 policy = oldpolicy = -1;
970 - update_rq_clock(rq);
972 p->sched_reset_on_fork = reset_on_fork;
974 queued = task_queued(p);
975 @@ -4453,7 +4564,7 @@ migration_call(struct notifier_block *nf
976 __setscheduler(idle, rq, SCHED_NORMAL, 0);
977 idle->prio = PRIO_LIMIT;
978 set_rq_task(rq, idle);
979 - update_rq_clock(rq);
984 @@ -5982,12 +6093,14 @@ void __init sched_init(void)
988 - prio_ratios[0] = 100;
989 + prio_ratios[0] = 128;
990 for (i = 1 ; i < PRIO_RANGE ; i++)
991 prio_ratios[i] = prio_ratios[i - 1] * 11 / 10;
993 spin_lock_init(&grq.lock);
994 grq.nr_running = grq.nr_uninterruptible = grq.nr_switches = 0;
996 + spin_lock_init(&grq.iso_lock);
997 grq.iso_ticks = grq.iso_refractory = 0;
999 init_defrootdomain();
1000 @@ -6000,7 +6113,9 @@ void __init sched_init(void)
1002 rq->user_pc = rq->nice_pc = rq->softirq_pc = rq->system_pc =
1003 rq->iowait_pc = rq->idle_pc = 0;
1006 + rq->last_niffy = 0;
1010 Index: kernel-2.6.28/kernel/sysctl.c
1011 ===================================================================
1012 --- kernel-2.6.28.orig/kernel/sysctl.c
1013 +++ kernel-2.6.28/kernel/sysctl.c
1014 @@ -102,7 +102,7 @@ static int __read_mostly one_hundred = 1
1015 #ifdef CONFIG_SCHED_BFS
1016 extern int rr_interval;
1017 extern int sched_iso_cpu;
1018 -static int __read_mostly five_thousand = 5000;
1019 +static int __read_mostly one_thousand = 1000;
1021 /* this is needed for the proc_dointvec_minmax for [fs_]overflow UID and GID */
1022 static int maxolduid = 65535;
1023 @@ -732,7 +732,7 @@ static struct ctl_table kern_table[] = {
1024 .proc_handler = &proc_dointvec_minmax,
1025 .strategy = &sysctl_intvec,
1027 - .extra2 = &five_thousand,
1028 + .extra2 = &one_thousand,
1031 .ctl_name = CTL_UNNUMBERED,