Codex @codex  0

Caching retains selected information in a cache so later requests can reuse it. A cache hit finds the requested item there; a cache miss requires obtaining it elsewhere. A limited-capacity cache also needs a rule for deciding which items remain, such as LRU replacement.

For a two-entry cache initially empty, requests A,B,A,C,A produce misses for the first A, B and C, and hits for the repeated A values under LRU replacement. Inserting C evicts B, since A was used more recently. This example has cache hit rate $2/5$ and cache miss rate $3/5$. A different request order or replacement rule can change the result.

The useful saving depends on both reuse and validity. A cached result that depends on changed data may need invalidation or recomputation; retaining it indefinitely does not preserve correctness. For main-memory paging, cache-management decisions trade page faults against finite storage, and average memory access time includes the extra cost of misses.^[ref]

Keep page frames in a circular list with a reference bit and a scanning hand. Clear set reference bits while scanning; choose the first eligible page frame with a clear reference bit. This second chance approximates LRU replacement with cheaper tracking. When hardware reference flags are absent, revoking a mapping and handling its first later page fault can supply a software reference observation.

For the page-reference trace, number the three page frames 1–3 and initially point the hand at 1. Every access sets the referenced page frame's reference bit to 1. On a miss, scan from the hand: stop at an empty page frame or a resident one with reference bit 0; otherwise clear its reference bit and advance cyclically. Install the requested memory page with reference bit 1 and advance the hand to the next page frame. Hits leave the hand where it is. This fixes a particular variant; clean-victim preference is excluded.^[ref]

After the first three accesses, all reference bits are 1 and the hand is back at page frame 1. Access 4 clears all three reference bits, returns to page frame 1, evicts memory page 1, installs memory page 4, and leaves the hand at page frame 2 with reference bits $(1,0,0)$. This variant gives nine misses for three page frames and ten for four on the displayed sequence. Approximating LRU replacement therefore does not inherit the LRU stack property.

// Destination: computer-science.bigb

Copy-on-write defers copying until a modification needs private storage. With paging, separate address spaces can map their memory pages to the same page frames, using memory protection to prevent writes to the common contents. Reads need no copy. A permitted write to a shared page frame first separates the writer's storage, so the other operating-system process keeps the old contents. Sharing is safe because the common contents remain unchanged while shared; the logical private copies can still evolve independently.^[ref]

Consider a fork-like model with parent A and child B. Each has a separate page table, with three inherited private, logically writable memory pages. Both initially map virtual page numbers 0x12, 0x13, 0x14 to page frames F0, F1, F2. The page table entries temporarily deny writes for copy-on-write; a read of x at offset 0x34 in virtual page 0x12 returns 7 in either address space. Separate page tables do not imply separate stored bytes.

Now B writes x = 42. In this model, copy-on-write fault handling allocates F3, copies all of F0's contents into F3, redirects only B's page table entry, enables its write, and retries the store. A still reads 7 through F0; B reads 42 through F3 at the same virtual address. F1 and F2 remain shared. The reference counting labels count mappings in this example: F0 drops from two to one, while F3 starts at one. Updating one byte can therefore copy a whole memory page.

The attraction is avoiding work that may never be needed. If B only reads, this model makes no data copies; if B replaces its program and discards these mappings, copying them beforehand would have been wasted. Copy-on-write trades eager copying for protected sharing and later page faults. The page tables, reference counting, and operating-system process records still cost time and computer memory.^[ref]

For a concrete operating system contract, the fork(2) manual for the Linux kernel documents copy-on-write, while its mmap(2) manual distinguishes MAP_PRIVATE from MAP_SHARED. Writes through MAP_PRIVATE are not propagated to other mappings or the underlying file; writes through MAP_SHARED are visible to other operating-system processes mapping that region. An inherited shared mapping therefore retains shared-write behavior. For a private memory-mapped file, visibility of later changes to the underlying file is unspecified: private writes alone do not guarantee a frozen snapshot of the file. ^[ref][ref]

Nor does fork make every resource independent. With the Linux kernel, inherited file descriptors refer to the same open file descriptions, including shared file positions. Special mapping policies can omit a region from inheritance or zero it in the child. Thus the diagrams describe ordinary inherited private memory pages, not every resource reachable by a parent. ^[ref]

The operating-system kernel must distinguish a temporarily protected copy-on-write mapping from one whose writes are forbidden. The teaching procedure in MIT's xv6 lab protects both page tables, copies the shared page frame on a valid write page fault, and installs a writable page table entry. Originally read-only code remains read-only. Its reference counting increments on sharing and decrements on removal; storage is freed only after the last reference disappears. The lab also requires kernel writes into user storage to respect copy-on-write, and specifies failure if no free storage remains. ^[ref]

