Process States

01 Introduction

A running program is not always running. It might be waiting for input from a user, blocked on a disk read, or simply queued behind another program that currently has the CPU. From the process's point of view, time passes without progress; from the operating system's point of view, the process is in a specific state that determines what can happen to it next.

The state model is the operating system's way of classifying every process in the system at every moment. It is the vocabulary the scheduler uses to decide which process runs next. It is the vocabulary the memory manager uses to decide which pages can be swapped out. It is the vocabulary you will use for the rest of the course when reasoning about what a program is doing.

This lesson presents the five-state model that describes almost every process on a modern general-purpose operating system. More elaborate models exist — the seven-state model adds Suspended states for processes swapped out to disk — but the five-state model captures the essential structure and is what the course will use throughout. By the end you will be able to read a state diagram, identify the transition that caused any particular state change, and observe process states directly on a live Linux system.

02 Learning objectives

This lesson contributes to U3.2 and to course learning outcomes CLO2 and CLO6.

03 Required reading

• Operating System Concepts — Chapter 3, Section 3.2 (Process States). The formal presentation of the five-state model and its transitions.
• OSTEP — Chapter 4, the discussion of process states and the OS's decision about which process to run. Pay particular attention to the diagram showing how a process moves between states during its lifetime.
• Linux man pages: man 1 ps (see the PROCESS STATE CODES section), man 5 proc (the stat file and its state field), man 2 wait (the blocking behaviour that produces the Blocked state).
• Love, R. — Linux Kernel Development, 3rd ed., Chapter 3, the section on process state. How Linux concretely implements the state model and what the state flags mean.

04 Core content

4.1 The five states

At any moment, a process is in exactly one of five states.

New

The process is being created. The kernel has allocated a process control block (PCB) but has not yet admitted the process to the set of runnable processes. In some systems, the program image is being loaded from disk. On Linux, this state exists only briefly, during the few microseconds of fork before the child is ready to run.

Ready

The process is able to run. All resources it needs for immediate execution are available, but the CPU is currently serving another process. A ready process is waiting in a queue for its turn. On a system with a single CPU core, only one process can be Running at a time; every other runnable process is Ready.

Running

The process has the CPU and its instructions are being executed. On a system with N CPUs, at most N processes can be Running at any instant — but many more may be Ready, waiting for a core.

Blocked

The process cannot proceed until some event occurs — typically the completion of an I/O operation, the arrival of a signal, or the acquisition of a lock. Even if a CPU were available, the process would not be able to use it. Blocked is sometimes called "waiting" or "sleeping" in different textbooks and in Linux itself.

Terminated

The process has finished executing. Its exit status may be held for the parent, but it will never run again. On Linux, this corresponds to the "zombie" state from Lesson 3.1 — the process has terminated but its parent has not yet reaped it.

The distinction between Ready and Blocked is subtle but fundamental. A Ready process could run if the scheduler chose it. A Blocked process could not, no matter what the scheduler chose. This is why the two states have different queues and are managed by different parts of the kernel. It is the single most important conceptual distinction in the model.

4.2 The state diagram

The relationships between states are conventionally drawn as a directed graph. Each state is a node; each transition is an arrow labelled with the event that triggers it.

4.3 The seven transitions

The model defines exactly seven transitions. Each is triggered by a specific event, and each requires the kernel to update the process's PCB and its position in the relevant queue.

4.4 Voluntary versus involuntary transitions

The transitions differ in who initiates them. This distinction matters because it determines whether the OS can guarantee fairness.

Voluntary transitions

The process itself gives up the CPU. Running → Blocked is the clearest example: the process calls read, or wait, or tries to acquire a lock that is held. The process is saying "I cannot proceed right now." Cooperative multitasking and early time-sharing systems relied entirely on voluntary yielding; if a process never yielded, the system stopped.

Involuntary transitions

The kernel takes the CPU away from a process that would prefer to keep running. Running → Ready is the primary example: a timer interrupt fires, or a higher-priority process becomes ready. This is preemption, and it is what makes modern systems responsive.

