Question

Three processes arrive at time zero with CPU bursts of 16, 20, and 10 milliseconds. If the scheduler has prior knowledge about the length of the CPU bursts, the minimum achievable average waiting time for these three processes in a non-preemptive scheduler (rounded to nearest integer) is \(\underline{\hspace{2cm}}\) milliseconds.

Hint:

Shortest Job First (SJF) scheduling always gives the minimum average waiting time when burst times are known.

Answer 1

Correct Answer: 12

Step 1: Identify the optimal scheduling policy.
When CPU burst times are known in advance, the Shortest Job First (SJF) scheduling policy minimizes average waiting time.

Step 2: Order the processes by CPU burst time.
The burst times in ascending order are:
\[ 10 \text{ ms}, \; 16 \text{ ms}, \; 20 \text{ ms} \]

Step 3: Compute waiting times.
- Process with 10 ms burst: waiting time \( = 0 \) ms
- Process with 16 ms burst: waiting time \( = 10 \) ms
- Process with 20 ms burst: waiting time \( = 10 + 16 = 26 \) ms

Step 4: Calculate the average waiting time.
\[ \text{Average waiting time} = \frac{0 + 10 + 26}{3} = \frac{36}{3} = 12 \] % Final Answer

Final Answer: \[ \boxed{12} \]