Scheduling Algorithms (RR, FCFS, SJF, Priority)

Scheduling Algorithms (RR, FCFS, SJF, Priority)

Why This Matters

Think of CPU scheduling like a restaurant manager deciding which customer to serve next. First Come First Served (FCFS) is like serving customers in the order they arrived—simple, but a slow order can delay everyone. Round Robin is like giving each customer a time slice, then moving to the next—fair, but can feel slow. Shortest Job First (SJF) is like serving quick orders first—efficient, but long orders wait forever.

This matters because the scheduling algorithm affects how your system performs. FCFS is simple but can cause long waits. Round Robin is fair but has overhead from frequent switching. SJF minimizes waiting time but requires knowing job lengths in advance. Understanding these helps you choose the right algorithm for your use case.

In interviews, when someone asks "How would you design a task scheduler?", they're testing whether you understand scheduling algorithms. Do you know the trade-offs? Can you choose the right algorithm? Most engineers don't. They use the default and wonder why performance isn't optimal.

What Engineers Usually Get Wrong

Most engineers think "Round Robin is always best because it's fair." But Round Robin has overhead—frequent context switches. For CPU-bound tasks, this overhead can hurt performance. Also, Round Robin treats all processes equally, but some processes might be more important (higher priority).

Engineers also don't understand that different algorithms optimize for different goals. FCFS optimizes for simplicity. Round Robin optimizes for fairness. SJF optimizes for waiting time. Priority scheduling optimizes for important tasks. The key is choosing the algorithm that matches your goals.

How This Breaks Systems in the Real World

A service was using FCFS scheduling. It processed requests in the order they arrived. Under normal load, this worked. But when a slow request arrived (processing a large file), it blocked all subsequent requests. Response times spiked. Users experienced long waits even for simple requests. The fix? Use Round Robin or priority scheduling. Give each request a time slice, or prioritize quick requests.

Another story: A service was using Round Robin scheduling. It gave each process equal time. But some processes were more important (handling user requests) than others (background tasks). Important processes had to wait behind less important ones. This created a poor user experience. The fix? Use priority scheduling. Give higher priority to important processes.

---

Scheduling Goals

1. Fairness: All processes get fair CPU time
2. Throughput: Maximize number of processes completed per unit time
3. Response time: Minimize time from request to first response
4. Waiting time: Minimize time process waits in ready queue
5. Turnaround time: Minimize time from submission to completion

---

First Come First Served (FCFS)

Also called: First In First Out (FIFO)

Concept: Process that arrives first is served first.

Characteristics:

• Non-preemptive: Once process starts, it runs until completion
• Simple: Easy to implement
• Fair: First come, first served

Example

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

Gantt Chart:
|----P1----|P2|P3|
0          24 27 30

Waiting Times:
P1: 0
P2: 24 - 1 = 23
P3: 27 - 2 = 25
Average: (0 + 23 + 25) / 3 = 16

Problem: P1 (long process) blocks P2 and P3 (convoy effect)

Advantages

• Simple to implement
• Fair (first come, first served)

Disadvantages

• Convoy effect: Long process blocks short processes
• Poor response time: Short processes wait for long processes
• Not optimal: High average waiting time

---

Shortest Job First (SJF)

Also called: Shortest Job Next (SJN)

Concept: Process with shortest burst time runs first.

Characteristics:

• Non-preemptive: Once process starts, it runs until completion
• Optimal: Minimizes average waiting time
• Requires: Knowledge of burst times (not always available)

Example

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

Gantt Chart (SJF):
|P1|P4|P3|----P2----|
0  6  9 16          24

Waiting Times:
P1: 0
P2: 16 - 2 = 14
P3: 9 - 4 = 5
P4: 6 - 6 = 0
Average: (0 + 14 + 5 + 0) / 4 = 4.75

Shortest Remaining Time First (SRTF)

Preemptive version of SJF: Process with shortest remaining time runs.

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

Gantt Chart (SRTF):
|P1|P2|P4|P3|P2|----P1----|
0  1  2  3  4  6          14

Better response time than non-preemptive SJF

Advantages

• Optimal: Minimizes average waiting time
• Good for: Batch systems with known burst times

Disadvantages

• Starvation: Long processes may never run
• Requires: Knowledge of burst times (difficult to predict)
• Not fair: Short processes always prioritized

---

Round Robin (RR)

Concept: Each process gets a small time slice (quantum), then preempted.

Characteristics:

• Preemptive: Process preempted after time quantum
• Fair: All processes get equal CPU time
• Good response time: Short processes get quick response

Example

Process Burst Time  Quantum = 4
P1      24
P2      3
P3      3

Gantt Chart (Round Robin):
|P1|P2|P3|P1|P2|P3|P1|P1|P1|P1|P1|P1|
0  4  7 10 14 17 20 24 28 32 36 40 44

