DOC PREVIEW
U of I CS 241 - Queueing Systems

This preview shows page 1-2-3-4 out of 12 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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

U of I CS 241 - Queueing Systems

Documents in this Course
Process

Process

28 pages

Files

Files

37 pages

File I/O

File I/O

52 pages

C Basics

C Basics

69 pages

Memory

Memory

23 pages

Threads

Threads

14 pages

Lecture

Lecture

55 pages

C Basics

C Basics

24 pages

Signals

Signals

27 pages

Memory

Memory

45 pages

Threads

Threads

47 pages

Threads

Threads

28 pages

LECTURE

LECTURE

45 pages

Threads

Threads

30 pages

Threads

Threads

55 pages

Files

Files

37 pages

SIGNALS

SIGNALS

22 pages

Files

Files

37 pages

Threads

Threads

14 pages

Threads

Threads

13 pages

Load more
Download Queueing Systems
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Queueing Systems and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Queueing Systems 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?