L3. Shortest Job First (or SJF) CPU Scheduling

This chapter explores the Shortest Job First (SJF) CPU scheduling algorithm, a classic greedy approach used in operating systems to minimize the average waiting time of processes. By prioritizing processes with the smallest burst/execution times first, we can optimize overall system throughput and responsiveness under non-preemptive conditions.

1. Problem Statement & Overview

When managing multiple processes in a computer system, the operating system must decide which process gets executed by the CPU first.

• Input: An array or list of $N$ processes, where each process has a known execution time (burst time).
• Arrival Condition: For this foundational model, assume all processes arrive simultaneously at time $t = 0$.
• Objective: Compute the average waiting time for all processes when scheduled according to the Shortest Job First (SJF) policy.
• Output Rule: If the resulting average waiting time is a floating-point number (e.g., $4.2$ or $4.7$), return the floor/integer value (e.g., $4$).

2. Core Mental Model & Greedy Strategy

Real-Life Analogy

Real-Life Analogy: Imagine standing in line at a checkout counter or a coffee shop where everyone has already ordered, and the cashier wants to minimize the total time people spend waiting. If you serve the person with the shortest task first (e.g., someone just buying a stick of gum taking 5 seconds), they clear the queue immediately. If you served the person with a 20-minute grocery cart first, everyone behind them would wait 20 minutes just for their first item.

The SJF Rule

The Shortest Job First algorithm is inherently greedy because at every step, it makes the locally optimal choice:

• Scheduling Policy: Always select the waiting process with the smallest execution time to execute next.

3. Step-by-Step Execution Walkthrough

Let us trace an example with $N = 5$ processes having varying execution times:

Process List: P1 (4), P2 (3), P3 (7), P4 (1), P5 (2)
All arrive at time t = 0.

Step 1: Sort the Processes by Execution Time (Ascending)

Before scheduling, we sort the processes based on their burst times:

• P4: execution time = $1$
• P5: execution time = $2$
• P2: execution time = $3$
• P1: execution time = $4$
• P3: execution time = $7$

Step 2: Timeline Simulation

Let's track the execution, completion, and waiting times step-by-step:

1. Process P4 (Burst: $1$):

   • Starts at: $t = 0$
   • Waiting Time ($WT$) for P4 = $0$
   • Ends at: $0 + 1 = 1$

2. Process P5 (Burst: $2$):

   • Starts at: $t = 1$ (when P4 finishes)
   • Waiting Time for P5 = $1$
   • Ends at: $1 + 2 = 3$

3. Process P2 (Burst: $3$):

   • Starts at: $t = 3$ (when P5 finishes)
   • Waiting Time for P2 = $3$
   • Ends at: $3 + 3 = 6$

4. Process P1 (Burst: $4$):

   • Starts at: $t = 6$ (when P2 finishes)
   • Waiting Time for P1 = $6$
   • Ends at: $6 + 4 = 10$

5. Process P3 (Burst: $7$):

   • Starts at: $t = 10$ (when P1 finishes)
   • Waiting Time for P3 = $10$
   • Ends at: $10 + 7 = 17$

4. Calculating Average Waiting Time

Summing up all individual waiting times:

Computing the average across $N = 5$ processes:

5. Algorithmic Approach & Implementation

To implement this efficiently, we leverage a greedy strategy: sort the execution time array, maintain a running timer, accumulate the waiting time at each step, and finally divide by $N$.

Python / Pseudocode Implementation

def shortestJobFirst(arr):
    # Step 1: Sort the execution times greedily
    arr.sort()
    
    n = len(arr)
    timer = 0
    total_waiting_time = 0
    
    # Step 2: Iterate through sorted processes
    for i in range(n):
        # The waiting time for the current process is equal 
        # to the cumulative timer when it starts execution
        total_waiting_time += timer
        
        # Advance the timer by the current process's execution time
        timer += arr[i]
        
    # Step 3: Compute average waiting time (integer division truncates decimal)
    average_waiting_time = total_waiting_time // n
    return average_waiting_time

6. Complexity Analysis

Summary and Key Takeaways

• Greedy Paradigm: SJF is a classic greedy algorithm that makes locally optimal choices (picking the shortest available job) to achieve globally optimal waiting times.
• Problem Goal: Given $N$ processes with known execution times arriving at time zero, compute the integer-truncated average waiting time.
• Prerequisite Step: Always sort the processes in ascending order of their burst/execution times before scheduling.
• Waiting Time Definition: A process's waiting time is equal to the sum of the execution times of all preceding processes that completed before it started.
• Total Accumulation: The running total waiting time is formed by accumulating the timer value at the start of each process execution.
• Time Complexity: Requires $O(N \log N)$ time due to the sorting phase, plus $O(N)$ for the linear traversal.
• Space Efficiency: Can be implemented in $O(1)$ auxiliary space by sorting and modifying the input array in-place.
• Truncation Rule: Fractional average waiting times must be truncated to their nearest smaller integer (floor value).