Computer Systems II: Operating Systems

These notes follow Operating System Concepts by Silberschatz, Galvin and Gagne (9th edition) [1]; figures marked “after Galvin” are redrawn from the book.

Overview

Operating-System Operations

Modern operating systems are interrupt driven: when there is nothing to do, the OS waits, and every event is signalled by an interrupt or a trap.

Dual-Mode Operation

For proper execution, the OS must distinguish between OS code and user-defined code. Hardware therefore provides (at least) two separate modes of operation, selected by a mode bit:

Kernel mode is also called supervisor, system or privileged mode. When a user application requests a service from the OS (via a system call), the system must transition from user to kernel mode to fulfil the request.

• At system boot time, the hardware starts in kernel mode. The OS is then loaded and starts user applications in user mode.
• Whenever a trap or interrupt occurs, the hardware switches from user mode to kernel mode. Hence, whenever the OS gains control of the computer, it is in kernel mode.
• The system always switches to user mode (sets the mode bit to 1) before passing control to a user program.

The instruction to switch to kernel mode is itself a privileged instruction. (This means an instruction that sets the mode bit directly. The trap or system-call instruction that a user program uses to enter the kernel is not privileged; it switches mode only by jumping to a fixed kernel entry point.) Other examples include I/O control, timer management and interrupt management.

Note. Without hardware dual mode, a buggy user program can wipe out the OS. Early PC operating systems ran on processors with no mode bit, so any program could overwrite the operating system. CPUs can also support more than two modes, e.g. a separate mode for a virtual machine manager, or the four privilege levels (rings) of x86.

Timer

The OS must keep control over the CPU even if a user program gets stuck in an infinite loop, or never calls system services and so never returns control to the OS. A timer can be set to interrupt the computer after a specific period. The period can be fixed or variable; a variable timer is usually implemented with a fixed-rate clock and a counter:

• the OS sets the counter (a privileged instruction);
• every clock tick decrements it;
• when it reaches 0, an interrupt occurs and the OS regains control. It can then treat the program as having exceeded its time limit.

Ways into the Kernel

There are only three ways for the CPU to switch from user mode to kernel mode: an interrupt, a trap (system call), or an exception caused by the running instruction (a fault or an abort). In each case it jumps to a handler at a fixed address taken from the interrupt vector table, so a user program can choose which service it wants but never what code runs in kernel mode [2].

When one of these occurs, the hardware atomically switches to kernel mode and the kernel stack, saves the PC (the resume address) and processor state, and jumps to the handler. A return-from-exception instruction later restores the state and drops back to user mode; if the kernel changes the saved state before returning, the CPU resumes a different process, which is exactly how a context switch happens [3].

Note. Since an interrupt can arrive between any two user-mode instructions, a program has no guarantee about the time between two of its own instructions. This is why the race conditions in the synchronization section can happen at all.

Note. A recoverable fault is invisible to the program. For example, if a recursive program runs past the end of its stack, the fault handler can allocate more stack memory and restart the faulting instruction. The same mechanism lets a virtual machine run in user mode: each privileged action it attempts faults to the real OS, which emulates it (trap-and-emulate) [2].

System Calls

Control is switched back to the OS via an interrupt, a trap or a system call. A system call usually takes the form of a trap to a specific location in the interrupt vector (a generic trap instruction, or a dedicated one such as syscall on MIPS).

When a system call is executed, it is treated by the hardware as a software interrupt: control passes through the interrupt vector to a service routine in the OS, and the mode bit is set to kernel mode. The kernel checks which call was made and that its parameters are legal, executes the request, and returns control to the instruction after the call.

Some examples of system calls (UNIX):

• fork(): creates a new process. The parent process calls fork() and a child process is created.
• exec(): replaces the memory image of a process with a new program.
• wait(): makes the parent sleep until a child terminates.
• exit(): terminates the calling process.
• sbrk(): used by malloc to increase the size of the heap.

Note. malloc() does not always result in a system call. It hands out memory from the heap the process already has, and only calls sbrk()/brk() (or mmap() for large blocks) when the heap has to grow.

Process Management

Processes

A program is a passive entity (an executable file on disk); a process is active. In memory, a process has the following sections:

• Text: the program code.
• Data: global variables.
• Heap: memory dynamically allocated at run time.
• Stack: temporary data such as function parameters, return addresses and local variables.

Process States

As a process executes, it changes state. A process may be in one of the following states:

• New: the process is being created.
• Running: instructions are being executed.
• Waiting: the process is waiting for some event to occur (e.g. I/O completion or a signal).
• Ready: the process is waiting to be assigned to a CPU.
• Terminated: the process has finished execution.

Process Control Block

Each process is represented in the OS by a process control block (PCB), also called a task control block. It contains the pieces of information associated with the process:

In Linux the PCB is the C structure task_struct, and all active processes are kept in a doubly linked list of them.

Process Scheduling

• The objective of multiprogramming is to have some process running at all times, to maximize CPU utilization.
• The objective of time sharing is to switch the CPU among processes so frequently that users can interact with each program while it is running.
• To meet these objectives, the process scheduler selects an available process for execution on the CPU. On a single-processor system there is never more than one running process.

Scheduling Queues

• As processes enter the system, they are put into a job queue, which consists of all processes in the system.
• The processes that are residing in main memory and are ready and waiting to execute are kept on a list called the ready queue. It is generally stored as a linked list: a ready-queue header contains pointers to the first and final PCBs, and each PCB points to the next PCB in the ready queue.
• Suppose a process makes an I/O request to a shared device such as a disk. Since there are many processes, the disk may be busy with another process’s request, so the process may have to wait. The list of processes waiting for a particular I/O device is called a device queue, and each device has its own device queue.

A common representation of process scheduling is a queueing diagram: rectangles are queues, circles are the resources that serve them, and arrows show the flow of processes.

A new process is initially put in the ready queue. It waits there until it is selected for execution, or dispatched. Once the process is allocated the CPU and is executing, one of several events could occur:

• The process could issue an I/O request and then be placed in an I/O queue.
• The process could create a new child process and wait for the child’s termination.
• The process could be removed forcibly from the CPU, as a result of an interrupt, and be put back in the ready queue.

In the first two cases, the process eventually switches from the waiting state to the ready state and is put back in the ready queue. A process continues this cycle until it terminates, at which time it is removed from all queues and has its PCB and resources deallocated.

Schedulers

A process migrates among the various scheduling queues throughout its lifetime; the OS selects processes from these queues with a scheduler.

Long-term scheduler (job scheduler). Selects processes from those spooled to mass storage (typically a disk) and loads them into memory for execution.

• It executes much less frequently, minutes may separate the creation of one process and the next.
• It controls the degree of multiprogramming (the number of processes in memory). If the degree of multiprogramming is stable, the average rate of process creation must equal the average departure rate, so the long-term scheduler may need to be invoked only when a process leaves the system.
• Because of the longer interval between executions, it can afford to take more time to decide which process should be selected.
• It should select a good process mix of I/O-bound and CPU-bound processes. If all processes are I/O bound, the ready queue will almost always be empty and the short-term scheduler will have little to do. If all are CPU bound, the I/O waiting queue will almost always be empty and devices will go unused.

Note. On some systems the long-term scheduler is absent or minimal: time-sharing systems such as UNIX and Windows simply put every new process in memory for the short-term scheduler.

Short-term scheduler (CPU scheduler). Selects from among the processes that are ready to execute and allocates the CPU to one of them. It executes very frequently (often at least once every 100 ms), so it must be fast.

Medium-term scheduler. Some OSs, such as time-sharing systems, introduce an additional, intermediate level of scheduling. The key idea is that it can be advantageous to remove a process from memory (and from active contention for the CPU), and thus reduce the degree of multiprogramming. Later, the process can be reintroduced into memory and its execution continued where it left off. This scheme is called swapping.

Swapping may be needed to improve the process mix, or because a change in memory requirements has overcommitted the available memory.

Context Switch

Interrupts cause the OS to change a CPU from its current task to a kernel routine. When an interrupt occurs, the system needs to save the current context of the process running on the CPU so that it can restore that context when its processing is done, essentially suspending the process and then resuming it. The context is represented in the PCB of the process.

• Context-switch time is pure overhead, since the system does no useful work while switching. A typical switch takes a few microseconds (Galvin, 9th edition, says milliseconds).
• Context-switch times are highly dependent on hardware support. Some processors provide multiple register sets, so a context switch only changes a pointer to the current set.

Operations on Processes

Process Creation

During the course of execution, a process may create several new processes. The creating process is called a parent process, and the new processes are called the children of that process, forming a tree of processes. Most OSs identify processes by a unique process identifier (pid).

When a process creates a new process, two possibilities exist for execution:

1. The parent continues to execute concurrently with its children.
2. The parent waits until some or all of its children have terminated.

There are also two address-space possibilities:

1. The child process is a duplicate of the parent process (same program and data).
2. The child process has a new program loaded into it.

In UNIX, a new process is created by the fork() system call. Both processes continue execution after the fork(), with one difference: fork() returns the pid of the child in the parent, and 0 in the child.

One of the two processes typically uses the exec() system call to replace the process’s memory space with a new program. The parent can create more children, or, if it has nothing else to do while the child runs, call wait() to move itself off the ready queue until the child terminates.

pid_t pid = fork();
if (pid < 0) {                 /* error */
    fprintf(stderr, "fork failed");
} else if (pid == 0) {         /* child */
    execlp("/bin/ls", "ls", NULL);
} else {                       /* parent */
    wait(NULL);                /* wait for the child to complete */
    printf("child complete");
}

What fork() actually copies is the caller’s memory (code, globals, heap and stack), its registers and its open files. Because the child has the same registers, it has the same program counter and stack pointer, so it too “returns” from fork(), just with the value 0 [4].

printf("pid = %d\n", getpid());
i = fork();
printf("fork returned %d, getpid = %d, getppid = %d\n", i, getpid(), getppid());

pid = 914
fork returned 915, getpid = 914, getppid = 381     <- parent
fork returned 0,   getpid = 915, getppid = 914     <- child

• Order is not guaranteed. Either the parent or the child may run first after fork(); on another run the two last lines can appear the other way round.
• Address spaces are separate. If the child changes a variable, the parent’s copy is unaffected.
• Open files are shared. Both processes point to the same open-file entry in the kernel, so they share the file offset: writes by one advance the offset for the other.
• Copy-on-write. Copying the whole address space would make fork() expensive, especially since the child usually calls exec() straight away. Modern Unix marks the pages read-only and shared, and copies a page only when one of the processes writes to it.
• exec() does not return on success (the old program is gone); it returns −1 only on error.

Counting processes. Every process that executes a fork() becomes two, so after $n$ successive fork() calls (e.g. for (i = 0; i < n; i++) fork();) there are $2^n$ processes: the original and $2^n - 1$ children. A printf placed after them runs $2^n$ times. When a fork() is inside a condition such as if (fork() == 0), only the processes that take that branch double.

The process tree for $n = 3$ is a full binary tree with one level per fork(). At each node the left branch is the calling process carrying on and the right branch is the new child, so every right branch is created by the node it hangs from. The leaves are the 8 processes that run the code after the loop.

In general the original process has $n$ children, and a process created in iteration $i$ ($i = 0, \ldots, n-1$) goes on to create $n - 1 - i$ children of its own.

Note. Buffered output is part of the address space, so it is copied too. If stdout is redirected to a file, printf("Before forking\n") may still be sitting in the stdio buffer at the time of fork(), and the line then appears twice in the file (once flushed by each process). On a terminal stdout is line-buffered, so it appears once [4].

Process Termination

A process terminates when it finishes executing its final statement and asks the OS to delete it with the exit() system call. At that point, the process may return a status value to its parent (collected via the wait() system call), and all its resources are deallocated by the OS.

A parent may terminate the execution of one of its children for a variety of reasons:

• The child has exceeded its usage of some of the resources it has been allocated.
• The task assigned to the child is no longer needed.
• The parent is exiting, and the OS does not allow a child to continue if its parent terminates.

In the last case, if a process terminates, all its children must also be terminated. This is referred to as cascading termination.

All processes transition to this state when they terminate, but generally only briefly. Once the parent calls wait(), the pid of the zombie process and its entry in the process table are released.

Linux and UNIX address this scenario by assigning the init process as the new parent of orphan processes. init periodically invokes wait(), thereby collecting the exit status of any orphan and releasing its pid and process-table entry.

For example, if a parent exits while its child is sleeping, the child’s getppid() returns 1 (the pid of init) once it wakes up [4].

Interprocess Communication

A process is independent if it cannot affect or be affected by other processes, and cooperating otherwise. Cooperating processes need an interprocess communication (IPC) mechanism, and there are two fundamental models:

