Thay thế trang hoạt động ra sao, và điều gì gây ra thrashing?

Question

IT Interview Practice · Accepted Answer

Khi RAM vật lý đầy nhưng các process vẫn cần thêm trang, OS phải **trục xuất (evict)** một trang đang cư trú để lấy chỗ — ghi nó ra **swap** (đĩa) nếu nó bẩn (dirty). Chọn trang nào để trục xuất là quyết định **thay thế trang (page replacement)**, và làm sai sẽ phá nát hiệu năng.

## Các chính sách thay thế

Tối ưu lý thuyết là trục xuất trang sẽ được dùng xa nhất trong tương lai (**OPT của Bélády**) — bất khả thi, vì bạn không thấy được tương lai. Nên ta xấp xỉ **LRU (least recently used — ít dùng gần đây nhất)**: trục xuất trang lâu nhất chưa được dùng. LRU thật cần một dấu thời gian ở mỗi lần truy cập (quá tốn kém), nên các kernel thực dùng **thuật toán 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 cho kết quả gần như LRU với chi phí O(1). Linux tinh chỉnh thêm bằng các **danh sách LRU active/inactive**.

## Working set và thrashing

**Working set** của một process là tập các trang nó chủ động dùng trong một cửa sổ thời gian. Paging hoạt động ổn *miễn là tổng các working set vừa với RAM*. Khi không vừa:

```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 là một vách đá, không phải một con dốc: chỉ cần vượt giới hạn một chút là throughput sụp đổ vì gần như mọi lần truy cập đều miss. Triệu chứng: CPU gần như rảnh nhưng I/O đĩa bão hòa, và latency bùng nổ.

## Sửa / tránh nó

- **Thêm RAM** hoặc **giảm tải** (ít process đồng thời hơn) để các working set vừa vặn.
- Scheduler có thể **treo và swap-out** cả process để thu nhỏ nhu cầu (medium-term scheduling).
- **OOM killer** của Linux là phương án cuối — giết một process còn hơn thrash mãi mãi.
- Cải thiện **locality** để bản thân working set nhỏ lại.

## Tại sao điều này quan trọng

Điều này gói lại toàn bộ câu chuyện bộ nhớ và là câu hỏi senior được ưa thích vì thrashing là một chế độ hỏng thực sự trong production: một service ổn ở N người dùng rơi khỏi vách đá ở N+1 khi working set của nó vượt RAM. Nhận ra dấu hiệu (paging nặng, đĩa bão hòa, CPU đình trệ) và biết các đòn bẩy (RAM, giảm tải, locality — và rằng swap biến một thiếu hụt bộ nhớ thành thảm họa latency) là khác biệt giữa chẩn đoán ra trong vài phút và ngồi nhìn một cái máy đơ một cách bí ẩn.

Các chính sách thay thế

Working set và thrashing

Sửa / tránh nó

Tại sao điều này quan trọng

Câu hỏi liên quan