Sjf And Srtf - Learning Module

Loading content...

0/227

SRTF (Preemptive SJF)

The Case for Preemption

Consider this scenario: A process with an 8ms CPU burst has just started executing. One millisecond later, a new process arrives with only a 2ms burst. Under non-preemptive SJF, the new process must wait the remaining 7ms for the current process to complete—even though the new process is shorter.

This seems wasteful. The short process is forced to wait behind a longer one, precisely the situation SJF was designed to avoid. The problem is that non-preemptive SJF only considers job lengths at scheduling decision points—when the CPU becomes free. It ignores new arrivals during execution.

Shortest Remaining Time First (SRTF), also called Preemptive SJF or Shortest Remaining Time (SRT), solves this by re-evaluating the schedule whenever a new process arrives. If a newly arrived process has a shorter remaining time than the currently running process, the current process is preempted—suspended mid-execution—and the new process takes over.

This simple enhancement reduces average waiting time even further, at the cost of additional context switches.

What You Will Master

By completing this page, you will understand SRTF's algorithm mechanics, its optimality among all scheduling algorithms, implementation with remaining time tracking, context switch overhead analysis, and the tradeoffs between preemptive and non-preemptive approaches.

Formal Definition and Mechanics

Shortest Remaining Time First (SRTF) extends SJF by considering the remaining burst time rather than the original burst time, and by making scheduling decisions at every process arrival.

Formal Definition

Let R = {p₁, p₂, ..., pₖ} be the set of processes in the ready queue plus the currently running process at time t. For each process pᵢ, let rᵢ(t) represent its remaining CPU burst time at time t. SRTF selects:

p = argmin{rᵢ(t) | pᵢ ∈ R}*

If p* differs from the currently running process, preemption occurs.

Decision Points

Unlike non-preemptive SJF, SRTF makes scheduling decisions:

When a process terminates or blocks — Same as SJF
When a new process arrives — The critical addition

At each arrival, SRTF compares the new process's burst time with the running process's remaining time. If the new process is shorter, preemption occurs.

SJF vs SRTF: Key Differences
Aspect	SJF (Non-Preemptive)	SRTF (Preemptive)
Decision criterion	Original burst time	Remaining burst time
Decision points	Process completion only	Completion + each arrival
Preemption	Never	When shorter process arrives
Context switches	Minimal (n switches for n processes)	Potentially many more
Average wait time	Optimal among non-preemptive	Optimal among ALL algorithms
Implementation complexity	Moderate	Higher (track remaining time)

Remaining Time Tracking

SRTF requires tracking how much CPU time each process has already consumed. When preemption occurs, the scheduler records the time used so far. The remaining time = original burst - time already used. This adds bookkeeping overhead not present in non-preemptive SJF.

Algorithm Mechanics: Step-by-Step

The SRTF algorithm requires an event-driven approach, processing events (arrivals and completions) in chronological order.

High-Level Algorithm

srtf_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
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
 
#define MAX_PROCESSES 100
 
typedef struct {
    int pid;
    int arrival_time;
    int burst_time;
    int remaining_time;      // Key for SRTF: tracks remaining burst
    int start_time;          // First time process gets CPU
    int completion_time;
    int waiting_time;
    int turnaround_time;
    int last_scheduled;      // Last time this process was scheduled (for wait calc)
    int started;             // Has this process ever run?
} Process;
 
/**
 * Find process with shortest REMAINING time among arrived processes
 */
int find_srtf(Process procs[], int n, int current_time, int completed[]) {
    int shortest_idx = -1;
    int min_remaining = INT_MAX;
    
    for (int i = 0; i < n; i++) {
        if (procs[i].arrival_time <= current_time && 
            !completed[i] && 
            procs[i].remaining_time > 0) {
            
            // Tie-breaker: earlier arrival, then lower PID
            if (procs[i].remaining_time < min_remaining ||
                (procs[i].remaining_time == min_remaining && 
                 (shortest_idx == -1 || 
                  procs[i].arrival_time < procs[shortest_idx].arrival_time))) {
                min_remaining = procs[i].remaining_time;
                shortest_idx = i;
            }
        }
    }
    return shortest_idx;
}
 
/**
 * Get next event time (arrival or completion)
 * Returns next significant time point for scheduling decision
 */
