DSA 450 Notes

Problem Statement

Implement the Shortest Job First (SJF) CPU scheduling algorithm. Given n processes with their arrival times and burst times, calculate the average waiting time and average turnaround time.

SJF Algorithm: At any point, the process with the smallest burst time (among those that have arrived) is executed first.

Definitions:

Waiting Time: Time a process waits before execution starts
Turnaround Time: Total time from arrival to completion (Waiting Time + Burst Time)

Constraints:

1 ≤ n ≤ 10^5
0 ≤ arrival_time[i] ≤ 10^6
1 ≤ burst_time[i] ≤ 10^4

Example:

Input: processes = [(0, 6), (1, 8), (2, 7), (3, 3)] (arrival, burst)
Output: Average Waiting Time: 7.0, Average Turnaround Time: 13.0

Example 2:

Input: processes = [(0, 3), (0, 2), (0, 1)] (all arrive at time 0)
Output: Execute in order of burst time: 1 → 2 → 3

Approach 1: Brute Force (Selection at Each Step)

Intuition

At each time unit, scan through all processes to find the one with minimum burst time that has arrived and not yet completed. This mimics the actual scheduling behavior.

Algorithm

Maintain list of incomplete processes
At current time, find process with minimum burst time among arrived processes
Execute that process completely
Update current time and calculate waiting/turnaround times
Repeat until all processes complete

java

import java.util.*;

class Process {
    int id, arrival, burst, waiting, turnaround;
    boolean completed;
    
    Process(int id, int arrival, int burst) {
        this.id = id;
        this.arrival = arrival;
        this.burst = burst;
        this.completed = false;
    }
}

public class Solution {
    public void sjfScheduling(List<Process> processes) {
        int n = processes.size();
        int currentTime = 0;
        int completed = 0;
        
        while (completed < n) {
            int minBurst = Integer.MAX_VALUE;
            int minIdx = -1;
            
            // Find process with minimum burst time among arrived processes
            for (int i = 0; i < n; i++) {
                Process p = processes.get(i);
                if (!p.completed && p.arrival <= currentTime && p.burst < minBurst) {
                    minBurst = p.burst;
                    minIdx = i;
                }
            }
            
            if (minIdx == -1) {
                currentTime++;
            } else {
                Process p = processes.get(minIdx);
                p.waiting = currentTime - p.arrival;
                currentTime += p.burst;
                p.turnaround = p.waiting + p.burst;
                p.completed = true;
                completed++;
            }
        }
    }
    
    public double[] calculateAverages(List<Process> processes) {
        double totalWaiting = 0, totalTurnaround = 0;
        int n = processes.size();
        
        for (Process p : processes) {
            totalWaiting += p.waiting;
            totalTurnaround += p.turnaround;
        }
        
        return new double[]{totalWaiting / n, totalTurnaround / n};
    }
}

Complexity Analysis

Time Complexity: O(n²) - For each of n processes, we scan all n processes
Space Complexity: O(n) - Storing process information

Approach 2: Optimized with Sorting and Priority Queue

Intuition

Instead of scanning all processes repeatedly, we can:

Sort processes by arrival time
Use a priority queue (min-heap) to efficiently get the process with minimum burst time

Algorithm

Sort processes by arrival time
Use min-heap based on burst time
At each step, add all arrived processes to heap
Extract minimum burst time process and execute
Repeat until all processes complete

java

import java.util.*;

class Process implements Comparable<Process> {
    int id, arrival, burst, waiting, turnaround;
    
    Process(int id, int arrival, int burst) {
        this.id = id;
        this.arrival = arrival;
        this.burst = burst;
    }
    
    @Override
    public int compareTo(Process other) {
        return this.burst - other.burst;
    }
}