A message-passing link can be designed in several ways:

• Naming. In direct communication each process names the other, send(P, message), receive(Q, message), and a link joins exactly one pair. In indirect communication messages go through a mailbox (port), send(A, message), which several processes may share.
• Synchronization. send and receive can each be blocking (synchronous) or nonblocking (asynchronous). When both block, the exchange is a rendezvous.
• Buffering. The queue of messages has zero capacity (the sender blocks until the receiver takes the message), bounded capacity $n$ (the sender blocks only when the queue is full) or unbounded capacity (the sender never blocks).

Pipes. An ordinary pipe (pipe(fd) in UNIX) is a unidirectional producer–consumer channel: one process writes to fd[1] and the other reads from fd[0]. It exists only while the processes use it, and it needs a parent–child relationship, since the child inherits the descriptors through fork(). A named pipe (FIFO in UNIX) appears in the file system, so unrelated processes can use it, and it lasts until it is deleted.

Threads

Note. Context switch cost is an important difference between processes and threads. Switching between two processes changes the address space, so the TLB (the cache of page-table entries) must be invalidated, and it then fills up again slowly. Switching between two threads of the same process keeps the same address space, so the TLB and caches stay valid. Hence

$$\text{cost of switching between threads} \ll \text{cost of switching between processes}$$

Thread Libraries

A thread library provides the programmer with an API for creating and managing threads (e.g. POSIX Pthreads, Windows threads, Java threads). There are two primary ways of implementing a thread library:

1. Provide a library entirely in user space with no kernel support.
2. Implement a kernel-level library supported directly by the OS.

Kernel Threads vs User-Level Threads

In systems that use kernel-level threads, the OS itself is aware of each individual thread.

• A context switch between kernel threads of the same process requires only the registers, PC and stack to be changed; the overall memory-management information does not need to be switched, since they share the same address space. So it is slightly faster than switching between two processes.
• However, kernel threads can still be expensive, because a system call is required to switch between them.

A user-level thread is a thread within a process which the OS does not know about.

• The cost of a context switch between user-level threads can be made even lower, since the OS itself is not involved: no extra system calls are required.
• A user-level thread is represented by a PC, registers, a stack and a small thread control block (TCB).
• The downside: since the kernel sees only one thread, if one user thread makes a blocking system call, the whole process blocks, and the threads cannot run in parallel on a multicore machine.

Multithreading Models

User threads must ultimately be mapped to kernel threads:

• Many-to-one: many user threads on one kernel thread. Thread management is done in user space and is efficient, but one blocking call blocks the whole process and there is no parallelism.
• One-to-one: each user thread is a kernel thread (Linux, Windows). More concurrency, but creating a user thread means creating a kernel thread.
• Many-to-many: many user threads multiplexed onto a smaller or equal number of kernel threads, combining the advantages of both.

CPU Scheduling

CPU scheduling is the basis of multiprogrammed operating systems: by switching the CPU among processes, the OS can make the computer more productive.

CPU–I/O Burst Cycle

Process execution consists of a cycle of CPU execution and I/O wait, and processes alternate between these two states. Execution begins with a CPU burst, followed by an I/O burst, then another CPU burst, and so on. Eventually the final CPU burst ends with a system request to terminate execution.

Measured CPU-burst durations have a large number of short bursts and a small number of long ones. An I/O-bound program typically has many short CPU bursts; a CPU-bound program might have a few long ones.

CPU Scheduler

Whenever the CPU becomes idle, the OS must select one of the processes in the ready queue to be executed. The selection is carried out by the short-term scheduler (CPU scheduler).

Note. The ready queue is not necessarily a FIFO (first-in, first-out) queue. It can be a priority queue, a tree, or simply an unordered linked list.

Preemptive Scheduling

CPU-scheduling decisions may take place under the following four circumstances:

1. When a process switches from the running state to the waiting state (e.g. as the result of an I/O request, or a wait() for a child).
2. When a process switches from the running state to the ready state (e.g. when an interrupt occurs).
3. When a process switches from the waiting state to the ready state (e.g. at completion of I/O).
4. When a process terminates.

For situations 1 and 4 there is no choice in terms of scheduling: a new process (if one exists in the ready queue) must be selected for execution. There is a choice, however, for situations 2 and 3.

Note. Cooperative scheduling does not require special hardware (e.g. a timer). That is why it was the only option on some older hardware platforms.

Unfortunately, preemptive scheduling has a cost when processes share data. Consider two processes that share data. While one is updating the data, it is preempted so that the second process can run. The second process then tries to read the data, which are in an inconsistent state: a race condition.

How is a running process preempted? The OS preemption code must run on the CPU, but the CPU is busy running the user process. The OS gets control back through the hardware timer interrupt.

Dispatcher

The dispatcher is the module that gives control of the CPU to the process selected by the short-term scheduler. This involves:

• switching context;
• switching to user mode;
• jumping to the proper location in the user program to restart that program.

The time it takes the dispatcher to stop one process and start another running is known as the dispatch latency. Since the dispatcher runs on every process switch, it should be as fast as possible.

Scheduling Criteria

Different CPU-scheduling algorithms have different properties, and the choice of an algorithm may favour one class of processes over another.

• CPU utilization: keep the CPU as busy as possible.
• Throughput: the number of processes completed per time unit.
• Turnaround time: how long it takes to execute a process, from the time of submission to the time of completion. It is the sum of the periods spent waiting to get into memory, waiting in the ready queue, executing on the CPU, and doing I/O.
• Waiting time: the sum of the periods spent waiting in the ready queue. The scheduling algorithm affects only this, not the time a process executes or does I/O.
• Response time: the time from the submission of a request until the first response is produced (not the time to output the whole response). In an interactive system a process can produce some output early and keep computing while earlier results are shown, so turnaround time is not the best measure.

Note. It is desirable to maximize CPU utilization and throughput, and to minimize turnaround, waiting and response time. Turnaround time is generally limited by the speed of the output device. For interactive systems it has been suggested that minimizing the variance of the response time matters more than minimizing its average: a system with reasonable and predictable response time may be preferred to one that is faster on average but highly variable [1].

Scheduling Algorithms

The examples below use Galvin’s process sets; all times are in milliseconds, and each Gantt chart was produced by simulating the algorithm.

First-Come, First-Served (FCFS)

Idea: maintain the ready queue as a FIFO queue. New processes are inserted at the back, and the next process is scheduled from the front. FCFS is nonpreemptive.

If they arrive in the order $P_2, P_3, P_1$ instead:

Problems.

• FCFS suffers from the convoy effect: all the other processes wait for one big process to get off the CPU, which results in lower CPU and device utilization.
• The average waiting time is often quite long, and varies a lot with the arrival order.

Shortest-Job-First (SJF)

This algorithm associates with each process the length of its next CPU burst. When the CPU is available, it is assigned to the process that has the smallest next CPU burst. If two processes have the same next burst, FCFS is used to break the tie.

Note. SJF is provably optimal: it gives the minimum average waiting time for a given set of processes. Moving a short process before a long one decreases the short process’s waiting time more than it increases the long one’s.

SJF is frequently used in long-term scheduling (where the user can give a time limit for a job). The real difficulty with SJF is knowing the length of the next CPU request, so although it is optimal, it cannot be implemented exactly at the level of short-term scheduling. We may, however, be able to predict it, as an exponential average of the previous bursts:

where $t_n$ is the actual length of the $n$th CPU burst and $\tau_{n+1}$ is the predicted value of the next one. The initial $\tau_0$ can be defined as a constant or as an overall system average.

• $\alpha = 0$: $\tau_{n+1} = \tau_n$, recent history has no effect.
• $\alpha = 1$: $\tau_{n+1} = t_n$, only the most recent burst matters.
• Expanding, $\tau_{n+1} = \alpha t_n + (1-\alpha)\alpha t_{n-1} + \cdots + (1-\alpha)^{n+1}\tau_0$. Each older term has less weight, hence exponential average.

Preemptive SJF. SJF can be nonpreemptive or preemptive. The preemptive version, shortest-remaining-time-first (SRTF), preempts the running process when a newly arrived process has a shorter burst than what is left of the current one.

SJF suffers from starvation: if processes with shorter bursts keep coming, the longer processes will never get the CPU.

Highest Response Ratio Next (HRRN)

A nonpreemptive fix for SJF’s starvation. Whenever the CPU becomes free, compute for each waiting process

and run the process with the highest ratio.

• Short jobs are favoured, since a small burst gives a large ratio.
• A long job’s ratio keeps growing while it waits, so it is eventually chosen: no starvation. This is aging built into the formula.

• At 0 only $A$ is present, and at 3 only $B$, so they run first.
• At 9: $C = 1 + 5/4 = 2.25$, $D = 1 + 3/5 = 1.6$, $E = 1 + 1/2 = 1.5$, so $C$ runs.
• At 13: $D = 1 + 7/5 = 2.4$, $E = 1 + 5/2 = 3.5$, so $E$ runs, then $D$.

Priority Scheduling

A priority is associated with each process, and the CPU is allocated to the process with the highest priority (equal priorities are scheduled FCFS). It can be preemptive or nonpreemptive. If

it is equivalent to SJF or SRTF (depending on whether it is preemptive).

Problem. A major problem with priority scheduling algorithms is starvation (indefinite blocking): a steady stream of higher-priority processes can keep a low-priority process waiting forever.

Solution: aging. Aging gradually increases the priority of processes that wait in the system for a long time (e.g. raise it by 1 every 15 minutes), so every process eventually reaches a high enough priority to run.

Round Robin (RR)

RR is FCFS with preemption, designed for time sharing:

• Maintain the ready queue as a FIFO (circular) queue.
• After a small unit of time called a time quantum (typically 10–100 ms), the currently running process is preempted, and the process at the front of the ready queue is scheduled.
• The previously running process is inserted at the end of the ready queue.

If the burst is shorter than the quantum, the process releases the CPU voluntarily and the next process is scheduled immediately.

Note. The average waiting time under RR is often long. In RR no process is allocated the CPU for more than one time quantum in a row, unless it is the only runnable process. With $n$ processes and quantum $q$, no process waits more than $(n - 1)\,q$ before its next quantum.

• If $q$ is very large, RR becomes FCFS. If $q$ is very small, the system spends most of its time context switching; $q$ should be large compared with the context-switch time.
• A context switch does not take place if only one process is running.
• The average turnaround time does not necessarily improve as the time quantum increases. It improves when most processes finish their next CPU burst within a single quantum (rule of thumb: 80% of CPU bursts should be shorter than $q$). Turnaround grows for a smaller quantum, since more context switches are required.

Multilevel Queue Scheduling

Without feedback.

• Multiple queues represent different priorities (e.g. foreground/interactive and background/batch).
• Processes are permanently assigned to one queue, based on a property such as memory size, priority or type.
• Each queue has its own scheduling algorithm (e.g. RR for foreground, FCFS for background).
• A lower-priority queue’s processes can only run if all higher-priority queues are empty (alternatively, the queues get time slices, e.g. 80% / 20%).

Problem: too many high-priority tasks means starvation will occur in the lower queues.

With feedback (multilevel feedback queue).

• Allows a process to move between queues.
• If a process uses too much CPU time, it will be moved to a lower-priority queue. This leaves I/O-bound and interactive processes, which have short bursts, in the higher-priority queues.
• If a process waits too long in a lower-priority queue, it may be moved to a higher-priority queue. This form of aging prevents starvation.

A multilevel feedback queue scheduler is defined by the number of queues, the scheduling algorithm for each queue, and the rules for when to upgrade or demote a process and which queue a new process enters. It is the most general CPU-scheduling algorithm, but also the most complex to tune.

Process Synchronization

A cooperating process is one that can affect or be affected by other processes executing in the system. Cooperating processes can either directly share a logical address space (both code and data), or be allowed to share data only through files or messages. The former case is achieved through the use of lightweight processes, i.e. threads.

Why Is Synchronization Needed?

Suppose $P_1$ and $P_2$ share a variable counter = 5; $P_1$ executes counter++ and $P_2$ executes counter--. Neither statement is atomic: in machine language each one is three instructions (load into a register, modify the register, store it back).

/* P1: counter++ */
R1 = counter;
R1 = R1 + 1;
counter = R1;

/* P2: counter-- */
R2 = counter;
R2 = R2 - 1;
counter = R2;

A context switch can happen between any two instructions, so the six instructions can be interleaved in many orders:

Race Conditions

To prevent race conditions, the processes must be synchronized so that only one process at a time can manipulate the shared data.

