Difficulty: Intermediate
Four processes arrive as P1 (AT 0, BT 5), P2 (AT 1, BT 3), P3 (AT 2, BT 8), P4 (AT 3, BT 6). Draw Gantt charts and compute average waiting and turnaround times for FCFS, non-preemptive SJF, SRTF and Round Robin with quantum 3.
Numerical scheduling problems are free marks if you follow a disciplined method, and a place where careless slips cost you. My advice is to always do three things: draw the Gantt chart first, write the completion time for each process from it, and then use the two formulas turnaround = completion - arrival and waiting = turnaround - burst. Never try to compute waiting times directly from intuition; derive them from the chart.
Our data is P1 (arrival 0, burst 5), P2 (1, 3), P3 (2, 8), P4 (3, 6). The total burst is 22, so every algorithm ends at time 22 as there is no idle gap.
FCFS runs in arrival order: P1 from 0 to 5, P2 from 5 to 8, P3 from 8 to 16, P4 from 16 to 22. Completion times are 5, 8, 16, 22, so turnaround times are 5, 7, 14, 19 (sum 45, average 11.25) and waiting times are 0, 4, 6, 13 (sum 23, average 5.75).
Non-preemptive SJF: at time 0 only P1 is present, so it runs to 5. At time 5, P2 (3), P3 (8) and P4 (6) are waiting; the shortest is P2, then P4, then P3. The chart is P1 0-5, P2 5-8, P4 8-14, P3 14-22. Turnaround times for P1 to P4 are 5, 7, 20, 11 (sum 43, average 10.75) and waiting times are 0, 4, 12, 5 (sum 21, average 5.25).
SRTF is preemptive. P1 starts at 0. At time 1, P2 arrives with burst 3, less than P1's remaining 4, so P2 preempts. P3 arrives at 2 (8) and P4 at 3 (6), but P2's remaining time is 2 and 1, always the smallest, so it continues and finishes at 4. Then P1 (remaining 4) beats P4 (6) and P3 (8), so P1 runs 4-8, then P4 8-14, then P3 14-22. Completion times: P1 8, P2 4, P3 22, P4 14. Turnaround: 8, 3, 20, 11 (sum 42, average 10.5). Waiting: 3, 0, 12, 5 (sum 20, average 5.0). SRTF gives the best average waiting time, as theory predicts.
Round Robin with quantum 3 needs care with queue order. The convention I use is that a process arriving at the same instant as a preempted one is queued first. P1 runs 0-3 (remaining 2); by then P2 and P3 have arrived and P4 arrives exactly at 3, so the queue becomes P2, P3, P4, P1. Then P2 runs 3-6 and finishes. P3 runs 6-9 (remaining 5). P4 runs 9-12 (remaining 3). P1 runs 12-14 and finishes. P3 runs 14-17 (remaining 2). P4 runs 17-20 and finishes. P3 runs 20-22 and finishes. Completion times: P1 14, P2 6, P3 22, P4 20. Turnaround: 14, 5, 20, 17 (sum 56, average 14.0). Waiting: 9, 2, 12, 11 (sum 34, average 8.5).
Compare the results: SRTF 5.0, SJF 5.25, FCFS 5.75, RR 8.5 for average waiting time. RR looks worst on waiting time, but that is expected because it is optimized for response time, not turnaround. Its response times here are 0, 2, 4, 6, which are much better than what FCFS gives (0, 4, 6, 13).
State your queue-order convention explicitly in an exam, because some textbooks put the preempted process before the newly arrived one, which can change the RR result. Also check your answer with a quick sanity test: total of bursts must equal the final completion time when the CPU never idles, and the sum of waiting times must equal the sum of turnaround times minus the sum of bursts (45 - 22 = 23 for FCFS).
Process AT BT
P1 0 5
P2 1 3
P3 2 8
P4 3 6
FCFS |P1 0-5|P2 5-8|P3 8-16|P4 16-22|
SJF |P1 0-5|P2 5-8|P4 8-14|P3 14-22|
SRTF |P1 0-1|P2 1-4|P1 4-8|P4 8-14|P3 14-22|
RR q=3 |P1 0-3|P2 3-6|P3 6-9|P4 9-12|P1 12-14|P3 14-17|P4 17-20|P3 20-22|
FCFS : CT = 5,8,16,22 TAT = 5,7,14,19 WT = 0,4,6,13 avg TAT 11.25 avg WT 5.75
SJF : CT = 5,8,22,14 TAT = 5,7,20,11 WT = 0,4,12,5 avg TAT 10.75 avg WT 5.25
SRTF : CT = 8,4,22,14 TAT = 8,3,20,11 WT = 3,0,12,5 avg TAT 10.50 avg WT 5.00
RR : CT = 14,6,22,20 TAT = 14,5,20,17 WT = 9,2,12,11 avg TAT 14.00 avg WT 8.50
(order of values is P1,P2,P3,P4)Each row is derived from its Gantt chart: TAT = CT - AT and WT = TAT - BT.
Gantt chart, waiting time, turnaround time, SRTF, Round Robin