Scheduling Algorithm Comparison

Introduction

Now that you have studied individual scheduling algorithms, a natural question arises: which one should you use? The answer, as with most things in computer science, is "it depends." Each algorithm excels in specific scenarios and fails in others. A batch processing server needs different scheduling than an interactive desktop, which needs different scheduling than a real-time embedded system.

This page provides a comprehensive comparison of all major CPU scheduling algorithms, helping you understand when to use each one, their tradeoffs, and how modern operating systems combine them.

Head-to-Head Comparison Table

Performance Analysis with Same Dataset

Let us compare all algorithms using identical processes:

FCFS Result

SJF (Non-Preemptive) Result

SJF (Preemptive / SRTF) Result

Round Robin (quantum = 3) Result

Key Insight: No Universal Winner

From the analysis above:

• SRTF gives best average waiting time (2.75ms) — optimal
• Round Robin gives best response time (3.0ms) — most interactive
• FCFS gives worst performance (7.0ms waiting) — but simplest

The right choice depends on your system goals.

When to Use Each Algorithm

FCFS — Use When:

• Batch processing systems (no user waiting at terminal)
• All processes have similar burst times
• Simplicity is more important than performance
• Example: Print queue, nightly backup jobs

SJF — Use When:

• Burst times are known or predictable
• Minimizing average waiting time is the primary goal
• Starvation of long jobs is acceptable
• Example: Job shop scheduling with known processing times

Priority Scheduling — Use When:

• Different processes have genuinely different importance levels
• Real-time systems with hard deadlines
• System processes must always preempt user processes
• Example: Hospital patient scheduling, military systems

Round Robin — Use When:

• Interactive/time-sharing systems
• Fairness is the primary concern
• Response time matters more than throughput
• Example: Desktop OS serving multiple users, web servers

MLFQ — Use When:

• Mix of interactive and batch processes
• Process behavior is unknown in advance
• Need both good response time and good throughput
• Example: General-purpose operating systems (Windows, Linux, macOS)

How Modern OS Combine Algorithms

Real operating systems never use a single algorithm in isolation. They combine multiple approaches:

Linux CFS

Linux's CFS does not use traditional queues. Instead, it assigns each process a virtual runtime that increases as it runs. The process with the lowest virtual runtime runs next. High-priority (low-nice) processes accumulate virtual runtime more slowly, so they run more often. This elegant approach combines fairness with priority support.

Windows Scheduler

Windows uses 32 priority levels with Round Robin within each level. It dynamically boosts priorities for GUI interaction, I/O completion, and starvation prevention. This is essentially a sophisticated MLFQ.

Exam Tips

When asked to compare algorithms in an exam:

1. Always calculate actual numbers for the given dataset
2. State which metric you are optimizing for
3. Mention the tradeoffs (starvation, overhead, predictability)
4. For "which algorithm should you use" questions, ask what the system requirements are

Key Takeaways

• No single scheduling algorithm is best for all scenarios — selection depends on system goals
• SRTF is provably optimal for average waiting time but impractical (needs future knowledge)
• Round Robin excels at response time and fairness for interactive systems
• MLFQ adaptively approximates optimal behavior without advance knowledge
• Modern OS combine multiple algorithms in a multilevel structure
• The fundamental tradeoff is between throughput (favor long uninterrupted runs) and response time (favor frequent short runs)
• Real systems also consider power consumption, cache efficiency, and NUMA topology in scheduling decisions