1Copyright ©: Nahrstedt, Angrave, Abdelzaher 1Queueing Systems Copyright ©: Nahrstedt, Angrave, Abdelzaher2Content of This Lecture Goals: Introduction to Principles for Reasoning about Process Management/Scheduling Things covered in this lecture Introduction to Queuing Theory2Copyright ©: Nahrstedt, Angrave, Abdelzaher3Process States Finite State DiagramCopyright ©: Nahrstedt, Angrave, Abdelzaher4Queueing Model Random Arrivals and the Poisson Distribution Elements of model3Copyright ©: Nahrstedt, Angrave, Abdelzaher5Discussion If a bus arrives at a bus stop every 15 minutes, how long do you have to wait at the bus stop assuming you start to wait at a random time?Copyright ©: Nahrstedt, Angrave, Abdelzaher6Discussion What assumption have you made about the bus?4Copyright ©: Nahrstedt, Angrave, Abdelzaher7Queuing TheoryARRIVAL RATE ARRIVAL RATE λλλλλλλλSERVICE RATE SERVICE RATE µµµµµµµµInput QueueInput QueueServerServerCopyright ©: Nahrstedt, Angrave, Abdelzaher8Queueing Theory (Point of Interest) Steady state Poisson arrival with λ constant arrival rate (customers per unit time) each arrival is independent. P( τ≤t ) = 1- e–λt01tAv λ0.55Copyright ©: Nahrstedt, Angrave, Abdelzaher9Analysis of Queueing Behavior Probability ncustomers arrive in time interval tis: e–λt (λt)n/ n! Assume random service times (also Poisson): µ constant service rate (customers per unit time) Copyright ©: Nahrstedt, Angrave, Abdelzaher10Useful Facts From Queuing Theory Wq= mean time a customer spends in the queue λ = arrival rate Lq= λ Wqnumber of customers in queue W = mean time a customer spends in the system L = λ W ( Little's theorem) number of customers in the systemIn words – average length of queue is arrival rate times average waiting time6Copyright ©: Nahrstedt, Angrave, Abdelzaher11Analysis of Single Server Queueµλρ=λµ−=1Wλµρ−=qWρρ−=12qL•Server Utilization:•Time in System:•Time in Queue:•Number in Queue (Little):Copyright ©: Nahrstedt, Angrave, Abdelzaher12Hamburger Problem 7 Hamburgers arrive on average every time unit 8 Hamburgers are processed by Joe on average every unit 1) Av. time hamburger waiting to be eaten? (Do they get cold?) Ans = ???? 2) Av number of hamburgers waiting in queue to be eaten? Ans = ????Queue787Copyright ©: Nahrstedt, Angrave, Abdelzaher13Hamburger Problem 7 Hamburgers arrive on average every time unit 8 Hamburgers are processed by Joe on average every unit1) How long is a hamburger waiting to be eaten? (Do they get cold?) Ans = 7/8 time units 2) How many hamburgers are waiting in queue to be serviced? Ans = 49/8 Queue78Copyright ©: Nahrstedt, Angrave, Abdelzaher14Example: How busy is the server?λ=2µ=366%8Copyright ©: Nahrstedt, Angrave, Abdelzaher15How long is an eater in the system?λ=2µ=3λµ−=1W= 1/(3-2)= 1Copyright ©: Nahrstedt, Angrave, Abdelzaher16How long is someone in the queue?λ=2µ=366.2366.=−=−=λµρqW9Copyright ©: Nahrstedt, Angrave, Abdelzaher17How many people in queue?λ=2µ=333.166.1266.12=−=−=ρρqLCopyright ©: Nahrstedt, Angrave, Abdelzaher18Interesting Fact If Arrival Rate = Service Rate, the queue length become infinitely large the longer you run the model.10Copyright ©: Nahrstedt, Angrave, Abdelzaher19Until Now We Looked at Single Server, Single Queue TheoryARRIVAL RATE ARRIVAL RATE λλλλλλλλSERVICE RATE SERVICE RATE µµµµµµµµInput QueueInput QueueServerServerCopyright ©: Nahrstedt, Angrave, Abdelzaher20Poisson Arrivals SumARRIVAL RATE ARRIVAL RATE λλλλλλλλ11SERVICE RATE SERVICE RATE µµµµµµµµInput QueueInput QueueServerServerARRIVAL RATE ARRIVAL RATE λλλλλλλλ22λλλλλλλλ==λλλλλλλλ1+1+λλλλλλλλ2211Copyright ©: Nahrstedt, Angrave, Abdelzaher21Example– Arrival 1 jobs/sec from Start– Arrival 2 jobs/sec from Event queue– Service 4 jobs/sec Utilization? Time in system? Time in queue ? Length of queue?Copyright ©: Nahrstedt, Angrave, Abdelzaher22As long as it’s a Poisson Distribution...ARRIVAL RATE ARRIVAL RATE λλλλλλλλSERVICE RATE SERVICE RATE µµµµµµµµ11Input QueueInput QueueServerServerServerServerSERVICE RATE SERVICE RATE µµµµµµµµ22CombinedCombinedµµµµµµµµ==µµµµµµµµ1+1+µµµµµµµµ2212Copyright ©: Nahrstedt, Angrave, Abdelzaher23Question: McDonalds ProblemµµµµµµµµµµµµλλλλλλλλλλλλA) Separate Queues per ServerA) Separate Queues per ServerB) Same Queue for ServersB) Same Queue for ServersIf WIf WAis waiting time for system A, and Wis waiting time for system A, and WBis waiting time for is waiting time for system B, what is Wsystem B, what is WA/W/WBB? Integer answer; W? Integer answer; WAA> W> WB B
View Full Document