§4.4–4.6Process States … Summary

A process, we said, is defined by its machine state. But a process also has a life — it gets paused, resumed, and parked while waiting for slow devices. That life is captured by a small set of states, an idea dating to the earliest computer systems.

4.4 Process States

In the simplified view, a process is in one of three states:

• Running running Process state: executing instructions on a processor. defined in ch. 4 — open in glossary : it is executing instructions on a processor.
• Ready ready Process state: able to run, but the OS has chosen not to run it at this moment. defined in ch. 4 — open in glossary : it could run, but the OS has chosen not to run it at this moment.
• Blocked blocked Process state: waiting for an event (e.g., I/O completion) before becoming ready again. defined in ch. 4 — open in glossary : it performed an operation (classically: initiated disk I/O) that makes it not ready until some event occurs.

Mapped to a graph, that’s Figure 4.2 — here, one you can drive:

Two things the diagram encodes: ready↔running transitions happen at the OS’s discretion (being picked is scheduled, being benched is descheduled); and once blocked, a process stays blocked until its event fires, at which point it becomes ready — not necessarily running.

Now trace two processes through these states. First the boring case — both are pure CPU users:

Then the interesting one — Process0 issues an I/O partway through:

Step through tick 4 and tick 7 carefully: the trace contains two OS decisions. When Process0 blocked, the system chose to run Process1 (keeping the CPU busy — better resource utilization); and when the I/O completed, it chose not to switch back right away. Was that second call right? The book pointedly asks what you think — and defers the answer to the scheduler scheduler The OS component whose policy decides which ready process runs next, using history, workload knowledge, and metrics. defined in ch. 4 — open in glossary chapters.

4.5 Data Structures

The OS is a program too, and it tracks all of this in data structures. To know the state of every process it keeps a process list process list The OS data structure tracking all processes in the system (a.k.a. task list). defined in ch. 4 — open in glossary (a.k.a. task list): who is ready, who is running, and which blocked process to wake when an I/O event completes. Here is what a real (small) OS tracks — the xv6 kernel’s process structure, Figure 4.5:

// the registers xv6 will save and restore
// to stop and subsequently restart a process
struct context {
  int eip;
  int esp;
  int ebx;
  int ecx;
  int edx;
  int esi;
  int edi;
  int ebp;
};

// the different states a process can be in
enum proc_state { UNUSED, EMBRYO, SLEEPING,
                  RUNNABLE, RUNNING, ZOMBIE };

// the information xv6 tracks about each process
// including its register context and state
struct proc {
  char *mem;                  // Start of process memory
  uint sz;                    // Size of process memory
  char *kstack;               // Bottom of kernel stack
                              // for this process
  enum proc_state state;      // Process state
  int pid;                    // Process ID
  struct proc *parent;        // Parent process
  void *chan;                 // If !zero, sleeping on chan
  int killed;                 // If !zero, has been killed
  struct file *ofile[NOFILE]; // Open files
  struct inode *cwd;          // Current directory
  struct context context;     // Switch here to run process
  struct trapframe *tf;       // Trap frame for the
                              // current interrupt
};

Figure 4.5: The xv6 Proc Structure (similar — but far more complex — structures exist in Linux, macOS, and Windows; look them up).

The struct context is the register context register context The saved register contents of a stopped process; restoring them resumes the process. defined in ch. 4 — open in glossary : when a process is stopped, its registers are saved here; restoring them (putting the values back into the physical registers) resumes the process exactly where it left off. That save/restore trick is the context switch context switch The mechanism that stops one program and starts another on a CPU by saving and restoring register state. defined in ch. 4 — open in glossary , dissected in chapter 6.

Notice xv6’s state list is richer than our three: UNUSED (slot free), EMBRYO — an initial state while creation is in progress, SLEEPING (blocked), RUNNABLE (ready), RUNNING, and ZOMBIE — a final state where the process has exited but not yet been cleaned up. The zombie zombie Final process state: exited but not yet cleaned up, so the parent can read the return code via wait(). defined in ch. 4 — open in glossary state is genuinely useful: it lets the parent examine the child’s return code (zero = success, by UNIX convention) before making one final wait()-style call that tells the OS to clean up the corpse.

4.6 Summary

The process — a running program, described by its address space, its registers (PC and friends), and its I/O state — is the OS’s most basic abstraction, and it lives out its life across the running/ready/blocked states under the OS’s direction. Next up, the nitty-gritty promised by the mechanism/policy split of the previous section: first the mechanisms (the process API, then limited direct execution), then the scheduling policies on top.