Preemptive Shortest Job First (SJF)
Preemptive Shortest Job First (SJF) is a CPU scheduling algorithm that selects the process with the smallest execution time to execute next. Unlike its non-preemptive counterpart, preemptive SJF can interrupt a currently running process if a new process arrives with a shorter burst time. This ensures a more optimal use of CPU time, leading to improved overall system performance in terms of average waiting time and average turnaround time.
Conceptual Overview
At its core, preemptive SJF scheduling is about minimizing the total waiting time for all processes. It operates under the assumption that the burst time (the time required by a process to complete its execution) is known in advance. The scheduler then dynamically orders processes based on their remaining burst times, leading to a dynamic reordering of the process queue as new processes arrive or as existing processes execute.
Algorithm Components
Understanding the preemptive SJF algorithm requires familiarity with its key components:
- Process Queue: A dynamic list of all processes waiting to be executed, ordered by burst time.
- Burst Time: The estimated time a process will take to complete its execution.
- Arrival Time: The time at which a process arrives in the ready queue.
- Preemption: The act of interrupting a currently running process to switch CPU control to another process, based on some priority (in this case, burst time).
Decision Making Process
The preemptive SJF scheduler makes scheduling decisions based on two key events:
- When a process arrives at the ready queue.
- When a process completes its execution.
At each decision point, the scheduler evaluates the burst times of all processes in the ready queue, including the currently executing process, and selects the process with the shortest burst time. This may result in preemption if a newly arrived process has a shorter burst time than the currently executing process.
Algorithm for Preemptive SJF
The core algorithm for Preemptive Shortest Job First (SJF) scheduling involves the following steps:
- Upon the arrival of a process, add it to the ready queue. If the CPU is idle, proceed to step 2; otherwise, proceed to step 3.
- Select the process with the shortest execution (burst) time from the ready queue and start its execution on the CPU.
- If a new process arrives with a shorter execution time than the remaining time of the currently executing process, preempt the current process. Save the context of the preempted process, and move it back to the ready queue.
- Execute the new process with the shortest execution time.
- If the currently executing process completes, select the next process with the shortest execution time from the ready queue.
- Repeat steps 3 to 5 until all processes have been executed and the ready queue is empty.
This approach ensures that at any given time, the process with the shortest execution time is being processed, thereby aiming to minimize the overall waiting time and improve system efficiency.
Implementation Challenges
Implementing preemptive SJF involves overcoming several challenges, including:
- Estimating Burst Times: Accurately predicting the burst time of processes is difficult and often relies on historical data or heuristics.
- Context Switching Overhead: Frequent preemptions increase the overhead due to context switching, potentially negating the benefits of reduced waiting times.
- Starvation: Long-burst-time processes may suffer starvation, as they are continually preempted by shorter-burst-time processes.
Optimizations
Several strategies can mitigate the challenges of preemptive SJF scheduling:
- Aging: Incrementally increasing the priority of waiting processes to prevent starvation.
- Effective Burst Time Estimation: Using more sophisticated algorithms to estimate burst times, such as exponential averaging.
- Limiting Preemption: Introducing constraints on preemption to reduce context switching overhead, balancing responsiveness with efficiency.
Mathematical Analysis
The effectiveness of preemptive SJF can be quantified through metrics like average waiting time (AWT) and average turnaround time (ATT) using the formulas mentioned previously in the FCFS article The goal is to minimize these metrics for enhanced performance.
Gantt Chart for Preemptive SJF
To demonstrate the Preemptive SJF scheduling algorithm, we'll use a process table to create a Gantt chart. This example will highlight the dynamic nature of preemptive scheduling, where processes can be interrupted and resumed based on the arrival of shorter burst time processes.
Given Process Table
Consider a process table for Preemptive SJF, with specified arrival and burst times.
Job | AT | BT |
---|---|---|
A | 1 | 2 |
B | 1 | 3 |
C | 0 | 5 |
D | 2 | 1 |
Step-by-Step Gantt Chart Construction
- Step 1: At time 0, start with P3 as it's the only process.
- Step 2: At time 1, P1 arrives and since P1 has the shortest remaining time, so continue with P1.
- Step 3: At time 3, P4 arrives. P4 completes with just 1 units of time.
- Step 4: At time 4, P2 arrives with the shortest burst time (3). Preempt P3 and start P2.
- Step 5: After P2 completes at time 7, resume P3 as it now has the shortest remaining time (4).
- Step 6: Continue this process until all processes have been completed, dynamically adjusting as new processes arrive.
- Step 6: P3 completes at 11 units of time in this case.
Gantt Chart Representation
This Gantt chart represents the execution order and duration for each process based on Preemptive SJF scheduling, illustrating the dynamic preemption and resumption of processes.
Gantt Chart Interpretation and Metrics Calculation
The visual representation demonstrates the preemptive nature of the SJF scheduling algorithm, emphasizing its efficiency in managing CPU time. By preempting longer processes in favor of shorter ones, Preemptive SJF minimizes average waiting time and improves overall system performance. It also illustrates the algorithm's complexity in real-time decision-making based on process arrival and burst times.
Job | AT | BT | CT | TAT | WT |
---|---|---|---|---|---|
C | 0 | 5 | 11 | 11 | 6 |
A | 1 | 2 | 7 | 6 | 4 |
B | 1 | 3 | 5 | 4 | 1 |
D | 2 | 1 | 3 | 1 | 0 |
Average | 22 / 4 = 5.5 | 11 / 4 = 2.75 |
Preemptive SJF Scheduling Example
Let's analyze Preemptive SJF scheduling using a process table with 5 processes, calculate key metrics, and illustrate with a Gantt chart.
Process | Arrival Time (AT) | Burst Time (BT) |
---|---|---|
P1 | 0 | 6 |
P2 | 2 | 8 |
P3 | 1 | 7 |
P4 | 3 | 3 |
P5 | 5 | 4 |
Gantt Chart Representation
The Gantt chart for these processes, scheduled according to Preemptive SJF, dynamically changes as processes arrive and is represented as follows:
This Gantt chart accounts for preemption whenever a process with a shorter burst time arrives.
Calculating Preemptive SJF Metrics
We calculate the Completion Time (CT), Turnaround Time (TAT), and Waiting Time (WT) for each process, followed by the average TAT and WT.
Completion Time (CT)
For Preemptive SJF, CT is calculated based on when each process finishes its execution, considering preemptions:
- \(CT_{P1} = 6\)
- \(CT_{P2} = 28\)
- \(CT_{P3} = 20\)
- \(CT_{P4} = 9\)
- \(CT_{P5} = 13\)
Turnaround Time (TAT)
Turnaround time (\(TAT = CT - AT\)):
- \(TAT_{P1} = 6 - 0 = 6\)
- \(TAT_{P2} = 28 - 2 = 26\)
- \(TAT_{P3} = 20 - 1 = 19\)
- \(TAT_{P4} = 9 - 3 = 6\)
- \(TAT_{P5} = 13 - 5 = 8\)
Waiting Time (WT)
Waiting time (\(WT = TAT - BT\)):
- \(WT_{P1} = 6 - 6 = 0\)
- \(WT_{P2} = 26 - 8 = 18\)
- \(WT_{P3} = 19 - 7 = 12\)
- \(WT_{P4} = 6 - 3 = 3\)
- \(WT_{P5} = 8 - 4 = 4\)
Note: Calculation corrections may be needed for accurate WT and TAT, especially in preemptive contexts.
Average Turnaround Time (TATave)
$$WT_{ave} = \frac{\sum{WT_i}}{n}$$ $$= \frac{6 + 26 + 19 + 6 + 8}{5}$$ $$= \frac{65}{5}$$ $$= 13$$
Average Waiting Time (WTave)
$$WT_{ave} = \frac{\sum{WT_i}}{n}$$ $$= \frac{0 + 18 + 12 + 3 + 4}{5}$$ $$= \frac{37}{5}$$ $$= 7.4$$
Job | AT | BT | FT | TAT | WT |
---|---|---|---|---|---|
P1 | 0 | 6 | 6 | 6 | 0 |
P3 | 1 | 7 | 20 | 19 | 12 |
P2 | 2 | 8 | 28 | 26 | 18 |
P4 | 3 | 3 | 9 | 6 | 3 |
P5 | 5 | 4 | 13 | 8 | 4 |
Average | 65 / 5 = 13 | 37 / 5 = 7.4 |
Preemptive SJF Scheduling Implementation in Python
Implementing Preemptive SJF involves preempting the currently running process if a new process arrives with a shorter burst time. This section outlines a Python implementation of the Preemptive SJF scheduling algorithm.
# Python pseudo-code for Preemptive SJF scheduling
def preemptive_sjf_schedule(processes):
"""
Preemptive SJF scheduling algorithm.
:param processes: List of tuples containing (process_id, arrival_time, burst_time)
:return: A list of tuples containing process execution order and their completion times
"""
# Sort processes by arrival time
processes.sort(key=lambda x: x[1])
completed = []
ready_queue = []
current_time = 0
while processes or ready_queue:
# Add arriving processes to the ready queue
while processes and processes[0][1] <= current_time:
ready_queue.append(processes.pop(0))
if ready_queue:
# Select process with the shortest burst time
ready_queue.sort(key=lambda x: x[2])
current_process = ready_queue.pop(0)
process_id, arrival_time, burst_time = current_process
# Determine next event time (arrival of new process or completion of current)
next_time = processes[0][1] if processes else float('inf')
execution_time = min(burst_time, next_time - current_time)
# Execute the process
current_time += execution_time
burst_time -= execution_time
# If process finished, add to completed; else, put back in ready queue with updated burst time
if burst_time == 0:
completed.append((process_id, current_time))
else:
ready_queue.append((process_id, arrival_time, burst_time))
else:
current_time = processes[0][1]
return completed
# Example processes: (process_id, arrival_time, burst_time)
processes = [("P1", 0, 6), ("P2", 2, 8), ("P3", 1, 7), ("P4", 3, 3), ("P5", 5, 4)]
# Execute scheduling
completed_processes = preemptive_sjf_schedule(processes)
# Print completion times
for process in completed_processes:
print(f"Process {process[0]} completed at time {process[1]}")
This implementation highlights the preemptive nature of the SJF algorithm, where processes are interrupted based on the arrival of shorter burst time processes. The code maintains a dynamic ready queue, ensuring that at any time, the process with the shortest remaining burst time is selected for execution.