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[S2] 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.

Part IV introduces both discrete-time Markov chains (referred to as DTMCs) and continuous-time Markov chains (referred to as CTMCs). These allow us to model systems in much greater detail and to answer distributional questions, such as “What is the probability that there are k jobs queued at server i?” Markov chains are extremely powerful. However, only certain problems can be modeled via Markov chains. These are problems that exhibit the Markovian property, which allows the future behavior to be independent of all past behavior.

Chapter 8 introduces DTMCs and the Markovian property. We purposely defer the more theoretical issues surrounding ergodicity, including the existence of a limiting distribution and the equivalence between time averages and ensemble averages, to Chapter 9. Less theoretically inclined readers may wish to skim Chapter 9 during a first reading. Chapter 10 considers some real-world examples of DTMCs in computing today, including Google's PageRank algorithm and the Aloha (Ethernet) protocol. This chapter also considers more complex DTMCs that occur naturally and how generating functions can be used to solve them.

Next we transition to CTMCs. Chapter 11 discusses the Markovian property of the Exponential distribution and the Poisson process, which make these very applicable to CTMCs. Chapter 12 shows an easy way to translate all that we learned for DTMCs to CTMCs. Chapter 13 applies CTMC theory to analyzing the M/M/1 single-server queue and also covers the PASTA property.

Part III is about operational laws. Operational laws are very powerful because they apply to any system or part of a system. They are both simple and exact. A very important feature of operational laws is that they are “distribution independent.” This means, for example, that the laws do not depend on the distribution of the job service requirements (job sizes), just on their mean. Likewise the results do not depend on the distribution of the job interarrival times, just on the mean arrival rate. The fact that the results do not require the Markovian assumptions that we will see in Part IV, coupled with the fact that using operational laws is so easy, makes these laws very popular with system builders.

The most important operational law that we will study is Little's Law, which relates the mean number of jobs in any system to the mean response time experienced by arrivals to that system. We will study Little's Law and several other operational laws in Chapter 6.

In Chapter 7 we will see how to put together several operational laws to prove asymptotic bounds on system behavior (specifically, mean response time and throughput) for closed systems. Asymptotic bounds will be proven both in the limit as the multiprogramming level approaches infinity and in the limit as the multiprogramming level approaches 1. These asymptotic bounds will be very useful in allowing us to answer “what-if” questions of the form, “Is it preferable to increase the speed of the CPU by a factor of 2, or to increase the speed of the I/O device by a factor of 3, or does neither really make a difference?”

Part VII is dedicated to scheduling.

Scheduling is an extremely important topic in designing computer systems, manufacturing systems, hospitals, and call centers. The right scheduling policy can vastly reduce mean response time without requiring the purchase of faster machines. Scheduling can be thought of as improving performance for free. Scheduling is also used to optimize performance metrics other than mean response time, such as “fairness” among users, and to provide differentiated levels of service where some class of jobs is guaranteed lower mean delay than other classes.

Stochastic scheduling analysis, even in the case of the M/G/1 queue, is not easy and is omitted from most textbooks. A notable exception is the 1967 Conway, Maxwell, and Miller book, Theory of Scheduling [45], which beautifully derives many of the known scheduling analyses.

In this part, we study scheduling in the M/G/1 queue, where G is continuous with finite mean and variance.We are interested in mean response time, the transform of response time, and other metrics like slowdown and fairness. Throughout we are interested in the effects of high variability in job size distribution.

Scheduling policies can be categorized based on whether the policy is preemptive or non-preemptive. A policy is preemptive if a job may be stopped partway through its execution and then resumed at a later point in time from the same point where it was stopped (this is also called preemptive-resume). A policy is non-preemptive if jobs are always run to completion. Scheduling policies can be differentiated further based on whether the policy assumes knowledge of the job sizes.

Many practical problems can be represented by a small finite-state CTMC. When this happens, one is always happy. A finite-state CTMC, whose transition rates are numbers (not variables), can always be solved, given enough computational power, because it simply translates to a finite set of linear simultaneous equations. When transition rates are arbitrary parameters (λ's and μ's and such), the chain might still be solvable via symbolic manipulation, provided that the number of equations is not too great. Section 16.1 provides additional practice with setting up and solving finite-state CTMCs.