The transition Running → Ready is the only one that requires preemption. Without it, a process that never issues a blocking call and never exits could monopolise the CPU indefinitely. A hardware timer is therefore essential: it lets the kernel interrupt any running process at a known maximum interval and reclaim control. This is why the timer interrupt appeared as a prerequisite in the historical discussion in Lesson 1.2 — it is what makes preemptive multitasking possible.

4.5 Queues associated with states

The kernel maintains a queue for every state that can hold multiple processes simultaneously. Understanding the queues clarifies what "moving a process from state A to state B" actually means operationally: the kernel removes the process from one queue and inserts it into another.

• Job queue. All processes in the system, including those in New and Terminated. On Linux, this is not a single literal queue but the collection of all task_structs the kernel maintains.
• Ready queue. Processes in the Ready state, waiting for the CPU. On Linux, this is a per-CPU run queue, implemented as a red-black tree of runnable tasks keyed by their virtual runtime.
• Device queues. Processes blocked on each device or on other events. Linux maintains wait queues per event: one per open file, one per socket, one per lock, and so on. When the event occurs, the kernel walks the corresponding wait queue and wakes the blocked processes.

When a process changes state, the kernel moves it from one queue to another. On a busy system, these moves happen hundreds or thousands of times per second. The efficiency of the queue operations therefore matters directly to system performance; this is one reason the kernel uses data structures such as red-black trees and per-CPU queues rather than a single global list.

4.6 Why the Ready/Blocked distinction is fundamental

The most important conceptual takeaway from this lesson is the distinction between Ready and Blocked. It is worth restating in concrete terms.

Consider two processes on the same machine. Process A is CPU-bound: it is running a long computation with no I/O, and the scheduler has just preempted it. Process B has just called read on a file and is waiting for the disk to respond.

If the scheduler were forced to choose between these two — say, because the currently running process has just exited — it would be absurd to consider B. B cannot run until the disk responds; dispatching B would be a wasted context switch and the CPU would be idle for the duration of the disk operation. Process A, on the other hand, is perfectly ready: it can resume immediately.

This is exactly what the Ready queue encodes. It is the set of processes that could actually make progress if given the CPU. Blocked processes are not in it, because they cannot. The distinction is not a classification of convenience; it reflects the physical reality that a process waiting on a device cannot use a CPU even if one is offered.

4.7 Process states on Linux

Linux implements the five-state model but with additional detail. The STAT column of ps and the state field in /proc/<pid>/stat encode the current state of each process. The common codes are:

Note that Linux merges Running and Ready into a single R code. This is because Linux's scheduler does not maintain a strict distinction: a task on the run queue is considered "running" from the kernel's point of view even if it is currently not executing. The distinction that matters for the scheduler — is it runnable, or is it blocked? — is captured by the difference between R and S/D.

Linux also distinguishes interruptible from uninterruptible sleep. The former can be interrupted by a signal, allowing the process to handle the signal and then continue or exit. The latter — used for short periods during critical I/O operations — cannot be interrupted by a signal, because doing so would leave the kernel in an inconsistent state. Processes in the D state are the ones that appear unkillable; kill -9 has no effect until the I/O completes.

4.8 What the diagram does not show

The five-state model is a simplification. It omits several things that real systems do:

• Suspended states. A process that has been swapped out to disk, or is otherwise not in physical memory, is in a state the five-state model does not name. The seven-state model adds "Suspended Ready" and "Suspended Blocked" for these cases.
• Multiple blocked reasons. A process may be blocked waiting for one of several events; the model shows a single Blocked state regardless.
• Threads. A process in the five-state model is a single thread of control. Once we introduce threads in Unit 4, each thread has its own state, and a process may be Ready, Blocked, and Running simultaneously in its different threads.
• Real-time states. Real-time processes have additional scheduling states that the general model does not cover.

None of these omissions change the fundamentals. The five-state model is the right level of abstraction for reasoning about general-purpose process behaviour, and everything else is a refinement.

4.9 How a process moves between states: a concrete walkthrough

To make the model concrete, consider what happens to a single process — an instance of a text editor — as you use it:

1. You type vim notes.txt at the shell. The shell forks a child. The child begins in the New state while its address space is being set up.
2. Admission. The kernel confirms the child has its resources. Transition: New → Ready. The process joins the ready queue behind any other runnable work.
3. Dispatch. The scheduler selects the process. Transition: Ready → Running. The kernel performs a context switch and vim begins executing.
4. vim reads notes.txt. It calls open, which may or may not block (usually the directory and inode are in cache). Then read. Assume the file is on disk and not cached. The read system call cannot return immediately. Transition: Running → Blocked. The process is moved to the wait queue for the storage device.
5. Timer preempts the editor? No — the process is Blocked, so no preemption is involved. It is simply not on the ready queue anymore.
6. The disk completes. The device controller raises an interrupt. The kernel's interrupt handler moves the editor's process back to the Ready state. Transition: Blocked → Ready.
7. The editor is dispatched again. Transition: Ready → Running. Its read call returns, and vim continues as if nothing had happened.
8. You type a character. vim reads from its terminal via read on stdin, blocks again, and the cycle repeats. This pattern repeats hundreds of times per minute while you edit.
9. You save and quit. vim writes the file with write and calls exit. Transition: Running → Terminated. The exit status is held for the shell.
10. The shell reaps. It calls wait, receives the exit status, and prints the next prompt.

If you were to watch this process with ps during the run, you would see the STAT column changing between S (when waiting for input), R (during the brief bursts of processing the input), and possibly D (during the initial file read). This is what the state model looks like in practice.

05 Worked example

A small program that drives a process through several states on demand, so that you can watch the transitions happen.

#include <stdio.h>
#include <unistd.h>
#include <sys/wait.h>

int main(void) {
    pid_t pid = fork();

    if (pid < 0) {
        perror("fork");
        return 1;
    } else if (pid == 0) {
        /* Child: block for a while, then exit */
        printf("child: pid = %d — about to sleep\n", getpid());
        sleep(30);
        printf("child: waking up and exiting\n");
        return 0;
    } else {
        /* Parent: sleep briefly, then check child's state */
        printf("parent: pid = %d, child = %d\n", getpid(), pid);
        sleep(2);
        printf("parent: waking up, will wait for child\n");
        wait(NULL);
        printf("parent: child reaped, exiting\n");
    }
    return 0;
}

06 Interactive activity

07 Knowledge check

08 Unit discussion

09 Practice exercise

10 Summary

• A process occupies one of five states at every moment: New, Ready, Running, Blocked, Terminated.
• Ready means "could run if given the CPU"; Blocked means "cannot proceed until an event occurs." The distinction is the most important in the model.
• Seven transitions connect the states. Of these, Running → Ready is the only one that requires preemption, and preemption requires hardware timer support.
• Transitions are either voluntary (the process gives up the CPU, e.g., Running → Blocked) or involuntary (the kernel takes the CPU away, e.g., Running → Ready).
• The kernel maintains queues for the multi-process states: the job queue (all processes), the ready queue (Ready processes), and device queues (blocked processes waiting on specific events).
• On Linux, the state is exposed through the STAT column of ps and the third field of /proc/<pid>/stat. Common codes are R (running/runnable), S (interruptible sleep), D (uninterruptible sleep), T (stopped), and Z (zombie).
• The five-state model omits some details — suspended states, multiple blocked reasons, per-thread states, and real-time extensions — but captures the essential structure that all of these refine.

11 References

• Silberschatz, A., Galvin, P. B., & Gagne, G. Operating System Concepts, 10th ed., Chapter 3, Section 3.2.
• Arpaci-Dusseau, R. H., & Arpaci-Dusseau, A. C. Operating Systems: Three Easy Pieces, Chapter 4. Available online at ostep.org.
• Love, R. Linux Kernel Development, 3rd ed., Chapter 3 (Process Management), especially the process-state discussion. Addison-Wesley, 2010.
• Linux man-pages: man 1 ps (PROCESS STATE CODES), man 5 proc (the /proc/<pid>/stat format), man 2 wait, man 7 signal.
• Bach, M. J. The Design of the UNIX Operating System, Chapter 6. Prentice Hall, 1986. (Classical presentation of the process state model.)