L-2.4: Shortest Job First(SJF) Scheduling Algorithm with Example | Operating System
Understanding Shortest Job First Scheduling Algorithm
Introduction to the Concept
- The video introduces the Shortest Job First (SJF) scheduling algorithm, focusing on four processes: P1, P2, P3, and P4. It outlines the need to calculate completion time, turnaround time, waiting time, and response time for these processes.
Key Characteristics of SJF
- The SJF algorithm prioritizes processes based on their burst time; shorter burst times are executed first.
- This scheduling mode is non-preemptive, meaning once a process starts executing on the CPU, it runs to completion without interruption.
Gantt Chart Utilization
- The explanation begins with a Gantt chart to visualize process execution over time. Time tracking starts from zero.
- At time 0, no processes have arrived; thus, the CPU remains idle until at least one process arrives.
Arrival and Execution of Processes
- At time 1, both P1 and P3 arrive. Burst times are compared to determine which process will execute first.
- Since P3 has a shorter burst time (2 units), it is selected for execution first. Its total execution takes place from time 1 to 3.
Continuing Process Selection
- After executing P3 completely by time 3, the next step involves checking which processes have arrived by that point—P1 and P2 are in consideration.
- With both processes available in the ready queue (P1 with a burst of 3 and P2 with a burst of 4), selection criteria focus again on burst times.
Handling Equal Burst Times
- When evaluating remaining processes at time 6 (P2 and newly arrived P4), both have equal burst times (4). Arrival times become crucial for decision-making.
- Since P2 arrived before P4 at time 2 versus an assumed arrival of 4 for P4, it is selected next despite equal burst durations.
Final Execution Steps
- After executing all prior processes up to their respective completion points (P1 at 6 and then running through others), only P4 remains. It executes last from time 10 to completion at 14.
Calculating Completion Times
- Completion times are recorded as follows:
- P1: Completed at 6
- P2: Completed at 10
- P3: Completed at 3
- P4: Completed at 14
Turnaround Time & Waiting Time Calculation
- Turnaround Time (TAT): TAT = Completion Time - Arrival Time:
- For each process calculated accordingly leading to values like TAT for P1 being 5, etc.
- Waiting Time (WT): WT = TAT - Burst Time:
- Each waiting period derived similarly results in specific values such as WT for each process being calculated directly from previous results.
Understanding Response Time and Turnaround Time in Pre-emptive Scheduling
Key Concepts of Pre-emptive Scheduling
- In pre-emptive scheduling, response time is not calculated as it equates to waiting time. If asked, one can explain the calculation method for clarity.
- When a process receives CPU time in a pre-emptive system, it executes completely without interruption. This means that once a process gets CPU access, it will finish its execution before another process can take over.
Implications of CPU Switching
- In pre-emptive cases, the CPU may switch between processes multiple times. This allows for fairness in resource allocation but complicates response time calculations.
- Since response time equals waiting time in this context, it's acceptable to omit direct calculations for response time when discussing average turnaround times.
Average Turnaround Time Calculation