Concepts and theorems · Intermediate

Working sets: count the pages a workload actually reuses

Distinguish allocated memory from recently referenced pages and reason about changing workload phases.

Ask Logeia about this articleTry the three questionsReview your answers

Updated

On this page
  1. Count references within a window
  2. Work through a reference trace
  3. Relate the set to pressure
  4. Avoid equating it with RSS
  5. Slide the window through a trace
  6. Test a small change in access order
  7. Ask Logeia about this articleCheck your understanding

Count references within a window

A working set is a set of pages referenced during a specified observation window. Reserving a large virtual region does not make every page part of the current working set. A program may repeatedly use only a small part of that region. Conversely, a scan that touches a little data on every page can need a wide resident footprint. State whether the window represents elapsed time or a number of references before comparing two measurements. Different definitions produce different, potentially useful views of the same workload.

A photo editor illustrates why the observation interval matters. Loading an image and repeatedly applying a filter can touch very different page sets. A sample taken only during startup does not describe the whole editing session. Record the beginning and end of the interval, and distinguish elapsed wall time from a window defined over references made while the process actually runs. Otherwise, descheduling a process can make its apparent recent demand shrink without any change to its algorithm or data.

Work through a reference trace

Consider the page trace A, B, A, C, D, A and define the window as the most recent four references. The final window is A, C, D, A, so its distinct pages are A, C and D. B was used earlier but is outside this window. With an assumed page size of 4 KiB, those three pages occupy 12 KiB of page capacity. Expanding the window to six references includes B and gives 16 KiB. These are calculations from an invented trace, not measured running times or an operating system counter.

Repeated access to a page does not add another element to the set. Three accesses to A and one access each to A, B, and C have equal reference counts but different distinct-page counts. The set also discards ordering information, so its size alone does not determine the best replacement decision. Keep the original reference trace and slide the window one position at a time. This makes it possible to explain exactly which page enters or leaves each observed set.

Relate the set to pressure

If several active workloads need more pages than physical memory can keep, a page may be evicted shortly before it is needed again. Reclaim and refault activity can then consume time without useful application progress. This is a way to reason about thrashing, not a diagnosis from one number. A one-pass file scan has different reuse needs from a loop over a recurring index. The same number of referenced pages can have different reuse distances, so retain the access order as well as the set size when analysing the problem.

Capacity planning must include other processes running concurrently. Giving one task more resident pages can displace pages needed by another task. Simply adding each process’s set can double-count shared pages, so a system-wide physical requirement needs a separate accounting model. Under severe pressure, reducing concurrent batch work can improve total completion time by allowing each remaining task to retain useful pages. That is a workload scheduling decision rather than a universal instruction to maximize every individual process’s resident memory.

Avoid equating it with RSS

RSS describes currently resident memory, not precisely the pages referenced in your chosen recent window. Shared mappings, anonymous memory, file cache and huge pages complicate comparisons further. Separate startup from steady state and observe faults and reclaim under the same workload and window definition. Processing a dataset in smaller blocks can reduce the pages needed together, but may add computation or I/O. A smaller working set is helpful only when the total cost and required behaviour improve; it is not an independent objective that overrides correctness.

Resident-memory counters and fault counters from Linux proc files are proxies, not a direct implementation of the mathematical definition. More minor faults do not necessarily mean more disk reads; anonymous allocation and copy-on-write are possible explanations. Align counter intervals and report the units before interpreting the numbers. Separating a conceptual reference set from an operating-system counter prevents an apparently precise number from becoming an unjustified claim about the minimum memory a production service requires.

Slide the window through a trace

With references A, B, A, C, D, A and a window of four references, the sets after the fourth, fifth, and sixth accesses are {A,B,C}, {B,A,C,D}, and {A,C,D}. Their sizes are three, four, and three. No physical-memory capacity changed in this calculation; only the recently referenced pages changed. Increasing the window from four to six is a different comparison because it changes the definition at the same observation point. Keep those two operations separate. Also specify whether the page identities are virtual or physical: aliases and shared mappings can make a simple distinct-virtual-page count differ from the required number of physical frames. A hand trace with fixed-size pages is a model, while production accounting must address the operating system’s actual mapping and sharing rules.

Test a small change in access order

Suppose a column-by-column scan is changed to process all relevant columns for a bounded group of rows before moving on. The intention is to shorten the interval between reuses of the same pages. Making groups too small can add loop overhead or extra I/O operations, so the transformation is not automatically beneficial. First establish equal results, then vary group size while holding input size and concurrency constant. Separate cold startup from warmed execution, and record the measurement conditions. Shared cache contents can depend on unrelated work. A single faster run is not proof of a universally optimal group size, but a controlled comparison can connect a change in access order to a plausible change in memory demand.

Reading and practice are recorded separately in this browser, for each language.

Learn this in order

Build your CS foundations · STEP 16

Understand the systems behind the web · STEP 6

Prepare for AI systems · STEP 6

Choose a learning path