By now you should understand the basic machinery of running processes, including how to context-switch between processes and the details therein. Thus, the low-level mechanisms should be clear. However, we have yet to understand the high-level policies that the OS scheduler employs. In this note, we will do just that, presenting a series of scheduling policies (sometimes called disciplines) that people have developed over the years. We will now develop some scheduling policies that have been put forth through the years. The origins of scheduling, in fact, predate computer systems, as early approaches were taken from the field of operations management and applied to computer systems. This should be no surprise: assembly lines and many other human constructions also require scheduling.
7.1
Workload Assumptions
Before getting into the range of possible policies, let us first make a number of simplifying assumptions about the processes running in the system, sometimes collectively called the workload. These assumptions are clearly unrealistic, but that is alright (for now), because we will relax them as we go and eventually develop what we will refer to as ... (dramatic pause) ...
1
2
S CHEDULING : I NTRODUCTION a fully-operational scheduling discipline1 . We will make the following assumptions about the processes, sometimes called jobs, that are running in the system: 1. 2. 3. 4. Each job runs for the same amount of time. All jobs arrive at the same time. All jobs only use the CPU (i.e., they perform no I/O) The run-time of each job is known.
We said all of these assumptions were unrealistic, but just as some animals are more equal than others in Orwell’s Animal Farm [O45], some assumptions are more unrealistic than others in this chapter. In particular, it might bother you that the run-time of each job is known: this would make the scheduler omniscient, which, although it would be great (probably), is not likely to happen anytime soon.
7.2 Scheduling Metrics
Beyond making workload assumptions, we also need one more thing to enable us to compare different scheduling policies: a scheduling metric. A metric is just something that we use to measure something, and of course there are a number of different metrics that make sense in scheduling. For now, however, let us also simplify our life by simply having a single metric: turnaround time. The turnaround time of a job, is defined as the time at which the job finally completes minus the time at which the job arrived in the system. More formally, the turnaround time Tturnaround is: Tturnaround = Tcompletion − Tarrival (7.1)
Because we have assumed that all jobs arrive at the same time, for now Tarrival = 0 and hence Tturnaround = Tcompletion . This fact will change as we relax the aforementioned assumptions. You should note that turnaround time is a performance metric, which will be our primary focus this chapter. Another metric of interest is fairness, as measured (for example) by Jain’s Fairness Index [J91]. Performance and fairness are often at odds in scheduling; a
1
Said in the same way you would say “A fully-operational Death Star.”
O PERATING S YSTEMS
A RPACI -D USSEAU
S CHEDULING : I NTRODUCTION scheduler, for example, may optimize performance but at the cost of preventing a few jobs from running, thus decreasing fairness. This conundrum shows us that life isn’t always perfect.
3
7.3
First In, First Out (FIFO)
The most basic algorithm a scheduler can implement is known as First In, First Out (FIFO) scheduling or sometimes First Come, First Served (FCFS). FIFO has a number of positive properties: it is clearly very simple and thus easy to implement. And given our assumptions, it works pretty well. Let’s do a quick example together. Imagine three jobs arrive in the system, A, B, and C, at roughly the same time (Tarrival = 0). Because FIFO has to put some job first, let’s assume that while they all
