Page replacement: FIFO, MIN, LRU, LFU

นึกภาพก่อน

โต๊ะวางหนังสือได้สี่เล่มและเต็มแล้ว ต้องหยิบเล่มที่ห้ามาใช้ จะเก็บเล่มไหนคืนชั้น

• เล่มที่วางบนโต๊ะมา นานที่สุด? (อาจเป็นเล่มที่ใช้ทุกห้านาทีก็ได้)
• เล่มที่ จะไม่ได้ใช้ไปอีกนานที่สุด? (ดีที่สุด แต่ต้องรู้อนาคต)
• เล่มที่ ไม่ได้แตะมานานที่สุด? (เดาอนาคตจากอดีต)
• เล่มที่ ใช้น้อยครั้งที่สุด?

สี่ข้อนี้คือ FIFO, MIN, LRU และ LFU

Replacement policy

เมื่อเกิด cache miss และ cache เต็ม ต้องเลือกรายการที่จะถูกแทน (โดยถือว่ารายการใหม่มีโอกาสถูกใช้ในอนาคตอันใกล้มากกว่า)

เป้าหมายของ policy:

• ลด cache miss — ปรับปรุง performance ในกรณีทั่วไป
• ลดโอกาสที่ performance จะแย่มาก ในบางกรณี

(ใน direct mapped cache ไม่มีปัญหานี้ เพราะแต่ละรายการมีที่ลงได้ที่เดียว ไม่ต้องเลือก)

ทำไม MIN optimal

สไลด์ให้เหตุผลแบบ exchange: ถ้าเลือกแทนรายการที่จะถูกใช้ เร็วกว่า ก็จะเกิด cache miss เร็วกว่า การเลือกตัวที่จะถูกใช้ไกลที่สุดจึงเลื่อน miss ครั้งถัดไปออกไปได้ไกลที่สุด MIN ใช้จริงไม่ได้เพราะต้องรู้อนาคต แต่ใช้เป็นมาตรฐานเทียบ policy อื่น

ทำไม LRU ประมาณ MIN ได้

เพราะ locality: page ที่เพิ่งถูกใช้มีแนวโน้มจะถูกใช้อีกเร็ว ๆ นี้ และ page ที่ไม่ถูกแตะมานานมีแนวโน้มจะไม่ถูกใช้อีกนาน อดีตจึงเป็นตัวทำนายอนาคตที่ใช้ได้ สำหรับโปรแกรมที่มี spatial และ temporal locality

วิธีนับ miss ด้วยมือ

1. เขียน reference string เป็นหัวคอลัมน์ และมีแถวตามจำนวนช่อง (frame)
2. ไล่ทีละ reference: ถ้า page อยู่ในช่องใดอยู่แล้ว → hit (ไม่เปลี่ยนเนื้อหาช่อง)
3. ถ้าไม่อยู่ → miss: ถ้ามีช่องว่างให้ใส่ช่องว่าง ไม่เช่นนั้นเลือกตัวออกตาม policy
4. นับ miss ทั้งหมด (รวม miss ตอนเติมช่องว่างด้วย)

สิ่งที่ต้องจำแยกแต่ละ policy:

ตัวอย่างไล่ทีละขั้น

FIFO กับการไล่ memory (สไลด์ p.22)

reference A B C D E A B C D E A B C D E กับ 4 ช่อง: หลัง A B C D เต็ม, E แทน A (เก่าสุด), แล้ว A กลับมาแทน B, B แทน C, … page ที่ต้องการถัดไปคือตัวที่เพิ่งถูกไล่ออกเสมอ → miss ทุกครั้ง (15 จาก 15)

กรณีแย่ที่สุดของ FIFO คือเมื่อโปรแกรมไล่ผ่าน memory ที่ใหญ่กว่า cache

LRU กับสตริงนี้ก็ miss ทุกครั้งเช่นกัน (ตัวที่ไม่ถูกใช้นานสุดคือตัวที่จะถูกใช้ถัดไปพอดี) ส่วน MIN miss เพียง 7 ครั้ง (สไลด์ p.24) ตัวอย่างนี้แสดงว่า LRU เป็นเพียงการประมาณ: กับ workload ที่ไม่มี locality อดีตทำนายอนาคตไม่ได้

เทียบ LRU, FIFO, MIN (สไลด์ p.25)

