Two independently linked programs both place code at virtual address 0x1000, grow a heap upward, and grow a stack downward. Loading both programs into one physical memory creates an immediate conflict if an address names a physical byte directly. Relocating every pointer when a process moves is not sufficient: pointers can be stored in files, registers, data structures, or generated while the program runs. A faulty process could also manufacture the physical address of another process’s data.
The missing mechanism is a controlled naming layer. A process issues a virtual address; the processor interprets that address through the process’s current address space; translation either yields an authorized physical address or raises an exception before the access completes.
Isolation invariant. A user-mode memory access may affect or reveal a physical byte only if the active address space contains a mapping for the requested virtual address and that mapping authorizes the requested operation.
The invariant contains three independent questions: Which address-space context is active? Which physical storage does the name select? Which operations does the mapping permit? Omitting any one turns translation into relocation without protection.
Names require a context
A virtual address is not globally meaningful. Model an address space as a partial function
Here is a virtual byte address, and is a physical byte address. The same bit pattern can produce different results under different contexts:
| Context and access | Mapping | Result |
|---|---|---|
process A reads 0x1800 | private data → frame 9, read/write | physical byte in frame 9 |
process B reads 0x1800 | private data → frame 27, read/write | a different physical byte |
process B executes 0x1800 | frame 27, read/write only | protection fault |
process C reads 0x1800 | no mapping | translation fault |
Two virtual names may also intentionally denote one physical object. Shared libraries, shared-memory regions, and file-backed mappings rely on this aliasing. Isolation therefore does not require one-to-one translation. It requires that every alias be deliberate, authorized, and revoked safely.
Retrieval — close the prose before answering. Why is the pair (virtual address, process identity) still insufficient to decide whether a store may proceed?
Reveal the diagnostic answerExpandCollapse
Identity and virtual address select a candidate mapping, but authority is operation-specific. A read-only code mapping may authorize a load and instruction fetch while rejecting a store. An answer that mentions only different physical locations has recovered relocation but not protection.
Address translation and operation authority
Evaluate each statement regarding virtual address translation, memory isolation, and paging invariants:
Classify each option as correct or incorrect, or leave uncertain options unanswered (“I don't know”) and verify at any time.
Relocation by base and bound
The smallest useful translation mechanism assigns one contiguous physical region to a process. Let be the physical base and the length of the process’s virtual region. For an unsigned virtual address
The bounds check must occur before the addition. If a fixed-width addition wraps, checking the physical result can authorize an address outside the allocated region.
Worked trace: a valid load and an overflow attack
Assume 16-bit addresses, B = 0x4000, and L = 0x1800.
- A load from
v = 0x02F0passes because0x02F0 < 0x1800. - Translation yields
0x4000 + 0x02F0 = 0x42F0. - A load from
v = 0xF100fails the virtual bound and must fault.
An incorrect implementation first computes a 16-bit sum and then tests whether the result lies below B + L:
// Incorrect: wrapped addition occurs before authority is established.
uint16_t physical = base + virtual;
if (physical < base + length)
return physical;
For base = 0x4000 and virtual = 0xF100, the sum wraps to 0x3100. A weak upper-bound-only test may accept the wrapped result. The safe form compares virtual with length, using an unsigned type whose width is part of the machine contract, and adds only after acceptance.
Worked trace: relocation without pointer rewriting
Process P executes a load from virtual 0x0710 while B = 0x2000; the physical access is 0x2710. The scheduler later runs P from a region beginning at 0x9000. Updating the privileged base register changes the same instruction’s physical access to 0x9710. P’s register and memory values remain virtual; no embedded pointer is rewritten.
Base-and-bound provides cheap relocation, but it imposes one contiguous extent. A 1 MiB heap and a 1 MiB stack separated by 1 GiB of unused virtual space either reserve that physical hole or cannot be represented by one pair. Growing the region can require physical relocation. Sharing one read-only library while keeping data private also needs more than one extent.
Application — execute before revealing. A 20-bit machine gives a process B = 0x62000 and L = 0x2A000. Classify virtual accesses 0x01FFC, 0x29FFF, and 0x2A000; compute every valid physical address.
Reveal the trace and error diagnosesExpandCollapse
0x01FFC < 0x2A000, so it maps to0x63FFC.0x29FFF < 0x2A000, so it maps to0x8BFFF, the final byte in the region.0x2A000equals the length and is outside the half-open interval[0, L); it faults.
Accepting the last address indicates an inclusive-upper-bound error. Subtracting one from every physical result indicates confusion between a region length and its final index.
Paging derives from sparse allocation
Paging divides virtual memory and physical memory into equal-size units. Let page size bytes. For virtual address
A page-table entry maps a virtual page number (VPN) to a physical frame number (PFN) and carries control state such as validity and permissions. If the entry is valid and authorizes the access,
The offset is preserved because pages and frames have the same size. Translation changes the container, not the byte’s position within that container.
Worked trace: noncontiguous physical placement
Take a 16-bit virtual address, 1 KiB pages, and these entries:
| VPN | PFN | Permission | Present |
|---|---|---|---|
0x00 | 0x12 | read + execute | yes |
0x01 | 0x2B | read + write | yes |
0x02 | — | — | no |
0x3F | 0x07 | read + write | yes |
Because the low ten bits are the offset.
- Virtual
0x0634has VPN1and offset0x234. A read maps to0x2B × 0x400 + 0x234 = 0xAE34. - Executing
0x0634reaches a present page but violates itsread + writepermission; the result is a protection fault, not a translation. - Reading
0x0A10selects VPN2, whose entry is absent; the result is a not-present fault. - Writing
0xFE20selects VPN0x3F, offset0x220, and maps to0x1E20.
The final case demonstrates non-monotonic placement: a high virtual address can map to a low physical frame. Sorting virtual addresses does not sort physical addresses.
Fragmentation is relocated, not eliminated
Paging removes external fragmentation from allocation of individual frames: any free frame can hold any virtual page. It introduces internal fragmentation in the partially used final page of an allocation. An object of bytes consumes
bytes of mapped capacity, wasting that quantity minus when it cannot share the final page.
A 10,500-byte isolated region with 4 KiB pages needs three pages: 12,288 bytes, of which 1,788 bytes are unused. The waste is a property of allocation granularity, not evidence that those physical frames are adjacent.
Transfer — change the granularity. The same 10,500-byte region uses 2 KiB pages. Compute mapped capacity and waste, then state one cost that the smaller pages increase.
Reveal the calculation and trade-offExpandCollapse
Six 2 KiB pages provide 12,288 bytes, so this particular size still wastes 1,788 bytes. Smaller pages do not guarantee less waste for every object. They increase the number of mappings and therefore page-table memory and translation-cache pressure. A response that claims the waste must halve has treated an average tendency as a per-object theorem.
Constructing a process address space
An address space is a set of regions with different backing objects and authorities, not a promise that every address between the lowest and highest mapping is valid.
| Region | Typical backing | Initial materialization | Common authority |
|---|---|---|---|
| executable text | executable file | file page on demand or at load | read + execute |
| read-only data | executable file | file page | read |
| writable data | private file image | file page, then private on write | read + write |
| heap | anonymous memory | zero-filled page on first touch | read + write |
| memory-mapped file | file object | file page on demand | mapping-dependent |
| guard interval | none | never | no access |
| user stack | anonymous memory | policy-bounded growth | read + write, non-execute |
The address-space manager records region-level intent; page tables record the translations currently installed. A valid region need not have a resident page yet. Conversely, a page-table entry left behind after its region is removed is stale authority.
Worked trace: stack growth or invalid access?
Assume a stack region may grow into one designated unmapped page below its current lowest mapped page, down to a fixed maximum size. Its current mapped interval is [0x7FFF_D000, 0x8000_0000); [0x7FFF_C000, 0x7FFF_D000) is the current growth page, and the page below that is a non-growable guard.
- A store at
0x7FFF_CFF8lands eight bytes below the current mapping, in the permitted one-page growth interval. The kernel may allocate a zeroed frame, install a non-executable user mapping, and retry. - A store at
0x7FFE_0000is far below the growth frontier. Treating every lower address as stack growth would let a stray pointer consume arbitrary memory and collide with another region. The access must fail. - An instruction fetch from
0x7FFF_E100targets a stack page. Presence is not enough; non-execute authority causes a protection fault.
The growth policy belongs to region metadata. A page-table miss alone cannot distinguish an intentional lazy page from an invalid pointer.
Application — design a map. Two worker processes need private 64 KiB heaps, one 12 KiB read-only lookup table shared at different virtual addresses, and one writable 8 KiB communication ring shared at the same virtual address. Draw the VPN→PFN relations for 4 KiB pages and state the permission invariant for each object.
Reveal an architectural verification modelExpandCollapse
A complete design has sixteen distinct heap frames per process, three table frames mapped into both address spaces without write permission, and two ring frames mapped read/write into both address spaces. The virtual addresses of the table may differ because sharing is defined by common PFNs, not common VPNs. The ring’s equal virtual address is a convenience, not a requirement. Complete verification requires separate PTE permissions in each address space and an explicit rule that no private heap PFN appears in the other process’s user mappings.
Common defects:
- allocating six table frames loses sharing;
- mapping the table writable loses its integrity contract;
- requiring equal VPNs confuses virtual naming with physical identity;
- sharing page-table entries between processes without context separation can expose unrelated mappings.
Boundary failures and adversarial cases
A pointer is not a physical address
Passing a user pointer to a device for direct memory access without pinning and mapping its pages gives the device an address in the wrong namespace. A device may use a bus or I/O virtual address, and the process mapping may change while the operation is in flight. Translation must occur in the correct agent’s context.
Presence does not imply authority
Marking code present and user-accessible while accidentally retaining write permission defeats write-xor-execute policy. The access does not fault because the mapping itself grants the wrong authority. Fault-handler testing cannot detect every over-permissive mapping; mapping construction needs invariant checks.
Unmapping is a concurrent revocation
Removing a page-table entry does not prove that no processor can use a cached translation. The kernel must invalidate stale translation state on every relevant processor before reusing the physical frame for a new security domain. Detailed invalidation mechanics are outside this scope, but the authority rule is immediate: frame reuse is forbidden until revocation is globally complete.
Aliases can disagree about policy
Mapping one physical frame writable through one alias and executable through another can defeat a policy checked per mapping. A system that requires write-xor-execute must reason about all aliases to the frame, not each PTE in isolation.
Retrieval plus boundary check. Classify each statement as invariant, common implementation choice, or false claim:
- Page translation preserves the offset within a page.
- Every process must map its shared library at the same virtual address.
- A valid PTE guarantees a user store may proceed.
- Any free physical frame can hold a virtual page of the same configured page size.
Reveal classificationsExpandCollapse
- Invariant for equal-size paging: the mapping substitutes the frame number and preserves the offset.
- False claim: different VPNs may map the same library frames; position-independent code makes this practical.
- False claim: user/supervisor and read/write/execute permissions still govern the operation.
- Implementation property under the stated paging model: equal-size frames eliminate the need for contiguous placement, although devices, huge pages, coloring, or physical constraints may narrow the eligible set.
Deep Practice
Solve these problems to test and consolidate your understanding. Complete worked solutions and diagnostic hints are available for each problem.
Exercise 4.1.1: Virtual Page Number and Offset Bitwise Decomposition
A processor uses 32-bit virtual addresses with a 4 KiB page size bytes). Given the virtual address 0x0045A8C4, determine:
- The page offset in hexadecimal.
- The Virtual Page Number (VPN) in hexadecimal.
- The resulting 32-bit physical address if the page table maps this VPN to Physical Frame Number (PFN)
0x1B02.
HintExpandCollapse
With 4 KiB pages, the lower 12 bits form the offset, while the upper 20 bits form the VPN.
Worked solutionExpandCollapse
- Page offset: With a 4 KiB page size, the offset width is bits (the lowest 3 hex nybbles). For
0x0045A8C4, the lowest 12 bits are0x8C4. - Virtual Page Number (VPN): Shifting right by 12 bits extracts the upper 20 bits:
- Physical address calculation:
Paging preserves the page offset exactly. Substituting PFN
0x1B02into the upper 20 bits gives:
Exercise 4.1.2: Address Translation under Base-and-Bound Protection Registers
A system implements hardware base-and-bound memory relocation. A process is assigned a base register of 0x00300000 and a bound (limit) register of 0x00028000.
- Compute the translated physical address for a load instruction at virtual address
0x00014A00. - Determine the hardware response for a load instruction at virtual address
0x00028000. - Explain why the boundary check must use strict inequality rather than weak inequality
HintExpandCollapse
The bound defines the total length of the segment, so valid offsets range from 0 to Bound - 1.
Worked solutionExpandCollapse
- Valid load: The virtual offset is strictly less than the bound Hardware translates the address by addition:
- Boundary check: The access at satisfies so The MMU hardware raises a segmentation fault or memory protection exception prior to executing the bus cycle.
- Strict inequality rationale: A segment of length bytes occupies offsets An access at offset falls exactly one byte beyond the authorized allocated range. Using would expose an unallocated or neighboring byte, violating memory isolation.
Exercise 4.1.4: Isolation Invariant Defense in Sparse Address Space Layouts
A 64-bit operating system places a 4 KiB non-mapped guard page immediately below each thread stack and immediately above the process heap.
- Formulate the isolation invariant that explains how unmapped guard pages detect stack overflow and heap overrun.
- Suppose an application bug causes an unchecked pointer increment of 64 KiB in a single step, jumping over the 4 KiB guard page into adjacent valid data. Explain why guard pages cannot prevent this corruption.
HintExpandCollapse
A guard page traps accesses whose stride is strictly smaller than the guard page thickness.
Worked solutionExpandCollapse
- Isolation invariant for guard pages: Let virtual page be unmapped Any instruction accessing immediately triggers an unhandled page fault exception before modifying memory. When stack frames grow sequentially by small increments the stack pointer inevitably references page on overflow, allowing the kernel to terminate the offending thread or expand the stack safely without silent memory corruption.
- Large-stride failure: Guard pages rely on continuous, localized traversal. If an allocation or array access strides by 64 KiB, the calculated target virtual address skips entirely past the 4 KiB range of and lands directly on an active, mapped virtual page belonging to another segment. Because possesses a valid PTE with write permissions, the hardware executes the store without faulting, silently corrupting unrelated data.
Exercise 4.1.5: Contrasting Paging Internal Fragmentation and Contiguous External Fragmentation
Contrast the origin and manifestation of internal fragmentation in fixed-size paging with external fragmentation in variable-size contiguous memory allocation. State why modern operating systems accept internal fragmentation in exchange for eliminating external fragmentation.
HintExpandCollapse
Consider unused space inside allocated units versus unallocatable scattered free space between units.
Worked solutionExpandCollapse
- Internal fragmentation: Occurs when memory is allocated in fixed-size discrete units (e.g., 4 KiB pages). If a process requests 5 KiB of heap space, the operating system must allocate two 4 KiB pages (8 KiB total). The remaining 3 KiB within the second page is allocated to the process but unused, representing internal waste. The average internal fragmentation per mapped segment is half a page
- External fragmentation: Occurs in variable-size contiguous allocation schemes (such as pure segmentation or unpaged physical placement). As processes allocate, deallocate, and terminate at varying lifetimes, free physical memory becomes checkerboarded into small non-contiguous blocks. Total free memory may exceed a request, but no single contiguous chunk is large enough to satisfy it, requiring expensive memory compaction.
- Architectural tradeoff: Paging completely eliminates external fragmentation at the physical level because any free physical frame can satisfy any virtual page request, regardless of physical location. Operating systems accept bounded internal fragmentation (at most a fraction of a page per region) because it avoids compaction overhead and enables non-contiguous, demand-paged allocation.