Performance Modeling and Design of Computer Systems
Queueing Theory in Action
By Mor Harchol-Balter
Publisher: Cambridge University Press
Print Publication Year: 2013
Online Publication Date:February 2013
Online ISBN:9781139226424
Hardback ISBN:9781107027503
Chapter DOI: http://dx.doi.org/10.1017/CBO9781139226424.040
Subjects: Computer Hardware, Architecture and Distributed Computing, Applied probability and stochastic networks
Image View Extract Fullview: Text View | Enlarge Image ‹ Previous Chapter ›Next Chapter
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.
pp. i-vi
pp. vii-xvi
pp. xvii-xxii
pp. xxiii-xxiv
I - Introduction to Queueing: Read PDF
pp. 1-2
1 - Motivating Examples of the Power of Analytical Modeling: Read PDF
pp. 3-12
2 - Queueing Theory Terminology: Read PDF
pp. 13-28
II - Necessary Probability Background: Read PDF
pp. 29-30
3 - Probability Review: Read PDF
pp. 31-69
4 - Generating Random Variables for Simulation: Read PDF
pp. 70-78
5 - Sample Paths, Convergence, and Averages: Read PDF
pp. 79-92
III - The Predictive Power of Simple Operational Laws: “What-If” Questions and Answers: Read PDF
pp. 93-94
6 - Little's Law and Other Operational Laws: Read PDF
pp. 95-113
7 - Modification Analysis: “What-If” for Closed Systems: Read PDF
pp. 114-126
IV - From Markov Chains to Simple Queues: Read PDF
pp. 127-128
8 - Discrete-Time Markov Chains: Read PDF
pp. 129-147
9 - Ergodicity Theory: Read PDF
pp. 148-189
10 - Real-World Examples: Google, Aloha, and Harder Chains: Read PDF
pp. 190-205
11 - Exponential Distribution and the Poisson Process: Read PDF
pp. 206-224
12 - Transition to Continuous-Time Markov Chains: Read PDF
pp. 225-235
13 - M/M/1 and PASTA: Read PDF
pp. 236-250
V - Server Farms and Networks: Multi-server, Multi-queue Systems: Read PDF
pp. 251-252
14 - Server Farms: M/M/k and M/M/k/k: Read PDF
pp. 253-268
15 - Capacity Provisioning for Server Farms: Read PDF
pp. 269-281
16 - Time-Reversibility and Burke's Theorem: Read PDF
pp. 282-296
17 - Networks of Queues and Jackson Product Form: Read PDF
pp. 297-310
18 - Classed Network of Queues: Read PDF
pp. 311-330
19 - Closed Networks of Queues: Read PDF
pp. 331-346
VI - Real-World Workloads: High Variability and Heavy Tails: Read PDF
pp. 347-348
20 - Tales of Tails: A Case Study of Real-World Workloads: Read PDF
pp. 349-358
21 - Phase-Type Distributions and Matrix-Analytic Methods: Read PDF
pp. 359-379
22 - Networks with Time-Sharing (PS) Servers (BCMP): Read PDF
pp. 380-394
23 - The M/G/1 Queue and the Inspection Paradox: Read PDF
pp. 395-407
24 - Task Assignment Policies for Server Farms: Read PDF
pp. 408-432
25 - Transform Analysis: Read PDF
pp. 433-449
26 - M/G/1 Transform Analysis: Read PDF
pp. 450-456
27 - Power Optimization Application: Read PDF
pp. 457-470
VII - Smart Scheduling in the M/G/1: Read PDF
pp. 471-472
28 - Performance Metrics: Read PDF
pp. 473-477
29 - Scheduling: Non-Preemptive, Non-Size-Based Policies: Read PDF
pp. 478-481
30 - Scheduling: Preemptive, Non-Size-Based Policies: Read PDF
pp. 482-498
31 - Scheduling: Non-Preemptive, Size-Based Policies: Read PDF
pp. 499-507
32 - Scheduling: Preemptive, Size-Based Policies: Read PDF
pp. 508-517
33 - Scheduling: SRPT and Fairness: Read PDF
pp. 518-530
pp. 531-540
pp. 541-548
No references available.