= Thrashing
{disambiguate=computer science}
{wiki}
= Memory thrashing
{synonym}
<Memory thrashing> is repeated costly cycling of <memory pages> out of and back into <computer memory>, leaving little useful computation between <page faults>. Active demand can exceed the available <page frames>, especially when <multiprogramming> admits too many <operating-system processes>. A high <page fault rate> during initial loading alone does not establish <memory thrashing>. <Operating Systems: Three Easy Pieces by Remzi H. Arpaci-Dusseau and others/Beyond Physical Memory: Policies>[Arpaci-Dusseau and Arpaci-Dusseau, OSTEP chapter 22, section 22.11: Thrashing]{ref}
Consider one <operating-system process> making the 20 <memory references> $1,2,3,4,1,2,3,4,\ldots,1,2,3,4$: five repetitions of four <memory pages>. Start with an empty <resident set>, use <demand paging> and exact <LRU replacement>, and assume no prefetching or competing <operating-system processes>. A hit finds the requested <memory page> resident; a miss requires a nonresident <page fault>. With three <page frames>, references 1–3 load pages 1–3. Reference 4 evicts page 1, reference 5 reloads page 1 and evicts page 2, and the cycle continues: every return finds its <memory page> evicted. With four <page frames>, only the first four references miss; all four <memory pages> then remain resident.
|| Available <page frames>
|| Misses in all 20 <memory references>
|| Overall <page fault rate>
|| Misses in references 5–20
|| <Page fault rate> in references 5–20
| 3
| 20
| 100%
| 16
| 100%
| 4
| 4
| 20%
| 0
| 0%
The four initial misses with four <page frames> are compulsory first-use misses from the empty <resident set>. They are startup work; the three-<page frame> case keeps faulting after startup. This makes the difference between <memory thrashing> and loading a new <working set> visible. For the three-<page frame> trace, each reused <memory page> has three distinct intervening <memory pages>, so <LRU replacement> has already evicted it before its next use.
\Image[/memory-thrashing-lru-capacity.png]
{title=The same 20 memory references under <LRU replacement>: three <page frames> miss every time, four miss only during startup}
To quantify the cost, assume each hit takes 100 nanoseconds and each miss incurs an additional 1 millisecond of <page fault> service, followed by the same 100-nanosecond memory access. These are toy latencies, not measurements. With miss <probability> $p$, the <expected value> of access time is
$$
E[T]=100\,\mathrm{ns}+p\,(1\,\mathrm{ms}).
$$
The service cost is additional: it does not include the final 100 nanoseconds. Thus $p=1$ gives $1{,}000{,}100\,\mathrm{ns}$ and $p=0.2$ gives $200{,}100\,\mathrm{ns}$, approximately a fivefold ratio over the complete trace. Over references 5–20, the corresponding ratio is $1{,}000{,}100/100=10{,}001$: repeated <page faults> dominate the useful accesses. The <expected value> model follows the additive miss-penalty convention of OSTEP chapter 22, section 22.1. <Operating Systems: Three Easy Pieces by Remzi H. Arpaci-Dusseau and others/Beyond Physical Memory: Policies>[Arpaci-Dusseau and Arpaci-Dusseau, OSTEP chapter 22, equation 22.1: average memory access time]{ref}
Not every <page fault> performs disk <input-output>: <demand paging> can allocate zero-filled <memory pages>, and <copy-on-write> can copy an existing <page frame>. The toy service cost models expensive misses; the miss trace alone establishes residency behavior, while <memory thrashing> additionally concerns repeated costly cycling. https://pages.cs.wisc.edu/~remzi/OSTEP/vm-complete.pdf[Arpaci-Dusseau and Arpaci-Dusseau, OSTEP chapter 23, section 23.1, Other Neat Tricks: demand zeroing and copy-on-write]{ref}
Possible remedies are more resident <page frames>, less <multiprogramming>, or reorganizing accesses to improve <temporal locality>. For this toy <sequence>, one extra <page frame> suffices under <LRU replacement>; that is not a universal threshold or policy. <Page replacement> alone cannot make every simultaneously needed <memory page> fit.
// Target: computer-science.bigb
Back to article page
