Process Scheduling

Introduction

With dozens or hundreds of processes competing for a single CPU, the operating system must decide which process runs when, and for how long. This decision-making is process scheduling — one of the most critical functions of any operating system. Poor scheduling means a sluggish, unresponsive system. Good scheduling means smooth multitasking where every application feels responsive.

Think of it like an air traffic controller managing a single runway. Many planes (processes) want to take off (use the CPU), but only one can use the runway at a time. The controller must decide the order — considering factors like fuel levels (priority), destination distance (burst time), and airline importance (process class). Process scheduling is that controller for the CPU.

Scheduling Queues

The OS maintains several queues to organize processes:

Job Queue

Contains ALL processes in the system, regardless of their state. This is the complete set of processes from creation to termination.

Ready Queue

Contains processes that are in memory, loaded, and ready to execute. They are waiting only for CPU allocation. This is typically implemented as a linked list of PCBs.

Device Queues (Wait Queues)

Each I/O device has its own queue of processes waiting for that device. When a process requests disk I/O, it is moved from the running state to the disk's wait queue.

The Three Schedulers

Long-Term Scheduler (Job Scheduler)

The long-term scheduler controls which processes are admitted into the system (moved from disk to memory). It determines the degree of multiprogramming — how many processes can be in memory simultaneously.

Frequency: Runs infrequently (seconds to minutes between decisions) Key decision: Should it admit more I/O-bound or CPU-bound processes? A good mix keeps both the CPU and I/O devices busy.

In many modern systems (especially time-sharing systems like Linux), there is no distinct long-term scheduler — processes are admitted to memory immediately upon creation. Virtual memory makes this feasible since not all process pages need to be in physical memory simultaneously.

Short-Term Scheduler (CPU Scheduler)

The short-term scheduler selects which ready process gets the CPU next. This is the scheduler we study most — FCFS, SJF, Round Robin, Priority, and MLFQ are all short-term scheduling algorithms.

Frequency: Runs very frequently (every 10-100 milliseconds, or on every context switch) Speed requirement: Must be extremely fast since it runs so often. A 10ms decision on a 100ms quantum means 10% overhead — unacceptable if the decision is complex.

Medium-Term Scheduler (Swapper)

The medium-term scheduler handles swapping — temporarily removing processes from memory and storing them on disk to reduce memory pressure. When memory becomes available (or the process is needed), it swaps them back in.

Purpose: Reduce the degree of multiprogramming when memory is overcommitted When it acts: When the system detects memory pressure (too many page faults, low free memory)

Degree of Multiprogramming

This is the number of processes currently in memory. More processes means:

• Better CPU utilization (always something ready to run when one blocks)
• But more memory pressure and more overhead

The long-term and medium-term schedulers work together to keep the degree of multiprogramming at an optimal level.

Process Scheduling in Practice

Linux

Linux has no explicit long-term scheduler (all processes are admitted). The medium-term scheduler equivalent is the OOM (Out of Memory) killer which terminates processes when RAM is critically low. The short-term scheduler is CFS (Completely Fair Scheduler).

Windows

Windows similarly admits all processes immediately. Its memory manager handles swapping (modified page writer, working set trimmer). The short-term scheduler uses a priority-based preemptive algorithm with 32 priority levels.

Queueing Diagram

A process migrates between queues throughout its life:

Real-World Analogy

Think of scheduling queues like an airport:

• Job Queue: All passengers who have booked flights (all known processes)
• Ready Queue: Passengers at the gate, boarding pass in hand, ready to board (in memory, waiting for CPU)
• Device Queue: Passengers waiting at security, baggage claim, or immigration (waiting for I/O)
• Long-term scheduler: The airline deciding how many tickets to sell per flight (controlling multiprogramming)
• Short-term scheduler: Gate agent calling boarding groups (selecting who gets CPU next)
• Medium-term scheduler: Asking some passengers to wait in the lounge when the gate area is too crowded (swapping)

Key Takeaways

• The OS uses multiple queues (ready queue, device queues) to organize processes by state
• Three schedulers operate at different time scales: long-term (seconds), short-term (milliseconds), medium-term (as needed)
• The long-term scheduler controls admission and the degree of multiprogramming
• The short-term scheduler makes the frequent CPU allocation decisions (FCFS, SJF, RR, etc.)
• The medium-term scheduler handles swapping to manage memory pressure
• Modern desktop OS often lack explicit long-term schedulers — virtual memory handles overcommitment
• A good balance of I/O-bound and CPU-bound processes maximizes overall system utilization