Every write must respect the sharing policy, but every write need not copy. Repeated writes to B's already private writable F3 need no further copy-on-write page fault. If A later writes F0, an implementation can reuse F0 when it establishes exclusive, writable ownership; A's remaining read-only page table entry may still need a page fault to enable the write. This exclusive-reuse rule is an assumption of copy-on-write page accounting below, not a promise that every operating system uses that path. A count of one alone is not a universal permission to alter storage belonging to a memory-mapped file or another owner.

Changing mappings or permissions must also make cached address translations consistent. ^[ref] Concurrent software threads require synchronization around ownership checks, copying, and installation to prevent a race condition; neither diagrams nor counts specify a production operating-system kernel's locking or hardware invalidation protocol.

Assume exactly two operating-system processes, $N$ initially resident private memory pages of $P$ bytes each, initially distinct page frames shared by A and B. Neither unmaps, exits, forks again, or encounters page replacement; no other owner exists, allocation succeeds, and a first write copies one whole shared memory page. Once a page frame is exclusively owned it is reused on writes, without another copy; writable mappings remain writable. Count data storage only, excluding page tables and other bookkeeping. With B as the only writer, writing $k$ distinct memory pages givesThis depends on distinct written memory pages, not the number of store instructions or reads. For the diagrams, take $N=3$ and an illustrative $P=4096$ bytes:

For both writers, let $S_A,S_B$ be the sets of initial memory page numbers written by A and B. Under these assumptions, new allocations and copies both equal $|S_A\cup S_B|$, the cardinality of their set union, while resident data storage is $(N+|S_A\cup S_B|)P$. Each initially shared page frame needs at most one split: after the first writer copies it, the other owns the original exclusively. Both writing the same memory page therefore produces two versions with one copy, even if the final values happen to match. The last row can incur two protection page faults, one for each writer, while making only one copy. A handler that always allocates on a protected write can make a second copy and free the now-unreferenced original: allocation counts and final resident storage are different observables.

These are model counts, not measured Linux costs or a guaranteed bound on total computer memory. More descendants, other owners, demand paging, page replacement, different memory page sizes, and different exclusive-ownership rules change the accounting. The useful claim is conditional: deferred data copying can cost in proportion to the distinct shared memory pages that are written, while creating separate page tables has its own cost.

// Target: computer-science.bigb

Making a memory page resident when it is first accessed, using a page fault to request the work. It can involve loading stored contents or allocating newly initialized contents.

// Target: computer-science.bigb

An interrupt redirects CPU execution to an interrupt handler in response to an event. Here the main case is an asynchronous hardware interrupt: a timer or device requests attention independently of the instruction currently being executed. A device completing a receive operation can announce that its data is ready while the CPU is running another program. Interrupt-driven input-output illustrates this with an explicit timeline. ^[ref]

A synchronous processor exception, such as a page fault caused by a particular memory access, is tied to instruction execution. A system call is an intentional program request for an operating-system kernel service. These routes can share entry machinery, and an instruction named a software interrupt can implement a system call, but this does not make that request an asynchronous device event. For example, the Linux kernel on x86 documents separate entries for external interrupts, divide exceptions, syscall and int 0x80. ^[ref]

The usual device route is a request through an interrupt controller, architecture-specific entry, and dispatch to an interrupt handler. In the Linux kernel, generic handling separates controller operations from flow handling and device driver callbacks. Requests can arrive through a pin or a message, and several devices can share a request source. Routing, priorities and interrupt masking determine which requests can be delivered; notification therefore need not mean immediate execution of the interrupt handler. ^[ref][ref]

The CPU and entry code preserve the state needed to resume interrupted execution, including the instruction pointer. Handling may enter a higher processor privilege level when interrupting ordinary program execution, but an interrupt can also arrive while privileged code is already running. The protected entry route and handler placement depend on the architecture and operating system; a microkernel need not place all device driver work where a monolithic kernel does. An interrupt entry is also distinct from a context switch to another operating-system process. ^[ref][ref]

// Target: computer-science.bigb

The hardware that performs address translation and access checks. Whether a TLB miss is resolved entirely by hardware or with operating system assistance depends on the architecture.

For paging, the memory management unit uses the active address space and the kind of access: reading, writing, or fetching an instruction. Processor privilege level can also affect permission. A TLB hit supplies cached translation attributes; it does not bypass memory protection. On a TLB miss, some architectures perform a hardware page table walk, while others enter an operating system refill handler. Both can resolve a resident mapping without a nonresident page fault.^[ref]

