32 - Scheduling: Preemptive, Size-Based Policies

Summary

In this chapter, we discuss preemptive scheduling policies that make use of knowing the size of the job. As in the last chapter, we start by defining and evaluating preemptive priority queueing, and then we extend that analysis to the Preemptive-Shortest-Job-First (PSJF) scheduling policy.

Motivation

Recall that we can divide scheduling policies into non-preemptive policies and preemptive policies.

Question: What is discouraging about the mean response time of all the non-preemptive scheduling policies that we have looked at?

Answer: They all have an E[S²] factor that comes from waiting for the excess of the job in service. This is a problem under highly variable job size distributions.

We have also looked at preemptive policies. These tend to do better with respect to mean response time under highly variable job size distributions. Not all of these have equal performance, however. Preemptive policies like PS and PLCFS that do not make use of size have mean response time equal to that of M/M/1/FCFS; namely, they are insensitive to the job size distribution beyond its mean. This is already far better than non-preemptive scheduling policies, when the job size distribution has high variability. However, preemptive policies that make use of size or age can do even better by biasing toward jobs with small size. So far, we have seen this only for the FB scheduling policy that favors jobs with small age. In this chapter and the next, we will examine policies that make use of a job's (original) size and remaining size.