Staircase cpu scheduler v13
Subsystems (3)
PATCH 1/1 Staircase cpu scheduler v13
Brief summary:
A complete cpu process scheduler policy rewrite based on the current O(1) scheduler.
It uses a single priority array in a modified foreground-background design.
Each task starts at a dynamic priority dependant initially on the nice level it is started at and then drops by one dynamic priority after one round-robin interval (currently set to 5ms). Once it reaches lowest dynamic priority and completes an RR there it is elevated back to its best dynamic prority.
The problem till now in current scheduler policies - nice was a determinant of cpu% and hard intrinsic latency. There was no way relatively niced tasks could get low latency no matter how little cpu they used in the presence of a less niced task.
Changes in staircase v13
Based on the percentage of time sleeping compared to the time running (and therefore the %cpu) accurately measured with the tsc clock in nanosecond resolution, the highest dynamic priority is determined.
Any nice level can run at every possible internal dynamic priority from 0 to 39.
Nice -20 tasks always start at 0 and drop by one every rr interval till they reach 39.
Nice 0 tasks start initially at dynamic priority 20 and drop till they reach
39. If they use less than 50% cpu (sleep 40 vs 20) they can start at dynamic priority 0
Nice 19 tasks start at 39. If they use less than 2.5% cpu (sleep 40 vs 1) then can start at dynamic priority 0.
Latest patch available here:
http://ck.kolivas.org/patches/staircase
and attached below is a full patch against 2.6.14.
Cheers,
Con
fs/proc/array.c | 4 include/linux/sched.h | 14 include/linux/sysctl.h | 2 kernel/exit.c | 1 kernel/sched.c | 1005 +++++++++++++++++++------------------------------ kernel/sysctl.c | 16 6 files changed, 425 insertions(+), 617 deletions(-)
fs/proc/array.c +2 -2
@@ -165,7 +165,7 @@ static inline char * task_state(struct tread_lock (&tasklist_lock); buffer +=sprintf (buffer,"State:\t%s\n" -"SleepAVG:\t%lu%%\n" +"Bonus:\t%d\n" "Tgid:\t%d\n" "Pid:\t%d\n" "PPid:\t%d\n"
@@ -173,7 +173,7 @@ static inline char * task_state(struct t"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->bonus, p->tgid, p->pid,pid_alive (p) ? p->group_leader->real_parent->tgid :0 , pid_alive(p) && p->ptrace ? p->parent->pid : 0,
include/linux/sched.h +7 -7
@@ -196,6 +196,7 @@ extern void show_stack(struct task_strucvoid 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 );
@@ -478,7 +479,6 @@ extern struct user_struct *find_user(uidextern struct user_struct root_user;#define INIT_USER (&root_user) -typedef struct prio_array prio_array_t ;struct backing_dev_info ;struct reclaim_state ;
@@ -653,18 +653,17 @@ struct task_struct {#endif int prio, static_prio;struct list_head run_list; -prio_array_t *array;unsigned short ioprio; -unsigned long sleep_avg; -unsigned long long timestamp, last_ran; +unsigned long long timestamp; +unsigned long runtime, totalrun, ns_debit; +unsigned int bonus; +unsigned int slice, time_slice;unsigned long long sched_time;/* sched_clock time spent running */ -int activated;unsigned long policy;cpumask_t cpus_allowed; -unsigned int time_slice, first_time_slice;#ifdef CONFIG_SCHEDSTATS struct sched_info sched_info;
@@ -864,6 +863,8 @@ do { if (atomic_dec_and_test(&(tsk)->usa#define PF_SYNCWRITE 0x00200000/* I am doing a sync write */ #define PF_BORROWED_MM 0x00400000/* I am a kthread doing use_mm */ #define PF_RANDOMIZE 0x00800000/* randomize virtual address space */ +#define PF_NONSLEEP 0x01000000/* Waiting on in kernel activity */ +#define PF_YIELDED 0x02000000/* I have just yielded */ /* * Only the _current_ task can read/write to tsk->flags, but other
@@ -985,7 +986,6 @@ extern void FASTCALL(wake_up_new_task(ststatic inline void kick_process (struct task_struct *tsk) { }#endif extern void FASTCALL (sched_fork (task_t * p,int clone_flags)); -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
@@ -146,6 +146,8 @@ enumKERN_RANDOMIZE =68 ,/* int: randomize virtual address space */ KERN_SETUID_DUMPABLE =69 ,/* int: behaviour of dumps for setuid core */ KERN_SPIN_RETRY =70 ,/* int: number of spinlock retries */ +KERN_INTERACTIVE =71 ,/* interactive tasks can have cpu bursts */ + KERN_COMPUTE=72, /* adjust timeslices for a compute server */ };
kernel/exit.c +0 -1
@@ -100,7 +100,6 @@ repeat: zap_leader = (leader->exit_signal ==-1 ); } -sched_exit (p);write_unlock_irq (&tasklist_lock);spin_unlock (&p->proc_lock);proc_pid_flush (proc_dentry);
kernel/sched.c +398 -607
1,561 lines not on this page · raw message
kernel/sysctl.c +16 -0
@@ -618,6 +618,22 @@ static ctl_table kern_table[] = { .mode = 0444, .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, + }, #if defined(CONFIG_X86_LOCAL_APIC) && defined(CONFIG_X86) { .ctl_name = KERN_UNKNOWN_NMI_PANIC,