LOGICAL ADDRESS (virtual address) generated by the CPU as the program runs. What your pointer contains. Every process has its own logical address space starting at 0. PHYSICAL ADDRESS the actual address on the memory bus, seen by the RAM chips. There is exactly one physical address space, shared by everything. The set of all logical addresses a process can generate is its LOGICAL ADDRESS SPACE; the set of corresponding physical addresses is its PHYSICAL ADDRESS SPACE. THE MEMORY MANAGEMENT UNIT (MMU) translates one to the other, in hardware, on EVERY access. Software translation would be far too slow — a single instruction may touch memory three times. COMPILE-TIME vs LOAD-TIME vs EXECUTION-TIME BINDING: COMPILE TIME the absolute address is fixed when compiling. The program MUST be loaded at that address. Used in embedded firmware with no MMU. LOAD TIME the compiler emits relocatable code; final addresses are fixed when the program is loaded. Cannot move afterwards. EXECUTION TIME binding is deferred until each access, done by the MMU. The process CAN be moved while running. → this is what every general-purpose OS uses, and it is what makes swapping and paging possible. THE SIMPLEST TRANSLATION — BASE AND LIMIT REGISTERS: physical = logical + base if logical < limit otherwise → TRAP (addressing error) base = where the process starts in physical memory limit = how large it is Two registers give BOTH relocation and PROTECTION. The limit check is the entire mechanism preventing one process from reading another's memory, and it costs one comparison. WORKED EXAMPLE: base = 14000, limit = 3000 logical 0 → physical 14000 ✔ logical 346 → physical 14346 ✔ logical 2999 → physical 16999 ✔ logical 3000 → 3000 ≥ 3000 → TRAP logical 4000 → TRAP Note the check is against the LOGICAL address before adding the base — checking afterwards would allow wraparound attacks.

/* Verified on Darwin arm64, 16 GiB RAM, 16 KB pages. */
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

int global_var = 42;              /* data segment  */
static int static_var = 7;        /* bss           */
const char *rodata = "read only"; /* rodata        */

int main(void) {
    int stack_var = 1;
    void *heap1 = malloc(64), *heap2 = malloc(64);
    printf("text (main)      %p\n", (void*)main);
    printf("rodata           %p\n", (void*)rodata);
    printf("data (global)    %p\n", (void*)&global_var);
    printf("bss  (static)    %p\n", (void*)&static_var);
    printf("heap  1          %p\n", heap1);
    printf("heap  2          %p\n", heap2);
    printf("stack            %p\n", (void*)&stack_var);
    return 0;
}
MEASURED OUTPUT:
text (main)      0x1045b84f8
rodata           0x1045b868c
data (global)    0x1045c0000
bss  (static)    0x1045c0010
heap  1          0x104d8d940
heap  2          0x104d8d980   (+64 bytes)
stack            0x16b846b48
page size        16384
stack - heap gap 1.60 GB

READ THOSE ADDRESSES — every one is a LOGICAL address, and the layout matches the textbook picture exactly: 0x1045b84f8 text (code) lowest 0x1045b868c rodata (string literal) just above text 0x1045c0000 data (initialised globals) 0x1045c0010 bss (uninitialised statics) — 16 bytes on 0x104d8d940 heap ~8 MB above data 0x16b846b48 stack 1.60 GB above the heap highest THE 1.60 GB GAP is the point. Nothing occupies it. The process's logical address space is far larger than the memory it uses, and the gap exists so the heap can grow up and the stack can grow down without meeting. A machine with 16 GiB of RAM cannot have 1.6 GB of untouched memory reserved per process — 599 processes would need a terabyte. The gap costs NOTHING because it is only logical: no page table entry exists for it, and no physical frame is allocated. Touch an address in the gap and you get SIGSEGV, because there is nothing to translate to. heap2 − heap1 = exactly 64 bytes, so malloc placed the two 64-byte requests adjacently with no header between them visible at this granularity. THE SPARSE ADDRESS SPACE is the whole idea of virtual memory: allocate address RANGES freely, commit PHYSICAL frames only when touched. That is why a 64-bit process can mmap 1 TB of address space on a 16 GB machine and only fail when it actually writes too much.

EXTERNAL FRAGMENTATION free memory exists but is split into pieces too small to satisfy a request. [used 100K][free 30K][used 200K][free 40K][used 50K] total free = 70K, but a 50K request FAILS because no single hole is large enough. · afflicts CONTIGUOUS allocation and SEGMENTATION · solved by COMPACTION (move processes to coalesce holes) — which is only possible with execution-time binding · the 50-PERCENT RULE: with first-fit, statistical analysis shows that for N allocated blocks about 0.5N are lost to fragmentation, i.e. up to one-third of memory wasted INTERNAL FRAGMENTATION memory allocated but unused, INSIDE an allocated unit. · afflicts PAGING: the last page of a process is rarely full · average waste = half a page per process (per segment) MEASURED ON THIS MACHINE — page size 16 KB, not the 4 KB most textbooks assume: average internal fragmentation per process = 16384 / 2 = 8192 bytes = 8 KB across 599 processes ≈ 4.8 MB wasted With 4 KB pages it would be 2 KB × 599 ≈ 1.2 MB. The larger page trades more internal fragmentation for smaller page tables — a deliberate design choice, not an accident. ALLOCATION STRATEGIES for contiguous memory: FIRST FIT scan from the start, take the first hole that fits. Fastest. BEST FIT take the SMALLEST hole that fits. Leaves tiny unusable holes; must search the whole list. WORST FIT take the LARGEST hole. Performs worst in practice. NEXT FIT first fit, but resume scanning where you stopped. EMPIRICAL RESULT: first fit and best fit both beat worst fit on storage utilisation, and first fit is generally FASTER. So first fit is the practical winner — best fit's extra search buys nothing.