Chapter 24 of 38

Memory Management Basics

So far in this tutorial we have looked at how the OS shares the CPU between processes (scheduling) and how processes safely share data (synchronization and deadlocks). Now we move to the second most important resource: main memory (RAM).

Every program you run, whether it is Chrome, VS Code or a small C program, must be in memory to execute. Many programs run at the same time, and each one believes it has the memory all to itself. Making this work fast and safely is the job of memory management.

In this chapter we will learn the basic ideas that every later memory chapter builds on: why memory needs managing, logical vs physical addresses, address binding, the MMU with base and limit registers, dynamic loading and linking, and swapping.


Why Does Memory Need Managing?

The CPU can directly access only two kinds of storage: its own registers and main memory. Instructions are fetched from memory, and data must be brought into memory before the CPU can work on it. A program sitting on the SSD cannot run until it is loaded into RAM.

Here is roughly how the storage levels compare (exact numbers vary between machines, but the ratios are what matter):

Level

Typical size

Approximate access time

CPU registers

Hundreds of bytes

Less than 1 ns (one clock cycle)

CPU cache (L1 / L2 / L3)

KB to tens of MB

About 1 ns to 20 ns

Main memory (RAM)

8 GB to hundreds of GB

About 50 ns to 100 ns

SSD

Hundreds of GB to TB

Tens of microseconds

Hard disk

TB

Several milliseconds

RAM is fast compared with disk but limited in size, and it is shared by every running process and by the OS itself. Memory management has to solve several problems at once:

  • Allocation: which part of memory should each process get, and how do we keep track of free space?

  • Relocation: a program does not know in advance where in memory it will be loaded. It might be loaded at a different place each time, or even moved while running.

  • Protection: a process must not read or overwrite the memory of another process or of the OS. A bug in your program should crash only your program.

  • Sharing: sometimes processes should share memory, for example one copy of the C library used by hundreds of programs, or shared memory used for IPC (see Inter-Process Communication).

  • Using memory efficiently: keep as many useful processes in memory as possible and waste as little as possible.


A Process in Memory

Recall from Processes & Process States that a process's memory is divided into sections: text (code), data (global variables), heap (dynamic memory from malloc) and stack (function calls and local variables).

This small program prints the address of something from each section:

#include <stdio.h>
#include <stdlib.h>

int global = 1;                          /* data segment */

int main(void) {
    int local = 2;                       /* stack */
    int *heap = malloc(sizeof *heap);    /* heap  */
    printf("code  (main)  : %p\n", (void *)main);
    printf("data  (global): %p\n", (void *)&global);
    printf("heap  (malloc): %p\n", (void *)heap);
    printf("stack (local) : %p\n", (void *)&local);
    free(heap);
    return 0;
}

We ran it twice on 64-bit Linux:

Run 1                                Run 2
code  (main)  : 0x55a76047a1a9       code  (main)  : 0x5d75d0d9d1a9
data  (global): 0x55a76047d010       data  (global): 0x5d75d0da0010
heap  (malloc): 0x55a78eb6b010       heap  (malloc): 0x5d75d45ff010
stack (local) : 0x7ffc9fdf847c       stack (local) : 0x7ffd057fd33c

Two things stand out:

  • Code and data are at low addresses, the heap is above them, and the stack is far away at a much higher address. This matches the usual picture of a process's address space.

  • The addresses change on every run. This is ASLR (Address Space Layout Randomization), a security feature that loads each section at a random position so that attackers cannot predict where code or data lives. When we disabled ASLR for one run (with setarch -R), the addresses became identical on every run, starting with 0x5555555551a9 for main.

But wait: if the program is loaded at a different place each time, how does the code still work? And how can two copies of the same program run at the same time without clashing? To answer that, we need two kinds of addresses.


Logical vs Physical Addresses

A logical address (also called a virtual address) is an address generated by the CPU while running a program. A physical address is the actual address of a location in the RAM chips, the one that is put on the memory bus.

  • The set of all logical addresses a program can generate is its logical address space.

  • The set of physical addresses corresponding to them is its physical address space.

Every address your program prints with %p, every pointer in C, every address in the compiled machine code is a logical address. Your program never sees physical addresses.

A hardware device called the Memory Management Unit (MMU) sits between the CPU and memory and translates every logical address to a physical address, on every single memory access, at hardware speed.

            logical address                 physical address
  +-----+   (e.g. 0x1F40)    +-------+      (e.g. 0x9F40)      +--------+
  | CPU | -----------------> |  MMU  | ----------------------> | Memory |
  +-----+                    +-------+                         +--------+
     program only sees          translation done by
     logical addresses          hardware, set up by the OS

Proof: same address, different values

Here is a neat experiment. After fork() (see Process Creation (fork & exec)), the child changes a global variable, and both processes print the variable and its address:

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

