Codex @codex  0

Use the two-level address translation model and map exactly four resident virtual memory pages, numbered 0x12, 0x13, 0xa0, and 0xa1. Assign their data page frames to 0x07, 0x02, 0x05, and 0x06, respectively. Only two root indices occur: 1 and 10. Allocate exactly three table nodes: the root at 0x8000, the lower-level table for root index 1 at 0x9000, and the lower-level table for root index 10 at 0xa000. Root entries 1 and 10 reference those tables; all other root entries are absent. Lower-level entries 2 and 3 in the first table and entries 0 and 1 in the second table hold the four mappings; every other lower-level entry is absent. Use the read-only permissions already specified for virtual memory page 0x12; let the other three mappings permit user reads and writes, with no execution, and let both populated root entries permit user reads and writes.

Each root index covers 16 virtual memory pages, hence $16\cdot 256=4096$ bytes of the address space. A compact table node occupies $16\cdot 4=64$ bytes. The three nodes therefore require $3\cdot 64=192$ bytes of table storage, including the root and all absent entry slots in the allocated nodes. A single-level array requires $256\cdot 4=1024$ bytes for the same address space, saving $1024-192=832$ bytes in the compact model. Four data page frames occupy another $4\cdot 256=1024$ bytes; those contents are separate from table storage.

If instead the allocator dedicates a whole 256-byte page frame to every table node, the three nodes consume 768 bytes, leaving $3(256-64)=576$ bytes unused within those allocations. The single-level table fills four such page frames and still consumes 1024 bytes. Thus this example saves 256 bytes of allocated table storage under that alternative policy. Neither accounting includes allocator metadata, operating-system process records, or translation lookaside buffer storage; data allocations are the same in both designs.

Placement matters as well as mapping count. Four virtual memory pages 0x12, 0x42, 0x72, and 0xa2 require the root plus four lower-level tables: five nodes, 320 compact bytes, or 1280 bytes with a dedicated page frame per node. Only four data page frames are still required. Let $g$ be the number of distinct root indices represented by the mappings. With no retained empty lower-level tables, table storage is $64(1+g)$ compact bytes or $256(1+g)$ allocated bytes under the dedicated-page frame policy. Even an empty address space retains the root in this accounting, so $g=0$ costs 64 or 256 bytes.

For a fully populated address space, $g=16$: 17 nodes cost 1088 compact bytes or 4352 allocated bytes. The single-level table remains 1024 bytes. Sparse allocation is therefore a conditional space benefit; scattered mappings, node allocation granularity, and the root's overhead can reverse it. Additional dependent lookups on a TLB miss also have a cost, but node counts alone establish no universal execution-time ordering.

Spatial locality is the tendency to access nearby locations in computer memory within a short interval. A sequential scan of a contiguous array has spatial locality even when each element is read only once. A memory cache can exploit spatial locality by fetching a whole cache line on a cache miss: later reads of neighbouring elements become cache hits. Proximity is in the address layout, so visually adjacent entries in a table need not be adjacent bytes.

Consider a $4\times 4$ array of 32-bit integers, each occupying four eight-bit bytes, stored contiguously in row-major order. Use toy physical addresses starting at zero, aligned to a 16-byte cache line boundary. For row $i$ and column $j$, with $0\le i,j<4$, the address and cache block number areHere $\lfloor \cdot \rfloor$ is the floor function. Each row occupies exactly one cache line: row zero begins at addresses $0,4,8,12$, row one at $16,20,24,28$, and so on. Row-major order describes this storage layout; traversal can follow rows or columns without moving the elements.

Read all sixteen elements and compute their integer sum, keeping the accumulator outside the modelled memory cache. Only the sixteen array reads count as memory references. The toy fully associative cache starts empty, holds exactly one 16-byte cache line, fetches the requested cache block on every cache miss, and uses LRU replacement. No cache block is fetched ahead of a request, and no writeback costs are counted because the modelled accesses are reads.

