CPU Scheduling
Learn how each algorithm works and when to use it.
Overview
CPU scheduling decides which process runs next when the CPU is free. Different algorithms optimize for fairness, throughput, response time, or priority. This guide covers the algorithms available in the Team 404 simulator.
Key formulas
TAT = CT − AT | WT = TAT − BT | (Turnaround = Completion − Arrival; Waiting = TAT − Burst)
FCFS — First Come First Serve
Processes are executed in the order they arrive. The first process to arrive is the first to get the CPU. Simple and fair in order, but can cause the "convoy effect": one long process at the front makes everyone else wait.
Pros
- • Simple to implement
- • No starvation
- • Predictable order
Cons
- • Convoy effect
- • Poor average waiting time
- • No priority
Round Robin
Each process gets a fixed time slice (quantum). When the quantum expires, the process is preempted and moved to the back of the ready queue. Fair and good for time-sharing; tuning the quantum is critical.
Pros
- • Fair
- • Good response time
- • No starvation
Cons
- • Context switch overhead
- • Quantum choice matters
SJF — Shortest Job First
The process with the smallest burst time runs next. Minimizes average waiting time but requires knowing (or estimating) burst times. Long jobs can starve if short jobs keep arriving.
Pros
- • Optimal average waiting time (non-preemptive)
- • Efficient
Cons
- • Starvation of long jobs
- • Burst time must be known
SRTF — Shortest Remaining Time First
Preemptive version of SJF. At any time, the process with the smallest remaining burst time runs. If a new process arrives with a shorter remaining time, it preempts the current process.
Pros
- • Optimal average waiting time
- • Responsive to short jobs
Cons
- • Starvation possible
- • Overhead from preemption
Priority Scheduling
Each process has a priority; lower number often means higher priority. The CPU runs the highest-priority ready process. Can be preemptive (new higher-priority job preempts) or non-preemptive.
Pros
- • Flexible
- • Important jobs first
Cons
- • Starvation of low priority
- • Priority inversion risk
MLQ — Multi-Level Queue
Processes are assigned to fixed priority queues (e.g. System, Interactive, Batch). The scheduler always serves the highest-priority non-empty queue first; within a queue, Round Robin is typically used. Processes never move between queues—assignment is static.
Pros
- • Clear separation of workload types
- • High-priority queues get preference
- • Simple queue assignment
Cons
- • No feedback—long batch jobs can starve
- • Rigid structure
- • Queue assignment must be decided upfront
MLFQ — Multi-Level Feedback Queue
Like MLQ but with feedback: processes can move between queues. A process that uses its time quantum is demoted to a lower-priority queue; processes that wait too long in lower queues can be promoted (aging). Used in many real OSs (e.g. macOS) to balance responsiveness and throughput.
Pros
- • Responsive to short interactive jobs
- • Long batch jobs don't block short ones
- • Aging prevents starvation
Cons
- • Tuning quantums and aging is complex
- • Demotion can hurt I/O-bound jobs
- • Many parameters to configure