Queueing Theory and Simulation in Computing
Explore the fundamentals of queueing theory and simulation in computing, covering topics such as event-driven simulation, stochastic setting, queueing metrics, and running simulations. Learn about job arrival rates, response times, server utilization, and more to optimize system performance.
Uploaded on | 0 Views
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Chapter 14 Event-Driven Simulation "Introduction to Probability for Computing", Harchol-Balter '24 1
Queueing Theory Terminology: Simplest Model the queue FCFS the server The server is the CPU A job is a red rectangle The size of a job is the height of the rectangle. ???? = ? = # seconds of CPU needed by the job Only one job is served (run) at a time. Jobs are served in FCFS order. Jobs arrive over time. The interarrival time is the time between subsequent arrivals. The average arrival rate (?) is the average number of arrivals per sec: ??= number of arrivals by time ? ?= lim ? ? ?? "Introduction to Probability for Computing", Harchol-Balter '24 2
Stochastic Setting vs. Trace-driven Simulation Stochastic Setting Trace-driven Simulation ? r.v.for size of job. Typically assume i.i.d. instances of ?. ? r.v.for interarrival time. Typically assume i.i.d. instances of ?. ? and ? instances are given by a trace. At time 1.5, job arrives of size 7. At time 1.7, job arrives of size 3. At time 13, job arrives of size 1.2. Given a Poisson Process w/ rate ? , how are ? and ?[?] related? 1 ? = ?[?] "Introduction to Probability for Computing", Harchol-Balter '24 3
Queueing Metrics ? Response time of job, ? Number of jobs in system, ? Mean Response time, ? ? Mean number of jobs, ? ? T1+ T2+ + ?? ? ? ? = lim ? "Introduction to Probability for Computing", Harchol-Balter '24 4
Queueing Metrics ? ? = total time server is busy by time ? Server utilization (a.k.a., load), ? Express ? in terms of ? ? ? is the long-run fraction of time that the server is busy ?(?) ? ? = lim ? "Introduction to Probability for Computing", Harchol-Balter '24 5
Queueing Metrics Q: Suppose ? = 3 jobs/sec and ? ? =1 4 sec. What is ?? Will there be queueing? 1/4 1/4 1/4 1/4 1/4 1/4 1/4 1/4 1/4 1/4 1/4 1/4 0? 1? 2? 3? 4? Not necessarily 3 arrivals/s A: Seems like ? = ?? ? =3 4. We will prove this in Chapter 27. If ?, ? are Deterministic no queueing If ?, ? have high variability lots of queueing "Introduction to Probability for Computing", Harchol-Balter '24 6
Running a Simulation Single Queue GOAL: Simulate this queue, where interarrival times ? and service times ? Determine ? ? across 106jobs Do you start by generating 106instances of ? and ? ? No! Generate as needed "Introduction to Probability for Computing", Harchol-Balter '24 7
Running a Simulation Single Queue GOAL: Simulate this queue, where interarrival times ? and service times ? Determine ? ? across 106jobs If a job takes 5?, do we wait 5? on computer clock? No! Simulate the clock! "Introduction to Probability for Computing", Harchol-Balter '24 8
Event-driven Simulation State = =Number of jobs, ?, currently in system What are these events? Arrivals & Completions! Track only events that change the state! Generate instances of ? and ? as needed. "Introduction to Probability for Computing", Harchol-Balter '24 9
Event-driven Simulation Example Suppose instances of ? are: 5.3, 2, 9.5, Suppose instances of ? are: 10, 1, 7, Iteration 2 Iteration 1 CLOCK = 5.3 CLOCK = 0 State = ? = 1 State = ? = 0 Time-to-next-Compl = ???????? ? = 10 Time-to-next-Compl = Time-to-next-Arrival = ???????? ? = 2 Time-to-next-Arrival = ???????? ? = 5.3 Next-Event = min T C,T A = T A = 2 Next-Event = min T C,T A = T A = 5.3 Event = Arrival @7.3 Event = Arrival @5.3 "Introduction to Probability for Computing", Harchol-Balter '24 10
Event-driven Simulation Example Suppose instances of ? are: 5.3, 2, 9.5, Suppose instances of ? are: 10, 1, 7, Iteration 3 Iteration 2 CLOCK = 7.3 CLOCK = 5.3 State = ? = 2 State = ? = 1 Time-to-next-Compl = 10 2 = 8 Time-to-next-Compl = ???????? ? = 10 Time-to-next-Arrival = ???????? ? = 9.5 Time-to-next-Arrival = ???????? ? = 2 Next-Event = min T C,T A = T C = 8 Next-Event = min T C,T A = T A = 2 Event = Completion @15.3 Event = Arrival @7.3 "Introduction to Probability for Computing", Harchol-Balter '24 11
Event-driven Simulation Example Suppose instances of ? are: 5.3, 2, 9.5, Suppose instances of ? are: 10, 1, 7, Iteration 4 Iteration 3 CLOCK = 15.3 CLOCK = 7.3 State = ? = 1 State = ? = 2 Time-to-next-Compl = ????????(?) = 1 Time-to-next-Compl = 10 2 = 8 Time-to-next-Arrival = 9.5 8 = 1.5 Time-to-next-Arrival = ???????? ? = 9.5 Next-Event = min T C,T A = T C = 1 Next-Event = min T C,T A = T C = 8 Event = Completion @16.3 Event = Completion @15.3 "Introduction to Probability for Computing", Harchol-Balter '24 12
Event-driven Simulation Example Suppose instances of ? are: 5.3, 2, 9.5, Suppose instances of ? are: 10, 1, 7, Iteration 5 Iteration 4 CLOCK = 16.3 CLOCK = 15.3 State = ? = 0 State = ? = 1 Time-to-next-Compl = Time-to-next-Compl = ????????(?) = 1 Time-to-next-Arrival = 1.5 1 = 0.5 Time-to-next-Arrival = 9.5 8 = 1.5 Next-Event = min T C,T A = T A = 0.5 Next-Event = min T C,T A = T C = 1 Event = Arrival @16.8 Event = Completion @16.3 "Introduction to Probability for Computing", Harchol-Balter '24 13
Event-driven Simulation Quiz Q: When exactly do you generate a new instance of ?? 1. Immediately after a job arrives 2. When drop to 0 jobs Q: In an event-driven simulation, what are the 4 variables you track? Q: When exactly do you generate a new instance of ?? 1. Global Clock 2. State = Number jobs in system 3. Time-to-next-Arrival 4. Time-to-next-Completion 1. Immediately after a job completes, assuming job leaves behind 1 job. 2. When system moves from state 0 to state 1. "Introduction to Probability for Computing", Harchol-Balter '24 14
Getting ?[?] T1+ T2+ + ?? ? ? ? = lim ? Q: How do we get Tifor our FCFS queue? A: Log arrival times as they happen on this list: 5.3 7.3 16.8 When completions happen: o Subtract earliest arrival on list from current clock time. o Delete earliest arrival from list Completion at 15.3 ?1= 15.3 5.3 = 10 Completion at 16.3 ?2= 16.3 7.3 = 9 Example: "Introduction to Probability for Computing", Harchol-Balter '24 15
Getting ?[?] T1+ T2+ + ?? ? ? ? = lim ? ?? Q: To get ? ? do I need to store all 106 ?? A: No! Let ? ?(?)= average of first ????=1 ? ?=1 ?? 1 ?(?+1)= ? ??+ ??+1 ? + 1 "Introduction to Probability for Computing", Harchol-Balter '24 16
Getting ?[?] Let ? ? = Number of jobs in the system at time ? ?? ? ?? 0 ?[?] = lim ? ? ? = 1 ? = 1 ? = 2 ? = 0 Q: How to get ? ? ? Idea 1: (Time Average) 15.3 16.3 5.3 7.3 0 Weight ? by length of interval? ?[?] =5.3 0 + 2 1 + 8 2 + 1(1) 16.3 "Introduction to Probability for Computing", Harchol-Balter '24 17
Getting ?[?] Let ? ? = Number of jobs in the system at time ? ?? ? ?? 0 ?[?] = lim ? ? Q: How to get ? ? ? Idea 2: (Ensemble Average) Whenever arrival happens, record how many jobs arrival sees in the system Take average over all these observations "Introduction to Probability for Computing", Harchol-Balter '24 18
Getting ?[?] Let ? ? = Number of jobs in the system at time ? ?? ? ?? 0 ?[?] = lim ? ? Every arrival walks into empty system Q: Is ? ????????= ? ????????????? Suppose ? ??????? 1,2 and ? = 1. Are your answers the same? ? = 1 ? = 1 ? = 1 ? = 1 ? ????????=2 3 0 ? ????????????= 0 Correct ?[?] "Introduction to Probability for Computing", Harchol-Balter '24 19
Getting ?[?] Why was ? ???????? ? ???????????? ? Arrival times were bad times to measure # jobs Is it ever true that ? ????????= ? ???????????? ? Need arrival times to be random. Poisson Process! "Introduction to Probability for Computing", Harchol-Balter '24 20
PASTA PASTA = Poisson Arrivals See Time Averages ? ????????= ? ???????????? Q: But what if arrival process is not Poisson. Can we still average over what arrivals see? A: No, but you can simulate a Poisson Process in the background, and record number of jobs at times of those events! "Introduction to Probability for Computing", Harchol-Balter '24 21
Running simulations: one long run? # jobs time restart restart restart Q: When running simulations, is it better to consider time-average over one long run, or many short runs? A: Turns out these are the same, provided simulation empties (restarts) infinitely often. See Chpt 25 of your book! "Introduction to Probability for Computing", Harchol-Balter '24 22
Running simulations: convergence # jobs time restart restart restart Q: How long should we run our simulation? How many arrivals? A: Run long enough to meet both these conditions: 1. Performance metric is no longer biased by initial state 2. Performance metric is no longer changing much (has converged) "Introduction to Probability for Computing", Harchol-Balter '24 23
