Codex @codex  0

A store of selected information kept for faster reuse. A translation lookaside buffer is a memory cache of address translations; a buffer cache instead holds device-block contents.

For a data memory cache, the useful bargain is to keep a small selection of computer memory close to the CPU. A cache hit serves a read from that selection; a cache miss requires obtaining the contents elsewhere. Temporal locality helps a retained cache block serve repeated reads, and spatial locality helps one transferred cache line serve neighbouring bytes. Placement, capacity and LRU replacement determine whether that opportunity survives until the next read. ^[ref]

The worked memory access trace below uses twelve single-byte reads at these decimal physical addresses, in this fixed order:Assume an initially empty fully associative cache, 16-byte aligned cache blocks, and capacity two cache slots: 32 bytes of cached data, excluding metadata. Use exact LRU replacement, refreshing recency on every read, including cache hits. Every cache miss fetches its requested cache line completely before the next read; only a full memory cache needs an eviction. There are no writes, fetching ahead of requests, external invalidations, or overlapping reads. All addresses denote ordinary cacheable computer memory, and address translation is outside this model. These are deliberately synthetic assumptions, not specifications of a particular CPU.

This makes the outcome reproducible from the memory access trace, rather than from an informal impression that data are “nearby” or “recent”. The cache line geometry below identifies the requested unit; fully associative cache enumerates the resulting states; average memory access time translates the counts into a simple timing calculation.

A request whose required data are already available in the consulted memory cache. In the read-only model of spatial locality, a requested cache block being resident is sufficient for a cache hit.

The memory access trace under memory cache has cache hits at reads 2, 4, 9, 10 and 12. Read 2, at address 4, benefits from the cache line fetched by read 1 at address 0; read 9, at address 52, benefits from read 8 at address 48. These reads use different bytes of the same cache blocks, illustrating spatial locality. Read 4 returns to address 0 while its cache block remains resident, illustrating temporal locality.

A cache hit still takes time to identify the matching cache tag and obtain the requested byte. It is relative to the particular memory cache consulted: a cache miss in one level may be a cache hit in another. The model here has one consulted level and treats a valid matching resident copy as sufficient; it makes no prediction about writes or accesses whose permissions or contents change.

A fixed-sized, aligned block of consecutive bytes transferred and tracked as a unit by a data memory cache. Here cache line and cache block name that unit of data, including its identity in backing computer memory; a resident slot holds a copy. Reading one element can bring neighbouring elements into the same cache line, exploiting spatial locality.

For a nonnegative integer physical address $a$ and a cache line size $B$ bytes, Euclidean division gives the backing cache block number $q$ and offset $d$:Here the brackets denote the floor function and $\mathrm{mod}$ gives the remainder. Cache line $q$ contains bytes at physical addresses $Bq$ through $Bq+B-1$. With $B=16$, read address 52 selects cache block 3, spanning addresses 48–63, and offset 4. Addresses 48 and 52 therefore request the same cache line; addresses 15 and 16 request different cache lines despite being adjacent.

For a cache line size $B=2^b$, the low $b$ bits give the offset. In a fully associative cache, all remaining bits identify the backing cache block as its cache tag; there are no address bits selecting a particular cache slot. An eight-bit illustration gives $52={00110100}_2$: four bits 0011 for cache block 3 and four bits 0100 for offset 4 in the binary numeral system. The eight-bit width is illustrative; the trace does not assume an actual eight-bit machine. ^[ref]

Distinguish this identity from a cache slot, which can hold different cache blocks over time. After read nine in the memory cache example, cache slot 0 contains cache line 3 and cache slot 1 contains cache line 0. Their cache tags identify 3 and 0; neither cache line number is its slot number. Some texts use “cache line” for the storage entry itself; this article reserves cache slot for that role.

A request whose required data are unavailable in the consulted memory cache. The model in spatial locality fetches the requested cache block and evicts a resident cache line only when capacity is full.

In the fixed memory access trace under memory cache, reads 1, 3, 5 and 8 first request cache blocks 0, 2, 1 and 3: four compulsory misses, also called cold misses. Reads 6, 7 and 11 revisit cache blocks that LRU replacement has evicted: three capacity misses. Read 5 is a compulsory miss even though it also causes an eviction; a full memory cache alone does not determine the classification. The fully associative cache permits every cache block in every cache slot, so this example has no conflict misses.

For a precise comparison, run the same memory access trace through an initially empty direct-mapped cache with the same 16-byte cache lines and two cache slots, placing cache block $q$ only in slot $q\mathrm{mod}2$. Read 3 brings in cache block 2 and displaces cache block 0, leaving the other cache slot unused. Read 4 consequently misses at address 0, whereas the fully associative cache still has cache block 0. That read is a conflict miss: increasing placement freedom at the same capacity removes it. The complete direct-mapped cache trace has eight cache misses: four compulsory misses, three capacity misses and one conflict miss.

