Operating SystemsCPU Scheduling

Shortest Job First (SJF) & SRTF

LevelIntermediate

Duration75 mins

TopicCPU Scheduling

1 / 5

SJF Algorithm

The Intuition Behind Shortest Job First

Imagine you're at a bank with several customers waiting to be served. There's an elderly person who needs a 15-minute financial consultation, a business owner requiring 30 minutes for a loan application review, and a student who simply needs to deposit a check—a task taking just 2 minutes. If customers are served in arrival order (FCFS), and the elderly person arrived first, the student waits 15 minutes for a 2-minute task.

Shortest Job First (SJF) captures an intuitive optimization: serve the shortest task first. This minimizes the cumulative waiting time across all customers. The student gets served immediately, finishes in 2 minutes, and the total system wait time decreases dramatically.

In operating systems, this concept translates directly to CPU scheduling. SJF selects the process with the smallest CPU burst—the process that needs the least CPU time—and schedules it next. This seemingly simple idea has profound implications for system performance and represents one of the most theoretically significant scheduling algorithms ever designed.

What You Will Master

By completing this page, you will understand the formal definition of SJF scheduling, its decision criteria at each scheduling point, implementation data structures, the algorithm's behavior under various workloads, and its fundamental tradeoffs. You'll be equipped to analyze, trace, and compare SJF against other scheduling algorithms.

Formal Definition and Core Principles

Shortest Job First (SJF), also known as Shortest Process Next (SPN) or Shortest Job Next (SJN), is a scheduling algorithm that prioritizes processes based on their expected CPU burst length. At each scheduling decision point, SJF selects the process with the shortest predicted next CPU burst.

Formal Definition

Let P = {p₁, p₂, ..., pₙ} be the set of processes in the ready queue at time t. For each process pᵢ, let τᵢ represent its predicted next CPU burst length. SJF selects:

p = argmin{τᵢ | pᵢ ∈ P}*

The process p* with the minimum predicted burst length is scheduled next.

Key Characteristics

SJF Defining Properties

•Selection Criterion: The process with the smallest next CPU burst is selected from the ready queue
•Non-Preemptive (Basic Form): Once a process begins execution, it runs to completion of its current CPU burst without interruption
•Priority Basis: CPU burst length serves as a dynamic priority—shorter bursts mean higher priority
•Optimal for Average Wait Time: Provably minimizes average waiting time among all non-preemptive algorithms
•Information Requirement: Requires knowledge (or prediction) of future CPU burst lengths—information not directly available at runtime

The Prediction Problem

The core challenge with SJF is that the operating system cannot know the future—it cannot know exactly how long a CPU burst will last before the process actually runs. This makes SJF an "oracle" algorithm in its pure form: theoretically optimal but impractical to implement exactly. Real implementations use predictions based on historical behavior, which we'll explore in a dedicated page.

Comparison with FCFS

Understanding SJF requires contrasting it with First-Come, First-Served (FCFS):

Aspect	FCFS	SJF
Selection Criterion	Arrival time	CPU burst length
Queue Structure	Simple FIFO	Priority queue (by burst length)
Fairness	Fair by arrival order	Unfair to long processes
Average Wait Time	Can be high (convoy effect)	Provably minimal
Implementation	Trivial	Requires burst prediction
Starvation	Impossible	Possible for long processes

SJF trades the simplicity and fairness of FCFS for optimal average waiting time—a tradeoff that profoundly shapes its applicability.

Algorithm Mechanics: Step-by-Step Execution

The non-preemptive SJF algorithm executes through a well-defined sequence of steps at each scheduling decision point.

Scheduling Decision Points

In non-preemptive SJF, scheduling decisions occur only when:

The running process terminates — It has completed its current CPU burst and either exits or blocks for I/O
The running process voluntarily yields — It requests I/O or waits for a resource
No process is currently running — The CPU is idle and processes are waiting

Notably, scheduling decisions do not occur when new processes arrive. Once a process starts running, it continues regardless of whether shorter processes subsequently become ready. This is the fundamental characteristic of non-preemptive scheduling.

sjf_scheduler.c
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
 
#define MAX_PROCESSES 100
 
typedef struct {
    int pid;              // Process ID
    int arrival_time;     // Time process enters ready queue
    int burst_time;       // Total CPU burst time needed
    int remaining_time;   // For tracking (equals burst_time in non-preemptive)
    int start_time;       // When process first gets CPU
    int completion_time;  // When process finishes
    int waiting_time;     // Time spent in ready queue
    int turnaround_time;  // Total time from arrival to completion
    int started;          // Flag: has this process started?
} Process;
 