int x = 100;                     /* a global variable */

int main(void) {
    pid_t pid = fork();
    if (pid == 0) {              /* child */
        x = 200;
        printf("child : x = %d, &x = %p\n", x, (void *)&x);
    } else {                     /* parent */
        wait(NULL);              /* let the child print first */
        printf("parent: x = %d, &x = %p\n", x, (void *)&x);
    }
    return 0;
}
child : x = 200, &x = 0x594e63c8b010
parent: x = 100, &x = 0x594e63c8b010

The same address holds two different values at the same time. That is impossible if 0x594e63c8b010 were a real location in RAM. It works because it is a logical address: the parent's MMU mapping sends it to one physical location, and the child's mapping sends it to a different one. (The exact address will be different on your machine and on every run, because of ASLR. The wait() call makes the output order fixed.)

This is the key idea of memory management: each process has its own private logical address space, and the OS plus MMU decide where it really lives in physical memory.

Logical (virtual) address

Physical address

Generated by

The CPU, while running the program

The MMU, after translation

Seen by the program?

Yes, pointers are logical addresses

No

Unique across processes?

No, two processes can use the same logical address

Yes, each refers to one real memory location

Address space size decided by

CPU architecture and OS (for example 48-bit on most x86-64 systems, 57-bit with 5-level paging)

