Five jobs A, B, C, D and E are waiting in Ready Queue. Their expected runtimes…
2016
Five jobs A, B, C, D and E are waiting in Ready Queue. Their expected runtimes are 9, 6, 3, 5 and x respectively. All jobs entered in Ready queue at time zero. They must run in _____ order to minimize average response time if 3 < x < 5.
- A.
B, A, D, E, C
- B.
C, E, D, B, A
- C.
E, D, C, B, A
- D.
C, B, A, E, D
Attempted by 367 students.
Show answer & explanation
Correct answer: B
Key insight: schedule jobs in order of increasing runtime (Shortest Job First) when all jobs arrive at the same time to minimize average response time.
Runtimes: A = 9, B = 6, C = 3, D = 5, E = x (where 3 < x < 5)
Optimal order: C, E, D, B, A
Waiting times with this order:
C: 0
E: 3
D: 3 + x
B: 3 + x + 5
A: 3 + x + 5 + 6
Sum of waiting times = 28 + 3x, so average waiting time = (28 + 3x) / 5.
Therefore, for 3 < x < 5 the ordering C, E, D, B, A minimizes the average response time.