Processes

A program is a file on disk: passive instructions. A process is a program running: the code plus everything that changes as it runs. Open the same program twice and you have two processes.

What a process has

In memory, each process has its own address space:

 high addresses  ┌──────────────┐
                 │    stack     │  local variables, function calls; grows down
                 │      ↓       │
                 │      ↑       │
                 │     heap     │  malloc; grows up
                 ├──────────────┤
                 │     data     │  global and static variables
                 ├──────────────┤
 low addresses   │     text     │  the machine code
                 └──────────────┘

The kernel keeps a process control block (PCB) for each process: its ID (pid), its state, the saved program counter and registers, its memory map, its open files, and scheduling information such as its priority.

Process states

            admitted          dispatch
   new ───────────→ ready ───────────→ running ────→ terminated
                     ↑   ←───────────    │      exit
                     │    interrupt      │
                     │   (time is up)    │ waits for I/O
                     │                   ↓
                     └───────────── waiting
                        I/O done

• ready: could run, waiting for a CPU. The ready processes form the ready queue.
• running: on a CPU now. One CPU core runs one process at a time.
• waiting (or blocked): waiting for something, such as a disk read or a key press. It cannot use the CPU even if it is free.

#include <stdio.h>

enum state { NEW, READY, RUNNING, WAITING, TERMINATED };
const char *names[] = { "new", "ready", "running", "waiting", "terminated" };

struct pcb {
    int pid;
    enum state state;
    int pc;          /* saved program counter */
};

struct pcb *running = 0;

/* The kernel stops the running process (if any) and continues `next`. */
void switch_to(struct pcb *next, int cpu_pc) {
    if (running != 0) {
        running->pc = cpu_pc;        /* save the old process's place */
        running->state = READY;
    }
    next->state = RUNNING;
    running = next;
}

/* The running process asks for I/O: it waits, and nobody has the CPU. */
void block(int cpu_pc) {
    running->pc = cpu_pc;
    running->state = WAITING;
    running = 0;
}

int main(void) {
    struct pcb a = { 100, NEW, 0 };
    struct pcb b = { 200, NEW, 0 };
    a.state = READY;                 /* both are admitted */
    b.state = READY;

    switch_to(&a, 0);                /* a runs */
    switch_to(&b, 40);               /* time is up: a stopped at 40, b runs */
    block(12);                       /* b asks for a disk read at 12 */
    switch_to(&a, 0);                /* a continues from its saved pc */
    b.state = READY;                 /* b's read is done */
    a.state = TERMINATED;            /* a exits */

    printf("a: pc %d, %s\n", a.pc, names[a.state]);
    printf("b: pc %d, %s\n", b.pc, names[b.state]);
    return 0;
}

The example keeps two PCBs and moves them through the states. Watch the context switch (switch_to): the kernel saves the running process's program counter into its PCB and loads the other one's. A context switch does no useful work for either process, so it is pure overhead; switching too often wastes the CPU.

Creating processes on UNIX

pid_t pid = fork();          /* makes a copy of this process */
if (pid == 0) {
    execlp("ls", "ls", NULL); /* child: replace the program with ls */
} else {
    wait(NULL);               /* parent: wait for the child to finish */
    printf("child %d done\n", pid);
}

• fork() creates a child, a copy of the parent. It returns twice: 0 in the child, and the child's pid in the parent.
• exec replaces the process's program with another one; the pid stays.
• wait makes the parent sleep until a child ends; exit ends a process.

A child that has ended but whose parent has not called wait yet is a zombie: its PCB stays so the parent can collect its exit status. A child whose parent ended first is an orphan, and is adopted by init. (StepVioz's C runner has no fork, so this code is shown, not run.)

Mark lesson complete