<aside> 💡

Summary of Section 17.1 - Scheduling Algorithms (C191: Operating Systems for Programmers, zyBooks)

</aside>

Overview

CPU scheduling is crucial for determining which process in the ready queue is allocated CPU time. The section introduces several CPU scheduling algorithms, primarily considering single-core CPUs. The goal of scheduling is to optimize CPU utilization, throughput, turnaround time, waiting time, and response time.

1. First-Come, First-Served (FCFS) Scheduling

• Mechanism: The first process to request CPU time is served first.
• Implementation: Uses a FIFO queue to maintain process order.
• Advantages: Simple and easy to implement.
• Disadvantages:
  • High waiting time when long processes precede short ones.
  • Convoy effect: If a long process is running, shorter processes must wait.
  • Non-preemptive: A process runs until completion or I/O request.
  • Poor performance for interactive systems due to long delays.

2. Shortest Job First (SJF) Scheduling

• Mechanism: The process with the shortest CPU burst time is executed first.
• Advantages:
  • Optimal in minimizing average waiting time.
  • Reduces the convoy effect seen in FCFS.
• Disadvantages:
  • Difficult to implement: Exact CPU burst times are not known in advance.
  • May lead to starvation: Long processes may never get scheduled.
• Variations:
  • Non-preemptive SJF: A running process is never preempted.
  • Preemptive SJF (Shortest-Remaining-Time-First, SRTF): If a new process has a shorter burst time than the current running process, it preempts the CPU.

3. Round-Robin (RR) Scheduling

• Mechanism: Each process is assigned a time quantum (e.g., 10–100 ms) and is preempted if it exceeds this time.
• Advantages:
  • Fair for all processes.
  • Prevents starvation of short processes.
  • Good for time-sharing systems.