Module 01 • COSC240

Physical Address Spaces & Monoprogramming

Trace the historical evolution of computer memory management from bare-metal monoprogramming without abstractions to hardware-assisted relocation and bounds protection using base and limit registers.

1. Bare-Metal Execution & The Monoprogramming Era

In the earliest digital computers—ranging from the vacuum-tube mainframes of the 1950s (such as the IBM 704 and 7094) to early personal computers running CP/M and MS-DOS—operating systems provided no memory abstraction whatsoever. Every program accessed raw physical memory directly.

When a compiler emitted an instruction such as:

MOV [0x1200], AX    ; Direct physical memory write
JMP 0x4000          ; Direct jump to physical memory address 0x4000

The value 0x1200 or 0x4000 was placed directly onto the processor's hardware address bus pins. The hardware RAM circuit responded directly to these physical voltage lines.

Historical Physical Memory Layouts

Under a monoprogrammed operating system, only a single user program runs at any given moment. Memory was divided into at most two contiguous partitions: the operating system routines and the user program:

The Fundamental Failure of Monoprogramming: Because user code could write to any physical address, a stray pointer or rogue instruction could overwrite kernel interrupt vectors or device tables, instantly freezing the machine. Furthermore, CPU utilization was dismal: whenever the running application waited for punch card readers, magnetic tape, or disk I/O, the processor sat completely idle.

2. Multiprogramming via Static Relocation & Linkage

To maximize CPU efficiency, operating systems needed to keep multiple programs resident in physical memory simultaneously. If Process $A$ blocked for I/O, the CPU could switch immediately to Process $B$.

However, if multiple programs are loaded concurrently, they cannot all occupy physical address 0x0000. Consider two independently compiled binaries that both execute JMP 0x1000. If Process $B$ is loaded at physical address 0x8000, its internal jump instruction must somehow jump to 0x9000 instead.

Static Software Relocation

Early systems solved this via static relocation during program loading (the IBM System/360 approach):

• The compiler produces relocatable machine code accompanied by a relocation dictionary identifying every absolute address reference.
• When the OS loader decides to load Process $B$ starting at physical address $L = \text{0x8000}$, the loader physically modifies the binary in RAM, adding offset $L$ to every jump and memory reference.

Limitations of Static Relocation:

1. High Load Latency: Loading an application requires parsing and rewriting thousands of memory words.
2. Immobility: Once loaded, a process cannot be easily swapped out to disk and returned to a different physical memory address without re-patching every pointer.
3. Zero Protection: Process $A$ can still forge an address pointing into Process $B$'s memory space and corrupt its data.

3. Dynamic Hardware Relocation: Base & Limit Registers

The breakthrough that enabled true, secure multiprogramming was dynamic hardware relocation, pioneered on computers such as the CDC 6600 and the GE-645.

Instead of modifying instructions at load time, the CPU incorporates two dedicated hardware registers into its execution pipeline: the Base Register and the Limit Register (also called the relocation and protection registers).

Under this architecture, every program is compiled as if it owns an isolated address space starting at virtual address $0$. The CPU pipeline transparently translates every memory reference in real time:

1. The CPU hardware compares the logical address against the Limit Register.
2. If the logical address is $\ge \text{Limit}$, the CPU raises a hardware exception (a segmentation fault or memory protection trap), terminating the process.
3. If the bounds check passes, the Base Register is added to the logical address on the hardware bus to generate the physical address for RAM.

4. Swapping vs. Overlays

In systems where physical RAM capacity is insufficient to hold all active applications simultaneously, operating systems resorted to two primary techniques:

Memory Overlays (Application-Managed)

In the 1960s and 1970s, programs were frequently larger than total core memory. Software engineers manually partitioned programs into a root module and mutually exclusive overlays:

• The root module remained permanently in memory.
• When Phase 1 of a compiler finished parsing, the overlay manager loaded Phase 2 (code generation) into the exact same memory partition previously occupied by Phase 1.

Defect: Overlays placed an immense intellectual burden on programmers, who had to manually construct complex overlay trees ($V = V_0 + \max(V_1, V_2)$) without kernel automation.

Process Swapping (Kernel-Managed)

Swapping automated multi-process concurrency by moving entire process memory images between RAM and a dedicated backing store (disk swap partition):

