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.

Memory thrashing is repeated costly cycling of memory pages out of and back into computer memory, leaving little useful computation between page faults. Active demand can exceed the available page frames, especially when multiprogramming admits too many operating-system processes. A high page fault rate during initial loading alone does not establish memory thrashing. ^[ref]

Consider one operating-system process making the 20 memory references $1,2,3,4,1,2,3,4,\dots ,1,2,3,4$: five repetitions of four memory pages. Start with an empty resident set, use demand paging and exact LRU replacement, and assume no prefetching or competing operating-system processes. A hit finds the requested memory page resident; a miss requires a nonresident page fault. With three page frames, references 1–3 load pages 1–3. Reference 4 evicts page 1, reference 5 reloads page 1 and evicts page 2, and the cycle continues: every return finds its memory page evicted. With four page frames, only the first four references miss; all four memory pages then remain resident.

The four initial misses with four page frames are compulsory first-use misses from the empty resident set. They are startup work; the three-page frame case keeps faulting after startup. This makes the difference between memory thrashing and loading a new working set visible. For the three-page frame trace, each reused memory page has three distinct intervening memory pages, so LRU replacement has already evicted it before its next use.

To quantify the cost, assume each hit takes 100 nanoseconds and each miss incurs an additional 1 millisecond of page fault service, followed by the same 100-nanosecond memory access. These are toy latencies, not measurements. With miss probability $p$, the expected value of access time isThe service cost is additional: it does not include the final 100 nanoseconds. Thus $p=1$ gives $1,000,100\mathrm{ns}$ and $p=0.2$ gives $200,100\mathrm{ns}$, approximately a fivefold ratio over the complete trace. Over references 5–20, the corresponding ratio is $1,000,100/100=10,001$: repeated page faults dominate the useful accesses. The expected value model follows the additive miss-penalty convention of OSTEP chapter 22, section 22.1. ^[ref]

Not every page fault performs disk input-output: demand paging can allocate zero-filled memory pages, and copy-on-write can copy an existing page frame. The toy service cost models expensive misses; the miss trace alone establishes residency behavior, while memory thrashing additionally concerns repeated costly cycling. ^[ref]

Possible remedies are more resident page frames, less multiprogramming, or reorganizing accesses to improve temporal locality. For this toy sequence, one extra page frame suffices under LRU replacement; that is not a universal threshold or policy. Page replacement alone cannot make every simultaneously needed memory page fit.

// Target: computer-science.bigb

A lookup that fails to find the required cached address translation. A successful refill can leave the memory page resident throughout and cause no page fault.

For process A's resident virtual page 4 in address translation, discarding only its translation lookaside buffer entry makes the next read a TLB miss while its contents remain in page frame 13. Page replacement would instead remove the resident memory page; these operations invalidate different kinds of cached information.

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]