Workload Assumptions and Scheduling Metrics

We will make the following assumptions about the processes, sometimes called jobs, that are running in the system:

1. Each job runs for the same amount of time.
2. All the ​jobs arrive at the same time.
3. Once started, each job runs to completion.
4. All jobs only use the CPU (i.e., they perform no I/O).
5. The run-time of each job is known.

We said many of these assumptions were unrealistic, but just as some animals are more equal than others in Orwell’s Animal Farm“Animal Farm” by George Orwell. Secker and Warburg (London), 1945. A great but depressing allegorical book about power and its corruptions. Some say it is a critique of Stalin and the pre-WWII Stalin era in the U.S.S.R; we say it’s a critique of pigs., 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.

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 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 completes minus the time at which the job arrived in the system. More formally, the turnaround time $T$_$turnaround$ is:

$T$_$turnaround$ $=$ $T$_$completion$ $−$ $T$_$arrival$

Because we have assumed that all jobs arrive at the same time, for now, $T$_$arrival$ $= 0$ and hence $T$_$turnaround$ = $T$_$completion$. 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 in this chapter. Another metric of interest is fairness, as measured (for example) by Jain’s Fairness Index“The Art of Computer Systems Performance Analysis-Techniques for Experimental Design, Measurement, Simulation, and Modeling” by R. Jain. Interscience, New York, April 1991. The standard text on computer systems measurement. A great reference for your library, for sure.. Performance and fairness are often at odds in scheduling; a 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.