sched: implement staircase deadline cpu scheduler

Staircase Deadline cpu scheduler policy
================================================

Design summary
==============

A novel design which incorporates a foreground-background descending priority system (the staircase) via a bandwidth allocation matrix according to nice level.

Features
========

A starvation free, strict fairness O(1) scalable design with interactivity as good as the above restrictions can provide. There is no interactivity estimator, no sleep/run measurements and only simple fixed accounting. The design has strict enough a design and accounting that task behaviour can be modelled and maximum scheduling latencies can be predicted by the virtual deadline mechanism that manages runqueues. The prime concern in this design is to maintain fairness at all costs determined by nice level, yet to maintain as good interactivity as can be allowed within the constraints of strict fairness.

Design description
==================

SD works off the principle of providing each task a quota of runtime that it is allowed to run at a number of priority levels determined by its static priority (ie. its nice level). If the task uses up its quota it has its priority decremented to the next level determined by a priority matrix. Once every runtime quota has been consumed of every priority level, a task is queued on the "expired" array. When no other tasks exist with quota, the expired array is activated and fresh quotas are handed out. This is all done in O(1).

Design details
==============

Each task keeps a record of its own entitlement of cpu time. Most of the rest of these details apply to non-realtime tasks as rt task management is straight forward.

Each runqueue keeps a record of what major epoch it is up to in the rq->prio_rotation field which is incremented on each major epoch. It also keeps a record of the current prio_level for each static priority task.

Each task keeps a record of what major runqueue epoch it was last running on in p->rotation. It also keeps a record of what priority levels it has already been allocated quota from during this epoch in a bitmap p->bitmap.

The only tunable that determines all other details is the RR_INTERVAL. This is set to 8ms, and is scaled gently upwards with more cpus. This value is tunable via a /proc interface.

All tasks are initially given a quota based on RR_INTERVAL. This is equal to RR_INTERVAL between nice values of -6 and 0, half that size above nice 0, and progressively larger for nice values from -1 to -20. This is assigned to p->quota and only changes with changes in nice level.

As a task is first queued, it checks in recalc_task_prio to see if it has run at this runqueue's current priority rotation. If it has not, it will have its p->prio level set according to the first slot in a "priority matrix" and will be given a p->time_slice equal to the p->quota, and has its allocation bitmap bit set in p->bitmap for this prio level. It is then queued on the current active priority array.

If a task has already been running during this major epoch, and it has p->time_slice left and the rq->prio_quota for the task's p->prio still has quota, it will be placed back on the active array, but no more quota will be added.

If a task has been running during this major epoch, but does not have p->time_slice left, it will find the next lowest priority in its bitmap that it has not been allocated quota from. It then gets the a full quota in p->time_slice. It is then queued on the current active priority array at the newly determined lower priority.

If a task has been running during this major epoch, and does not have any entitlement left in p->bitmap and no time_slice left, it will have its bitmap cleared, and be queued at its best prio again, but on the expired priority array.

When a task is queued, it has its relevant bit set in the array->prio_bitmap.

p->time_slice is stored in nanosconds and is updated via update_cpu_clock on schedule() and scheduler_tick. If p->time_slice is below zero then the recalc_task_prio is readjusted and the task rescheduled.

Priority Matrix
===============

In order to minimise the latencies between tasks of different nice levels running concurrently, the dynamic priority slots where different nice levels are queued are dithered instead of being sequential. What this means is that there are 40 priority slots where a task may run during one major rotation, and the allocation of slots is dependant on nice level. In the following table, a zero represents a slot where the task may run.

nice -20 0000000000000000000000000000000000000000
nice -10 1001000100100010001001000100010010001000
nice 0 0101010101010101010101010101010101010101
nice 5 1101011010110101101011010110101101011011

nice  10 0110111011011101110110111011101101110111
nice  15 0111110111111011111101111101111110111111
nice  19 1111111111111111111011111111111111111111

As can be seen, a nice -20 task runs in every priority slot whereas a nice 19 task only runs one slot per major rotation. This dithered table allows for the smallest possible maximum latencies between tasks of varying nice levels, thus allowing vastly different nice levels to be used.

SCHED_BATCH tasks are managed slightly differently, receiving only the top slots from its priority bitmap giving it equal cpu as SCHED_NORMAL, but slightly higher latencies.

Modelling deadline behaviour
============================

