CPU Scheduling Algorithms

# CHAPTER 7

CPU Scheduling Algorithms #

1. Introduction #

At any given moment, your computer might have 200 processes in the "Ready" state, all waiting to use the CPU. If you only have a 4-core processor, only 4 processes can run at once. Who gets to go first? Who gets kicked out if a more important task arrives? The Operating System component responsible for making these split-second decisions is the CPU Scheduler. Designing a fair and efficient scheduler is one of the most mathematically complex challenges in Computer Science. If the scheduler makes bad decisions, the mouse cursor lags, audio stutters, and the system feels sluggish. In this chapter, we will explore the core mathematics of Operating Systems: CPU Scheduling Algorithms. We will calculate execution times for First-Come First-Served (FCFS), Shortest Job First (SJF), and the modern standard, Round Robin.

2. Learning Objectives #

By the end of this chapter, you will be able to:

• Define the primary goals of CPU Scheduling (Max throughput, min wait time).

• Distinguish between Preemptive and Non-Preemptive scheduling.

• Calculate Turnaround Time and Waiting Time for various processes.

• Simulate the First-Come First-Served (FCFS) and Shortest Job First (SJF) algorithms.

• Explain the Time Quantum mechanic in the Round Robin (RR) algorithm.

3. Preemptive vs. Non-Preemptive Scheduling #

Schedulers are categorized by how aggressive they are:

• Non-Preemptive (Polite): Once a process is given the CPU, it keeps the CPU until it voluntarily finishes its job or asks for I/O. The OS cannot force it off the CPU. (Used in old batch systems; terrible for modern PCs).

• Preemptive (Aggressive): The OS can violently interrupt a running process, kick it off the CPU, and give the CPU to someone else based on a timer or priority rule. (This is how all modern operating systems work).

4. Scheduling Metrics (How we grade them) #

To judge if an algorithm is "good," we use specific math metrics:

• Arrival Time: The exact millisecond the process enters the "Ready" queue.

• Burst Time: Exactly how many milliseconds of CPU time the process needs to finish its math.

• Turnaround Time: Total time from arrival to completion. *(Completion Time - Arrival Time)*.

• Waiting Time: Total time the process spent sitting in the queue doing nothing. *(Turnaround Time - Burst Time)*.

5. Algorithm 1: First-Come First-Served (FCFS) #

This is the simplest algorithm. Whoever gets in line first, goes first.

• Type: Non-Preemptive.

• The Problem: The "Convoy Effect." If Process A takes 100 seconds to finish, and Process B only takes 1 second, Process B has to wait an agonizing 100 seconds just to do 1 second of work. FCFS is terribly inefficient for interactive systems.

6. Algorithm 2: Shortest Job First (SJF) #

The OS looks at all the processes in the queue and picks the one with the shortest Burst Time to go next.

• Type: Can be Preemptive or Non-Preemptive.

• The Benefit: It mathematically guarantees the lowest average waiting time of any algorithm!

• The Problem: "Starvation." If a massive 100-second video rendering job enters the queue, but tiny 1-second background tasks keep arriving, the OS will *always* pick the 1-second tasks. The heavy video job will "starve" and never get executed!

7. Algorithm 3: Round Robin (RR) #

This is the foundation of modern Time-Sharing operating systems. The OS gives every single process a strict time limit called a Time Quantum (e.g., 10 milliseconds).

• How it works: Process A gets 10ms. Even if Process A isn't finished, the OS forcibly kicks it off the CPU (Preemption), puts it at the back of the line, and gives Process B 10ms.

• The Benefit: It guarantees fairness. No process ever starves. The system feels highly responsive to the human user.

• The Problem: If the Time Quantum is too small (e.g., 1ms), the CPU spends 90% of its time Context Switching instead of actually doing work.

8. Diagrams/Visual Suggestions #

*Visual Concept: The Gantt Chart* Operating Systems use Gantt Charts to visualize scheduling. Draw a horizontal bar representing the CPU timeline from 0ms to 20ms.