Note. Always use instruction-level interleaving to show a race condition, since high-level statements are not atomic and can be switched in the middle. For instance, with int a[3] = {3, 4, 5}, running a[1] = a[0] + a[1] in $P_1$ and a[2] = a[1] + a[2] in $P_2$ gives {3, 7, 12} or {3, 7, 9} depending on which runs first, but executing whole statements one after the other has no concurrent access, so it is not a valid example of a race condition. Two different execution sequences are needed to show that the answer depends on the order [5].

The Critical-Section Problem

For example, with int count; shared, the statements count++ in $P_1$, count-- in $P_2$ and cout << count in $P_3$ are all critical sections, since count is shared.

A critical-section protocol consists of two parts, an entry section and an exit section. Between them is the critical section, which must run in a mutually exclusive way:

Requirements of a Solution

A good solution to the critical-section problem must satisfy the following three requirements.

1. Mutual exclusion. If a process $P$ is executing in its critical section, no other process can be executing in its critical section.
   • The entry protocol should be able to block processes that wish to enter but should not.
   • When the process in its critical section exits, the entry protocol must know this and allow a waiting process to enter.
2. Progress. If no process is executing in its critical section and some processes want to enter theirs, then only the processes that are waiting to enter can take part in deciding which one goes next (no other process can influence this decision), and this decision cannot be postponed indefinitely (it is made in finite time). So one of the waiting processes can enter its critical section.
3. Bounded waiting. After a process has made a request to enter its critical section and before that request is granted, there exists a bound on the number of times that other processes are allowed to enter their critical sections.

Moreover, a solution cannot depend on the CPUs’ relative speeds, timing, the scheduling policy or other external factors: we assume only that each process executes at a nonzero speed.

Note. Finite is not the same as bounded. “Finite” means any value you can write down (a billion, a trillion, …); “bounded” means the value can be no larger than one particular number, the bound.

Progress vs Bounded Waiting

• Progress does not imply bounded waiting. Progress says a process can enter within a finite decision time. It does not say which process enters, so there is no guarantee for any particular waiting process: it could lose every time.
• Bounded waiting does not imply progress. Even with a bound, all processes may be locked up in the entry section (e.g. due to a deadlock), i.e. the decision time is infinite.

Hence progress and bounded waiting are independent of each other, and a solution needs both.

A Few Related Terms

• Deadlock freedom: if two or more processes are trying to enter their critical sections, one of them will eventually enter. This is progress without the “outsiders have no influence” condition.
• Starvation freedom: if a process is trying to enter its critical section, it will eventually enter.

Q. Does starvation freedom imply deadlock freedom? Yes. If every process can eventually enter its critical section (although the waiting time may vary), then the decision time of selecting a process is finite. Otherwise, all processes would wait in the entry section.

Q. Does starvation freedom imply bounded waiting? No. The waiting time may not be bounded, even though each process can eventually enter its critical section.

Q. Does bounded waiting imply starvation freedom? No. Bounded waiting does not say whether a process can actually enter; it only says there is a bound. E.g. all processes could be locked up in the entry section (a deadlock, i.e. a failure of progress).

Q. Do bounded waiting and deadlock freedom together imply starvation freedom? Yes. Deadlock freedom guarantees that some waiting process always gets in, and bounded waiting limits how many times a given process can be overtaken, so every waiting process eventually enters.

So we need progress + bounded waiting. Together they are in fact stronger than starvation freedom, since there is now a bound instead of some arbitrary finite amount.

Solutions for the Critical Section

Disabling Interrupts

/* Process 1 */
while (1) {
    disable_interrupts();
    /* critical section */
    enable_interrupts();
    /* other code */
}

/* Process 2 */
while (1) {
    disable_interrupts();
    /* critical section */
    enable_interrupts();
    /* other code */
}

• Simple: when interrupts are disabled, a context switch won’t happen.
• Requires privileges: user processes generally cannot disable interrupts.
• Not suited for multicore systems: disabling interrupts on one core does not stop the other cores, and disabling them on all cores is slow (the message must be passed to every processor). It is the approach taken by some nonpreemptive kernels on a single processor.

Attempt 1: Strict Alternation

A single shared turn variable, int turn = 1;:

/* Process 1 */
while (1) {
    while (turn == 2) ;   /* busy wait */
    /* critical section */
    turn = 2;
    /* other code */
}

/* Process 2 */
while (1) {
    while (turn == 1) ;   /* busy wait */
    /* critical section */
    turn = 1;
    /* other code */
}

• Achieves mutual exclusion.
• Busy waiting: the waiting process keeps looping, a waste of power and time.
• Strict alternation: the order is always $P_1 \to P_2 \to P_1 \to P_2 \to \cdots$
• No progress: even when $P_2$ wants to enter its critical section, if $P_1$ has not started (or doesn’t need to go into its critical section), $P_2$ cannot enter.
• Bounded waiting is satisfied: the bound is 1. A process will go into its critical section after the other process changes turn.

Attempt 2: Two “Inside” Flags

Two shared variables, p1_inside = false, p2_inside = false;:

/* Process 1 */
while (1) {
    while (p2_inside == true) ;
    p1_inside = true;
    /* critical section */
    p1_inside = false;
    /* ... */
}

/* Process 2 */
while (1) {
    while (p1_inside == true) ;
    p2_inside = true;
    /* critical section */
    p2_inside = false;
    /* ... */
}

• The processes no longer need to alternate.
• Does not guarantee mutual exclusion: both can pass their while test before either sets its flag (check, switch, check, both set), and then both are in the critical section.

Attempt 3: Announce Intent First

Swap the order: set your own flag before checking the other’s. Globally defined p1_wants_to_enter, p2_wants_to_enter:

/* Process 1 */
while (1) {
    p1_wants_to_enter = true;
    while (p2_wants_to_enter == true) ;
    /* critical section */
    p1_wants_to_enter = false;
    /* ... */
}

/* Process 2 */
while (1) {
    p2_wants_to_enter = true;
    while (p1_wants_to_enter == true) ;
    /* critical section */
    p2_wants_to_enter = false;
    /* ... */
}

• Achieves mutual exclusion.
• Does not achieve progress: if both set their flag before either checks, each waits for the other forever (a deadlock). We can use a turn variable to break the deadlock.

Attempt 4: Peterson’s Solution

Peterson’s solution combines both ideas for two processes $P_i$ and $P_j$ ($j = 1 - i$), sharing int turn; and boolean flag[2];:

do {
    flag[i] = true;                  /* I want to enter            */
    turn = j;                        /* you can enter next         */
    while (flag[j] && turn == j) ;   /* if you want to enter and   */
                                     /* it's your turn, I'll wait  */
    /* critical section */
    flag[i] = false;                 /* I don't want to enter anymore */
    /* remainder section */
} while (true);

If both processes try to enter at the same time, turn is set to both i and j at roughly the same time; only the last assignment lasts, and it decides who enters first.

• It solves the critical-section problem for 2 processes.
• Mutual exclusion is achieved: both could be in the critical section only if flag[0] == flag[1] == true and turn equalled both 0 and 1.
• Progress is achieved: a process won’t have to wait for the other if the other doesn’t want to enter. The deadlock of attempt 3 is broken through the turn variable: the process which assigns turn first will enter first.
• Bounded waiting is achieved with bound = 1: after one entry by $P_j$, $P_j$ sets turn = i on its next attempt, so the processes alternate when both want to enter.

Note. Because modern processors and compilers may reorder loads and stores, Peterson’s solution is not guaranteed to work on modern architectures without memory barriers. Galvin still presents it because it gives a good algorithmic description of solving the critical-section problem, and shows the difficulty of meeting mutual exclusion, progress and bounded waiting in software [1].

Synchronization Hardware

A solution to the critical-section problem can be built using locks:

do {
    acquire lock
        /* critical section */
    release lock
        /* remainder section */
} while (true);

Many modern computer systems therefore provide special hardware instructions that allow us either to test and modify the content of a word, or to swap the contents of two words atomically, i.e. as one uninterruptible unit.

Test-and-Set

The TestAndSet() instruction can be defined as:

boolean TestAndSet(boolean *target) {
    boolean rv = *target;
    *target = TRUE;
    return rv;
}

The important characteristic is that this instruction is executed atomically. Thus, if two TestAndSet() instructions are executed simultaneously (each on a different core), they will be executed sequentially in some arbitrary order.

If the machine supports TestAndSet(), we can implement mutual exclusion by declaring a boolean variable lock, initialized to false. The structure of $P_i$ is:

do {
    while (TestAndSet(&lock))
        ;  /* do nothing: busy waiting */
    /* critical section */
    lock = FALSE;
    /* remainder section */
} while (true);

This type of lock is also called a spinlock (a mutex that spins).

Mutex locks. The OS packages this as a mutex lock (from mutual exclusion): a boolean available with two operations, which must be atomic and are usually built from TestAndSet or compare_and_swap:

acquire() {
    while (!available)
        ;  /* busy wait */
    available = false;
}

release() {
    available = true;
}

A process calls acquire() before its critical section and release() after it. The busy waiting wastes CPU cycles, but a spinning process needs no context switch, so spinlocks are preferred on multiprocessors when locks are held only briefly.

Note. TestAndSet satisfies mutual exclusion and progress, but not bounded waiting: when the lock is released, whichever spinning process happens to run TestAndSet first gets it, and an unlucky process can lose every time. (Galvin, Fig. 5.7, gives a longer version with a waiting[] array that does satisfy bounded waiting.)

The similar compare_and_swap(&value, expected, new_value) instruction sets value to new_value only if value == expected, and always returns the original value; while (compare_and_swap(&lock, 0, 1) != 0) ; gives the same spinlock.

Semaphores

Semaphores are the OS-level solution.

All modifications to the integer value of the semaphore in wait() and signal() must be executed indivisibly: when one process modifies the semaphore value, no other process can simultaneously modify that same semaphore value.

The classical definitions busy-wait, so a semaphore defined this way is a spinlock:

wait(S) {
    while (S <= 0)
        ;   /* busy waiting */
    S--;
}

signal(S) {
    S++;
}

Counting and Binary Semaphores

• The value of a counting semaphore can range over an unrestricted domain ($-\infty$ to $+\infty$).
• The value of a binary semaphore can range only between 0 and 1. Binary semaphores behave like mutex locks and provide mutual exclusion.

We can use binary semaphores to deal with the critical-section problem for $n$ processes. The $n$ processes share a semaphore mutex, initialized to 1:

do {
    wait(mutex);
        /* critical section */
    signal(mutex);
        /* remainder section */
} while (true);

Counting semaphores can be used to control access to a given resource consisting of a finite number of instances. The semaphore is initialized to the number of resources available. Each process that wishes to use a resource performs a wait() on the semaphore (decrementing the count), and performs a signal() when it releases the resource (incrementing the count). When the count becomes 0, all resources are being used; after that, processes that wish to use a resource will block until the count becomes greater than 0.

Note. A counting semaphore with its value bounded by $S \le 1$ is equivalent to a binary semaphore.

Busy Waiting and Spinlocks

The main disadvantage of this definition is that it requires busy waiting. While a process is in its critical section, any other process that tries to enter must loop continuously in the entry code. This is clearly a problem in a real multiprogramming system, where a single CPU is shared among many processes: busy waiting wastes CPU cycles that some other process might be able to use productively.

Note. Spinlocks do have an advantage: no context switch is required when a process must wait on a lock, and a context switch may take considerable time. Thus, when locks are expected to be held for short times, spinlocks are useful. They are often employed on multiprocessor systems, where one thread can “spin” on one processor while another thread performs its critical section on another processor.

Semaphores Without Busy Waiting

To overcome the need for busy waiting, we can modify the definitions of wait() and signal(). Rather than engaging in busy waiting, the process can block itself. The block operation places a process into a waiting queue associated with the semaphore, and the state of the process is switched to the waiting state. Control is then transferred to the CPU scheduler, which selects another process to execute.

A process that is blocked, waiting on a semaphore $S$, should be restarted when some other process executes a signal() operation. The process is restarted by a wakeup() operation, which changes the process from the waiting state to the ready state, and the process is placed in the ready queue. (The CPU may or may not be switched from the running process to the newly ready process, depending on the CPU-scheduling algorithm.)

So each semaphore has an integer value and a list of processes:

typedef struct {
    int value;
    struct process *list;
} semaphore;

When a process must wait on a semaphore, it is added to the list of processes. A signal() operation removes one process from the list of waiting processes and awakens that process.

wait(semaphore *S) {
    S->value--;
    if (S->value < 0) {
        add this process to S->list;
        block();    /* system call: suspends
                       the process that invokes it */
    }
}

signal(semaphore *S) {
    S->value++;
    if (S->value <= 0) {
        remove a process P from S->list;
        wakeup(P);  /* system call: resumes
                       the blocked process P */
    }
}