As the accounting in this design is hard and not modified by sleep average calculations or interactivity modifiers, it is possible to accurately predict the maximum latency that a task may experience under different conditions. This is a virtual deadline mechanism enforced by mandatory timeslice expiration and not outside bandwidth measurement.

The maximum duration a task can run during one major epoch is determined by its nice value. Nice 0 tasks can run at 19 different priority levels for RR_INTERVAL duration during each epoch. Nice 10 tasks can run at 9 priority levels for each epoch, and so on. The table in the priority matrix above demonstrates how this is enforced.

Therefore the maximum duration a runqueue epoch can take is determined by the number of tasks running, and their nice level. After that, the maximum duration it can take before a task can wait before it get scheduled is determined by the position of its first slot on the matrix.

In the following examples, these are _worst case scenarios_ and would rarely occur, but can be modelled nonetheless to determine the maximum possible latency.

So for example, if two nice 0 tasks are running, and one has just expired as another is activated for the first time receiving a full quota for this runqueue rotation, the first task will wait:

nr_tasks * max_duration + nice_difference * rr_interval 1 * 19 * RR_INTERVAL + 0 = 152ms

In the presence of a nice 10 task, a nice 0 task would wait a maximum of 1 * 10 * RR_INTERVAL + 0 = 80ms

In the presence of a nice 0 task, a nice 10 task would wait a maximum of 1 * 19 * RR_INTERVAL + 1 * RR_INTERVAL = 160ms

More useful than these values, though, are the average latencies which are a matter of determining the average distance between priority slots of different nice values and multiplying them by the tasks' quota. For example in the presence of a nice -10 task, a nice 0 task will wait either one or two slots. Given that nice -10 tasks have a quota 2.5 times the RR_INTERVAL, this means the latencies will alternate between 2.5 and 5 RR_INTERVALs or 20 and 40ms respectively (on uniprocessor at 1000HZ).

Achieving interactivity
=======================

A requirement of this scheduler design was to achieve good interactivity despite being a completely fair deadline based design. The disadvantage of designs that try to achieve interactivity is that they usually do so at the expense of maintaining fairness. As cpu speeds increase, the requirement for some sort of metered unfairness towards interactive tasks becomes a less desirable phenomenon, but low latency and fairness remains mandatory to good interactive performance.

This design relies on the fact that interactive tasks, by their nature, sleep often. Most fair scheduling designs end up penalising such tasks indirectly giving them less than their fair possible share because of the sleep, and have to use a mechanism of bonusing their priority to offset this based on the duration they sleep. This becomes increasingly inaccurate as the number of running tasks rises and more tasks spend time waiting on runqueues rather than sleeping, and it is impossible to tell whether the task that's waiting on a runqueue only intends to run for a short period and then sleep again after than runqueue wait. Furthermore, all such designs rely on a period of time to pass to accumulate some form of statistic on the task before deciding on how much to give them preference. The shorter this period, the more rapidly bursts of cpu ruin the interactive tasks behaviour. The longer this period, the longer it takes for interactive tasks to get low scheduling latencies and fair cpu.

This design does not measure sleep time at all. Interactive tasks that sleep often will wake up having consumed very little if any of their quota for the current major priority rotation. The longer they have slept, the less likely they are to even be on the current major priority rotation. Once woken up, though, they get to use up a their full quota for that epoch, whether part of a quota remains or a full quota. Overall, however, they can still only run as much cpu time for that epoch as any other task of the same nice level. This means that two tasks behaving completely differently from fully cpu bound to waking/sleeping extremely frequently will still get the same quota of cpu, but the latter will be using its quota for that epoch in bursts rather than continuously. This guarantees that interactive tasks get the same amount of cpu as cpu bound ones.

The other requirement of interactive tasks is also to obtain low latencies for when they are scheduled. Unlike fully cpu bound tasks and the maximum latencies possible described in the modelling deadline behaviour section above, tasks that sleep will wake up with quota available usually at the current runqueue's priority_level or better. This means that the most latency they are likely to see is one RR_INTERVAL, and often they will preempt the current task if it is not of a sleeping nature. This then guarantees very low latency for interactive tasks, and the lowest latencies for the least cpu bound tasks.

