Scheduling Algorithms (RR, FCFS, SJF, Priority)

CPU scheduling determines which process runs when multiple processes are ready to execute. Different scheduling algorithms optimize for different goals: fairness, throughput, response time, or waiting time.

---

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

---

Key Takeaways

• 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