Note. $S = n$: $n$ more processes can enter. $S = 0$: no process can enter (but none is waiting). $S = -n$: $n$ processes are waiting.

Deadlock and Starvation

The implementation of a semaphore with a waiting queue may result in a situation where two or more processes are waiting indefinitely for an event that can be caused only by one of the waiting processes (a deadlock). Let $S$ and $Q$ be two semaphores initialized to 1:

/* P0 */
wait(S);
wait(Q);
  ...
signal(S);
signal(Q);

/* P1 */
wait(Q);
wait(S);
  ...
signal(Q);
signal(S);

If $P_0$ executes wait(S) and then $P_1$ executes wait(Q), then $P_0$ blocks in wait(Q) until $P_1$ signals $Q$, and $P_1$ blocks in wait(S) until $P_0$ signals $S$. Neither signal can ever happen, so $P_0$ and $P_1$ are deadlocked.

Another problem related to deadlocks is indefinite blocking, or starvation: a situation in which processes wait indefinitely within the semaphore. Indefinite blocking may occur if we add and remove processes from the list associated with a semaphore in LIFO (last-in, first-out) order.

A related problem is livelock. It is similar to a deadlock, except that the states of the processes involved keep changing with regard to one another, yet none of them makes progress. (Think of two people in a corridor who keep stepping aside the same way to let each other pass.) Livelock is a special case of resource starvation; starvation in general only says that some process is not progressing.

Priority Inversion

A scheduling challenge arises when a higher-priority process needs to read or modify kernel data that are currently being accessed by a lower-priority process, or a chain of lower-priority processes. Since kernel data are typically protected with a lock, the higher-priority process will have to wait for a lower-priority one to finish with the resource. The situation becomes more complicated if the lower-priority process is preempted in favour of another process with a higher priority.

Ordinarily, process $H$ would wait for $L$ to finish using resource $R$. However, now suppose that process $M$ becomes runnable, thereby preempting process $L$. Indirectly, a process with a lower priority ($M$) has affected how long process $H$ must wait for $L$ to relinquish resource $R$.

This problem is known as priority inversion. It occurs only in systems with more than two priorities.

Typically, these systems solve the problem by implementing a priority-inheritance protocol: all processes that are accessing resources needed by a higher-priority process inherit the higher priority until they are finished with the resources in question. When they are finished, their priorities revert to their original values.

Note. Priority inversion caused repeated system resets on NASA’s Mars Pathfinder in 1997; it was fixed by enabling priority inheritance (see Galvin, sidebar Priority Inversion and the Mars Pathfinder, p. 218).

Classic Problems of Synchronization

Producer–Consumer Problem (Inconsistency of Data)

A producer process produces information that is consumed by a consumer process. To allow the producer and consumer to run concurrently, we must have a buffer of items that can be filled by the producer and emptied by the consumer. This buffer will reside in a region of memory that is shared by the producer and consumer. A producer can produce one item while the consumer is consuming another.

The producer and consumer must be synchronized, so that the consumer does not try to consume an item that has not yet been produced.

Two types of buffer can be used:

• The unbounded buffer places no practical limit on the size of the buffer. The consumer may have to wait for new items, but the producer can always produce new items.
• The bounded buffer assumes a fixed buffer size. In this case, the consumer must wait if the buffer is empty, and the producer must wait if the buffer is full.

The following variables reside in a region of memory shared by the producer and consumer processes:

#define BUFFER_SIZE 10

typedef struct {
    ...
} item;

item buffer[BUFFER_SIZE];
int in = 0;    /* next free position  */
int out = 0;   /* first full position */

The shared buffer is implemented as a circular array with two logical pointers, in and out.

• The buffer is empty when in == out.
• The buffer is full when ((in + 1) % BUFFER_SIZE) == out.

The producer process has a local variable next_produced in which the new item to be produced is stored. The consumer process has a local variable next_consumed in which the item to be consumed is stored.

/* Producer */
item next_produced;
while (true) {
    /* produce an item in next_produced */
    while (((in + 1) % BUFFER_SIZE) == out)
        ;  /* do nothing */
    buffer[in] = next_produced;
    in = (in + 1) % BUFFER_SIZE;
}

/* Consumer */
item next_consumed;
while (true) {
    while (in == out)
        ;  /* do nothing */
    next_consumed = buffer[out];
    out = (out + 1) % BUFFER_SIZE;
    /* consume the item in next_consumed */
}

Note. This allows at most BUFFER_SIZE − 1 items in the buffer at the same time (only $n - 1$ positions can be used). To fix this, we can add a counter that counts the items.

/* Producer */
while (true) {
    /* produce an item in next_produced */
    while (counter == BUFFER_SIZE)
        ;  /* do nothing */
    buffer[in] = next_produced;
    in = (in + 1) % BUFFER_SIZE;
    counter++;
}

/* Consumer */
while (true) {
    while (counter == 0)
        ;  /* do nothing */
    next_consumed = buffer[out];
    out = (out + 1) % BUFFER_SIZE;
    counter--;
    /* consume the item in next_consumed */
}

Here counter and buffer are shared. Both routines may be correct separately, but they might not function correctly when executed concurrently, because of the race condition on the shared counter (exactly the counter++ / counter-- interleavings shown earlier).

Bounded Buffer with Semaphores

We can use semaphores for synchronization:

semaphore mutex = 1;   /* binary semaphore for mutual exclusion   */
semaphore empty = n;   /* counting semaphore: number of empty slots */
semaphore full  = 0;   /* counting semaphore: number of full slots  */

/* Producer */
do {
    /* produce next_p */
    wait(empty);   /* wait if full  */
    wait(mutex);
    /* add next_p to buffer */
    signal(mutex);
    signal(full);  /* one more item */
} while (true);

/* Consumer */
do {
    wait(full);    /* wait if empty */
    wait(mutex);
    /* remove item to next_c */
    signal(mutex);
    signal(empty); /* one more slot */
    /* consume next_c */
} while (true);

Note the symmetry: we can read this as the producer producing full buffers for the consumer, or as the consumer producing empty buffers for the producer.

Note. The order of the two wait()s matters. If the producer did wait(mutex) before wait(empty) on a full buffer, it would block while holding mutex, and the consumer could never get in to empty a slot: a deadlock.

The Readers–Writers Problem

A database is to be shared among several concurrent processes. Some of these processes may want only to read the database (readers), whereas others may want to update it, i.e. read and write (writers). If two readers access the shared data simultaneously, no adverse effects will result. However, if a writer and some other thread (either a reader or a writer) access the database simultaneously, chaos may ensue.

The readers–writers problem has several variations, all involving priorities.

• The simplest one, referred to as the first readers–writers problem, requires that no reader be kept waiting unless a writer has already obtained permission to use the shared object. In other words, no reader should wait for other readers to finish simply because a writer is waiting. (This variation’s solution can suffer from starvation of writers.)
• The second readers–writers problem requires that, once a writer is ready, it performs its write as soon as possible: if a writer is waiting, no new readers may start reading. (Here readers may starve.)

For the first problem, the readers and writers share the following:

semaphore rw_mutex = 1, mutex = 1;
int read_count = 0;

/* Writer */
do {
    wait(rw_mutex);    /* mutually exclusive for writing */
    /* writing is performed */
    signal(rw_mutex);
} while (true);

/* Reader */
do {
    wait(mutex);       /* mutual excl. to update read_count */
    read_count++;
    if (read_count == 1)
        wait(rw_mutex);  /* first reader in: make writers wait */
    signal(mutex);
    /* reading is performed */
    wait(mutex);       /* mutual excl. to update read_count */
    read_count--;
    if (read_count == 0)
        signal(rw_mutex);  /* last reader out: writer can write */
    signal(mutex);
} while (true);

rw_mutex works as a mutual-exclusion semaphore for the writers, and is also used by the first reader to enter and the last reader to leave; readers that come and go while other readers are reading don’t touch it.

Note. If a writer is in the critical section and $n$ readers are waiting, then one reader is queued on rw_mutex, and $n - 1$ readers are queued on mutex.

Printer Spooler Daemon (Loss of Data)

Consider a situation where there are multiple processes and only one printer for printing purposes, and the printer is a slower device as compared to the CPU and memory. So the spooler comes into the picture. The spooler is a program that maintains a directory containing the list of files that the printer has to print. The spooler hands over the files to the printer one by one.

Each process that wants to keep its file in the spooler directory needs to execute this program, where IN is shared between the processes and SD is the spooler directory:

LOAD   Ri, M[IN]          ; Ri = IN
STORE  SD[Ri], "filename" ; put the file name in slot Ri
INCR   Ri
STORE  M[IN], Ri          ; IN = Ri

Similar to the producer–consumer problem, we can use semaphores to prevent this data loss or inconsistency.

The Dining-Philosophers Problem

• Philosophers either think or eat.
• To eat, a philosopher needs to hold both forks (the one on their left and the one on their right).
• If a philosopher is not eating, they are thinking.
• Problem: develop an algorithm where no philosopher starves.

It is a simple representation of the need to allocate several resources among several processes in a deadlock-free and starvation-free manner.

First try.

#define N 5

void philosopher(int i) {
    while (true) {
        think();          /* for some time */
        take_fork(Ri);    /* take fork on the right */
        take_fork(Li);    /* take fork on the left  */
        eat();
        put_fork(Li);
        put_fork(Ri);
    }
}

This could deadlock when all philosophers take the fork on their right at the same time: there will be a circular wait, each philosopher holding one fork and waiting for the next.

Second try.

#define N 5

void philosopher(int i) {
    while (true) {
        think();
        take_fork(Ri);
        if (available(Li)) {
            take_fork(Li);
            eat();
            put_fork(Ri);
            put_fork(Li);
        } else {
            put_fork(Ri);
            sleep(T);
        }
    }
}

If all philosophers take $R_i$, check for $L_i$ and put $R_i$ back continuously, they never eat even though nobody is blocked: a livelock (starvation). Even if $T$ is random for each philosopher, the possibility is still there.

Solution using a mutex.

#define N 5

void philosopher(int i) {
    while (true) {
        think();
        lock(mutex);
        take_fork(Ri);
        take_fork(Li);
        eat();
        put_fork(Ri);
        put_fork(Li);
        unlock(mutex);
    }
}

• It protects the critical section with a mutex, and prevents deadlock.
• But it has performance issues: only one philosopher can eat at a time, although two non-neighbours could eat together.

Solution with semaphores. Use $N$ semaphores s[0], …, s[N−1], all initialized to 0, and a mutex. Each philosopher has 3 states: HUNGRY, EATING and THINKING. A philosopher can only move to the EATING state if neither neighbour is eating (LEFT = (i + N − 1) % N, RIGHT = (i + 1) % N).

void philosopher(int i) {
    while (true) {
        think();
        take_forks(i);
        eat();
        put_forks(i);
    }
}

void take_forks(int i) {
    lock(mutex);
    state[i] = HUNGRY;
    test(i);          /* try to get both forks */
    unlock(mutex);
    wait(s[i]);       /* block if forks were not acquired */
}

void put_forks(int i) {
    lock(mutex);
    state[i] = THINKING;
    test(LEFT);       /* can the left neighbour eat now?  */
    test(RIGHT);      /* can the right neighbour eat now? */
    unlock(mutex);
}

void test(int i) {
    if (state[i] == HUNGRY &&
        state[LEFT] != EATING &&
        state[RIGHT] != EATING) {
        state[i] = EATING;
        signal(s[i]);
    }
}

This is deadlock-free and allows the maximum parallelism (two philosophers can eat at once). A philosopher who finishes eating checks whether a neighbour was waiting for the forks, and wakes them up.

Note. Galvin’s simple semaphore solution (one semaphore chopstick[i] per fork) deadlocks in the same way as the first try. Possible remedies are: allow at most four philosophers at the table; allow a philosopher to pick up forks only if both are available (picking them up in a critical section, as in the solution above); or use an asymmetric solution where odd philosophers pick up the left fork first and even ones the right. A deadlock-free solution does not necessarily eliminate starvation.

Monitors

Semaphores are effective, but using them incorrectly causes timing errors that are hard to detect, because they appear only for particular execution sequences. With a semaphore mutex guarding a critical section [1]:

• swapping the order, signal(mutex) … wait(mutex), lets several processes into their critical sections at once (mutual exclusion is violated);
• writing wait(mutex) … wait(mutex) causes a deadlock;
• omitting the wait(), the signal() or both either violates mutual exclusion or deadlocks.

These problems arise even if only a single process is not well behaved, whether from an honest programming error or an uncooperative programmer. To deal with such errors, high-level language constructs were developed; a fundamental one is the monitor.