/**
 * Finds the process with shortest burst time among arrived processes
 * Returns -1 if no process is available
 */
int find_shortest_job(Process procs[], int n, int current_time, int completed[]) {
    int shortest_idx = -1;
    int min_burst = INT_MAX;
    
    for (int i = 0; i < n; i++) {
        // Process must have arrived and not be completed
        if (procs[i].arrival_time <= current_time && !completed[i]) {
            // Select if shorter, or if equal length, prefer earlier arrival
            if (procs[i].burst_time < min_burst ||
                (procs[i].burst_time == min_burst && 
                 (shortest_idx == -1 || 
                  procs[i].arrival_time < procs[shortest_idx].arrival_time))) {
                min_burst = procs[i].burst_time;
                shortest_idx = i;
            }
        }
    }
    return shortest_idx;
}
 
/**
 * Non-preemptive SJF Scheduler
 * Simulates SJF scheduling and computes all metrics
 */
void sjf_schedule(Process procs[], int n) {
    int completed[MAX_PROCESSES] = {0};  // Track completed processes
    int completed_count = 0;
    int current_time = 0;
    
    printf("\nSJF Scheduling Simulation:\n");
    printf("═══════════════════════════════════════════════════════════\n");
    
    while (completed_count < n) {
        // Find the shortest job among arrived, uncompleted processes
        int idx = find_shortest_job(procs, n, current_time, completed);
        
        if (idx == -1) {
            // No process available - fast forward to next arrival
            int next_arrival = INT_MAX;
            for (int i = 0; i < n; i++) {
                if (!completed[i] && procs[i].arrival_time < next_arrival) {
                    next_arrival = procs[i].arrival_time;
                }
            }
            printf("Time %3d: CPU idle (waiting for process arrival)\n", 
                   current_time);
            current_time = next_arrival;
            continue;
        }
        
        // Schedule the selected process
        Process *p = &procs[idx];
        p->start_time = current_time;
        p->completion_time = current_time + p->burst_time;
        p->turnaround_time = p->completion_time - p->arrival_time;
        p->waiting_time = p->turnaround_time - p->burst_time;
        
        printf("Time %3d: P%d starts (burst=%d, arrival=%d)\n",
               current_time, p->pid, p->burst_time, p->arrival_time);
        
        current_time = p->completion_time;
        completed[idx] = 1;
        completed_count++;
        
        printf("Time %3d: P%d completes (wait=%d, turnaround=%d)\n",
               current_time, p->pid, p->waiting_time, p->turnaround_time);
    }
    
    printf("═══════════════════════════════════════════════════════════\n");
}
 
/**
 * Calculate and display average metrics
 */
void print_metrics(Process procs[], int n) {
    float total_wait = 0, total_turnaround = 0;
    
    printf("\n%-5s %-10s %-10s %-10s %-10s %-12s\n",
           "PID", "Arrival", "Burst", "Wait", "Turnaround", "Completion");
    printf("─────────────────────────────────────────────────────────\n");
    
    for (int i = 0; i < n; i++) {
        printf("P%-4d %-10d %-10d %-10d %-10d %-12d\n",
               procs[i].pid, procs[i].arrival_time, procs[i].burst_time,
               procs[i].waiting_time, procs[i].turnaround_time,
               procs[i].completion_time);
        total_wait += procs[i].waiting_time;
        total_turnaround += procs[i].turnaround_time;
    }
    
    printf("─────────────────────────────────────────────────────────\n");
    printf("Average Waiting Time:    %.2f\n", total_wait / n);
    printf("Average Turnaround Time: %.2f\n", total_turnaround / n);
}

Tie-Breaking Strategy

When multiple processes have identical burst times, a tie-breaking rule is needed. Common strategies include: (1) FCFS among ties—earlier arrival wins, (2) Process ID—lower PID wins, or (3) Random selection. The implementation above uses FCFS tie-breaking, which is most common in practice and ensures deterministic behavior.

Worked Example: Tracing SJF Execution

Let's trace through a complete SJF scheduling example to solidify understanding. Consider the following process set:

Process	Arrival Time	CPU Burst
P1	0	8
P2	1	4
P3	2	9
P4	3	5

Step-by-Step Execution

Time 0:

Ready Queue: {P1}
Only P1 has arrived; P1 starts execution (burst = 8)
Decision: Schedule P1

Time 0-8:

