Processes, PCB and Process States

A program is a passive file of instructions on disk. A process is a program in execution: the code together with a program counter, register values, a stack, a heap, open files and everything else the OS must remember to stop it and later continue it exactly where it left off. Two users running the same editor have one program and two processes.

The process is the unit the OS schedules, protects and accounts for. Scheduling, synchronization, deadlock and memory management all build on the life cycle described here: a process is created, waits for the CPU, runs, waits for I/O, runs again, and finally terminates. The kernel records all of this in one data structure per process, the process control block.

The gap between heap and stack is what lets both grow. A stack overflow is the stack running into something it should not.

The PCB (called a task structure in Linux) holds everything the kernel needs about one process:

The PCB is kernel data. It lives in protected kernel memory, not in user-accessible process memory, so a process cannot change its own priority or page table by writing memory.

Legal transitions.

Impossible transitions. Waiting to Running directly (a woken process must go through Ready and be chosen), Ready to Waiting (only a running process can issue the request that blocks it), and New to Running. In a non-preemptive system the Running to Ready edge is used only when a process yields voluntarily; it is never forced.

Counting limits on $n$ CPUs. At most $n$ processes are Running at any instant; Ready and Waiting have no fixed limit. With one CPU and $k$ processes in memory, at most one is Running and up to $k$ can be Ready or Waiting.

When memory is short, the medium-term scheduler swaps a whole process out to disk. That adds two states, giving the seven-state model: Ready-suspended (could run if it were in memory) and Blocked-suspended (waiting for an event and swapped out). A blocked-suspended process whose event occurs becomes ready-suspended; it becomes ready again when it is swapped in.

The degree of multiprogramming is the number of processes in memory. An I/O-bound process spends most time waiting for I/O and has short CPU bursts; a CPU-bound process has long bursts. A good long-term scheduler mixes both, so that the CPU and the devices are busy at the same time.

Switching the CPU from process A to process B means saving A's CPU state into A's PCB and loading B's state from B's PCB, plus switching the address space (page-table base register and, on many machines, flushing or tagging the TLB). The switch does no useful work for either process: it is pure overhead, typically microseconds, and it grows with the amount of hardware state to save.

Mode switch versus context switch. System calls and interrupts from user mode enter kernel mode; they may return to the same process or trigger a context switch. A context switch changes the running process/thread and executes kernel scheduling code, but need not itself change privilege mode if the CPU is already in kernel mode.

When a process calls exit, its memory and files are released but a small entry (PID and exit status) stays until the parent calls wait. Until then the dead child is a zombie. If the parent terminates first, the child becomes an orphan; on UNIX systems it is adopted by init (PID 1) or a designated subreaper, which collects it when it dies.

Tanenbaum's simple probabilistic model assumes each of $n$ processes in memory independently spends a fraction $p$ of its time waiting for I/O. The CPU is idle only when all $n$ are waiting at once, so

This is an approximation: it ignores that processes compete for the one CPU, so it is optimistic for large $n$. It still explains why adding processes raises utilization with diminishing returns.

If each process runs for a quantum $q$ and every switch costs $s$, the fraction of CPU time doing useful work is

assuming every quantum is fully used and then followed by a switch.

With $p = 0.8$ (processes wait 80% of the time) and $n = 4$: $U = 1 - 0.8^{4} = 1 - 0.4096 = 0.5904$, about 59%.

How many processes are needed for at least 90% utilization? We need $0.8^{n} \le 0.1$. Since $0.8^{10} \approx 0.107$ and $0.8^{11} \approx 0.0859$, the answer is $n = 11$.

A process runs alone on one CPU with the burst pattern CPU 3, I/O 2, CPU 4, I/O 1, CPU 2, with no preemption. It enters Ready once on admission, then: Ready to Running 3 times (one per CPU burst), Running to Waiting 2 times (one per I/O burst), Waiting to Ready 2 times, Running to Terminated once. Its turnaround time, measured from admission, is $3 + 2 + 4 + 1 + 2 = 12$ units, since nothing else competes.

With $q = 10$ ms and $s = 1$ ms, $E = 10/11 \approx 0.909$: about 9.1% of CPU time is lost to switching. Cutting the quantum to $q = 2$ ms gives $E = 2/3$, so a third of the time is overhead. This is why the quantum must be large compared with the switch time.

Common misconceptions.