Scheduling

First-come first-served scheduling is also known as “First-In First-Out” (FIFO) or “run until done” scheduling. In early systems, FCFS scheduling meant that one program was scheduled until it was done (including I/O). Now, this means that the program keeps the CPU until the thread blocks.

This scheduling policy is simple and good at maximizing usage of the CPU, but it is not particularly fair to programs themselves. The convoy effect may occur, where a shorter program is stuck behind the execution of a very long program: with FCFS non-preemptive scheduling, “convoys” of small tasks tend to build up when a large one is running:

In the round robin scheduling scheme, each process gets a small unit of CPU time (the time quantum), usually 10-100 milliseconds. After the time quantum expires, the process is preempted and added to the end of the ready queue. Therefore, if there are \(n\) processes in the ready queue with a time quantum of \(q\) time units, then no process waits more than \((n-1)q\) time units:

Choosing \(q\) is important here: if \(q\) is too large, then it just becomes like FCFS; if \(q\) is very small, then the time is all spent on overhead. It is important to choose a \(q\) such that it is sufficiently longer than the time spent on overhead.

To implement RR in the kernel, we have a FIFO queue, just like FCFS. However, we preempt the job after the quantum expires using a timer interrupt.

If we knew the future, then we could use shortest job first scheduling, also sometimes called “shortest time to completion first” (STCF) scheduling. The idea is we run whatever job has the least amount of computation to do: this has a big effect on short jobs, but only a small effect on long ones.

A variant of this is shortest remaining time first (SRTF) scheduling, which is the preemptive version of SJF: if a job arrives and it has a shorter time to completion that the current job, we immediately preempt the CPU.

A clear issue is that SRTF can lead to starvation if we have a lot of small jobs, since the large jobs never get to run.

Obviously, we can’t predict the future. However, we can use SRTF as a yardstick for measuring other policies, since it is guaranteed to be the best at optimizing for average response time.

Priority allows us to do multi-level feedback scheduling: each priority level gets its own queue that can be processed in RR with some time quantum.

However, there can be some problems with this:

• starvation: lower priority jobs don’t get to run because of higher priority jobs
• priority inversion: happens when low priority task has lock needed by high-priority task, which usually involves a third intermediate priority task which prevents the high priority task from running

We can try to prevent starvation by giving each queue some fraction of the CPU. We can also attempt to increase the priority of jobs that don’t get service. The tradeoff here is that as we gain more fairness, we lose in average response time.

Note that starvation does not imply deadlock. Deadlock is a specific case of starvation that is unresolvable: starvation could resolve under the right circumstances.

Case study: Linux O (1) Scheduler

The Linux O(1) scheduler was a priority scheduler with 140 priority levels, with levels 0-99 for kernel/realtime tasks, levels 100-139 for user tasks, and a different time quantum per level. An active priority queue held the active processes waiting to be run, and once a process uses up its time quantum it is put on a expired priority queue. Once the scheduler processed all of programs on the active queue, the two queues would swap.

It was called the O(1) scheduler becaues it did not contain any algorithms that ran in worse than O(1) time

It also had a lot of ad-hoc heuristics: it tries to boost priority of “I/O-bound tasks”, as well as the priority of “starved tasks.” There was also an idea of interactive credit, where IC was earned when a task sleeps for a “long” time and spent when a task runs for a “long” time.

With lottery scheduling, we give each job some number of “tickets.” On each time slice, we randomly pick a winning ticket. On average, CPU time is proportional to the number of tickets given to each job.

In this way, we can assign tickets in a way that gives “priorities” to each job. However, by giving each job at least one ticket, we prevent starvation (since everyone will get a proportion of CPU time).

Stride scheduling is a deterministic version of a lottery scheduler. Each job is given some number of tickes \(n_i\), and the stride of a task is a number inversely proportional to the number of tickets, typically calculated as \(\frac{W}{n_i}\) where \(W\) is some large number.

On every time slice, the task with the lowest pass is chosen. The pass for a task is initialized to the minimum of all the existing tasks’ pass values when the task starts, and when a task is chosen, pass is incremented by stride. A smaller stride means that a task runs more often.

Our goal is to give each process an equal share of the CPU. The basic idea is to track CPU time per thread and schedule threads to match up average rate of execution. We want to choose the thread with the minimum CPU time such that we want to “repair” the illusion that each thread gets exactly 1/N of the CPU.

In addition to fairness, we also want to have low response time and starvation freedom. We can use a target latency to dynamically choose a time quantum (like RR) by dividing our target latency by the number of threads (e.g. 20 ms target latency over 4 threads means that each thread gets a 5 ms time slice).

However, we also want to avoid excessive overhead, so we must have a minimum length of any time slice. This minimum granularity constraint prevents the time slice from being so short that it is taken up completely by overhead.

But what if we want to give more CPU time to some processes than others (i.e. priority)? We can use weights instead to track virtual time instead of actual CPU time. The virtual time would be CPU time divided by weight, and so the same virtual time but different weights would result in differing CPU times.

Rate monotonic scheduling is a scheme that does not look at deadlines. Each process is assigned a unique priority based on its period, and we always execute the active job with the highest priority. The shorter the period, the higher the priority. If RMS meets deadlines, it will continue to meet deadlines. However it doesn’t always work:

We can compute the utilization of our tasks as \(U_i = \frac{C_i}{P_i}\). If the sum of utilizations of each task is greater than 1, we overload our processor and clearly it cannot work. However, for the above example, the sum of utilizations is \(0.936 < 1\), so what gives?

Turns out that RMS only works if we meet a stricter criteria:

\begin{align} \sum_{i=1}^n \left(\frac{C_i}{P_i}\right) \leq n(2^{\frac{1}{n}} - 1) \end{align}

where \(n\) is the number of tasks.

Earliest deadline first is a preemptive priority-based dynamic scheduling scheme that takes deadlines into account. The policy is to give CPU time to the active task with the closest absolute deadline. Then, schedulability is given by:

\begin{align} \sum_{i=1}^n \left(\frac{C_i}{P_i}\right) \leq 1 \end{align}

EDF minimizies the lateness of the “most tardy task.”

To detect deadlock, we can use a resource-allocation graph. Each resouce and thread is a node on the graph. We have two types of directed edges: a request edge, which represents a thread requesting a resource (from thread to resource), and a assignment edge, which represents a thread currently holding a resource (from resource to thread).

For our algorithm, [FreeResources] is a vector of the current free resources of each type, [Request_x] is a vector of the current requests from thread X, and [Alloc_x] are the current resources held by thread X. Then, we run:

[Avail] = [FreeResources]
Add all nodes to UNFINISHED
do {
    done = true
    foreach node in UNFINISHED {
    if [Request_node] <= [Avail] {
        remove node from UNFINISHED
        [Avail] = [Avail] + [Alloc_node]
        done = false
    }
} until done

Nodes that are left in UNFINISHED are deadlocked.

The banker’s algorithm is a deadlock avoidance technique. The thread states the maximum amount of resources of each type it needs. We then evaluate each request and grant it if some ordering of threads is still deadlock free afterward. The technique is to pretend that each request is granted, then run a modified deadlock detection algorithm:

[Avail] = [FreeResources]
Add all nodes to UNFINISHED
do {
    done = true
    foreach node in UNFINISHED {
    if [Max_node]-[Alloc_node] <= [Avail] {
        remove node from UNFINISHED
        [Avail] = [Avail] + [Alloc_node]
        done = false
    }
} until done

This algorithm instead pretends that the thread asks for every resource it needs at once. However, it is also less conservative because not every thread ordering has to prevent deadlock.