P1 runs to completion (non-preemptive)
During this time, P2 (at t=1), P3 (at t=2), and P4 (at t=3) all arrive
They cannot preempt P1—they wait in the ready queue

Time 8:

P1 completes
Ready Queue: {P2, P3, P4}
Burst times: P2=4, P3=9, P4=5
Shortest burst: P2 (4)
Decision: Schedule P2

Time 8-12:

P2 runs to completion

Time 12:

Ready Queue: {P3, P4}
Burst times: P3=9, P4=5
Shortest burst: P4 (5)
Decision: Schedule P4

Time 12-17:

P4 runs to completion

Time 17:

Ready Queue: {P3}
Only P3 remains
Decision: Schedule P3

Time 17-26:

P3 runs to completion
Scheduling complete

Converting Mermaid diagram...

Metrics Calculation

Completion Times:

P1: 8
P2: 12
P3: 26
P4: 17

Turnaround Time = Completion Time - Arrival Time

P1: 8 - 0 = 8
P2: 12 - 1 = 11
P3: 26 - 2 = 24
P4: 17 - 3 = 14

Waiting Time = Turnaround Time - Burst Time

P1: 8 - 8 = 0
P2: 11 - 4 = 7
P3: 24 - 9 = 15
P4: 14 - 5 = 9

Average Waiting Time = (0 + 7 + 15 + 9) / 4 = 7.75

Average Turnaround Time = (8 + 11 + 24 + 14) / 4 = 14.25

Comparison with FCFS

If we had used FCFS on this same process set, the execution order would be P1→P2→P3→P4, with average waiting time of (0 + 7 + 19 + 18) / 4 = 11.0. SJF achieves 7.75—a 29% improvement. This improvement becomes more dramatic with greater variance in burst times.

Data Structure Considerations

Efficient SJF implementation requires careful data structure selection. The core operation is repeatedly finding the minimum element (shortest burst) from a dynamic set—a classic use case for priority queues.

Naive Approach: Unsorted List

The simplest implementation uses an unsorted list:

Insert (process arrival): O(1)—append to end
Find Minimum (scheduling decision): O(n)—scan entire list
Delete (after selection): O(1)—mark as complete

For n processes, this gives O(n²) total scheduling overhead. Acceptable for small n, but problematic at scale.

Optimized Approach: Min-Heap (Priority Queue)

A min-heap provides logarithmic operations:

Insert: O(log n)
Find Minimum: O(1)
Delete Minimum: O(log n)

For n processes, total scheduling overhead is O(n log n)—dramatically better for systems with many processes.

Data Structure Comparison for SJF
Data Structure	Insert	Find Min	Delete Min	Total (n ops)
Unsorted Array	O(1)	O(n)	O(n)	O(n²)
Sorted Array	O(n)	O(1)	O(1)	O(n²)
Binary Heap	O(log n)	O(1)	O(log n)	O(n log n)
Fibonacci Heap	O(1)*	O(1)	O(log n)*	O(n log n)*
Self-Balancing BST	O(log n)	O(log n)	O(log n)	O(n log n)

sjf_priority_queue.c
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
/**
 * Min-Heap based SJF Ready Queue
 * Optimized for efficient minimum extraction
 */
 
#define HEAP_CAPACITY 1024
 
typedef struct {
    int pid;
    int burst_time;
    int arrival_time;
} HeapProcess;
 
typedef struct {
    HeapProcess data[HEAP_CAPACITY];
    int size;
} MinHeap;
 
/**
 * Comparison: returns true if a should come before b
 * Primary: shorter burst. Tie-breaker: earlier arrival.
 */
static inline int compare(HeapProcess *a, HeapProcess *b) {
    if (a->burst_time != b->burst_time)
        return a->burst_time < b->burst_time;
    return a->arrival_time < b->arrival_time;
}
 
/**
 * Bubble up: restore heap property after insertion
 */
void heapify_up(MinHeap *heap, int index) {
    while (index > 0) {
        int parent = (index - 1) / 2;
        if (compare(&heap->data[index], &heap->data[parent])) {
            // Swap with parent
            HeapProcess temp = heap->data[index];
            heap->data[index] = heap->data[parent];
            heap->data[parent] = temp;
            index = parent;
        } else {
            break;
        }
    }
}
 
/**
 * Bubble down: restore heap property after extraction
 */
