Skip to contentSkip to conversation

Staircase scheduler v7.3 for 2.6.7

PATCH In review Con Kolivas 2 participants 2 messages Jun 22, 2004

Subsystems (3)
Scheduler Proc filesystem Proc sysctl
lore
Share & tools
lore

Con Kolivas

author
#0 lore raw

PATCH 1/1 Staircase scheduler v7.3 for 2.6.7

This is a complete scheduler policy rewrite designed to be intrinsically interactive yet very simple and scalable. See previous announcements for more details.

This version addresses a few minor bugs that are somewhat difficult to stumble upon but can cause problems. Thanks to the many people who reported their experiences so far, and especially to Pauli Virtanen for extensive testing of a nasty bug and feedback along the way.

This version improves the gameplay on some games that seem to depend on yield() for locking in places (eg Unreal Tournament), as well as removing an "exploit".

Changes since 7.0:
7.1: Yield() wasn't putting yielded tasks last, yield logic improved.

7.2: Internal

7.3: Yielded tasks were gaining burst by yielding, this was removed
as it was inappropriately rewarding tasks that yielded. Forked tasks were gaining burst by forking. This was removed as for yield()

Full patches against 2.6.7 and incremental from previous versions of staircase can be found in the 2.6.7 directory and -ck1 incrementals in the 2.6.7-ck1/experimental directory from here:

http://ck.kolivas.org/patches/2.6/

Signed off by: Con Kolivas<[email protected]>

 7 files changed, 246 insertions(+), 609 deletions(-)
fs/proc/array.c +2 -2
diff -Naurp --exclude-from=/home/con/kernel/dontdiff linux-2.6.7-base/fs/proc/array.c linux-2.6.7-staircase7.3/fs/proc/array.c
@@ -155,7 +155,7 @@ static inline char * task_state(struct t
 	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 @@ 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->burst,
 	       	p->tgid,
 		p->pid, p->pid ? p->real_parent->pid : 0,
 		p->pid && p->ptrace ? p->parent->pid : 0,
include/linux/sched.h +4 -8
diff -Naurp --exclude-from=/home/con/kernel/dontdiff linux-2.6.7-base/include/linux/sched.h linux-2.6.7-staircase7.3/include/linux/sched.h
@@ -164,6 +164,7 @@ extern void show_stack(struct task_struc
 
 void io_schedule(void);
 long io_schedule_timeout(long timeout);
+extern int interactive, compute;
 
 extern void cpu_init (void);
 extern void trap_init(void);

@@ -325,7 +326,6 @@ extern struct user_struct *find_user(uid
 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;
 

@@ -392,16 +392,13 @@ struct task_struct {
 
 	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;

@@ -742,7 +739,6 @@ extern void FASTCALL(wake_up_forked_proc
  }
 #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
diff -Naurp --exclude-from=/home/con/kernel/dontdiff linux-2.6.7-base/include/linux/sysctl.h linux-2.6.7-staircase7.3/include/linux/sysctl.h
@@ -133,6 +133,8 @@ enum
 	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 */
 };
init/main.c +8 -1
diff -Naurp --exclude-from=/home/con/kernel/dontdiff linux-2.6.7-base/init/main.c linux-2.6.7-staircase7.3/init/main.c
@@ -314,8 +314,15 @@ static void __init smp_init(void)
 #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
kernel/exit.c +0 -1
diff -Naurp --exclude-from=/home/con/kernel/dontdiff linux-2.6.7-base/kernel/exit.c linux-2.6.7-staircase7.3/kernel/exit.c
@@ -96,7 +96,6 @@ repeat: 
 	p->parent->cmaj_flt += p->maj_flt + p->cmaj_flt;
 	p->parent->cnvcsw += p->nvcsw + p->cnvcsw;
 	p->parent->cnivcsw += p->nivcsw + p->cnivcsw;
-	sched_exit(p);
 	write_unlock_irq(&tasklist_lock);
 	spin_unlock(&p->proc_lock);
 	proc_pid_flush(proc_dentry);
kernel/sched.c +214 -597

1,213 lines not on this page · raw message

kernel/sysctl.c +16 -0
diff -Naurp --exclude-from=/home/con/kernel/dontdiff linux-2.6.7-base/kernel/sysctl.c linux-2.6.7-staircase7.3/kernel/sysctl.c
@@ -636,6 +636,22 @@ static ctl_table kern_table[] = {
 		.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 = 0 }
 };
#1 lore raw
Quoted 4 lines · Con Kolivas

This is a complete scheduler policy rewrite designed to be intrinsically interactive yet very simple and scalable. See previous announcements for more details.

Quoted 8 lines

This version addresses a few minor bugs that are somewhat difficult to stumble upon but can cause problems. Thanks to the many people who reported their experiences so far, and especially to Pauli Virtanen for extensive testing of a nasty bug and feedback along the way.

This version improves the gameplay on some games that seem to depend on yield() for locking in places (eg Unreal Tournament), as well as removing an "exploit".

No problems so far :-)
Nice work!