public class Solution {
    public double[] sjfScheduling(List<Process> processes) {
        int n = processes.size();
        
        // Sort by arrival time
        processes.sort((a, b) -> a.arrival - b.arrival);
        
        // Min-heap based on burst time
        PriorityQueue<Process> pq = new PriorityQueue<>();
        
        int currentTime = 0;
        int idx = 0;
        int completed = 0;
        double totalWaiting = 0, totalTurnaround = 0;
        
        while (completed < n) {
            // Add all processes that have arrived by current time
            while (idx < n && processes.get(idx).arrival <= currentTime) {
                pq.offer(processes.get(idx));
                idx++;
            }
            
            if (pq.isEmpty()) {
                currentTime = processes.get(idx).arrival;
            } else {
                Process p = pq.poll();
                
                p.waiting = currentTime - p.arrival;
                currentTime += p.burst;
                p.turnaround = p.waiting + p.burst;
                
                totalWaiting += p.waiting;
                totalTurnaround += p.turnaround;
                completed++;
            }
        }
        
        return new double[]{totalWaiting / n, totalTurnaround / n};
    }
    
    public static void main(String[] args) {
        Solution sol = new Solution();
        List<Process> processes = Arrays.asList(
            new Process(0, 0, 6),
            new Process(1, 1, 8),
            new Process(2, 2, 7),
            new Process(3, 3, 3)
        );
        double[] result = sol.sjfScheduling(processes);
        System.out.println("Average Waiting Time: " + result[0]);
        System.out.println("Average Turnaround Time: " + result[1]);
    }
}

Dry Run Example

Processes: P0(arr=0, burst=6), P1(arr=1, burst=8), P2(arr=2, burst=7), P3(arr=3, burst=3)

Step 1: Sort by arrival (already sorted)
Processes = [P0, P1, P2, P3]

Step 2: Initialize
currentTime = 0, heap = []

Iteration 1: currentTime = 0
- Add P0 (arrived at 0) to heap
- heap = [P0(6)]
- Execute P0: waiting = 0-0 = 0, currentTime = 0+6 = 6
- P0: turnaround = 0+6 = 6

Iteration 2: currentTime = 6
- Add P1(arr=1), P2(arr=2), P3(arr=3) to heap
- heap = [P3(3), P2(7), P1(8)] (min-heap by burst)
- Execute P3: waiting = 6-3 = 3, currentTime = 6+3 = 9
- P3: turnaround = 3+3 = 6

Iteration 3: currentTime = 9
- No new arrivals
- heap = [P2(7), P1(8)]
- Execute P2: waiting = 9-2 = 7, currentTime = 9+7 = 16
- P2: turnaround = 7+7 = 14

Iteration 4: currentTime = 16
- No new arrivals
- heap = [P1(8)]
- Execute P1: waiting = 16-1 = 15, currentTime = 16+8 = 24
- P1: turnaround = 15+8 = 23

Results:
- Total Waiting = 0 + 3 + 7 + 15 = 25 (Note: using proper calculation)
- Let me recalculate...

Correct calculation:
P0: waiting = 0, turnaround = 6
P3: waiting = 6-3 = 3, turnaround = 3+3 = 6
P2: waiting = 9-2 = 7, turnaround = 7+7 = 14
P1: waiting = 16-1 = 15, turnaround = 15+8 = 23

Total waiting = 0 + 3 + 7 + 15 = 25 → Avg = 6.25
Total turnaround = 6 + 6 + 14 + 23 = 49 → Avg = 12.25

Complexity Analysis

Time Complexity: O(n log n) - Sorting takes O(n log n), and each heap operation is O(log n)
Space Complexity: O(n) - For storing processes in heap

Key Takeaways

SJF is Optimal: Minimizes average waiting time among non-preemptive algorithms
Greedy Choice: Always select the process with shortest burst time
Convoy Effect: Long processes may wait indefinitely (starvation)
Priority Queue Optimization: Reduces selection from O(n) to O(log n)
Real-World Usage: Basis for many production scheduling systems
Limitation: Requires knowing burst times in advance (not always possible)
Variants: SRTF (Shortest Remaining Time First) is the preemptive version

Program for Shortest Job First (or SJF) CPU Scheduling

Problem Statement

Approach 1: Brute Force (Selection at Each Step)

Intuition

Algorithm

Complexity Analysis

Approach 2: Optimized with Sorting and Priority Queue

Intuition

Algorithm

Dry Run Example

Complexity Analysis

Key Takeaways