Processes, system calls and threads

An operating system does two jobs: it offers programs a convenient abstraction of the machine (files instead of disk sectors, processes instead of processor registers) and it manages its resources so that many programs can coexist without harming each other. The central concept is the process, a program in execution. In this lesson we look at protected mode and system calls, the structure of a process and its states, context switching, process creation in Unix with the proof of how many processes arise from a sequence of forks, threads and inter-process communication.

User mode and kernel mode

The processor has at least two privilege levels (Computer Systems lesson on input and output). In kernel mode all instructions can be executed and all memory and devices accessed; in user mode privileged instructions cause an exception. Programs run in user mode; when they need a service (reading a file, creating a process, allocating memory) they execute a system call: a special instruction (trap) passes control to the kernel at a fixed point, the kernel checks the parameters, performs the service and returns the result, going back to user mode.

The transition costs from tens to hundreds of nanoseconds, much more than a function call: this is why libraries batch operations (for example the C printf function accumulates characters in a buffer and calls the kernel only once).

The process

A process consists of:

• a private address space: code, global data, heap (dynamically allocated memory) and stack (Computer Science Foundations lesson on dynamic memory);
• the processor state: program counter, registers, stack pointer;
• system resources: open files, permissions, identifier (PID), parent process.

The kernel keeps all this in a process descriptor (PCB, process control block). During its life a process goes through several states.

On a CPU only one process runs at a time; the other ready ones wait in a queue, and those waiting wait for an event (the end of a disk read, a packet from the network, a key press). Choosing who runs is the job of the scheduler (lesson on scheduling).

Context switching

To move from one process to another the kernel saves the registers of the first in its PCB, loads those of the second and changes the address space (the page table, lesson on virtual memory). The switch takes a few microseconds, but the real cost is indirect: caches and the TLB contain data of the previous process and refill, slowly. A scheduler that switches too often wastes the machine.

Creating processes in Unix

In Unix a process is born by cloning another one with the fork call: the child is a copy of the parent (same memory, same open files), and fork returns 0 in the child and the child’s PID in the parent. To run another program the child calls exec, which replaces its code. The parent can wait for the child to finish with wait.

#include <stdio.h>
#include <unistd.h>
#include <sys/wait.h>

int main(void) {
    pid_t pid = fork();
    if (pid == 0) {                        /* child */
        execlp("ls", "ls", "-l", NULL);    /* becomes the ls program */
        perror("exec");                    /* reached only if exec fails */
        return 1;
    }
    waitpid(pid, NULL, 0);                 /* the parent waits for the child */
    printf("child %d finished\n", pid);
    return 0;
}

Copying all the memory would be slow; modern systems use copy-on-write: parent and child share the pages, marked read-only, and a page is duplicated only when one of the two modifies it.

Theorem. A program that executes fork calls in sequence, without checking their result, produces processes in total.

Proof. By induction on . With there is only the initial process, . Suppose that after forks there are processes; each continues from where it is and executes the next fork, creating a child. The processes become . ∎

With we get 1024 processes: this is the principle of the “fork bomb”, defended against by limiting the number of processes per user.

Threads

A thread is a flow of execution inside a process: it has its own registers and stack, but shares memory and files with the other threads of the same process. Creating one and switching between threads costs less than between processes, and communication is immediate through shared memory. The price is that every shared access must be synchronised (lesson on synchronisation), and a bug in one thread can corrupt the whole process. Threads are used to exploit several cores (lesson on multicore systems) and to avoid blocking an interactive program while it waits for the disk or the network.

Inter-process communication

Separate processes communicate through the kernel:

• pipes: a one-way byte channel between two processes; the shell uses them to connect commands, as in ls | grep txt, where the output of the first becomes the input of the second;
• shared memory: an area mapped into the address spaces of several processes, very fast but needing synchronisation;
• message queues and sockets, which also work between different machines (Telecommunication Networks lesson on layered architecture);
• signals: asynchronous notifications, such as interruption with Ctrl-C.

Unix filters, small programs that read a text stream and transform it, such as sed, grep and sort, are composed with pipes into powerful chains: this is the “do one thing and do it well” philosophy.