int next_event_time(Process procs[], int n, int current_time, 
                    int completed[], int running_idx) {
    int next_time = INT_MAX;
    
    // Check for next arrival
    for (int i = 0; i < n; i++) {
        if (!completed[i] && procs[i].arrival_time > current_time) {
            if (procs[i].arrival_time < next_time) {
                next_time = procs[i].arrival_time;
            }
        }
    }
    
    // Check for completion of running process
    if (running_idx >= 0) {
        int completion = current_time + procs[running_idx].remaining_time;
        if (completion < next_time) {
            next_time = completion;
        }
    }
    
    return next_time;
}
 
/**
 * SRTF Scheduler Simulation (Event-Driven)
 */
void srtf_schedule(Process procs[], int n) {
    // Initialize remaining times
    for (int i = 0; i < n; i++) {
        procs[i].remaining_time = procs[i].burst_time;
        procs[i].started = 0;
        procs[i].waiting_time = 0;
    }
    
    int completed[MAX_PROCESSES] = {0};
    int completed_count = 0;
    int current_time = 0;
    int running = -1;  // Currently running process index
    int prev_running = -1;
    
    printf("\nSRTF Scheduling Simulation:\n");
    printf("═══════════════════════════════════════════════════════════\n");
    
    while (completed_count < n) {
        // Select process with shortest remaining time
        int selected = find_srtf(procs, n, current_time, completed);
        
        if (selected == -1) {
            // CPU idle: advance to next arrival
            int next_arrival = INT_MAX;
            for (int i = 0; i < n; i++) {
                if (!completed[i] && procs[i].arrival_time > current_time) {
                    if (procs[i].arrival_time < next_arrival) {
                        next_arrival = procs[i].arrival_time;
                    }
                }
            }
            printf("Time %3d: CPU idle\n", current_time);
            current_time = next_arrival;
            continue;
        }
        
        // Context switch detection
        if (running != selected) {
            if (running >= 0 && procs[running].remaining_time > 0) {
                printf("Time %3d: P%d preempted (remaining=%d)\n",
                       current_time, procs[running].pid, 
                       procs[running].remaining_time);
            }
            
            if (!procs[selected].started) {
                procs[selected].start_time = current_time;
                procs[selected].started = 1;
            }
            
            printf("Time %3d: P%d starts/resumes (remaining=%d)\n",
                   current_time, procs[selected].pid,
                   procs[selected].remaining_time);
        }
        
        running = selected;
        
        // Find next event (arrival that could preempt, or completion)
        int next_event = next_event_time(procs, n, current_time, completed, running);
        int run_time = next_event - current_time;
        
        // Check if running process completes before next event
        if (procs[running].remaining_time <= run_time) {
            run_time = procs[running].remaining_time;
            current_time += run_time;
            procs[running].remaining_time = 0;
            procs[running].completion_time = current_time;
            procs[running].turnaround_time = current_time - procs[running].arrival_time;
            procs[running].waiting_time = procs[running].turnaround_time - 
                                          procs[running].burst_time;
            
            printf("Time %3d: P%d completes (turnaround=%d, wait=%d)\n",
                   current_time, procs[running].pid,
                   procs[running].turnaround_time, procs[running].waiting_time);
            
            completed[running] = 1;
            completed_count++;
            running = -1;
        } else {
            // Process runs until next event but doesn't complete
            procs[running].remaining_time -= run_time;
            current_time = next_event;
        }
    }
    
    printf("═══════════════════════════════════════════════════════════\n");
}

Event-Driven vs Time-Driven

The code above uses event-driven simulation, jumping between significant events (arrivals, completions). An alternative is time-driven simulation, advancing one time unit at a time. Event-driven is more efficient (O(n²) vs O(T×n) where T is total time), but time-driven is simpler to implement.

Worked Example: Tracing SRTF Execution

Let's trace SRTF on the same process set we used for SJF, highlighting where preemption occurs:

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

Step-by-Step Execution

Time 0:

P1 arrives; only process → P1 starts (remaining = 8)

Time 1:

P2 arrives (burst = 4)
P1 remaining = 7, P2 remaining = 4
P2 < P1 → PREEMPT P1, P2 starts

Time 2:

P3 arrives (burst = 9)
P2 remaining = 3, P3 burst = 9
P2 still shortest → P2 continues

Time 3:

P4 arrives (burst = 5)
P2 remaining = 2, P4 burst = 5
P2 still shortest → P2 continues

