Πώς λειτουργεί η αντικατάσταση σελίδων (page replacement), και τι προκαλεί το thrashing;

Question

IT Interview Practice · Accepted Answer

Όταν η φυσική RAM γεμίζει αλλά οι διεργασίες χρειάζονται περισσότερες σελίδες, το OS πρέπει να **εκδιώξει (evict)** μια σελίδα που κατοικεί για να κάνει χώρο — γράφοντάς την στο **swap** (δίσκο) αν είναι βρώμικη (dirty). Το ποια σελίδα να εκδιώξει είναι η απόφαση **αντικατάστασης σελίδων (page replacement)**, και το να την κάνετε λάθος καταστρέφει τις επιδόσεις.

## Πολιτικές αντικατάστασης

Το θεωρητικό βέλτιστο είναι να εκδιώξετε τη σελίδα που θα χρησιμοποιηθεί πιο μακριά στο μέλλον (**OPT του Bélády**) — αδύνατο, αφού δεν μπορείτε να δείτε το μέλλον. Έτσι προσεγγίζουμε το **LRU (least recently used)**: εκδιώξτε τη σελίδα που είναι αχρησιμοποίητη για τον μεγαλύτερο χρόνο. Το πραγματικό LRU χρειάζεται χρονοσφραγίδα σε κάθε πρόσβαση (πολύ δαπανηρό), οπότε οι πραγματικοί kernels χρησιμοποιούν τον **αλγόριθμο 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 δίνει αποτελέσματα σαν LRU με κόστος O(1). Το Linux το βελτιώνει περαιτέρω με **active/inactive λίστες LRU**.

## Working set και thrashing

Το **working set** μιας διεργασίας είναι το σύνολο των σελίδων που χρησιμοποιεί ενεργά μέσα σε ένα χρονικό παράθυρο. Το paging λειτουργεί μια χαρά *εφόσον τα συνδυασμένα working sets χωράνε στη RAM*. Όταν δεν χωράνε:

```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 είναι ένας γκρεμός, όχι μια πλαγιά: ξεπεράστε λίγο το όριο και το throughput καταρρέει επειδή σχεδόν κάθε πρόσβαση αστοχεί. Συμπτώματα: CPU σχεδόν σε αδράνεια αλλά I/O δίσκου κορεσμένο, και latency να εκρήγνυται.

## Διόρθωση / αποφυγή

- **Προσθέστε RAM** ή **μειώστε το φορτίο** (λιγότερες ταυτόχρονες διεργασίες) ώστε τα working sets να χωρέσουν.
- Ο scheduler μπορεί να **αναστείλει και να κάνει swap-out** ολόκληρες διεργασίες για να συρρικνώσει τη ζήτηση (medium-term scheduling).
- Ο **OOM killer** του Linux είναι η έσχατη λύση — σκότωσε μια διεργασία αντί να κάνεις thrash για πάντα.
- Βελτιώστε την **locality** ώστε το ίδιο το working set να είναι μικρότερο.

## Γιατί έχει σημασία

Αυτό δένει όλη την ιστορία της μνήμης μαζί και είναι αγαπημένη ερώτηση senior επειδή το thrashing είναι ένας πραγματικός τρόπος αποτυχίας στην παραγωγή: μια υπηρεσία που είναι εντάξει με N χρήστες πέφτει από τον γκρεμό στους N+1 καθώς το working set της ξεπερνά τη RAM. Η αναγνώριση της υπογραφής (βαρύ paging, κορεσμένος δίσκος, καθηλωμένη CPU) και η γνώση των μοχλών (RAM, load shedding, locality — και ότι το swap μετατρέπει μια έλλειψη μνήμης σε καταστροφή latency) είναι η διαφορά ανάμεσα στο να το διαγνώσετε σε λεπτά και στο να κοιτάτε ένα μυστηριωδώς παγωμένο μηχάνημα.

Πολιτικές αντικατάστασης

Working set και thrashing

Διόρθωση / αποφυγή

Γιατί έχει σημασία

Σχετικές ερωτήσεις