1CS 520, Operating Systems Concepts Lecture 3 Simulation of a System of Asynchronous Processes (Queuing Systems) Igor Faynberg Slide 2 Agenda 1. Two paradigms of programming 2. Queuing model 3. Simulation mechanisms 1. Random number generation 2. Event generation 3. Event processing 4. Statistics gathering 4. Homework: The First Programming Assignment Igor Faynberg Slide 3 1) Two Paradigms of Programming (after A. Tannenbaum) I: Algorithmic code II: Event-driven code main() { event_t event; while (get_event(event)) { switch (event.type) { case 1: ...; case 2: ...; case 3: ...; } } } Even better! #define Total_Event_Number … ; /* some constant */ void Event_0(); void Event_1(); … *p [Total_Event_Number] Event_Handler (); Event_Handler([0] = Event_0; Event_Handler([1] = Event_1; … main() { event_t event; while TRUE Event_Handler[get(event)] } Igor Faynberg 4 On to 2) Queing Models! 5 Igor Faynberg Slide 6 The Poisson Model The Server (takes time to process a customer, so the queue is formed) The Customer Queue Independent Arrivals Departure Mean rate:  customers/sec Mean rate:  customers/sec Steady State:  <  Igor Faynberg Slide 7 What does mean mean? Let the probability density of a random variable  be p(x) defined on an interval [a, b] Then the mean E[] is defined as [] = න () For a discrete variable  with p(k) = P(=k), [] = ෍ =0 ∞ () Igor Faynberg Slide 8 The Poisson Distribution ! )( },{ k t ektP k t −= The probability of exactly k arrivals within the interval [0, t] is independent from the previous arrival history: Consider something simple Igor Faynberg Slide 9 There are ml balls in a box: l red balls and (m-1)l blue balls. What is a probability p of blind- picking a red ball? p = l/ml = 1/m Now we have n identical boxes and pick one ball from each of them? Igor Faynberg Slide 10 … There are n = ml balls in each box: l red balls and (m-1)l blue balls. What is a probability P of blind- picking exactly k red balls? = [ − 1 ]− ()− = = (1 − )− This is the Binomial Distribution, which applies to trials of independent events The Poisson Distribution Igor Faynberg Slide 11 0 t … Divide the interval 0, t into n sufficiently small parts so the probability of one arrival in each part is p = . p{t, k, n} = ( )(1 − )− = !() (1− ) ! − ! (1 − )− P t, k = lim →∞ , , = ()− ! . Igor Faynberg Slide 12 Inter-arrival Time  For the Poisson distribution, the inter-arrival probability density is distributed exponentially, too: p[inter-arrival time ≤ t] = = 1 – p[inter-arrival time > t]= 1 – P[t,0] = = 1- e- t Igor Faynberg Slide 13 3) Simulations  Analytical approach does not work very well for all classes of queuing disciplines  The low price of computing permits us to use computer simulations of very complex queuing systems (it is equivalent to integrating complex difference-differential equations) on a computer  Simulations are widely used in modeling (and thus predicting) computer, communications, financial, and biological systems  From now on, we will use simulations systematically in our homework Igor Faynberg Slide 14 3.1 First Comes First: Random Number Generation  Well, one could generate them using Geiger counter, for example, or—better yet—using the data from past experiences, or—the best—using special devices (necessary in cryptography)  But very often—and this is what we will do– what is used is pseudo-random number generators  In your case, you should use Java.Util.Random (but you must understand how it works and test it!)  If you are interested in the subject, the best place to start (and finish) is D. Knuth, “The Art of Computer Programming, “ Volume II public double getNext() { return Math.log(1-rand.nextDouble())/(-lambda); } Igor Faynberg Slide 15 Pseudo-Random Number Generation (The Linear Congruential Method)  We start with four natural “magic numbers”: ◼ m, the modulus ◼ a, the multiplier (a < m, a is co-prime with m)) ◼ c, the increment (c < m) ◼ X0, the starting value (or seed) (X0 < m) The desired sequence (which should have a long period) is Xn+1 = (aXn + c) mod m, n > 0 Igor Faynberg Slide 16 Pseudo-Random Number Generation (The Linear Congruential Method)  Again, you can find (and you should, if you have time) much better magic numbers, but just for the purpose of the exercise here is a choice of magic numbers (and they don’t require the use of long integers): a = 25173, c = 13849, m = 65536. Igor Faynberg Slide 17 Uniformly Distributed Pseudo-Random Numbers We can obtain a uniformly-distributed sequence Yn in the interval [0, 1) by scaling the sequence Xn+1 = (aXn + c) mod m: Yn+1 = Xn+1 / m How to Get the Inter-Arrival Time? ξ(t)= p[inter-arrival time ≤ t] = 1- e- t. and so t = -(1/ )ln(1- ξ). (The values of ξ themselves are distributed uniformly in [0, 1) because the arrivals are independent) 18 Igor Faynberg Slide 19 Exponentially Distributed Pseudo- Random Numbers That allows us to obtain an exponentially-distributed interarrival sequence Zn, with the mean arrival rate  (or mean inter-arival rate 1/ ): Xn+1 = (aXn + c) mod m: =− 1  ln(1 − ) Igor Faynberg Slide 20 Hint: Using Java.Util public double getNext() { return Math.log(1-rand.nextDouble())/(-lambda); } public double getNextPersonTime() { return -Math.log(1-rand.nextDouble())/(lambda); } Again, understand well how this works and experiment producing the distribution an ensuring that its mean is indeed 1/! Igor Faynberg Slide 21 The Simulation Algorithm  We create a data structure (a heap, or a doubly-linked ring), which delivers the next event); we initialize this structure by inserting all events scheduled for time 0.  We generate events based on the system we are simulating; as the result, a generated event enters the structure in an appropriate place  We execute the program by repeating the following steps until simulated current time exceeds the defined time limit 1. Take the next event from the event structure and update the current simulation time 2. Process the event; (that will likely generate other events in turn) Igor Faynberg Slide 22 We Will Simulate a Bus Service Igor Faynberg Slide 23 Three Kinds of Events 1. person: A person arrives in the queue at a bus stop Action: After a random (exponentially-distributed inter- arrival) time, another person is scheduled to arrive in the queue 2. arrival: A bus arrives at a bus stop Action: If there is no one in the queue, the bus proceeds to the next stop, and the event of its arrival there is generated; otherwise, the event to be generated (at present time!) is the first person in the queue boarding the bus; 3. boarder: A person boards the bus Action: The length of the queue diminishes by 1; If the queue is now empty, the bus proceeds to the next stop, otherwise the next passenger boards the bus Igor Faynberg Slide 24 Assumptions  It takes everyone the same time to enter the bus  As many people (on average) exit the bus as enter it, and the time to exit the bus is negligible. Consequence: we do not consider the exit event in our model  The stops are equally spaced in a circle  The buses may not pass one another Igor Faynberg Slide 25 The Event Record This is an entry in the event structure. It contains 1. The time of the event 2. The type of the event 3. The rest of the information, which is event- dependent: the name (number) of the stop, the number of the bus, etc. Igor Faynberg Slide 26 The Main Program Initialization(); do { Get the next event; clock = event time; switch event_kind person: { update the queue[stop_number]; generate_event (person, stop_number); } arrival: {...} /* board the bus boarder: {...} } while clock < = stop_time Igor Faynberg Slide 27 Initialization  Read the number of buses, the number of stops, the driving time between stops, the boarding time, the stop time, and the mean arrival rate from an initialization file. ◼ For the beginning, assume there are 15 bus stops, 5 buses, the (uniform) time to drive between two contiguous stops is 5 min., mean arrival rate at each stop is 2 persons/min, and boarding time is 3 seconds  Start with the buses distributed uniformly along the route (by generating appropriate arrival events) and generating one person event for each stop. Igor Faynberg Slide 28 Event Generation  When the bus arrival event occurs, if the queue is empty, generate the arrival at the next bus stop at clock + drive_time. If the queue is not empty, generate the boarder event (at clock)  When the boarder event occurs, if the queue is empty (i.e., the last person boarded), generate the arrival event at the next bus stop at clock + drive_time. If the queue is not empty, generate the boarder event (at clock + boarding_time)  Whent the person event occurs, generate the next person event at the same stop at clock + getNextPersonTime(). Igor Faynberg Slide 29 The Goal  The purpose of the simulation is to observe the behavior of the system, and answer the following questions: ◼ Do the distances between two consecutive buses keep uniform? If not, what should be done to ensure they are uniform? Modify the rules, if necessary, and run another simulation to prove that this works. ◼ What is the average size of a waiting queue at each stop (and what are its maximum and minimum)? ◼ Plot the positions of buses as a function of time (you will need to generate periodic snapshots of the system for that)