Title here
Summary here
OS 5.03.02 - Shortest Job First
The Shortest Job First (SJF) scheduling algorithm assigns the CPU to the process with the shortest next CPU burst. The process with the smallest next burst time is given priority when the CPU becomes available.
If two processes have the same next CPU burst, FCFS (First-Come, First-Served) is used to break the tie.
- A more appropriate term for this algorithm would be Shortest-Next-CPU-Burst scheduling, as it relies on the length of the next CPU burst of a process, rather than its total CPU burst time.
Optimality:
- The SJF algorithm is provably optimal, meaning it minimizes the average waiting time for a given set of processes.
- Moving shorter processes ahead of longer ones reduces the waiting time of short processes more than it increases the waiting time of long processes, leading to a decrease in average waiting time.
Preemptive vs Nonpreemptive SJF:
Nonpreemptive SJF: Once a process starts executing, it continues until it finishes its CPU burst, even if a new process arrives with a shorter burst.
Preemptive SJF: If a new process arrives with a shorter CPU burst than the remaining burst of the currently running process, the CPU is preempted and allocated to the new process.
- Preemptive SJF is also known as Shortest-Remaining-Time-First (SRTF) scheduling.
Example 1 : Preemptive SJF (SRTF)
Processes:
- P1: Arrival Time = 0 ms, Burst Time = 8 ms
- P2: Arrival Time = 1 ms, Burst Time = 4 ms
- P3: Arrival Time = 2 ms, Burst Time = 3 ms
- P4: Arrival Time = 3 ms, Burst Time = 2 ms
Step-by-Step Execution:
| Time | Process Running | Remaining Burst Time | Notes |
|---|---|---|---|
| 0 | P1 | 8 | P1 arrives, starts execution. |
| 1 | P2 | 4 | P2 arrives; P1 has 7 ms left, P2 has 4 ms; P2 preempts P1. |
| 2 | P3 | 3 | P3 arrives; P2 has 3 ms left, P3 has 3 ms; P3 preempts P2. |
| 3 | P4 | 2 | P4 arrives; P3 has 2 ms left, P4 has 2 ms; P4 preempts P3. |
| 4 | P4 | 1 | P4 completes 1 ms of its burst. |
| 5 | P4 | 0 | P4 finishes its burst. |
| 6 | P3 | 2 | P3 resumes, has 2 ms remaining. |
| 7 | P3 | 1 | P3 runs for 1 ms. |
| 8 | P3 | 0 | P3 finishes its burst. |
| 9 | P2 | 3 | P2 resumes and runs for 3 ms. |
| 12 | P1 | 7 | P1 resumes with 7 ms left. |
| 13 | P1 | 6 | P1 runs for 1 ms. |
| 14 | P1 | 5 | P1 runs for 1 ms. |
| 15 | P1 | 4 | P1 runs for 1 ms. |
| 16 | P1 | 3 | P1 runs for 1 ms. |
| 17 | P1 | 2 | P1 runs for 1 ms. |
| 18 | P1 | 1 | P1 runs for 1 ms. |
| 19 | P1 | 0 | P1 finishes its burst. |
Gantt Chart:
| P1 | P2 | P3 | P4 | P4 | P3 | P3 | P2 | P1 | P1 | P1 | P1 | P1 | P1 |
0 1 2 3 4 5 6 7 8 9 10 11 12 13Example 2 : Preemptive SJF (SRTF) Scenario
Processes:
- P1: Arrival Time = 0 ms, Burst Time = 6 ms
- P2: Arrival Time = 1 ms, Burst Time = 2 ms
- P3: Arrival Time = 2 ms, Burst Time = 8 ms
Step-by-Step Execution:
| Time | Process Running | Remaining Burst Time | Notes |
|---|---|---|---|
| 0 | P1 | 6 | P1 starts execution. |
| 1 | P2 | 2 | P2 arrives and preempts P1, since P2 has the shortest burst time. |
| 2 | P2 | 1 | P2 runs for 1 ms. |
| 3 | P2 | 0 | P2 finishes execution. |
| 4 | P1 | 5 | P1 resumes with 5 ms left. |
| 5 | P1 | 4 | P1 runs for 1 ms. |
| 6 | P1 | 3 | P1 runs for 1 ms. |
| 7 | P1 | 2 | P1 runs for 1 ms. |
| 8 | P1 | 1 | P1 runs for 1 ms. |
| 9 | P1 | 0 | P1 finishes. |
| 10 | P3 | 8 | P3 starts execution. |
| 11 | P3 | 7 | P3 runs for 1 ms. |
| 12 | P3 | 6 | P3 runs for 1 ms. |
| 13 | P3 | 5 | P3 runs for 1 ms. |
| 14 | P3 | 4 | P3 runs for 1 ms. |
| 15 | P3 | 3 | P3 runs for 1 ms. |
| 16 | P3 | 2 | P3 runs for 1 ms. |
| 17 | P3 | 1 | P3 runs for 1 ms. |
| 18 | P3 | 0 | P3 finishes. |
Gantt Chart:
| P1 | P2 | P2 | P1 | P1 | P1 | P1 | P1 | P3 | P3 | P3 | P3 | P3 | P3 | P3 | P3 |
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15Challenges with Implementation:
- While SJF is optimal, it is not directly implementable in short-term CPU scheduling since the next CPU burst is unknown.
- We can approximate the next CPU burst by predicting its length based on previous bursts.
Predicting the Next CPU Burst:
The next CPU burst is generally predicted as an exponential average of the lengths of previous CPU bursts. The formula for the prediction is:
T(n+1) = α * Tn + (1 - α) * TnWhere:
Tn= length of the nth CPU burstT(n+1)= predicted value for the next CPU burstα= weighting factor (0 ≤ α ≤ 1)
Interpretation of α:
- If
α = 0, thenT(n+1) = Tn, meaning only the most recent CPU burst is considered. - If
α = 1, thenT(n+1) = Tn, meaning only the most recent burst is considered, with no weight given to past history. - Typically,
α = 0.5, meaning recent and past bursts are equally weighted.
The initial value of T0 can be set as a constant or as the system’s overall average.