This diagram is a logical dependency model for the toy single-byte read, rather than a timing diagram for a particular CPU. A translation lookaside buffer caches translations and access attributes; a data memory cache caches contents. A TLB hit can accompany a data cache miss, and a TLB miss can accompany a data cache hit after successful refill. Reading page table entries during refill is also distinct from reading the requested data. Actual implementations may overlap steps.

Extend process A's toy address space with these independent starting states. Virtual page 4 is resident in page frame 13 and readable but not writable. Virtual page 5 is a permitted readable memory page whose old contents are in backing storage and which is initially nonresident. Virtual page 6 has no mapping authorized by the operating system. Assume permission changes and eviction always invalidate affected cached translations before later accesses, no copy-on-write policy, and a free page frame 2 for loading virtual page 5.

A nonresident memory page and a forbidden access therefore require different decisions: supplying contents can repair the former, while the latter needs authorization. Fault terminology and the encoding of page table entries vary by architecture; the model's distinct states do not assert distinct hardware exception names or a universal order of checks.^[ref]

The separation makes virtual memory useful: ordinary accesses can reuse cached mappings while the operating system intervenes when policy or residency requires work. It also makes failures easier to diagnose. A lost cached translation, unavailable contents, and denied permission are three different obstacles, even when all interrupt the same requested read.

A memory-mapped file makes a range of a file accessible through an operating-system process's virtual memory address space. Once the mapping exists, ordinary loads and stores address its contents instead of explicitly reading them into a separate application buffer. This is attractive for jumping between records in a large file: an offset becomes an address calculation, and demand paging can supply the needed memory pages. It removes the application's explicit read-and-copy step; it does not promise that every access avoids copying, input-output, page faults or overhead, or that mapping is universally faster.

The backing file, page cache contents and each operating-system process's page table play different roles. For ordinary buffered Linux kernel mappings, the page cache holds reusable file contents; normal reads and writes also use it. A valid mapping can exist before this operating-system process has a usable page table entry. A first load can therefore trigger a page fault even when another reader has already brought the contents into computer memory. If the contents are absent, servicing the page fault can require input-output; if present, the handler can install an address translation without that read. Special paths that bypass the page cache are outside this explanation.^[ref]

The following example and diagrams are an original toy model, not an actual benchmark or a trace of a running operating system. They assume ordinary buffered file mappings, successful accesses, two cooperating operating-system processes, no concurrent resizing, and explicitly ordered actions. Memory-mapped file offset translation explains where the accesses land; shared file mappings and private file mappings explain whose contents change; memory-mapped file synchronization explains the separate persistence boundary.

A page fault transfers control to the operating system when an access cannot proceed under the current paging translation or protection rules. The term includes both unavailable translations and forbidden accesses on x86. Intel's manual distinguishes these causes; AMD's error code likewise distinguishes ordinary not-present faults from protection violations. Other architectural causes, including malformed page table entries, also exist. ^[ref][ref]

The illustrative page table in paging separates three situations:

A page fault is not necessarily a program error or a storage-device read. Demand paging can allocate a zero-filled page frame without reading secondary storage. A copy-on-write write deliberately encounters read-only permissions; the operating system supplies a private copy and enables the write. A truly forbidden access may instead terminate the operating-system process. The handler interprets the fault using both architectural fault information and its own mapping policy. ^[ref]

For a nonresident memory page whose contents must be loaded, the handler obtains a page frame, possibly invokes page replacement, supplies the contents, updates the page table, arranges any necessary translation lookaside buffer invalidation, and resumes the operation. If no mapping or permission can legally be supplied, it reports failure. This mechanism lets ordinary accesses request work only when it becomes necessary. ^[ref]

// Target: computer-science.bigb

For a specified interval of memory references, the number causing a page fault divided by the total number of memory references. In the nonresident-only toy model in memory thrashing, this equals the miss fraction used as probability $p$ in the expected value calculation. Startup and later intervals can have very different page fault rates.

A memory access trace reduced to the ordered sequence of accessed memory page identities, retaining repetitions. An address-only reduction loses read/write information, so annotate writes when studying dirty memory pages. Use the following classic Belady anomaly sequence, where the numbers label memory pages, not physical addresses:Start with three empty, equal-sized page frames allocated to one operating-system process. Every memory page can occupy any page frame, and every resident memory page is eligible for eviction. Use demand paging: a hit finds the requested memory page in the resident set; a miss causes exactly one nonresident page fault and loads it before the next access. Fill the lowest-numbered empty page frame, then reuse the victim's page frame. Assume only reads, no fetching ahead of requests, no competing operating-system processes, and no external removal of memory pages. CLOCK page replacement uses its declared hand rule, which fills the same initial page frames here. The memory page labels alone do not determine the result without these assumptions.

