CPU Scheduling Algorithms

Category: Operating System Fundamentals
Type: Operating System Concept
Generated on: 2025-07-10 02:59:32
For: System Administration, Development & Technical Interviews

---

CPU Scheduling Algorithms Cheatsheet

1. Quick Overview

CPU scheduling is the process of deciding which of the ready processes in memory should be allocated the CPU for execution. It’s crucial for multitasking, fairness, and efficient resource utilization in operating systems. A good scheduling algorithm aims to minimize waiting time, turnaround time, and response time, while maximizing CPU utilization and throughput.

Why is it important?

• Improved User Experience: Faster response times make the system feel more responsive.
• Increased System Efficiency: Better CPU utilization means more work gets done.
• Fairness: Prevents starvation, ensuring every process gets a fair share of CPU time.

2. Key Concepts

• Process State: New, Ready, Running, Waiting, Terminated
• CPU Burst: The time a process needs the CPU.
• I/O Burst: The time a process spends waiting for I/O operations.
• Arrival Time: The time a process enters the ready queue.
• Burst Time: The total CPU time required by a process.
• Completion Time: The time a process finishes execution.
• Turnaround Time (TAT): Completion Time - Arrival Time (Total time in the system)
• Waiting Time (WT): Turnaround Time - Burst Time (Total time spent waiting in the ready queue)
• Response Time (RT): Time when process first gets CPU - Arrival Time
• Throughput: Number of processes completed per unit time.
• CPU Utilization: Percentage of time CPU is busy.
• Starvation: A process is indefinitely blocked from getting CPU time.
• Preemptive Scheduling: The CPU can be taken away from a running process.
• Non-Preemptive Scheduling: A process runs until it completes or voluntarily blocks.

3. How It Works: CPU Scheduling Algorithms

Here’s a breakdown of common CPU scheduling algorithms:

a) First-Come, First-Served (FCFS)

• Type: Non-preemptive
• How it works: Processes are executed in the order they arrive.

Arrival Order: P1 -> P2 -> P3
CPU: | P1 | P2 | P3 |

• Pros: Simple to implement.
• Cons: Can lead to long waiting times for short processes if a long process arrives first (Convoy Effect). Not ideal for interactive systems.
• Example: Imagine a single checkout line at a grocery store. The first person in line is served first.

b) Shortest Job First (SJF)

• Type: Non-preemptive (can be preemptive as Shortest Remaining Time First - SRTF)
• How it works: The process with the smallest burst time is executed next.

Processes:  P1(8), P2(4), P3(9), P4(5)
Order:      P2 -> P4 -> P1 -> P3
CPU: | P2 | P4 | P1 | P3 |

• Pros: Minimizes average waiting time.
• Cons: Requires knowing burst times in advance (difficult to predict accurately). Can lead to starvation of longer processes.
• Example: A doctor seeing patients. If they know how long each patient will take, they can prioritize the quickest consultations.

c) Shortest Remaining Time First (SRTF)

• Type: Preemptive version of SJF.
• How it works: The process with the smallest remaining burst time is executed. If a new process arrives with a shorter remaining burst time than the currently running process, the current process is preempted.

Processes: P1(8), P2(4), P3(9), P4(5)  Arrival Times: P1(0), P2(1), P3(2), P4(3)

Time  Running  Ready Queue
0     P1       -
1     P1       P2
2     P1       P2, P3
3     P4       P2, P3, P1
4     P4       P2, P3, P1
5     P4       P2, P3, P1
6     P2       P3, P1
7     P2       P3, P1
8     P2       P3, P1
9     P2       P3, P1
10    P1       P3
11    P1       P3
12    P1       P3
13    P1       P3
14    P1       P3
15    P1       P3
16    P1       P3
17    P3       -
...

• Pros: Optimal in minimizing average waiting time.
• Cons: Requires knowing burst times in advance. High overhead due to frequent context switching. Starvation is possible.
• Example: Imagine a hospital emergency room. The doctor immediately attends to the patient with the most urgent (shortest remaining time to live) condition, even if they were already treating another patient.

d) Priority Scheduling

• Type: Can be preemptive or non-preemptive
• How it works: Each process is assigned a priority. The process with the highest priority (usually the lowest number) is executed next.

Processes:  P1(10, 3), P2(1, 1), P3(2, 4), P4(1, 5)   (Burst time, Priority)
Order (Priority): P2 -> P4 -> P1 -> P3  (assuming lower number = higher priority)
CPU: | P2 | P4 | P1 | P3 |

