Consider the following set of processes with their arrival times and burst times:
| Process | Arrival Time | Burst Time |
|---|---|---|
| P1 | 0 | 8 |
| P2 | 1 | 4 |
| P3 | 2 | 9 |
| P4 | 3 | 5 |
The CPU scheduling algorithm used is Preemptive Shortest Remaining Time First (SRTF). A context switch incurs an overhead of 1 unit of time. Whenever the CPU switches from one process to another (due to preemption or completion), it takes 1 unit of time for the switch during which no process executes. If two processes have the same remaining time, the one that arrived earlier is scheduled. If they arrive at the same time and have the same remaining time, the process with the lower ID is scheduled. What is the average turnaround time for these processes?
Let's trace the execution of processes using the SRTF algorithm with a context switch overhead of 1 unit. The rule for context switch overhead is that 1 unit of time is consumed *between* any two processes executing, where the CPU is idle.
Processes:
- P1: Arrival Time = 0, Burst Time = 8
- P2: Arrival Time = 1, Burst Time = 4
- P3: Arrival Time = 2, Burst Time = 9
- P4: Arrival Time = 3, Burst Time = 5
Context Switch Overhead (CS) = 1 unit
Gantt Chart and Timeline:
- Time 0: P1 arrives. No other process. P1 starts execution. Remaining Burst (RB) for P1 = 8.
- Time 1: P2 arrives. P1 has run for 1 unit (RB P1 = 7). Comparing P1 (RB=7) and P2 (BT=4). P2 has a shorter remaining time. P1 is preempted.
- Time 1 to 2: Context Switch (CS) occurs (1 unit idle time).
- Time 2: P2 starts execution. RB for P2 = 4.
- Time 3: P4 arrives. Current running process is P2 (RB=3). Ready processes: P1 (RB=7), P4 (BT=5), P3 (not yet arrived). P2 (RB=3) is still the shortest. P2 continues.
- Time 4: P3 arrives. Current running process is P2 (RB=2). Ready processes: P1 (RB=7), P3 (BT=9), P4 (BT=5). P2 (RB=2) is still the shortest. P2 continues.
- Time 6: P2 finishes its burst (executed for 4 units from T=2 to T=6). RB for P2 = 0.
- Time 6 to 7: Context Switch (CS) occurs (1 unit idle time).
- Time 7: Ready processes: P1 (RB=7), P3 (RB=9), P4 (RB=5). P4 (RB=5) is the shortest. P4 starts execution.
- Time 12: P4 finishes its burst (executed for 5 units from T=7 to T=12). RB for P4 = 0.
- Time 12 to 13: Context Switch (CS) occurs (1 unit idle time).
- Time 13: Ready processes: P1 (RB=7), P3 (RB=9). P1 (RB=7) is the shortest. P1 starts execution.
- Time 20: P1 finishes its burst (executed for 7 units from T=13 to T=20). RB for P1 = 0.
- Time 20 to 21: Context Switch (CS) occurs (1 unit idle time).
- Time 21: Ready processes: P3 (RB=9). P3 starts execution.
- Time 30: P3 finishes its burst (executed for 9 units from T=21 to T=30). RB for P3 = 0.
Completion Times (CT):
- P1: 20
- P2: 6
- P3: 30
- P4: 12
Turnaround Times (TAT = CT - Arrival Time):
- P1: 20 - 0 = 20
- P2: 6 - 1 = 5
- P3: 30 - 2 = 28
- P4: 12 - 3 = 9
Average Turnaround Time:
Average TAT = (20 + 5 + 28 + 9) / 4 = 62 / 4 = 15.5 The correct answer is 15.5.