Scheduling

Round Robin

Fair,

How efficient? Depends on quantum size.

Let's assume that task switching takes 2ms.

If we have a quantum of 8ms, we ensure very good response time. For example, imagine 20 users all logged in to a single CPU server; with every user making a request at the same time, each task takes up 10ms (8ms quantum + 2ms overhead), and the 20th user gets a response in 200 ms (10ms × 20), which is pretty good (5th second).

On the other hand, efficiency is

useful time ÷ total time
= 8ms ÷ 10ms
= 80%, i.e. 20% of the CPU time is wasted on overhead.

With a 200ms quantum, efficiency is 200ms / 202ms = ~99%

but, reponse time if 20 users make a request at once is 202 * 20 = 4040 ms or >4 seconds, which is not good.

Large quantum, more efficient vs. small quantum, better response-time. Throughput and turnaround depend on number of jobs in system---and I/O usage per task.

Complications: process may use less than its time slice (e.g. blocking on a semaphore or I/O operation). Idle task sould never get CPU except when no other task is running (it should not participate in the round robin).


last updated 29 April 1998