Processes & Threads

A process is the kernel's name for "a program that is running": an address space, one or more threads of execution, and a record of everything the kernel needs to manage it. In this lesson your program is the kernel's process table. It creates children with fork, turns exiting processes into zombies, hands orphans to init, and reaps zombies in wait, with the same rules as Unix.

What the kernel remembers about each process

Each process has a process control block (in xv6 it is struct proc). The important fields:

The lifecycle: embryo (being built), runnable (ready), running, sleeping (blocked on something), zombie (exited, not yet reaped). Your table needs only runnable and zombie.

fork: the only way in

fork creates a copy of the calling process: same memory contents (copied, or shared copy-on-write, later lesson), same open files. It returns twice: the child gets 0, the parent gets the child's new pid. Everything else on a Unix system follows from this one primitive: the shell forks, and the child replaces itself with the program you asked for. Process ids grow upward and are not handed out again while an entry exists.

exit, zombies and wait

When a process exits it cannot simply vanish, because its parent may want to know how it ended. So the kernel frees its memory but keeps the table entry as a zombie, holding only the pid and the exit status. The parent collects it with wait, which returns the child's pid and status and finally frees the entry. wait has three outcomes:

1. a child is a zombie: reap one (the lowest pid, for determinism) and return it;
2. children exist but none has exited: the caller would block;
3. no children at all: error ECHILD.

Orphans and init

If a process exits while it still has children, they must not be left pointing at a dead parent. The kernel reparents them, live or zombie, to init, process 1. Init's whole job is a loop around wait, so adopted zombies are always eventually reaped. This also explains why init must never exit: with no ancestor left to adopt orphans the kernel panics.

A worked trace

After that the table holds pids 1, 3 and 4, with 3 and 4 children of init.

Threads: processes that share

A thread is a schedulable flow of control. A process is one address space plus one or more threads sharing it. Each thread needs its own stack and saved registers; the code, heap and open files are shared. Linux makes both with one system call that takes flags saying what to share, and the scheduler treats them alike.

Common mistakes

• Reusing a pid, or numbering from 0.
• Removing the exiting process's entry immediately, so the parent's wait finds nothing.
• Forgetting to reparent zombie children as well as live ones.
• Letting wait return a zombie that belongs to somebody else's children.

Your exercise

Implement the process table commands in the exercise. The starter parses commands and prints tables; you write the logic of fork, exit and wait.