Staircase cpu scheduler 2.6.8-rc2-mm1
Subsystems (3)
PATCH 1/1 Staircase cpu scheduler 2.6.8-rc2-mm1
This is a rewrite of the scheduler policy for 2.6, based on the current O(1) scheduler. It removes a lot of complexity and replaces it with an obvious and simple design
Aims:
- Simple predictable design.
- Good scalability.
- Interactive by design rather than have complicated interactivity heuristics
- Maintain fairer cpu distribution with load
- Low scheduling latency for SCHED_NORMAL tasks.
- Low overhead.
- Making renicing processes actually matter for CPU distribution (nice 0 gets 19 times what nice +19 gets)
- Easily configured for different workloads (compute server, non-interactive)
Summary of design:
A descending foreground-background single runqueue per cpu priority array
Details:
This patch takes advantage of the existing infrastructure but has no expired array. Real time tasks are treated simiilary as the current fixed priority & timeslice system. The details are in the management of normal policy (SCHED_NORMAL) tasks.
Normal policy tasks have a dynamic priority that drops by one every RR_INTERVAL which equals 10ms. Once they drop to lowest priority they are requeued at their top dynamic priority again.
Every time a task sleeps it gains "burst" which allows them to stay at their highest priority for an extra interval per burst before dropping priority.
The sub-jiffy case is handled specially to prevent it fooling this system, by continuing their current timeslice next wakeup. Tasks that have just forked are also treated the same way.
Yield()ing is implemented by putting tasks to the end of the lowest priority queue, but once scheduled the task wakes up to it's normal first wake up priority.
Use a fixed font to see clearly:
ieRR_INTERVALs nice 0 task
20<-------------->40 PRI
11111111111111111111
21111111111111111110
31111111111111111100
and so on
nice +10 task
30<---->40 PRI
1111111111
2111111110
3111111100
and so on
This is how cpu distribution is kept proportional while optimising latency for interactive tasks (which wake frequently).
Features:
This scheduler has coded in 2 simple sysctl configuration options.
/proc/sys/kernel/interactive
is a sysctl which when set to 0 disables the burst mechanism entirely making all tasks descend the staircase in a more rigid manner and thus maintaining much stricter cpu distribution (ie suitable to multi-user setups, servers and non gui machines.) Since the design remains foreground-background descending interactivity is maintained but response becomes slower/proportional to load.
/proc/sys/kernel/compute
is a sysctl which puts the cpu scheduler in "computational" mode which is designed for optimal cpu throughput at the expense of latency. It enlarges timeslices to 10 times larger than default and introduces delayed preemption of normal tasks to optimise cpu cache utilisation. This mode effectively sets interactive to 0 as well.
With thanks to William Lee Irwin III and Zwane Mwaikambo for patches and debugging and Peter Williams for useful suggestions.
Patch against 2.6.8-rc2-mm1
fs/proc/array.c | 4 include/linux/sched.h | 15 include/linux/sysctl.h | 2 init/main.c | 1 kernel/exit.c | 1 kernel/sched.c | 865 ++++++++++++++----------------------------------- kernel/sysctl.c | 16 7 files changed, 283 insertions(+), 621 deletions(-)
fs/proc/array.c +2 -2
@@ -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,
include/linux/sched.h +7 -8
@@ -164,6 +164,7 @@void io_schedule (void );long io_schedule_timeout (long timeout); +extern int sched_interactive, sched_compute;extern void cpu_init (void );extern void trap_init (void );
@@ -339,7 +340,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 ;
@@ -414,16 +414,13 @@int prio, 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 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;
@@ -578,6 +575,9 @@#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 */ +#define PF_YIELDED 0x00800000/* I have just yielded */ +#define PF_UISLEEP 0x01000000/* Uninterruptible sleep */ #ifdef CONFIG_SMP #define SCHED_LOAD_SCALE 128UL/* increase resolution of load */
@@ -774,7 +774,6 @@static inline void kick_process (struct task_struct *tsk) { }#endif extern void FASTCALL (sched_fork (task_t * p)); -extern void FASTCALL (sched_exit (task_t * p));extern int in_group_p (gid_t );extern int in_egroup_p (gid_t );
include/linux/sysctl.h +2 -0
@@ -134,6 +134,8 @@KERN_SPARC_SCONS_PWROFF =64 ,/* int: serial console power-off halt */ KERN_HZ_TIMER =65 ,/* int: hz timer on or off */ KERN_UNKNOWN_NMI_PANIC =66 ,/* int: unknown nmi panic flag */ +KERN_INTERACTIVE =67 ,/* interactive tasks can have cpu bursts */ + KERN_COMPUTE=68, /* adjust timeslices for a compute server */ };
init/main.c +1 -0
@@ -685,6 +685,7 @@static int init (void * unused) {lock_kernel (); + current->prio =MAX_PRIO -1 ;/* * Tell the world that we're going to be the grim * reaper of innocent orphaned children.
kernel/exit.c +0 -1
@@ -96,7 +96,6 @@ p->parent->cnvcsw += p->nvcsw + p->cnvcsw; p->parent->cnivcsw += p->nivcsw + p->cnivcsw;perfctr_release_task (p); -sched_exit (p);write_unlock_irq (&tasklist_lock);spin_unlock (&p->proc_lock);proc_pid_flush (proc_dentry);
kernel/sched.c +255 -610
1,266 lines not on this page · raw message
kernel/sysctl.c +16 -0
@@ -915,6 +915,22 @@ .mode = 0644, .proc_handler = &proc_dointvec, }, + { + .ctl_name = KERN_INTERACTIVE, + .procname = "interactive", + .data = &sched_interactive, + .maxlen = sizeof (int), + .mode = 0644, + .proc_handler = &proc_dointvec, + }, + { + .ctl_name = KERN_COMPUTE, + .procname = "compute", + .data = &sched_compute, + .maxlen = sizeof (int), + .mode = 0644, + .proc_handler = &proc_dointvec, + }, { .ctl_name = 0 } };