บทที่ 3 · Virtual Memory เน้นที่สุด
ชีท virtaul_memory(3_2) หน้า 85–91 (7 หน้า) — อาจารย์เปิดในคลิปนาที 17:00–23:05
ที่จะออกก็คือเรื่อง page replacement หลักๆ … ให้ลด page fault ให้น้อยที่สุด สิ่งที่คำนวณคือ page fault rate, page fault rate น้อยแปลว่าดี การทำงานระบบจะเร็ว
สิ่งที่จะออกก็คืออัลกอริทึมต่างๆ ในการสลับ ซึ่งสอนย้ำไปหลายรอบ ให้ไปเช็คดูทุกอัน ทำให้เข้าใจในทุกอัน แล้วก็ข้อดีข้อเสียของแต่ละอัน แล้วก็เวลาที่ anomaly จะเกิดขึ้นเมื่อไหร่ กับอันไหน
2) เรียงขั้นตอน page fault ได้
3) ทำตาราง FIFO, OPT, LRU, LFU, MFU ได้ถูกและเร็ว
4) คิด page fault rate
5) อธิบาย Belady's anomaly
6) บอกข้อดีข้อเสียของแต่ละอัลกอริทึม
3.1 Virtual memory คืออะไร
🤔 คืออะไร
Virtual memory = เทคนิคที่ทำให้โปรแกรมเห็นหน่วยความจำใหญ่กว่า RAM จริง โดยเก็บบาง page ไว้ใน RAM และที่เหลือพักไว้บนดิสก์ (backing store) ส่วน page table (ในชีทเรียกว่า memory map) จดว่า page ไหนอยู่ใน RAM หรืออยู่บนดิสก์
❓ ทำไมต้องมี
- RAM มีจำกัด แต่โปรแกรมใหญ่ขึ้นเรื่อยๆ และต้องรันหลายโปรแกรมพร้อมกัน
- overlay กับ dynamic loading ก็ยังมีข้อจำกัด (overlay ต้องให้คนเขียนโปรแกรมแบ่งเอง)
- โปรแกรมไม่ได้ใช้ทุกส่วนพร้อมกัน ช่วงหนึ่งใช้แค่บางส่วน (เรียกว่า locality) จึงไม่จำเป็นต้องให้ทั้งโปรแกรมอยู่ใน RAM
⚙️ ทำงานยังไง (ต่อยอดจาก paging ในบทที่ 2)
- โปรแกรมถูกแบ่งเป็น page เหมือน paging ปกติ
- ไม่ต้องโหลดทุก page เข้า RAM โหลดเฉพาะ page ที่ต้องใช้ ที่เหลืออยู่บนดิสก์
- page table บอกว่า page ไหนอยู่ใน RAM (frame ไหน) และ page ไหนยังอยู่บนดิสก์
- ถ้าโปรแกรมอ้าง page ที่ยังอยู่บนดิสก์ → OS ไปโหลดมาให้ (page fault ในหัวข้อ 3.3) ถ้า RAM เต็มก็เลือก page เก่าออก (page replacement ในหัวข้อ 3.5)
💡 เทียบให้เห็นภาพ: โต๊ะเรียนกับชั้นหนังสือ
โต๊ะ (= RAM) วางหนังสือได้ไม่กี่หน้า ส่วนชั้นหนังสือ (= ดิสก์) เก็บได้ทั้งเล่ม เราวางบนโต๊ะเฉพาะหน้าที่กำลังอ่าน พอโต๊ะเต็มก็เก็บบางหน้ากลับชั้นแล้วหยิบหน้าใหม่มาแทน ผลคือเหมือนมีโต๊ะใหญ่เท่าทั้งเล่ม
3.2 Demand paging และ valid–invalid bit ★
🤔 Demand paging คืออะไร
= "โหลดเมื่อต้องใช้" (demand = ความต้องการ) ตอนเริ่มรันไม่ต้องโหลดทุก page ให้โหลดทีละ page ตอนที่โปรแกรมอ้างถึงครั้งแรก ทำให้เริ่มโปรแกรมได้เร็วและประหยัด RAM
🤔 Valid–invalid bit คืออะไร
ในแต่ละช่องของ page table จะมีบิตเพิ่มมา 1 ตัว บอกว่าตอนนี้ page นั้นอยู่ใน RAM หรือไม่
- v (valid) = อยู่ใน RAM แล้ว ช่องนั้นมีเลข frame ให้ใช้ได้เลย
- i (invalid) = ไม่อยู่ใน RAM (ยังอยู่บนดิสก์) ถ้าอ้างถึงจะเกิด page fault
🔍 อ่านรูป 3.2.C
page frame bit ความหมาย 0 (A) 4 v A อยู่ใน RAM ที่ frame 4 1 (B) - i B อยู่บนดิสก์ → อ้างแล้ว page fault 2 (C) 6 v C อยู่ที่ frame 6 3 (D) - i 4 (E) - i 5 (F) 9 v F อยู่ที่ frame 9 6 (G) - i 7 (H) - i
สมมุติทีละ 3 frame … ถูกโยนไปในฮาร์ด ที่ยังไม่อยู่ในเมมโมรีก็จะเป็น invalid
3.3 ขั้นตอนเมื่อเกิด page fault ★
🤔 Page fault คืออะไร
คือเหตุการณ์ที่โปรแกรมอ้าง page ที่ไม่อยู่ใน RAM (bit = i) ซึ่งไม่ใช่ error แต่เป็นสัญญาณให้ OS ไปโหลด page นั้นมาให้ แล้วโปรแกรมก็ทำต่อได้ตามปกติ
💡 เทียบให้เห็นภาพ: ห้องสมุด
เราขอหนังสือเล่มหนึ่ง บรรณารักษ์ดูสมุดรายการแล้วพบว่าไม่ได้วางอยู่บนชั้นหน้าร้าน (invalid) จึงเดินไปหยิบจากคลังหลังร้าน (ดิสก์) มาวางบนชั้นว่าง แก้สมุดรายการว่าตอนนี้อยู่ชั้นไหน แล้วยื่นให้เรา
⚙️ แต่ละขั้นทำอะไร (รูป 3.2.D)
- Reference — CPU รันคำสั่งที่อ้าง page นั้น (เช่น
load M) - Trap — ฮาร์ดแวร์เห็นว่า bit = i จึงหยุดคำสั่งแล้วส่งเรื่องให้ OS (trap = ขัดจังหวะไปหา OS)
- Page is on backing store — OS ตรวจว่าเป็นการอ้างที่ถูกต้อง แล้วหาว่า page อยู่ตรงไหนบนดิสก์
- Bring in missing page — หา free frame แล้วโหลด page จากดิสก์มาใส่ (ถ้าไม่มี frame ว่าง ต้องใช้ page replacement ในหัวข้อ 3.5 เลือก page ออกก่อน)
- Reset page table — เขียนเลข frame ใหม่ลง page table และเปลี่ยน bit เป็น v
- Restart instruction — สั่งคำสั่งเดิมใหม่อีกครั้ง คราวนี้ bit = v จึงอ่านได้ปกติ
เพราะการอ่านดิสก์ช้ามาก (ช้ากว่า RAM เป็นแสนเท่า) ยิ่ง page fault น้อย ระบบยิ่งเร็ว นี่คือเหตุผลที่อาจารย์เน้นการคำนวณ page fault rate
เกิด page fault OS จะดัก แล้วก็ทำการสั่ง เพราะว่า OS เป็นคนจัดการ virtual memory ก็ต้องรู้ว่าตำแหน่งจริงมันอยู่ที่ไหน ก็จะบอกว่าให้ไปโหลดตำแหน่งจริงมา แล้วมาเก็บใน RAM ใหม่ แล้ว loop ถัดมา CPU จะพยายาม request ใหม่ ก็จะไม่ fault แล้ว จะเป็น valid
① reference อ้างเพจ (เช่นคำสั่ง load M) ② trap page table เป็น i → trap ไปหา OS ③ page is on backing store OS หาว่าเพจอยู่ตรงไหนบนดิสก์ ④ bring in missing page โหลดเพจเข้า free frame ⑤ reset page table ใส่เลขเฟรมใหม่ และเปลี่ยน bit เป็น v ⑥ restart instruction รันคำสั่งเดิมอีกครั้ง (คราวนี้ valid)
3.4 Reference string
🤔 คืออะไร
Reference string = ลำดับหมายเลข page ที่โปรแกรมอ้างถึงตามเวลา เช่น 7 0 1 2 0 3 … แปลว่า อ้าง page 7 ก่อน แล้ว page 0 แล้ว page 1 …
❓ ทำไมต้องมี
เพื่อใช้จำลองว่าแต่ละอัลกอริทึม page replacement จะเกิด fault กี่ครั้ง โดยไม่ต้องสนใจ address ละเอียด สนใจแค่ว่าอ้าง page ไหน
⚙️ ถ้าโจทย์ให้มาเป็น address (ตัวอย่างในชีท: 100 byte/page)
- หาเลข page ของแต่ละ address: page = address div 100 เช่น 0432 → 4, 0612 → 6
- ยุบตัวที่ซ้ำติดกัน เพราะถ้าอ้าง page เดิมซ้ำทันที page นั้นอยู่ใน RAM แน่นอน ไม่มีทาง fault
address : 0100 0432 0101 0612 0102 0103 0104 0101 0611 0102 0103 page : 1 4 1 6 1 1 1 1 6 1 1 ยุบซ้ำ : 1 4 1 6 1 6 1 reference string = 1, 4, 1, 6, 1, 6, 1
3.5 Page replacement ★★★
🤔 คืออะไร
process แต่ละตัวได้ frame (ช่องใน RAM) จำนวนจำกัด เช่น 3 frames ถ้าเกิด page fault ตอนที่ frame เต็มแล้ว ต้องเลือก page หนึ่งในนั้นออก (เรียกว่า victim) เพื่อเอา page ใหม่เข้ามาแทน Page replacement algorithm คือกติกาการเลือก victim
❓ ทำไมสำคัญ
ถ้าเลือกผิด (เอา page ที่จะใช้อีกเร็วๆ นี้ออก) ก็จะ fault บ่อย ระบบช้า เป้าหมายจึงเป็น page fault ให้น้อยที่สุด
⚙️ อ่าน/เขียนตารางแบบชีทยังไง
- แถวบนสุด = reference string (การอ้างแต่ละครั้งเรียงตามเวลา)
- แถว F1, F2, F3 = ข้างในแต่ละ frame หลังจากอ้างครั้งนั้นแล้ว
- ใต้คอลัมน์: F = page fault (page ไม่อยู่ใน frame ต้องโหลด) ส่วนช่องว่าง = hit (อยู่แล้ว)
- ตอนเริ่ม frame ว่าง การอ้างครั้งแรกๆ จึงเป็น fault แล้วใส่ลงช่องว่างได้เลย การเลือก victim เกิดเฉพาะตอน frame เต็มแล้ว
🔍 เห็นความต่างใน 1 ตัวอย่าง: 3 frames, reference string 1 2 3 1 4 3 2
อ้าง 1, 2, 3 → fault ทั้งสามครั้ง ใส่ลงช่องว่าง · อ้าง 1 → hit · อ้าง 4 → fault และ frame เต็ม (มี 1, 2, 3) จะเอาใครออก?
| อัลกอริทึม | คิดยังไง | เอาออก |
|---|---|---|
| FIFO | 1 เข้ามาก่อนสุด (ตำแหน่งที่ 1) | 1 |
| OPT | มองอนาคต: 3 ใช้อีกที่ตำแหน่ง 6, 2 ใช้อีกที่ 7, ส่วน 1 ไม่ใช้อีกเลย | 1 |
| LRU | มองอดีต: 1 เพิ่งใช้ที่ตำแหน่ง 4, 3 ใช้ที่ 3, 2 ใช้ที่ 2 → 2 ไม่ได้ใช้นานสุด | 2 |
| LFU | นับครั้ง: 1 = 2 ครั้ง, 2 = 1, 3 = 1 → น้อยสุดเสมอกัน (2 กับ 3) ใช้ FIFO: 2 เข้ามาก่อน | 2 |
| MFU | นับครั้ง: 1 = 2 ครั้ง มากที่สุด | 1 |
สังเกตว่า FIFO สนใจแค่ใครเข้ามาก่อน ไม่สนว่า 1 เพิ่งถูกใช้ ส่วน LRU เห็นว่า 1 เพิ่งถูกใช้จึงเก็บไว้
สรุปคือเมื่อเกิด page fault แล้วเฟรมเต็ม ต้องเลือกเพจหนึ่งออก (victim) อัลกอริทึมต่างกันแค่ "เลือกใครออก"
2) ถ้ามีเพจที่เข้าเงื่อนไขให้เอาออกมากกว่า 1 เพจ → ใช้ FIFO ตัดสิน (เอาตัวที่เข้ามาก่อนออก)
3) แบบ counting (LFU/MFU): เพจที่ถูกเอาออกแล้วกลับเข้ามาใหม่ → เริ่มนับ 1 ใหม่
4) เขียนตารางแบบชีท: แถว = เฟรม, คอลัมน์ = การอ้างแต่ละครั้ง, ใส่ F ใต้คอลัมน์ที่ fault
FIFO — First-In, First-Out
หลักการ: เพจที่เข้ามาก่อนออกก่อน (เหมือนคิว)
ต้องจดอะไร: ลำดับที่เพจเข้ามา (ใช้ซ้ำ ไม่ทำให้ลำดับเปลี่ยน)
เคล็ดลับ: เฟรมที่ถูกแทนจะวนลงไปทีละแถว F1 → F2 → F3 → F1 … เสมอ
OPT — Optimal
หลักการ (อาจารย์ไฮไลต์ไว้): เพจที่จะยังไม่ถูกใช้เป็นเวลานานที่สุดในอนาคต ให้เอาออกก่อน
ต้องทำอะไร: มองไปข้างหน้าใน reference string ว่าแต่ละเพจในเฟรมจะถูกใช้อีกเมื่อไร ตัวที่ไกลที่สุดหรือไม่ใช้อีกเลย = ออก (ถ้าไม่ใช้อีกเลยหลายตัว ใช้ FIFO)
LRU — Least Recently Used
หลักการ: เพจที่ไม่ได้ถูกใช้นานที่สุด (มองย้อนอดีต) ออกก่อน
ต่างจาก FIFO: ถ้าเพจที่อยู่มานานถูกใช้ซ้ำ จะถือว่า "เพิ่งใช้" (ชีทเขียนว่า "แสดงว่าเพจดังกล่าวนี้ยังถือว่าถูกใช้งานไม่นาน")
เคล็ดลับ: มองย้อนจากคอลัมน์ปัจจุบันไปทางซ้าย เพจในเฟรมตัวไหนเจอช้าที่สุด = ออก
LFU / MFU — Counting
LFU (Least Frequently Used): เพจที่ถูกใช้น้อยครั้งที่สุดออก
MFU (Most Frequently Used): เพจที่ถูกใช้มากครั้งที่สุดออก (เหตุผล: ตัวที่นับน้อยน่าจะเพิ่งเข้ามาและยังจะใช้อีก)
ต้องจด: จำนวนครั้งของแต่ละเพจตั้งแต่เข้ามารอบนี้ ถ้าถูกเอาออกแล้วกลับเข้ามาใหม่ ให้เริ่มนับ 1
counting หรือนับจำนวน นับความถี่ในการใช้งานในอดีต … least frequently used กับ most frequently used แต่ละอันเป็นยังไง ทบทวนการบ้าน ก็จะไม่สอนซ้ำ
🕹 ลองเองทีละขั้น (เริ่มจากโจทย์การบ้าน)
กด ถัดไป ▶ ทีละช่องแล้วอ่านเหตุผล จากนั้นเปลี่ยนเป็นโหมด "ฝึกเอง" ซึ่งทุกครั้งที่ต้องเอาเพจออก ระบบจะให้เราเลือกเอง เป็นวิธีฝึกที่ดีที่สุดก่อนสอบ
วิธีทำในข้อสอบให้เร็วและไม่พลาด
2) FIFO: เขียนลำดับคิวไว้ข้างๆ (เช่น
[2,3,1] แล้วตัดตัวหน้าทิ้งทุกครั้งที่แทน)
3) LRU: ตอนต้องแทน ให้มองย้อนไปทางซ้าย แล้วตัดเพจที่เจอทีละตัว ตัวสุดท้ายที่เหลือ = ออก
4) OPT: มองไปทางขวา ตัดเพจที่เจอทีละตัว ตัวสุดท้ายที่เหลือ (หรือตัวที่ไม่เจอเลย) = ออก
5) LFU/MFU: เขียนตัวเลขนับเล็กๆ ใต้ตาราง และรีเซ็ตเมื่อเพจถูกเอาออก
6) นับ F แล้วเขียน page fault rate = F ÷ จำนวนการอ้าง เป็น %
7) ตรวจเอง: OPT ต้องน้อยที่สุดเสมอ ถ้า LRU ได้น้อยกว่า OPT แปลว่าผิดแน่
3.6 Page fault rate ★
สิ่งที่คำนวณคือ page fault rate, page fault rate น้อยแปลว่าดี การทำงานระบบจะเร็ว
page fault rate = จำนวน page fault ÷ จำนวนการอ้างทั้งหมด ลายมืออาจารย์ในชีท (หน้า 88–89): FIFO 3 เฟรม = 15/20 = 75% Belady 3 เฟรม = 9/12 = 75% (เขียนว่า 9/(9+3): fault 9 + hit 3) Belady 4 เฟรม = 10/12 = 83.3%
3.7 Belady's anomaly ★
🤔 คืออะไร
ปกติเราคาดว่าให้ frame มากขึ้น → fault น้อยลง (โต๊ะใหญ่ขึ้น ก็ไม่ต้องเดินไปหยิบหนังสือบ่อย) แต่ Belady's anomaly คือกรณีแปลกที่เพิ่ม frame แล้ว fault กลับเพิ่มขึ้น ซึ่งเกิดกับ FIFO
❓ ทำไมเกิดกับ FIFO
FIFO เลือก victim จาก "ใครเข้ามาก่อน" ซึ่งไม่เกี่ยวกับว่า page ไหนกำลังถูกใช้ พอจำนวน frame เปลี่ยน ลำดับคิวก็เปลี่ยนไปทั้งชุด บางครั้งจึงไล่ page ที่กำลังจะถูกใช้ออกพอดี ส่วน LRU กับ OPT เลือกจากการใช้งานจริง (อดีต/อนาคต) จึงไม่เกิด
Belady's anomaly = เพิ่มจำนวนเฟรมแล้ว page fault กลับเพิ่มขึ้น แทนที่จะลดลง ซึ่งเกิดกับ FIFO
ตัวอย่างชีท: 1 2 3 4 1 2 5 1 2 3 4 5 ใช้ 3 เฟรม = 9 faults แต่ 4 เฟรม = 10 faults (รูป 3.2.F, 3.2.G)
ลองเองในเครื่องมือด้านบน: เลือก preset "Belady — 3 เฟรม" แล้วเปลี่ยนเป็น 4 เฟรม
3.8 ข้อดี / ข้อเสียของแต่ละอัลกอริทึม ★
| Algorithm | หลักการ | ข้อดี | ข้อเสีย | Belady? |
|---|---|---|---|---|
| FIFO | เข้าก่อน ออกก่อน | ง่ายที่สุด overhead ต่ำ ใช้แค่คิว | อาจเอาเพจที่ยังใช้บ่อยออก ทำให้ fault มาก | เกิด |
| OPT | ไม่ใช้นานสุดในอนาคต | fault น้อยที่สุดเท่าที่เป็นไปได้ | ใช้จริงไม่ได้ เพราะต้องรู้อนาคต จึงใช้เป็นเกณฑ์เทียบ | ไม่เกิด |
| LRU | ไม่ได้ใช้นานสุด (อดีต) | ใกล้เคียง OPT ใช้หลัก locality | ต้องจดเวลาทุกครั้งที่อ้าง (counter/stack) จึงต้องมีฮาร์ดแวร์ช่วยและ overhead สูง | ไม่เกิด |
| LFU | ใช้น้อยครั้งสุด | เก็บเพจที่ใช้บ่อยไว้ | เพจที่ใช้หนักช่วงแรกค้างอยู่นานแม้เลิกใช้แล้ว เพจใหม่ถูกไล่ง่าย และต้องมีตัวนับ | อาจเกิด |
| MFU | ใช้มากครั้งสุด | เหมาะกับงานที่ใช้เพจหนักช่วงหนึ่งแล้วเลิกใช้ | มักไล่เพจที่ยังใช้หนักออก ผลมักแย่ และต้องมีตัวนับ | อาจเกิด |
3.9 โจทย์จากชีทและการบ้าน
ตัวอย่างที่ 3.2.ก (หน้า 91)
3 เฟรม, 2 3 2 1 5 2 4 5 3 2 5 2 → FIFO = 9, LRU = 7, OPT = 6 (เลือก preset "ตัวอย่าง 3.2.ก" ในเครื่องมือด้านบนเพื่อดูทีละขั้น)
การบ้าน (Classroom)
2 3 2 1 5 2 4 5 3 2 5 2 1 4 3 5 2 4 1 3คำตอบที่ถูก: FIFO = 17, OPT = 10, LRU = 15, LFU = 12 (MFU = 17) ซึ่งตรงกับที่ส่งไปทุกข้อ
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 3 เฟรม ใช้ FIFO ได้กี่ fault🎲 ฝึกไม่จำกัด
3.10 เสริมนอกชีท: EAT, thrashing, working set ข้ามได้
⏭ ข้ามได้ — ไม่อยู่ในชีทอาจารย์ และอาจารย์ไม่ได้พูดถึง (กดเพื่อเปิดดู)
- EAT ของ demand paging = (1 − p) × memory access + p × page-fault service time เช่น 200 ns, 8 ms, p = 1/1000 → ≈ 8.2 µs (ช้าลงราว 40 เท่า) page fault rate จึงต้องต่ำมาก
- Thrashing = โปรเซสใช้เวลาไปกับการสลับเพจเข้าออกมากกว่าทำงานจริง (มีเฟรมไม่พอ) ทำให้ CPU utilization ตก แล้ว OS ก็เพิ่มโปรเซสเข้าไปอีก ยิ่งแย่ลง
- Working set = ชุดเพจที่ถูกอ้างในหน้าต่าง Δ ล่าสุด ถ้าผลรวม working set ของทุกโปรเซส (D) มากกว่าจำนวนเฟรม (m) → thrashing ต้อง suspend บางโปรเซส
สรุปบทนี้ใน 1 นาที
- Virtual memory = logical ใหญ่กว่า physical โดยใช้ดิสก์ · demand paging · v/i bit
- Page fault: อ้าง → trap → หาบนดิสก์ → โหลด → แก้ page table → รันใหม่ (OS จัดการ)
- FIFO เข้าก่อนออกก่อน · OPT ไกลสุดในอนาคต · LRU นานสุดในอดีต · LFU/MFU นับครั้ง (รีเซ็ตเมื่อออก) · เสมอกันใช้ FIFO
- page fault rate = fault ÷ การอ้างทั้งหมด
- Belady: FIFO เพิ่มเฟรมแล้ว fault เพิ่ม (1 2 3 4 1 2 5 1 2 3 4 5: 9 → 10)