Consider the following table of arrival time and burst time for three…
2011
Consider the following table of arrival time and burst time for three processes P0,P1 and P2.
\(\small \begin{array}{|c|c|c|} \hline \textbf{Process} & \textbf{Arrival Time} & \textbf{Burst Time}\\\hline \text{P0} & \text{0 ms} & 9 \\\hline \text{P1} & \text{1 ms} & 4 \\\hline \text{P2} & \text{2 ms} & 9 \\\hline \end{array}\)
The pre-emptive shortest job first scheduling algorithm is used. Scheduling is carried out only at arrival or completion of processes. What is the average waiting time for the three processes?
- A.
5.0 ms
- B.
4.33 ms
- C.
6.33 ms
- D.
7.33 ms
Attempted by 412 students.
Show answer & explanation
Correct answer: A
Key idea: apply preemptive SJF (shortest remaining time first); at each arrival or completion run the process with the smallest remaining time.
t = 0 to 1: P0 runs (remaining 8 at t = 1).
t = 1: P1 arrives with burst 4, which is less than P0's remaining 8, so P1 preempts and runs from 1 to 5 (completes).
t = 2: P2 arrives (burst 9) but P1 (remaining) is shortest, so no change.
t = 5 to 13: P0 resumes and completes.
t = 13 to 22: P2 runs and completes.
Waiting times:
P0: completion 13 − arrival 0 − burst 9 = 4 ms
P1: completion 5 − arrival 1 − burst 4 = 0 ms
P2: completion 22 − arrival 2 − burst 9 = 11 ms
Average waiting time = (4 + 0 + 11) / 3 = 5.0 ms.
A video solution is available for this question — log in and enroll to watch it.