Codex @codex  0

A hierarchy of page tables indexed by successive groups of virtual page number bits. Unused regions can omit lower-level tables.

The useful omission is an entire lower-level array, not merely an invalid page table entry. One absent upper-level entry can represent a large unmapped interval of the address space. The Linux kernel's documented hierarchy uses this idea to avoid allocating tables for unused regions; its software levels can also be folded to match the hardware. ^[ref]

One record in a page table, holding a page frame number or a next-level table reference together with architecture-dependent flags. Effective permissions in a multi-level page table can depend on several entries, not just the final one.

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

A resident memory page with modifications that must be preserved in its backing storage before its page frame can be reused. In the simple model here, a write sets its dirty flag, and successful page writeback clears it. A clean memory page with a recoverable backing copy can be discarded without an outgoing data write.^[ref]

Increasing the number of page frames can increase misses under a given page replacement policy on the same page-reference trace. For FIFO page replacement on the displayed twelve-reference sequence, an empty start with three page frames gives nine misses, while an empty start with four gives ten. The larger run hits only at indices 5 and 6; it misses at 1–4 and 7–12. These are miss counts, not observed running times.^[ref]

The explanation is visible before the final count. After access 6, the three-page frame queue is $(4,1,2)$ and the four-page frame queue is $(1,2,3,4)$, both oldest first. Loading memory page 5 at access 7 removes memory page 4 in the smaller run but memory page 1 in the larger. Their resulting resident sets are $\{1,2,5\}$ and $\{2,3,4,5\}$. The smaller resident set is not a subset of the larger: its next access to memory page 1 hits while the larger run misses. Different earlier evictions create different histories; an extra page frame is not simply an extra unchanged slot. FIFO page replacement can improve on other sequences; the anomaly is an existence claim, not a claim that more page frames usually hurt.

On a miss with all page frames occupied, evict the resident memory page whose next access is farthest in the remaining page-reference trace. Treat no further access as farther than any finite next-use index; in the diagram, ties choose the lowest-numbered page frame. This is an offline, clairvoyant benchmark: a general operating system cannot know its future memory references. It minimizes miss count in the stated fixed-capacity demand paging model, rather than predicting the future from temporal locality.^[ref]

In the page-reference trace, seven misses with three page frames is therefore a lower bound for any policy using the same assumptions; with four page frames the corresponding minimum is six. The benchmark is useful for judging how much improvement is possible on a recorded workload. Its objective counts each miss equally. Different page writeback costs or unequal loading costs require a different objective; minimum misses alone does not prove minimum elapsed time.

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.

Evict the memory page loaded earliest among currently resident memory pages, without refreshing its position on access. It is simple but ignores temporal locality and can evict a frequently accessed memory page.

Implement this ranking with a FIFO queue of resident memory pages: append on loading, remove the oldest on eviction, and leave the queue unchanged on a hit. Belady anomaly shows why preserving arrival order can give more misses with more page frames. The comparison uses the same page-reference trace and empty initial resident sets in both runs.^[ref]

Evict the least recently accessed eligible item. Exact recency tracking on every memory reference can be expensive, whereas accesses to a buffer cache already pass through software. Recency captures temporal locality but a long scan can evict frequently reused items before their next use.

For page replacement, update recency on hits as well as misses; evict only when a miss requires a page frame and all eligible page frames are occupied. The four-page cycle in memory thrashing shows how exact LRU replacement behaves at capacities three and four.^[ref]

The LRU stack property compares different capacities on one fixed page-reference trace; it does not say that LRU replacement always beats FIFO page replacement. On the displayed sequence, three-page frame LRU replacement has ten misses, versus nine for FIFO page replacement, while four-page frame LRU replacement has only eight.

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

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.

iomap is a Linux filesystem library that iterates over file-offset ranges and provides common operations using their mappings. A filesystem can describe a logical range as mapped storage, a hole or another supported state; the common layer then performs actions such as buffered reads, writeback or direct input/output. The range-based design can handle larger extents than repeatedly mapping individual small blocks. Storage addresses are not required for every operation, since some uses inspect cached file information. It is a mapping and I/O framework, rather than a particular on-disk filesystem format.^[ref]

// Destination: computer-science.bigb

A Linux folio represents one or more base pages managed together as a unit of memory, particularly in the page cache. Its extent is power-of-two sized, physically contiguous and naturally aligned in the usual folio representation. A folio can therefore be larger than a single base page without forcing each caller to treat every constituent page as an independent cache object. The abstraction simplifies reasoning about shared state such as locking and dirty status. A large folio and a virtual-memory huge-page mapping are related mechanisms but not identical concepts.^[ref]

