Process address space

Why it exists

A program is written without knowing where in memory it will run. Its addresses must somehow turn into the real addresses of the machine, and different processes must be kept apart even though each believes it has the whole memory to itself. The idea that makes this possible is that the addresses a program generates (logical, or virtual, addresses) are different from the addresses the memory sees (physical addresses), with hardware translating between them for every reference. This page explains that separation, when the translation can be fixed, and how a process's address space is laid out; paging and segmentation then give the most important translation schemes.

Prerequisites

The layout of a C program's memory (text, data, bss, heap and stack) is described in C memory layout, and the contiguous-allocation setting in memory management basics.

Precise definitions

Logical (virtual) address. The address generated by the CPU when the process executes an instruction or accesses data. The set of all logical addresses a process can generate is its logical address space. With $n$-bit addresses the logical address space has $2^n$ addresses.

Physical address. The address seen by the memory hardware (loaded into the memory address register). The set of physical addresses is the physical address space; with $m$-bit physical addresses and byte addressing it has $2^m$ bytes at most.

Memory-management unit (MMU). The hardware that maps logical addresses to physical addresses at run time. The program only ever sees logical addresses; the physical addresses are never visible to it.

Address binding. Mapping the symbolic addresses in the source (variable and function names) to actual addresses. It can happen at three times:

Logical and physical addresses are the same under compile-time and load-time binding, and differ under execution-time binding.

Base and limit registers. The simplest MMU. A base (relocation) register holds the physical address where the process starts; a limit register holds the size of its logical address space. For every address the CPU generates:

1. if the logical address is at least the limit, trap to the operating system (an addressing error);
2. otherwise the physical address is the logical address plus the base.

The legal logical addresses are $0, 1, \ldots, \text{limit} - 1$. The registers can be loaded only by privileged instructions, so a process cannot change its own protection. Because each process has its own base and limit (saved and restored at a context switch), one process cannot reach another's memory, and moving a process only needs a new base value.

Dynamic loading. A routine is not loaded until it is called; unused routines never occupy memory. Static linking: the libraries are combined into the executable. Dynamic linking: linking is postponed until run time; a small stub finds the library routine, loading it if needed; the library can be shared by many processes (a shared library, a DLL) and updated without relinking every program.

The layout of a process's logical address space. From low addresses: text (code, read-only, shareable), initialised data, uninitialised data (bss), the heap (grows upward) and the stack (grows downward from the top), with a large unused gap between heap and stack. The kernel is usually mapped into a protected part of every process's address space (for example the top part on 32-bit systems), so a system call does not need to change the address space. The exact order and the addresses are system dependent and are often randomised for security. Each process has its own address space: the same logical address in two processes refers to different physical memory.

Swapping and address binding. A process swapped out can be brought back to a different place only if addresses are bound at execution time (swapping).

How it works

The animation is the base and limit MMU at work: base 14000, limit 3000. Addresses below 3000 are relocated; the address 3000 itself is not legal (the legal range is 0 to 2999), nor is 3250.

Worked examples

#include <stdio.h>
 
/* relocation: the MMU adds the base to every address the program generates, after checking it against the limit */
struct mmu { unsigned base, limit; };
 
static int translate(struct mmu m, unsigned logical, unsigned *physical) {
    if (logical >= m.limit) return 0;
    *physical = m.base + logical;
    return 1;
}
 
int main(void) {
    struct mmu a = {14000, 3000}, b = {40000, 1200};
    unsigned p;
    unsigned addrs[3] = {346, 1199, 2999};
    for (int i = 0; i < 3; i++) {
        printf("logical %4u: process A -> %s", addrs[i], translate(a, addrs[i], &p) ? "" : "trap");
        if (translate(a, addrs[i], &p)) printf("%u", p);
        printf(";  process B -> ");
        if (translate(b, addrs[i], &p)) printf("%u\n", p); else printf("trap\n");
    }
    /* the same logical address in two processes reaches different physical memory; the logical space of each is 0 .. limit - 1 */
    printf("logical space of A: %u addresses, of B: %u addresses\n", a.limit, b.limit);
    return 0;
}

logical  346: process A -> 14346;  process B -> 40346
logical 1199: process A -> 15199;  process B -> 41199
logical 2999: process A -> 16999;  process B -> trap
logical space of A: 3000 addresses, of B: 1200 addresses

Cheat box

Traps and GATE patterns

Connections

The layout of text, data, heap and stack in a C program is traced from a real run in C memory layout. Base-and-limit hardware is the simplest of the translation schemes; paging replaces the single base with a table of frame numbers, and segmentation gives every segment its own base and limit. Because the logical space can exceed physical memory, virtual memory keeps only part of it in RAM.

PYQs

A computer system supports 32-bit virtual addresses
as well as 32-bit physical addresses. Since the virtual
address space is of the same size as the physical
address space, the operating system designers decide
to get rid of the virtual memory entirely. Which one
of the following is true?

Self-check

Revision card

References