Processes, Threads, System Calls & IPC
The operating system's central abstraction is that a program in execution is a distinct, protected entity, and this chapter is about what that entity contains.
The organising fact is a division of labour: a process is a resource container, a thread is a schedulable execution. The process owns the address space, the open files and the accounting information. The thread owns a program counter, a register set and a stack.
Almost every question in this chapter is answered by deciding which of the two a given item belongs to. Is the heap shared between threads? It belongs to the process, so yes. Is the stack shared? It belongs to the thread, so no.
The second organising fact is that crossing the boundary between user code and the kernel is not free, and the exam repeatedly distinguishes the cheap crossing from the expensive one.
A mode switch changes privilege level while staying in the same process. A context switch replaces one execution's saved state with another's. The first costs hundreds of cycles; the second costs thousands, and more once caches are counted.
The third is that two processes cannot touch each other's memory by default, so any communication between them must go through machinery the kernel provides.
1. The Process and Its Control Block
A process is a program in execution together with everything the system must remember about it.
That information lives in the process control block, a kernel data structure created when the process is created and destroyed when it is reaped.
| Category | Contents |
|---|---|
| Identification | Process ID, parent process ID, user and group IDs |
| Scheduling | State, priority, scheduling queue pointers, accumulated CPU time |
| CPU state | Program counter, stack pointer, general registers, condition codes |
| Memory | Page table base register, segment or region descriptors, limits |
| Files | File descriptor table, working directory, root directory |
| Accounting | CPU time used, time limits, process start time |
| Signals | Pending signals, signal handler table, signal mask |
The CPU state fields are the ones saved and restored on a context switch. Everything else in the PCB persists across switches and is only consulted, not copied.
The address space of a process has four regions. Text holds the machine code and is read-only. Data holds initialised and uninitialised globals. Heap grows upward as the program allocates. Stack grows downward and holds activation records.
2. Process States and Transitions
The classical model has five states.
New is a process being created, with its PCB allocated but not yet admitted to the ready queue.
Ready means runnable and waiting only for a CPU.
Running means currently executing on a CPU. On a single-core machine exactly one process is running.
Waiting, also called blocked, means the process cannot proceed until some event occurs, typically the completion of an I/O operation.
Terminated means execution has finished but the PCB may still exist so the parent can read the exit status.
Five transitions connect them, and each has a distinct cause.
Admit moves new to ready. Dispatch moves ready to running. Interrupt or timer expiry moves running back to ready. A blocking request moves running to waiting. Event completion moves waiting to ready.
Note the asymmetry that examiners exploit: there is no transition from waiting directly to running. A process whose I/O completes goes to the ready queue and must be dispatched like any other. Assuming otherwise produces wrong answers in scheduling questions.
Suspended states are added when swapping is modelled. A ready or waiting process whose memory has been swapped to disk becomes ready-suspended or waiting-suspended, and must be swapped back before running.
3. Process Creation and Termination
In the UNIX model, creation and program loading are separate operations, and this separation is examined constantly.
The fork system call creates a near-duplicate of the calling process. The child gets a copy of the address space, a copy of the file descriptor table, and a new process ID.
fork returns twice. In the parent it returns the child's PID, a positive number. In the child it returns zero. On failure it returns negative one and no child is created.
The child does not restart the program. It resumes immediately after the fork call, with the same instruction pointer the parent had, which is why both continue with the rest of the code.
Modern systems implement fork with copy-on-write. The page tables of both processes point at the same physical frames, marked read-only, and a frame is copied only when one of them writes to it. This makes fork cheap even for large address spaces.
The exec family replaces the current process image with a new program. The PID, the parent, and the open file descriptors survive; the text, data, heap and stack are all replaced. A successful exec never returns, because there is no longer any code to return to.
wait blocks the parent until a child terminates and returns the child's PID and exit status. Reaping the child through wait is what finally frees its PCB.
A zombie is a process that has terminated but has not been waited for. It holds no memory and runs no code, but its PCB entry remains so the exit status is available. A program that forks many children and never waits leaks PCB entries.
An orphan is a process whose parent terminated first. It is reparented to the init process, which waits for it routinely, so orphans are cleaned up automatically while zombies are not.
4. Threads
A thread is a single flow of control within a process, and a process may contain many.
What is shared and what is private is the single most examined fact in this section.
| Shared across threads | Private to each thread |
|---|---|
| Text (code) segment | Program counter |
| Data segment (globals) | Register set |
| Heap | Stack |
| Open file descriptors | Thread ID |
| Signal handlers | Signal mask |
| Working directory, PID | errno value |
The rule follows directly from the organising principle. Anything the process owns is shared; anything an execution needs to know where it is and how it got there is private.
Threads are cheaper than processes on every axis. Creation avoids duplicating an address space. Switching between threads of the same process avoids reloading the page table base register and therefore avoids flushing translation caches. Communication needs no kernel call at all, because the heap is already shared.
The price is that a bug in one thread can corrupt another, since there is no protection boundary between them, and that shared data needs synchronisation.
Threading Models
Many-to-one maps all user threads onto a single kernel thread. Switching is fast because it needs no kernel involvement, but one blocking system call blocks the entire process, and the process cannot use more than one CPU.
One-to-one maps each user thread to its own kernel thread. Blocking affects only the blocking thread and true parallelism is available, but every thread consumes a kernel resource, so systems cap the count. This is what Linux and Windows use.
Many-to-many multiplexes some number of user threads onto a smaller or equal number of kernel threads, aiming for the benefits of both. It is complex to implement and has largely fallen out of favour.
User-level threads are invisible to the kernel, which schedules only the containing process. Kernel-level threads are scheduled by the kernel directly.
5. System Calls and Mode Switching
A system call is the interface through which user code requests a service the kernel alone may perform.
It is not an ordinary function call. The user program places a call number in a register, places arguments in registers or a buffer, and executes a trap instruction. The trap raises the privilege level and transfers control to a fixed kernel entry point.
The kernel validates the arguments, performs the service, places a result in a register, and executes a return-from-trap that restores the previous privilege level.
A mode switch is not a context switch. The mode switch changes only the privilege level; the same process continues executing, its address space is unchanged, and no PCB is saved. A system call that returns quickly involves no context switch at all.
A context switch is required only when the kernel decides to run a different process, which is why blocking calls cost far more than non-blocking ones.
Six categories cover the system call interface: process control, file management, device management, information maintenance, communication, and protection.
6. Interprocess Communication
Because processes have separate address spaces, the kernel must provide a channel.
Shared memory has the kernel map the same physical frames into two address spaces. After setup, communication proceeds at memory speed with no further kernel involvement, which makes it the fastest mechanism.
The cost is that the processes must synchronise themselves, since nothing prevents one reading a structure the other is halfway through writing.
Message passing has the kernel copy data between processes. It is slower because every message crosses the user-kernel boundary twice, but the kernel provides implicit synchronisation and the model extends naturally across machines.
Message passing has two axes of variation. Communication may be direct, naming the peer process, or indirect, through a named mailbox. Sends and receives may each be blocking or non-blocking, giving synchronous and asynchronous variants.
A pipe is a unidirectional byte stream with a fixed-size kernel buffer. A write blocks when the buffer is full and a read blocks when it is empty, which gives producer-consumer flow control for free.
Ordinary pipes require a common ancestor, because the pipe is inherited through the file descriptor table across fork. Named pipes, or FIFOs, appear in the file system and so can join unrelated processes.
Sockets generalise the idea across machines and are the basis of all network communication.
7. Worked Examples
Example 1. How many processes exist in total after the following, and how many lines does it print?
fork();
fork();
fork();
printf("hello\n");
Track the population after each call.
Before any fork there is one process. The first fork makes each existing process become two, giving 2.
The second fork executes in both processes, since the child resumed after the first fork and therefore reaches the second. Population doubles to 4.
The third doubles again to 8.
The general result is that unconditional forks in sequence produce processes, of which one is the original.
All eight reach the printf, so eight lines are printed and seven new processes were created.
Example 2. How many processes are created by the following?
fork();
if (fork() == 0) {
fork();
}
Work forward carefully.
After the first fork there are 2 processes, call them P and A.
Both execute the second fork, producing 4 processes: P and its new child B, and A and its new child C.
Now the condition selects only the children of the second fork. In P and A the second fork returned a positive PID, so the condition is false. In B and C it returned zero, so the condition is true.
B and C each execute the third fork, adding two more processes.
Total population is 6, so five processes were created beyond the original.
The trap here is assuming all four processes enter the if-block. Only those for which fork returned zero do, which is exactly half.
Example 3. Classify each item as shared between threads of one process or private to each thread: global array, local variable in a function, dynamically allocated buffer, file descriptor returned by open, return address of the current call.
A global array lives in the data segment, which the process owns, so it is shared.
A local variable lives on the stack, which each thread has its own of, so it is private.
A dynamically allocated buffer lives on the heap, which the process owns, so it is shared. This is worth stating carefully: the pointer to that buffer may be a local variable and hence private, but the memory it points at is shared, so passing the pointer to another thread gives it real access.
A file descriptor indexes the process-wide descriptor table, so it is shared. One thread can read from a file another thread opened.
A return address sits in the current stack frame, so it is private.
The one-line rule to carry into the exam: process-owned resources are shared, execution-state items are private.
Example 4. A system takes 2 microseconds for a mode switch and 20 microseconds for a full context switch. A process makes 5000 system calls per second, of which 20 percent block. What fraction of a second is spent on switching overhead?
Every system call costs a mode switch in and a mode switch out, so 5000 calls cost 5000 pairs.
At 2 microseconds per mode switch, and counting a call as one round trip of 2 mode switches, the mode-switch cost is microseconds.
The 20 percent that block additionally cause a context switch away and, when the I/O completes, a context switch back.
That is blocking calls, each incurring 2 context switches, so microseconds.
Total overhead is microseconds, which is 0.06 seconds, or 6 percent of the second.
Notice where the cost concentrates. Blocking calls are only a fifth of the total but account for two thirds of the overhead, which is why avoiding unnecessary blocking matters more than reducing call count.
Example 5. Two processes communicate through an ordinary pipe with a 4 KB kernel buffer. The producer writes 1 KB records as fast as it can; the consumer reads one record every 10 milliseconds. Describe the steady-state behaviour.
Initially the buffer is empty and the producer writes freely. After 4 writes the buffer holds 4 KB and is full.
The fifth write blocks, because a write to a full pipe blocks until space is available.
Each consumer read removes 1 KB and frees space, which wakes the blocked producer, which writes its record and fills the buffer again.
In steady state the producer is blocked almost all the time, waking briefly once every 10 milliseconds to write one record, and the throughput is set entirely by the consumer at 100 KB per second.
This is flow control without any explicit synchronisation code. The blocking semantics of the pipe are doing the work that a semaphore pair would otherwise have to do, which is exactly why pipes are the standard producer-consumer channel in shell pipelines.
If the consumer instead terminated, the next write would deliver a broken-pipe signal to the producer rather than blocking forever.
Example 6. A parent forks a child and immediately enters an infinite loop without calling wait. The child runs briefly and exits. What is the child's state, and what changes if the parent is killed?
The child becomes a zombie. It has terminated, so it holds no memory, no open files and consumes no CPU, but its PCB entry remains because the exit status has not been collected.
Only a wait by the parent removes it, and the parent is looping forever, so the entry persists.
When the parent is killed, the zombie is reparented to init. The init process calls wait in a loop as part of its normal operation, so it reaps the child and the PCB entry is finally released.
The asymmetry is the point. An orphan is harmless because init cleans up after it. A zombie is a leak because the responsible parent is not doing its job, and a program that forks thousands of children without waiting will eventually exhaust the process table.
Summary
A process is a resource container and a thread is a schedulable execution; deciding which of the two owns an item answers most questions in this chapter.
The process control block holds identification, scheduling state, CPU state, memory mappings, open files, accounting and signal information. Only the CPU state is saved and restored on a context switch.
The five states are new, ready, running, waiting and terminated. There is no direct transition from waiting to running; a process whose event completes joins the ready queue.
Fork duplicates a process and returns the child PID to the parent, zero to the child, and negative one on failure. Copy-on-write makes it cheap. Exec replaces the image but keeps the PID and open descriptors, and never returns on success.
A zombie has terminated but not been reaped and leaks a PCB entry. An orphan has lost its parent and is reparented to init, which reaps it.
Threads share the text, data, heap, file descriptors and signal handlers; each has its own program counter, registers, stack, thread ID and errno. Many-to-one is fast but blocks entirely on one call; one-to-one is what real systems use; many-to-many is a rarely used compromise.
A system call traps into the kernel, changing privilege level. A mode switch is not a context switch, and only a blocking call forces the expensive one.
Shared memory is fastest but requires explicit synchronisation. Message passing is slower but synchronises implicitly and extends across machines. Pipes give producer-consumer flow control through their blocking semantics, and require a common ancestor unless they are named.