One of the potential disadvantages of a strict fairness design is that users may prefer a degree of unfairness towards certain tasks (such as a gui) and will notice the relative slowdown that occurs under load. As the dithered matrix minimises the latencies when differential nice levels are used, this can be countered by running a gui at a negative nice value such as -10 without causing adversely large latencies in nice 0 tasks.

---

 Documentation/sysctl/kernel.txt |   12 
 include/linux/init_task.h       |    4 
 include/linux/sched.h           |   29 -
 kernel/sched.c                  | 1156 ++++++++++++++++++----------------------
 kernel/sysctl.c                 |   25 
 5 files changed, 577 insertions(+), 649 deletions(-)

Index: linux-2.6.21-rc5-sd/include/linux/init_task.h
===================================================================
@@ -102,13 +102,15 @@ extern struct group_info init_groups;
 	.prio		= MAX_PRIO-20,					\
 	.static_prio	= MAX_PRIO-20,					\
 	.normal_prio	= MAX_PRIO-20,					\
+	.rotation	= 0,						\
 	.policy		= SCHED_NORMAL,					\
 	.cpus_allowed	= CPU_MASK_ALL,					\
 	.mm		= NULL,						\
 	.active_mm	= &init_mm,					\
 	.run_list	= LIST_HEAD_INIT(tsk.run_list),			\
 	.ioprio		= 0,						\
-	.time_slice	= HZ,						\
+	.time_slice	= 1000000000,						\
+	.quota		= 1000000000,						\
 	.tasks		= LIST_HEAD_INIT(tsk.tasks),			\
 	.ptrace_children= LIST_HEAD_INIT(tsk.ptrace_children),		\
 	.ptrace_list	= LIST_HEAD_INIT(tsk.ptrace_list),		\

