Avg turnaround: FCFS, RR, SJF, SRT, HRRN

Turnaround time = completion time − arrival time. Assumptions: in round robin, a process that arrives at the same instant a quantum expires joins the queue before the preempted process; SJF is non-preemptive; SRT (shortest remaining time) is its preemptive version.

(a) FCFS

Order of arrival: A, B, C, D, E

| A | B | C | D | E |
0   3   9   13  18  20

Average turnaround = 43/5 = 8.6 ms

(b) Round robin, q = 4

Queue evolution: A runs 0-3 (finishes); B 3-7 (needs 2 more); C 7-11 (finishes); D 11-15 (1 more); B 15-17 (finishes); E 17-19 (finishes); D 19-20 (finishes).

Gantt chart

| A | B | C | D | B | E | D |
0   3   7   11  15  17  19  20

Average turnaround = 50/5 = 10 ms

(c) SJF (non-preemptive)

At t = 3 only B is ready. At t = 9 the ready jobs are C(4), D(5) and E(2): E is shortest, then C, then D.

Gantt chart

| A | B | E | C | D |
0   3   9   11  15  20

Average turnaround = 38/5 = 7.6 ms

(d) SRT (preemptive SJF)

B (6) starts at 3. At t = 4, C (4) arrives with less remaining time than B (5), so C preempts B. At t = 8, C finishes just as E (2) arrives; E is now the shortest, so E runs. After that, B and D both need 5; B arrived earlier, so B runs, then D.

Gantt chart

| A | B | C | E | B | D |
0   3   4   8   10  15  20

Average turnaround = 36/5 = 7.2 ms

(e) HRRN (non-preemptive)

Response ratio = (waiting + service)/service. At t = 9: C = (5+4)/4 = 2.25, D = (3+5)/5 = 1.6, E = (1+2)/2 = 1.5, so C runs. At t = 13: D = (7+5)/5 = 2.4, E = (5+2)/2 = 3.5, so E runs, then D.

Gantt chart

| A | B | C | E | D |
0   3   9   13  15  20

Average turnaround = 40/5 = 8 ms

Summary

Answer: FCFS 8.6, RR 10.0, SJF 7.6, SRT 7.2, HRRN 8.0 ms. SRT gives the lowest average turnaround time.