void heapify_down(MinHeap *heap, int index) {
    while (1) {
        int smallest = index;
        int left = 2 * index + 1;
        int right = 2 * index + 2;
        
        if (left < heap->size && 
            compare(&heap->data[left], &heap->data[smallest])) {
            smallest = left;
        }
        if (right < heap->size && 
            compare(&heap->data[right], &heap->data[smallest])) {
            smallest = right;
        }
        
        if (smallest != index) {
            HeapProcess temp = heap->data[index];
            heap->data[index] = heap->data[smallest];
            heap->data[smallest] = temp;
            index = smallest;
        } else {
            break;
        }
    }
}
 
/**
 * Insert process into ready queue - O(log n)
 */
void heap_insert(MinHeap *heap, int pid, int burst, int arrival) {
    if (heap->size >= HEAP_CAPACITY) {
        fprintf(stderr, "Ready queue overflow\n");
        return;
    }
    
    int index = heap->size++;
    heap->data[index] = (HeapProcess){pid, burst, arrival};
    heapify_up(heap, index);
}
 
/**
 * Get process with shortest burst - O(1)
 */
HeapProcess* heap_peek(MinHeap *heap) {
    if (heap->size == 0) return NULL;
    return &heap->data[0];
}
 
/**
 * Remove and return shortest burst process - O(log n)
 */
HeapProcess heap_extract_min(MinHeap *heap) {
    HeapProcess min = heap->data[0];
    heap->data[0] = heap->data[--heap->size];
    heapify_down(heap, 0);
    return min;
}
 
int heap_empty(MinHeap *heap) {
    return heap->size == 0;
}

Real-World Complexity

Production schedulers face additional complexity: processes may have their predicted burst times updated, requiring decrease-key operations. Priority inversions and aging mechanisms add further overhead. The theoretical O(n log n) can be significantly impacted by these practical considerations.

Behavioral Analysis Under Different Workloads

SJF's performance depends heavily on workload characteristics. Understanding how it behaves under different scenarios is essential for knowing when to apply it.

Uniform Burst Times

When all processes have identical burst times, SJF degenerates to FCFS:

All processes are equally "short"
Tie-breaking (typically FCFS) determines order
No advantage over simpler algorithms

Implication: SJF's benefits require variance in process lengths.

High Variance Workloads

With significant variation in burst times (e.g., short interactive tasks mixed with long batch jobs), SJF shines:

Short processes complete quickly, reducing total wait time
Average waiting time can be dramatically lower than FCFS
System appears more responsive to interactive users

Implication: SJF excels in mixed workload environments.

Continuous Arrival of Short Jobs

If short jobs continuously arrive while a long job waits:

The long job is perpetually deferred
This is the starvation problem—covered in depth in a later page

Implication: SJF requires starvation mitigation in production.

SJF Excels When

•Burst times have high variance
•Many short interactive processes exist
•Average response time is the primary metric
•Burst prediction is reasonably accurate
•Long processes can tolerate delays

SJF Struggles When

•All bursts are similar length
•Burst prediction is unreliable
•Long jobs have deadlines
•Fairness is a hard requirement
•Short jobs arrive continuously

Batch vs Interactive Systems

SJF was originally designed for batch processing systems where job lengths were known (specified by users submitting punch cards). Modern interactive systems make burst prediction far more challenging, but the core principle—favor short tasks—remains influential in schedulers like the Linux CFS, which approximates similar behavior through virtual runtime tracking.

Advantages and Limitations

A comprehensive assessment of SJF requires balancing its theoretical optimality against its practical constraints.

Fundamental Advantages

Why SJF Matters

•Provably Optimal Average Waiting Time — Among all non-preemptive algorithms, SJF minimizes average waiting time. This is a mathematical guarantee, not merely an observation.
•Minimizes Convoy Effect — Unlike FCFS, short processes don't wait behind long ones. System throughput for interactive work improves.
•Reduced Average Turnaround Time — By prioritizing quick completions, SJF maximizes the number of processes finishing early.
•Theoretical Foundation — SJF provides the benchmark against which other algorithms are compared. Understanding it illuminates scheduler design principles.
•Applicable Beyond OS Scheduling — The SJF principle applies to queuing systems, task scheduling in databases, network packet prioritization, and more.

Critical Limitations

Why Pure SJF Isn't Practical

•Requires Future Knowledge — True SJF needs exact CPU burst lengths, which are unknowable until execution completes. Every implementation is an approximation.
•Starvation of Long Processes — Long processes may wait indefinitely if short processes keep arriving. This violates fairness guarantees.
•Prediction Overhead — Maintaining burst predictions adds computational and storage overhead. Inaccurate predictions degrade performance below FCFS.
•Not Real-Time Compatible — SJF provides no deadline guarantees. Real-time systems require different approaches.
•Non-Preemptive Delays — A long process that starts cannot be interrupted, potentially blocking higher-priority arrivals.

