Comment fonctionne le remplacement de page, et qu'est-ce qui cause le thrashing ?

Question

IT Interview Practice · Accepted Answer

Quand la RAM physique se remplit mais que les processus ont besoin de plus de pages, l'OS doit **évincer (evict)** une page résidente pour faire de la place — en l'écrivant sur le **swap** (disque) si elle est dirty. Quelle page évincer est la décision de **remplacement de page (page replacement)**, et se tromper détruit la performance.

## Les politiques de remplacement

L'optimum théorique est d'évincer la page utilisée le plus loin dans le futur (**OPT de Bélády**) — impossible, puisqu'on ne peut pas voir le futur. On approxime donc **LRU (least recently used)** : évincer la page inutilisée depuis le plus longtemps. Le vrai LRU nécessite un horodatage à chaque accès (trop coûteux), donc les vrais kernels utilisent l'**algorithme 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 donne des résultats proches de LRU pour un coût O(1). Linux l'affine encore avec des **listes LRU active/inactive**.

## Working set et thrashing

Le **working set** d'un processus est l'ensemble des pages qu'il utilise activement dans une fenêtre de temps. Le paging fonctionne bien *tant que les working sets combinés tiennent en RAM*. Quand ce n'est pas le cas :

```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
```

Le thrashing est une falaise, pas une pente : dépassez un peu la limite et le throughput s'effondre car presque chaque accès manque (miss). Symptômes : CPU quasi inactif mais I/O disque saturé, et latence qui explose.

## Corriger / éviter

- **Ajouter de la RAM** ou **réduire la charge** (moins de processus concurrents) pour que les working sets tiennent.
- Le scheduler peut **suspendre et swapper (swap-out)** des processus entiers pour réduire la demande (medium-term scheduling).
- L'**OOM killer** de Linux est le dernier recours — tuer un processus plutôt que de thrasher indéfiniment.
- Améliorer la **locality** pour que le working set lui-même soit plus petit.

## Pourquoi c'est important

Cela rassemble toute l'histoire de la mémoire et c'est une question senior favorite car le thrashing est un vrai mode de panne en production : un service qui va bien à N utilisateurs tombe de la falaise à N+1 lorsque son working set dépasse la RAM. Reconnaître la signature (paging intensif, disque saturé, CPU à l'arrêt) et connaître les leviers (RAM, délestage de charge, locality — et le fait que le swap transforme une pénurie de mémoire en catastrophe de latence) fait la différence entre diagnostiquer en quelques minutes et fixer une machine mystérieusement figée.

Les politiques de remplacement

Working set et thrashing

Corriger / éviter

Pourquoi c'est important

Questions connexes