• Pros: Allows prioritizing important processes.
• Cons: Can lead to starvation of low-priority processes. Requires careful assignment of priorities.
• Solution to Starvation: Aging (gradually increasing the priority of waiting processes).
• Example: A system where critical system processes are given higher priority than user applications.

e) Round Robin (RR)

• Type: Preemptive
• How it works: Each process is given a fixed time slice called a quantum. If the process doesn’t complete within the quantum, it’s preempted and moved to the back of the ready queue.

Processes: P1(4), P2(5), P3(2)  Quantum = 2

CPU: | P1 | P2 | P3 | P1 | P2 | P2 |
     | 2  | 2  | 2  | 2  | 2  | 1  |

• Pros: Fair (each process gets a chance). Good for interactive systems.
• Cons: Performance depends heavily on the quantum size. Too small a quantum results in excessive context switching. Too large a quantum degenerates to FCFS.
• Example: A timesharing system where multiple users are interacting with the system simultaneously.
• Code Snippet (Conceptual):

def round_robin(processes, quantum):
  ready_queue = processes.copy()
  current_time = 0
  while ready_queue:
    process = ready_queue.pop(0)
    execution_time = min(process['burst_time'], quantum)
    print(f"Time {current_time}: Executing {process['name']} for {execution_time}")
    current_time += execution_time
    process['burst_time'] -= execution_time
    if process['burst_time'] > 0:
      ready_queue.append(process)  # Put back in queue

4. Real-World Examples

• FCFS: Batch processing systems (e.g., processing payroll).
• SJF/SRTF: Systems where minimizing response time is crucial (e.g., web servers handling short requests). Less common due to the difficulty of predicting burst times.
• Priority Scheduling: Real-time operating systems (RTOS) where critical tasks must be executed with minimal delay (e.g., flight control systems).
• Round Robin: Timesharing operating systems (e.g., Linux, Windows) providing interactive user experiences.

5. Common Issues

• Starvation: Some algorithms can lead to starvation of certain processes. Aging can help mitigate this.
• Convoy Effect (FCFS): A long process blocking shorter processes.
• Context Switching Overhead: Frequent context switching (especially in preemptive algorithms with small quanta) can reduce overall CPU utilization.
• Inaccurate Burst Time Prediction: SJF/SRTF rely on accurate burst time predictions, which are often difficult to obtain. Exponential averaging can be used to estimate future burst times based on past behavior.

6. Interview Questions

• Q: What is CPU scheduling and why is it important?

  • A: The process of deciding which ready process gets the CPU. Important for fairness, efficiency, and responsiveness.

• Q: Explain the difference between preemptive and non-preemptive scheduling.

  • A: Preemptive scheduling allows the OS to interrupt a running process and allocate the CPU to another process. Non-preemptive scheduling requires a process to run until it completes or voluntarily blocks.

• Q: Describe the FCFS scheduling algorithm and its advantages and disadvantages.

  • A: (See above). Simple, but can lead to long waiting times.

• Q: What are the advantages and disadvantages of SJF scheduling?

  • A: (See above). Minimizes waiting time, but requires knowing burst times.

• Q: Explain Round Robin scheduling and the importance of the quantum size.

  • A: (See above). The quantum size affects fairness and context switching overhead.

• Q: How can starvation be prevented in priority scheduling?

  • A: Using aging, where the priority of waiting processes is gradually increased.

• Q: What are the performance metrics used to evaluate CPU scheduling algorithms?

  • A: Turnaround time, waiting time, response time, throughput, CPU utilization.

• Q: Explain the difference between turnaround time and waiting time.

  • A: Turnaround time is the total time a process spends in the system (from arrival to completion). Waiting time is the time a process spends waiting in the ready queue.

• Q: Compare and contrast SJF and SRTF.

  • A: Both aim to minimize waiting time, but SRTF is the preemptive version, allowing a shorter job to interrupt a longer one that’s already running.

7. Further Reading

• Operating System Concepts (Silberschatz, Galvin, Gagne): A classic textbook on operating systems.
• Modern Operating Systems (Tanenbaum): Another comprehensive operating systems textbook.
• Online Resources: GeeksforGeeks, TutorialsPoint, and other online resources provide detailed explanations and examples of CPU scheduling algorithms. Search for “[Algorithm Name] CPU Scheduling” for specific topics.
• Linux Kernel Documentation: Explore the Linux kernel source code to see how scheduling is implemented in a real-world OS.

This cheatsheet provides a solid foundation for understanding CPU scheduling algorithms. Practice problems and real-world scenarios will further solidify your knowledge. Good luck!