Understanding CPU Scheduling in Operating Systems

Exam Tip: Do not confuse Waiting Time with Turnaround Time. Turnaround time includes the time the process was actually running, whereas Waiting Time only counts the time spent in the queue.

Preemptive vs. Non-Preemptive Scheduling

Scheduling approaches are broadly categorized into two types based on how much control the Operating System has over a running process:

1. Non-preemptive Scheduling: Once a process is allocated the CPU, it holds onto it until it either terminates or voluntarily blocks (e.g., waiting for I/O).
2. Preemptive Scheduling: The OS has the authority to interrupt a running process and move it back to the ready queue to allow another process to run.

While preemption significantly improves system responsiveness and fairness, it comes with a cost: context-switch overhead. Every time the OS switches processes, it must save the state of the old process and load the state of the new one, which consumes CPU cycles.

Major Scheduling Algorithms

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

FCFS is the simplest algorithm: processes are executed in the order they arrive. It is non-preemptive and easy to implement using a FIFO (First-In, First-Out) queue. However, it suffers from the convoy effect, where several short processes get stuck behind one very long, resource-heavy process, leading to poor average waiting times.

2. Shortest Job First (SJF)

SJF selects the process with the smallest next CPU burst. This algorithm is mathematically proven to minimize the average waiting time for a given set of processes. The main drawback is that in a real-world system, the OS rarely knows exactly how long a process's next burst will be, requiring estimation.

3. Shortest Remaining Time First (SRTF)

SRTF is the preemptive version of SJF. If a new process arrives with a CPU burst shorter than the remaining time of the currently running process, the current process is preempted. While efficient for short jobs, it can lead to long jobs being delayed indefinitely.

4. Priority Scheduling

In this approach, each process is assigned a priority level, and the CPU is allocated to the process with the highest priority.

A major risk here is starvation, where low-priority processes may never execute because a steady stream of high-priority processes keeps arriving. To solve this, operating systems use aging, a technique that gradually increases the priority of processes that have been waiting in the queue for a long time.

5. Round Robin (RR)

Designed specifically for time-sharing and interactive systems, Round Robin assigns each process a small unit of CPU time called a time quantum. The algorithm is preemptive; once the quantum expires, the process is moved to the back of the queue.

• If the time quantum is too small, the system spends too much time on context-switch overhead.
• If the time quantum is too large, the algorithm behaves like FCFS.

6. Multilevel Queue and Multilevel Feedback Queue

Complex systems often use multiple queues to categorize processes (e.g., foreground interactive processes vs. background batch processes).

• Multilevel Queue: Processes are permanently assigned to a specific queue based on their type, and each queue may use a different scheduling algorithm.
• Multilevel Feedback Queue: This is a more flexible version where processes can move between queues. For example, a process that uses too much CPU might be demoted to a lower-priority queue, while a process that waits too long might be promoted to a higher-priority queue.

Summary Table of Algorithms

Final Checkpoint: Before moving on, ask yourself: Which algorithm minimizes average waiting time under ideal conditions? (Answer: SJF). What is the primary way to prevent starvation in priority scheduling? (Answer: Aging).