Waiting Times:
P1: (0-0) + (10-4) + (20-14) + (24-20) = 16
P2: (4-0) + (14-10) = 8
P3: (7-4) + (17-14) = 6
Average: (16 + 8 + 6) / 3 = 10

Quantum Size

Too small:

• High context switch overhead
• Poor CPU utilization

Too large:

• Approaches FCFS
• Poor response time

Optimal: Typically 10-100ms

Advantages

• Fair: All processes get equal time
• Good response time: Short processes respond quickly
• No starvation: All processes eventually run

Disadvantages

• Overhead: Context switching overhead
• Not optimal: May not minimize waiting time

---

Priority Scheduling

Concept: Each process has a priority, higher priority runs first.

Characteristics:

• Preemptive or non-preemptive: Can be either
• Priority: Higher number = higher priority (or vice versa)
• Starvation: Low priority processes may never run

Example

Process Burst Time  Priority
P1      10         3 (low)
P2      1          1 (high)
P3      2          4 (low)
P4      1          5 (low)
P5      5          2 (high)

Gantt Chart (Priority, higher number = higher priority):
|P2|P5|P1|P3|P4|
0  1  6 16 18 19

Waiting Times:
P1: 6 - 0 = 6
P2: 0
P3: 16 - 0 = 16
P4: 18 - 0 = 18
P5: 1 - 0 = 1
Average: (6 + 0 + 16 + 18 + 1) / 5 = 8.2

Aging

Problem: Low priority processes may starve.

Solution: Aging - Increase priority of waiting processes over time.

Process Priority (increases over time):
P1: 3 → 4 → 5 → 6 (eventually runs)

Advantages

• Flexible: Can prioritize important processes
• Good for: Real-time systems, interactive systems

Disadvantages

• Starvation: Low priority processes may never run
• Requires: Priority assignment (can be complex)

---

Multi-Level Queue Scheduling

Concept: Separate queues for different process types.

Structure:

Queue 1 (System): Round Robin, quantum = 8ms
Queue 2 (Interactive): Round Robin, quantum = 16ms
Queue 3 (Batch): FCFS

Scheduling:

1. Process assigned to queue based on type
2. Higher priority queues run first
3. Within queue: Use queue's scheduling algorithm

---

Examples

FCFS Implementation

class FCFSScheduler:
    def __init__(self):
        self.ready_queue = []  # FIFO queue
    
    def add_process(self, process):
        self.ready_queue.append(process)
    
    def schedule(self):
        if self.ready_queue:
            return self.ready_queue.pop(0)  # First process
        return None

Round Robin Implementation

class RoundRobinScheduler:
    def __init__(self, quantum=10):
        self.ready_queue = []
        self.quantum = quantum
        self.current_process = None
        self.time_used = 0
    
    def add_process(self, process):
        self.ready_queue.append(process)
    
    def schedule(self, current_time):
        # If current process used up quantum, preempt
        if self.current_process and self.time_used >= self.quantum:
            # Move to end of queue
            self.ready_queue.append(self.current_process)
            self.current_process = None
            self.time_used = 0
        
        # Get next process
        if not self.current_process and self.ready_queue:
            self.current_process = self.ready_queue.pop(0)
            self.time_used = 0
        
        return self.current_process
    
    def tick(self):
        if self.current_process:
            self.time_used += 1
            self.current_process.burst_time -= 1
            
            if self.current_process.burst_time == 0:
                # Process completed
                self.current_process = None
                self.time_used = 0

Priority Scheduling with Aging

class PriorityScheduler:
    def __init__(self):
        self.ready_queue = []  # Priority queue
    
    def add_process(self, process):
        self.ready_queue.append(process)
        self.ready_queue.sort(key=lambda p: p.priority, reverse=True)
    
    def schedule(self):
        if self.ready_queue:
            return self.ready_queue[0]  # Highest priority
        return None
    
    def age_processes(self):
        # Increase priority of waiting processes
        for process in self.ready_queue[1:]:  # Skip running process
            process.priority += 1
        self.ready_queue.sort(key=lambda p: p.priority, reverse=True)

---

Common Pitfalls

• Ignoring context switch overhead: Too small quantum in Round Robin. Fix: Balance quantum size with overhead
• Starvation in priority scheduling: Low priority processes never run. Fix: Use aging, or multi-level feedback queue
• Not considering process types: Using same algorithm for all. Fix: Use multi-level queue for different process types
• Poor quantum size: Too small or too large in Round Robin. Fix: Use 10-100ms quantum
• Not handling I/O-bound processes: CPU-bound processes dominate. Fix: Use multi-level feedback queue

---

Interview Questions

Beginner

Q: What is CPU scheduling and why is it needed?

A:

CPU scheduling determines which process runs when multiple processes are ready to execute.