Time 5:

P2 completes
Ready: P1 (remaining=7), P3 (remaining=9), P4 (remaining=5)
P4 (5) is shortest → P4 starts

Time 10:

P4 completes
Ready: P1 (remaining=7), P3 (remaining=9)
P1 (7) is shortest → P1 starts

Time 17:

P1 completes
Ready: P3 (remaining=9)
P3 starts

Time 26:

P3 completes
All done

Converting Mermaid diagram...

Metrics Calculation

Completion Times:

P1: 17 (ran 0-1, then 10-17)
P2: 5
P3: 26
P4: 10

Turnaround Time = Completion - Arrival:

P1: 17 - 0 = 17
P2: 5 - 1 = 4
P3: 26 - 2 = 24
P4: 10 - 3 = 7

Waiting Time = Turnaround - Burst:

P1: 17 - 8 = 9
P2: 4 - 4 = 0
P3: 24 - 9 = 15
P4: 7 - 5 = 2

Average Waiting Time = (9 + 0 + 15 + 2) / 4 = 6.5

Comparison with Non-Preemptive SJF

Metric	SJF	SRTF	Improvement
P1 Wait	0	9	Worse (preempted)
P2 Wait	7	0	Much better
P3 Wait	15	15	Same
P4 Wait	9	2	Better
Average	7.75	6.5	16% better

SRTF's Advantage

SRTF reduced average waiting time from 7.75 (SJF) to 6.5—a 16% improvement. P2 especially benefits: instead of waiting 7 time units behind P1, it preempts P1 and completes with zero wait. The cost: P1's wait increased from 0 to 9 due to being preempted.

SRTF Optimality: The Best Possible

SRTF has a remarkable property: it minimizes average waiting time among ALL scheduling algorithms—preemptive or non-preemptive. This is a stronger result than SJF's non-preemptive optimality.

Theorem

SRTF achieves the minimum possible average waiting time for any set of processes with known arrival times and burst lengths.

Proof Sketch (Exchange Argument)

The proof extends the SJF exchange argument:

Consider any schedule S that differs from SRTF
At some point, S must have a process running when a shorter-remaining-time process is ready
Swapping execution to the shorter process reduces waiting time for the shorter process without increasing it for the longer
Repeat until all such "inversions" are fixed
The result is the SRTF schedule

Since every non-SRTF schedule can be transformed to SRTF with decreased total waiting time, SRTF is optimal.

Why Preemption Helps

Non-preemptive SJF can make suboptimal decisions because:

It can't react to new arrivals
A long process that starts "traps" the CPU until completion

SRTF avoids this by continuously asking: "Is there a process that would complete sooner than the current one?" Preemption ensures the answer is always "no"—the running process always has the shortest remaining time.

The Clairvoyance Requirement

Like SJF, SRTF's optimality assumes known burst times. With predictions instead of exact values, SRTF is an approximation. But it's the best approximation possible—if our predictions are perfect, SRTF is optimal; if predictions have errors, no other algorithm can do systematically better.

Optimality Comparison
Algorithm	Optimality Claim	Conditions
FCFS	None (often worst)	—
SJF (non-preemptive)	Optimal among non-preemptive	Known burst times
SRTF (preemptive SJF)	Optimal among ALL algorithms	Known burst times + arrival times
Round Robin	Good for response time, not wait time	—
Priority	No wait time guarantee	—

The Context Switch Overhead Problem

SRTF's improved average waiting time comes at a cost: more context switches. Each preemption requires saving the current process's state and loading the new process's state—a non-trivial overhead.

Context Switch Costs

A typical context switch involves:

Operation	Typical Cost
Save registers	~100-500 cycles
Save FPU/SIMD state	~500-2000 cycles
Update PCB	~100-200 cycles
TLB flush (partial)	1000-10000 cycles
Cache disruption	Variable (huge)
Total direct cost	~5,000-50,000 cycles (2-20µs)

Indirect Costs: Cache Pollution

The direct cost underestimates the true impact. After a context switch:

L1/L2 cache contains the preempted process's data
The new process must reload its working set
Multiple cache misses occur (100+ cycles each)
Effective cost can exceed direct cost by 10x

When Preemption Hurts

Consider: P1 has 10ms remaining, P2 arrives with 9ms burst.

SRTF behavior: Preempt P1, run P2 Context switches: 1 preemption + 1 return to P1 = 2 extra switches

