Scheduling

Welcome to our lesson on CPU scheduling, students! 🎯 Today, we'll dive into one of the most crucial aspects of computer engineering - how operating systems decide which programs get to use the processor and when. By the end of this lesson, you'll understand different scheduling algorithms, how priority systems work, and why these decisions matter for system performance. Think of it like a traffic controller at a busy intersection - someone needs to decide which cars go first to keep everything moving smoothly!

Understanding CPU Scheduling Fundamentals

Imagine you're the manager of a busy restaurant kitchen 👨‍🍳. Multiple orders come in simultaneously, but you only have one chef (the CPU). How do you decide which order gets prepared first? This is exactly what CPU scheduling does - it determines which process gets to use the processor at any given moment.

CPU scheduling is essential because modern computers run hundreds of processes simultaneously, but most systems have limited CPU cores. The scheduler acts as the decision-maker, ensuring fair resource allocation while maximizing system efficiency. According to recent performance studies, effective scheduling can improve system throughput by up to 40% compared to basic first-come-first-served approaches.

The scheduling process involves several key components. The dispatcher is responsible for actually switching the CPU from one process to another, while the scheduler makes the decisions about which process should run next. This switching process, called a context switch, takes time - typically 1-10 microseconds on modern systems. The goal is to minimize this overhead while maximizing useful work.

First Come First Served and Shortest Job First

Let's start with the simplest scheduling algorithm: First Come First Served (FCFS) 📋. Just like waiting in line at a coffee shop, processes are executed in the order they arrive. While fair and easy to implement, FCFS can lead to the "convoy effect" where short processes wait behind long ones.

Consider this real-world scenario: Process A needs 10 seconds, Process B needs 2 seconds, and Process C needs 3 seconds. If they arrive in that order, the total waiting time is 0 + 10 + 12 = 22 seconds. The average waiting time is 22/3 = 7.33 seconds.

Shortest Job First (SJF) aims to minimize average waiting time by executing the shortest process first. Using our previous example, if we reorder to B, C, A, the waiting times become 0 + 2 + 5 = 7 seconds, with an average of 2.33 seconds - a significant improvement!

However, SJF has a major drawback called starvation - long processes might never execute if short ones keep arriving. It's like being in a grocery store express lane where people with fewer items keep cutting in front of someone with a full cart. To address this, many systems use aging, gradually increasing the priority of waiting processes over time.

Round Robin and Time-Sharing Systems

Round Robin (RR) scheduling revolutionized interactive computing by introducing time slices or quantum periods ⏰. Each process gets a fixed amount of CPU time (typically 10-100 milliseconds) before being moved to the back of the queue. This ensures all processes make progress and provides good response times for interactive applications.

The choice of time quantum is critical. Too short, and you waste time on context switches. Too long, and it behaves like FCFS. Research shows that optimal quantum sizes are typically 20-50 milliseconds for desktop systems, balancing responsiveness with efficiency.

Modern web browsers are excellent examples of Round Robin scheduling. When you have multiple tabs open, each tab's processes get regular time slices, preventing one heavy webpage from freezing your entire browser. This is why you can still switch tabs even when one is loading a complex video or running intensive JavaScript.

Priority Scheduling Systems

Priority scheduling assigns each process a priority value, with higher priority processes executing first 🏆. This mirrors real-world scenarios where some tasks are more urgent than others. Emergency room triage systems work similarly - critical patients are treated before those with minor injuries, regardless of arrival time.

There are two main types: preemptive and non-preemptive priority scheduling. In preemptive systems, a running process can be interrupted if a higher priority process arrives. Non-preemptive systems let the current process finish its CPU burst before switching.

Priority scheduling faces the priority inversion problem. Consider three processes: high priority H, medium priority M, and low priority L. If L holds a resource that H needs, but M keeps preempting L, H waits indefinitely despite having the highest priority. The Mars Pathfinder mission experienced this exact issue in 1997, causing system resets until engineers implemented priority inheritance protocols.