Why needed:

1. Multiprogramming: Multiple processes in memory, but one CPU
2. Fairness: All processes get CPU time
3. Efficiency: Maximize CPU utilization
4. Response time: Interactive processes need quick response

Goals:

• Fairness: All processes get fair CPU time
• Throughput: Maximize processes completed per unit time
• Response time: Minimize time from request to first response
• Waiting time: Minimize time process waits in ready queue

Types:

• Preemptive: Process can be interrupted (Round Robin, Priority)
• Non-preemptive: Process runs until completion (FCFS, SJF)

Example:

Ready Queue: [P1, P2, P3]
Scheduler: Selects P1 to run
After time slice: Preempts P1, selects P2

---

Intermediate

Q: Compare FCFS, SJF, Round Robin, and Priority scheduling. When would you use each?

A:

FCFS (First Come First Served):

• Algorithm: First process in queue runs first
• Type: Non-preemptive
• Advantages: Simple, fair
• Disadvantages: Convoy effect, poor response time
• Use when: Simple systems, batch processing

SJF (Shortest Job First):

• Algorithm: Shortest burst time runs first
• Type: Non-preemptive (or preemptive as SRTF)
• Advantages: Optimal waiting time
• Disadvantages: Starvation, requires burst time knowledge
• Use when: Batch systems with known burst times

Round Robin:

• Algorithm: Each process gets time quantum, then preempted
• Type: Preemptive
• Advantages: Fair, good response time, no starvation
• Disadvantages: Context switch overhead
• Use when: Time-sharing systems, interactive systems

Priority:

• Algorithm: Higher priority runs first
• Type: Preemptive or non-preemptive
• Advantages: Flexible, can prioritize important processes
• Disadvantages: Starvation (use aging)
• Use when: Real-time systems, systems with priority requirements

Comparison:

Algorithm	Preemptive	Starvation	Optimal	Use Case
FCFS	No	No	No	Simple systems
SJF	No	Yes	Yes (waiting time)	Batch systems
Round Robin	Yes	No	No	Time-sharing
Priority	Yes/No	Yes	No	Real-time

---

Senior

Q: Design a CPU scheduler for a modern operating system that handles both interactive and batch processes efficiently. How do you prevent starvation and optimize for different process types?

A:

class MultiLevelFeedbackQueueScheduler {
  private queues: ProcessQueue[];
  private quantum: number[];
  private agingTimer: number;
  
  constructor() {
    // Multiple queues with different priorities and quanta
    this.queues = [
      new ProcessQueue({ priority: 0, quantum: 8, algorithm: 'RR' }),   // System
      new ProcessQueue({ priority: 1, quantum: 16, algorithm: 'RR' }),  // Interactive
      new ProcessQueue({ priority: 2, quantum: 32, algorithm: 'RR' }),  // Batch
      new ProcessQueue({ priority: 3, quantum: Infinity, algorithm: 'FCFS' }) // Background
    ];
    
    this.quantum = [8, 16, 32, Infinity];
    this.agingTimer = 0;
  }
  
  // 1. Process Classification
  classifyProcess(process: Process): number {
    // Classify based on characteristics
    if (process.isSystemProcess()) {
      return 0; // System queue
    } else if (process.isInteractive()) {
      return 1; // Interactive queue
    } else if (process.isBatch()) {
      return 2; // Batch queue
    } else {
      return 3; // Background queue
    }
  }
  
  // 2. Scheduling
  schedule(): Process | null {
    // Check queues from highest to lowest priority
    for (const queue of this.queues) {
      if (queue.hasProcesses()) {
        return queue.getNextProcess();
      }
    }
    return null;
  }
  
  // 3. Process Promotion/Demotion
  handleTimeSlice(process: Process, queueIndex: number): void {
    // If process used full quantum, demote
    if (process.usedFullQuantum()) {
      if (queueIndex < this.queues.length - 1) {
        // Move to lower priority queue
        this.queues[queueIndex].remove(process);
        this.queues[queueIndex + 1].add(process);
      }
    }
    
    // If process blocked on I/O, promote
    if (process.isIOBound()) {
      if (queueIndex > 0) {
        // Move to higher priority queue
        this.queues[queueIndex].remove(process);
        this.queues[queueIndex - 1].add(process);
      }
    }
  }
  
  // 4. Aging (Prevent Starvation)
  ageProcesses(): void {
    this.agingTimer++;
    
    // Every 100 time units, promote processes
    if (this.agingTimer >= 100) {
      for (let i = 1; i < this.queues.length; i++) {
        const processes = this.queues[i].getAllProcesses();
        for (const process of processes) {
          process.waitingTime += 100;
          
          // If waited too long, promote
          if (process.waitingTime > 1000) {
            this.queues[i].remove(process);
            this.queues[i - 1].add(process);
            process.waitingTime = 0;
          }
        }
      }
      this.agingTimer = 0;
    }
  }
  