If each switch costs 20µs:

Overhead: 40µs
Benefit: P2 waits 0 instead of 10ms = 10ms saved
Net benefit: ~10ms - 40µs ≈ 10ms (worthwhile)

But if P1 has 50µs remaining and P2 has 40µs burst:

Overhead: 40µs (two switches)
Benefit: P2 waits 0 instead of 50µs = 50µs saved
Net benefit: 50µs - 40µs = 10µs (marginal)

The overhead becomes significant when differences are small.

Thrashing Risk

If many processes have similar burst times and arrivals are frequent, SRTF can thrash—constantly preempting before making progress. The scheduler spends more time context-switching than running processes. This is why pure SRTF is rarely used in practice.

Mitigating Context Switch Overhead

Real systems use several techniques:

1. Minimum Granularity

Only preempt if the difference exceeds a threshold:

if (new_remaining < current_remaining - THRESHOLD)
    preempt();

Typical threshold: 1-5ms

2. Quantum-Based Preemption

Check for preemption only at quantum boundaries, not every arrival. Reduces switch frequency while maintaining approximate SRTF behavior.

3. Hysteresis

Require the improvement to be sustained:

if (new_remaining < current_remaining for 3 consecutive checks)
    preempt();

Prevents thrashing on noisy burst estimates.

Implementation Details

Implementing SRTF requires additional bookkeeping beyond SJF.

Tracking Remaining Time

For each process, maintain:

remaining_time: Updated whenever process stops running
last_scheduled: When process last got the CPU

When preemption occurs at time t:

running->remaining_time -= (t - running->last_scheduled);
new_process->last_scheduled = t;

Data Structure: Dynamic Priority Queue

The ready queue must support:

Insert — When process arrives
Find minimum — Identify shortest remaining time
Update key — When remaining time changes (for running process)
Delete minimum — When selecting next process

A min-heap with decrease-key is ideal:

Insert: O(log n)
Find min: O(1)
Update: O(log n)
Delete min: O(log n)

srtf_implementation.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
/**
 * SRTF Scheduler - Key Implementation Components
 */
 
typedef struct {
    int pid;
    int remaining_time;
    int arrival_time;
    // ... other fields
} Process;
 
// Min-heap keyed by remaining_time
typedef struct {
    Process* processes[MAX_PROCESSES];
    int heap_position[MAX_PROCESSES]; // PID -> heap index (for decrease-key)
    int size;
} SRTFReadyQueue;
 
/**
 * Called when a new process arrives
 * May trigger preemption if new process is shorter
 */
void on_process_arrival(SRTFReadyQueue* queue, Process* new_proc, 
                        Process** running, int current_time) {
    
    // Update remaining time of currently running process
    if (*running != NULL) {
        (*running)->remaining_time -= (current_time - (*running)->last_scheduled);
    }
    
    // Check if preemption needed
    if (*running == NULL || 
        new_proc->remaining_time < (*running)->remaining_time) {
        
        // Preempt current process
        if (*running != NULL) {
            (*running)->state = READY;
            heap_insert(queue, *running);
            context_switches++;  // Track overhead
        }
        
        // Schedule new process
        *running = new_proc;
        (*running)->state = RUNNING;
        (*running)->last_scheduled = current_time;
        
        if (!(*running)->started) {
            (*running)->start_time = current_time;
            (*running)->started = 1;
        }
    } else {
        // New process waits; add to queue
        heap_insert(queue, new_proc);
    }
}
 
/**
 * Called when running process completes or blocks
 */
void on_process_yield(SRTFReadyQueue* queue, Process** running, 
                      int current_time) {
    
    // Record completion metrics
    (*running)->completion_time = current_time;
    (*running)->turnaround_time = current_time - (*running)->arrival_time;
    (*running)->state = TERMINATED;  // or BLOCKED
    
    // Select next process
    if (queue->size > 0) {
        *running = heap_extract_min(queue);
        (*running)->state = RUNNING;
        (*running)->last_scheduled = current_time;
        context_switches++;
    } else {
        *running = NULL;  // CPU idle
    }
}
 
/**
 * Preemption threshold check (practical optimization)
 */
#define PREEMPTION_THRESHOLD_MS 2  // Only preempt if >2ms difference
 