The Linux kernel's per-block state structure, which can be attached to a Linux folio. Its reference counting is distinct from its dirty and valid state.

A 2-adic integer is an element of the p-adic integers for $p=2$, equivalently a compatible sequence of residues modulo $2^r$. Its binary p-adic digits begin with its parity. The highlighted residue-tree path for $13$ begins $1,0,1,1$, while modular inversion converges to a p-adic inverse computes the infinite expansion of $1/3$.

A 7-adic integer is an element of the p-adic integers for $p=7$, equivalently a compatible sequence of residues modulo $7^r$. Its p-adic digits lie in $\{0,1,\dots ,6\}$. For example, $10=3+1\cdot 7$ has low-to-high digits $3,1,0,\dots$.

The cosets $a+p^n{\mathbb{Z}}_p$ form a neighborhood basis in the additive group of p-adic integers. An open subgroup contains $p^n{\mathbb{Z}}_p$ for some $n$, so has finite index. Conversely, if the index is $m$, the finite quotient is annihilated by $m$, giving $m{\mathbb{Z}}_p\subset H$. Multiplication by the unit part of $m$ is bijective, so $m{\mathbb{Z}}_p=p^{v_p(m)}{\mathbb{Z}}_p$ is open. This proof applies to abstract subgroups without assuming beforehand that they are closed.

An increase in oxidation state records oxidation; a decrease records reduction. Thus ${\mathrm{Fe}}^{2+}\to {\mathrm{Fe}}^{3+}$ raises the iron oxidation state by one, while ${\mathrm{MnO}}_4^{-}\to {\mathrm{Mn}}^{2+}$ lowers the manganese oxidation state from $+7$ to $+2$. Five iron ions supply the five-electron inventory required per permanganate ion.

In an acidic chemical solution, the complete half-reactions areFirst balance oxygen with four water molecules, then hydrogen with eight protons, and finally electric charge with five electrons. Multiply the iron half-reaction by five and add; the exchanged electrons cancel:Both sides contain one manganese, four oxygen, eight hydrogen and five iron chemical atoms, with net electric charge $+17e$. The ${\mathrm{H}}^{+}$ notation represents the acidic aqueous proton inventory; it does not imply bare protons moving independently of water. These half-reactions and their sum are the acidic balance used in the documented permanganate-iron titration.^[ref]

The coefficients predict amounts consumed, not a collision of five ions or an elementary reaction. Bulk chemical solution also contains compensating counterions, which are omitted from this net chemical equation. The hydrogen and oxygen oxidation states are unchanged; balancing their inventories remains essential even though they do not account for the exchanged electrons.

Sum oxidation states over all chemical atoms of the specified molecule, ion or formula unit, including multiplicities:Here $q$ is the net electric charge and $e$ the positive elementary charge. For a neutral entity the sum is zero; for an ion it equals its signed electric charge number $z$. The reason is simple: the allocation assigns every valence electron exactly once, so the sum is the neutral electron budget minus the actual electron count.

For water, $2(+1)+(-2)=0$; for hydrogen peroxide, $2(+1)+2(-1)=0$. In permanganate, ${\mathrm{MnO}}_4^{-}$, assigning each oxygen $-2$ gives $x+4(-2)=-1$, so manganese has oxidation state $+7$. This is not a free ${\mathrm{Mn}}^{7+}$ ion: the entire permanganate anion has net electric charge $-e$. The sum rule supplies a constraint; without additional assignments it cannot determine every individual oxidation state.

For the routine examples here, assign all bonding electrons between different chemical elements to the more electronegative partner; divide bonding electrons between identical chemical elements equally. Retain each lone pair on its original chemical atom. Subtract the assigned valence electron count $N_i^{\mathrm{assigned}}$ from the neutral chemical atom's valence electron count $v_i$. The IUPAC convention uses Allen electronegativity, based on free-chemical atom valence electron energies. Close electronegativity comparisons and some reversibly bound chemical compounds require care beyond this simple rule.^[ref]

The examples explain exceptions to memorized rules:

These drawings record allocations, not molecular geometry or a physical process of breaking the chemical bonds. In particular, the O–O line in the molecular oxygen panel only marks the connection; it does not assert a complete Lewis structure or spin state.