Shortest Job First (SJF) Scheduling Algorithm - Problem Solving

Introduction

Discussion of a problem related to Shortest Job First (SJF) Scheduling Algorithm.
Previously covered algorithm basics and properties.
Problem context: Gate 2014, Computer Science.

Operating system uses Shortest Remaining Time First for preemptive scheduling.
Given:
- Set of processes with arrival and burst times in milliseconds.
- Aim: Find the average waiting time.
Options:
- A: 4.5 ms
- B: 5.0 ms
- C: 5.5 ms
- D: 6.5 ms

Preemptive Scheduling: CPU can be taken away from a process if another process with a shorter remaining burst time arrives.
Shortest Remaining Time First: A preemptive version of SJF.

4 Processes: P1 to P4
Arrival and Burst Times Table:
- P1: arrival=0 ms, burst=12 ms
- P2: arrival=2 ms, burst=4 ms
- P3: arrival=3 ms, burst=6 ms
- P4: arrival=8 ms, burst=5 ms

Construct the Gantt Chart: Process Execution Timeline.
- Time 0: P1 arrives, starts execution.
- Time 2: P2 arrives, as P2 burst time (4 ms) < P1 remaining burst time (10 ms), P2 preempts P1 and starts execution.
- Time 3: P3 arrives, but P2 continues as its remaining burst time (3 ms) < P3 burst time (6 ms).
- Time 6: P2 completes, P1 continues execution (remaining burst time 10 ms) until P4 arrives.
- Time 8: P4 arrives, preempts P1 (remaining time 2 ms for P3 < P4, hence P4 starts execution).
- Time 12: P3 continues execution till 12º ms and finishes.
- Time 17: P4 continues and finishes at 17º ms, P1 resumes and finishes at 27º ms.
Calculate Waiting Times for Each Process: Arrival vs Execution Timeline.
- P1: Waiting Time = (Total Wait Time - Executed Time - Arrival Time) = (17 - 2 - 0) = 15 ms.
- P2: Waiting Time = (2 - 0 - 2) = 0 ms.
- P3: Waiting Time = (6 - 0 - 3) = 3 ms.
- P4: Waiting Time = (12 - 0 - 8) = 4 ms.
Compute Average Waiting Time: Sum of Waiting Times / Number of Processes.
- (15 + 0 + 3 + 4) / 4 = 22 / 4 = 5.5 ms