the working set and locality of reference

Programs do not touch memory at random. Over any short stretch of time a program keeps coming back to the same small handful of pages — the loop it is running, the data it is chewing on — and leaves the rest alone. The working set is that set of pages a program is actively using right now; locality of reference is the general tendency that makes the working set small and predictable.

Locality comes in two flavours, both worth naming. Temporal locality: if you used an address recently, you are likely to use it again soon (a loop counter, a frequently called function). Spatial locality: if you used an address, you are likely to use nearby ones soon (walking through an array element by element, fields of the same struct). Together they mean that at any moment only a modest number of pages are 'hot', and a program with good locality keeps that hot set tight. The working set is essentially the pages it has touched in the recent past, used as a guess for what it will touch next.

This is the idea that makes the whole memory hierarchy work. The TLB, CPU caches, demand paging, and the page-eviction policy all bet on locality: keep the working set in fast memory, let the cold rest sit in slower storage. As long as a program's working set fits in RAM, paging is cheap and rare. The danger appears when working sets outgrow RAM — that is precisely the condition for thrashing. Writing memory-friendly code (traversing arrays in order, keeping related data together) is mostly about shrinking and tightening the working set.