🕐 CPU Scheduling Algorithms

FCFS
SJF
Priority
Round Robin
Visualize Algorithms
1

First Come First Serve (FCFS)

Theory

First Come First Serve (FCFS) is the simplest CPU scheduling algorithm. In this scheme:

  • Processes are executed strictly in the order they arrive in the ready queue
  • It is non-preemptive - once a process starts executing, it continues until it completes or blocks
  • Implementation uses a FIFO (First In, First Out) queue
  • Simple to understand and implement but not optimal for performance

Example

Process Arrival Time Burst Time
P1 0 4
P2 1 3
P3 2 1

Gantt Chart

P1 0 4
P2 7
P3 8

Results:

  • Waiting Time: P1 = 0, P2 = 3, P3 = 5
  • Average Waiting Time: (0 + 3 + 5) / 3 = 2.67 time units
  • Turnaround Time: P1 = 4, P2 = 6, P3 = 6
  • Average Turnaround Time: (4 + 6 + 6) / 3 = 5.33 time units

Advantages

  • Simple to understand and implement
  • No starvation - every process gets CPU time
  • Fair for FIFO environment
  • Good for batch systems where run time is important

Disadvantages

  • Poor average waiting time
  • Not suitable for interactive systems
  • Suffers from "convoy effect" - short processes wait for long ones
  • No priority consideration
2

Shortest Job First (SJF)

Theory

Shortest Job First (SJF) selects the process with the smallest CPU burst time. It comes in two variants:

  • Non-preemptive: Once a process begins execution, it runs until completion
  • Preemptive (SRTF): If a new process arrives with a shorter burst time, the current process is preempted
  • Provably optimal for minimizing average waiting time
  • Main challenge: predicting the burst time of processes

Example (Non-preemptive SJF)

Process Arrival Time Burst Time
P1 0 6
P2 1 2
P3 2 8
P4 3 3

Gantt Chart

P1 0 6
P2 8
P4 11
P3 19

Results:

  • Waiting Time: P1 = 0, P2 = 5, P3 = 11, P4 = 5
  • Average Waiting Time: (0 + 5 + 11 + 5) / 4 = 5.25 time units

Advantages

  • Optimal average waiting time
  • Good for systems with known job lengths
  • Reduces average response time
  • Better performance than FCFS

Disadvantages

  • Difficult to predict burst times accurately
  • May cause starvation for longer processes
  • Not implementable in interactive systems easily
  • Overhead in calculating remaining time in preemptive version
3

Priority Scheduling

Theory

Priority Scheduling assigns a priority value to each process and the CPU is allocated based on priority:

  • Lower priority number typically indicates higher priority
  • Can be either preemptive or non-preemptive
  • Priority can be determined based on memory requirements, time constraints, or other factors
  • Often uses a priority queue data structure for implementation

Example (Non-preemptive Priority)

Process Arrival Time Burst Time Priority (lower = higher)
P1 0 5 2
P2 1 3 1
P3 2 8 3

Gantt Chart

P1 0 5
P2 8
P3 16

Results:

  • Waiting Time: P1 = 0, P2 = 4, P3 = 8
  • Average Waiting Time: (0 + 4 + 8) / 3 = 4 time units

Advantages

  • Flexible - priority can reflect business or system requirements
  • Allows important processes to run first
  • Good for real-time systems with deadline requirements
  • Can be combined with other algorithms for better performance

Disadvantages

  • Prone to starvation for low-priority processes
  • Possibility of priority inversion problem
  • May need aging mechanism to prevent starvation
  • Overhead in maintaining priority information
4

Round Robin (RR)

Theory

Round Robin is designed specifically for time-sharing systems. The key characteristics include:

  • Each process gets CPU time in fixed time slices called time quantum (q)
  • Always preemptive - process is preempted if it exceeds the time quantum
  • Ready queue is treated as a circular queue
  • Processes that don't complete within the time quantum are placed at the end of the queue
  • Time quantum selection is critical - too small causes excessive context switching, too large approaches FCFS

Example (Time Quantum = 2)

Process Arrival Time Burst Time
P1 0 5
P2 1 3
P3 2 1

Gantt Chart

P1 0 2
P2 4
P3 5
P1 7
P2 8
P1 9

Results:

  • Waiting Time: P1 = 4, P2 = 4, P3 = 2
  • Average Waiting Time: (4 + 4 + 2) / 3 = 3.33 time units
  • Turnaround Time: P1 = 9, P2 = 7, P3 = 3
  • Average Turnaround Time: (9 + 7 + 3) / 3 = 6.33 time units

Advantages

  • Fair allocation of CPU time
  • No starvation - every process gets a chance
  • Good response time for short processes
  • Ideal for time-sharing environments
  • Better for interactive systems than FCFS

Disadvantages

  • Higher average waiting time than SJF
  • Performance heavily depends on time quantum selection
  • Context switching overhead if time quantum is too small
  • Treats all processes equally regardless of priority or importance
Visualize Algorithms