• FCFS Chart: Process 1 (P1) is a massive block from 0 to 15. Process 2 (P2) is a tiny block from 15 to 16.

• Round Robin Chart (Quantum = 5ms): P1 runs 0-5. P2 runs 5-6 (finishes early). P1 runs 6-11. P1 runs 11-16.

This visually demonstrates how Round Robin chops massive jobs into pieces to ensure smaller jobs don't wait forever.

9. Best Practices #

• Multilevel Feedback Queues: Modern OSs (like Windows and Linux) don't use just one algorithm. They use multiple queues. High-priority interactive apps (like your mouse cursor) are put in a Round Robin queue with a fast quantum. Heavy, boring background tasks (like a virus scan) are pushed down into a slower FCFS queue so they don't interrupt your video game.

10. Common Mistakes #

• Assuming SJF is Possible in Reality: In a university exam, you are told exactly what the Burst Time is (e.g., "Process A needs 5ms"). In the real world, the OS has *absolutely no idea* how long a process will take to finish until it actually runs! Therefore, pure Shortest Job First is mathematically impossible to implement in a real desktop OS. It is only used as a theoretical benchmark.

11. Mini Project: Calculate Waiting Time #

Calculate the Average Waiting Time for this FCFS scenario (Assume all arrive at 0ms):

• P1: Burst Time = 10ms

• P2: Burst Time = 2ms

• P3: Burst Time = 3ms

Calculation:

• P1 waits: 0ms. (Executes from 0 to 10).

• P2 waits: 10ms. (Executes from 10 to 12).

• P3 waits: 12ms. (Executes from 12 to 15).

Average Wait: (0 + 10 + 12) / 3 = 7.33 ms. *(If we used SJF, P2 goes first, P3 goes second, P1 goes last. The average wait drops to 2.33ms!)*

12. Practice Exercises #

1. 1. Define the "Convoy Effect" in the context of the First-Come First-Served (FCFS) algorithm.

1. 2. Explain the concept of "Starvation" in a CPU scheduling environment. Which specific algorithm is highly susceptible to causing Starvation?

13. MCQs with Answers #

14. Interview Questions #

• Q: Explain the mechanical difference between Preemptive and Non-Preemptive CPU scheduling. Why is a Preemptive architecture an absolute requirement for a modern, responsive GUI operating system like Windows 11?

• Q: Describe the Priority Scheduling algorithm. What is the fundamental risk of assigning permanent, static priorities to processes, and how does the OS technique of "Aging" solve this risk? *(Hint: Solving Starvation).*

• Q: You are designing an operating system for a medical device that processes highly predictable, sequential batches of data where user interaction is non-existent. Which CPU scheduling algorithm would you choose, and why would you intentionally avoid Round Robin?

15. FAQs #

Q: Does adding more RAM to my computer help the CPU Scheduler? A: No. The CPU scheduler only cares about processes that are already loaded in the RAM (The "Ready" queue). Adding more RAM allows you to hold *more* processes open simultaneously without using the hard drive, but it doesn't make the mathematical algorithm of the CPU scheduler run any faster.

16. Summary #

In Chapter 7, we engineered the brain of the Operating System. We abandoned chaotic execution in favor of strict, mathematically optimized CPU Scheduling Algorithms. We defined the critical performance metrics of Turnaround and Waiting Time, evaluating the sluggish Convoy Effect of FCFS, and the starvation risks associated with Shortest Job First (SJF). We identified the aggressive, preemptive nature of the Round Robin algorithm as the foundation of modern time-sharing systems, utilizing the Time Quantum to guarantee fairness and user responsiveness across hundreds of competing processes.

17. Next Chapter Recommendation #

When two processes are scheduled to run concurrently, they might try to edit the exact same file at the exact same millisecond, causing data corruption. We must learn how the OS prevents them from colliding. Proceed to Chapter 8: Process Synchronization.