monitor monitor_name {
    /* shared variable declarations */

    function P1(...) { ... }
    function P2(...) { ... }
    ...
    function Pn(...) { ... }

    initialization_code(...) { ... }
}

The programmer does not need to code the mutual exclusion explicitly. Many programming languages, including Java and C#, have incorporated the monitor idea [1]. For other synchronization schemes, a monitor can declare condition variables:

condition x, y;

The only operations on a condition variable are wait() and signal():

• x.wait() suspends the calling process until another process calls x.signal().
• x.signal() resumes exactly one suspended process. If none is suspended, it has no effect: the state of x is as if it had never been called. This differs from a semaphore’s signal(), which always changes the semaphore’s value.

When a process $P$ calls x.signal() and a process $Q$ is suspended on x, both cannot be active in the monitor. There are two options [1]:

1. Signal and wait: $P$ waits until $Q$ leaves the monitor or waits on another condition.
2. Signal and continue: $Q$ waits until $P$ leaves the monitor or waits on another condition.

Signal-and-continue seems reasonable since $P$ was already running, but by the time $Q$ resumes, the condition it was waiting for may no longer hold. Concurrent Pascal uses a compromise: the signalling process leaves the monitor immediately, so $Q$ resumes at once.

Dining Philosophers Using a Monitor

A philosopher may pick up the chopsticks only if both are available. Each philosopher is THINKING, HUNGRY or EATING, and philosopher $i$ can eat only if neither neighbour is eating. A condition self[i] lets a hungry philosopher wait [1]:

monitor DiningPhilosophers {
    enum {THINKING, HUNGRY, EATING} state[5];
    condition self[5];

    void pickup(int i) {
        state[i] = HUNGRY;
        test(i);
        if (state[i] != EATING)
            self[i].wait();
    }

    void putdown(int i) {
        state[i] = THINKING;
        test((i + 4) % 5);      /* left neighbour  */
        test((i + 1) % 5);      /* right neighbour */
    }

    void test(int i) {
        if (state[(i + 4) % 5] != EATING &&
            state[i] == HUNGRY &&
            state[(i + 1) % 5] != EATING) {
            state[i] = EATING;
            self[i].signal();
        }
    }

    initialization_code() {
        for (int i = 0; i < 5; i++)
            state[i] = THINKING;
    }
}

Philosopher $i$ calls DiningPhilosophers.pickup(i), eats, then calls DiningPhilosophers.putdown(i). No two neighbours eat at the same time and there is no deadlock, but a philosopher can still starve.

Note. A monitor can be implemented with semaphores: a semaphore mutex (initially 1) is acquired on entering and released on leaving the monitor, and a semaphore next (initially 0) lets a signalling process suspend itself until the resumed process leaves or waits [1].

Deadlocks

In a multiprogramming environment, several processes may compete for a finite number of resources. A process requests resources; if the resources are not available at that time, the process enters a waiting state. Sometimes a waiting process is never again able to change state, because the resources it has requested are held by other waiting processes. This situation is called a deadlock.

System Model

A system consists of a finite number of resources to be distributed among a number of competing processes. Resources are partitioned into types, each with some number of identical instances: if a system has two CPUs, the resource type CPU has 2 instances; similarly, the resource type printer may have 5 instances.

A process uses a resource in the following sequence:

1. Request: if the request cannot be granted immediately (e.g. the resource is being used by another process), the requesting process must wait until it can acquire the resource.
2. Use: the process operates on the resource.
3. Release: the process releases the resource.

Note. The request and release of resources are system calls (e.g. request()/release() of a device, open()/close() of a file, wait()/signal() on a semaphore). Multithreaded programs are good candidates for deadlock because multiple threads can compete for shared resources.

Deadlock Characterization

A deadlock can arise only if the following four conditions hold simultaneously in a system.

1. Mutual exclusion: at least one resource must be held in a non-sharable mode, i.e. only one process at a time can use it.
2. Hold and wait: a process must be holding at least one resource and waiting to acquire additional resources that are currently held by other processes.
3. No preemption: resources cannot be preempted; a resource can be released only voluntarily by the process holding it, after that process has completed its task.
4. Circular wait: a set $\{P_0, P_1, \ldots, P_n\}$ of waiting processes must exist such that $P_0$ is waiting for a resource held by $P_1$, $P_1$ is waiting for a resource held by $P_2$, …, and $P_n$ is waiting for a resource held by $P_0$.

Note. The four conditions are not completely independent: circular wait implies hold and wait. Separating them is still useful, because each prevention strategy below attacks one of them.

How many instances rule out deadlock. Let $n$ processes share $m$ instances of one resource type, where process $P_i$ needs at most $\text{max}_i$ instances. In the worst case every process holds $\text{max}_i - 1$ instances and waits for one more. One extra instance lets some process finish and release everything, so deadlock is impossible if and only if

For example, 3 processes that each need 2 tape drives cannot deadlock with 4 drives, but can with 3. With equal needs $k$, the bound is $n(k - 1) + 1$.

Resource-Allocation Graphs

Deadlocks can be described more precisely in terms of a directed graph called a resource-allocation graph $G = (V, E)$:

• Vertices $V$: the processes $P_i$ (circles) and the resource types $R_j$ (rectangles, with one dot per instance).
• Edges $E$: a request edge $P_i \to R_j$ (process $P_i$ has requested an instance of $R_j$ and is waiting), and an assignment edge $R_j \to P_i$ (an instance of $R_j$ has been allocated to $P_i$; it starts from the particular instance).

If the graph contains no cycle, no process is deadlocked. If it contains a cycle, there can be a deadlock:

If every resource type has a single instance, then a cycle is both necessary and sufficient: a cycle $\iff$ deadlock. With several instances per type, a cycle is necessary but not sufficient.

Methods for Handling Deadlocks

There are three strategies to deal with deadlocks:

1. Use a protocol to prevent or avoid deadlocks, ensuring that the system will never enter a deadlocked state.
2. Allow the system to enter a deadlocked state, detect it and recover.
3. Ignore the problem altogether and pretend that deadlocks never occur.

The third solution is the one used by most operating systems, including Linux and Windows. It is then up to application developers to write programs that handle deadlocks.

To ensure that deadlocks never occur, the system can use either a deadlock-prevention or a deadlock-avoidance scheme.

Deadlock Prevention

Prevent at least one of the four necessary conditions from holding, by constraining how requests for resources can be made.

• Mutual exclusion: cannot be prevented in general, because some resources are intrinsically non-sharable (a mutex lock cannot be shared). Sharable resources such as read-only files never need it.
• Hold and wait: guarantee that whenever a process requests a resource, it does not hold any others. Either a process requests all its resources before it begins execution, or it may request resources only when it holds none. Both work, but they are very inefficient: resource utilization is low, and a process that needs several popular resources may starve.
• No preemption: can be done using some approaches. If a process holding resources requests another that cannot be immediately allocated, all the resources it holds are preempted (implicitly released), and it is restarted only when it can regain them along with the new ones. This works for resources whose state can be saved and restored, like CPU registers and memory, but not for printers or mutex locks.
• Circular wait: one way to ensure that this condition never holds is to impose a total ordering of all resource types and to require that each process requests resources in an increasing order.

Ordering resources. Define a mapping of resources to natural numbers,

and require that a process holding $r_i$ can request $r_j$ only if $F(r_j) > F(r_i)$. (Equivalently, a process requesting $r_j$ must first release any $r_i$ with $F(r_i) \ge F(r_j)$.)

Proof that no circular wait can exist. Suppose a circular wait exists, $P_0 \to r_0 \to P_1 \to r_1 \to \cdots \to P_n \to r_n \to P_0$, where $P_{i+1}$ holds $r_i$ while requesting $r_{i+1}$. Then

so $F(r_0) < F(r_0)$, which is not possible. Hence circular wait is avoided.

Deadlock Avoidance

Deadlock-prevention algorithms prevent deadlocks by restraining how requests can be made, which causes low device utilization and reduced system throughput. An alternative method for avoiding deadlocks is to require additional information about how resources are to be requested.

The simplest and most useful algorithm requires that each process declare the maximum number of resources of each type that it may need. A deadlock-avoidance algorithm then dynamically examines the resource-allocation state to ensure that a circular-wait condition can never exist.

Safe State

• A safe state is not a deadlocked state. A deadlocked state is an unsafe state.
• Not all unsafe states are deadlocks; an unsafe state may lead to a deadlock.
• In an unsafe state, the OS cannot prevent processes from requesting resources in such a way that a deadlock occurs.

Whenever a process requests a resource that is currently available, the system must decide whether the resource can be allocated immediately or whether the process must wait. The request is granted only if the allocation leaves the system in a safe state.

Note. In this scheme, if a process requests a resource that is currently available, it may still have to wait. Thus resource utilization may be lower than it would otherwise be.

Banker’s Algorithm

The resource-allocation-graph avoidance algorithm (which adds dashed claim edges to the graph) is not applicable to a resource-allocation system with multiple instances of each resource type. The Banker’s algorithm is applicable, but it is less efficient than the graph scheme.

When a new process enters the system, it must declare the maximum number of instances of each resource type that it may need. This number may not exceed the total number of resources in the system. When a process requests a set of resources, the system must determine whether the allocation of these resources will leave the system in a safe state. If it will, the resources are allocated; otherwise, the process must wait until some other process releases enough resources.

Data Structures

With $n$ processes and $m$ resource types:

• $\text{Available}[m]$: $\text{Available}[j] = k$ means $k$ instances of resource type $R_j$ are available.
• $\text{Max}[n \times m]$: $\text{Max}[i][j] = k$ means process $P_i$ may request at most $k$ instances of $R_j$.
• $\text{Allocation}[n \times m]$: $\text{Allocation}[i][j] = k$ means $P_i$ is currently allocated $k$ instances of $R_j$.
• $\text{Need}[n \times m]$: $\text{Need}[i][j] = k$ means $P_i$ may need $k$ more instances of $R_j$ to complete its task. It can be computed as

Safety Algorithm

1. Let $\text{Work} = \text{Available}$ and $\text{Finish}[i] = \text{false}$ for all $i$.
2. Find an $i$ such that $\text{Finish}[i] = \text{false}$ and $\text{Need}_i \le \text{Work}$. If no such $i$ exists, go to step 4.
3. $\text{Work} = \text{Work} + \text{Allocation}_i$, $\text{Finish}[i] = \text{true}$ ($P_i$ can finish and return its resources). Go to step 2.
4. If $\text{Finish}[i] = \text{true}$ for all $i$, the state is safe.

This takes $O(m \cdot n^2)$ operations.

Resource-Request Algorithm

When $P_i$ makes a request $\text{Request}_i$:

1. If $\text{Request}_i \le \text{Need}_i$, go to step 2. Otherwise raise an error: the process has exceeded its maximum claim (abort).
2. If $\text{Request}_i \le \text{Available}$, go to step 3. Otherwise $P_i$ must wait, since the resources are not available.
3. Pretend to allocate the resources:

and run the safety algorithm. If the new state is safe, the resources are allocated to $P_i$. If it is unsafe, $P_i$ must wait, and the old state is restored.

Worked Example

Running the safety algorithm, each process that can finish returns its allocation to Work:

The safe sequence $\langle P_1, P_3, P_4, P_0, P_2 \rangle$ exists, so the state is safe. The safe sequence may not be unique: $\langle P_1, P_3, P_4, P_2, P_0 \rangle$ also works.

Now suppose $P_1$ requests $\text{Request}_1 = (1, 0, 2)$. We have to check whether we can grant it.

• $\text{Request}_1 = (1, 0, 2) \le \text{Need}_1 = (1, 2, 2)$ ✓ (abort if $>$).
• $\text{Request}_1 = (1, 0, 2) \le \text{Available} = (3, 3, 2)$ ✓.

Pretend to allocate, and check the updated vectors:

Running the safety algorithm again, $\langle P_1, P_3, P_4, P_0, P_2 \rangle$ is still a safe sequence, with Work going $(2,3,0) \to (5,3,2) \to (7,4,3) \to (7,4,5) \to (7,5,5) \to (10,5,7)$. So the state is safe and $P_1$’s request is approved.

Note. In this new state, a request $(3, 3, 0)$ by $P_4$ cannot be granted, since the resources are not available. A request $(0, 2, 0)$ by $P_0$ cannot be granted either: the resources are available, but the resulting state, with Available $= (2, 1, 0)$, is unsafe, because no process’s Need fits in Work.

Deadlock Detection

If a system uses neither prevention nor avoidance, a deadlock may occur. Then it needs an algorithm that examines the state of the system to detect whether a deadlock has occurred, and an algorithm to recover from it. Both cost something: the run-time cost of keeping the information and running the detection, plus the losses of recovery.