Every element is read once in both traversals. The row traversal exploits spatial locality between distinct elements and temporal locality of their shared cache block. The column traversal returns to each cache block after three other distinct cache blocks, too late for the one-line memory cache. Increase the fully associative cache to four cache lines and both traversals give four compulsory misses and twelve cache hits: no loaded cache block needs eviction. The difference therefore depends on capacity as well as access order and layout.

This makes spatial locality useful and beautiful: the same logical operation on the same elements can use a fetched cache line much more fully simply by changing traversal order. The toy counts do not predict a universal speed ratio on real hardware. Actual cache line sizes, capacities, placement rules, fetching ahead of requests and overlapping work affect runtime; measure a concrete implementation with statistical program profiling. Ulrich Drepper's November 2007 authored paper explains cache line transfers and gives array and matrix access examples connecting layout, temporal locality and spatial locality. Its hardware measurements are historical examples, rather than specifications for every present-day CPU. ^[ref]

// Destination: computer-science.bigb

The actual Sv39 page table geometry uses three nine-bit indices and a twelve-bit offset for base 4096-byte memory pages. Each table contains 512 eight-byte page table entries, exactly one 4096-byte memory page; the satp processor register identifies the root. A 64-bit virtual address must repeat bit 38 in bits 63 through 39. Higher-level terminal entries can also map aligned larger memory pages, shortening the page table walk. These rules differ from the 16-bit, four-byte-entry two-level address translation model. ^[ref]

For ordinary Sv39 page tables, valid nonterminal page table entries reference the next table with read, write, and execute flags clear; those clear flags do not prohibit reading the eventual data. The terminal entry supplies access permissions, with additional processor privilege level and status checks. An invalid entry, malformed encoding, or denied access can cause a page fault. Thus the model's set intersection of read/write permissions at both levels must not be applied mechanically to Sv39 page tables. ^[ref]

In xv6 RISC-V source code, root allocation is separate from lower-level allocation: uvmcreate() allocates and clears a root page table, while walk() with allocation enabled allocates and clears missing lower-level tables and installs valid references to them. With allocation disabled, a missing table makes walk() return failure. This software routine finds a page table entry for the operating system; it is not the hardware's complete permission-checking page table walk. ^[ref]

A lookup that finds a valid cached address translation for the relevant address space. The access can still cause a page fault if the cached permissions forbid it.

For the 64-byte toy model in address translation, a cached process A page-4 mapping covers reads at both 0x12D and 0x12E, yielding physical addresses 0x36D and 0x36E. The TLB hit reuses the mapping; it does not guarantee that either requested byte is in a data memory cache.

A translation lookaside buffer is a small hardware memory cache of virtual address to physical address mappings and their access attributes. A TLB hit finds a usable cached mapping for the current address space; access permissions still apply. A TLB miss means that mapping is absent from the translation lookaside buffer. It says nothing by itself about whether the memory page is resident. Evicting a translation lookaside buffer entry removes a cached translation, not the memory page's contents. ^[ref]

For the 256-byte example, a cached virtual page 0x12 to physical frame 0x07 mapping covers every offset from 0x00 to 0xff. Reads at virtual addresses 0x1234 and 0x1235 can reuse it to reach physical addresses 0x0734 and 0x0735. If the translation lookaside buffer is initially empty, the first read instead requires a page table walk; with a resident, readable mapping, it completes without a page fault. A write can fault even on a TLB hit because cached permissions deny it.

The diagrams show an ordinary x86 model with hardware page table walks. Some architectures use an operating system handler to refill the translation lookaside buffer after a TLB miss; that refill event alone is not a nonresident page fault. Temporal locality helps a small translation lookaside buffer serve repeated accesses, and one entry can cover many bytes. ^[ref]

A context switch does not universally flush the whole translation lookaside buffer. An address space identifier can distinguish translations with the same virtual page number in different address spaces; Intel's PCIDs support retaining translations across appropriate switches. The operating system must still invalidate stale translations when mappings or permissions change, following the architecture's rules, including coordination with other processors that could use them. ^[ref]

