Gaurav’s Notes

Scheduling Algorithm

3 min read

⚙️ 1. FCFS — First Come First Serve

🔹 Simple queue: the first process that arrives gets the CPU first

🔁 Working:

  • Non-preemptive

  • Like a ticket line: whoever comes first, gets served first

🧠 Pros:

  • Very simple

  • No starvation

⚠️ Cons:

  • Poor average waiting time

  • Long jobs block short ones (Convoy Effect)

🔧 Use Case:

  • Batch systems with uniform-length jobs

  • Not used in real-time or interactive systems

⚙️ 2. SJF — Shortest Job First

🔹 Run the process with the shortest CPU burst time next

🔁 Working:

  • Can be preemptive (SRTF) or non-preemptive

  • Requires burst time prediction

🧠 Pros:

  • Optimal average waiting time

⚠️ Cons:

  • Starvation of long processes

  • Needs burst-time estimation (hard in practice)

🔧 Use Case:

  • Good in batch processing systems

  • Not widely used in real-world OS kernels due to unpredictability

⚙️ 3. Priority-Based Scheduling

🔹 Each process is assigned a priority, and the CPU is given to the highest-priority process

🔁 Working:

  • Can be preemptive or non-preemptive

🧠 Pros:

  • Good for real-time systems

  • Supports importance-based scheduling

⚠️ Cons:

  • Starvation of low-priority tasks

  • Needs aging to prevent starvation

🔧 Use Case:

  • Real-time OS, embedded systems

  • Kernel-level tasks (e.g., interrupt handling)

⚙️ 4. Round-Robin (RR)

🔹 Every process gets the CPU for a fixed time quantum, then goes to the end of the queue

🔁 Working:

  • Fully preemptive

  • Fair — no process hogs the CPU

🧠 Pros:

  • Responsive, especially for interactive systems

⚠️ Cons:

  • Too small quantum → too many context switches

  • Too large quantum → behaves like FCFS

🔧 Use Case:

  • Time-sharing and interactive systems (e.g., user desktops)

  • Used in early versions of Unix

⚙️ 5. MLQS — Multi-Level Queue Scheduling

🔹 Multiple separate queues for processes (e.g., foreground, background), each with its own scheduling algorithm

🔁 Working:

  • Processes stay in their queue permanently

  • Priority between queues is fixed

🧠 Pros:

  • Separates system tasks vs user tasks

  • Supports different service needs

⚠️ Cons:

  • Rigid — no movement between queues

  • Lower queues can starve

🔧 Use Case:

  • Used in older Windows and RTOS designs

  • Still used in safety-critical embedded systems

⚙️ 6. MLFQS — Multilevel Feedback Queue Scheduling

🔹 Like MLQS, but processes can move between queues based on behavior (feedback)

🔁 Working:

  • Interactive processes promoted

  • CPU-hogs demoted

  • Priorities are dynamic

🧠 Pros:

  • Balances interactivity and throughput

  • Adaptable, fair, responsive

⚠️ Cons:

  • Complex to tune

  • Needs historical data for decision-making

🔧 Use Case:

  • Modern desktop OSes

    • ✅ Windows (uses feedback-based queueing)

    • ✅ Linux (used to use O(1) scheduler with MLFQ model)

    • ✅ macOS (XNU kernel uses priority bands)

🧠 So… Which is Used in the Real World?

OSScheduler
🐧 LinuxCFS (Completely Fair Scheduler) — balances fairness and latency using red-black trees
🪟 WindowsHybrid priority-based preemptive with dynamic aging + feedback
🍏 macOSPriority + multilevel feedback, similar to BSD
⏱️ RTOS (Real-Time)Priority-based preemptive with strict deadlines (e.g., FreeRTOS, VxWorks)

🔍 TL;DR: Modern OSes use variations of MLFQ or hybrid schedulers inspired by it, but not in textbook form.

🧠 Interview-Ready Summary:

Common scheduling algorithms include FCFS, SJF, Priority, Round Robin, MLQ, and MLFQ. Real-world operating systems use hybrid models based on Multilevel Feedback Queues with dynamic priorities, tuned for responsiveness, fairness, and throughput.

Graph View

Backlinks