reference A B A C B D A D E D A E B A C กับ 4 ช่อง (M = miss, ✓ = hit)

FIFO — 8 miss

ที่ E (ตำแหน่ง 9): FIFO แทน A เพราะเข้ามาก่อนสุด ทั้งที่ A เพิ่งถูกใช้และกำลังจะถูกใช้อีก → A miss ในอีกสองก้าว แล้วไล่ B ออก → B miss ต่ออีก

LRU — 6 miss

ที่ E: ใช้ล่าสุด A ที่ตำแหน่ง 7, B ที่ 5, C ที่ 4, D ที่ 8 → C ไม่ถูกใช้นานสุด จึงแทน C ที่ C ตัวสุดท้าย: ใช้ล่าสุด A ที่ 14, B ที่ 13, E ที่ 12, D ที่ 10 → แทน D

MIN — 6 miss

ที่ E: มองไปข้างหน้า A ถูกใช้ที่ตำแหน่ง 11, B ที่ 13, D ที่ 10, C ที่ 15 → C ไกลสุด จึงแทน C (เลือกเหมือน LRU) ที่ C ตัวสุดท้าย: ไม่มีตัวใดถูกใช้อีก แทนตัวใดก็ได้ → รวม 6 miss เท่ากับ LRU

กับสตริงนี้ LRU ทำได้ดีเท่า MIN เพราะสตริงมี locality (A, B, D ถูกใช้ซ้ำใกล้ ๆ กัน) ส่วน FIFO แย่กว่า

Belady's anomaly

สามัญสำนึกบอกว่า memory มากขึ้น miss ต้องไม่เพิ่ม FIFO ไม่เป็นอย่างนั้นเสมอ

reference A B C D A B E A B C D E

FIFO 3 ช่อง — 9 miss

FIFO 4 ช่อง — 10 miss

เพิ่มจาก 3 เป็น 4 ช่อง miss เพิ่ม จาก 9 เป็น 10

เกิดอะไรขึ้น: กับ 4 ช่อง A และ B hit ที่ตำแหน่ง 5–6 แต่ FIFO ไม่สนใจ hit ลำดับเข้ายังเป็น A, B, C, D พอ E มาจึงไล่ A ออก แล้ว A ที่ต้องใช้ถัดไปก็ไล่ B ออก เป็นลูกโซ่ miss 6 ครั้งติด กับ 3 ช่อง ลำดับการไล่บังเอิญลงจังหวะที่ A และ B ยังอยู่ตอนถูกใช้ที่ตำแหน่ง 8–9

LRU และ MIN ไม่มีปัญหานี้: กับสตริงเดียวกัน LRU ได้ 10 miss (3 ช่อง) และ 8 miss (4 ช่อง) ส่วน MIN ได้ 7 และ 6

Recap ตามสไลด์

• MIN optimal — แทน page หรือ cache entry ที่จะถูกใช้ไกลที่สุดในอนาคต
• LRU เป็นการประมาณ MIN — สำหรับโปรแกรมที่มี spatial และ temporal locality
• Clock / Nth Chance เป็นการประมาณ LRU — จัด page เข้ากลุ่ม "ไม่ได้ใช้เมื่อเร็ว ๆ นี้"

จุดที่มักพลาด

1. ลืมนับ miss ตอนเติมช่องว่าง

การอ้างถึงครั้งแรกของทุก page เป็น miss เสมอ

2. อัปเดตลำดับของ FIFO เมื่อ hit

FIFO ดูแค่เวลาที่ เข้ามา hit ไม่เปลี่ยนอะไร ถ้าอัปเดตจะกลายเป็น LRU

3. LRU: ดูเวลาที่เข้ามาแทนเวลาที่ใช้ล่าสุด

ต้องมองย้อนใน reference string หาตำแหน่งล่าสุดที่แต่ละ page ถูกอ้างถึง

4. MIN: มองย้อนหลังแทนมองไปข้างหน้า

MIN ดูอนาคต LRU ดูอดีต

5. คิดว่า frame มากขึ้นแล้ว miss ไม่เพิ่มกับทุก policy

FIFO มี Belady's anomaly

6. คิดว่า LRU ดีเท่า MIN เสมอ

เป็นการประมาณ และแย่ได้เท่า FIFO เมื่อ workload ไม่มี locality (ตัวอย่าง sequential scan)

ที่มา: 08-Virtual memory_v3.pdf หน้า 20–27