  // 5. I/O-Bound Process Optimization
  handleIOCompletion(process: Process): void {
    // I/O-bound processes: Promote to higher priority
    const currentQueue = this.findProcessQueue(process);
    if (currentQueue > 0) {
      this.queues[currentQueue].remove(process);
      this.queues[currentQueue - 1].add(process);
    }
  }
  
  // 6. CPU-Bound Process Handling
  handleCPUIntensive(process: Process): void {
    // CPU-bound processes: Demote to lower priority
    const currentQueue = this.findProcessQueue(process);
    if (currentQueue < this.queues.length - 1) {
      this.queues[currentQueue].remove(process);
      this.queues[currentQueue + 1].add(process);
    }
  }
  
  // 7. Adaptive Quantum
  adjustQuantum(queueIndex: number): void {
    // Adjust quantum based on queue load
    const load = this.queues[queueIndex].getLoad();
    
    if (load > 0.8) {
      // High load: Increase quantum (reduce context switches)
      this.quantum[queueIndex] = Math.min(
        this.quantum[queueIndex] * 1.2,
        this.quantum[queueIndex + 1] || Infinity
      );
    } else if (load < 0.3) {
      // Low load: Decrease quantum (better response time)
      this.quantum[queueIndex] = Math.max(
        this.quantum[queueIndex] * 0.8,
        4 // Minimum quantum
      );
    }
  }
}

Features:

1. Multi-level queues: Different queues for different process types
2. Feedback mechanism: Promote I/O-bound, demote CPU-bound
3. Aging: Prevent starvation by promoting waiting processes
4. Adaptive quantum: Adjust quantum based on load
5. Process classification: System, interactive, batch, background
6. Optimization: Different algorithms per queue type

---

Failure Stories You'll Recognize

The FCFS Convoy Effect: A service was using FCFS scheduling. It processed requests in the order they arrived. Under normal load, this worked. But when a slow request arrived (processing a large file), it blocked all subsequent requests. Response times spiked. Users experienced long waits even for simple requests. The fix? Use Round Robin or priority scheduling. Give each request a time slice, or prioritize quick requests.

The Priority Starvation: A service was using priority scheduling. Important processes had high priority, background tasks had low priority. Over time, low-priority processes never ran because high-priority processes always had work. Background tasks accumulated. The system became unresponsive. The fix? Use aging—gradually increase priority of waiting processes. Or use multi-level feedback queues.

The Round Robin Overhead: A service was using Round Robin with a very small time quantum (1ms). This created fairness, but the overhead from frequent context switches hurt performance. CPU spent more time switching than executing. The fix? Increase time quantum to 10-50ms. Balance fairness with overhead.

What Interviewers Are Really Testing

They want to hear you talk about scheduling algorithms as trade-offs, not absolutes. Junior engineers say "use Round Robin for fairness." Senior engineers say "different algorithms optimize for different goals. FCFS is simple but can cause convoy effect. Round Robin is fair but has overhead. SJF minimizes waiting but requires knowing job lengths. Choose based on your use case."

When they ask "How would you design a task scheduler?", they're testing:

• Do you understand the trade-offs between algorithms?

• Do you know when to use each algorithm?

• Can you design systems that balance fairness, throughput, and response time?

• CPU scheduling: Determines which process runs when multiple processes are ready

• FCFS: First come first served, simple but has convoy effect

• SJF: Shortest job first, optimal waiting time but requires burst time knowledge

• Round Robin: Time-sliced, fair, good response time, no starvation

• Priority: Higher priority runs first, flexible but can cause starvation

• Preemptive vs non-preemptive: Preemptive allows interruption, non-preemptive runs to completion

• Multi-level feedback queue: Multiple queues with different priorities, prevents starvation, optimizes for different process types

• Best practices: Use appropriate algorithm for process type, prevent starvation with aging, balance quantum size with overhead

How InterviewCrafted Will Teach This

We'll teach this through production failures, not definitions. Instead of memorizing "Round Robin uses time slices," you'll learn through scenarios like "why did our system become slow when we used FCFS scheduling?"

You'll see how scheduling algorithms affect system performance and user experience. When an interviewer asks "how would you design a task scheduler?", you'll think about fairness, throughput, response time, and trade-offs—not just "use Round Robin."

• Context Switching - How the OS switches between processes and the overhead involved in scheduling
• Process vs Thread - Understanding processes and threads that are scheduled by the CPU scheduler
• Deadlock Conditions and Prevention - How scheduling relates to deadlock prevention and resource allocation
• PCB (Process Control Block) - How the OS tracks process state for scheduling decisions
• Kernel Mode vs User Mode - How the scheduler runs in kernel mode to manage CPU resources