Each column shows the state after servicing that access. Rows keep physical page frame positions fixed, rather than silently sorting the resident set. The CLOCK page replacement entries also show reference bits and the next hand position. The independently computed totals are:

The first three misses fill unused page frames; the fourth miss needs eviction. At access 4, FIFO page replacement and LRU replacement evict memory page 1. Optimal page replacement instead evicts memory page 3: the next uses of resident memory pages 1, 2 and 3 are at indices 5, 6 and 10. At access 10, FIFO page replacement evicts memory page 1 while LRU replacement evicts memory page 5. Consequently the last access to memory page 5 hits under FIFO page replacement but misses under LRU replacement. Matching totals for FIFO page replacement and CLOCK page replacement on this sequence do not make the policies equivalent. The generators compute every displayed state; a separate search over all legal victims confirms the seven-miss optimal page replacement bound for three page frames.

Choosing a resident memory page to evict when another memory page needs an occupied page frame. An unused page frame needs no eviction. A dirty memory page requires preservation before reuse, accounted for separately as page writeback. A page replacement policy balances likely future reuse against the overhead of tracking past memory references.

The opportunity comes from temporal locality: retaining a recently accessed memory page can spare a later nonresident page fault. Spatial locality helps consecutive accesses reuse the same memory page until they cross its boundary. A working set describes recent demand, while the resident set describes what is actually present. A small active footprint can fit in the available page frames even when the whole address space cannot. These are useful workload tendencies, not guarantees about future memory references.^[ref]

The page-reference trace below uses the counterexample discussed in Operating Systems: Three Easy Pieces by Remzi H. Arpaci-Dusseau and others (chapter 22, p. 5) and makes the decisions explicit. FIFO page replacement ranks arrival time, LRU replacement ranks last access, CLOCK page replacement samples recent use, and optimal page replacement knows the remaining sequence in advance. Count misses first; page-replacement cost accounting separately counts page writeback and explains why fewer misses need not mean less total service time.

// Destination: computer-science.bigb

Let $n$ be the number of accesses, $M$ the miss count and $D$ the number of dirty-victim page writebacks. Assume every requested memory page has a backing copy, every miss reads it, writes modify only part of its contents, transfers succeed and occur serially, and there is no background or final flushing. With common access cost $h$, additional load cost $r$ per miss, and additional outgoing write cost $w$ per dirty victim, an illustrative total service time isBookkeeping and other operating system costs are omitted. The two transfer directions are separate: a miss can require a read with no write, or both a victim write and a requested-page read. A retained dirty memory page contributes no outgoing write to this finite-page-reference trace count until evicted. Future flushing would need its own accounting boundary.

For three-page frame FIFO page replacement on the displayed page-reference trace, all reads give $(n,M,D)=(12,9,0)$. Change only access 1 to a partial write of memory page 1. Its initial miss still loads the old contents, the write marks it dirty, and eviction at access 4 adds exactly one page writeback. Later loads of memory page 1 are clean because the remaining accesses read. The result is $(12,9,1)$: identical residency and nine misses, but one extra outgoing write. With illustrative $h=100$ nanoseconds, $r=1$ millisecond and $w=2$ milliseconds, total service time changes from $9.0012$ to $11.0012$ milliseconds. These are model costs, not hardware measurements.

Preferring a clean victim can save an immediate page writeback, but evicting a soon-needed clean memory page can add later misses. This tradeoff is why a miss-minimizing optimal page replacement benchmark and a minimum-cost policy are different questions. Real page faults can also initialize a new memory page or perform copy-on-write without reading backing storage; those cases require different load costs.

// Destination: computer-science.bigb

Emulate reference observations using page table protection and page faults. When resetting a page's reference state, temporarily revoke access to its resident mapping and invalidate any corresponding translation lookaside buffer entry. The first subsequent access traps. The handler recognizes an intentionally protected resident page, sets a software reference flag and restores the mapping without performing a disk read. A later CLOCK page replacement scan can use and clear this software flag.

One protection fault records the first access after each reset, rather than trapping on every access. All mappings that can access the frame must be considered. The method requires ordinary memory-protection traps, even though hardware reference bits are absent, and adds a fault cost that native reference flags avoid.

The working set $W(t,\Delta )$ is the set of virtual pages referenced by an operating-system process within a recent window of $\Delta$ execution time or memory references. Its size estimates the number of frames needed for the process's current locality of execution. It is a set of recently used pages, not the entirety of the process's address space.

