第1页 / 共574页
第2页 / 共574页
第3页 / 共574页
第4页 / 共574页
第5页 / 共574页
第6页 / 共574页
第7页 / 共574页
第8页 / 共574页
Performance Modeling and Design of Computer Systems Queueing Theory in Action.pdf
Contents
Preface
The ad hoc World of Computer System Design
Analytical Modeling for Computer Systems
The Goal of This Book
How This Book Came to Be
Outline of the Book
Acknowledgments
Part I Introduction to Queueing
Chapter 1 Motivating Examples of the Power of Analytical Modeling
1.1 What Is Queueing Theory?
1.2 Examples of the Power of Queueing Theory
Chapter 2 Queueing Theory Terminology
2.1 Where We Are Heading
2.2 The Single-Server Network
2.3 Classification of Queueing Networks
2.4 Open Networks
2.5 More Metrics: Throughput and Utilization
2.6 Closed Networks
2.7 Differences between Closed and Open Networks
2.8 Related Readings
2.9 Exercises
Part II Necessary Probability Background
Chapter 3 Probability Review
3.1 Sample Space and Events
3.2 Probability Defined on Events
3.3 Conditional Probabilities on Events
3.4 Independent Events and Conditionally Independent Events
3.5 Law of Total Probability
3.6 Bayes Law
3.7 Discrete versus Continuous Random Variables
3.8 Probabilities and Densities
3.9 Expectation and Variance
3.10 Joint Probabilities and Independence
3.11 Conditional Probabilities and Expectations
3.12 Probabilities and Expectations via Conditioning
3.13 Linearity of Expectation
3.14 Normal Distribution
3.15 Sum of a Random Number of Random Variables
3.16 Exercises
Chapter 4 Generating Random Variables for Simulation
4.1 Inverse-Transform Method
4.2 Accept-Reject Method
4.3 Readings
4.4 Exercises
Chapter 5 Sample Paths, Convergence, and Averages
5.1 Convergence
5.2 Strong and Weak Laws of Large Numbers
5.3 Time Average versus Ensemble Average
5.4 Related Readings
5.5 Exercise
Part III The Predictive Power of Simple Operational Laws: ``What-If'' Questions and Answers
Chapter 6 Little's Law and Other Operational Laws
6.1 Little's Law for Open Systems
6.2 Intuitions
6.3 Little's Law for Closed Systems
6.4 Proof of Little's Law for Open Systems
6.5 Proof of Little's Law for Closed Systems
6.6 Generalized Little's Law
6.7 Examples Applying Little's Law
6.8 More Operational Laws: The Forced Flow Law
6.9 Combining Operational Laws
6.10 Device Demands
6.11 Readings and Further Topics Related to Little's Law
6.12 Exercises
Chapter 7 Modification Analysis: ``What-If'' for Closed Systems
7.1 Review
7.2 Asymptotic Bounds for Closed Systems
7.3 Modification Analysis for Closed Systems
7.4 More Modification Analysis Examples
7.5 Comparison of Closed and Open Networks
7.6 Readings
7.7 Exercises
Part IV From Markov Chainsto Simple Queues
Chapter 8 Discrete-Time Markov Chains
8.1 Discrete-Time versus Continuous-Time Markov Chains
8.2 Definition of a DTMC
8.3 Examples of Finite-State DTMCs
8.4 Powers of P: n-Step Transition Probabilities
8.5 Stationary Equations
8.6 The Stationary Distribution Equals the Limiting Distribution
8.7 Examples of Solving Stationary Equations
8.8 Infinite-State DTMCs
8.9 Infinite-State Stationarity Result
8.10 Solving Stationary Equations in Infinite-State DTMCs
8.11 Exercises
Chapter 9 Ergodicity Theory
9.1 Ergodicity Questions
9.2 Finite-State DTMCs
9.3 Infinite-State Markov Chains
9.4 Ergodic Theorem of Markov Chains
9.5 Time Averages
9.6 Limiting Probabilities Interpreted as Rates
9.7 Time-Reversibility Theorem
9.8 When Chains Are Periodic or Not Irreducible
9.9 Conclusion
9.10 Proof of Ergodic Theorem of Markov Chains
9.11 Exercises
Chapter 10 Real-World Examples: Google, Aloha, and Harder Chains
10.1 Google's PageRank Algorithm
10.2 Aloha Protocol Analysis
10.3 Generating Functions for Harder Markov Chains
10.4 Readings and Summary
10.5 Exercises
Chapter 11 Exponential Distribution and the Poisson Process
11.1 Definition of the Exponential Distribution
11.2 Memoryless Property of the Exponential
11.3 Relating Exponential to Geometric via -Steps
11.4 More Properties of the Exponential
11.5 The Celebrated Poisson Process
11.6 Merging Independent Poisson Processes
11.7 Poisson Splitting
11.8 Uniformity
11.9 Exercises
Chapter 12 Transition to Continuous-Time Markov Chains
12.1 Defining CTMCs
12.2 Solving CTMCs
12.3 Generalization and Interpretation
12.4 Exercises
Chapter 13 M/M/1 and PASTA
13.1 The M/M/1 Queue
13.2 Examples Using an M/M/1 Queue
13.3 PASTA
13.4 Further Reading
13.5 Exercises
Part V Server Farms and Networks: Multi-server, Multi-queue Systems
Chapter 14 Server Farms: M/M/k and M/M/k/k
14.1 Time-Reversibility for CTMCs
14.2 M/M/k/k Loss System
14.3 M/M/k
14.4 Comparison of Three Server Organizations
14.5 Readings
14.6 Exercises
Chapter 15 Capacity Provisioning for Server Farms
15.1 What Does Load Really Mean in an M/M/k?
15.2 The M/M/
15.3 Square-Root Staffing
15.4 Readings
15.5 Exercises
Chapter 16 Time-Reversibility and Burke's Theorem
16.1 More Examples of Finite-State CTMCs
16.2 The Reverse Chain
16.3 Burke's Theorem
16.4 An Alternative (Partial) Proof of Burke's Theorem
16.5 Application: Tandem Servers
16.6 General Acyclic Networks with Probabilistic Routing
16.7 Readings
16.8 Exercises
Chapter 17 Networks of Queues and Jackson Product Form
17.1 Jackson Network Definition
17.2 The Arrival Process into Each Server
17.3 Solving the Jackson Network
17.4 The Local Balance Approach
17.5 Readings
17.6 Exercises
Chapter 18 Classed Network of Queues
18.1 Overview
18.2 Motivation for Classed Networks
18.3 Notation and Modeling for Classed Jackson Networks
18.4 A Single-Server Classed Network
18.5 Product Form Theorems
18.6 Examples Using Classed Networks
18.7 Readings
18.8 Exercises
Chapter 19 Closed Networks of Queues
19.1 Motivation
19.2 Product Form Solution
19.3 Mean Value Analysis (MVA)
19.4 Readings
19.5 Exercises
Part VI Real-World Workloads: High Variability and Heavy Tails
Chapter 20 Tales of Tails: A Case Study of Real-World Workloads
20.1 Grad School Tales Process Migration
20.2 UNIX Process Lifetime Measurements
20.3 Properties of the Pareto Distribution
20.4 The Bounded Pareto Distribution
20.5 Heavy Tails
20.6 The Benefits of Active Process Migration
20.7 Pareto Distributions Are Everywhere
20.8 Exercises
Chapter 21 Phase-Type Distributions and Matrix-Analytic Methods
21.1 Representing General Distributions by Exponentials
21.2 Markov Chain Modeling of PH Workloads
21.3 The Matrix-Analytic Method
21.4 Analysis of Time-Varying Load
21.5 More Complex Chains
21.6 Readings and Further Remarks
21.7 Exercises
Chapter 22 Networks with Time-Sharing (PS) Servers (BCMP)
22.1 Review of Product Form Networks
22.2 BCMP Result
22.3 M/M/1/PS
22.4 M/Cox/1/PS
22.5 Tandem Network of M/G/1/PS Servers
22.6 Network of PS Servers with Probabilistic Routing
22.7 Readings
22.8 Exercises
Chapter 23 The M/G/1 Queue and the Inspection Paradox
23.1 The Inspection Paradox
23.2 The M/G/1 Queue and Its Analysis
23.3 Renewal-Reward Theory
23.4 Applying Renewal-Reward to Get Expected Excess
23.5 Back to the Inspection Paradox
23.6 Back to the M/G/1 Queue
23.7 Exercises
Chapter 24 Task Assignment Policies for Server Farms
24.1 Task Assignment for FCFS Server Farms
24.2 Task Assignment for PS Server Farms
24.3 Optimal Server Farm Design
24.4 Readings and Further Follow-up
24.5 Exercises
Chapter 25 Transform Analysis
25.1 Definitions of Transforms and Some Examples
25.2 Getting Moments from Transforms: Peeling the Onion
25.3 Linearity of Transforms
25.4 Conditioning
25.5 Distribution of Response Time in an M/M/1
25.6 Combining Laplace and z-Transforms
25.7 More Results on Transforms
25.8 Readings
25.9 Exercises
Chapter 26 M/G/1 Transform Analysis
26.1 The z-Transform of the Number in System
26.2 The Laplace Transform of Time in System
26.3 Readings
26.4 Exercises
Chapter 27 Power Optimization Application
27.1 The Power Optimization Problem
27.2 Busy Period Analysis of M/G/1
27.3 M/G/1 with Setup Cost
27.4 Comparing ON/IDLE versus ON/OFF
27.5 Readings
27.6 Exercises
Part VII Smart Schedulingin the M/G/1
Chapter 28 Performance Metrics
28.1 Traditional Metrics
28.2 Commonly Used Metrics for Single Queues
28.3 Today's Trendy Metrics
28.4 Starvation/Fairness Metrics
28.5 Deriving Performance Metrics
28.6 Readings
Chapter 29 Scheduling: Non-Preemptive, Non-Size-Based Policies
29.1 FCFS, LCFS, and RANDOM
29.2 Readings
29.3 Exercises
Chapter 30 Preemptive, Non-Size-Based Policies
30.1 Processor-Sharing (PS)
30.2 Preemptive-LCFS
30.3 FB Scheduling
30.4 Readings
30.5 Exercises
Chapter 31 Scheduling: Non-Preemptive, Size-Based Policies
31.1 Priority Queueing
31.2 Non-Preemptive Priority
31.3 Shortest-Job-First (SJF)
31.4 The Problem with Non-Preemptive Policies
31.5 Exercise
Chapter 32 Scheduling: Preemptive, Size-Based Policies
32.1 Motivation
32.2 Preemptive Priority Queueing
32.3 Preemptive-Shortest-Job-First (PSJF)
32.4 Transform Analysis of PSJF
32.5 Exercises
Chapter 33 Scheduling: SRPT and Fairness
33.1 Shortest-Remaining-Processing-Time (SRPT)
33.2 Precise Derivation of SRPT Waiting Time
33.3 Comparisons with Other Policies
33.4 Fairness of SRPT
33.5 Readings
Bibliography
Index
more information - www.cambridge.org/9781107027503
Performance Modeling and Design of Computer Systems
Computer systems design is full of conundrums:
r Given a choice between a single machine with speed s, or n machines each with
r
speed s/n, which should we choose?
If both the arrival rate and service rate double, will the mean response time stay the
same?
r Should systems really aim to balance load, or is this a convenient myth?
r
If a scheduling policy favors one set of jobs, does it necessarily hurt some other jobs,
or are these “conservation laws” being misinterpreted?
r Do greedy, shortest-delay, routing strategies make sense in a server farm, or is what
is good for the individual disastrous for the system as a whole?
r How do high job size variability and heavy-tailed workloads affect the choice of a
scheduling policy?
r How should one trade off energy and delay in designing a computer system?
r
If 12 servers are needed to meet delay guarantees when the arrival rate is 9 jobs/sec,
will we need 12,000 servers when the arrival rate is 9,000 jobs/sec?
Tackling the questions that systems designers care about, this book brings queueing theory
decisively back to computer science. The book is written with computer scientists and
engineers in mind and is full of examples from computer systems, as well as manufacturing
and operations research. Fun and readable, the book is highly approachable, even for
undergraduates, while still being thoroughly rigorous and also covering a much wider span
of topics than many queueing books.
Readers benefit from a lively mix of motivation and intuition, with illustrations, examples,
and more than 300 exercises – all while acquiring the skills needed to model, analyze,
and design large-scale systems with good performance and low cost. The exercises are an
important feature, teaching research-level counterintuitive lessons in the design of computer
systems. The goal is to train readers not only to customize existing analyses but also to
invent their own.
Mor Harchol-Balter is an Associate Professor in the Computer Science Department at
Carnegie Mellon University. She is a leader in the ACM Sigmetrics Conference on Measure-
ment and Modeling of Computer Systems, having served as technical program committee
chair in 2007 and conference chair in 2013.
Performance Modeling and
Design of Computer Systems
Queueing Theory in Action
Mor Harchol-Balter
Carnegie Mellon University, Pennsylvania
cambridge university press
Cambridge, New York, Melbourne, Madrid, Cape Town,
Singapore, S˜ao Paulo, Delhi, Mexico City
Cambridge University Press
32 Avenue of the Americas, New York, NY 10013-2473, USA
www.cambridge.org
Information on this title: www.cambridge.org/9781107027503
C Mor Harchol-Balter 2013
This publication is in copyright. Subject to statutory exception
and to the provisions of relevant collective licensing agreements,
no reproduction of any part may take place without the written
permission of Cambridge University Press.
First published 2013
Printed in the United States of America
A catalog record for this publication is available from the British Library.
Library of Congress Cataloging in Publication Data
Harchol-Balter, Mor, 1966–
Performance modeling and design of computer systems : queueing theory in
action / Mor Harchol-Balter.
pages cm
Includes bibliographical references and index.
ISBN 978-1-107-02750-3
1. Transaction systems (Computer systems) – Mathematical models. 2. Computer
systems – Design and construction – Mathematics. 3. Queueing theory.
4. Queueing networks (Data transmission)
QA76.545.H37 2013
519.8
2012019844
2–dc23
I. Title.
ISBN 978-1-107-02750-3 Hardback
Cambridge University Press has no responsibility for the persistence or accuracy of
URLs for external or third-party Internet websites referred to in this publication and
does not guarantee that any content on such websites is, or will remain, accurate or
appropriate.
To my loving husband Andrew, my awesome son Danny,
and my parents, Irit and Micha
I have always been interested in finding better designs for computer systems, designs
that improve performance without the purchase of additional resources. When I look
back at the problems that I have solved and I look ahead to the problems I hope to
solve, I realize that the problem formulations keep getting simpler and simpler, and my
footing less secure. Every wisdom that I once believed, I have now come to question:
If a scheduling policy helps one set of jobs, does it necessarily hurt some other jobs,
or are these “conservation laws” being misinterpreted? Do greedy routing strategies
make sense in server farms, or is what is good for the individual actually disastrous for
the system as a whole? When comparing a single fast machine with n slow machines,
each of 1/nth the speed, the single fast machine is typically much more expensive – but
does that mean that it is necessarily better? Should distributed systems really aim to
balance load, or is this a convenient myth? Cycle stealing, where machines can help
each other when they are idle, sounds like a great idea, but can we quantify the actual
benefit? How much is the performance of scheduling policies affected by variability
in the arrival rate and service rate and by fluctuations in the load, and what can we do
to combat variability? Inherent in these questions is the impact of real user behaviors
and real-world workloads with heavy-tailed, highly variable service demands, as
well as correlated arrival processes. Also intertwined in my work are the tensions
between theoretical analysis and the realities of implementation, each motivating the
other. In my search to discover new research techniques that allow me to answer
these and other questions, I find that I am converging toward the fundamental core
that defines all these problems, and that makes the counterintuitive more believable.
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