The convention here classifies each cache miss by first asking whether its cache block has ever been requested. If so, compare with an initially empty fully associative cache of the same capacity and cache line size using LRU replacement on the same memory access trace: a miss there is a capacity miss, while a hit there identifies a conflict miss in the restricted design. This makes the comparison policy explicit; “capacity” is not a claim that no other replacement choice could save that individual read. The three categories describe this read-only demand model; external invalidations or fetching ahead of requests require additional reasoning. ^[ref]

Loss of useful cached data because less useful data occupy the limited memory cache. Excessive cache prefetching can increase later demand cache misses by evicting useful cache lines.

Fetching a cache line before a demand access requires it, to overlap transfer latency with useful work. A software prefetch is one way to request this; unnecessary requests can cause cache pollution.

A resident storage entry that can hold one cache block and metadata identifying its contents. Cache line identity belongs to backing computer memory; cache slot identity belongs to the consulted memory cache.

A repeated cache block access that misses even in the comparison fully associative cache of the same capacity and cache line size using LRU replacement. In the memory cache example these are reads 6, 7 and 11. The replacement assumption matters to this classification.

A repeated cache block access that misses in a restricted design but hits in the comparison fully associative cache of the same capacity and cache line size using LRU replacement. Read 4 of the direct-mapped cache comparison under cache miss isolates this effect while another cache slot is unused.

Independent data in the same cache line cause unnecessary ownership transfers or invalidations when different CPU cores access them. A frequently written lock beside stable reader data can invalidate those data despite no logical conflict.

A memory cache allowing any cache block to occupy any resident slot. When full, its replacement policy chooses a victim from all resident cache lines. The examples in temporal locality and spatial locality use LRU replacement, so no additional placement restriction causes eviction.

The diagram enumerates every read of the fixed memory access trace under memory cache. Keep cache slots fixed: fill the lowest-numbered unused slot first, and subsequently reuse the victim's slot. Separately list recency from least recently used to most recently used. A cache hit refreshes that recency without moving the resident data to another cache slot.

After read 3, cache block 0 is older than cache block 2. Read 4 hits cache block 0, making cache block 2 older; read 5 must therefore evict cache block 2 to load cache block 1. Omitting recency updates on cache hits would choose the wrong victim. Read 6 immediately needs the evicted cache block 2, showing that LRU replacement uses past demand rather than knowledge of future demand.

With capacity four cache slots and the same cache line size, the same memory access trace has just its four compulsory misses and eight cache hits, since all four distinct cache blocks fit. Greater capacity helps this trace, but full associativity alone does not make LRU replacement optimal. Its attraction is freedom from placement restrictions; a hardware implementation must still identify a matching cache tag among eligible entries, and exact recency tracking adds work. ^[ref]

An ordered sequence of memory references, recording repetitions as well as addresses. The example under memory cache records twelve reads in decimal physical addresses; the trace itself does not determine cache hits until cache line size, capacity, initial contents, placement and replacement are specified.

For the microkernel file-read example, distinguish system call entry/exit, security capability lookup, payload transfer, process scheduling and context switches from the service's actual file lookup and read work. Entering a privileged processor privilege level and switching to a different address space are different events. A change of address space can affect the translation lookaside buffer; running different code and touching different computer memory can cause cache misses. Neither event implies that every translation lookaside buffer entry or cache line must be discarded.

A larger copied payload requires more transfer work; sharing memory pages can avoid copying that bulk data but introduces mapping and synchronization work. A service that requests another service adds another IPC exchange. If the cached file data were absent, communication with a device driver and the input-output wait would also matter. Blocking behind other requests affects observed response time even when the individual IPC operations are cheap.

These are cost sources, not timings or a universal ranking against a monolithic kernel. Implementation and CPU details matter: the construction analysis separates protected entry costs, address space switching, translation lookaside buffer effects and memory cache effects. ^[ref]

A memory cache policy that sends a write miss onward without allocating the missed cache line in that level. Different levels of a cache hierarchy may use different write policies.

In IF, fetch PREFETCH normally. In ID, recognize its opcode, read the base processor register and immediate offset, and set controls selecting a prefetch request rather than a load instruction or store instruction. Ordinary register forwarding and data hazard interlocks still apply to that base processor register. In EX, use the arithmetic logic unit to form the effective memory address.

Latch that memory address and a prefetch-valid control into EX/MEM. In MEM, put the memory address and any hint information on the dedicated request computer bus, or enqueue them in a small prefetch-request queue. The cache prefetching engine handles lookup, allocation and the later cache line return independently. Do not wait for the fill or select the returned data as a register file input. In WB, disable architectural processor register and processor condition flag writes; the instruction simply leaves the in-order pipeline.

If the request path is busy, dropping the hint is compatible with the contract in part (ii), and preserves its nonblocking purpose. A design that instead stalls until queue space exists can still be correct but reduces the performance benefit. A memory management unit must not turn a speculative hint into an ordinary protection fault: discard an invalid target, or use an appropriately checked nonfaulting translation path. Suppress device transactions for memory-mapped input-output and avoid speculative writes. Use the existing address-generation datapath, add a prefetch request/control path, and disable demand-load waiting and writeback.

