Bagaimana page replacement bekerja, dan apa yang menyebabkan thrashing?

Question

IT Interview Practice · Accepted Answer

Ketika RAM fisik penuh tetapi process membutuhkan lebih banyak page, OS harus **mengusir (evict)** sebuah page yang residen untuk memberi ruang — menulisnya ke **swap** (disk) jika ia kotor (dirty). Page mana yang diusir adalah keputusan **page replacement**, dan salah melakukannya merusak performa.

## Kebijakan replacement

Optimum teoretisnya adalah mengusir page yang dipakai paling jauh di masa depan (**OPT milik Bélády**) — mustahil, karena Anda tidak bisa melihat masa depan. Jadi kita mendekati **LRU (least recently used)**: usir page yang paling lama tidak dipakai. LRU sejati membutuhkan timestamp pada setiap akses (terlalu mahal), sehingga kernel nyata menggunakan **algoritma 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 memberi hasil mirip-LRU dengan biaya O(1). Linux menyempurnakannya lebih jauh dengan **daftar LRU active/inactive**.

## Working set dan thrashing

**Working set** sebuah process adalah himpunan page yang aktif ia gunakan dalam suatu jendela waktu. Paging bekerja baik-baik saja *selama gabungan working set muat di RAM*. Ketika tidak muat:

```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 adalah sebuah tebing, bukan sebuah lereng: sedikit saja melewati batas dan throughput runtuh karena hampir setiap akses miss. Gejalanya: CPU nyaris idle tetapi I/O disk jenuh, dan latency meledak.

## Memperbaiki / menghindarinya

- **Tambah RAM** atau **kurangi beban** (lebih sedikit process bersamaan) agar working set muat.
- Scheduler bisa **menangguhkan dan swap-out** seluruh process untuk menyusutkan permintaan (medium-term scheduling).
- **OOM killer** milik Linux adalah pilihan terakhir — bunuh sebuah process ketimbang thrash selamanya.
- Perbaiki **locality** agar working set itu sendiri lebih kecil.

## Mengapa ini penting

Ini mengikat seluruh cerita memory menjadi satu dan merupakan pertanyaan senior favorit karena thrashing adalah mode kegagalan produksi yang nyata: sebuah service yang baik-baik saja pada N pengguna jatuh dari tebing pada N+1 saat working set-nya melampaui RAM. Mengenali tanda tangannya (paging berat, disk jenuh, CPU macet) dan mengetahui tuas-tuasnya (RAM, load shedding, locality — dan bahwa swap mengubah kekurangan memory menjadi bencana latency) adalah perbedaan antara mendiagnosisnya dalam hitungan menit dan menatap sebuah mesin yang membeku secara misterius.

Kebijakan replacement

Working set dan thrashing

Memperbaiki / menghindarinya

Mengapa ini penting

Pertanyaan terkait