Separate allocated space from recently used pages
A program can allocate a large array without touching every page at once. Two jobs with equal allocation sizes may also impose different pressure when one repeatedly visits a much wider region. A working set models pages referenced within a declared recent window. The window definition is essential; a bare number of bytes does not identify what was counted.
Our model uses page-reference positions and a window of the last several references. That is not automatically identical to research or OS mechanisms defining windows in elapsed or execution time. Start with a small explicit trace. Keep virtual address range, allocated storage, resident pages and recently referenced pages as separate quantities. Their relationship helps explain behavior, but their values cannot be substituted for one another simply because all are described informally as memory usage.
Count one trace using two windows
For references zero, one, two, three, zero, four, one, five, the final four references contain four distinct pages: zero, one, four and five. The final eight contain six distinct pages, zero through five. At one execution point, changing the window changes the answer. Eight references and six distinct pages are also different counts.
When a window slides, one departing occurrence does not necessarily remove its page from the set; another occurrence may remain. A frequency-maintaining implementation can update membership efficiently, while this small example simply slices and constructs a set. Those are representation choices for the same declared measurement. Do not accidentally change the meaning of the window while optimizing the method used to count its pages.
| Reference window | References in window | Distinct pages |
|---|---|---|
| Last four | 0,4,1,5 | 4 |
| Last eight | 0,1,2,3,0,4,1,5 | 6 |
Check the identity space before adding jobs
Suppose A references zero through three and B references two through five. Set sizes sum to eight while their union has six members. This union calculation only represents shared page identities if the model uses one common page-ID space. Equal virtual page numbers in separate processes need not designate the same physical page. They cannot establish that six physical frames suffice.
Read-only shared libraries, copy-on-write separation and private heaps create different sharing relationships. Process RSS sums therefore need not equal deduplicated physical usage. When planning resident capacity, identify the address space, physical sharing and measurement API. The model's set arithmetic explains a distinction but is not a direct formula for operating-system memory accounting across arbitrary processes.
Execute the reference-set model
The code prints the two window sets and asserts sizes four and six, then checks size-sum eight versus union six for the two modeled jobs. It measures neither page faults nor RSS. Its final label explicitly identifies a virtual-page-set model. Compare it by hand to the duplicate-eliminated trace before extending the input.
A real trace requires definitions for address-to-page rounding, what event counts as a reference and whether observation misses accesses. A sampled trace is not a complete reference stream. Huge pages and file mappings may also differ from the uniform-page model. Preserve those observation limits rather than treating unseen references as nonexistent. Executing the set calculation validates that calculation, not a reproduction of every OS replacement or residency decision.
references=[0,1,2,3,0,4,1,5]
for window in [4,8]:
pages=set(references[max(0,len(references)-window):]);print('window=',window,'pages=',sorted(pages),'size=',len(pages))
assert len(set(references[-4:]))==4 and len(set(references[-8:]))==6
left={0,1,2,3};right={2,3,4,5}
assert len(left)+len(right)==8 and len(left|right)==6
print('two virtual-page sets: sum=8 union=6; not a physical RSS measurement')
Do not equate every fault with a disk read
Page faults cover different conditions, including page allocation, mapping or permission handling and copy-on-write. Check the operating system's major/minor counter definitions before converting total faults into disk-read counts. A page may already be cached elsewhere. An address-translation exception and waiting for storage media are different events.
Repeatedly touching a working region larger than available residency can increase replacement work and reduce useful progress, but elapsed-time growth alone does not prove that cause. Observe CPU, I/O, residency and fault categories over a common interval. The set model helps reason about needed pages; it is not a complete diagnosis of physical latency. Connect it to vmstat and memory-observation readings and state which measurements support a particular explanation.
Change the processing unit deliberately
Processing all users a little at a time versus finishing one user's necessary fields together can produce different page sets in a short reference window. This connects to the earlier row/column access experiment. Larger batches may amortize preparation while increasing retained state or request waiting. A smaller working-set estimate alone does not make the smallest batch universally best.
Preserve results and total visited work when comparing order changes. Separate setup and output from the measured operation. If layout changes too, record access order and layout as different factors. A single RSS observation after a configuration change does not prove that the recently referenced region moved in the same direction. Evaluate modeled working pages, actual residency and user-visible waiting as separate columns rather than interchangeable optimization scores.
A page leaving the model window is not an eviction event
When page two leaves the reference window, the operating system has not necessarily evicted it at that instant. The model describes recent accesses rather than issuing a physical-residency command. A later reference may find the page still resident. Do not assign a one-to-one replacement event to every change in the modeled set.
Likewise the time at which a residency API samples state can differ from the reference event being analyzed. Align observation timing and event scope. Counting pages needed by a trace and locating data currently resident answer separate questions, so unchanged values in one do not automatically invalidate the other. Use model and observation as complementary evidence with distinct names. That separation is especially useful when a small change in processing order improves access behavior without producing an equally obvious change in total resident bytes.
Record sensitivity to the chosen window
One window size can hide an accidental relationship with workload periodicity. A job repeatedly scanning four pages may occasionally touch a broad administrative region; whether that event remains inside the chosen window changes the result. Use several widths and record the trace position to distinguish transient expansion from recurring locality.
Both compared methods must use the same window definition. The last hundred references and the last second are not interchangeable scales. Align input, page granularity, window and observation point, then record where conclusions change. The two-window code is an introduction to that sensitivity analysis, not a trace of every phase of a real application. It helps select what additional trace evidence is needed before deciding a memory-capacity or processing-order change.
Exercise: solve the window and sharing questions
For references one, two, one, three, four, one, the final three references give set one, three, four with size three. The final six give one through four with size four. Doubling reference count does not double distinct pages. State that the window counts references rather than seconds; those definitions are not interchangeable.
If two processes both use virtual page numbers one and two, the required physical-page count cannot be determined from those numbers alone. Shared mappings and private frames must be identified. Similarly, fewer faults with nearly unchanged RSS is not inherently contradictory because recent reference activity and resident quantity measure different things. Answer by separating the set definition, identity scope, measurement API and interpretation of observed performance.