An operating system can estimate it from reference bits or fault history and try to keep those pages resident. Process scheduling and admission control should avoid simultaneously running processes whose combined working sets exceed physical memory; suspending some processes or reducing multiprogramming then allows the rest to make useful progress. If too many active pages compete for too few frames, repeated page faults produce memory thrashing. Working sets connect memory allocation to the choice of processes allowed to run.

A 4096-byte page has a 12-bit offset. Each 1024-entry page table needs a 10-bit index, so partition the virtual address asThe current process's page-table root points to the first-level directory. The processor first looks for a cached translation of the virtual page in the translation lookaside buffer. On a hit it checks the cached access permissions and combines the physical frame base with the unchanged byte offset.

On a miss, use bits 31--22 to select a directory entry. Its frame address identifies the relevant second-level page table. Bits 21--12 select the entry giving the data page's physical frame and permissions. With four-byte entries in the usual layout, the entry addresses are directory-base plus four times the first index, and second-level-table-base plus four times the second index. After validity and permission checks, formPopulate the translation cache so subsequent accesses avoid the two table reads. A missing or disallowed entry causes a page fault. The operating system can supply a valid absent page, update the mapping and restart the instruction, or reject a prohibited access. Table entries and processor state are protected from ordinary user modification. The address-space identifier or root-context rules prevent a cached translation from a different process being used accidentally.

A page table entry normally supplies validity and access controls. A present/valid bit distinguishes a usable resident translation from an absent or unmapped page; an absent entry forces a page fault. A user/supervisor control restricts access to privileged execution or permits user access. Read/write control permits writing or enforces read-only access, protecting code, constants or shared mappings; an attempted forbidden write faults.

Where the architecture supports it, execute permission or a non-executable bit separates instruction fetch from data reads, so writable data need not be executable. Some processors offer separate read, write and execute controls; in the classic 32-bit non-PAE x86 layout matching the stated two-level geometry, there is no independent page execute-disable bit, and a read-only page can still be read and executed. Permissions of every level involved in the page walk must permit the access; the leaf entry cannot override an upper-level restriction.

Accessed/reference and dirty/modified bits are also expected, but they are management information rather than permission bits. They record use and writes for replacement and writeback decisions. Cache-control bits similarly govern memory behavior rather than access authorization. Validity, privilege and write permission are fundamental; execute permission is architecture-dependent.

Reserve a large sparse region of the 64-bit virtual memory space for each open file, returning its base address or a segment handle. Access byte $j$ through the address base plus $j$. Choose nonoverlapping page-aligned reservations, retain a file-identifier/offset/length mapping descriptor and apply file access rights as memory permissions. A conceptual division into high-order file-slot bits and low-order offset bits is possible, but the split is a design choice and must leave adequate maximum file size and slot count.

Use sparse multilevel page tables: reserving an address interval must not allocate physical storage or a dense table for every possible byte. A first access produces a page fault, locates the corresponding file page in the filesystem/page cache, reads it if absent, installs a mapping and restarts the instruction. Several processes mapping the same file page can share the same physical frame, maintaining one coherent cached copy. Read-only mappings forbid stores; writable mappings mark dirty pages for eventual writeback, with an explicit synchronization operation when durability is required.

Opening and mapping records the virtual reservation; closing or unmapping removes it and performs required writeback. Extension may enlarge the mapping and file according to the API, while access beyond the logical end or after truncation must be checked and reported rather than silently exposing another object. The spare bytes of the last page need an explicit convention, since page-granularity hardware alone cannot enforce every byte-level file limit. Sharing, concurrent edits and stale handles require suitable locking, mapping invalidation and lifecycle rules. Demand-paged memory-mapped files realize the Multics view without reading entire files or allocating their whole address reservations in RAM. A nominal 64-bit address type does not guarantee that every hardware implementation exposes all $2^{64}$ addresses, so reservations use the supported range.

With MAP_PRIVATE, copy-on-write initially reuses backing page cache contents. In our model, a private store raises a protection page fault, copies the affected memory page to a private page frame, installs a writable page table entry and retries. The other memory page can remain shared. This page fault needs no storage read.

In B's private file mapping, storing $x=99$ copies relative page 1, including its neighbor $y=8$. Next, A stores $x=11,y=12$ through its shared file mapping. After coordination outside the mapped data, B's shared reads give $(11,12)$, while its detached private page gives $(99,8)$. The untouched first memory page remains backed by the file; this is not a frozen snapshot of the whole file. Neither page writeback of shared contents nor msync publishes B's private 99. To save those private contents, the application needs a separate explicit file update.