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 จริง ๆ ต้องมี timestamp ทุกครั้งที่เข้าถึง (แพงเกินไป) kernel จริงจึงใช้ **อัลกอริทึม 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 ปรับแต่งเพิ่มด้วย **รายการ LRU แบบ active/inactive**

## working set และ thrashing

**working set** ของโปรเซสคือชุดของเพจที่มันใช้อย่างแข็งขันภายในหน้าต่างเวลาหนึ่ง Paging ทำงานได้ดี *ตราบเท่าที่ผลรวมของ working set ทั้งหมดพอดีกับ 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 ก็พังทลาย เพราะแทบทุกการเข้าถึงกลายเป็น miss อาการ: CPU เกือบว่าง แต่ I/O ดิสก์อิ่มตัว และ latency ระเบิด

## แก้ / หลีกเลี่ยงมัน

- **เพิ่ม RAM** หรือ **ลดโหลด** (โปรเซสพร้อมกันน้อยลง) เพื่อให้ working set พอดี
- scheduler สามารถ **พักและ swap-out** ทั้งโปรเซสเพื่อลดความต้องการ (medium-term scheduling)
- **OOM killer** ของ Linux เป็นทางเลือกสุดท้าย — ฆ่าโปรเซสหนึ่งดีกว่า thrash ตลอดกาล
- ปรับปรุง **locality** เพื่อให้ working set เล็กลงในตัวมันเอง

## ทำไมจึงสำคัญ

สิ่งนี้ห่อเรื่องราวหน่วยความจำทั้งหมดเข้าด้วยกัน และเป็นคำถาม senior ที่ถูกใจ เพราะ thrashing เป็นโหมดความล้มเหลวจริงใน production: เซอร์วิสที่ปกติดีที่ N ผู้ใช้ ตกหน้าผาที่ N+1 เมื่อ working set ของมันเกิน RAM การจดจำลายเซ็น (paging หนัก, ดิสก์อิ่มตัว, CPU ค้าง) และการรู้คันโยก (RAM, การทิ้งโหลด, locality — และรู้ว่า swap เปลี่ยนการขาดหน่วยความจำให้เป็นหายนะด้าน latency) คือความต่างระหว่างการวินิจฉัยได้ในไม่กี่นาทีกับการนั่งจ้องเครื่องที่ค้างอย่างลึกลับ

นโยบายการแทนที่

working set และ thrashing

แก้ / หลีกเลี่ยงมัน

ทำไมจึงสำคัญ

คำถามที่เกี่ยวข้อง