The Optimality Paradox

SJF is theoretically optimal yet practically impossible to implement exactly. This paradox drives the field of CPU scheduling research: how do we approximate SJF's optimality while accommodating real-world constraints? SRTF, aging mechanisms, and multi-level feedback queues all represent answers to this question.

Summary: The SJF Foundation

We have established a comprehensive understanding of the Shortest Job First scheduling algorithm. Let's consolidate the essential knowledge:

Key Takeaways

•SJF selects the process with the smallest predicted CPU burst — It's a priority-based algorithm where shorter burst = higher priority
•Non-preemptive SJF runs selected processes to completion — No interruption once a process starts, regardless of new arrivals
•SJF is provably optimal for average waiting time — Among non-preemptive algorithms, no approach achieves lower average wait
•The algorithm requires knowledge of future burst lengths — This fundamental limitation makes pure SJF an "oracle" algorithm
•Efficient implementation uses min-heap priority queues — O(log n) operations versus O(n²) for naive list-based approaches
•SJF excels with high-variance workloads — Benefits diminish when burst times are uniform

Looking Ahead:

The next page provides a rigorous mathematical proof of SJF's optimality. Understanding why SJF minimizes average waiting time—not just that it does—deepens comprehension and builds the analytical foundation for evaluating scheduling algorithms. We'll see that the optimality proof is elegant and illuminates the fundamental principles of algorithmic scheduling theory.

Page Complete

You now understand the mechanics, implementation, and behavioral characteristics of Shortest Job First scheduling. The algorithm's elegant simplicity belies its profound implications—and its limitations drive the evolution of more sophisticated scheduling approaches.

1 / 5

Loading learning content...

Operating SystemsCPU Scheduling

Shortest Job First (SJF) & SRTF

LevelIntermediate

Duration75 mins

TopicCPU Scheduling

1 / 5

SJF Algorithm

The Intuition Behind Shortest Job First

What You Will Master

Formal Definition and Core Principles

Formal Definition

Let P = {p₁, p₂, ..., pₙ} be the set of processes in the ready queue at time t. For each process pᵢ, let τᵢ represent its predicted next CPU burst length. SJF selects:

p = argmin{τᵢ | pᵢ ∈ P}*

The process p* with the minimum predicted burst length is scheduled next.

Key Characteristics

SJF Defining Properties

•Selection Criterion: The process with the smallest next CPU burst is selected from the ready queue
•Non-Preemptive (Basic Form): Once a process begins execution, it runs to completion of its current CPU burst without interruption
•Priority Basis: CPU burst length serves as a dynamic priority—shorter bursts mean higher priority
•Optimal for Average Wait Time: Provably minimizes average waiting time among all non-preemptive algorithms
•Information Requirement: Requires knowledge (or prediction) of future CPU burst lengths—information not directly available at runtime

The Prediction Problem

Comparison with FCFS

Understanding SJF requires contrasting it with First-Come, First-Served (FCFS):

Aspect	FCFS	SJF
Selection Criterion	Arrival time	CPU burst length
Queue Structure	Simple FIFO	Priority queue (by burst length)
Fairness	Fair by arrival order	Unfair to long processes
Average Wait Time	Can be high (convoy effect)	Provably minimal
Implementation	Trivial	Requires burst prediction
Starvation	Impossible	Possible for long processes

SJF trades the simplicity and fairness of FCFS for optimal average waiting time—a tradeoff that profoundly shapes its applicability.

Algorithm Mechanics: Step-by-Step Execution

The non-preemptive SJF algorithm executes through a well-defined sequence of steps at each scheduling decision point.

Scheduling Decision Points

In non-preemptive SJF, scheduling decisions occur only when:

The running process terminates — It has completed its current CPU burst and either exits or blocks for I/O
The running process voluntarily yields — It requests I/O or waits for a resource
No process is currently running — The CPU is idle and processes are waiting

sjf_scheduler.c
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
 
#define MAX_PROCESSES 100
 
typedef struct {
    int pid;              // Process ID
    int arrival_time;     // Time process enters ready queue
    int burst_time;       // Total CPU burst time needed
    int remaining_time;   // For tracking (equals burst_time in non-preemptive)
    int start_time;       // When process first gets CPU
    int completion_time;  // When process finishes
    int waiting_time;     // Time spent in ready queue
    int turnaround_time;  // Total time from arrival to completion
    int started;          // Flag: has this process started?
} Process;
 