• When a process blocks on user input or runs out of execution quantum, the OS swaps its entire contiguous address space out to disk.
• Another ready process is swapped from disk into RAM.
• Base Register Benefit: Because base and limit registers relocate addresses dynamically at runtime, when a process is swapped back into RAM, it does not need to return to its original physical location. The OS simply loads it into any available contiguous free slot and updates its Base Register.

5. Memory Fragmentation: Internal vs. External

In any dynamic storage allocation system, memory fragmentation is the inevitable systemic inefficiency that arises as processes are allocated, expanded, and released over time. Understanding the exact mechanical distinction between Internal Fragmentation and External Fragmentation is fundamental to OS memory architecture.

1. Internal Fragmentation: Allocation Quantum Slack

Internal fragmentation occurs when memory is assigned in fixed-size allocation quanta or granularity blocks (such as fixed partition slots, power-of-two blocks in buddy allocators, or 4 KB paging frames). When an application's requested memory footprint does not align perfectly with the hardware or allocator's unit size, the system must round up to the nearest whole block.

Step-by-Step Numeric Walkthrough

Consider a standard operating system allocating memory in standard 4 KB (4096-byte) pages:

1. Program Request ($R$): Your application requests $5000\text{ bytes}$ ($R = 5000$, $S = 4096$).
2. Divide by Block Size: $R / S = 5000 / 4096 \approx 1.2207\text{ blocks}$.
3. Apply Ceiling Rounding ($\lceil \dots \rceil$): Because the hardware MMU cannot allocate fractions of a page, the OS rounds up to $\lceil 1.2207 \rceil = 2\text{ full blocks}$.
4. Compute Total Memory Allocated ($A$): $A = 2 \times 4096 = 8192\text{ bytes}$.
5. Determine Internal Slack ($W_{\text{internal}}$): $$ W_{\text{internal}} = A - R = 8192 - 5000 = 3192\text{ bytes} $$

These $3192\text{ bytes}$ are trapped inside the boundary of the second page allocated to your process. Because that physical page belongs exclusively to your process, the kernel cannot lend those remaining 3192 bytes to any other program.

Statistical Expectation: The Half-Block Rule

A central sizing question in operating system engineering is: If memory is allocated in fixed-size blocks of size $S$ (such as 4 KB paging frames), how much physical memory is wasted on average across all running applications?

Notice that when a process or thread allocates contiguous memory spanning multiple blocks, all blocks except the last one are 100% utilized:

• Block $1, 2, \dots, (k-1)$: Completely saturated with application data (0% waste).
• Block $k$ (Terminal Block): Contains the remaining spill payload, leaving internal slack space.

Internal fragmentation therefore exists exclusively in the final allocated block of each memory segment.

1. The Intuitive Symmetric Distribution Argument

Consider a standard 4 KB ($S = 4096\text{ bytes}$) page. The amount of data spilling into the final page depends on the requested size modulo $S$:

• If the spill is $4095\text{ bytes}$, the process fills nearly the entire page: $$ W_{\text{internal}} = 4096 - 4095 = 1\text{ byte} $$
• If the spill is $1\text{ byte}$, the OS must allocate a full 4096-byte page just for that single byte: $$ W_{\text{internal}} = 4096 - 1 = 4095\text{ bytes} $$
• If the spill is $2048\text{ bytes}$, exactly half the page is wasted: $$ W_{\text{internal}} = 4096 - 2048 = 2048\text{ bytes} $$

Across thousands of varied application allocations, these residual payloads are uniformly distributed across the interval $(0, S]$. Because every near-empty page ($4095\text{ B}$ waste) is statistically paired with a corresponding near-full page ($1\text{ B}$ waste), the expected mean converges symmetrically:

2. Continuous Calculus Derivation

Formally, let $x$ be a continuous random variable representing the bytes used in the final block ($0 < x \le S$). Assuming a uniform probability distribution $x \sim U(0, S)$, the constant probability density function is $f(x) = \frac{1}{S}$.

The expected internal slack $\mathbb{E}[W]$ is computed by integrating the waste function $W(x) = S - x$ over the entire block:

3. Architectural Trade-offs: Choosing Block Size ($S$)

