CO2017 — Surgery 1, 2015-16
Dr Gilbert Laycock (gtl1)
2016–02–01; R582
Questions
The following jobs arrive in the scheduler’s ready queue in the order given; the right hand column
gives the running time of each job.
Job Estimated runtime (ms) Arrival time (ms)
A 18 0
B 9 0
C 14 2
D 2 6
E 4 8
In what order would these jobs be scheduled under the following scheduling policies?
1. First Come First Served (FCFS)
2. Shortest Job First (SJF)
3. Shortest Remaining Time (SRT)
4. Round Robin (RR) with a time quantum of 5ms
For the purpose of this exercise, assume that the time taken for a context switch, addition to
ready queue, etc, is zero.
In each case, calculate the completion time and turnaround time, the runtime (time spent ex-
ecuting), the waiting time (time spent “idle” in the ready queue) and the ratio of waiting time
over runtime of each job.
Discuss the scheduling policies.
1
Model Answers to CO2017 Surgery 1
1. For FCFS policy, the jobs are executed in order, until completion:
Time Running(RT,waiting) Queue(RT,waiting) Complete(waiting)
0 A(18,0) B(9,0)
2 A(16,0) B(9,2),C(14,0)
6 A(12,0) B(9,6),C(14,4),D(2,0)
8 A(10,0) B(9,8),C(14,6),D(2,2),E(4,0)
18 B(9,18) C(14,16),D(2,12),E(4,10) A(0)
27 C(14,25) D(2,21),E(4,19) B(18)
41 D(2,35) E(4,33) C(25)
43 E(4,35) D(35)
47 E(35)
Job Runtime Arrive Start End Turnaround Waiting Ratio (wait/run)
A 18 0 0 18 18 0 0.0
B 9 0 18 27 27 18 2.0
C 14 2 27 41 39 25 1.79
D 2 6 41 43 37 35 17.5
E 4 8 43 47 39 35 8.75
Average 32 6.01
2
2. For Shortest Job First, the jobs are executed as follows:
Time Running(RT,waiting) Queue(RT,waiting) Complete(waiting)
0 B(9,0) A(18,0)
2 B(7,0) C(14,0),A(18,2)
6 B(3,0) D(2,0),C(14,4),A(18,6)
8 B(1,0) D(2,2),E(4,0),C(14,6),A(18,8)
9 D(2,3) E(4,1),C(14,7),A(18,9) B(0)
11 E(4,3) C(14,9),A(18,11) D(3)
15 C(14,13) A(18,15) E(3)
29 A(18,29) C(13)
47 A(29)
Job Runtime Arrive Start End Turnaround Waiting Ratio (wait/run)
B 9 0 0 9 9 0 0.0
D 2 6 9 11 5 3 1.5
E 4 8 11 15 7 3 0.75
C 14 2 15 29 27 13 0.93
A 18 0 29 47 47 29 1.61
Average 19 0.96
3
3. For Shortest Remaining Time, the jobs are executed as follows:
Time Running(RT,waiting) Queue(RT,waiting) Complete(waiting)
0 B(9,0) A(18,0)
2 B(7,0) C(14,0),A(18,2)
6 D(2,0) B(3,0),C(14,4),A(18,6) D preempts B
8 B(3,2) E(4,0),C(14,6),A(18,8) D(0) B resumes
11 E(4,3) C(14,9),A(18,11) B(2)
15 C(14,13) A(18,15) E(3)
29 A(18,29) C(13)
47 A(29)
Job Runtime Arrive Start End Turnaround Waiting Ratio (wait/runtime)
D 2 6 6 8 2 0 0
B 9 0 0 11 11 2 0.22
E 4 8 11 15 7 3 0.75
C 14 2 15 29 27 13 0.93
A 18 0 29 47 47 29 1.61
Average 18.8 0.70
4
4. For Round Robin, with a time quantum of 5ms, the jobs are executed as follows:
Time Running(RT,waiting) Queue(RT,waiting) Complete(waiting)
0 A(18,0) B(9,0)
2 A(16,0) B(9,2),C(14,0)
5 B(9,5) C(14,3),A(13,0) timeout
6 B(8,5) C(14,4),A(13,1),D(2,0)
8 B(6,5) C(14,6),A(13,3),D(2,2),E(4,0)
10 C(14,8) A(13,5),D(2,4),E(4,2),B(4,5) timeout
15 A(13,10) D(2,9),E(4,7),B(4,10),C(9,8) timeout
20 D(2,14) E(4,12),B(4,15),C(9,13),A(8,10) timeout
22 E(4,14) B(4,17),C(9,15),A(8,12) D(14) reset quantum
26 B(4,21) C(9,19),A(8,16) E(14) reset quantum
30 C(9,23) A(8,20) B(21) reset quantum
35 A(8,25) C(4,23) timeout
40 C(4,23) A(3,25) timeout
44 A(3,29) C(23) reset quantum
47 A(29)
The wait time/run time ratios are as follows:
Job Runtime Arrive Start End Turnaround Waiting Ratio (wait/runtime)
D 2 6 20 22 16 14 7.0
E 4 8 22 26 18 14 3.5
B 9 0 5 30 30 21 2.33
C 14 2 10 44 42 28 2.0
A 18 0 0 47 47 29 1.61
Average 30.6 3.29
General observations
The final completion time is the same (47ms) with each scheduling policy, because the processor
is always busy.
Note that
• Turnaround = End −Arrive.
• Waiting = Turnaround −Runtime.
Shortest Job First gives the best wait time/run time ratios. First Come First Served is bad for
jobs near the back of the queue, particularly short ones. Round Robin gives intermediate results,
although most processes get some processing earlier, which is better for interactive tasks.
5