/**
 * Finds the process with shortest burst time among arrived processes
 * Returns -1 if no process is available
 */
int find_shortest_job(Process procs[], int n, int current_time, int completed[]) {
    int shortest_idx = -1;
    int min_burst = INT_MAX;
    
    for (int i = 0; i < n; i++) {
        // Process must have arrived and not be completed
        if (procs[i].arrival_time <= current_time && !completed[i]) {
            // Select if shorter, or if equal length, prefer earlier arrival
            if (procs[i].burst_time < min_burst ||
                (procs[i].burst_time == min_burst && 
                 (shortest_idx == -1 || 
                  procs[i].arrival_time < procs[shortest_idx].arrival_time))) {
                min_burst = procs[i].burst_time;
                shortest_idx = i;
            }
        }
    }
    return shortest_idx;
}
 
/**
 * Non-preemptive SJF Scheduler
 * Simulates SJF scheduling and computes all metrics
 */
void sjf_schedule(Process procs[], int n) {
    int completed[MAX_PROCESSES] = {0};  // Track completed processes
    int completed_count = 0;
    int current_time = 0;
    
    printf("\nSJF Scheduling Simulation:\n");
    printf("═══════════════════════════════════════════════════════════\n");
    
    while (completed_count < n) {
        // Find the shortest job among arrived, uncompleted processes
        int idx = find_shortest_job(procs, n, current_time, completed);
        
        if (idx == -1) {
            // No process available - fast forward to next arrival
            int next_arrival = INT_MAX;
            for (int i = 0; i < n; i++) {
                if (!completed[i] && procs[i].arrival_time < next_arrival) {
                    next_arrival = procs[i].arrival_time;
                }
            }
            printf("Time %3d: CPU idle (waiting for process arrival)\n", 
                   current_time);
            current_time = next_arrival;
            continue;
        }
        
        // Schedule the selected process
        Process *p = &procs[idx];
        p->start_time = current_time;
        p->completion_time = current_time + p->burst_time;
        p->turnaround_time = p->completion_time - p->arrival_time;
        p->waiting_time = p->turnaround_time - p->burst_time;
        
        printf("Time %3d: P%d starts (burst=%d, arrival=%d)\n",
               current_time, p->pid, p->burst_time, p->arrival_time);
        
        current_time = p->completion_time;
        completed[idx] = 1;
        completed_count++;
        
        printf("Time %3d: P%d completes (wait=%d, turnaround=%d)\n",
               current_time, p->pid, p->waiting_time, p->turnaround_time);
    }
    
    printf("═══════════════════════════════════════════════════════════\n");
}
 
/**
 * Calculate and display average metrics
 */
void print_metrics(Process procs[], int n) {
    float total_wait = 0, total_turnaround = 0;
    
    printf("\n%-5s %-10s %-10s %-10s %-10s %-12s\n",
           "PID", "Arrival", "Burst", "Wait", "Turnaround", "Completion");
    printf("─────────────────────────────────────────────────────────\n");
    
    for (int i = 0; i < n; i++) {
        printf("P%-4d %-10d %-10d %-10d %-10d %-12d\n",
               procs[i].pid, procs[i].arrival_time, procs[i].burst_time,
               procs[i].waiting_time, procs[i].turnaround_time,
               procs[i].completion_time);
        total_wait += procs[i].waiting_time;
        total_turnaround += procs[i].turnaround_time;
    }
    
    printf("─────────────────────────────────────────────────────────\n");
    printf("Average Waiting Time:    %.2f\n", total_wait / n);
    printf("Average Turnaround Time: %.2f\n", total_turnaround / n);
}

Tie-Breaking Strategy

Worked Example: Tracing SJF Execution

Let's trace through a complete SJF scheduling example to solidify understanding. Consider the following process set:

Process	Arrival Time	CPU Burst
P1	0	8
P2	1	4
P3	2	9
P4	3	5

Step-by-Step Execution

Time 0:

Ready Queue: {P1}
Only P1 has arrived; P1 starts execution (burst = 8)
Decision: Schedule P1

Time 0-8:

P1 runs to completion (non-preemptive)
During this time, P2 (at t=1), P3 (at t=2), and P4 (at t=3) all arrive
They cannot preempt P1—they wait in the ready queue

Time 8:

P1 completes
Ready Queue: {P2, P3, P4}
Burst times: P2=4, P3=9, P4=5
Shortest burst: P2 (4)
Decision: Schedule P2

Time 8-12:

P2 runs to completion

Time 12:

Ready Queue: {P3, P4}
Burst times: P3=9, P4=5
Shortest burst: P4 (5)
Decision: Schedule P4

Time 12-17:

P4 runs to completion

Time 17:

Ready Queue: {P3}
Only P3 remains
Decision: Schedule P3

Time 17-26:

P3 runs to completion
Scheduling complete

Converting Mermaid diagram...

Metrics Calculation

Completion Times:

P1: 8
P2: 12
P3: 26
P4: 17

Turnaround Time = Completion Time - Arrival Time

P1: 8 - 0 = 8
P2: 12 - 1 = 11
P3: 26 - 2 = 24
P4: 17 - 3 = 14

Waiting Time = Turnaround Time - Burst Time

P1: 8 - 8 = 0
P2: 11 - 4 = 7
P3: 24 - 9 = 15
P4: 14 - 5 = 9

Average Waiting Time = (0 + 7 + 15 + 9) / 4 = 7.75

Average Turnaround Time = (8 + 11 + 24 + 14) / 4 = 14.25

Comparison with FCFS

Data Structure Considerations

Naive Approach: Unsorted List

The simplest implementation uses an unsorted list:

Insert (process arrival): O(1)—append to end
Find Minimum (scheduling decision): O(n)—scan entire list
Delete (after selection): O(1)—mark as complete

For n processes, this gives O(n²) total scheduling overhead. Acceptable for small n, but problematic at scale.

Optimized Approach: Min-Heap (Priority Queue)

A min-heap provides logarithmic operations:

Insert: O(log n)
Find Minimum: O(1)
Delete Minimum: O(log n)

For n processes, total scheduling overhead is O(n log n)—dramatically better for systems with many processes.

Data Structure Comparison for SJF
Data Structure	Insert	Find Min	Delete Min	Total (n ops)
Unsorted Array	O(1)	O(n)	O(n)	O(n²)
Sorted Array	O(n)	O(1)	O(1)	O(n²)
Binary Heap	O(log n)	O(1)	O(log n)	O(n log n)
Fibonacci Heap	O(1)*	O(1)	O(log n)*	O(n log n)*
Self-Balancing BST	O(log n)	O(log n)	O(log n)	O(n log n)

sjf_priority_queue.c
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
/**
 * Min-Heap based SJF Ready Queue
 * Optimized for efficient minimum extraction
 */
 
#define HEAP_CAPACITY 1024
 
typedef struct {
    int pid;
    int burst_time;
    int arrival_time;
} HeapProcess;
 
typedef struct {
    HeapProcess data[HEAP_CAPACITY];
    int size;
} MinHeap;
 
/**
 * Comparison: returns true if a should come before b
 * Primary: shorter burst. Tie-breaker: earlier arrival.
 */
static inline int compare(HeapProcess *a, HeapProcess *b) {
    if (a->burst_time != b->burst_time)
        return a->burst_time < b->burst_time;
    return a->arrival_time < b->arrival_time;
}
 
/**
 * Bubble up: restore heap property after insertion
 */
void heapify_up(MinHeap *heap, int index) {
    while (index > 0) {
        int parent = (index - 1) / 2;
        if (compare(&heap->data[index], &heap->data[parent])) {
            // Swap with parent
            HeapProcess temp = heap->data[index];
            heap->data[index] = heap->data[parent];
            heap->data[parent] = temp;
            index = parent;
        } else {
            break;
        }
    }
}
 
/**
 * Bubble down: restore heap property after extraction
 */
void heapify_down(MinHeap *heap, int index) {
    while (1) {
        int smallest = index;
        int left = 2 * index + 1;
        int right = 2 * index + 2;
        
        if (left < heap->size && 
            compare(&heap->data[left], &heap->data[smallest])) {
            smallest = left;
        }
        if (right < heap->size && 
            compare(&heap->data[right], &heap->data[smallest])) {
            smallest = right;
        }
        
        if (smallest != index) {
            HeapProcess temp = heap->data[index];
            heap->data[index] = heap->data[smallest];
            heap->data[smallest] = temp;
            index = smallest;
        } else {
            break;
        }
    }
}
 
/**
 * Insert process into ready queue - O(log n)
 */
