Follow a page read through the computer

The page introduction showed a file page entering a memory frame. What happens when the engine asks for a page that is not in its own frames? It may need storage, but a missing engine-buffer entry does not prove that a device read occurred.

The operating system manages the machine’s resources and provides file operations to programs. In a typical buffered-file setup, it also keeps recently used file data in a memory cache. The engine’s buffer pool and this operating-system cache are separate collections.

Follow the missing page

Suppose product 27 is stored on page P. The engine knows P’s identity but does not currently hold it. Assume ordinary buffered file I/O, rather than direct I/O that bypasses some caching.

Engine checks its frames
P is absent. The engine reserves a frame for the read.
Engine asks the operating system
If cached file bytes for P are available, the system can supply them without a new device read.
If those bytes are absent
The system requests storage I/O, waits for completion, and returns the bytes or an error.

A miss at one layer can be a hit at the next. Measure which layer performed the expensive work.

A cache hit means the requested item is already available in the cache being discussed. A miss means it is not. Naming the cache matters: “the cache missed” is incomplete evidence when several caches exist.

The processor still has work to do

Even when P is in the engine’s memory, reading it takes instructions and memory accesses. A processor executes instructions using small, fast caches near its cores. A core is an execution unit that can run a stream of instructions. Fetching scattered data can leave it waiting for memory.

Consider a linked chain where each entry contains the address of the next. The processor cannot know the third address until it reads the second entry. Some waits are therefore dependent and cannot all happen at once. A compact array can expose upcoming addresses sooner. This explains why two structures with similar comparison counts can have different elapsed times.

We do not need a memorized latency table. We need to identify the path: instructions, waiting for memory, waiting for storage, and any copying between layers. Actual timings depend on the machine and workload.

Interpret a second run

A lookup is much faster the second time. Does that prove the index became more efficient?

Hold the algorithm separate from the stored state

No. The same lookup algorithm may now find its pages in the engine’s pool, the operating-system cache, or processor caches. To compare algorithms fairly, describe the initial cache state and inspect the work performed. A faster elapsed time alone does not identify the cause.

The practical question is now sharper: which useful pages should the engine keep? The buffer-management lesson follows a workload where a one-time scan evicts pages that ordinary lookups keep needing.

OSTEP’s I/O-device chapter explains the operating system’s role in device access. Cache behavior varies with the chosen I/O interface.

Extended reference

The extended chapter preserves the original technical coverage, additional examples, and citations. The explanation above supplies the concepts needed for this page; the reference develops the specialist cases.

Find a section from the original chapter