Choose an original teaching model with 16-bit virtual addresses, 16-bit physical addresses, and 256-byte memory pages and page frames. The eight high bits identify a virtual memory page; divide these into two four-bit indices. The eight low bits are the offset within the memory page. Thus each page table has 16 entries: the root selects a lower-level page table, and that table selects a data page frame. Every page table entry is four bytes, including its reference and flags. These are chosen model parameters, not a hardware entry encoding.

For a virtual address $v$, extract the root index $i$, lower-level index $j$, and offset $d$ by Euclidean division:Here $\lfloor \cdot \rfloor$ is the floor function and $\mathrm{mod}$ denotes the remainder in Euclidean division. Each index ranges from 0 to 15, and $d$ ranges from 0 to 255. In hexadecimal, virtual address 0x1234 splits into $i=1$, $j=2$, and $d=0x34=52$; its binary numeral system representation is 0001 | 0010 | 00110100.

Fix the requested operation to be a one-byte user read. Assume both table nodes and the data page frame are resident, table reads are allowed, and no mapping changes during the page table walk. The model requires presence at both levels and takes the set intersection of the two entries' read, write, execute, and user-access permissions. This is an explicit memory protection rule for this model; Sv39 page tables use different rules. The root's physical address is 0x8000; the relevant entries are:

The first lookup obtains a table reference, not the final data physical address. The second lookup obtains page frame number 7. Both entries permit a user read, so the original offset is added to the data page frame base:The page table walk therefore reads records at 0x8004 and 0x9008, then the requested read accesses data at 0x0734. All three are distinct physical addresses. These are two dependent table lookups followed by one data access, not a claim of three accesses to main computer memory: a memory cache can satisfy table lookups, and cached intermediate translations can skip them.

Under the same memory protection rule, a user write at 0x1234 fails because lower-level entry 2 denies writes, even though root entry 1 allows them. Clearing either entry's presence flag also prevents the access. An absent root entry stops the page table walk before any lower-level lookup. A page fault then requires the operating system to determine whether a permitted mapping needs storage or the access is invalid; absence alone does not establish demand paging eligibility.

With an empty translation lookaside buffer, the permitted read causes a TLB miss and this successful page table walk, with no page fault. If the resulting mapping and permissions are cached for the current address space, a later read at 0x1235 can use a TLB hit to reach 0x0735. A later write can cause a protection page fault on a TLB hit because the cached mapping remains read-only. Assume cached permissions are current; changing them requires the architecture's prescribed invalidation. A TLB miss describes a missing cached translation, while a page fault describes an access that cannot proceed under the translation or protection rules. ^[ref]

For an ordinary file under the POSIX rules used here, successful unlink("a") removes the named directory entry and decreases the hard link count. An existing open file description still refers to the same file; removing a name does not detach an already open file descriptor. When the final hard link disappears, the contents remain available through open references until those references close. This distinction is between the lifetime of a name and the lifetime of the underlying file. ^[ref]

Start with names a and b for inode 42 and one file descriptor 3 referring to one open file description. Let $L$ count hard links and $O$ count live open file descriptions for this file. Assume successful operations, no additional references, and no memory-mapped file. The stages areAfter the first removal, b still works. After the second, neither name works, but a read through the existing file descriptor can still obtain all six bytes if its open file description's current position is at the beginning. The final close releases the last open reference, allowing the inode and its file data blocks to be reclaimed. Freed storage is reusable; this does not promise that old bytes are securely erased. ^[ref]

The reasoning is bookkeeping rather than a long proof: each successful removal subtracts one from $L$ and leaves $O$ unchanged; closing the only file descriptor in this example releases the sole open file description. Storage is reclaimable only at the last stage. $O$ is a teaching count, not a count of file descriptors or an asserted internal inode field: several file descriptors can share one open file description, and other references such as a memory-mapped file require additional lifetime accounting. The diagrams are abstract models, not operations on actual user files.