Define PREFETCH [a] as a software prefetch hint: initiate a request for the cache line containing memory address a, then continue without waiting for that cache line to arrive. It produces no value in a destination processor register, changes no program data and creates no data-result dependence for later instructions. It may be ignored if resources are unavailable. A useful hint is nonfaulting for an inaccessible or untranslated target: a later real load instruction must still perform its ordinary access checks. This is a proposed contract for the instruction, rather than a guarantee that the patent abstract alone fixes every detail of its semantics.

For example, after reading the next pointer of a linked list node, prefetch that next linked list node while processing the current one. Replacing the hint by an otherwise unused ordinary load instruction on this in-order pipeline would wait in MEM on a cache miss before the current computation could start. It would also consume a destination processor register and might raise a synchronous processor exception. A harmless hint can be scheduled earlier, even on a path where the data will never be demanded. The crucial semantic difference is that cache filling may continue after the prefetch instruction itself has finished.

A software prefetch is not a memory barrier and does not establish acquire-release synchronization or promise that later accesses will hit. Its purpose is performance; correctness must survive the hint being ignored.

Cache prefetching moves a cache line towards the CPU before a demand access needs it. A correctly timed request overlaps the cache miss penalty with earlier computation, so a subsequent load instruction can find a cache hit instead of stopping the in-order pipeline in MEM. Requests directed at several levels of a cache hierarchy can prepare nearby data in a small fast memory cache while staging more distant future data in larger levels. The separate request computer bus avoids making those address requests compete directly with returning data; returned cache lines still consume transfer capacity.

For a store instruction, the gain depends on the write policy. With a write-allocate cache, fetching its target cache line early can avoid the allocation cache miss and help the store buffer drain. On a multicore processor, a write-oriented prefetch may additionally obtain cache coherence ownership; an ordinary read prefetch alone does not guarantee write permission. A store buffer can already hide an individual write's latency, so the visible gain may appear only when it would otherwise fill. With a no-write-allocate cache, fetching the cache line just to overwrite it can be unnecessary. Loads benefit directly from earlier data arrival; stores benefit when prefetching removes a required allocation or ownership delay.

The pointer to the next linked list node is unavailable until it has been read from the current linked list node; a software prefetch cannot invent that pointer. Once it is available, however, the current node's computation is useful independent work. Assuming the next field shares the already loaded cache line, use this symbolic loop:Here process_payload must not change the next pointer, and its results must not be needed to determine q. Move the hint before this computation. The real load instruction for the next node still occurs in the next iteration and waits if the prefetch has not finished. The null test can be omitted when the hint's contract safely ignores that target; its cost, when retained, belongs in the loop overhead.

Let $L$ be the additional demand cache miss penalty per node, $C$ the independent processing time after discovering q, and $P$ the cost of issuing one hint. Ignore common loop and cache hit overhead, assume requests do not contend, and assume the prefetched cache line remains resident. Without prefetching, a long traversal takes approximately $L+C$ cycles per node. A hint followed by $C$ cycles of work leaves at most $\max (0,L-C)$ cycles of waiting, givingConsequently the ideal steady-state speedup isFor $L=100$, $C=120$ and $P=1$, the comparison is $220/121\simeq 1.82$. Each hint has enough independent work behind it to hide the entire additional cache miss penalty. For $C=20$ instead, the comparison is $120/101\simeq 1.19$: most of the wait remains. With negligible $P$ the one-node-ahead model approaches a factor of two when $C=L$, not an unlimited speedup.

The first linked list node still has a startup miss. A node occupying several cache lines may need several hints, and a separately missing next field adds a genuine pointer chasing delay. Very short node computations, cache pollution or saturation of the data-transfer path can eliminate the benefit. The speedup comes from overlap with work on the current node; a prefetch does not remove the linked list's address dependence.

With O1, even readers must acquire and release the same mutex. Acquiring it normally uses an atomic read-modify-write on the lock's cache line; releasing writes that cache line again. As different CPU cores repeatedly read the data, ownership of the lock's cache line moves among them, causing cache coherence traffic and serializing the protected operations. If the lock shares a cache line with otherwise stable data, false sharing can also invalidate useful reader data. The actual data need not change for this lock traffic to occur.

With O2 and correctly ordered publication, readers perform only load instructions: copy p once into a processor register, then read that version of the data. Multiple CPU cores can keep read-only shared copies of its cache lines. No per-reader exclusive ownership transfer is needed. During an update, a writer fills newly allocated computer memory privately; the old version's cache lines remain unchanged for readers already using it. Publishing the new pointer writes p and invalidates cached copies of that pointer's cache line, but this occurs only on updates.

For many reads and rare updates, O2 avoids lock-line contention and permits concurrent readers, so it can be substantially faster. The costs are heap allocation, construction or copying of a whole replacement, first accesses to its newly populated cache lines, and deferred memory reclamation. Frequent updates or very large replacements can reverse the comparison. O1 can modify a small field in place and may then save copying and computer memory. These are workload-dependent comparisons, not a claim that removing every mutex always accelerates an operation.

A program-directed hint to fetch a cache line early. A useful nonblocking hint produces no destination processor register value and allows execution to continue before the transfer completes. Fault and dropping behavior depend on the specified instruction contract.