13. From M/M/1 to GPS

Question 1

Generalized Processor Sharing (GPS)

Answer 1

• Distributes the capacity of a given resource among all or a portion of the jobs
• Each job class is assigned some fractional weight of the server capacity

Question 2

Round-Robin Algorithm

Answer 2

• Assume slice of length s and each job has own class
• Process a job for length s, then move on to the next job in the queue
• Only repeat a job once each job has been processed in the round
• We reach perfect GPS as s –> 0

Question 3

Round-Robin as Network of Queues

Answer 3

• Let p be probability that job not done in slice
• Assume slice ~ exp(s)
• Aggregated flow lambda prime = lambda / (1-p)

Question 4

Time to Complete RR Job

Answer 4

• Let m = # of times going back into queue after slice
• f(m) ~ geometric(1-p)
• E[m] = p / (1-p)
• t = (m+1) * s

Question 5

RR Service Time

Answer 5

• T_s = s / (1-p)
• T_s = 1 / mu

Question 6

RR Response Time

Answer 6

• q = rho / (1-rho)
• T_q = q / lamba

Question 7

Length-Unaware Scheduling Policy

Answer 7

• Scheduling policy does not consider the length of the job (FIFO, RR)

Question 8

Work-Conserving

Answer 8

• Server is working 100% when there is a request in the system, 0% otherwise

Question 9

Impact on System Averages

Answer 9

• A work-conserving, length-unaware scheduling policy does not affect system averages

Question 10

RR Utilization

Answer 10

• rho = aggregated lambda * s
• rho = lambda * T_s

Question 11

Relationship between M/M/1 and GPS

Answer 11

M/M/1 is a good way to approximate any work-conserving, length-unaware scheduling policy on average