Unfortunately, many systems problems involve unbounded queues that translate into infinite-state CTMCs. We have already seen the M/M/1 and the M/M/k, which involve just a single queue and are solvable, even though the number of states is infinite. However, as we move to queueing networks (systems with multiple queues), we see that we need to track the number of jobs in each queue, resulting in a chain that is infinite in more than one dimension. At first such chains seem entirely intractable. Fortunately, it turns out that a very large class of such chains is easily solvable in closed form. This chapter, starting with Section 16.2 on time-reversibility and leading into Section 16.3 on Burke's theorem, provides us with the foundations needed to develop the theory of queueing networks, which will be the topic of the next few chapters.

In this chapter, we introduce Shortest-Remaining-Processing-Time (SRPT) scheduling. SRPT is even superior to the PSJF policy that we saw in the last chapter, because it takes a job's remaining service requirement into account, not just the original job size. We also compare all the scheduling policies that we have studied so far with respect to mean response time as a function of load and the variability of the job size distribution. Finally, we study the fairness of SRPT by comparing it to the (fair) PS policy and proving the All-Can-Win theorem.

Shortest-Remaining-Processing-Time (SRPT)

Under SRPT, at all times the server is working on that job with the shortest remaining processing time. The SRPT policy is preemptive so that a new arrival will preempt the current job serving if the new arrival has a shorter remaining processing time.

Observe that, under SRPT, once a job, j, starts running, it can only be preempted by a new arrival whose size is shorter than j's remaining time. In particular, any jobs that are in the system with j, while j is running, will never run before j completes.

Remember that in Exercise 2.3 we proved that SRPT achieves the lowest possible mean response time on every arrival sequence. In this section, we analyze the mean response time for SRPT in the M/G/1 setting.

Question: Can we look at SRPT as some type of preemptive priority system with classes?

Answer: No! The problem is that in SRPT a job's priority is its “remaining” size, which changes as the job ages. The preemptive priority model does not allow jobs to change priorities while in queue.

If servers were free, then every server farm would have an infinite number of servers, and no job would ever have to wait in a queue. Unfortunately, servers are not free to buy, and they are also not free to operate. Running servers consumes lots of power, and even leaving a server on, but idle, still consumes nearly 60% of the power consumed by a busy server [15]. Given these costs, it pays to spend some time thinking about how many servers one really needs. This subject is called capacity provisioning.

Observe that we can actually already, in theory, answer the question of how many servers we need to achieve a given Quality of Service (QoS) goal, based on the formulas we derived in Chapter 14. In that chapter, we considered the M/M/k server farm model and derived expressions for the distribution of the number of jobs in the system, the probability of queueing, PQ, and the expected response time, E[T]. Given a QoS constraint on E[T] or PQ, we can iterate over these formulas and deduce the exact number of servers, k, needed to achieve the desired constraint.

However, iterating over a formula is time consuming and also does not provide any intuitions for the result. The purpose of this chapter is to formulate intuitions and rules of thumb for understanding how many servers we need to achieve a certain QoS goal, and what the impact is of increasing the number of servers.

In this chapter we revisit server farms, however this time in the context of high-variability job sizes (indicative of the workloads described in Chapter 20), rather than Exponential job sizes.

The server farm architecture is ubiquitous in computer systems. Rather than using a single, powerful server to handle all incoming requests (assuming such a beast can even be purchased), it is more cost efficient to buy many slow, inexpensive servers and pool them together to harness their combined computational power. The server farm architecture is also popular for its flexibility: It is easy to add servers when load increases and easy to take away servers when the load drops. The term server farm is used to connote the fact that the servers tend to be co-located, in the same room or even on one rack.

Thus far, we have primarily studied server farms with a central queue, as in the M/M/k system, which we initially examined in Chapter 14 and then revisited from a capacity provisioning perspective in Chapter 15. In the M/M/k, jobs are held in a central queue, and only when a server is free does it take on the job at the head of the queue.

By contrast, in computer systems, most server farms do immediate dispatching (also known as task assignment), whereby incoming jobs are immediately assigned to servers (also known as hosts). There is typically no central queue; instead the queues are at the individual hosts.

The ad hoc World of Computer System Design

