Shortest Job First (SJF)
Schedules process with shortest burst time first. Minimizes average waiting time (optimal).
Visualization
Interactive visualization for Shortest Job First (SJF)
SJF Scheduling:
- • Shortest Job First
- • Minimizes avg waiting time
Interactive visualization with step-by-step execution
Implementation
1function sjfScheduling(processes: {id: number; arrivalTime: number; burstTime: number}[]): {avgWaitTime: number} {
2 processes.sort((a, b) => a.arrivalTime - b.arrivalTime || a.burstTime - b.burstTime);
3 const completed: boolean[] = Array(processes.length).fill(false);
4 let currentTime = 0, totalWait = 0, done = 0;
5
6 while (done < processes.length) {
7 let idx = -1, minBurst = Infinity;
8 for (let i = 0; i < processes.length; i++) {
9 if (!completed[i] && processes[i].arrivalTime <= currentTime && processes[i].burstTime < minBurst) {
10 minBurst = processes[i].burstTime;
11 idx = i;
12 }
13 }
14 if (idx === -1) {
15 currentTime++;
16 continue;
17 }
18 const waitTime = currentTime - processes[idx].arrivalTime;
19 totalWait += waitTime;
20 currentTime += processes[idx].burstTime;
21 completed[idx] = true;
22 done++;
23 }
24
25 return {avgWaitTime: totalWait / processes.length};
26}Deep Dive
Theoretical Foundation
Select process with minimum burst time from ready queue. Provably optimal for minimizing average waiting time. Can be preemptive (SRTF) or non-preemptive. Requires knowing burst times in advance.
Complexity
Time
O(n²)
O(n²)
O(n²)
Space
O(n)
Applications
Industry Use
Batch job scheduling in high-performance computing
Background task scheduling with known execution times
Job shop scheduling in manufacturing
Database query optimization
Compiler optimization for instruction scheduling
Network packet scheduling with size-based priorities
Use Cases
Related Algorithms
First Come First Serve (FCFS)
Non-preemptive scheduling executing processes in arrival order. Simple queue-based scheduling algorithm that serves as the foundation for understanding CPU scheduling. Despite its simplicity, FCFS can suffer from the convoy effect where short processes are delayed by long-running processes ahead of them in the queue.
Round Robin Scheduling
Preemptive scheduling with fixed time quantum. Each process gets equal CPU time slices.
Priority Scheduling
Schedules processes based on priority. Higher priority executes first. Can be preemptive or non-preemptive.
Quicksort
A highly efficient, in-place sorting algorithm that uses divide-and-conquer strategy. Invented by Tony Hoare in 1959, it remains one of the most widely used sorting algorithms due to its excellent average-case performance and cache efficiency.