Process Scheduling

A computer typically has far more processes than CPU cores. At any given moment, only one process per core can actually be executing instructions. The OS must multiplex (share) the CPU among all active processes, creating the illusion that each process has its own dedicated CPU.

Without multiplexing:

A buggy or infinite loop in one process would freeze the entire system.
I/O operations (like reading from disk or network) would idle the CPU for milliseconds or seconds (an eternity in CPU time).
Interactive programs (editors, browsers) would feel unresponsive.

On a multi-core CPU, the scheduler can run multiple threads simultaneously – one per core. This is true parallel execution, not just concurrency (interleaving).

The scheduler is the OS component that decides which process runs when and for how long. This decision is based on the Process Control Block (PCB) is key: the PCB holds all the information the scheduler needs to make an intelligent choice.

The Process Control Block (PCB)

The scheduler maintains a data structure of PCBs. For each process, the PCB is a kernel data structure that contains:

Process state (new, ready, running, waiting, terminated – more on this later)
Program counter (address of the next instruction to execute)
CPU registers (all general-purpose registers, stack pointer, etc.)
Memory management info (page tables, segment limits)
Scheduling information (priority, time slice used, waiting time)
Accounting info (CPU time used, process ID, parent process)
I/O status (list of open files, pending I/O operations)

The scheduler does not just look at one PCB; it typically manages several queues of PCBs. The "ready queue" is one of them. The scheduler’s decision (which process to run next) is made by examining the scheduling-related fields in the PCBs of all processes in the ready queue.

We talk about process state. There are five classic states: new, running, ready, waiting, terminated. This is a state machine that every process goes through. Understanding transitions is essential to understanding scheduling.

         +---------+      (admitted)      +----------+
         |   New   | -------------------> |   Ready  |
         +---------+                      +----------+
                                                |
                                                | (scheduler dispatch)
                                                v
         +----------+                        +---------+
         | Terminated| <-------------------- | Running |
         +----------+     (exit)             +---------+
                           (I/O or event wait)   |
                           |                     | (I/O or event complete)
                           v                     |
                      +---------+                |
                      | Waiting | <--------------+
                      +---------+

New – The process is being created. The OS is allocating the PCB and initial resources. The process is not yet ready to run.
Ready – The process is loaded in memory, has all resources except the CPU, and is waiting to be scheduled. It is in the ready queue.
Running – The process is currently executing on the CPU.
Waiting (or Blocked) – The process is waiting for some event (e.g., disk I/O completion, network packet, user input, a lock to be released). It is not eligible to be scheduled until the event occurs. The OS moves it to a wait queue associated with that event.
Terminated – The process has finished execution (either normally or abnormally). Its PCB remains (zombie state) until the parent process collects its exit status, then the PCB is deallocated.

The scheduler only considers processes in the Ready state. Processes in Waiting are not in the ready queue; they are elsewhere. This separation prevents the scheduler from wasting CPU time on processes that cannot proceed.

Scheduling Decisions

The ready queue is typically implemented as a linked list of PCBs (or more sophisticated data structures like a multilevel queue or a priority heap).

The scheduler’s job is to pick one process from the ready queue to run next. The scheduling policy determines the order. Different policies make different trade-offs (see Part 7). But before we dive into policies, we must understand two key concepts:

Non-preemptive (cooperative) – Once a process gets the CPU, it keeps it until it voluntarily yields (e.g., by waiting for I/O or calling yield()). The scheduler cannot forcibly take the CPU away. This was common in early systems (Windows 3.1, classic Mac OS). Problem: a buggy process can hog the CPU forever.
Preemptive – The OS uses a hardware timer interrupt (e.g., every 1–100 ms) to forcibly regain control. The scheduler can then decide to switch to another process. Modern general-purpose OSes (Linux, Windows, macOS) are preemptive. This ensures fairness and responsiveness.

In real OSes, there isn't just one ready queue. There are multiple scheduling levels:

Long-term scheduler (job scheduler) – Selects which processes from disk are admitted into memory (into the ready queue). Rare in modern general-purpose OSes (except batch systems) because virtual memory allows many processes.
Medium-term scheduler (swapping) – Temporarily removes processes from memory (swaps them to disk) to reduce multiprogramming degree. This is used when memory is overcommitted. The process goes from ready/waiting to suspended states. Your notes don't include this, but it's an important extension.
Short-term scheduler (CPU scheduler) – Selects the next process from the ready queue to run (what we described above).

Often, the scheduler’s policy is the most important influence on the performance of a system. Different policies optimize for different metrics:

Throughput – Number of processes completed per time unit.
Turnaround time – Time from process arrival to completion.
Waiting time – Total time a process spends in the ready queue.
Response time – Time from request submission to first response (e.g., keystroke to screen update).