int should_preempt(Process* running, Process* new_proc) {
    if (running == NULL) return 1;
    
    int difference = running->remaining_time - new_proc->remaining_time;
    return difference > PREEMPTION_THRESHOLD_MS;
}

Implementation Optimization

Production schedulers often approximate SRTF rather than implementing it exactly. Linux CFS, for example, doesn't use explicit burst prediction but achieves similar effects by tracking actual CPU time consumption and favoring processes that have used less CPU recently.

SRTF vs SJF: When to Choose Each

Both algorithms optimize for short jobs, but they suit different scenarios.

When to Use SJF (Non-Preemptive)

SJF is Preferred When

•Batch processing environments — Jobs run to completion without interruption
•High context switch costs — Systems where preemption is expensive
•Predictable arrival patterns — Processes arrive in batches, not continuously
•Simple implementation required — Less bookkeeping than SRTF
•Process progress must be guaranteed — No risk of indefinite preemption

When to Use SRTF (Preemptive)

SRTF is Preferred When

•Interactive systems — Response time matters; short tasks should not wait
•Variable arrival patterns — Processes arrive unpredictably, potentially during long jobs
•Low context switch costs — Modern processors with efficient state save/restore
•Minimizing average wait is critical — SRTF achieves the theoretical minimum
•High variance in burst times — Short processes frequently arrive during long ones

Head-to-Head Comparison
Criterion	Winner	Margin
Average waiting time	SRTF	5-20% typically
Context switch count	SJF	Often 2-3x fewer
Implementation complexity	SJF	Significantly simpler
Response time (interactive)	SRTF	Much better
Throughput (batch)	Comparable	Depends on workload
Predictability	SJF	No mid-job interruption
Starvation risk	Both suffer	See next page

Modern Systems

Most modern general-purpose operating systems use neither pure SJF nor SRTF. Instead, they use multi-level feedback queues (MLFQ) or fair schedulers (CFS) that approximate the benefits of shortest-job-first while providing better fairness and avoiding starvation.

Practical Considerations

Combining SRTF with Burst Prediction

SRTF needs remaining time, which means:

For a fresh process: remaining = predicted burst
For a preempted process: remaining = predicted burst - time already used

Prediction errors compound in SRTF because we may preempt based on wrong predictions, then preempt again when predictions are revised.

Real-World Approximations

Linux CFS (Completely Fair Scheduler):

Doesn't predict bursts explicitly
Tracks "virtual runtime" (vruntime) for each process
Favors processes with less accumulated vruntime
Achieves SRTF-like behavior for interactive processes

Windows Scheduler:

Uses priority boost for interactive processes
Processes that complete I/O quickly get priority boost
Implicitly favors short-burst processes

SRTF in Specialized Systems

SRTF (or close approximations) is still used in:

Real-time systems — With known execution times
Network packet scheduling — Shortest packet first
Database query scheduling — Shortest query estimated time first
Web server request handling — Small requests prioritized

Key Insight

The principle behind SRTF—favor the task that will complete soonest—appears throughout computing wherever queuing occurs. Understanding SRTF's tradeoffs helps in designing efficient systems beyond just OS scheduling.

Summary: The Power and Cost of Preemption

We have thoroughly examined SRTF, understanding both its theoretical optimality and practical limitations.

Key Takeaways

•SRTF preempts when a shorter process arrives — It continuously ensures the process with least remaining time runs
•SRTF achieves optimal average waiting time — Among ALL scheduling algorithms, not just non-preemptive ones
•Preemption incurs context switch overhead — Direct costs (state save/restore) plus indirect costs (cache pollution)
•Practical implementations use thresholds — Only preempt when the improvement exceeds overhead costs
•SRTF excels for interactive systems — Short tasks get immediate attention, improving responsiveness
•Modern schedulers approximate SRTF — CFS and similar algorithms achieve similar benefits with better fairness

Looking Ahead:

Both SJF and SRTF share a critical weakness: they can cause starvation of long processes. If short processes continually arrive, long processes may wait indefinitely. The next page explores the starvation problem in depth, understanding its causes, detecting when it occurs, and learning prevention techniques like aging.

Page Complete

You now understand SRTF's mechanics, optimality, and tradeoffs. The algorithm represents the theoretical best for average waiting time, but practical constraints—especially context switch overhead and the starvation problem—limit its direct application. Real schedulers draw inspiration from SRTF while addressing its weaknesses.