Single Instance of Each Resource Type

If every resource has only one instance, use a wait-for graph: take the resource-allocation graph, remove the resource nodes and collapse the edges. An edge $P_i \to P_j$ means $P_i$ is waiting for $P_j$ to release a resource; it exists exactly when the resource-allocation graph has edges $P_i \to R_q$ and $R_q \to P_j$ for some $R_q$.

A deadlock exists if and only if the wait-for graph has a cycle. The system maintains the graph and periodically searches it for a cycle, which takes $O(n^2)$ operations for $n$ processes.

Several Instances of a Resource Type

The wait-for graph does not work with multiple instances. The detection algorithm instead uses data structures like the banker’s algorithm, with the current Request in place of Need:

• Available: vector of length $m$, the number of available resources of each type.
• Allocation: $n \times m$ matrix, the resources of each type currently allocated to each process.
• Request: $n \times m$ matrix, the current request of each process.

The algorithm:

1. Let $\text{Work} = \text{Available}$. For each $i$, set $\text{Finish}[i] = \text{false}$ if $\text{Allocation}_i \ne 0$, otherwise $\text{true}$.
2. Find an $i$ with $\text{Finish}[i] = \text{false}$ and $\text{Request}_i \le \text{Work}$. If there is none, go to step 4.
3. $\text{Work} = \text{Work} + \text{Allocation}_i$, $\text{Finish}[i] = \text{true}$; go to step 2.
4. If $\text{Finish}[i] = \text{false}$ for some $i$, the system is deadlocked, and every such $P_i$ is deadlocked.

It takes $O(m \times n^2)$ operations.

Note. Step 3 reclaims $P_i$’s resources as soon as $\text{Request}_i \le \text{Work}$. This is optimistic: we assume $P_i$ needs nothing more and will soon finish and return everything. If that is wrong, a deadlock may occur later, and the next run of the algorithm will detect it. The difference from the safety algorithm is that we use the current request, not the maximum future need.

Work goes $(0,0,0) \xrightarrow{P_0} (0,1,0) \xrightarrow{P_2} (3,1,3) \xrightarrow{P_3} (5,2,4) \xrightarrow{P_1} (7,2,4) \xrightarrow{P_4} (7,2,6)$. Every process can finish, with $\langle P_0, P_2, P_3, P_1, P_4 \rangle$, so the system is not deadlocked.

Now suppose $P_2$ requests one more instance of $C$, so $\text{Request}_2 = (0, 0, 1)$. $P_0$ can still finish, giving $\text{Work} = (0, 1, 0)$, but then no other request fits: $P_1$, $P_2$ and $P_4$ need $C$, and $P_3$ needs $A$. The system is deadlocked, and the deadlock consists of $P_1, P_2, P_3, P_4$.

When to Run Detection

It depends on how often deadlocks occur and how many processes they affect.

• Deadlocks happen only when a request cannot be granted immediately, so detection could run on every such request. This also identifies the process whose request completed the cycle, but costs a lot of computation.
• A cheaper choice is to run it at intervals, e.g. once per hour, or whenever CPU utilization drops below 40% (a deadlock eventually cripples throughput). Then the graph may contain many cycles, and we usually cannot tell which process “caused” the deadlock.

Recovery from Deadlock

Once a deadlock is detected, the operator can be told to deal with it manually, or the system can recover automatically, either by aborting processes or by preempting resources.

Process Termination

In both methods the system reclaims all resources of the terminated processes.

• Abort all deadlocked processes. This surely breaks the cycle, but at great expense: their partial computations are lost and must be redone.
• Abort one process at a time until the cycle is eliminated. This needs a detection run after each abort.

Aborting is not always easy: a process in the middle of updating a file leaves it in an incorrect state. For partial termination, choose the process whose termination costs least, based on factors such as:

1. its priority;
2. how long it has computed, and how much longer it needs;
3. how many and what types of resources it has used (whether they are easy to preempt);
4. how many more resources it needs to complete;
5. how many processes will need to be terminated;
6. whether it is interactive or batch.

Resource Preemption

Preempt resources from some processes and give them to others until the cycle is broken. Three issues must be addressed:

1. Selecting a victim: which resources and processes to preempt, so as to minimize cost (e.g. the number of resources held, the time used so far).
2. Rollback: the process cannot continue without the resource, so it must be rolled back to some safe state and restarted from there. Since a safe state is hard to determine, the simplest solution is a total rollback: abort and restart it.
3. Starvation: if victims are chosen only by cost, the same process may always be picked. A process should be picked as a victim only a finite (small) number of times; the usual fix is to include the number of rollbacks in the cost.

Memory Management

Main Memory

Main memory and the registers built into the processor itself are the only storage that the CPU can access directly. There are machine instructions that take memory addresses as arguments, but none that take disk addresses. Therefore, any instruction in execution, and any data being used by the instructions, must be in one of these direct-access storage devices. If the data are not in memory, they must be moved there before the CPU can operate on them.

Registers that are built into the CPU are generally accessible within one cycle of the CPU clock. Memory access may take many cycles of the CPU clock to complete, in which case the processor normally needs to stall, since it does not have the data required to complete the instruction that it is executing.

Note. The remedy is to add fast memory between the CPU and main memory, typically on the CPU chip: a cache.

Idea of Address Translation

• There could be many programs running concurrently on a machine, and they must be protected from each other: one program should not be able to access the variables of another. This is physically done through address translation.
• Each program is compiled to use addresses in the range $0$ to MaxAddr (e.g. $0$ to $2^{64} - 1$).
• These addresses are not real, but only virtual addresses. They have to be translated into actual main-memory addresses.
• Memory management unit (MMU): the hardware that does the address translation.

Protection with Base and Limit Registers

Not only are we concerned with the relative speed of accessing physical memory, but we must also protect user processes from one another. We need to make sure that each process has a separate memory space. To do this, we need the ability to determine the range of legal addresses that the process may access and to ensure that the process can access only these legal addresses.

We can provide this protection by using two registers, usually a base and a limit:

• the base register holds the smallest legal physical memory address;
• the limit register specifies the size of the range.

Protection of memory space is accomplished by having the CPU hardware compare every address generated in user mode with the registers:

Any attempt by a program executing in user mode to access OS memory or other users’ memory results in a trap to the OS, which treats it as a fatal error. This scheme prevents a user program from (accidentally or deliberately) modifying the code or data structures of either the OS or other users.

Note. The base and limit registers can be loaded only by the OS, using a special privileged instruction. Since privileged instructions can be executed only in kernel mode, only the OS can change them.

Address Binding

Usually, a program resides on a disk as a binary executable file. To be executed, the program must be brought into memory and placed within a process. Depending on the memory management in use, the process may be moved between disk and memory during its execution. The processes on the disk that are waiting to be brought into memory for execution form the input queue.

The normal procedure is to select one of the processes in the input queue and to load that process into memory. As the process is executed, it accesses instructions and data from memory. Eventually, the process terminates, and its memory space is declared available.

Addresses in the source program are generally symbolic (such as the variable count). A compiler typically binds these symbolic addresses to relocatable addresses (such as “14 bytes from the beginning of this module”). The linkage editor or loader in turn binds the relocatable addresses to absolute addresses (such as 74014).

Classically, the binding of instructions and data to memory addresses can be done at any step along the way:

• Compile time. If you know at compile time where the process will reside in memory, then absolute code can be generated. If the starting location changes later, the code must be recompiled.
• Load time. If it is not known at compile time where the process will reside in memory, then the compiler must generate relocatable code, and final binding is delayed until load time.
• Execution time. If the process can be moved during its execution from one memory segment to another, then binding must be delayed until run time. Special hardware must be available for this scheme to work.

Logical vs Physical Address Space

Note. The compile-time and load-time address-binding methods generate identical logical and physical addresses. However, the execution-time address-binding scheme results in different logical and physical addresses. In this case, we usually refer to the logical address as a virtual address.

The run-time mapping from virtual to physical addresses is done by the MMU, a hardware device inside the CPU. In the simplest scheme, the base register is now called a relocation register, and its value is added to every address generated by a user process at the time the address is sent to memory:

The user program never sees the real physical addresses: it deals with logical addresses in the range $0$ to max, which are mapped to physical addresses in the range $R + 0$ to $R + \text{max}$ for a relocation value $R$.

Dynamic Loading

So far, the entire program and all data of a process must be in physical memory for the process to execute. The size of a process is thus limited to the size of physical memory. To obtain better memory-space utilization, we can use dynamic loading.

With dynamic loading, a routine is not loaded until it is called. All routines are kept on disk in a relocatable load format.

1. The main program is loaded into memory and is executed.
2. When a routine needs to call another routine, the calling routine first checks to see whether the other routine has been loaded.
3. If it has not, the relocatable linking loader is called to load the desired routine into memory and to update the program’s address tables to reflect this change.
4. Then control is passed to the newly loaded routine.

The advantage of dynamic loading is that an unused routine is never loaded. This is particularly useful when large amounts of code are needed to handle infrequently occurring cases, such as error routines: the total program size may be large, but the portion that is actually used (and hence loaded) may be much smaller.

Note. Dynamic loading does not require special support from the OS. It is the responsibility of the users to design their programs to take advantage of such a method. The OS may help, however, by providing library routines to implement dynamic loading.

Dynamic Linking and Shared Libraries

Some operating systems support only static linking, in which system language libraries are treated like any other object module and are combined by the loader into the binary program image.

With dynamic linking, linking is postponed until execution time. This feature is usually used with system libraries, such as language subroutine libraries; without it, each program on a system must include a copy of its language library in the executable image, which wastes both disk space and main memory.

With dynamic linking, a stub is included in the image for each library-routine reference. The stub is a small piece of code that indicates how to locate the appropriate memory-resident library routine, or how to load the library if the routine is not already present. When the stub is executed, it replaces itself with the address of the routine and executes it, so the next time that code segment is reached, the library routine is executed directly.

• All processes that use a language library execute only one copy of the library code; hence these are called shared libraries.
• A library can be updated (e.g. for bug fixes) and every program that references it automatically uses the new version, without relinking. Version information in the program and the library keeps a program from using an incompatible version.

Note. Unlike dynamic loading, dynamic linking generally requires help from the OS. If the processes in memory are protected from one another, only the OS can check whether the needed routine is in another process’s memory space, and allow multiple processes to access the same memory addresses.

Swapping

A process has to be in main memory while it runs, but it does not have to stay there the whole time. It can be swapped out to a backing store (usually a fast disk) for a while and later brought back to continue where it left off. Because some processes can wait on disk, the total memory needed by all processes can be larger than the physical memory, which raises the degree of multiprogramming.

Swapping with round robin. In a multiprogramming system using round-robin CPU scheduling, when a process uses up its quantum, the memory manager can move it out and bring another process into the space it frees. Meanwhile the CPU scheduler keeps giving time slices to processes that are already in memory. Ideally the swapping is fast enough that some process is always in memory and ready whenever the scheduler wants to run one. This also means the quantum must be long enough that a reasonable amount of computation happens between swaps.

Swapping with priorities. A similar policy works for priority scheduling. When a higher-priority process arrives and needs memory, the memory manager can swap out a lower-priority process to make room, run the higher-priority one, and when it finishes, swap the lower-priority process back in to continue. This variant is sometimes called roll out, roll in.

Where does it come back to? Normally a swapped-out process returns to the same memory region it used before. Whether that is required depends on address binding:

• if binding is done at assembly or load time, the addresses are fixed in the code, so the process cannot easily be moved to a different location;
• with execution-time binding, the physical addresses are computed while the process runs, so it can be swapped back into any free region.

Swapping is slow. Most of the cost is transfer time, which grows with the amount of memory moved. For example, moving a 100 MB process over a disk that transfers 50 MB/s takes $100/50 = 2$ s each way, so swapping it out and another one in takes about 4 s. This is why it helps for the OS to know how much memory a process is actually using, not just how much it could use.

Note. A process should be idle when it is swapped out. If it is waiting on I/O that will write directly into its memory buffers, swapping it out would let that I/O land in memory now owned by another process. So either such processes are never swapped, or I/O goes into OS buffers first and is copied to the process when it is back in memory (double buffering). Because full swapping is so slow, modern systems (UNIX, Linux, Windows) swap only when free memory runs low, and often swap just parts of processes, as part of virtual memory.

Memory Allocation

A simple way to allocate memory is to split it into several fixed-sized partitions, each holding exactly one process. The degree of multiprogramming is then limited by the number of partitions. In this multiple-partition method, whenever a partition becomes free, a process from the input queue is chosen and loaded into it; when that process terminates, the partition is free again for another process.

