Back To Scheduling

Round Robin

e.g.
          Quantum = Q =  4
 Process
CPU Burst
Remainder CPU time
Remainder CPU time
P1
20
16
12
P2
5
1
0
P3
6
2
0

 
P1 P2 P3 P1 P2 P3 P1
0                     4
8
12
16
17
19
31

Average waiting time:         Waiting Time = (Final Start Time - Previous Time in CPU - Arrival Time)

[(19 - 8 - 0) + (16 - 4) + (17 - 4)]/3 = (11 + 12 + 13)/3=12
Every one gets about the same amount of waiting time.
If there are n number of process, each process gets 1/n of CPU in chunks of Q , how long has to wait until next quantum?
(n - 1) Q
Small Q means more context switches.
Overhead is a function of Q (plus some other stuff)
Set up your quantum close to average of CPU burst time.  (It reduces the number of swapping.)
 

e.g.
 
Process Burst Arrival Time
P1 24 0
P2 3 5
P3 3 10

Q = 4           Ready List  =  P1 P2 P3    (You can use link list or queue to implement the ready list.)
 
P1 P1 P2 P1 P3 P1
0                                  4
8
11
15
18
30
 5
P2 in 
                     10
                   P3 in
                                            
                                            Only on the I/O time or the end of Q, it can be preemptive.

Waiting Queue:
 
Time Process in Waiting Queue
0 P1
5
P1   P2
8 P2   P1
10 P2     P1    P3