Index: linux-2.6.21-rc5-sd/include/linux/sched.h
===================================================================
@@ -522,8 +522,9 @@ struct signal_struct {
 
 #define MAX_USER_RT_PRIO	100
 #define MAX_RT_PRIO		MAX_USER_RT_PRIO
+#define PRIO_RANGE		(40)
 
-#define MAX_PRIO		(MAX_RT_PRIO + 40)
+#define MAX_PRIO		(MAX_RT_PRIO + PRIO_RANGE)
 
 #define rt_prio(prio)		unlikely((prio) < MAX_RT_PRIO)
 #define rt_task(p)		rt_prio((p)->prio)

@@ -788,13 +789,6 @@ struct mempolicy;
 struct pipe_inode_info;
 struct uts_namespace;
 
-enum sleep_type {
-	SLEEP_NORMAL,
-	SLEEP_NONINTERACTIVE,
-	SLEEP_INTERACTIVE,
-	SLEEP_INTERRUPTED,
-};
-
 struct prio_array;
 
 struct task_struct {

@@ -814,20 +808,33 @@ struct task_struct {
 	int load_weight;	/* for niceness load balancing purposes */
 	int prio, static_prio, normal_prio;
 	struct list_head run_list;
+	DECLARE_BITMAP(bitmap, PRIO_RANGE + 1);
+	/*
+	 * This bitmap shows what priorities this task has received quota
+	 * from for this major priority rotation on its current runqueue.
+	 */
 	struct prio_array *array;
+	unsigned long rotation;
+	/* Which major runqueue rotation did this task run */
 
 	unsigned short ioprio;
 #ifdef CONFIG_BLK_DEV_IO_TRACE
 	unsigned int btrace_seq;
 #endif
-	unsigned long sleep_avg;
 	unsigned long long timestamp, last_ran;
 	unsigned long long sched_time; /* sched_clock time spent running */
-	enum sleep_type sleep_type;
 
 	unsigned long policy;
 	cpumask_t cpus_allowed;
-	unsigned int time_slice, first_time_slice;
+	int time_slice;
+	/*
+	 * How much this task is entitled to run at the current priority
+	 * before being requeued at a lower priority.
+	 */
+	unsigned int first_time_slice;
+	/* Is this the very first time_slice this task has ever run. */
+	int quota;
+	/* How much this task receives at each priority level */
 
 #if defined(CONFIG_SCHEDSTATS) || defined(CONFIG_TASK_DELAY_ACCT)
 	struct sched_info sched_info;

Index: linux-2.6.21-rc5-sd/Documentation/sysctl/kernel.txt
===================================================================
@@ -43,6 +43,7 @@ show up in /proc/sys/kernel:
 - printk
 - real-root-dev               ==> Documentation/initrd.txt
 - reboot-cmd                  [ SPARC only ]
+- rr_interval
 - rtsig-max
 - rtsig-nr
 - sem

@@ -288,6 +289,17 @@ rebooting. ???
 
 ==============================================================
 
+rr_interval:
+
+This is the smallest duration that any cpu process scheduling unit
+will run for. Increasing this value can increase throughput of cpu
+bound tasks substantially but at the expense of increased latencies
+overall. This value is in _ticks_ and the default value chosen depends
+on the number of cpus available at scheduler initialisation. Valid
+values are from 1-100.
+
+==============================================================
+
 rtsig-max & rtsig-nr:
 
 The file rtsig-max can be used to tune the maximum number

Index: linux-2.6.21-rc5-sd/kernel/sysctl.c
===================================================================
@@ -76,6 +76,7 @@ extern int pid_max_min, pid_max_max;
 extern int sysctl_drop_caches;
 extern int percpu_pagelist_fraction;
 extern int compat_log;
+extern int rr_interval;
 
 /* this is needed for the proc_dointvec_minmax for [fs_]overflow UID and GID */
 static int maxolduid = 65535;

@@ -159,6 +160,13 @@ int sysctl_legacy_va_layout;
 #endif
 
 
+/* Constants for minimum and maximum testing in vm_table.
+   We use these as one-element integer vectors. */
+static int  __read_mostly zero;
+static int  __read_mostly one = 1;
+static int  __read_mostly one_hundred = 100;
+
+
 /* The default sysctl tables: */
 
 static ctl_table root_table[] = {

@@ -499,6 +507,17 @@ static ctl_table kern_table[] = {
 		.mode		= 0444,
 		.proc_handler	= &proc_dointvec,
 	},
+	{
+		.ctl_name	= CTL_UNNUMBERED,
+		.procname	= "rr_interval",
+		.data		= &rr_interval,
+		.maxlen		= sizeof (int),
+		.mode		= 0644,
+		.proc_handler	= &proc_dointvec_minmax,
+		.strategy	= &sysctl_intvec,
+		.extra1		= &one,
+		.extra2		= &one_hundred,
+	},
 #if defined(CONFIG_X86_LOCAL_APIC) && defined(CONFIG_X86)
 	{
 		.ctl_name       = KERN_UNKNOWN_NMI_PANIC,

@@ -607,12 +626,6 @@ static ctl_table kern_table[] = {
 	{ .ctl_name = 0 }
 };
 
-/* Constants for minimum and maximum testing in vm_table.
-   We use these as one-element integer vectors. */
-static int zero;
-static int one_hundred = 100;
-
-
 static ctl_table vm_table[] = {
 	{
 		.ctl_name	= VM_OVERCOMMIT_MEMORY,

-ck

There are also some instances of if (foo = bar()). Maybe someone who isn't buried in work (as you always are) can find time to review.

-Mike

I'll be dropping this from -mm now. I don't think we're learning anything more by having it in there and I generally want to get things more back into sync.

For the record, I don't recall any problem reports arising from SD's presence in -mm (Except for possibly Jiri's recent "many processes end up in D state", but we don't have a clue what's causing that yet).

Thanks. It was a worthwhile putting it in -mm anyway because it allowed me to shake up a lot of bugs and stabilise it. Now SD will stick around for comparison. It also appears to me, having discussed with many people now, that hardly anyone understands how it actually works. In summary it is an O(1) dual array bitmap lookup based system for creating a minimal overhead earliest eligible virtual deadline first design. I guess I never really made that clear and now, ironically, with people quoting papers on that particular design now I probably should have. I appreciate the code does not in any way make it clear that that's the case because of the unique approach I used and doesn't really do or display any calculations in the code; it is all managed by handing out entitlements at priority intervals.

Anyway, good, bad or indifferent I intend to keep it around for comparison to drive cfs further.

-ck

Well, just to let you know some of us really like the design, and prefer to use SD and have an extremely strict scheduling priority set through nice
levels, so it is not there just to drive CFS further :-) I imagine people
in the embedded world might want it for that reason, too.

  "One disk to rule them all, One disk to find them. One disk to bring
  them all and in the darkness grind them. In the Land of Redmond
  where the shadows lie." -- The Silicon Valley Tarot
  Henrique Holschuh