In the variable-partition scheme, the OS keeps a table recording which parts of memory are free and which are in use. At the start, all memory available to user processes is one large free block, called a hole. When a process arrives and needs memory, the OS looks for a hole big enough for it. If one is found, the process is given only as much memory as it needs, and the rest stays free for later requests.

So at any moment there is a set of holes of different sizes scattered across memory:

• When a process arrives, the system searches this set for a hole that is large enough. If the hole is bigger than needed, it is split in two: one part goes to the process, and the other goes back into the set of holes.
• When a process terminates, its block is returned to the set of holes. If the new hole is adjacent to other holes, they are merged into one bigger hole.

This is a special case of the general dynamic storage-allocation problem: how to satisfy a request of size $n$ from a list of free holes. Of the many solutions, the first-fit, best-fit and worst-fit strategies are the ones most commonly used to pick a hole.

• First fit: allocate the first hole that is big enough. The search can start from the beginning of the set of holes, or from where the previous first-fit search stopped (next fit).
• Best fit: allocate the smallest hole that is big enough. The whole list must be searched, unless it is kept ordered by size. This leaves the smallest leftover hole.
• Worst fit: allocate the largest hole. Again the whole list must be searched unless it is sorted by size. This leaves the largest leftover hole, which may be more useful than the small leftover from best fit.

Note. Both first fit and best fit are better than worst fit in terms of decreasing time and storage utilization. Neither first fit nor best fit is clearly better than the other in storage utilization, but first fit is usually faster.

Both first-fit and best-fit allocation suffer from external fragmentation.

Fragmentation

As processes are loaded into and removed from memory, the free memory gets broken into small pieces.

In the worst case there could be a block of free (wasted) memory between every pair of processes. If all these pieces were one large block, several more processes might fit.

Note. The 50-percent rule: statistical analysis of first fit shows that, even with some optimization, for every $N$ allocated blocks about another $0.5N$ blocks are lost to fragmentation. That is, roughly one-third of memory may be unusable.

Compaction. One solution to external fragmentation is compaction: shuffle the memory contents so that all free memory is placed together in one large block.

Compaction is not always possible, however. If relocation is static (done at assembly or load time), the processes cannot be moved, so compaction cannot be done. It is possible only if relocation is dynamic and done at execution time: moving a process then only needs its relocation (base) register to be changed. Even then it can be expensive, since the simplest algorithm moves every process towards one end of memory.

Another possible solution to external fragmentation is to permit the logical address space of a process to be non-contiguous, so that a process can be given physical memory wherever it is available. Segmentation (below) and paging are two techniques that do this.

For example, if a hole of 18,464 bytes is used for a request of 18,462 bytes, a hole of 2 bytes would be left, and keeping track of it would cost more than the hole itself. So memory is usually broken into fixed-size blocks and allocated in whole blocks, and the unused part of the last block is internal fragmentation.

Segmentation

When writing a program, a programmer thinks of it as a main program together with a set of methods, procedures or functions, and maybe some data structures such as a stack or a symbol table. They do not care which addresses in memory these elements occupy.

For simplicity, segments are numbered and referred to by a segment number rather than a name. Thus a logical address consists of a two-tuple:

Normally, the user program is compiled, and the compiler automatically constructs segments reflecting the input program. A C compiler might create separate segments for:

• the code;
• global variables;
• the heap, from which memory is allocated;
• the stacks used by each thread;
• the standard C library.

(Libraries that are linked in during compile time might be assigned separate segments; the loader takes all these segments and assigns them segment numbers.)

Segmentation hardware. The user refers to objects by a two-dimensional address, but physical memory is still a one-dimensional sequence of bytes. The mapping is done by a segment table. Each entry has a segment base, the starting physical address of the segment in memory, and a segment limit, the length of the segment.

A logical address $(s, d)$ is translated as follows:

1. The segment number $s$ is used as an index into the segment table.
2. The offset $d$ must be between $0$ and the segment limit. If it is not, the hardware traps to the OS (addressing error: logical addressing attempt beyond the end of the segment).
3. If the offset is legal, it is added to the segment base to produce the physical address of the desired byte.

The segment table is thus essentially an array of base–limit register pairs.

• Byte 53 of segment 2 is mapped to $4300 + 53 = 4353$.
• Byte 852 of segment 3 is mapped to $3200 + 852 = 4052$.
• A reference to byte 1222 of segment 0 results in a trap to the OS, since segment 0 is only 1000 bytes long.

Note. Since segments have different lengths and are allocated contiguously, segmentation can still suffer from external fragmentation; it simply moves the problem from whole processes to individual segments. Paging avoids it by using fixed-size blocks.

Paging

Segmentation still lets a process be placed non-contiguously, but each segment must be contiguous, so external fragmentation remains. Paging avoids external fragmentation and the need for compaction.

Every logical address is split into a page number $p$, which indexes the page table, and a page offset $d$, which is copied unchanged into the physical address. With a logical address space of $2^m$ and a page size of $2^n$, the high $m - n$ bits are the page number and the low $n$ bits are the offset.

Note. Paging has no external fragmentation, since any free frame can be used. It can have internal fragmentation: the last page of a process is usually not completely full.

Size of the Page Table

But what will be the size of the page table? Take a 32-bit machine with 4-byte (32-bit) page-table entries.

• If we map every byte: $2^{32}$ entries, each $32$ bits, so

which is far too big.

• If we map each word (4 B): $2^{30}$ entries $\times\ 4\,\text{B} = 4\,\text{GB}$, still too big.
• If we map each 256 B unit: $2^{24}$ entries $\times\ 4\,\text{B} = 64\,\text{MB}$.

The size of the page table can be reduced by using a larger page size, but this also increases internal fragmentation (more unused space in the last page).

Note. In general, with a $2^m$-byte address space, $2^n$-byte pages and $e$-byte entries, a flat page table has $2^{m-n}$ entries and takes $2^{m-n} \cdot e$ bytes. Typical page sizes today are 4 KB to 8 KB (with larger “huge pages” also supported).

Implementation of Address Translation

• The memory management unit (MMU) is the part of the CPU that does address translation.
• Recall the problem of page size: with 32-bit addresses and a 256 B page size, the page table is 64 MB (per process). It can be stored in memory, but then, to translate a virtual address, the MMU has to read the relevant page-table entry out of memory first.
• The hardware must provide page-table entries faster than that (most of the time), so it keeps some of them inside the MMU.

Translation Look-aside Buffer (TLB)

• If the required page-table entry is present in the TLB (a TLB hit), the MMU can do the translation fast.
• Otherwise it is a TLB miss: the entry must be fetched from the page table in memory (and added to the TLB). A TLB miss must be handled, possibly like the OS handles a page fault.

• Some TLBs allow entries to be wired down, meaning that they cannot be removed from the TLB. Typically, TLB entries for kernel code are wired down.
• Some TLBs store address-space identifiers (ASIDs) in each TLB entry. An ASID uniquely identifies each process and is used to provide address-space protection for that process.
  • When the TLB attempts to resolve virtual page numbers, it ensures that the ASID for the currently running process matches the ASID associated with the virtual page. If the ASIDs do not match, the attempt is treated as a TLB miss.
  • This allows the TLB to contain entries for several different processes simultaneously.
  • If the TLB does not support separate ASIDs, then every time a new page table is selected (on a context switch), the TLB must be flushed (erased) to ensure that the next running process does not use the wrong translation information.

Effective Memory-Access Time

Let $h$ be the TLB hit ratio, $T_A$ the TLB access (search) time and $M_A$ the memory-access time.

Simplifying, we can get

Multi-Level Paging

A flat page table has one entry for every page of the virtual address space, used or not:

• 32-bit virtual address: several MB per process.
• 64-bit virtual address: far too big.

Yet a process uses only a small part of its address space: code, data and heap at the bottom, the stack at the top, and many terabytes unused in between. Multi-level page tables use bits of the virtual address to index a tree of smaller tables, and simply leave out the tables for the unused regions.

Structure

The page number is split into an outer and an inner part. The outer part indexes the outer page table, whose entry gives the location of an inner page table; the inner part indexes that table, whose entry gives the frame number. In other words, the page table itself is paged.

Because translation works from the outer table inward, this is also called a forward-mapped page table. An outer entry whose region is unused is marked invalid, and its inner table is not stored at all.

Two-Level Example

Flat. There are $2^{32} / 2^{12} = 2^{20}$ pages, so the table is $2^{20} \times 8\text{ B} = 8$ MB.

Two-level. Split the 20-bit page number into two 10-bit parts, so that every table has $2^{10} = 1024$ entries:

• The outer page table has 1024 entries: $2^{10} \times 8\text{ B} = 8$ KB.
• Each inner table covers $2^{10}$ pages $= 4$ MB of address space. The two used regions fall in outer entries 0 and 1023, so only two inner tables are needed: $2 \times 2^{10} \times 8\text{ B} = 16$ KB.

Four-Level Example

Flat. There are $2^{64} / 2^{16} = 2^{48}$ entries, so the table is $2^{48} \times 8\text{ B} = 2^{51}$ B, about 2 PB.

Four-level. The 48-bit page number is split into four 12-bit parts, so every table has $2^{12}$ entries and is $2^{12} \times 8\text{ B} = 32$ KB:

• The program uses $2^{32} / 2^{16} = 2^{16}$ pages.
• One last-level table ($P_4$) holds $2^{12}$ pages, so we need $2^{16} / 2^{12} = 2^4 = 16$ of them.
• One $P_3$ table can point to $2^{12}$ $P_4$ tables, so a single $P_3$ table is enough, and likewise a single $P_2$ and a single $P_1$ table.

The saving is huge for a sparse address space. For a process that really used its whole address space, a multi-level table would be slightly larger than a flat one, because the upper levels come on top.

Effective Memory-Access Time with $L$ Levels

The price is time: on a TLB miss, the MMU now has to read one entry per level before it can fetch the data.

With $L = 1$ this is the formula for a flat page table above.

Hashed Page Tables

For 64-bit addresses even a hierarchy gets deep. With 4 KB pages and 1024-entry inner tables, a two-level split leaves a 42-bit outer index, i.e. an outer table of $2^{42}$ entries; paging that again still leaves $2^{34}$ bytes (16 GB) at the top. With these sizes, a full 64-bit address space needs six levels ($\lceil 52/10 \rceil$) if every table must fit in a page, i.e. six page-table accesses per TLB miss, plus one for the data. Galvin quotes seven levels for the 64-bit UltraSPARC. So for 64-bit architectures, hierarchical page tables are generally considered inappropriate.

A common alternative for address spaces larger than 32 bits is a hashed page table: the virtual page number is hashed, and each entry of the hash table holds a linked list of the pages that hash to it (to handle collisions). Each list element has three fields:

1. the virtual page number,
2. the frame number it maps to,
3. a pointer to the next element.

To translate, hash the virtual page number $p$ and walk the list of that entry, comparing $p$ with field 1. On a match, field 2 gives the frame $r$, and the physical address is $(r, d)$.

A variation for 64-bit address spaces is the clustered page table: each hash entry maps several consecutive pages (e.g. 16) instead of one. This suits sparse address spaces, where references are scattered over the address space.

Inverted Page Tables

An ordinary page table has one entry per virtual page of each process, so with many processes the page tables alone can take a lot of physical memory. An inverted page table turns this around:

• it has one entry for each physical frame, holding the virtual page stored in that frame and the process that owns it;
• there is only one page table in the whole system.

A virtual address is the triple $\langle \text{process-id}, \text{page-number}, \text{offset} \rangle$. The pair $\langle \text{process-id}, \text{page-number} \rangle$ is searched for in the inverted table; if it is found at entry $i$, the physical address is $\langle i, \text{offset} \rangle$. If no match is found, the access is illegal. The process id plays the role of an address-space identifier, which is needed because the table holds the pages of many address spaces at once.

Trade-offs.

• Less memory, more time: the table is sorted by physical frame but looked up by virtual page, so in the worst case the whole table must be searched. A hash table limits the search to one or a few entries, but adds a memory access: one virtual reference now needs at least two real memory reads, one for the hash entry and one for the page table. (The TLB is searched first, which hides most of this.)
• Shared memory is hard: sharing normally maps several virtual addresses to the same frame, but here each frame has only one entry, so it can record only one virtual address. A common fix is to allow only one mapping of the shared frame at a time; references through the other virtual addresses then cause page faults.

Virtual Memory

With virtual memory a process can run even when only part of it is in main memory: its pages stay on disk and are brought in when they are needed.

Paged Virtual Memory