Multilevel queue scheduling addresses complex priority scenarios by maintaining separate queues for different process types. System processes might use one queue with high priority, interactive processes another with medium priority, and batch jobs a third with low priority. Each queue can use its own scheduling algorithm - system processes might use FCFS, while interactive processes use Round Robin.

Real-Time Scheduling

Real-time systems have deadlines that must be met for correct operation ⚡. Missing a deadline in a heart pacemaker or aircraft control system isn't just inconvenient - it's potentially catastrophic. Real-time scheduling algorithms focus on meeting these timing constraints rather than maximizing throughput.

Hard real-time systems have absolute deadlines that cannot be missed. Examples include automotive engine control units, medical devices, and industrial safety systems. Soft real-time systems prefer to meet deadlines but can tolerate occasional misses, like video streaming or online gaming.

Earliest Deadline First (EDF) is optimal for single-processor real-time scheduling. It always schedules the process with the nearest deadline. If a set of processes can be scheduled to meet all deadlines, EDF will find that schedule. However, EDF requires precise knowledge of process execution times and deadlines.

Rate Monotonic Scheduling (RMS) assigns static priorities based on process periods - shorter period processes get higher priorities. While not always optimal, RMS is predictable and widely used in embedded systems. The Mars Rover missions use RMS-based scheduling for their critical control systems.

Performance Metrics and Trade-offs

Understanding scheduling performance requires examining several key metrics 📊. Throughput measures how many processes complete per unit time. Turnaround time is the total time from process submission to completion. Response time measures how quickly a process begins receiving service - crucial for interactive systems.

CPU utilization indicates how busy the processor stays, while waiting time measures how long processes spend in the ready queue. These metrics often conflict - optimizing for throughput might increase response time, while minimizing response time might reduce overall throughput.

Modern operating systems use multilevel feedback queues to balance these trade-offs. New processes start in high-priority queues with short time slices. If they use their entire quantum, they're demoted to lower priority queues with longer quanta. This automatically separates interactive processes (which typically yield the CPU quickly) from CPU-intensive batch processes.

Linux's Completely Fair Scheduler (CFS) uses a red-black tree to track process virtual runtime, ensuring all processes receive proportional CPU time. Windows uses a multilevel feedback queue with 32 priority levels, while macOS employs a similar approach with additional optimizations for energy efficiency on mobile devices.

Conclusion

CPU scheduling is the invisible conductor orchestrating the symphony of processes in your computer 🎼. From simple FCFS to sophisticated real-time algorithms, each approach represents different trade-offs between fairness, efficiency, and responsiveness. Understanding these algorithms helps you appreciate why your computer can seamlessly juggle multiple applications while maintaining good performance. Whether you're designing embedded systems or optimizing server performance, scheduling decisions directly impact user experience and system reliability.

Study Notes

• CPU Scheduling - Process of determining which process gets CPU time and when

• Context Switch - Time required to switch CPU from one process to another (1-10 microseconds)

• FCFS (First Come First Served) - Processes executed in arrival order; simple but can cause convoy effect

• SJF (Shortest Job First) - Minimizes average waiting time but can cause starvation of long processes

• Round Robin - Each process gets fixed time quantum (typically 20-50ms); good for interactive systems

• Priority Scheduling - Processes assigned priority values; higher priority executes first

• Priority Inversion - High priority process waits for low priority process holding needed resource

• Real-Time Scheduling - Must meet deadlines; hard real-time (absolute) vs soft real-time (preferred)

• EDF (Earliest Deadline First) - Optimal single-processor real-time scheduling algorithm

• Performance Metrics - Throughput, turnaround time, response time, CPU utilization, waiting time

• Multilevel Feedback Queues - Multiple priority levels with different scheduling algorithms per level

• Aging - Gradually increasing priority of waiting processes to prevent starvation