a. Four jobs are waiting to be run. Their expected run times are 6, 3, 5, and 2 (in some unit). In what order should they be run to minimize the average response time?
b. Write a concurrent program using par begin/par end to represent the precedence graph shown below (a graph where S1 must complete before S2 and S3 can start; S2 and S3 must complete before S4 can start).
GATE 1998 · Operating System · Process Scheduling · medium
Answer: Schedule order: 2, 3, 5, 6 (ascending run time). Average response time = 8.25 units.
Sort jobs by run time (SJF order): Run times sorted ascending: 2, 3, 5, 6. Order: D(2), B(3), C(5), A(6).
Calculate completion times and average: D finishes at t=2. B finishes at t=2+3=5. C finishes at t=5+5=10. A finishes at t=10+6=16. Average = (2+5+10+16)/4 = 33/4 = 8.25.