Take a program (process) on a 32-bit machine, so its virtual address space is $2^{32}$ B = 4 GB, divided into 256 B pages. Suppose physical memory is only 16 MB, i.e. 24-bit physical addresses, so it holds $2^{24} / 2^8 = 2^{16}$ physical pages.

• A virtual address splits into a page number (the top 24 bits) and an offset within the page (the low 8 bits, since $2^8 = 256$). For 0x00000124, the page number is 0x000001 and the offset is 0x24.
• The page table has an entry for this mapping: virtual page 1 → physical page 0.
• The offset is not translated; it is simply copied into the physical address.

Note. Physical memory can be smaller than the virtual address space. Only some of the virtual pages are in main memory at any time; the rest stay on disk.

Address Translation

Each page-table entry holds the physical page number (PPN), a disk address, and a valid bit:

1. The virtual page number is used as an index into the page table.
2. If the entry’s valid bit is 1, the page is in main memory and the entry gives its PPN.
3. The physical address is the PPN followed by the unchanged offset.

Suppose there are many virtual pages for a process, which cannot all be stored in main memory. Then we store them on the hard disk, and the page table records where each one is:

For example, $P_1$’s page 0 is in frame 0, $P_2$’s page 2 is in frame 3, and $P_3$’s pages 0 and 2 are in frames 2 and 1. $P_1$’s page 3 is not in main memory at all: its entry is invalid, and its contents are only on disk.

Note. This is the idea behind virtual memory: a process can run even if only part of it is in memory. The page table, together with the disk address of each page, lets the OS bring pages in only when they are needed.

Page Fault

What happens when process $P_1$ now accesses a variable that is on its virtual page 3, which is not in main memory?

• It is detected on the attempt to translate the address: the page-table entry is invalid.
• It must be handled by the OS:
  1. identify a slot (frame) in main memory to be used;
  2. get the page contents from disk;
  3. update the page-table entry.
• The data can then be provided to the processor.

In more detail:

1. The process references a page, and the hardware finds its page-table entry marked invalid.
2. This causes a trap to the OS.
3. The OS checks that the reference was a legal address (otherwise the process is terminated) and finds where the page is on the backing store.
4. It finds a free frame and schedules a disk read of the missing page into it.
5. When the read is complete, it updates the page table to mark the page valid and record the frame.
6. The instruction that was interrupted by the trap is restarted; the process can now access the page as though it had always been in memory.

Page-Fault Handler

• The handler identifies a slot in main memory to be used.
• It must keep track of the available, unused physical pages, maybe in a free list.
• What if the free list is empty? That is, all the main-memory physical pages are already mapped to virtual pages.
  • Then the page-fault handler must identify a page to be replaced (evicted) from main memory. How it picks one is decided by a page-replacement policy (below).

Note. Paging in a page only when it is needed is called demand paging, and the component that does it is a lazy swapper: it never swaps a page into memory unless that page will be needed. In the extreme case, pure demand paging, a process starts with no pages in memory and faults on its very first instruction.

Performance of Demand Paging

As long as there are no page faults, the effective access time is the memory-access time $ma$. On a page fault, the page must first be read from disk. Let $p$ be the probability of a page fault ($0 \le p \le 1$):

The service time has three main parts: service the page-fault interrupt, read in the page, and restart the process. The first and third take microseconds; reading the page takes milliseconds (seek + latency + transfer), so it dominates.

If one access in 1000 faults ($p = 0.001$), EAT $\approx 8.2\ \mu$s: the machine is 40 times slower. For less than 10% slowdown:

i.e. fewer than one access in 399,990 may fault. The page-fault rate has to be kept very low.

Page-Replacement Policies

Question: how does the page-fault handler decide which page to replace when there is a page fault?

• In the worst case, the policy could always replace the page that is going to be accessed next. Each of these would require copying the virtual page from the hard disk to memory again.
• So the OS page-fault manager code must be written based on a realistic model of how programs behave with respect to memory.

Principle of Locality of Reference

Based on your experience, why do you expect that programs will display locality of reference?

For a program that displays good locality of reference, what would be a good page-replacement policy? Suppose a page fault occurs at time $t$ on a reference to page $P_x$: which page should be replaced from memory to make space for $P_x$? By locality, a page used recently is likely to be used again soon, so pick the page that was referenced least recently.

To compare policies we count page faults on a reference string (the sequence of pages referenced). The examples below use Galvin’s string with 3 frames:

Least Recently Used (LRU)

• Keep track of when each page was last referenced, with a timestamp.
  • The LRU page is the one with the smallest timestamp.
  • This requires a large number of comparisons.
• Or keep a stack of recently used pages.
  • The LRU page is at the bottom of the stack.
  • The stack must be updated on every memory access.
• So exact LRU might be too expensive without hardware support.

Alternate Page-Replacement Policies

1. First In, First Out (FIFO).

• Keep track of the order in which the pages came into memory, and replace the oldest.
• Advantage: it does not have to be updated when a page is re-accessed.
• Problem: unlike LRU, FIFO does not guarantee that the number of page faults will decrease if you increase the size of main memory. This is Belady’s anomaly (a stack-based algorithm never suffers from it).

2. Approximate LRU. For example:

• Maintain 1 bit of status information (a reference bit) with each physical page.
• Initially all bits are 0.
• Set a page’s bit to 1 when that page is referenced.
• Replace a page that has its bit equal to 0.
• Reset all bits to 0 every once in a while.

Note. The second-chance (clock) algorithm is a refinement: pages are kept in FIFO order, but if the oldest page has its reference bit set, the bit is cleared and the page gets a second chance (it is moved to the back) instead of being replaced.

3. Random.

• Randomly pick an $i$ between 1 and $n$, and replace the $i$th page.
• It suffers from Belady’s anomaly, since it can simulate FIFO (the random choices may happen to be the FIFO ones).

4. Optimal page replacement (OPT).

• An optimal page-replacement algorithm has the lowest page-fault rate of all algorithms, and will never suffer from Belady’s anomaly.
• Replace the page that will not be used for the longest period of time.
• Unfortunately, it is difficult to implement, because it requires future knowledge of the reference string. It is mainly used as a yardstick to compare other algorithms.

Stack Algorithms

LRU and OPT are both called stack algorithms.

For LRU, the set of pages in memory is the $n$ most recently referenced pages; with one more frame it is the $n + 1$ most recently referenced pages, which includes them. So adding frames can never add faults: stack algorithms cannot suffer from Belady’s anomaly.

Note.

• For a reference string $S$ and its reverse $S^R$, LRU has the same page-fault rate. Similarly, OPT has the same page-fault rate for $S$ and $S^R$. (On the string above, LRU gives 12 faults both ways and OPT gives 9; FIFO gives 15 forwards but 14 reversed.)
• The second-chance algorithm and random page replacement suffer from Belady’s anomaly.

Dirty Bit

Back to the page-fault handler: it identifies a slot in main memory to be used and gets the page content from disk.

• Problem: the victim page identified by the page-replacement algorithm might have been modified while it was in main memory.
• Then it cannot simply be overwritten by the incoming page, but must first be copied back to disk.
• Optimization: keep track of whether the page has been modified while in main memory, with a dirty (modified) bit. If the bit is 0, the copy on disk is still up to date and the page can be overwritten directly, saving one disk write.

If a fraction $d$ of the victim pages are dirty, a page fault costs one disk read for a clean victim and a write plus a read for a dirty one:

which goes into the EAT formula of demand paging above.

The Page-Table Entry

After all this information, a page-table entry holds:

Flow of TLB and Cache

Putting the pieces together, one memory reference goes through the TLB, then (on a miss) the page table, then (on a page fault) the disk, and finally the cache:

Allocation of Frames

How do we split the fixed number of free frames among the processes?

• Minimum: each process needs at least enough frames to hold all the pages that a single instruction can reference, since an instruction that faults part-way must be restarted. This is defined by the architecture. For example, if an instruction can reference one memory operand with one level of indirection, it needs at least 3 frames: the instruction, the indirect address and the operand.
• Maximum: the amount of available physical memory.

Allocation Algorithms

With $m$ frames and $n$ processes:

• Equal allocation: each process gets $m / n$ frames. With 93 frames and 5 processes, each gets 18, and the 3 left over form a free-frame pool.
• Proportional allocation: processes get frames according to their size. If process $p_i$ has virtual memory size $s_i$ and $S = \sum s_i$, then

(rounded to integers above the minimum, with $\sum a_i \le m$).

In both schemes a high-priority process is treated like a low-priority one. The ratio can instead be based on priority, or on size and priority together.

Global versus Local Replacement

• Global replacement: a process may select a replacement frame from all frames, even one allocated to another process. So a process’s number of frames can change.
• Local replacement: a process selects only from its own frames, so its number of frames stays fixed.

With global replacement a process cannot control its own page-fault rate: the pages it has in memory depend on the paging behaviour of other processes too, so the same program may take 0.5 s on one run and 10.3 s on the next. Local replacement does not have this problem, but it can hinder a process by not letting it use other, less used pages. Global replacement generally gives greater throughput, and is more commonly used.

Thrashing

If a process does not have enough frames for the pages it is actively using, it quickly page-faults. It must then replace a page, but all its pages are in active use, so it replaces one that is needed again right away, faults again, and so on.

Cause of Thrashing

Consider an OS that raises the degree of multiprogramming whenever CPU utilization is low, with global replacement:

1. A process enters a new phase and needs more frames. It faults and takes frames from other processes.
2. Those processes need their pages, so they fault too and take frames from others.
3. The faulting processes queue up for the paging device, the ready queue empties, and CPU utilization drops.
4. The scheduler sees low utilization and adds more processes, which take even more frames, causing even more faults.

Throughput plunges, the page-fault rate soars, and the effective access time increases. No work gets done, because the processes spend all their time paging.

Local replacement limits the effect: a thrashing process cannot steal frames from others and make them thrash too. But it does not solve the problem, since the thrashing processes still crowd the paging-device queue, and the page-fault service time rises for everyone.

To prevent thrashing, a process must be given as many frames as it needs. To estimate how many, we use the locality model: a process moves from locality to locality, where a locality is a set of pages actively used together (e.g. a function’s code, its local variables and some globals). If a process has enough frames for its current locality, it faults only until those pages are in, and then not again until it changes locality. If not, it thrashes.

Working-Set Model

The working set is the set of pages in the most recent $\Delta$ page references, the working-set window. A page in active use is in the working set; a page no longer used drops out $\Delta$ references after its last use. So the working set approximates the current locality.

The choice of $\Delta$ matters: too small and it does not cover the whole locality; too large and it overlaps several localities (if $\Delta = \infty$, it is every page the process has touched).

If $WSS_i$ is the working-set size of process $i$, the total demand for frames is

If $D > m$, the number of available frames, thrashing will occur. The OS gives each process frames for its working set; if there are frames left, it can start another process, and if $D$ exceeds $m$ it suspends a process and gives its frames to the others. This prevents thrashing while keeping the degree of multiprogramming as high as possible.

Tracking the exact moving window is expensive, so it is approximated with a timer interrupt and the reference bit. For example, with $\Delta = 10{,}000$ and an interrupt every 5000 references, the reference bits are copied and cleared at each interrupt, and a page with any of these bits set counts as in the working set.

Page-Fault Frequency

A more direct way to control thrashing is to control the page-fault rate itself. Set an upper and a lower bound on the desired rate for each process:

• if the rate is above the upper bound, the process needs more frames: give it another frame;
• if it is below the lower bound, it may have too many: take a frame away.

If the rate rises and no frames are free, a process is swapped out and its frames go to the processes with high fault rates.

Memory-Mapped Files

Reading a file with open(), read() and write() needs a system call and a disk access for every access. Instead, virtual memory can treat file I/O as ordinary memory accesses: memory mapping a file logically associates part of the virtual address space with the file.

• A disk block is mapped to a page in memory. The first access goes through ordinary demand paging: it page-faults, and a page-sized part of the file is read into a physical page.
• After that, reads and writes to the file are routine memory accesses, with no read()/write() system-call overhead.
• Writes to the mapped memory are not necessarily written to the disk at once. The OS may update the file when it checks whether the page has been modified (the dirty bit), and when the file is closed all mapped data are written back and removed from the process’s virtual memory.

In UNIX/Linux this is done with the mmap() system call. Solaris goes further and memory-maps every file, even one accessed with read()/write() (into the kernel address space in that case).

Sharing. Several processes can map the same file at once. Each process’s page table points to the same physical page, the one holding the copy of the disk block, so a write by one process is seen by all the others. Mapping can also be copy-on-write: processes share the file read-only, and get their own copy of any page they modify. Shared memory between processes is in fact often implemented by memory-mapping the same file into both address spaces.