Hur fungerar page replacement, och vad orsakar thrashing?

Question

IT Interview Practice · Accepted Answer

När fysiskt RAM fylls men processer behöver fler pages måste OS **evicta** en resident page för att göra plats — och skriva den till **swap** (disk) om den är dirty. Vilken page som ska evictas är beslutet **page replacement**, och att få det fel förstör prestanda.

## Replacement-policyer

Det teoretiska optimum är att evicta den page som används längst in i framtiden (**Béládys OPT**) — omöjligt, eftersom man inte kan se framtiden. Så vi approximerar **LRU (least recently used)**: evicta den page som varit oanvänd längst. Äkta LRU behöver en tidsstämpel vid varje åtkomst (för dyrt), så riktiga kernels använder **clock (second-chance)-algoritmen**:

```text
Frames arranged in a ring; each has a REFERENCE bit the hardware sets on access.
A "hand" sweeps around the ring:
   ref bit = 1 → clear it, give the page a second chance, move on
   ref bit = 0 → evict THIS page (approximates "least recently used")

[1]→[1]→[0] ← evict here   (the sweep clears 1s until it finds a 0)
         ▲___________|
```

Clock ger LRU-liknande resultat till O(1)-kostnad. Linux förfinar det ytterligare med **active/inactive LRU lists**.

## Working set och thrashing

En process **working set** är den uppsättning pages den aktivt använder inom ett tidsfönster. Paging fungerar bra *så länge de kombinerade working sets ryms i RAM*. När de inte gör det:

```text
working set > RAM → evict a page that's about to be needed → immediate page fault →
evict another needed page → ... → the CPU spends ~all its time paging to disk, ~0% on real work
                            = THRASHING
```

Thrashing är en klippa, inte en sluttning: gå lite över gränsen och throughput kollapsar eftersom nästan varje åtkomst missar. Symptom: CPU nära inaktiv men disk-I/O mättad, och latency som exploderar.

## Att åtgärda / undvika det

- **Lägg till RAM** eller **minska last** (färre samtidiga processer) så att working sets ryms.
- Schedulern kan **suspendera och swappa ut** hela processer för att krympa efterfrågan (medium-term scheduling).
- Linux **OOM killer** är sista utvägen — döda en process hellre än att thrasha för evigt.
- Förbättra **locality** så att själva working set blir mindre.

## Varför det är viktigt

Detta knyter ihop hela minnesberättelsen och är en favoritfråga för seniorer eftersom thrashing är ett verkligt produktionsfelläge: en tjänst som mår bra vid N användare faller av en klippa vid N+1 när dess working set överstiger RAM. Att känna igen signaturen (tung paging, mättad disk, avstannad CPU) och känna till spakarna (RAM, load shedding, locality — och att swap förvandlar en minnesbrist till en latency-katastrof) är skillnaden mellan att diagnostisera det på minuter och att stirra på en mystiskt frusen maskin.

Replacement-policyer

Working set och thrashing

Att åtgärda / undvika det

Varför det är viktigt

Relaterade frågor