Bagaimana penggantian page berfungsi, dan apakah yang menyebabkan thrashing?

Question

IT Interview Practice · Accepted Answer

Apabila RAM fizikal penuh tetapi process memerlukan lebih banyak page, OS mesti **mengusir (evict)** page pemastautin untuk memberi ruang — menulisnya ke **swap** (cakera) jika ia kotor (dirty). Page mana untuk diusir ialah keputusan **penggantian page (page replacement)**, dan tersalah membuatnya merosakkan prestasi.

## Dasar penggantian

Optimum teori ialah mengusir page yang akan digunakan paling jauh pada masa hadapan (**OPT Bélády**) — mustahil, kerana anda tidak boleh melihat masa hadapan. Jadi kita menghampiri **LRU (least recently used — paling lama tidak digunakan)**: usir page yang paling lama tidak digunakan. LRU sebenar memerlukan cap masa pada setiap capaian (terlalu mahal), jadi kernel sebenar 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 keputusan seperti LRU pada kos O(1). Linux memperhalusnya lagi dengan **senarai LRU active/inactive**.

## Working set dan thrashing

**Working set** sesuatu process ialah set page yang ia gunakan secara aktif dalam satu tetingkap masa. Paging berfungsi baik *selagi gabungan working set muat dalam RAM*. Apabila tidak:

```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 ialah cenuram, bukan cerun: melepasi had sedikit sahaja dan throughput runtuh kerana hampir setiap capaian miss. Simptom: CPU hampir melahu tetapi I/O cakera tepu, dan latency meletup.

## Membaiki / mengelakkannya

- **Tambah RAM** atau **kurangkan beban** (kurang process serentak) supaya working set muat.
- Scheduler boleh **menggantung dan swap-out** keseluruhan process untuk mengecilkan permintaan (medium-term scheduling).
- **OOM killer** Linux ialah pilihan terakhir — bunuh satu process daripada thrash selama-lamanya.
- Perbaiki **locality** supaya working set itu sendiri lebih kecil.

## Mengapa ia penting

Ini mengikat keseluruhan cerita memori dan ialah soalan senior kegemaran kerana thrashing ialah mod kegagalan production sebenar: service yang elok pada N pengguna terjunam di N+1 apabila working set-nya melebihi RAM. Mengecam tandatangannya (paging berat, cakera tepu, CPU terhenti) dan mengetahui tuasnya (RAM, penyingkiran beban, locality — dan bahawa swap menukar kekurangan memori menjadi bencana latency) ialah perbezaan antara mendiagnosisnya dalam beberapa minit dan merenung kotak yang beku secara misteri.

Dasar penggantian

Working set dan thrashing

Membaiki / mengelakkannya

Mengapa ia penting

Soalan berkaitan