The design of computer systems is often viewed very much as an art rather than a science. Decisions about which scheduling policy to use, how many servers to run, what speed to operate each server at, and the like are often based on intuitions rather than mathematically derived formulas. Specific policies built into kernels are often riddled with secret “voodoo constants,” which have no explanation but seem to “work well” under some benchmarked workloads. Computer systems students are often told to first build the system and then make changes to the policies to improve system performance, rather than first creating a formal model and design of the system on paper to ensure the system meets performance goals.

Even when trying to evaluate the performance of an existing computer system, students are encouraged to simulate the system and spend many days running their simulation under different workloads waiting to see what happens. Given that the search space of possible workloads and input parameters is often huge, vast numbers of simulations are needed to properly cover the space. Despite this fact, mathematical models of the system are rarely created, and we rarely characterize workloads stochastically. There is no formal analysis of the parameter space under which the computer system is likely to perform well versus that under which it is likely to perform poorly.

If you are a theoretician, you probably are already starting to get uncomfortable with the way we use the word “average” without carefully defining it and, in particular, with the way we define the load ρ by seemingly dividing two averages. Everything we have said is correct, but we would like to prove this, rather than just assuming it. This chapter sets up the groundwork to allow us to make such claims about averages.

Before we can talk about averages, we first need to discuss convergence of random variables. In this chapter, we define the convergence of random variables and state some limit theorems. We then define two types of averages: ensemble averages and time averages. These are needed for the next chapter on Little's Law, which will allow us to formally relate mean response time to the mean number of jobs in the system and to properly define the load, ρ.

This chapter is more theoretically oriented and abstract than the rest of this book. It is not necessary for the reader to follow everything in this chapter to understand later chapters. A reader might wish to skim the chapter to pick up the basic terminology and then come back later for a more in-depth reading.

Although this chapter is somewhat formal, we are still just grazing the surface of this material. If you really want to understand the concepts in depth, we recommend reading a measure-theory book such as Halmos's book [80].

In Chapter 3 we reviewed the most common discrete and continuous random variables. This chapter shows how we can use the density function or cumulative distribution function for a distribution to generate instances of that distribution. For example, we might have a system in which the interarrival times of jobs are well modeled by an Exponential distribution and the job sizes (service requirements) are well modeled by a Normal distribution. To simulate the system, we need to be able to generate instances of Exponential and Normal random variables. This chapter reviews the two basic methods used in generating random variables. Both these methods assume that we already have a generator of Uniform(0,1) random variables, as is provided by most operating systems.

Inverse-Transform Method

This method assumes that (i) we know the c.d.f. (cumulative distribution function), Fx (x) = P{X ± x}, of the random variable X that we are trying to generate, and (ii) that this distribution is easily invertible, namely that we can get x from FX (x).

The Continuous Case

Idea: We would like to map each instance of a uniform r.v. generated by our operating system – that is, u ∈ U (0, 1) – to some x, which is an instance of the random variable X, where X has c.d.f. FX. We assume WLOG that X ranges from 0 to ∞. Let's suppose there is some mapping that takes each u and assigns it a unique x. Such a mapping is illustrated by g-1(·) in Figure 4.1.

Let's review what we already know how to do at this point.

Closed Systems

For closed systems, we can approximate and bound the values of throughput, X, and the expected response time, E[R]. The approximations we have developed are independent of the distribution of service times of the jobs, but require that the system is closed. When the multiprogramming level, N, is much higher than N*, we have a tight bound on X and E[R]. Also, when N = 1, we have a tight bound. However, for intermediate values of N, we can only approximate X and E[R].

Open Systems

For open systems, we cannot do very much at all yet. Consider even a single queue. If we knew E[N], then we could calculate E[T], but we do not yet know how to compute E[N].

Markov chain analysis is a tool for deriving the above performance metrics and in fact deriving a lot more. It will enable us to determine not only the mean number of jobs, E[Ni], at server i of a queueing network, but also the full distribution of the number of jobs at the server.

All the chapters in Parts IV and V will exploit the power of Markov chain analysis. It is important, however, to keep in mind that not all systems can readily be modeled using Markov chains. We will see that, in queueing networks where the service times at a server are Exponentially distributed and the interarrival times of jobs are also Exponentially distributed, the system can often be exactly modeled by a Markov chain.