From 'which page' to 'how many frames'
The first three guides treated one process in isolation: given a fixed number of frames and a reference string, which page should the policy evict? FIFO, the optimal benchmark, LRU and the clock all answer that same narrow question. But a real machine is never running one process. Dozens of them — your browser, your editor, a music player, a pile of background daemons — are all alive at once, and they share one physical RAM. So there is a prior question the policy alone cannot answer: out of the total pool of frames, how many does each process get to call its own? That is frame allocation, and it is the subject of this guide.
Why does the count matter so much? Because, as guide 1 showed, the number of frames a process holds is the second great knob on its page-fault rate — and a fault is tens of thousands of times slower than a RAM access. Give a process too few frames and it faults constantly, even under a perfect eviction policy; give it generously and faults nearly vanish. The catch is that frames are zero-sum: every frame you hand to the browser is a frame the editor cannot have. Frame allocation is the art of dividing a scarce, shared resource so that the whole system, not any single process, runs well.
Equal shares versus proportional shares
Suppose the OS has 100 free frames to divide among the processes it is running. The simplest scheme is equal allocation: if there are 5 processes, hand each one 100 / 5 = 20 frames. It is wonderfully fair in the playground sense — everybody gets the same slice. But it is blind to how big each process actually is. A tiny status-bar applet with a 10-page footprint is drowning in 20 frames it will never use, while a 200-page image editor is starved at 20 and faults on nearly every step. Equal shares spread the pain evenly, which often means spreading it badly.
The fairer-in-spirit scheme is proportional allocation: give each process a share of the frames in proportion to the size of its address space (or some estimate of its needs). If process A wants 30 pages and process B wants 70, and 100 frames are available, A gets about 30 and B about 70 rather than a flat 50 each. This matches frames to appetite, so the big process is not starved and the small process is not handed frames it cannot use. Most real allocators lean on a proportional idea, sometimes weighted further by process priority so an important job gets a richer share.
Pool = 100 frames. Two processes, by address-space size: A wants 30 pages B wants 70 pages Equal allocation: A -> 50 frames B -> 50 frames (ignores size) Proportional allocation (share = size / total size): total = 30 + 70 = 100 A -> floor(30/100 * 100) = 30 frames B -> floor(70/100 * 100) = 70 frames Both schemes must respect the per-process minimum, and both must be RECOMPUTED when a new process arrives or an old one exits (the pool gets resliced).
Either way, allocation is not a one-time decision. The mix of running processes is always shifting — a new program launches, another exits, a job swells as it loads a big file. Each change means the pool must be resliced, and a process that was comfortable a second ago can suddenly find its allotment shrinking. That churn is exactly why allocation and replacement cannot be designed apart: how many frames you grant feeds straight into how often the eviction policy has to run.
Global versus local replacement: who can steal from whom
Allocation sets the starting shares, but the moment a process faults with no free frame, a second question fires: where does it find a victim? This is the global versus local replacement choice, and it is arguably more consequential than the equal-versus-proportional split. Under local replacement, a faulting process may only evict one of its own pages. Its frame count is therefore fixed — it can shuffle which of its pages are resident, but it can never grow or shrink its territory at another process's expense. Each process is walled into its own apartment.
Under global replacement, a faulting process may evict any frame in the whole system, including frames currently belonging to other processes. A frame-hungry process simply takes what it needs, so frame counts float freely with demand. This usually gives better overall throughput — frames flow to wherever they are needed most — and it is what most real systems use. But it has a sharp downside: a process's fault rate now depends on the behaviour of its neighbours, not just on its own reference string. One badly behaved, memory-hungry process can quietly steal frames from everyone else, dragging down processes that were running fine.
How much does a process actually need? The working set
All of this raises the real question: how many frames does a process genuinely need right now? Too few and it thrashes; too many and you waste RAM that a neighbour could use. The honest answer is that the need is not constant — it rises and falls as the program moves through its phases. The key insight, due to Denning, is locality: at any moment a program is not scattering its accesses uniformly across its whole address space; it is working intensely within a small cluster of pages — the loop it is in, the array it is scanning, the few data structures in play. That cluster is its current locality, and it shifts as the program moves on.
The working set turns this idea into something the OS can measure. Pick a window of the most recent accesses — say the last 10,000 page references — and the working set is simply the set of distinct pages touched within that window. It is a moving estimate of the program's current locality. If the OS gives a process enough frames to hold its whole working set, it will fault only when the locality shifts (which is rare and unavoidable); if it gives fewer, the process faults on the pages it keeps needing but cannot keep resident. So the working-set size is a far better answer to 'how many frames?' than either equal or pure proportional allocation, because it tracks what the program is doing now, not how big it is in total.
There is a beautifully simple allocation rule lurking here. Sum the working-set sizes of all runnable processes; call it D, the total demand. If D is comfortably less than the number of frames you own, everyone can hold their working set and the machine runs smoothly. But if D climbs above the frame count, then by definition some process must run without its full working set, and the door to trouble swings open. That gap between total demand and physical frames is precisely the precondition for thrashing — the topic of the next and final guide in this rung.
Steering by the fault rate, and what allocation cannot fix
Measuring an exact working set over a sliding window is expensive, so real systems often use a cheaper feedback loop instead: page-fault-frequency (PFF) control. The idea is direct. The OS sets an acceptable band for each process's fault rate. If a process's fault rate climbs above the upper bound, it plainly does not have enough frames — so give it more. If its fault rate drops below the lower bound, it has more frames than it needs — so take some back for others. You do not need to know the working set precisely; you just watch the symptom (faults) and adjust the dose (frames) until the patient settles into the healthy band.
- Periodically measure each process's recent page-fault rate (faults per unit time, or per references).
- If a process is above the upper threshold, it is frame-starved: allocate it more frames (taking them from the free pool, or from a process running below its lower threshold).
- If a process is below the lower threshold, it is over-supplied: reclaim some of its frames so others can use them.
- If demand is so high that no process can be pushed below its threshold without starving, there are simply too few frames for the workload — and the OS must reduce the degree of multiprogramming (suspend or swap out a whole process) rather than keep reshuffling.
That last step is the crucial, humbling limit of allocation. Be honest about what frame allocation can and cannot do: it can divide a sufficient pool well, but it cannot conjure frames that do not exist. When the summed demand of the runnable processes genuinely exceeds physical RAM, no allocation policy — equal, proportional, global, local, or PFF-steered — can give every process its working set, because there are not enough frames to go around. The only real cure is to run fewer processes at once: suspend one, free its frames, and let the survivors breathe. Remember too that virtual memory never made programs faster; it let them run at all, and when frames are this scarce it makes them dramatically slower. Spotting that collapse, naming its feedback spiral, and pulling the system out of it is exactly where the final guide picks up: thrashing.