Amount of RAM installed (and the hardware's limit)


Address Binding

When you write x = 200; in C, the variable x is a name. Somewhere along the way it must become a number, an address. Mapping names to addresses, and logical addresses to physical ones, is called address binding. A program goes through several stages, and binding can happen at any of them:

  source code  --compiler-->  object file  --linker-->  executable
  (names: x)                  (relocatable                (on disk)
                               addresses)                     |
                                                            loader
                                                              |
                                                              v
                                                     process in memory
                                                       (running)

Binding time

How it works

Consequence

Compile time

The compiler already knows where the program will sit in memory and writes absolute physical addresses into the code.

The program must always be loaded at that exact place. If that place changes, recompile. Example: old MS-DOS .COM programs.

Load time

The compiler produces relocatable code (addresses like "start + 1200"). The loader fills in real addresses when it loads the program.

Can load anywhere, but once loaded the process cannot be moved. Moving it means reloading it.

Execution time (run time)

The program uses logical addresses all the way; translation to physical happens on every access, by the MMU.

The process can be moved in memory even while it runs. Needs hardware support. All modern general-purpose OSes use this.

With compile-time and load-time binding, logical and physical addresses are the same. With execution-time binding, they differ, and that is exactly what our fork() experiment showed.


The Simplest MMU: Base and Limit Registers

Real MMUs use paging, which we will meet in Paging. But the core ideas are easiest to see in the simplest possible MMU, which uses just two registers.

  • The relocation register (also called the base register) holds the physical address where the process starts.

  • The limit register holds the size of the process's logical address space.

On every memory access, the hardware does this:

                      +-------------+          +---------------+
 logical address L    |  L < limit? |   yes    |  L + base     |   physical
 ------------------>  |             | -------> |               | ----------> Memory
                      +-------------+          +---------------+   address
                             | no
                             v
                  TRAP to OS: addressing error
                  (the process is usually killed,
                   like a "segmentation fault")

So the process sees addresses 0 to limit − 1, and they are mapped to physical addresses base to base + limit − 1.

Worked example

A process is loaded at physical address 40000 and is 12000 bytes long. So base = 40000, limit = 12000.

Logical address

Check L < 12000

Result

0

Yes

Physical 40000 + 0 = 40000

2500

Yes

Physical 40000 + 2500 = 42500

11999

Yes

Physical 40000 + 11999 = 51999 (last valid byte)

12000

No (12000 is not < 12000)

Trap, addressing error

15000

No

Trap, addressing error

If the OS later moves this process to physical address 70000, it only needs to copy the memory and set base = 70000. The program's logical addresses do not change at all; logical 2500 now becomes physical 72500. That is the power of execution-time binding.

Note on conventions: some textbooks describe a slightly different scheme where the program uses physical addresses directly and the hardware checks base ≤ address < base + limit. Both schemes give the same protection. The one above, where the base is added to a logical address, is the relocation-register scheme that also provides relocation. In exam questions, read carefully which scheme is being used.

Why this gives protection

  • A process cannot generate a physical address outside its own region: anything ≥ limit traps, and everything else is shifted into its own area.

  • The instructions that load the base and limit registers are privileged, so only the kernel (in kernel mode) can change them. A user program cannot simply set its own base to the OS's memory. (See OS Structure & Kernel for user mode and kernel mode.)

  • On a context switch, the dispatcher loads the next process's base and limit values, saved in its PCB (see Process Control Block & Context Switching).


Dynamic Loading

Must the whole program be in memory before it runs? Not necessarily.

With dynamic loading, a routine is not loaded into memory until it is first called. The main program is loaded and runs; when it calls a routine that is not in memory yet, that routine is loaded from disk on demand.

This helps when a program has a large amount of code that is rarely used, such as error-handling routines or rarely used features. That code never takes up memory unless it is needed.

Classic dynamic loading is something the program designs for; the OS may provide library routines to help. On Linux, a program can load a library at run time with dlopen() and look up functions with dlsym(). This is how many applications load plug-ins.

(Modern systems go much further: with demand paging, the OS automatically loads only the pages of a program that are actually touched. We will study it in Virtual Memory & Demand Paging.)


Static vs Dynamic Linking and Shared Libraries

Almost every C program calls printf, which lives in the C library. How does that code get into the program?

  • Static linking: the linker copies the library code into the executable file. Every program gets its own copy of printf, on disk and in memory.

  • Dynamic linking: the executable contains only a reference to the library. When the program starts (or when the function is first called), the dynamic linker finds the shared library and connects the program to it. Libraries used this way are called shared libraries (.so files on Linux, .dll on Windows).

We compiled a simple "Hello, memory!" program both ways:

gcc -std=c17 -Wall -Wextra hello.c -o hello_dynamic
gcc -std=c17 -Wall -Wextra -static hello.c -o hello_static
stat -c '%n: %s bytes' hello_dynamic hello_static
hello_dynamic: 15952 bytes
hello_static: 816936 bytes

The static version is about 50 times larger because it carries its own copy of the parts of the C library it uses. The ldd command lists the shared libraries a program needs:

ldd ./hello_dynamic
	linux-vdso.so.1 (0x000070f3a4b64000)
	libc.so.6 => /usr/lib/x86_64-linux-gnu/libc.so.6 (0x000070f3a4800000)
	/lib64/ld-linux-x86-64.so.2 (0x000070f3a4b66000)
ldd ./hello_static
	not a dynamic executable

(The hexadecimal load addresses change on every run because of ASLR.) The dynamic version depends on libc.so.6 (the C library) and ld-linux-x86-64.so.2 (the dynamic linker itself). linux-vdso.so.1 is a small piece of code the kernel maps into every process to make some system calls faster.

Why does dynamic linking matter for memory? Because the code of a shared library can be loaded into physical memory once and mapped into the logical address space of every process that uses it. A hundred running programs share one physical copy of the C library's code. This needs OS help, since normally the OS stops processes from touching each other's memory.

Static linking

Dynamic linking

Executable size

Large

Small

Memory use with many programs

Each has its own copy of library code

One shared copy of library code

Library bug fix

Every program must be relinked

Update the shared library once; all programs get the fix

Start-up

Slightly faster, no symbol resolution

Small extra work by the dynamic linker

Portability

Runs without the library installed

Needs a compatible library version on the machine

Dynamic loading

Dynamic linking

Delays loading a routine into memory until it is called

Delays linking to a library until load time or run time

Mainly the program's responsibility

Needs OS support (dynamic linker, shared memory mapping)

Saves memory by not loading unused code

Saves memory and disk by sharing one copy of library code


Swapping

What if the processes we want to run need more memory than we have? One old and simple answer is swapping.

Swapping means temporarily moving a process (or part of it) out of main memory to a fast disk area called the backing store (or swap space), and bringing it back into memory later to continue execution.

        Main memory                         Backing store (disk)
   +-------------------+                   +-------------------+
   |        OS         |                   |                   |
   +-------------------+   swap out        |   +-----------+   |
   |    Process P1     | ----------------> |   |    P1     |   |
   +-------------------+                   |   +-----------+   |
   |    Process P2     |                   |                   |
   +-------------------+   swap in         |   +-----------+   |
   |      (free)       | <---------------- |   |    P3     |   |
   +-------------------+                   |   +-----------+   |
                                           +-------------------+

Swapping lets the total memory used by all processes be larger than physical RAM, which increases the degree of multiprogramming.

Where does a swapped-in process go? With compile-time or load-time binding, it must return to the same place. With execution-time binding, it can go anywhere: just set a new base register value. This is another reason modern systems use execution-time binding.

The cost. Swapping a whole process is slow because the transfer time is proportional to the amount of memory moved. For example, if a process uses 200 MB and the disk transfers 100 MB per second:

Swap out time = 200 MB ÷ 100 MB/s = 2 seconds
Swap in time  = 200 MB ÷ 100 MB/s = 2 seconds
Total         ≈ 4 seconds  (ignoring disk latency)

Compare that with a CPU time slice of a few milliseconds. This is far too slow to do routinely. Another catch: a process waiting for I/O into its memory buffer should not be swapped out, or the device might write into memory that now belongs to someone else.

Swapping today. Modern systems rarely swap entire processes. Instead they swap individual pages (small fixed-size pieces, covered in Paging), and only when memory is under pressure. On Linux, the "swap" partition or swap file you may have created during installation is used this way. Mobile systems generally avoid traditional swapping to flash storage; Android, for example, compresses memory in RAM (zram) and, when memory is still short, kills background apps that can be restarted later.


Ways to Allocate Memory: A Roadmap

The base-and-limit scheme assumes each process occupies one contiguous block of physical memory. That is the simplest approach, but not the only one. The next few chapters cover the main techniques:

Technique

Main idea

Chapter

Contiguous allocation

Each process gets one continuous block of memory

Contiguous Memory Allocation & Fragmentation

Paging

Memory split into equal-size frames; a process can be scattered across them

Paging, Page Tables & TLB

Segmentation

Memory split into variable-size logical units (code, stack, data…)

Segmentation

Virtual memory

Only parts of a process need to be in RAM; the rest stays on disk

Virtual Memory & Demand Paging


Common Mistakes

  • "The pointer value I print is the real RAM address." No. In user programs on modern systems, every pointer is a logical (virtual) address. The fork experiment proves it.

  • "Logical address space and physical address space are always the same size." They are independent. A 64-bit process can have a huge logical address space on a machine with only 8 GB of RAM.

  • Off-by-one with the limit register. Valid logical addresses are 0 to limit − 1. Address equal to the limit is already out of range.

  • Mixing up dynamic loading and dynamic linking. Loading is about when code is brought into memory; linking is about when references to library code are resolved, and it allows sharing.

  • Thinking the MMU is software. The OS sets up the MMU's tables and registers, but the translation itself is done by hardware on every memory access. Doing it in software would make every memory access many times slower.

  • "Swapping is the same as virtual memory." Classic swapping moves whole processes. Virtual memory with demand paging moves individual pages and lets a process run with only part of it in memory.


Interview Questions

What is the difference between a logical and a physical address?

A logical (virtual) address is generated by the CPU for a running program; a physical address is the actual location in RAM. The MMU translates logical to physical addresses at run time. Programs only ever see logical addresses.

What is the MMU?

The Memory Management Unit is a hardware device that translates every logical address generated by the CPU into a physical address, and enforces protection by trapping on illegal accesses.

What are the three times at which address binding can be done?

Compile time (absolute code, fixed location), load time (relocatable code, fixed after loading), and execution time (translation on every access by the MMU, so the process can move while running). Modern OSes use execution-time binding.

How do base and limit registers provide protection?

Every logical address is compared with the limit register; if it is not smaller, the hardware traps to the OS. Valid addresses are added to the base register. Only the kernel can change these registers because the instructions are privileged, so a process cannot reach outside its region.

A process has base 40000 and limit 12000. What is the physical address of logical address 2500? What about 12000?

2500 maps to 40000 + 2500 = 42500. Logical address 12000 is not less than the limit, so it causes a trap (addressing error).

Why can a parent and child print the same address for a variable but see different values?

Because the printed address is a logical address. After fork, each process has its own address space, and the MMU maps that same logical address to different physical locations for parent and child.

What is the difference between dynamic loading and dynamic linking?

Dynamic loading postpones loading a routine until it is called, mainly to save memory for rarely used code. Dynamic linking postpones linking a library until load time or run time, which allows one copy of a shared library to be shared by many processes and updated without relinking programs.

What is swapping and why is it expensive?

Swapping moves a process out of memory to a backing store and later back in. It is expensive because transfer time grows with the size of the process; moving hundreds of MB takes seconds, far longer than a CPU time slice. Modern systems swap individual pages instead of whole processes.

What is ASLR?

Address Space Layout Randomization places the code, heap, stack and libraries of a process at random logical addresses each time it runs, making it harder for attackers to predict where to jump or what to overwrite.


Summary

  • The CPU can directly access only registers and main memory, so programs must be in RAM to run. Memory management handles allocation, relocation, protection, sharing and efficiency.

  • Programs use logical (virtual) addresses; the MMU translates them to physical addresses in hardware on every access.

  • Address binding can happen at compile time, load time or execution time. Modern systems use execution-time binding, which lets processes be placed and moved anywhere.

  • The simplest MMU uses a relocation (base) register and a limit register: if L < limit, physical = base + L, else trap. Only the kernel can change these registers.

  • Dynamic loading loads routines only when called; dynamic linking connects to shared libraries at load or run time so one copy can be shared.

  • Swapping moves processes between RAM and a backing store; whole-process swapping is slow, so modern systems swap pages instead.

  • ASLR randomises where each section of a process is placed, which is why printed addresses change from run to run.

Next, we look at the simplest way to give each process its own region of memory, and the problem of wasted space it creates, in Contiguous Memory Allocation & Fragmentation.