Consider the following four processes with the arrival time and length of CPU burst given in milliseconds:

Process	Arrival Time	Burst Time
P1	0	8
P2	1	4
P3	2	9
P4	3	5

Using the preemptive shortest job first (SJF / SRTF) scheduling algorithm, what is the average waiting time (in ms) for these processes?

Explanation

Under preemptive SJF (SRTF), the scheduler always runs whichever ready process has the least remaining burst time, re-checking at every new arrival. P1 starts at t=0, but at t=1 P2 (burst 4) preempts it since P2's remaining time is less than P1's remaining 7 ms, and P2 keeps the shortest remaining time through the arrivals of P3 (t=2) and P4 (t=3), so it runs uninterrupted to completion at t=5. At t=5 the shortest remaining job is P4 (5), which runs 5-10; then P1 (remaining 7) runs 10-17; finally P3 (9) runs 17-26, giving completion times 17, 5, 26, 10 for P1-P4. Waiting time = completion time - arrival time - burst time: P1=17-0-8=9, P2=5-1-4=0, P3=26-2-9=15, P4=10-3-5=2, so the average waiting time is (9+0+15+2)/4 = 6.5 ms.