Index: Linux-2.6.X/fs/proc/array.c diff -u Linux-2.6.X/fs/proc/array.c:1.1.1.4 Linux-2.6.X/fs/proc/array.c:1.1.1.4.24.1.2.1 --- Linux-2.6.X/fs/proc/array.c:1.1.1.4 Fri Jun 4 14:29:01 2004 +++ Linux-2.6.X/fs/proc/array.c Thu Jun 17 16:47:14 2004 @@ -155,7 +155,7 @@ read_lock(&tasklist_lock); buffer += sprintf(buffer, "State:\t%s\n" - "SleepAVG:\t%lu%%\n" + "Burst:\t%d\n" "Tgid:\t%d\n" "Pid:\t%d\n" "PPid:\t%d\n" @@ -163,7 +163,7 @@ "Uid:\t%d\t%d\t%d\t%d\n" "Gid:\t%d\t%d\t%d\t%d\n", get_task_state(p), - (p->sleep_avg/1024)*100/(1020000000/1024), + p->burst, p->tgid, p->pid, p->pid ? p->real_parent->pid : 0, p->pid && p->ptrace ? p->parent->pid : 0, @@ -427,3 +427,25 @@ return sprintf(buffer,"%d %d %d %d %d %d %d\n", size, resident, shared, text, lib, data, 0); } + +int task_cpu_sched_stats(struct task_struct *p, char *buffer) +{ + struct task_sched_stats stats; + unsigned long nvcsw, nivcsw, cnvcsw, cnivcsw; /* context switch counts */ + + read_lock(&tasklist_lock); + get_task_sched_stats(p, &stats); + nvcsw = p->nvcsw; + nivcsw = p-> nivcsw; + cnvcsw = p->cnvcsw; + cnivcsw = p->cnivcsw; + read_unlock(&tasklist_lock); + return sprintf(buffer, + "%llu (%llu) %llu (%llu) %llu (%llu) %llu %lu %lu %lu %lu @ %llu\n", + stats.total_sleep, stats.avg_sleep_per_cycle, + stats.total_cpu, stats.avg_cpu_per_cycle, + stats.total_delay, stats.avg_delay_per_cycle, + stats.cycle_count, + nvcsw, nivcsw, cnvcsw, cnivcsw, + stats.timestamp); +} Index: Linux-2.6.X/fs/proc/base.c diff -u Linux-2.6.X/fs/proc/base.c:1.1.1.8 Linux-2.6.X/fs/proc/base.c:1.1.1.8.26.1 --- Linux-2.6.X/fs/proc/base.c:1.1.1.8 Tue Jun 8 19:10:54 2004 +++ Linux-2.6.X/fs/proc/base.c Thu Jun 17 16:47:14 2004 @@ -83,6 +83,7 @@ PROC_TID_MAPS, PROC_TID_MOUNTS, PROC_TID_WCHAN, + PROC_TID_CPU_STATS, #ifdef CONFIG_SECURITY PROC_TID_ATTR, PROC_TID_ATTR_CURRENT, @@ -145,6 +146,7 @@ #ifdef CONFIG_KALLSYMS E(PROC_TID_WCHAN, "wchan", S_IFREG|S_IRUGO), #endif + E(PROC_TID_CPU_STATS, "cpustats", S_IFREG|S_IRUGO), {0,0,NULL,0} }; @@ -181,6 +183,7 @@ int proc_pid_status(struct task_struct*,char*); int proc_pid_statm(struct task_struct*,char*); int proc_pid_cpu(struct task_struct*,char*); +extern int task_cpu_sched_stats(struct task_struct *p, char *buffer); static int proc_fd_link(struct inode *inode, struct dentry **dentry, struct vfsmount **mnt) { @@ -1375,6 +1378,10 @@ ei->op.proc_read = proc_pid_wchan; break; #endif + case PROC_TID_CPU_STATS: + inode->i_fop = &proc_info_file_operations; + ei->op.proc_read = task_cpu_sched_stats; + break; default: printk("procfs: impossible type (%d)",p->type); iput(inode); Index: Linux-2.6.X/fs/proc/proc_misc.c diff -u Linux-2.6.X/fs/proc/proc_misc.c:1.1.1.7 Linux-2.6.X/fs/proc/proc_misc.c:1.1.1.7.44.1 --- Linux-2.6.X/fs/proc/proc_misc.c:1.1.1.7 Mon May 24 11:55:32 2004 +++ Linux-2.6.X/fs/proc/proc_misc.c Thu Jun 17 16:47:14 2004 @@ -44,6 +44,7 @@ #include #include #include +#include #include #include #include @@ -274,6 +275,37 @@ .release = seq_release, }; +static int cpustats_read_proc(char *page, char **start, off_t off, + int count, int *eof, void *data) +{ + int i; + int len = 0; + struct cpu_sched_stats total = {0, }; + + for_each_online_cpu(i) { + struct cpu_sched_stats stats; + + get_cpu_sched_stats(i, &stats); + len += sprintf(page + len, "cpu%02d %llu %llu %llu %llu @ %llu\n", i, + stats.total_idle, + stats.total_busy, + stats.total_delay, + stats.nr_switches, + stats.timestamp); + total.total_idle += stats.total_idle; + total.total_busy += stats.total_busy; + total.total_delay += stats.total_delay; + total.nr_switches += stats.nr_switches; + } + len += sprintf(page + len, "total %llu %llu %llu %llu\n", + total.total_idle, + total.total_busy, + total.total_delay, + total.nr_switches); + + return proc_calc_metrics(page, start, off, count, eof, len); +} + extern struct seq_operations vmstat_op; static int vmstat_open(struct inode *inode, struct file *file) { @@ -676,6 +708,7 @@ #endif {"locks", locks_read_proc}, {"execdomains", execdomains_read_proc}, + {"cpustats", cpustats_read_proc}, {NULL,} }; for (p = simple_ones; p->name; p++) Index: Linux-2.6.X/include/linux/init_task.h diff -u Linux-2.6.X/include/linux/init_task.h:1.1.1.4 Linux-2.6.X/include/linux/init_task.h:1.1.1.4.22.1.6.1 --- Linux-2.6.X/include/linux/init_task.h:1.1.1.4 Thu May 6 18:40:15 2004 +++ Linux-2.6.X/include/linux/init_task.h Thu Jun 17 16:47:14 2004 @@ -71,7 +71,6 @@ .usage = ATOMIC_INIT(2), \ .flags = 0, \ .lock_depth = -1, \ - .prio = MAX_PRIO-20, \ .static_prio = MAX_PRIO-20, \ .policy = SCHED_NORMAL, \ .cpus_allowed = CPU_MASK_ALL, \ @@ -112,6 +111,7 @@ .proc_lock = SPIN_LOCK_UNLOCKED, \ .switch_lock = SPIN_LOCK_UNLOCKED, \ .journal_info = NULL, \ + .sched_timestamp = ((INITIAL_JIFFIES * NSEC_PER_SEC) / HZ), \ } Index: Linux-2.6.X/include/linux/sched.h diff -u Linux-2.6.X/include/linux/sched.h:1.1.1.10 Linux-2.6.X/include/linux/sched.h:1.1.1.10.2.1.4.1.2.3 --- Linux-2.6.X/include/linux/sched.h:1.1.1.10 Wed Jun 16 18:12:45 2004 +++ Linux-2.6.X/include/linux/sched.h Mon Jun 28 14:09:32 2004 @@ -164,6 +164,7 @@ void io_schedule(void); long io_schedule_timeout(long timeout); +extern int interactive, compute, log_at_exit; extern void cpu_init (void); extern void trap_init(void); @@ -305,7 +306,7 @@ #define MAX_PRIO (MAX_RT_PRIO + 40) -#define rt_task(p) ((p)->prio < MAX_RT_PRIO) +#define rt_task(p) ((p)->policy != SCHED_NORMAL) /* * Some day this will be a full-fledged user tracking system.. @@ -325,7 +326,6 @@ extern struct user_struct root_user; #define INIT_USER (&root_user) -typedef struct prio_array prio_array_t; struct backing_dev_info; struct reclaim_state; @@ -390,18 +390,21 @@ int lock_depth; /* Lock depth */ - int prio, static_prio; + int static_prio; struct list_head run_list; - prio_array_t *array; - - unsigned long sleep_avg; - long interactive_credit; unsigned long long timestamp; - int activated; + unsigned long runtime, totalrun; + unsigned int burst; + + unsigned long long sched_timestamp; + unsigned long long avg_sleep_per_cycle; + unsigned long long avg_delay_per_cycle; + unsigned long long avg_cpu_per_cycle; + unsigned long long cycle_count, total_sleep, total_cpu, total_delay; unsigned long policy; cpumask_t cpus_allowed; - unsigned int time_slice, first_time_slice; + unsigned int slice, time_slice; struct list_head tasks; struct list_head ptrace_children; @@ -549,6 +552,7 @@ #define PF_SWAPOFF 0x00080000 /* I am in swapoff */ #define PF_LESS_THROTTLE 0x00100000 /* Throttle me less: I clean memory */ #define PF_SYNCWRITE 0x00200000 /* I am doing a sync write */ +#define PF_FORKED 0x00400000 /* I have just forked */ #ifdef CONFIG_SMP #define SCHED_LOAD_SCALE 128UL /* increase resolution of load */ @@ -673,6 +677,45 @@ extern unsigned long long sched_clock(void); +/* + * Scheduling statistics for a task/thread + */ +struct task_sched_stats { + unsigned long long timestamp; + unsigned long long avg_sleep_per_cycle; + unsigned long long avg_delay_per_cycle; + unsigned long long avg_cpu_per_cycle; + unsigned long long cycle_count; + unsigned long long total_sleep; + unsigned long long total_cpu; + unsigned long long total_delay; +}; + +/* + * Get "up to date" scheduling statistics for the given task + * This function should be used if reliable scheduling statistitcs are required + * outside the scheduler itself as the relevant fields in the task structure + * are not "up to date" NB the possible difference between those in the task + * structure and the correct values could be quite large for sleeping tasks. + */ +extern void get_task_sched_stats(const struct task_struct *tsk, struct task_sched_stats *stats); + +/* + * Scheduling statistics for a CPU + */ +struct cpu_sched_stats { + unsigned long long timestamp; + unsigned long long total_idle; + unsigned long long total_busy; + unsigned long long total_delay; + unsigned long long nr_switches; +}; + +/* + * Get scheduling statistics for the nominated CPU + */ +extern void get_cpu_sched_stats(unsigned int cpu, struct cpu_sched_stats *stats); + #ifdef CONFIG_SMP extern void sched_balance_exec(void); #else Index: Linux-2.6.X/include/linux/sysctl.h diff -u Linux-2.6.X/include/linux/sysctl.h:1.1.1.10 Linux-2.6.X/include/linux/sysctl.h:1.1.1.10.38.1.2.1 --- Linux-2.6.X/include/linux/sysctl.h:1.1.1.10 Fri Jun 4 14:29:46 2004 +++ Linux-2.6.X/include/linux/sysctl.h Thu Jun 17 16:47:14 2004 @@ -133,6 +133,9 @@ KERN_NGROUPS_MAX=63, /* int: NGROUPS_MAX */ KERN_SPARC_SCONS_PWROFF=64, /* int: serial console power-off halt */ KERN_HZ_TIMER=65, /* int: hz timer on or off */ + KERN_INTERACTIVE=66, /* interactive tasks can have cpu bursts */ + KERN_COMPUTE=67, /* adjust timeslices for a compute server */ + KERN_LOG_AT_EXIT=68, /* log task CPU scheduling statistics at exit */ }; Index: Linux-2.6.X/init/main.c diff -u Linux-2.6.X/init/main.c:1.1.1.11 Linux-2.6.X/init/main.c:1.1.1.11.18.1 --- Linux-2.6.X/init/main.c:1.1.1.11 Tue Jun 8 19:12:17 2004 +++ Linux-2.6.X/init/main.c Thu Jun 17 11:12:44 2004 @@ -314,8 +314,15 @@ #define smp_init() do { } while (0) #endif +unsigned long cache_decay_ticks; static inline void setup_per_cpu_areas(void) { } -static inline void smp_prepare_cpus(unsigned int maxcpus) { } +static void smp_prepare_cpus(unsigned int maxcpus) +{ + // Generic 2 tick cache_decay for uniprocessor + cache_decay_ticks = 2; + printk("Generic cache decay timeout: %ld msecs.\n", + (cache_decay_ticks * 1000 / HZ)); +} #else Index: Linux-2.6.X/kernel/sched.c diff -u Linux-2.6.X/kernel/sched.c:1.1.1.11 Linux-2.6.X/kernel/sched.c:1.1.1.11.2.1.4.1.2.4 --- Linux-2.6.X/kernel/sched.c:1.1.1.11 Wed Jun 16 18:11:46 2004 +++ Linux-2.6.X/kernel/sched.c Mon Jun 28 14:09:32 2004 @@ -16,6 +16,10 @@ * by Davide Libenzi, preemptible kernel bits by Robert Love. * 2003-09-03 Interactivity tuning by Con Kolivas. * 2004-04-02 Scheduler domains code by Nick Piggin + * 2004-06-11 New staircase scheduling policy by Con Kolivas with help + * from William Lee Irwin III, Zwane Mwaikambo & Peter Williams. + * 2004-06-03 Single priority array by Peter Williams + * (Courtesy of Aurema Pty Ltd, www.aurema.com) */ #include @@ -43,12 +47,6 @@ #include -#ifdef CONFIG_NUMA -#define cpu_to_node_mask(cpu) node_to_cpumask(cpu_to_node(cpu)) -#else -#define cpu_to_node_mask(cpu) (cpu_online_map) -#endif - /* * Convert user-nice values [ -20 ... 0 ... 19 ] * to static priority [ MAX_RT_PRIO..MAX_PRIO-1 ], @@ -66,133 +64,75 @@ #define USER_PRIO(p) ((p)-MAX_RT_PRIO) #define TASK_USER_PRIO(p) USER_PRIO((p)->static_prio) #define MAX_USER_PRIO (USER_PRIO(MAX_PRIO)) -#define AVG_TIMESLICE (MIN_TIMESLICE + ((MAX_TIMESLICE - MIN_TIMESLICE) *\ - (MAX_PRIO-1-NICE_TO_PRIO(0))/(MAX_USER_PRIO - 1))) /* * Some helpers for converting nanosecond timing to jiffy resolution */ #define NS_TO_JIFFIES(TIME) ((TIME) / (1000000000 / HZ)) -#define JIFFIES_TO_NS(TIME) ((TIME) * (1000000000 / HZ)) - -/* - * These are the 'tuning knobs' of the scheduler: - * - * Minimum timeslice is 10 msecs, default timeslice is 100 msecs, - * maximum timeslice is 200 msecs. Timeslices get refilled after - * they expire. - */ -#define MIN_TIMESLICE ( 10 * HZ / 1000) -#define MAX_TIMESLICE (200 * HZ / 1000) -#define ON_RUNQUEUE_WEIGHT 30 -#define CHILD_PENALTY 95 -#define PARENT_PENALTY 100 -#define EXIT_WEIGHT 3 -#define PRIO_BONUS_RATIO 25 -#define MAX_BONUS (MAX_USER_PRIO * PRIO_BONUS_RATIO / 100) -#define INTERACTIVE_DELTA 2 -#define MAX_SLEEP_AVG (AVG_TIMESLICE * MAX_BONUS) -#define STARVATION_LIMIT (MAX_SLEEP_AVG) -#define NS_MAX_SLEEP_AVG (JIFFIES_TO_NS(MAX_SLEEP_AVG)) -#define CREDIT_LIMIT 100 - -/* - * If a task is 'interactive' then we reinsert it in the active - * array after it has expired its current timeslice. (it will not - * continue to run immediately, it will still roundrobin with - * other interactive tasks.) - * - * This part scales the interactivity limit depending on niceness. - * - * We scale it linearly, offset by the INTERACTIVE_DELTA delta. - * Here are a few examples of different nice levels: - * - * TASK_INTERACTIVE(-20): [1,1,1,1,1,1,1,1,1,0,0] - * TASK_INTERACTIVE(-10): [1,1,1,1,1,1,1,0,0,0,0] - * TASK_INTERACTIVE( 0): [1,1,1,1,0,0,0,0,0,0,0] - * TASK_INTERACTIVE( 10): [1,1,0,0,0,0,0,0,0,0,0] - * TASK_INTERACTIVE( 19): [0,0,0,0,0,0,0,0,0,0,0] - * - * (the X axis represents the possible -5 ... 0 ... +5 dynamic - * priority range a task can explore, a value of '1' means the - * task is rated interactive.) - * - * Ie. nice +19 tasks can never get 'interactive' enough to be - * reinserted into the active array. And only heavily CPU-hog nice -20 - * tasks will be expired. Default nice 0 tasks are somewhere between, - * it takes some effort for them to get interactive, but it's not - * too hard. - */ - -#define CURRENT_BONUS(p) \ - (NS_TO_JIFFIES((p)->sleep_avg) * MAX_BONUS / \ - MAX_SLEEP_AVG) - -#ifdef CONFIG_SMP -#define TIMESLICE_GRANULARITY(p) (MIN_TIMESLICE * \ - (1 << (((MAX_BONUS - CURRENT_BONUS(p)) ? : 1) - 1)) * \ - num_online_cpus()) -#else -#define TIMESLICE_GRANULARITY(p) (MIN_TIMESLICE * \ - (1 << (((MAX_BONUS - CURRENT_BONUS(p)) ? : 1) - 1))) -#endif - -#define SCALE(v1,v1_max,v2_max) \ - (v1) * (v2_max) / (v1_max) - -#define DELTA(p) \ - (SCALE(TASK_NICE(p), 40, MAX_BONUS) + INTERACTIVE_DELTA) - -#define TASK_INTERACTIVE(p) \ - ((p)->prio <= (p)->static_prio - DELTA(p)) - -#define INTERACTIVE_SLEEP(p) \ - (JIFFIES_TO_NS(MAX_SLEEP_AVG * \ - (MAX_BONUS / 2 + DELTA((p)) + 1) / MAX_BONUS - 1)) -#define HIGH_CREDIT(p) \ - ((p)->interactive_credit > CREDIT_LIMIT) - -#define LOW_CREDIT(p) \ - ((p)->interactive_credit < -CREDIT_LIMIT) - -#define TASK_PREEMPTS_CURR(p, rq) \ - ((p)->prio < (rq)->curr->prio) +int compute = 0; +/* + *This is the time all tasks within the same priority round robin. + *compute setting is reserved for dedicated computational scheduling + *and has ten times larger intervals. + */ +#define _RR_INTERVAL ((10 * HZ / 1000) ? : 1) +#define RR_INTERVAL (_RR_INTERVAL * (1 + 9 * compute)) /* - * BASE_TIMESLICE scales user-nice values [ -20 ... 19 ] - * to time slice values. - * - * The higher a thread's priority, the bigger timeslices - * it gets during one round of execution. But even the lowest - * priority thread gets MIN_TIMESLICE worth of execution time. - * - * task_timeslice() is the interface that is used by the scheduler. + * Fixed denominator rational numbers for use by the CPU scheduler */ +#define SCHED_AVG_OFFSET 8 +/* + * Get the rounded integer value of a scheduling statistic average field + * i.e. those fields whose names begin with avg_ + */ +#define SCHED_AVG_RND(x) \ + (((x) + (1 << (SCHED_AVG_OFFSET - 1))) >> (SCHED_AVG_OFFSET)) +#define SCHED_AVG_ALPHA ((1 << SCHED_AVG_OFFSET) - 1) +#define SCHED_AVG_MUL(a, b) (((a) * (b)) >> SCHED_AVG_OFFSET) +#define SCHED_AVG_REAL(a) ((a) << SCHED_AVG_OFFSET) -#define BASE_TIMESLICE(p) (MIN_TIMESLICE + \ - ((MAX_TIMESLICE - MIN_TIMESLICE) * \ - (MAX_PRIO-1 - (p)->static_prio) / (MAX_USER_PRIO-1))) - -static unsigned int task_timeslice(task_t *p) +static inline void apply_sched_avg_decay(unsigned long long *valp) { - return BASE_TIMESLICE(p); + *valp = SCHED_AVG_MUL(*valp, SCHED_AVG_ALPHA); } +/* + * What "base time slice" for nice 0 and "average time slice" evaluated to + */ +#define TIME_SLICE_MSECS 100 +#define TIME_SLICE_TICKS \ + (((TIME_SLICE_MSECS * HZ) / 1000) ? ((TIME_SLICE_MSECS * HZ) / 1000) : 1) + #define task_hot(p, now, sd) ((now) - (p)->timestamp < (sd)->cache_hot_time) /* * These are the runqueue data structures: */ +#define IDLE_PRIO MAX_PRIO +#define NUM_PRIO_SLOTS (IDLE_PRIO + 1) -#define BITMAP_SIZE ((((MAX_PRIO+1+7)/8)+sizeof(long)-1)/sizeof(long)) +/* + * Is the run queue idle? + */ +#define RUNQUEUE_IDLE(rq) ((rq)->curr == (rq)->idle) + +/* + * Control values for niceness + */ +#define PROSPECTIVE_BASE_PROM_INTERVAL ((TIME_SLICE_TICKS * 255) / 100) +#if (PROSPECTIVE_BASE_PROM_INTERVAL > 0) +#define BASE_PROM_INTERVAL PROSPECTIVE_BASE_PROM_INTERVAL +#else +#define BASE_PROM_INTERVAL TIME_SLICE_TICKS +#endif typedef struct runqueue runqueue_t; -struct prio_array { - unsigned int nr_active; - unsigned long bitmap[BITMAP_SIZE]; - struct list_head queue[MAX_PRIO]; +struct prio_slot { + unsigned int prio; + struct list_head queue; }; /* @@ -214,12 +154,16 @@ unsigned long cpu_load; #endif unsigned long long nr_switches; - unsigned long expired_timestamp, nr_uninterruptible; + unsigned long nr_uninterruptible; unsigned long long timestamp_last_tick; + unsigned long long total_delay; + unsigned int cache_ticks, preempted; task_t *curr, *idle; struct mm_struct *prev_mm; - prio_array_t *active, *expired, arrays[2]; - int best_expired_prio; + DECLARE_BITMAP(bitmap, NUM_PRIO_SLOTS); + struct prio_slot queues[NUM_PRIO_SLOTS]; + struct prio_slot *current_prio_slot; + unsigned long next_prom_due; atomic_t nr_iowait; #ifdef CONFIG_SMP @@ -253,6 +197,13 @@ # define task_running(rq, p) ((rq)->curr == (p)) #endif +static inline unsigned long get_prom_interval(const struct runqueue *rq) +{ + if (rq->nr_running < 2) + return BASE_PROM_INTERVAL; + return rq->nr_running * BASE_PROM_INTERVAL; +} + /* * task_rq_lock - lock the runqueue a given task resides on and disable * interrupts. Note the ordering: we can safely lookup the task_rq without @@ -297,23 +248,47 @@ spin_unlock_irq(&rq->lock); } +static inline int preemption_warranted(unsigned int prio, + const struct task_struct *p, runqueue_t *rq) +{ + if (prio >= rq->current_prio_slot->prio) + return 0; + if (!compute || rq->cache_ticks >= cache_decay_ticks || + rt_task(p) || !p->mm || rq->curr == rq->idle) + return 1; + rq->preempted = 1; + return 0; +} + +static inline int task_queued(const task_t *task) +{ + return !list_empty(&task->run_list); +} + /* - * Adding/removing a task to/from a priority array: + * Adding/removing a task to/from a runqueue: */ -static void dequeue_task(struct task_struct *p, prio_array_t *array) +static void dequeue_task(struct task_struct *p) { - array->nr_active--; - list_del(&p->run_list); - if (list_empty(array->queue + p->prio)) - __clear_bit(p->prio, array->bitmap); + /* + * If p is the last task in this priority slot then slotp will be + * a pointer to the head of the list in the sunqueue structure + */ + struct list_head *slotp = p->run_list.next; + + /* + * Initialize after removal from the list so that list_empty() works + * as a means for testing whether the task is runnable + */ + list_del_init(&p->run_list); + if (list_empty(slotp)) + __clear_bit(list_entry(slotp, struct prio_slot, queue)->prio, task_rq(p)->bitmap); } -static void enqueue_task(struct task_struct *p, prio_array_t *array) +static void enqueue_task(struct task_struct *p, runqueue_t *rq, int prio) { - list_add_tail(&p->run_list, array->queue + p->prio); - __set_bit(p->prio, array->bitmap); - array->nr_active++; - p->array = array; + list_add_tail(&p->run_list, &rq->queues[prio].queue); + __set_bit(prio, rq->bitmap); } /* @@ -321,148 +296,161 @@ * remote queue so we want these tasks to show up at the head of the * local queue: */ -static inline void enqueue_task_head(struct task_struct *p, prio_array_t *array) +static inline void enqueue_task_head(struct task_struct *p, runqueue_t *rq, int prio) { - list_add(&p->run_list, array->queue + p->prio); - __set_bit(p->prio, array->bitmap); - array->nr_active++; - p->array = array; + list_add(&p->run_list, &rq->queues[prio].queue); + __set_bit(prio, rq->bitmap); } /* - * effective_prio - return the priority that is based on the static - * priority but is modified by bonuses/penalties. - * - * We scale the actual sleep average [0 .... MAX_SLEEP_AVG] - * into the -5 ... 0 ... +5 bonus/penalty range. - * - * We use 25% of the full 0...39 priority range so that: - * - * 1) nice +19 interactive tasks do not preempt nice 0 CPU hogs. - * 2) nice -20 CPU hogs do not get preempted by nice 0 tasks. - * - * Both properties are important to certain workloads. + * __activate_task - move a task to the runqueue. */ -static int effective_prio(task_t *p) +static inline void __activate_task(task_t *p, runqueue_t *rq, int prio) { - int bonus, prio; + enqueue_task(p, rq, prio); + rq->nr_running++; +} +/* + * burst - extra intervals an interactive task can run for at best priority + * instead of descending priorities. + */ +static unsigned int burst(const task_t *p) +{ + unsigned int task_user_prio; if (rt_task(p)) - return p->prio; + return p->burst; + task_user_prio = TASK_USER_PRIO(p); + if (likely(task_user_prio < 40)) + return 39 - task_user_prio; + else + return 0; +} - bonus = CURRENT_BONUS(p) - MAX_BONUS / 2; +static void inc_burst(task_t *p) +{ + unsigned int best_burst; + best_burst = burst(p); + if (p->burst < best_burst) + p->burst++; +} - prio = p->static_prio - bonus; - if (prio < MAX_RT_PRIO) - prio = MAX_RT_PRIO; - if (prio > MAX_PRIO-1) - prio = MAX_PRIO-1; - return prio; +static void dec_burst(task_t *p) +{ + if (p->burst) + p->burst--; } /* - * __activate_task - move a task to the runqueue. + * slice - the duration a task runs before getting requeued at it's best + * priority and has it's burst decremented. */ -static inline void __activate_task(task_t *p, runqueue_t *rq) +static unsigned int slice(const task_t *p) { - enqueue_task(p, rq->active); - rq->nr_running++; + unsigned int slice = RR_INTERVAL; + if (!rt_task(p)) + slice += burst(p) * RR_INTERVAL; + return slice; } /* - * __activate_idle_task - move idle task to the _front_ of runqueue. + * interactive - sysctl which allows interactive tasks to have bursts */ -static inline void __activate_idle_task(task_t *p, runqueue_t *rq) -{ - enqueue_task_head(p, rq->active); - rq->nr_running++; -} +int interactive = 1; -static void recalc_task_prio(task_t *p, unsigned long long now) +/* + * Update various statistics for the end of a + * ((on_run_queue :-> on_cpu)* :-> sleep) cycle. + * We can't just do this in activate_task() as every invocation of that + * function is not the genuine end of a cycle. + */ +static void update_stats_for_cycle(task_t *p, const runqueue_t *rq) { - unsigned long long __sleep_time = now - p->timestamp; - unsigned long sleep_time; + unsigned long long delta; - if (__sleep_time > NS_MAX_SLEEP_AVG) - sleep_time = NS_MAX_SLEEP_AVG; - else - sleep_time = (unsigned long)__sleep_time; - - if (likely(sleep_time > 0)) { - /* - * User tasks that sleep a long time are categorised as - * idle and will get just interactive status to stay active & - * prevent them suddenly becoming cpu hogs and starving - * other processes. - */ - if (p->mm && p->activated != -1 && - sleep_time > INTERACTIVE_SLEEP(p)) { - p->sleep_avg = JIFFIES_TO_NS(MAX_SLEEP_AVG - - AVG_TIMESLICE); - if (!HIGH_CREDIT(p)) - p->interactive_credit++; - } else { - /* - * The lower the sleep avg a task has the more - * rapidly it will rise with sleep time. - */ - sleep_time *= (MAX_BONUS - CURRENT_BONUS(p)) ? : 1; + apply_sched_avg_decay(&p->avg_delay_per_cycle); + apply_sched_avg_decay(&p->avg_cpu_per_cycle); + delta = (rq->timestamp_last_tick - p->sched_timestamp); + p->avg_sleep_per_cycle += delta; + p->total_sleep += delta; + /* + * Do this second so that averages for all measures are for + * the current cycle + */ + apply_sched_avg_decay(&p->avg_sleep_per_cycle); + p->sched_timestamp = rq->timestamp_last_tick; + p->cycle_count++; +} - /* - * Tasks with low interactive_credit are limited to - * one timeslice worth of sleep avg bonus. - */ - if (LOW_CREDIT(p) && - sleep_time > JIFFIES_TO_NS(task_timeslice(p))) - sleep_time = JIFFIES_TO_NS(task_timeslice(p)); +/* + * effective_prio - dynamic priority dependent on burst. + * The priority normally decreases by one each RR_INTERVAL. + * As the burst increases the priority stays at the top "stair" or + * priority for longer. + */ +static int effective_prio(task_t *p) +{ + int prio; + unsigned int full_slice, used_slice, first_slice; + unsigned int best_burst; - /* - * Non high_credit tasks waking from uninterruptible - * sleep are limited in their sleep_avg rise as they - * are likely to be cpu hogs waiting on I/O - */ - if (p->activated == -1 && !HIGH_CREDIT(p) && p->mm) { - if (p->sleep_avg >= INTERACTIVE_SLEEP(p)) - sleep_time = 0; - else if (p->sleep_avg + sleep_time >= - INTERACTIVE_SLEEP(p)) { - p->sleep_avg = INTERACTIVE_SLEEP(p); - sleep_time = 0; - } - } + if (rt_task(p)) + return (MAX_USER_RT_PRIO - 1) - p->rt_priority; - /* - * This code gives a bonus to interactive tasks. - * - * The boost works by updating the 'average sleep time' - * value here, based on ->timestamp. The more time a - * task spends sleeping, the higher the average gets - - * and the higher the priority boost gets as well. - */ - p->sleep_avg += sleep_time; + best_burst = burst(p); + full_slice = slice(p); + used_slice = full_slice - p->slice; + if (p->burst > best_burst) + p->burst = best_burst; + first_slice = RR_INTERVAL; + if (interactive && !compute) + first_slice *= (p->burst + 1); + prio = MAX_PRIO - 1 - best_burst; + + if (used_slice < first_slice) + return prio; + prio += 1 + (used_slice - first_slice) / RR_INTERVAL; + if (prio > MAX_PRIO - 1) + prio = MAX_PRIO - 1; + return prio; +} - if (p->sleep_avg > NS_MAX_SLEEP_AVG) { - p->sleep_avg = NS_MAX_SLEEP_AVG; - if (!HIGH_CREDIT(p)) - p->interactive_credit++; +/* + * recalc_task_prio - this checks for tasks that run ultra short timeslices + * or have just forked a thread/process and make them continue their old + * slice instead of starting a new one at high priority. + */ +static void recalc_task_prio(task_t *p, unsigned long long now) +{ + unsigned long sleep_time = now - p->timestamp; + unsigned long ns_totalrun = p->totalrun + p->runtime; + unsigned long total_run = NS_TO_JIFFIES(ns_totalrun); + if (p->flags & PF_FORKED || (!(NS_TO_JIFFIES(p->runtime)) && + NS_TO_JIFFIES(p->runtime + sleep_time) < RR_INTERVAL)) { + p->flags &= ~PF_FORKED; + if (p->slice - total_run < 1) { + p->totalrun = 0; + dec_burst(p); + } else { + p->totalrun = ns_totalrun; + p->slice -= total_run; } - } + } else { + inc_burst(p); + p->runtime = 0; + p->totalrun = 0; } - - p->prio = effective_prio(p); } /* * activate_task - move a task to the runqueue and do priority recalculation - * - * Update all the scheduling statistics stuff. (sleep average - * calculation, priority modifiers, etc.) + * return prio to allow preemption testing */ -static void activate_task(task_t *p, runqueue_t *rq, int local) +static int activate_task(task_t *p, runqueue_t *rq, int local) { - unsigned long long now; + int prio; + unsigned long long now = sched_clock(); - now = sched_clock(); #ifdef CONFIG_SMP if (!local) { /* Compensate for drifting sched_clock */ @@ -471,34 +459,14 @@ + rq->timestamp_last_tick; } #endif - + p->slice = slice(p); recalc_task_prio(p, now); - - /* - * This checks to make sure it's not an uninterruptible task - * that is now waking up. - */ - if (!p->activated) { - /* - * Tasks which were woken up by interrupts (ie. hw events) - * are most likely of interactive nature. So we give them - * the credit of extending their sleep time to the period - * of time they spend on the runqueue, waiting for execution - * on a CPU, first time around: - */ - if (in_interrupt()) - p->activated = 2; - else { - /* - * Normal first-time wakeups get a credit too for - * on-runqueue time, but it will be weighted down: - */ - p->activated = 1; - } - } + prio = effective_prio(p); + p->time_slice = RR_INTERVAL; p->timestamp = now; + __activate_task(p, rq, prio); - __activate_task(p, rq); + return prio; } /* @@ -509,8 +477,7 @@ rq->nr_running--; if (p->state == TASK_UNINTERRUPTIBLE) rq->nr_uninterruptible++; - dequeue_task(p, p->array); - p->array = NULL; + dequeue_task(p); } /* @@ -583,7 +550,7 @@ * If the task is not on a runqueue (and not running), then * it is sufficient to simply update the task's cpu field. */ - if (!p->array && !task_running(rq, p)) { + if (!task_queued(p) && !task_running(rq, p)) { set_task_cpu(p, dest_cpu); return 0; } @@ -614,7 +581,7 @@ repeat: rq = task_rq_lock(p, &flags); /* Must be off runqueue entirely, not preempted. */ - if (unlikely(p->array)) { + if (unlikely(task_queued(p))) { /* If it's preempted, we yield. It could be a while. */ preempted = !task_running(rq, p); task_rq_unlock(rq, &flags); @@ -733,6 +700,7 @@ unsigned long flags; long old_state; runqueue_t *rq; + int prio; #ifdef CONFIG_SMP unsigned long load, this_load; struct sched_domain *sd; @@ -744,7 +712,7 @@ if (!(old_state & state)) goto out; - if (p->array) + if (task_queued(p)) goto out_running; cpu = task_cpu(p); @@ -811,7 +779,7 @@ old_state = p->state; if (!(old_state & state)) goto out; - if (p->array) + if (task_queued(p)) goto out_running; this_cpu = smp_processor_id(); @@ -820,16 +788,15 @@ out_activate: #endif /* CONFIG_SMP */ - if (old_state == TASK_UNINTERRUPTIBLE) { + if (old_state == TASK_UNINTERRUPTIBLE) rq->nr_uninterruptible--; - /* - * Tasks on involuntary sleep don't earn - * sleep_avg beyond just interactive state. - */ - p->activated = -1; - } /* + * This is the end of one scheduling cycle and the start + * of the next + */ + update_stats_for_cycle(p, rq); + /* * Sync wakeups (i.e. those types of wakeups where the waker * has indicated that it will leave the CPU in short order) * don't trigger a preemption, if the woken up task will run on @@ -837,9 +804,9 @@ * the waker guarantees that the freshly woken up task is going * to be considered on this CPU.) */ - activate_task(p, rq, cpu == this_cpu); + prio = activate_task(p, rq, cpu == this_cpu); if (!sync || cpu != this_cpu) { - if (TASK_PREEMPTS_CURR(p, rq)) + if (preemption_warranted(prio, p, rq)) resched_task(rq->curr); } success = 1; @@ -866,6 +833,21 @@ } /* + * Initialize the scheduling statistics counters + */ +static inline void initialize_stats(task_t *p) +{ + p->avg_sleep_per_cycle = 0; + p->avg_delay_per_cycle = 0; + p->avg_cpu_per_cycle = 0; + p->total_sleep = 0; + p->total_delay = 0; + p->total_cpu = 0; + p->cycle_count = 0; + p->sched_timestamp = 0 /* set this to current time later */; +} + +/* * Perform scheduler related setup for a newly forked process p. * p is forked by current. */ @@ -879,7 +861,6 @@ */ p->state = TASK_RUNNING; INIT_LIST_HEAD(&p->run_list); - p->array = NULL; spin_lock_init(&p->switch_lock); #ifdef CONFIG_PREEMPT /* @@ -891,32 +872,9 @@ p->thread_info->preempt_count = 1; #endif /* - * Share the timeslice between parent and child, thus the - * total amount of pending timeslices in the system doesn't change, - * resulting in more scheduling fairness. - */ - local_irq_disable(); - p->time_slice = (current->time_slice + 1) >> 1; - /* - * The remainder of the first timeslice might be recovered by - * the parent if the child exits early enough. + * Initialize the scheduler statistics counters */ - p->first_time_slice = 1; - current->time_slice >>= 1; - p->timestamp = sched_clock(); - if (!current->time_slice) { - /* - * This case is rare, it happens when the parent has only - * a single jiffy left from its timeslice. Taking the - * runqueue lock is not a problem. - */ - current->time_slice = 1; - preempt_disable(); - scheduler_tick(0, 0); - local_irq_enable(); - preempt_enable(); - } else - local_irq_enable(); + initialize_stats(p); } /* @@ -930,67 +888,54 @@ unsigned long flags; runqueue_t *rq = task_rq_lock(current, &flags); + /* + * Forked process gets no burst to prevent fork bombs. + */ + p->burst = 0; BUG_ON(p->state != TASK_RUNNING); + set_task_cpu(p, smp_processor_id()); + /* - * We decrease the sleep average of forking parents - * and children as well, to keep max-interactive tasks - * from forking tasks that are max-interactive. + * Scheduling statistics compilation starts now */ - current->sleep_avg = JIFFIES_TO_NS(CURRENT_BONUS(current) * - PARENT_PENALTY / 100 * MAX_SLEEP_AVG / MAX_BONUS); - - p->sleep_avg = JIFFIES_TO_NS(CURRENT_BONUS(p) * - CHILD_PENALTY / 100 * MAX_SLEEP_AVG / MAX_BONUS); - - p->interactive_credit = 0; + p->sched_timestamp = rq->timestamp_last_tick; - p->prio = effective_prio(p); - set_task_cpu(p, smp_processor_id()); - - if (unlikely(!current->array)) - __activate_task(p, rq); + /* + * Now that the idle task is back on the run queue we need extra care + * to make sure that its one and only fork() doesn't end up in the idle + * priority slot. Just testing for empty run list is no longer adequate. + */ + if (unlikely(!task_queued(current) || RUNQUEUE_IDLE(rq))) + __activate_task(p, rq, effective_prio(p)); else { - p->prio = current->prio; + /* + * Put the child on the same list(s) as (but ahead of) the parent + */ list_add_tail(&p->run_list, ¤t->run_list); - p->array = current->array; - p->array->nr_active++; rq->nr_running++; } + current->flags |= PF_FORKED; task_rq_unlock(rq, &flags); } -/* - * Potentially available exiting-child timeslices are - * retrieved here - this way the parent does not get - * penalized for creating too many threads. - * - * (this cannot be used to 'generate' timeslices - * artificially, because any timeslice recovered here - * was given away by the parent in the first place.) +/** + * (Optionally) log scheduler statistics at exit. */ +int log_at_exit = 0; void fastcall sched_exit(task_t * p) { - unsigned long flags; - runqueue_t *rq; + struct task_sched_stats stats; - local_irq_save(flags); - if (p->first_time_slice) { - p->parent->time_slice += p->time_slice; - if (unlikely(p->parent->time_slice > MAX_TIMESLICE)) - p->parent->time_slice = MAX_TIMESLICE; - } - local_irq_restore(flags); - /* - * If the child was a (relative-) CPU hog then decrease - * the sleep_avg of the parent as well. - */ - rq = task_rq_lock(p->parent, &flags); - if (p->sleep_avg < p->parent->sleep_avg) - p->parent->sleep_avg = p->parent->sleep_avg / - (EXIT_WEIGHT + 1) * EXIT_WEIGHT + p->sleep_avg / - (EXIT_WEIGHT + 1); - task_rq_unlock(rq, &flags); + if (!log_at_exit) + return; + + get_task_sched_stats(p, &stats); + printk("SCHED_EXIT[%d] (%s) %llu %llu %llu %llu %lu %lu %lu %lu\n", + p->pid, p->comm, + stats.total_sleep, stats.total_cpu, stats.total_delay, + stats.cycle_count, + p->nvcsw, p->nivcsw, p->cnvcsw, p->cnivcsw); } /** @@ -1167,7 +1112,7 @@ /* * find_idlest_cpu - find the least busy runqueue. */ -static int find_idlest_cpu(struct task_struct *p, int this_cpu, +static int find_idlest_cpu(const struct task_struct *p, int this_cpu, struct sched_domain *sd) { unsigned long load, min_load, this_load; @@ -1253,38 +1198,34 @@ double_rq_unlock(this_rq, rq); goto lock_again; } - /* - * We decrease the sleep average of forking parents - * and children as well, to keep max-interactive tasks - * from forking tasks that are max-interactive. - */ - current->sleep_avg = JIFFIES_TO_NS(CURRENT_BONUS(current) * - PARENT_PENALTY / 100 * MAX_SLEEP_AVG / MAX_BONUS); - p->sleep_avg = JIFFIES_TO_NS(CURRENT_BONUS(p) * - CHILD_PENALTY / 100 * MAX_SLEEP_AVG / MAX_BONUS); - - p->interactive_credit = 0; - - p->prio = effective_prio(p); set_task_cpu(p, cpu); + /* + * Scheduling statistics compilation starts now + */ + p->sched_timestamp = rq->timestamp_last_tick; + if (cpu == this_cpu) { - if (unlikely(!current->array)) - __activate_task(p, rq); + /* + * Now that the idle task is back on the run queue we need + * extra care to make sure that its one and only fork() doesn't + * end up in the idle priority slot. Just testing for empty + * run list is no longer adequate. + */ + if (unlikely(!task_queued(current) || RUNQUEUE_IDLE(rq))) + __activate_task(p, rq, effective_prio(p)); else { - p->prio = current->prio; list_add_tail(&p->run_list, ¤t->run_list); - p->array = current->array; - p->array->nr_active++; rq->nr_running++; } } else { + int prio = effective_prio(p); /* Not the local CPU - must adjust timestamp */ p->timestamp = (p->timestamp - this_rq->timestamp_last_tick) + rq->timestamp_last_tick; - __activate_task(p, rq); - if (TASK_PREEMPTS_CURR(p, rq)) + __activate_task(p, rq, prio); + if (preemption_warranted(prio, p, rq)) resched_task(rq->curr); } @@ -1376,22 +1317,28 @@ * pull_task - move a task from a remote runqueue to the local runqueue. * Both runqueues must be locked. */ -static inline -void pull_task(runqueue_t *src_rq, prio_array_t *src_array, task_t *p, - runqueue_t *this_rq, prio_array_t *this_array, int this_cpu) +static inline +void pull_task(runqueue_t *src_rq, task_t *p, + runqueue_t *this_rq, int this_cpu, int prio) { - dequeue_task(p, src_array); + unsigned long long delta; + + dequeue_task(p); src_rq->nr_running--; + delta = (src_rq->timestamp_last_tick - p->sched_timestamp); + p->avg_delay_per_cycle += delta; + p->total_delay += delta; set_task_cpu(p, this_cpu); this_rq->nr_running++; - enqueue_task(p, this_array); + p->sched_timestamp = this_rq->timestamp_last_tick; + enqueue_task(p, this_rq, prio); p->timestamp = (p->timestamp - src_rq->timestamp_last_tick) + this_rq->timestamp_last_tick; /* - * Note that idle threads have a prio of MAX_PRIO, for this test + * Note that idle threads have a prio of IDLE_PRIO, for this test * to be always true for them. */ - if (TASK_PREEMPTS_CURR(p, this_rq)) + if (preemption_warranted(prio, p, this_rq)) resched_task(this_rq->curr); } @@ -1399,7 +1346,7 @@ * can_migrate_task - may task p from runqueue rq be migrated to this_cpu? */ static inline -int can_migrate_task(task_t *p, runqueue_t *rq, int this_cpu, +int can_migrate_task(const task_t *p, runqueue_t *rq, int this_cpu, struct sched_domain *sd, enum idle_type idle) { /* @@ -1434,7 +1381,6 @@ unsigned long max_nr_move, struct sched_domain *sd, enum idle_type idle) { - prio_array_t *array, *dst_array; struct list_head *head, *curr; int idx, pulled = 0; task_t *tmp; @@ -1442,38 +1388,17 @@ if (max_nr_move <= 0 || busiest->nr_running <= 1) goto out; - /* - * We first consider expired tasks. Those will likely not be - * executed in the near future, and they are most likely to - * be cache-cold, thus switching CPUs has the least effect - * on them. - */ - if (busiest->expired->nr_active) { - array = busiest->expired; - dst_array = this_rq->expired; - } else { - array = busiest->active; - dst_array = this_rq->active; - } - -new_array: /* Start searching at priority 0: */ idx = 0; skip_bitmap: if (!idx) - idx = sched_find_first_bit(array->bitmap); + idx = sched_find_first_bit(busiest->bitmap); else - idx = find_next_bit(array->bitmap, MAX_PRIO, idx); - if (idx >= MAX_PRIO) { - if (array == busiest->expired && busiest->active->nr_active) { - array = busiest->active; - dst_array = this_rq->active; - goto new_array; - } + idx = find_next_bit(busiest->bitmap, IDLE_PRIO, idx); + if (idx >= IDLE_PRIO) goto out; - } - head = array->queue + idx; + head = &busiest->queues[idx].queue; curr = head->prev; skip_queue: tmp = list_entry(curr, task_t, run_list); @@ -1486,7 +1411,7 @@ idx++; goto skip_bitmap; } - pull_task(busiest, array, tmp, this_rq, dst_array, this_cpu); + pull_task(busiest, tmp, this_rq, this_cpu, idx); pulled++; /* We only want to steal up to the prescribed number of tasks. */ @@ -1645,7 +1570,7 @@ /* * find_busiest_queue - find the busiest runqueue among the cpus in group. */ -static runqueue_t *find_busiest_queue(struct sched_group *group) +static runqueue_t *find_busiest_queue(const struct sched_group *group) { cpumask_t tmp; unsigned long load, max_load = 0; @@ -1924,6 +1849,11 @@ } } } + +static inline int needs_idle_balance(const runqueue_t *rq) +{ + return rq->nr_running == 0; +} #else /* * on UP we do not need to balance between CPUs: @@ -1934,6 +1864,10 @@ static inline void idle_balance(int cpu, runqueue_t *rq) { } +static inline int needs_idle_balance(const runqueue_t *rq) +{ + return 0; +} #endif static inline int wake_priority_sleeper(runqueue_t *rq) @@ -1951,27 +1885,52 @@ return 0; } +/* + * Are promotions due? + */ +static inline int promotions_due(const runqueue_t *rq) +{ + return time_after_eq(jiffies, rq->next_prom_due); +} + +/* + * Assume runqueue lock is NOT already held. + */ +static void do_promotions(runqueue_t *rq) +{ + int idx = MAX_RT_PRIO; + + spin_lock(&rq->lock); + for (;;) { + int new_prio; + idx = find_next_bit(rq->bitmap, IDLE_PRIO, idx + 1); + if (idx > (IDLE_PRIO - 1)) + break; + + new_prio = idx - 1; + __list_splice(&rq->queues[idx].queue, rq->queues[new_prio].queue.prev); + INIT_LIST_HEAD(&rq->queues[idx].queue); + __clear_bit(idx, rq->bitmap); + __set_bit(new_prio, rq->bitmap); + /* + * If promotion occurs from the slot + * associated with rq->current_prio_slot then the + * current task will be one of those promoted + * so we should update rq->current_prio_slot + * This will only be true for at most one slot. + */ + if (unlikely(idx == rq->current_prio_slot->prio)) + rq->current_prio_slot = rq->queues + new_prio; + } + rq->next_prom_due = (jiffies + get_prom_interval(rq)); + spin_unlock(&rq->lock); +} + DEFINE_PER_CPU(struct kernel_stat, kstat); EXPORT_PER_CPU_SYMBOL(kstat); /* - * We place interactive tasks back into the active array, if possible. - * - * To guarantee that this does not starve expired tasks we ignore the - * interactivity of a task if the first expired task had to wait more - * than a 'reasonable' amount of time. This deadline timeout is - * load-dependent, as the frequency of array switched decreases with - * increasing number of running tasks. We also ignore the interactivity - * if a better static_prio task has expired: - */ -#define EXPIRED_STARVING(rq) \ - ((STARVATION_LIMIT && ((rq)->expired_timestamp && \ - (jiffies - (rq)->expired_timestamp >= \ - STARVATION_LIMIT * ((rq)->nr_running) + 1))) || \ - ((rq)->curr->static_prio > (rq)->best_expired_prio)) - -/* * This function gets called by the timer code, with HZ frequency. * We call it with interrupts disabled. * @@ -2015,82 +1974,53 @@ cpustat->user += user_ticks; cpustat->system += sys_ticks; - /* Task might have expired already, but not scheduled off yet */ - if (p->array != rq->active) { - set_tsk_need_resched(p); - goto out; - } spin_lock(&rq->lock); /* - * The task was running during this tick - update the - * time slice counter. Note: we do not update a thread's - * priority until it either goes to sleep or uses up its - * timeslice. This makes it possible for interactive tasks - * to use up their timeslices at their highest priority levels. + * SCHED_FIFO tasks never run out of timeslice. */ - if (unlikely(rt_task(p))) { - /* - * RR tasks need a special form of timeslice management. - * FIFO tasks have no timeslices. - */ - if ((p->policy == SCHED_RR) && !--p->time_slice) { - p->time_slice = task_timeslice(p); - p->first_time_slice = 0; - set_tsk_need_resched(p); - - /* put it at the end of the queue: */ - dequeue_task(p, rq->active); - enqueue_task(p, rq->active); - } + if (unlikely(p->policy == SCHED_FIFO)) + goto out_unlock; + rq->cache_ticks++; + /* + * Tasks lose burst each time they use up a full slice(). + */ + if (!--p->slice) { + set_tsk_need_resched(p); + dequeue_task(p); + dec_burst(p); + p->slice = slice(p); + rq->current_prio_slot = rq->queues + effective_prio(p); + p->time_slice = RR_INTERVAL; + enqueue_task(p, rq, rq->current_prio_slot->prio); goto out_unlock; } + /* + * Tasks that run out of time_slice but still have slice left get + * requeued with a lower priority && RR_INTERVAL time_slice. + */ if (!--p->time_slice) { - dequeue_task(p, rq->active); + dequeue_task(p); set_tsk_need_resched(p); - p->prio = effective_prio(p); - p->time_slice = task_timeslice(p); - p->first_time_slice = 0; - - if (!rq->expired_timestamp) - rq->expired_timestamp = jiffies; - if (!TASK_INTERACTIVE(p) || EXPIRED_STARVING(rq)) { - enqueue_task(p, rq->expired); - if (p->static_prio < rq->best_expired_prio) - rq->best_expired_prio = p->static_prio; - } else - enqueue_task(p, rq->active); - } else { - /* - * Prevent a too long timeslice allowing a task to monopolize - * the CPU. We do this by splitting up the timeslice into - * smaller pieces. - * - * Note: this does not mean the task's timeslices expire or - * get lost in any way, they just might be preempted by - * another task of equal priority. (one with higher - * priority would have preempted this task already.) We - * requeue this task to the end of the list on this priority - * level, which is in essence a round-robin of tasks with - * equal priority. - * - * This only applies to tasks in the interactive - * delta range with at least TIMESLICE_GRANULARITY to requeue. - */ - if (TASK_INTERACTIVE(p) && !((task_timeslice(p) - - p->time_slice) % TIMESLICE_GRANULARITY(p)) && - (p->time_slice >= TIMESLICE_GRANULARITY(p)) && - (p->array == rq->active)) { - - dequeue_task(p, rq->active); - set_tsk_need_resched(p); - p->prio = effective_prio(p); - enqueue_task(p, rq->active); - } + p->time_slice = RR_INTERVAL; + rq->current_prio_slot = rq->queues + effective_prio(p); + enqueue_task(p, rq, rq->current_prio_slot->prio); + goto out_unlock; } + if (rq->preempted && rq->cache_ticks >= cache_decay_ticks) + set_tsk_need_resched(p); out_unlock: spin_unlock(&rq->lock); out: rebalance_tick(cpu, rq, NOT_IDLE); + if (unlikely(promotions_due(rq))) { + /* + * If there's less than 2 SCHED_OTHER tasks defer the next promotion + */ + if ((rt_task(p) ? rq->nr_running - 1 : rq->nr_running) < 2) + rq->next_prom_due = (jiffies + get_prom_interval(rq)); + else + do_promotions(rq); + } } #ifdef CONFIG_SCHED_SMT @@ -2149,8 +2079,8 @@ * task from using an unfair proportion of the * physical cpu's resources. -ck */ - if (((smt_curr->time_slice * (100 - sd->per_cpu_gain) / 100) > - task_timeslice(p) || rt_task(smt_curr)) && + if (((smt_curr->slice * (100 - sd->per_cpu_gain) / 100) > + slice(p) || rt_task(smt_curr)) && p->mm && smt_curr->mm && !rt_task(p)) ret = 1; @@ -2159,14 +2089,19 @@ * or wake it up if it has been put to sleep for priority * reasons. */ - if ((((p->time_slice * (100 - sd->per_cpu_gain) / 100) > - task_timeslice(smt_curr) || rt_task(p)) && + if ((((p->slice * (100 - sd->per_cpu_gain) / 100) > + slice(smt_curr) || rt_task(p)) && smt_curr->mm && p->mm && !rt_task(smt_curr)) || (smt_curr == smt_rq->idle && smt_rq->nr_running)) resched_task(smt_curr); } return ret; } + +static inline int dependent_idle(const runqueue_t *rq, const task_t *p) +{ + return p == rq->idle; +} #else static inline void wake_sleeping_dependent(int cpu, runqueue_t *rq) { @@ -2176,6 +2111,11 @@ { return 0; } + +static inline int dependent_idle(const runqueue_t *rq, const task_t *p) +{ + return 0; +} #endif /* @@ -2186,11 +2126,9 @@ long *switch_count; task_t *prev, *next; runqueue_t *rq; - prio_array_t *array; - struct list_head *queue; unsigned long long now; - unsigned long run_time; - int cpu, idx; + int cpu; + unsigned long long delta; /* * Test if we are atomic. Since do_exit() needs to call into @@ -2211,19 +2149,8 @@ release_kernel_lock(prev); now = sched_clock(); - if (likely(now - prev->timestamp < NS_MAX_SLEEP_AVG)) - run_time = now - prev->timestamp; - else - run_time = NS_MAX_SLEEP_AVG; - - /* - * Tasks with interactive credits get charged less run_time - * at high sleep_avg to delay them losing their interactive - * status - */ - if (HIGH_CREDIT(prev)) - run_time /= (CURRENT_BONUS(prev) ? : 1); + prev->runtime = now - prev->timestamp; spin_lock_irq(&rq->lock); /* @@ -2241,64 +2168,44 @@ } cpu = smp_processor_id(); - if (unlikely(!rq->nr_running)) { + if (unlikely(needs_idle_balance(rq))) idle_balance(cpu, rq); - if (!rq->nr_running) { - next = rq->idle; - rq->expired_timestamp = 0; - wake_sleeping_dependent(cpu, rq); - goto switch_tasks; - } - } - array = rq->active; - if (unlikely(!array->nr_active)) { - /* - * Switch the active and expired arrays. - */ - rq->active = rq->expired; - rq->expired = array; - array = rq->active; - rq->expired_timestamp = 0; - rq->best_expired_prio = MAX_PRIO; + rq->current_prio_slot = rq->queues + sched_find_first_bit(rq->bitmap); + next = list_entry(rq->current_prio_slot->queue.next, task_t, run_list); + if (dependent_idle(rq, next)) { + wake_sleeping_dependent(cpu, rq); + goto switch_tasks; } - idx = sched_find_first_bit(array->bitmap); - queue = array->queue + idx; - next = list_entry(queue->next, task_t, run_list); - if (dependent_sleeper(cpu, rq, next)) { + rq->current_prio_slot = rq->queues + IDLE_PRIO; next = rq->idle; - goto switch_tasks; - } - - if (!rt_task(next) && next->activated > 0) { - unsigned long long delta = now - next->timestamp; - - if (next->activated == 1) - delta = delta * (ON_RUNQUEUE_WEIGHT * 128 / 100) / 128; - - array = next->array; - dequeue_task(next, array); - recalc_task_prio(next, next->timestamp + delta); - enqueue_task(next, array); } - next->activated = 0; switch_tasks: prefetch(next); clear_tsk_need_resched(prev); RCU_qsctr(task_cpu(prev))++; - prev->sleep_avg -= run_time; - if ((long)prev->sleep_avg <= 0) { - prev->sleep_avg = 0; - if (!(HIGH_CREDIT(prev) || LOW_CREDIT(prev))) - prev->interactive_credit--; - } - prev->timestamp = now; - + /* + * Update estimate of average CPU time used per cycle + */ + delta = (rq->timestamp_last_tick - prev->sched_timestamp); + prev->avg_cpu_per_cycle += delta; + prev->total_cpu += delta; + prev->timestamp = prev->sched_timestamp = rq->timestamp_last_tick; + if (likely(prev != next)) { - next->timestamp = now; + rq->preempted = 0; + rq->cache_ticks = 0; + /* + * Update estimate of average delay on run queue per cycle + */ + delta = (rq->timestamp_last_tick - next->sched_timestamp); + next->avg_delay_per_cycle += delta; + next->total_delay += delta; + next->timestamp = next->sched_timestamp = rq->timestamp_last_tick; + rq->total_delay += delta; rq->nr_switches++; rq->curr = next; ++*switch_count; @@ -2560,9 +2467,8 @@ void set_user_nice(task_t *p, long nice) { unsigned long flags; - prio_array_t *array; runqueue_t *rq; - int old_prio, new_prio, delta; + int queued, delta; if (TASK_NICE(p) == nice || nice < -20 || nice > 19) return; @@ -2577,30 +2483,27 @@ * it wont have any effect on scheduling until the task is * not SCHED_NORMAL: */ - if (rt_task(p)) { - p->static_prio = NICE_TO_PRIO(nice); - goto out_unlock; - } - array = p->array; - if (array) - dequeue_task(p, array); - - old_prio = p->prio; - new_prio = NICE_TO_PRIO(nice); - delta = new_prio - old_prio; + if ((queued = (!rt_task(p) && task_queued(p)))) + dequeue_task(p); + + delta = PRIO_TO_NICE(p->static_prio) - nice; p->static_prio = NICE_TO_PRIO(nice); - p->prio += delta; - if (array) { - enqueue_task(p, array); + if (queued) { + int new_prio = effective_prio(p); + + enqueue_task(p, rq, new_prio); + if (task_running(rq, p)) + rq->current_prio_slot = rq->queues + new_prio; + /* - * If the task increased its priority or is running and - * lowered its priority, then reschedule its CPU: + * If the task increased its setting or is running and lowered + * its setting, then reschedule its CPU: */ - if (delta < 0 || (delta > 0 && task_running(rq, p))) + if ((delta > 0) || ((delta < 0) && task_running(rq, p))) resched_task(rq->curr); } -out_unlock: + task_rq_unlock(rq, &flags); } @@ -2660,7 +2563,7 @@ */ int task_prio(task_t *p) { - return p->prio - MAX_RT_PRIO; + return effective_prio(p) - MAX_RT_PRIO; } /** @@ -2697,13 +2600,9 @@ /* Actually do priority change: must hold rq lock. */ static void __setscheduler(struct task_struct *p, int policy, int prio) { - BUG_ON(p->array); + BUG_ON(task_queued(p)); p->policy = policy; p->rt_priority = prio; - if (policy != SCHED_NORMAL) - p->prio = MAX_USER_RT_PRIO-1 - p->rt_priority; - else - p->prio = p->static_prio; } /* @@ -2713,8 +2612,7 @@ { struct sched_param lp; int retval = -EINVAL; - int oldprio; - prio_array_t *array; + int queued; unsigned long flags; runqueue_t *rq; task_t *p; @@ -2774,24 +2672,23 @@ if (retval) goto out_unlock; - array = p->array; - if (array) + if ((queued = task_queued(p))) deactivate_task(p, task_rq(p)); retval = 0; - oldprio = p->prio; __setscheduler(p, policy, lp.sched_priority); - if (array) { - __activate_task(p, task_rq(p)); + if (queued) { + int prio = effective_prio(p); + + __activate_task(p, task_rq(p), prio); /* * Reschedule if we are currently running on this runqueue and * our priority decreased, or if we are not currently running on * this runqueue and our priority is higher than the current's */ - if (task_running(rq, p)) { - if (p->prio > oldprio) - resched_task(rq->curr); - } else if (TASK_PREEMPTS_CURR(p, rq)) + if (preemption_warranted(prio, p, rq)) resched_task(rq->curr); + if (task_running(rq, p)) + rq->current_prio_slot = rq->queues + prio; } out_unlock: @@ -2980,31 +2877,115 @@ return real_len; } +void get_task_sched_stats(const struct task_struct *tsk, struct task_sched_stats *stats) +{ + int on_runq = 0; + int on_cpu = 0; + unsigned long long timestamp; + runqueue_t *rq = this_rq_lock(); + + stats->timestamp = rq->timestamp_last_tick; + stats->avg_sleep_per_cycle = tsk->avg_sleep_per_cycle; + stats->avg_delay_per_cycle = tsk->avg_delay_per_cycle; + stats->avg_cpu_per_cycle = tsk->avg_cpu_per_cycle; + stats->cycle_count = tsk->cycle_count; + stats->total_sleep = tsk->total_sleep; + stats->total_cpu = tsk->total_cpu; + stats->total_delay = tsk->total_delay; + timestamp = tsk->sched_timestamp; + if ((on_runq = task_queued(tsk))) + on_cpu = rq->idle == tsk; + + rq_unlock(rq); + + /* + * Update values to the previous tick (only) + */ + if (stats->timestamp > timestamp) { + unsigned long long delta = stats->timestamp - timestamp; + + if (on_cpu) { + stats->avg_cpu_per_cycle += delta; + stats->total_cpu += delta; + } else if (on_runq) { + stats->avg_delay_per_cycle += delta; + stats->total_delay += delta; + } else { + stats->avg_sleep_per_cycle += delta; + stats->total_sleep += delta; + } + } + /* + * Convert internal "real number" representation of average times + * to integer values in nanoseconds + */ + stats->avg_sleep_per_cycle = SCHED_AVG_RND(stats->avg_sleep_per_cycle); + stats->avg_cpu_per_cycle = SCHED_AVG_RND(stats->avg_cpu_per_cycle); + stats->avg_delay_per_cycle = SCHED_AVG_RND(stats->avg_delay_per_cycle); +} + +EXPORT_SYMBOL(get_task_sched_stats); + +/* + * Get scheduling statistics for the nominated CPU + */ +void get_cpu_sched_stats(unsigned int cpu, struct cpu_sched_stats *stats) +{ + int idle; + unsigned long long idle_timestamp; + runqueue_t *rq = cpu_rq(cpu); + + /* + * No need to crash the whole machine if they've asked for stats for + * a non existent CPU, just send back zero. + */ + if (rq == NULL) { + stats->timestamp = 0; + stats->total_idle = 0; + stats->total_busy = 0; + stats->total_delay = 0; + stats->nr_switches = 0; + + return; + } + local_irq_disable(); + spin_lock(&rq->lock); + idle = rq->curr == rq->idle; + stats->timestamp = rq->timestamp_last_tick; + idle_timestamp = rq->idle->sched_timestamp; + stats->total_idle = rq->idle->total_cpu; + stats->total_busy = rq->idle->total_delay; + stats->total_delay = rq->total_delay; + stats->nr_switches = rq->nr_switches; + rq_unlock(rq); + + /* + * Update idle/busy time to the current tick + */ + if (idle) + stats->total_idle += (stats->timestamp - idle_timestamp); + else + stats->total_busy += (stats->timestamp - idle_timestamp); +} + +EXPORT_SYMBOL(get_cpu_sched_stats); + /** * sys_sched_yield - yield the current processor to other threads. * - * this function yields the current CPU by moving the calling thread - * to the expired array. If there are no other threads running on this * CPU then this function will return. */ asmlinkage long sys_sched_yield(void) { runqueue_t *rq = this_rq_lock(); - prio_array_t *array = current->array; - prio_array_t *target = rq->expired; - /* - * We implement yielding by moving the task into the expired - * queue. - * - * (special rule: RT tasks will just roundrobin in the active - * array.) - */ - if (unlikely(rt_task(current))) - target = rq->active; - - dequeue_task(current, array); - enqueue_task(current, target); + dequeue_task(current); + current->slice = slice(current); + current->time_slice = RR_INTERVAL; + if (!rt_task(current)) + rq->current_prio_slot = rq->queues + MAX_PRIO - 1; + current->burst = 0; + enqueue_task(current, rq, rq->current_prio_slot->prio); /* * Since we are going to call schedule() anyway, there's @@ -3143,7 +3124,7 @@ goto out_unlock; jiffies_to_timespec(p->policy & SCHED_FIFO ? - 0 : task_timeslice(p), &t); + 0 : slice(p), &t); read_unlock(&tasklist_lock); retval = copy_to_user(interval, &t, sizeof(t)) ? -EFAULT : 0; out_nounlock: @@ -3261,10 +3242,25 @@ idle_rq->curr = idle_rq->idle = idle; deactivate_task(idle, rq); - idle->array = NULL; - idle->prio = MAX_PRIO; + /* + * Initialize scheduling statistics counters as they may provide + * valuable about the CPU e.g. avg_cpu_time_per_cycle for the idle + * task will be an estimate of the average time the CPU is idle + */ + initialize_stats(idle); + idle->sched_timestamp = rq->timestamp_last_tick; idle->state = TASK_RUNNING; + idle->burst = 0; set_task_cpu(idle, cpu); + /* + * Putting the idle process onto a run queue simplifies the selection of + * the next task to run in schedule(). + */ + list_add_tail(&idle->run_list, &idle_rq->queues[IDLE_PRIO].queue); + /* + * The idle task is the current task on idle_rq + */ + idle_rq->current_prio_slot = idle_rq->queues + IDLE_PRIO; double_rq_unlock(idle_rq, rq); set_tsk_need_resched(idle); local_irq_restore(flags); @@ -3371,8 +3367,8 @@ if (!cpu_isset(dest_cpu, p->cpus_allowed)) goto out; - set_task_cpu(p, dest_cpu); - if (p->array) { + if (task_queued(p)) { + unsigned long long delta; /* * Sync timestamp with rq_dest's before activating. * The same thing could be achieved by doing this step @@ -3382,10 +3378,25 @@ p->timestamp = p->timestamp - rq_src->timestamp_last_tick + rq_dest->timestamp_last_tick; deactivate_task(p, rq_src); - activate_task(p, rq_dest, 0); - if (TASK_PREEMPTS_CURR(p, rq_dest)) + /* + * Do set_task_cpu() until AFTER we dequeue the task, since + * dequeue_task() relies on task_cpu() always being accurate. + */ + set_task_cpu(p, dest_cpu); + delta = (rq_dest->timestamp_last_tick - p->sched_timestamp); + p->avg_delay_per_cycle += delta; + p->total_delay += delta; + if (preemption_warranted(activate_task(p, rq_dest, 0), p, rq_dest)) resched_task(rq_dest->curr); + } else { + unsigned long long delta; + + set_task_cpu(p, dest_cpu); + delta = (rq_dest->timestamp_last_tick - p->sched_timestamp); + p->avg_sleep_per_cycle += delta; + p->total_sleep += delta; } + p->sched_timestamp = rq_dest->timestamp_last_tick; out: double_rq_unlock(rq_src, rq_dest); @@ -3533,9 +3544,11 @@ */ spin_lock_irqsave(&rq->lock, flags); - __setscheduler(p, SCHED_FIFO, MAX_RT_PRIO-1); /* Add idle task to _front_ of it's priority queue */ - __activate_idle_task(p, rq); + dequeue_task(p); + __setscheduler(p, SCHED_FIFO, MAX_RT_PRIO-1); + enqueue_task_head(p, rq, 0); + rq->nr_running++; spin_unlock_irqrestore(&rq->lock, flags); } @@ -3581,11 +3594,12 @@ rq = cpu_rq(cpu); kthread_stop(rq->migration_thread); rq->migration_thread = NULL; - /* Idle task back to normal (off runqueue, low prio) */ + /* Idle task back to normal in IDLE_PRIO slot */ rq = task_rq_lock(rq->idle, &flags); deactivate_task(rq->idle, rq); - rq->idle->static_prio = MAX_PRIO; + rq->idle->static_prio = IDLE_PRIO; __setscheduler(rq->idle, SCHED_NORMAL, 0); + enqueue_task(rq->idle, rq, IDLE_PRIO); task_rq_unlock(rq, &flags); BUG_ON(rq->nr_running != 0); @@ -3896,7 +3910,7 @@ void __init sched_init(void) { runqueue_t *rq; - int i, j, k; + int i, k; #ifdef CONFIG_SMP /* Set up an initial dummy domain for early boot */ @@ -3917,13 +3931,11 @@ #endif for (i = 0; i < NR_CPUS; i++) { - prio_array_t *array; - rq = cpu_rq(i); spin_lock_init(&rq->lock); - rq->active = rq->arrays; - rq->expired = rq->arrays + 1; - rq->best_expired_prio = MAX_PRIO; + + rq->cache_ticks = 0; + rq->preempted = 0; #ifdef CONFIG_SMP rq->sd = &sched_domain_init; @@ -3935,15 +3947,17 @@ #endif atomic_set(&rq->nr_iowait, 0); - for (j = 0; j < 2; j++) { - array = rq->arrays + j; - for (k = 0; k < MAX_PRIO; k++) { - INIT_LIST_HEAD(array->queue + k); - __clear_bit(k, array->bitmap); - } - // delimiter for bitsearch - __set_bit(MAX_PRIO, array->bitmap); - } + for (k = 0; k <= IDLE_PRIO; k++) { + rq->queues[k].prio = k; + INIT_LIST_HEAD(&rq->queues[k].queue); + } + bitmap_zero(rq->bitmap, NUM_PRIO_SLOTS); + // delimiter for bitsearch + __set_bit(IDLE_PRIO, rq->bitmap); + rq->current_prio_slot = rq->queues + (IDLE_PRIO - 20); + rq->timestamp_last_tick = sched_clock(); + rq->next_prom_due = (jiffies + get_prom_interval(rq)); + rq->total_delay = 0; } /* * We have to do a little magic to get the first Index: Linux-2.6.X/kernel/sysctl.c diff -u Linux-2.6.X/kernel/sysctl.c:1.1.1.9 Linux-2.6.X/kernel/sysctl.c:1.1.1.9.12.1.2.1 --- Linux-2.6.X/kernel/sysctl.c:1.1.1.9 Wed Jun 16 18:11:47 2004 +++ Linux-2.6.X/kernel/sysctl.c Thu Jun 17 16:47:14 2004 @@ -636,6 +636,30 @@ .mode = 0444, .proc_handler = &proc_dointvec, }, + { + .ctl_name = KERN_INTERACTIVE, + .procname = "interactive", + .data = &interactive, + .maxlen = sizeof (int), + .mode = 0644, + .proc_handler = &proc_dointvec, + }, + { + .ctl_name = KERN_COMPUTE, + .procname = "compute", + .data = &compute, + .maxlen = sizeof (int), + .mode = 0644, + .proc_handler = &proc_dointvec, + }, + { + .ctl_name = KERN_LOG_AT_EXIT, + .procname = "log_at_exit", + .data = &log_at_exit, + .maxlen = sizeof (int), + .mode = 0644, + .proc_handler = &proc_dointvec, + }, { .ctl_name = 0 } };