Scheduling Algorithms: SRTF/SJF-P - CSU360 - Shoolini University

Scheduling Algorithms: Preemptive Shortest Job First

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:

Decision Making Process

The preemptive SJF scheduler makes scheduling decisions based on two key events:

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:

  1. 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.
  2. Select the process with the shortest execution (burst) time from the ready queue and start its execution on the CPU.
  3. 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.
  4. Execute the new process with the shortest execution time.
  5. If the currently executing process completes, select the next process with the shortest execution time from the ready queue.
  6. 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:

Optimizations

Several strategies can mitigate the challenges of preemptive SJF scheduling:

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

C
A
D
B
C
0
1
3
4
7
11

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:

P1
P4
P5
P3
P2
0
6
9
13
20
28

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.