Here are the major policies:

First-Come, First-Served (FCFS)

Non-preemptive. Ready queue is a FIFO queue.

Pros: Simple, fair in arrival order.
Cons: Convoy effect – a long CPU-bound process blocks many short I/O-bound processes, hurting response time.

Shortest Job First (SJF) / Shortest Remaining Time First (SRTF)

SJF is non-preemptive (run the process with the smallest total burst time). SRTF is preemptive (if a new process arrives with a shorter remaining time than the current one, preempt).

Pros: Optimal average waiting time.
Cons: Impossible to know future burst lengths (must predict). Starvation possible for long jobs.

Round Robin (RR)

This is the most common preemptive policy. Your notes about the timer interrupt directly enable RR. Each process gets a fixed time quantum (time slice) – e.g., 10 ms. When quantum expires, a timer interrupt forces a context switch, and the process is moved to the back of the ready queue.

Pros: Good response time, fair.
Cons: Too small quantum → many context switches (high overhead). Too large quantum → degenerates into FCFS (poor response for interactive tasks).

The 10% overhead rule helps choose the quantum: if context switch time is C (e.g., 1 µs), and you want overhead ≤ 10%, then quantum Q should be ≥ 10*C (e.g., 10 µs). But also must be large enough to amortize the cost.

Priority Scheduling

Each process has a priority (static or dynamic). The scheduler always runs the highest priority ready process. Preemptive or non-preemptive.

Problem: Starvation (low priority processes may never run).
Solution: Dynamic priority aging – increase priority of waiting processes over time. This is used in many real systems.

Multilevel Feedback Queue (MLFQ) – The practical winner

Used in modern Unix-like systems (including Linux, BSD, macOS). Multiple ready queues, each with a different priority level and time quantum.

Processes start in the highest priority queue. If they use their entire quantum without yielding (CPU‑bound), they are demoted to a lower priority queue (longer quantum). I/O‑bound processes stay in higher queues for quick response. This dynamically approximates SJF without needing future knowledge. It also prevents starvation via periodic promotion.

Here, the data structure is an array of queues, and the scheduler scans from highest priority queue downward for a non-empty queue.

An example

Let's trace an example to show how all the pieces fit together:

Process A is running. A timer interrupt occurs (every 10 ms). The OS saves A’s state (program counter, registers) into its PCB.
The scheduler looks at the ready queue (contains processes B, C, D, all in the ready state). Using Round Robin, it picks B.
The OS loads B’s state from its PCB into the CPU.
Process B runs for a while, then issues a read() system call to read from disk. The OS moves B from running to waiting (blocked on I/O) and removes it from the ready queue. B is placed in a separate I/O wait queue.
The scheduler now picks the next process in the ready queue – say C. This is a context switch due to I/O, not due to timer.
Later, the disk interrupt indicates B’s data is ready. The OS moves B from waiting to ready and inserts B back into the ready queue.
When B eventually reaches the front of the queue, it will be dispatched again – loading its saved state from its PCB (including the fact it was in the middle of the read system call).

This cycle illustrates how the scheduler uses the PCB, the process state model, and context switching to multiplex the CPU.

Further material

These notes focus on general-purpose scheduling. Advanced topics that build on these fundamentals:

Real-time scheduling – For systems where missing a deadline is catastrophic (car engines, medical devices). Policies like Rate Monotonic Scheduling (RMS) or Earliest Deadline First (EDF) guarantee that critical processes meet timing constraints.
Linux CFS (Completely Fair Scheduler) – Uses a red-black tree (not a simple queue) with a concept of "virtual runtime" to achieve perfect fairness. It's like a sophisticated, weighted round-robin.
Symmetric multiprocessing (SMP) – Multiple cores, each with its own scheduler runqueue, plus load balancing. Processes can be pinned to cores (affinity) to avoid costly cache migration.
Energy-aware scheduling – On mobile devices, scheduler may pack tasks onto fewer cores to let other cores sleep, saving battery.
Tickless scheduling – Modern Linux can disable the periodic timer interrupt when only one thread is ready, saving power. It uses a one-shot timer to wake up only when a timeout expires. This challenges the classic model but still relies on interrupts.
User-mode scheduling (UMS) – A hybrid where the kernel schedules “virtual processors” and user-level code schedules threads onto them, avoiding many kernel entries. This is like the one-to-many model but with kernel awareness of blocking.
Priority-based preemption – A higher-priority thread that becomes ready (e.g., after I/O) can preempt the current thread immediately, not just at the next timer tick. This requires the scheduler to run at interrupt time.

But all of these still rely on the same core ideas: PCBs, context switches, and a decision policy based on process state.

Subscribe for monthly AI research/project updates.