Program-counter-based classification (PCC)
PCC classifies buffer-cache accesses by the program contexts issuing I/O, allowing learned access patterns to guide replacement across files.
PCC's signature PC sums call-site addresses along the stack up to main(), separating callers that share an I/O wrapper. A single system-call address would merge those callers. The historical 32-bit signature is a compact context key, not a collision-free identity. [1]
The block table records the last accessing context. When a tracked block is reused, its previous context receives the reuse evidence, even if a different context issues the new access. The classifier's sequential category means distinct blocks without reuse, not necessarily adjacent disk addresses. [1]
The OSDI 2004 comparison replaced UBM's classifier while retaining its marginal-gain cache manager; the kernel implementation used Linux 2.4.20. AMP's later PCC* comparator instead used PCC detection with AMP cache management. These are different experimental comparisons. [1] [2]
For synthetic address lists, [0x1000,0x2000,0x4000] and [0x1000,0x2800,0x3800] both sum to 0x7000. This collision needs neither overflow nor identical frames. Exact-list identity separates them; a sum alone does not. The downloadable calculation is an arithmetic illustration, not a measured collision rate or cache benchmark. [3]
Relations
Limitations
- Sampling and context history affect classification; a learned pattern is a prediction, not a guarantee of future block reuse. [1]
- The Linux 2.4.20 prototype could not obtain signature PCs for mmap accesses and classified those references as other. [1]
Citations
- Gniady, Butt and Hu. Program-Counter-Based Pattern Classification in Buffer Caching. OSDI 2004, sections 4-5.
- Zhou, von Behren and Brewer. AMP: Program Context Specific Buffer Caching. USENIX ATC 2005, sections 1-3.
- Hesela. Exact additive-signature examples: common wrappers, distinct sums and equal-sum collisions.
Further reading
- Hesela. Bounded exact-sum illustration; no stack unwinding, cache simulation or hash-probability model.
- Hesela. Signature arithmetic tests and an independent bit-column addition oracle.
- Hesela. Interpretation, reproduction instructions and limits of the signature example.
Sources & caveats
- Full primary-paper design and evaluation reviewed. Historical workloads and kernel results are not performance predictions for current systems. [1] [2]
- The constructed equal-sum case uses invented addresses, not executable traces. It establishes non-unique arithmetic, not observed collisions in PCC. [3]