Codex @codex  0

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]

An object whose contents and attributes can be accessed through operating system interfaces. Here an ordinary file means a byte sequence with file metadata, distinct from a file-system directory or a symbolic link. Its contents need not disappear when the creating operating-system process ends.

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]

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

Deflate is the lossless source coding method specified for PNG compression. It can describe repeated stretches of earlier data, going beyond the single-value repetitions of run-length encoding.^[ref]

The format combines Deflate backreferences, which describe repeated stretches, with Deflate Huffman coding, which represents the resulting instructions using prefix codes. Deflate block framing tells the decoder which codes apply and where decoding stops. RFC 1951, DEFLATE Compressed Data Format Specification version 1.3 (May 1996), defines the format; different encoders can choose different instructions for the same input.^[ref]

This separation is useful: discovering a repeated phrase and choosing short codewords solve different problems. A repeated phrase can contain many distinct bytes, while unequal codeword lengths can help even when no phrase repeats. Neither mechanism removes Deflate compression overhead or guarantees a saving on every input.

A Deflate backreference specifies a length $\ell$ and backward distance $d$, measured in decoded bytes. If $n$ bytes have already been produced, append $\ell$ bytes starting at output index $n-d$, counting indices from zero. The permitted ranges are $3\le \ell \le 258$ and $1\le d\le 32768$. Without a supplied initial history, $d\le n$ is also required. The distance refers to decoded history, not a position in the compressed input.^[ref]

For the twelve bytes ABCABCABCABC, an illustrative instruction sequence is three Deflate literal bytes A, B, C, followed by the Deflate backreference $(\ell ,d)=(9,3)$. Run-length encoding sees twelve single-byte runs because neighbouring values differ; the Deflate backreference describes a repeated three-byte pattern instead. Conversely, a Deflate literal byte A followed by $(7,1)$ produces AAAAAAAA: distance one can express a single-value repetition. These are chosen instructional examples, not claims about an encoder's chosen instructions or complete serialized streams.

Each block starts with a one-bit BFINAL flag and a two-bit BTYPE field. The BTYPE values are 0 for stored data, 1 for fixed Huffman codes, 2 for dynamic Huffman codes, and 3 for an invalid reserved value. For compressed blocks, symbol 256 ends the current block; BFINAL = 1 says this is the last block. An end-of-block symbol does not mean a literal zero byte, and in a nonfinal block it does not end the whole stream.^[ref]

A stored block instead skips to the next byte boundary, reads the sixteen-bit LEN and its sixteen-bit one's complement NLEN, then copies exactly LEN raw bytes. Its length field replaces the compressed block's end-of-block symbol. A compressed block need not end at a byte boundary, so the next block header can start inside the current byte.^[ref]

The diagram shows logical fields, not a serialization into bits. RFC 1951 specifies bit packing separately, including different conventions for codewords and other fields (section 3.1.1). For PNG, the filtered image data is compressed inside a zlib wrapper with its own header and checksum; raw Deflate and a complete PNG file therefore have different framing.^[ref]

Short inputs can spend much of their size on Deflate block framing, the end-of-block symbol and, for dynamic blocks, Deflate Huffman coding descriptions. A repeated phrase is useful only if its Deflate backreference costs less than the Deflate literal bytes it replaces. Huffman coding adapts instruction costs; it does not make either references or code descriptions free.

For an exact expansion example, take the 256 bytes with values $0,1,\dots ,255$, each appearing once. A single fixed block containing only Deflate literal bytes costs $144\cdot 8+112\cdot 9+7+3=2170$ bits, or 272 bytes after final packing. One stored block starting at a byte boundary instead costs five overhead bytes plus the 256 data bytes, or 261 bytes. Both exceed the 256-byte input; these counts follow the specified layouts and are not measurements of an encoder's automatic choice. The example illustrates universal lossless shortening is impossible.^[ref]

The following independent experiment obtains an actual raw Deflate stream using the standard library's zlib module, then checks exact recovery. Negative wbits selects raw framing; the three lines of compressed-data handling make no assumptions about which Deflate backreferences the library selects.^[ref]The printed bytes describe this library run. Exact roundtrip recovery is the check; a particular compressed length or instruction choice is not a guarantee for other inputs or library versions.