void heap_insert(MinHeap *heap, int pid, int burst, int arrival) {
    if (heap->size >= HEAP_CAPACITY) {
        fprintf(stderr, "Ready queue overflow\n");
        return;
    }
    
    int index = heap->size++;
    heap->data[index] = (HeapProcess){pid, burst, arrival};
    heapify_up(heap, index);
}
 
/**
 * Get process with shortest burst - O(1)
 */
HeapProcess* heap_peek(MinHeap *heap) {
    if (heap->size == 0) return NULL;
    return &heap->data[0];
}
 
/**
 * Remove and return shortest burst process - O(log n)
 */
HeapProcess heap_extract_min(MinHeap *heap) {
    HeapProcess min = heap->data[0];
    heap->data[0] = heap->data[--heap->size];
    heapify_down(heap, 0);
    return min;
}
 
int heap_empty(MinHeap *heap) {
    return heap->size == 0;
}

Real-World Complexity

Behavioral Analysis Under Different Workloads

SJF's performance depends heavily on workload characteristics. Understanding how it behaves under different scenarios is essential for knowing when to apply it.

Uniform Burst Times

When all processes have identical burst times, SJF degenerates to FCFS:

All processes are equally "short"
Tie-breaking (typically FCFS) determines order
No advantage over simpler algorithms

Implication: SJF's benefits require variance in process lengths.

High Variance Workloads

With significant variation in burst times (e.g., short interactive tasks mixed with long batch jobs), SJF shines:

Short processes complete quickly, reducing total wait time
Average waiting time can be dramatically lower than FCFS
System appears more responsive to interactive users

Implication: SJF excels in mixed workload environments.

Continuous Arrival of Short Jobs

If short jobs continuously arrive while a long job waits:

The long job is perpetually deferred
This is the starvation problem—covered in depth in a later page

Implication: SJF requires starvation mitigation in production.

SJF Excels When

•Burst times have high variance
•Many short interactive processes exist
•Average response time is the primary metric
•Burst prediction is reasonably accurate
•Long processes can tolerate delays

SJF Struggles When

•All bursts are similar length
•Burst prediction is unreliable
•Long jobs have deadlines
•Fairness is a hard requirement
•Short jobs arrive continuously

Batch vs Interactive Systems

Advantages and Limitations

A comprehensive assessment of SJF requires balancing its theoretical optimality against its practical constraints.

Fundamental Advantages

Why SJF Matters

•Provably Optimal Average Waiting Time — Among all non-preemptive algorithms, SJF minimizes average waiting time. This is a mathematical guarantee, not merely an observation.
•Minimizes Convoy Effect — Unlike FCFS, short processes don't wait behind long ones. System throughput for interactive work improves.
•Reduced Average Turnaround Time — By prioritizing quick completions, SJF maximizes the number of processes finishing early.
•Theoretical Foundation — SJF provides the benchmark against which other algorithms are compared. Understanding it illuminates scheduler design principles.
•Applicable Beyond OS Scheduling — The SJF principle applies to queuing systems, task scheduling in databases, network packet prioritization, and more.

Critical Limitations

Why Pure SJF Isn't Practical

•Requires Future Knowledge — True SJF needs exact CPU burst lengths, which are unknowable until execution completes. Every implementation is an approximation.
•Starvation of Long Processes — Long processes may wait indefinitely if short processes keep arriving. This violates fairness guarantees.
•Prediction Overhead — Maintaining burst predictions adds computational and storage overhead. Inaccurate predictions degrade performance below FCFS.
•Not Real-Time Compatible — SJF provides no deadline guarantees. Real-time systems require different approaches.
•Non-Preemptive Delays — A long process that starts cannot be interrupted, potentially blocking higher-priority arrivals.

The Optimality Paradox

Summary: The SJF Foundation

We have established a comprehensive understanding of the Shortest Job First scheduling algorithm. Let's consolidate the essential knowledge:

Key Takeaways

•SJF selects the process with the smallest predicted CPU burst — It's a priority-based algorithm where shorter burst = higher priority
•Non-preemptive SJF runs selected processes to completion — No interruption once a process starts, regardless of new arrivals
•SJF is provably optimal for average waiting time — Among non-preemptive algorithms, no approach achieves lower average wait
•The algorithm requires knowledge of future burst lengths — This fundamental limitation makes pure SJF an "oracle" algorithm
•Efficient implementation uses min-heap priority queues — O(log n) operations versus O(n²) for naive list-based approaches
•SJF excels with high-variance workloads — Benefits diminish when burst times are uniform

Looking Ahead:

Page Complete

1 / 5