Cum funcționează înlocuirea paginilor și ce cauzează thrashing-ul?

Question

IT Interview Practice · Accepted Answer

Când RAM-ul fizic se umple, dar procesele au nevoie de mai multe pagini, OS-ul trebuie să **evacueze (evict)** o pagină rezidentă pentru a face loc — scriind-o în **swap** (disc) dacă e murdară (dirty). Ce pagină să evacueze este decizia de **înlocuire a paginilor (page replacement)**, iar greșeala aici distruge performanța.

## Politici de înlocuire

Optimul teoretic este să evacuezi pagina folosită cel mai departe în viitor (**OPT al lui Bélády**) — imposibil, pentru că nu poți vedea viitorul. Așa că aproximăm **LRU (least recently used)**: evacuează pagina nefolosită cel mai mult timp. LRU adevărat are nevoie de un timestamp la fiecare acces (prea costisitor), așa că kernel-urile reale folosesc **algoritmul clock (second-chance)**:

```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 dă rezultate asemănătoare LRU la cost O(1). Linux îl rafinează suplimentar cu **liste LRU active/inactive**.

## Working set și thrashing

**Working set**-ul unui proces este mulțimea paginilor pe care le folosește activ într-o fereastră de timp. Paging-ul funcționează bine *atâta timp cât working set-urile combinate încap în RAM*. Când nu încap:

```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-ul este o prăpastie, nu o pantă: depășești puțin limita și throughput-ul se prăbușește pentru că aproape fiecare acces dă miss. Simptome: CPU aproape inactiv, dar I/O-ul de disc saturat, iar latența explodând.

## Repararea / evitarea lui

- **Adaugă RAM** sau **redu încărcarea** (mai puține procese concurente) ca working set-urile să încapă.
- Scheduler-ul poate **suspenda și face swap-out** la procese întregi pentru a micșora cererea (medium-term scheduling).
- **OOM killer**-ul din Linux este ultima soluție — omoară un proces în loc să facă thrashing la nesfârșit.
- Îmbunătățește **locality**-tea, astfel încât working set-ul însuși să fie mai mic.

## De ce contează

Asta leagă întreaga poveste a memoriei și este o întrebare senior preferată, pentru că thrashing-ul este un mod real de eșec în producție: un serviciu care e în regulă la N utilizatori cade în prăpastie la N+1 pe măsură ce working set-ul depășește RAM-ul. A recunoaște semnătura (paging masiv, disc saturat, CPU blocat) și a cunoaște pârghiile (RAM, load shedding, locality — și faptul că swap-ul transformă o lipsă de memorie într-o catastrofă de latență) este diferența dintre a-l diagnostica în câteva minute și a te holba la o cutie înghețată în mod misterios.

Politici de înlocuire

Working set și thrashing

Repararea / evitarea lui

De ce contează

Întrebări conexe