The Half-Block Rule exposes an unavoidable architectural tension when operating system designers select hardware page sizes:

Design Dimension	Small Pages (e.g., 1 KB)	Large Pages (e.g., 64 KB or 2 MB)
Average Internal Slack	Low: $\frac{1024}{2} = 512\text{ bytes}$ per segment.	High: $\frac{65536}{2} = 32\text{ KB}$ (or 1 MB for huge pages).
Page Table Memory Footprint	Massive: Requires $4\times$ more Page Table Entries (PTEs) to map the same RAM.	Compact: Drastically fewer PTEs required in physical memory.
TLB Cache Coverage	Poor: TLB misses skyrocket due to narrow spatial range.	Superior: A single TLB entry covers large contiguous regions.

4. System-Wide Memory Slack Calculation

In an operating system executing $N$ concurrent processes where each process maintains distinct segments for Code (text), Data/Heap, and Stack, there are $3$ terminal pages per process ($3N$ terminal pages system-wide).

The total physical memory consumed purely by internal fragmentation across the system is:

On a modern machine with 16 GB to 64 GB of physical RAM, sacrificing $\approx 3\text{ MB}$ to internal slack is an extraordinarily small price to pay for the enormous speed and protection benefits of fixed-page hardware memory management.

2. External Fragmentation: Checkerboard Hole Formation

External fragmentation emerges in variable-sized contiguous allocation schemes (such as dynamic partitioning with Base and Limit registers). As processes of varying sizes enter and terminate at arbitrary times, free contiguous memory is fragmented into a scattered collection of small, non-contiguous "holes."

A system suffers from external fragmentation when the sum total of all free memory holes is sufficient to satisfy a process allocation request, but no single contiguous hole is large enough to hold the process.

Knuth's 50% Rule of Allocation

In The Art of Computer Programming (Vol. 1), Donald Knuth proved a fundamental statistical theorem governing contiguous dynamic storage allocation under steady-state conditions:

Consequence: If each hole is approximately the same average size as an allocated block, approximately one-third of all physical memory is rendered unusable due to external fragmentation: $$ \text{Fraction of Memory in Holes} \approx \frac{M}{N + M} = \frac{0.5 N}{N + 0.5 N} = \frac{0.5}{1.5} \approx 33.3\% $$

3. Resolving External Fragmentation: Memory Compaction

To reclaim checkerboarded free memory in a contiguous system, the operating system must execute Memory Compaction (relocation defragmentation). The kernel shifts all active processes toward one end of physical memory (usually toward address $0$), coalescing all isolated holes into a single contiguous pool.

Compaction Mechanics & Algorithms

• Sliding Compaction: Active segments are slid downward toward low memory while preserving their original relative ordering. This minimizes displacement distance and preserves data cache spatial locality.
• Two-Finger Compaction (LISP-style): Uses two pointers moving toward each other: a free-space scanner starting at memory zero and a process scanner starting at high memory. Processes from the top are moved into free slots at the bottom. While faster, it scrambles process ordering.

The Cost of Compaction

Compaction imposes severe architectural performance penalties:

1. Bus Saturation & Latency: Compacting 16 GB of active RAM across memory channels at 25 GB/s stalls the system for over 600 milliseconds—an unacceptable latency spike for interactive and real-time operating systems.
2. Hardware Prerequisite: Compaction is impossible under static relocation. It requires hardware-assisted dynamic relocation (Base and Limit registers), because every moved process must have its Base Register updated to reflect its new physical offset.
3. Direct Memory Access (DMA) Lockout: If a network card or disk controller is currently executing a DMA transfer into a process's buffer, that process cannot be moved until the hardware I/O finishes, locking memory in place.

4. Summary Comparison

Attribute	Internal Fragmentation	External Fragmentation
Location of Wasted Space	Inside the allocated partition or page boundary.	Between distinct allocated partitions (holes in RAM).
Root Cause	Fixed-size allocation granularity (quanta rounding).	Variable-sized allocations combined with dynamic allocation/freeing.
Typical Occurrences	Paging systems (4 KB pages), Buddy allocators.	Base/Limit dynamic partitioning, unpaged heap managers.
Architectural Solution	Smaller allocation quanta (e.g., fine-grained slab allocators).	Paging: Decouple contiguous virtual space from physical frames.