หน่วยความจำเสมือน ( Virtual Memory )

หน่วยความจำเสมือน

(VIRTUAL MEMORY)

ความเป็นมา (Background)

เราจำเป็นต้องมีวิธีการจัดการหน่วยความจำหลักแบบต่าง ๆ ข้อจำกัดที่ว่ากระบวนการทั้งตัวจะต้องอยู่ในหน่วยความจำจริง ก่อนที่จะเริ่มทำงานได้ ซึ่งข้อจำกัดนี้ เป็นสิ่งจำเป็นและสมเหตุสมผล แต่ทำให้ขนาดของโปรแกรมถูกจำกัดด้วยขนาดของหน่วยความจำหลัก

ถ้าเราตรวจดูโปรแกรมทั่วไปจะพบว่า หลายส่วนของโปรแกรมไม่จำเป็นต้องใช้ เช่น

• มักมีส่วนของโปรแกรมสำหรับจัดการข้อผิดพลาดพิเศษ หรือไม่ปกติรวมอยู่ด้วย เนื่องจากข้อผิดพลาดนี้เกิดได้ยาก ดังนั้นโปรแกรมส่วนนี้จึงแทบจะไม่เคยได้ใช้เลย
• โครงสร้างข้อมูล เช่น แถวลำดับ (array) , ตารางหรือแถวคอย ส่วนใหญ่จะมีการกันเนื้อที่ไว้ขนาดใหญ่กว่าที่ใช้จริง เช่น อาจประกาศแถวลำดับเป็น 100 x 100 ทั้ง ๆ ที่ปกติจะใช้เพียง 10 x 10 ตารางสัญลักษณ์ในตัวแปรภาษา assembly อาจเผื่อไว้สำหรับตัวแปรถึง 3000 ตัว แต่โปรแกรมภาษา assembly ส่วนใหญ่ใช้ตัวแปรไม่เกิน 200 ตัวเท่านั้น
• โปรแกรมย่อย คุณสมบัติหรือ หน้าที่บางอย่างของโปรแกรมอาจใช้น้อยมาก เช่น โปรแกรมย่อยในคอมพิวเตอร์ของรัฐบาลสหรัฐที่เกี่ยวกับงานด้านงบประมาณย่อมไม่จำเป็นต้องใช้เลยในระหว่างปี

และถึงแม้ว่ากรณีที่กล่าวมาโปรแกรมทั้งโปรแกรมอาจเป็นสิ่งจำเป็น แต่ก็ไม่จำเป็นต้องใช้ในเวลาเดียวกัน (เห็นได้จากกรณีการแบ่งส่วนของโปรแกรม (overlays))

การที่สามารถให้โปรแกรมทำงานได้ โดยมีเพียงบางส่วนอยู่ในหน่วยความจำหลัก มีประโยชน์หลายประการดังนี้

• ขนาดของโปรแกรมไม่ได้ถูกจำกัดด้วยขนาดของหน่วยความจำหลัก ผู้เขียนโปรแกรมอาจเขียนโปรแกรมที่ใช้หน่วยความจำเสมือนซึ่งมีขนาดใหญ่มาก ๆ ได้ ทำให้การเขียนโปรแกรมง่ายขึ้น
• ผู้ใช้แต่ละคนจะใช้หน่วยความจำจริงสำหรับโปรแกรมของตนลดลง ดังนั้นเราสามารถเพิ่มจำนวนผู้ใช้หรือกระบวนการได้มากขึ้นในระบบ ซึ่งจะช่วยให้ประสิทธิผลการใช้งานหน่วยประมวลผลกลางดีขึ้น และมีอัตรางานเสร็จสูงขึ้นด้วย
• การบรรจุโปรแกรมลงหน่วยความจำทำได้เร็วขึ้น (เนื่องจากอ่านเข้ามาเพียงบางส่วน) การย้ายโปรแกรมผู้ใช้ เข้า-ออก ไปพักชั่วคราว ก็ทำได้เร็วขึ้น เช่นกัน ทำให้ผู้ใช้ทำงานได้เร็วขึ้นกว่าเดิม

ดังนั้น การที่สามารถให้โปรแกรมทำงานได้ โดยโปรแกรมทั้งตัวไม่ได้อยู่ในหน่วยความจำหลักเป็นประโยชน์ทั้งต่อระบบเอง และผู้ใช้แต่ละคน

หน่วยความจำเสมือนเป็นระบบที่แยกหน่วยความจำทางตรรกะ (ผู้ใช้มองเห็น) ออกจากหน่วยความจำจริง (ทางกายภาพ) การทำเช่นนี้ทำให้หน่วยความจำทางตรรกะ มีขนาดได้ใหญ่มากๆ ทำให้ผู้เขียนโปรแกรมทำงานได้ดีขึ้น เพราะไม่ต้องสนใจขนาดของหน่วยความจำอีกต่อไป ข้อดีข้อนี้ เกือบจะทำให้วิธีการแบ่งส่วน (overlays) หมดความหมายไปเลย

 

การจัดสรรหน้าตามคำร้องขอ (Demand Paging)

การจัดสรรหน้าตามคำร้องขอ ก็เหมือนกับ ระบบแบ่งเป็นหน้า (Paging System) ที่มีการสับเปลี่ยนหน้า (Swapping)  เราเก็บกระบวนการไว้ในหน่วยความจำสำรอง (ปกติใช้จานบันทึก) เมื่อต้องการให้กระบวนการทำงาน ระบบก็จะย้ายกระบวนการเข้ามาในหน่วยความจำหลัก แต่แทนที่จะย้ายเข้ามาทั้งตัว เราใช้ Lazy Swapper ซึ่งจะย้ายเฉพาะเมื่อมีการร้องขอและย้ายเข้ามาเฉพาะหน้าที่ร้องขอเท่านั้น กระบวนการหนึ่ง ๆ จะถูกแบ่งเป็นหน้า ๆ แทนที่จะเป็นเนื้อที่ติดต่อกันหมด ปกติตัวย้ายกระบวนการ (Swapper) จะย้ายเข้ามาทั้งกระบวนการ เราจึงเรียกชื่อใหม่ว่า “ตัวสับเปลี่ยนหน้า” (Pager) ซึ่งย้ายเข้ามาทีละหน้า

  แสดงการย้ายหน้าจากหน่วยความจำไปสู่จานบันทึก

เมื่อต้องการย้ายกระบวนการเข้ามาในระบบ (หน่วยความจำหลัก) ตัวสับเปลี่ยนหน้า (Pager) จะเดาว่าต้องการย้ายหน้าใดเข้ามา และย้ายเฉพาะหน้านั้น ๆ เข้ามาในหน่วยความจำหลัก ทำให้ใช้เนื้อที่เพียงจำนวนน้อย และเสียเวลาย้ายน้อยลงกว่าการย้ายเข้ามาทั้งหมด

วิธีนี้ต้องมีอุปกรณ์ช่วย (ฮาร์ดแวร์) คือ เพิ่ม บิตสถาน (Valid-invalid Bit) อีก หนึ่งบิตต่อช่องในตารางเลขหน้า ถ้าบิตสถานะมีค่าเป็น ใช้ได้ (valid) แสดงว่าหน้านั้นอยู่ในหน่วยความจำหลัก ถ้าบิตสถานมีค่าเป็น ใช้ไม่ได้ (invalid) แสดงว่าหน้านั้นอยู่ในจานบันทึก การใช้ตารางเลขหน้าก็จะเหมือนในระบบแบ่งเป็นหน้า (Paging) คือ ตารางเลขหน้าจะต้องถูกนำลงในหน่วยความจำหลักพร้อมกับตัวกระบวนการ เพียงแต่ไม่ต้องนำหน้าจริงเข้ามาด้วย (ค่าบิตสถานะเป็นใช้ไม่ได้ (invalid))

แสดงตารางเลขหน้าเมื่อบางหน้าไม่ได้อยู่ในหน่วยความจำหลัก

จะสังเกตเห็นว่า หน้าที่มีบิตสถานะเป็น ใช้ไม่ได้ (invalid) จะไม่มีผลอะไรต่อระบบเลย ถ้ากระบวนการไม่ได้มีการใช้หน้านี้ ดังนั้น ถ้าตัวสับเปลี่ยนหน้า (Pager) เดาถูกและนำหน้าเฉพาะที่ต้องการให้เข้ามาในหน่วยความจำหลักแล้ว กระบวนการจะสามารถทำงานได้เสมือนทังตัวอยู่ในหน่วยความจำหลัก

อะไรจะเกิดขึ้นเมื่อกระบวนการพยายามใช้หน้าที่ยังไม่ได้ถูกย้ายเข้ามาในหน่วยความจำหลัก ? เมื่อฮาร์ดแวร์ในระบบแบ่งเป็นหน้า ตรวจดูว่าหน้าที่กระบวนการต้องการมีบิตสถานะเป็นใช้ไม่ได้ จะเกิด “การผิดหน้า” (Page Fault) ขึ้น และรายงานข้อผิดพลาดไปยังระบบปฏิบัติการ ปกติเมื่อมีการอ้างอิงตำแหน่งผิดพลาด กระบวนการจะต้องถูกยกเลิก แต่กรณีนี้ระบบจะนำหน้าที่ต้องการเข้ามาในหน่วยความจำหลัก ตามขั้นตอนดังนี้

ขั้นตอนในการจัดการการผิดหน้า (Page fault)

1. ตรวจดูตารางข้อมูลจำเพาะของกระบวนการ (PCB) ว่าหน้าที่ต้องการอ้างอิงถูกต้องหรือไม่
2. ถ้าเป็นการอ้างอิงผิดพลาดก็ให้ยกเลิกกระบวนการ ถ้าถูกต้องแต่หน้าที่ต้องการนี้ไม่ได้อยู่ในหน่วยความจำหลักให้ดำเนินการขั้นต่อไป
3. หาเนื้อที่ว่างในหน่วยความจำจริง (frame) 1 หน้า (เช่น เลือกจากรายชื่อหน้าว่าง (free frame list))
4. จัดคำร้องขอส่งไปยังจานบันทึกเพื่อให้อ่านหน้าที่ต้องการมาไว้ในเนื้อที่ว่างที่เลือกไว้
5. เมื่อจานบันทึกนำหน้าเข้ามาเสร็จแล้ว ระบบก็จะแก้ไขบิตสถานะในตารางเลขหน้าเป็น “ใช้ได้” (valid)
6. จัดให้กระบวนการทำงานต่อจากจุดที่เกิด “การผิดหน้า” กระบวนการจึงสามารถทำงานต่อได้เสมือนว่าหน้าที่ต้องการอยู่ในหน่วยความจำหลักตลอดเวลา

อย่าลืมว่าเมื่อกระบวนการหยุดชั่วคราว (เนื่องจากการผิดหน้า) ระบบได้เก็บค่าสถานะต่าง ๆ ของกระบวนการ (ค่าในรีจีสเตอร์ ตัวชี้คำสั่ง ค่าสถานะอื่น ๆ) ดังนั้นเราจึงสามารถให้กระบวนการทำงานต่อจากจุดเดิมได้ เสมือนว่าไม่มีการหยุดทำงานเลย ด้วยวิธีนี้เราจึงสามารถให้กระบวนการทำงานได้ โดยไม่ต้องนำกระบวนการเข้ามาในหน่วยความจำพร้อมกันทั้งหมด เมื่อกระบวนการพยายามอ่านตำแหน่งที่ไม่ได้อยู่ในหน่วยความจำหลัก ฮาร์ดแวร์จะรายงานข้อผิดพลาดไปยังระบบ (การผิดหน้า) ระบบปฏิบัติการจะนำหน้าที่ต้องการเข้ามาในหน่วยความจำและให้กระบวนการทำงานต่อราวกับว่าหน้าที่ต้องการอยู่ในหน่วยความจำหลักตลอดเวลา

ในกรณีสุดขั้ว เราอาจให้กระบวนการทำงานโดยไม่มีการนำส่วนของกระบวนการเข้ามาในหน่วยความจำเลยแม้แต่หน้าเดียว เมื่อกระบวนการเริ่มทำงาน ก็จะเกิดการผิดหน้าทันทีที่คำสั่งแรก หลังจากที่ระบบนำหน้าแรกเข้ามาแล้วกระบวนการจะทำงานต่อ และจะเกิดการผิดหน้าขึ้นอีกเรื่อย ๆ จนกระทั่งทุก ๆ หน้าได้ถูกนำเข้ามาในหน่วยความจำหลัก แล้วจะไม่มีการผิดหน้าอีกต่อไป วิธีนี้เรียกว่า การจัดสรรหน้าตามคำร้องขอสมบูรณ์แบบ (Pure Demand Paging) คือจะไม่มีการนำหน้าเข้ามาก่อนที่จะมีการร้องขอ

อุปกรณ์ช่วยในระบบนี้ก็เหมือนกับในระบบแบ่งเป็นหน้า (Paging and Swapping) คือ

• ตารางเลขหน้า (Page table) ในตารางต้องมีบิตสถานะหรือบิตป้องกันพิเศษเพื่อแสดงสถานะของหน้าว่า “ใช้ได้” (valid) หรือ “ใช้ไม่ได้” (invalid)
• หน่วยความจำสำรอง (Secondary Memory) เพื่อใช้เก็บส่วนของกระบวนการที่ไม่ได้อยู่ในหน่วยความจำหลัก ปกติใช้จานบันทึกความเร็วสูงซึ่งมีชื่อเรียกว่า “อุปกรณ์สับเปลี่ยนหน้า” (Swap device) และพื้นที่ในจานบันทึกซึ่งเรียกว่า “พื้นที่สับเปลี่ยน” (Swap Space) หรือ “หน่วยเก็บโปรแกรมชั่วคราว” (Backing Store)

นอกจากนี้ยังต้องมีโปรแกรมช่วยอีกด้วย ดังจะกล่าวต่อไป

มีข้อจำกัดบางอย่างในด้านสถาปัตยกรรมของเครื่องคอมพิวเตอร์ที่ต้องจัดการ เพื่อที่จะให้สามารถให้กระบวนการทำงานต่อจากจุดเดิมที่หยุดทำงานไปได้หลังจากที่เกิดการผิดหน้า ปกติแล้วข้อจำกัดนี้สามารถทำได้ง่าย การผิดหน้าอาจเกิดขึ้นได้ทุกครั้งที่มีการอ้างอิงหน่วยความจำหลัก ถ้าเกิดการผิดหน้าขณะที่พยายามจะอ่านคำสั่ง (Instruction fetch) เราก็เพียงอ่านคำสั่งเข้ามาใหม่อีกครั้ง ถ้าเกิดการผิดหน้าระหว่างที่พยายามอ่านตัวแปร (Operand) เราต้องเริ่มอ่านคำสั่งเข้ามาใหม่ แปลคำสั่งอีกครั้ง และอ่านตัวแปรอีกครั้ง

ในกรณีที่แย่ที่สุด อาจเกิดการผิดหน้าระหว่างคำสั่งประเภทที่อ้างอิง 3 ตำแหน่ง (Three address Instruction) เช่น บวก A กับ B และใส่ผลลัพธ์ไว้ที่ C ขั้นตอนการทำงานเป็นดังนี้

1. อ่านคำสั่งเข้ามา และแปลคำสั่ง (ADD)
2. อ่านค่า A
3. อ่านค่า B
4. บวก A กับ B
5. เขียนผลลัพธ์ลงไปที่ C

ถ้าเกิดการผิดหน้าเมื่อกำลังเขียนผลลัพธ์ลงที่ C (เพราะ C อยู่ในหน้าที่ไม่ได้อยู่ในหน่วยความจำหลัก) เราก็ต้องนำหน้าที่ C อยู่เข้ามาแก้ไขตารางเลขหน้า และเริ่มทำคำสั่งซ้ำใหม่ โดยต้องทำขั้นตอนที่ 1 2 3 4 และ 5 ซ้ำอีกทุกขั้นตอน แต่อย่างไรก็ตามเป็นงานที่ซ้ำไม่มากนัก (เพียงไม่เกิน 1 คำสั่ง) และจะต้องทำซ้ำเฉพาะเมื่อเกิดการผิดหน้าขึ้นเท่านั้น

ปัญหาเดียวกันนี้เกิดขึ้นในคำสั่งที่มีการแก้ไขหลายตำแหน่งในคำสั่งเดียว เช่น คำสั่งย้ายตัวอักษร (Move Character – MVC) ในเครื่องคอมพิวเตอร์ IBM 360/370 สามารถย้ายตัวอักษรได้มากถึง 256 ไบต์ จากที่หนึ่ง ไปสู่อีกที่หนึ่ง (พื้นที่เหลื่อมกันได้ด้วย) ถ้าพื้นที่หนึ่งบังเอิญอยู่ระหว่างขอบหน้า อาจเกิดการผิดหน้าเมื่อมีการย้ายตัวอักษรไปได้บางส่วนแล้ว ! และถ้าพื้นที่มีการเหลื่อมกัน ข้อมูลต้นทางอาจถูกแก้ไขแล้ว ซึ่งเหตุการณ์นี้เราไม่อาจทำซ้ำได้โดยง่าย

การแก้ปัญหานี้ทำได้ 2 วิธี

• วิธีแรก โปรแกรมในฮาร์ดแวร์ (microcode) พยายามอ้างอิงที่หัว-ท้ายของพื้นที่ ก่อนจะเริ่มต้นย้าย ถ้าจะเกิดการผิดหน้าขึ้นก็จะเกิดในขั้นตอนนี้ ซึ่งยังไม่มีการแก้ไขข้อมูลใด ๆ หลังจากนำหน้าที่ต้องการเข้ามาแล้วจึงทำคำสั่งนี้ซ้ำใหม่
• วิธีที่สอง ใช้รีจีสเตอร์ชั่วคราวเก็บค่าเดิมของตำแหน่งที่ถูกแก้ไขไว้ ถ้าเกิดการผิดหน้า ก็เพียงแต่เขียนค่าเก่ากลับลงไปในตำแหน่งเดิมก่อนที่จะรายงานข้อผิดพลาดไปยังระบบปฏิบัติการ ซึ่งทำให้ค่าต่าง ๆ ในหน่วยความจำเหมือนเดิม ก่อนที่จะรายงานข้อผิดพลาดไปยังระบบปฏิบัติการ ซึ่งทำให้ค่าต่าง ๆ ในหน่วยความจำเหมือนเดิมก่อนที่จะทำคำสั่งนี้ เราจึงสามารถทำคำสั่งนี้ซ้ำอีกได้เมื่อกระบวนการเริ่มทำงานต่อ

ปัญหาด้านสถานปัตยกรรมของเครื่องคอมพิวเตอร์แบบนี้อาจเกิดขึ้นได้ในเครื่องที่มีการอ้างอิงแบบพิเศษประเภทเพิ่มค่าหรือลดค่าอัตโนมัติ (เช่น เครื่อง PDP-11) การอ้างอิงตำแหน่งแบบนี้ใช้รีจีสเตอร์เป็นตัวชี้ไปยังตำแหน่งที่ต้องการ และเพิ่มค่าหรือลดค่าในรีจีสเตอร์โดยอัตโนมัติ การลดค่าอัตโนมัติ จะลดค่าในรีจีสเตอร์ก่อนที่จะใช้ค่าในรีจีสเตอร์ ส่วนการเพิ่มค่าอัตโนมัติ จะเพิ่มค่าในรีจีสเตอร์หลังจากที่ใช้ค่าในรีจีสเตอร์แล้ว เช่น คำสั่ง

MOV (R2)+,-(R3)

คือ คัดลอกค่าจากตำแหน่งที่ชี้โดยรีจีสเตอร์ R2 ลงในตำแหน่งที่ชี้โดยรีจีสเตอร์ R3 เพิ่มค่าในรีจีสเตอร์ R2 อีก 2 (2 ไบต์ = 1 คำ) หลังจากที่ได้เป็นตัวชี้แล้ว และลดค่าในรีจีสเตอร์ R3 ลง 2 ก่อนที่จะใช้เป็นตัวชี้ ถ้าเกิดการผิดหน้าขณะที่พยายามจะเขียนค่าลงในตำแหน่งที่ชี้โดยรีจีสเตอร์ R3 เราต้องแก้ไขค่าในรีจีสเตอร์ทั้งคู่ให้กลับไปเป็นค่าเดิมก่อนที่จะทำคำสั่งนี้ซ้ำใหม่ ทางแก้คือต้องเพิ่มรีจีสเตอร์พิเศษอีกตัว เพื่อเก็บหมายเลขและปริมาณค่าที่ถูกแก้ไข (เพิ่มหรือลด) ในระหว่างคำสั่งเพื่อให้ระบบปฏิบัติการสามารถใช้ “ทำย้อนกลับ” (Undo) ค่าเดิมได้ก่อนที่จะเกิดการผิดหน้า

ที่กล่าวมาเป็นเพียงปัญหาบางอย่างด้านสถานปัตยกรรมคอมพิวเตอร์ที่เกิดจากการเพิ่มการจัดสรรหน้าตามคำร้องขอ (Demand Paging) ลงในระบบ วิธีการจัดสรรนี้แทรกลงไประหว่างหน่วยประมวลผลกลางกับหน่วยความจำหลัก ดังนั้นกระบวนการผู้ใช้จึงมองไม่เห็นอะไรแตกต่างจากเดิมเลย เราสามารถเพิ่มการจัดสรรนี้ลงในระบบใด ๆ ก็ได้ที่มีการย้ายตำแหน่งแบบสัมพัทธ์ ปัญหาที่กล่าวมาแสดงให้เห็นว่า เมื่อเกิดการผิดหน้าไม่ได้หมายความว่า เราแค่จัดการนำหน้าที่ต้องการเข้ามาในหน่วยความจำให้ได้ก็เสร็จ

ประสิทธิภาพของระบบจัดสรรหน้าตามคำร้องขอ (Performance of Demand Paging)

การจัดสรรหน้าตามคำร้องขอ (Demand Paging) มีผลต่อประสิทธิภาพของระบบเป็นอย่างมาก ลองมาคำนวณเวลาเฉลี่ยในการอ้างอิงหน่วยความจำ (Effective Access Time) ในระบบนี้ดู ในระบบคอมพิวเตอร์ส่วนใหญ่เวลาที่ใช้ในการอ้างอิงหน่วยความจำให้เป็น ma มีค่าระหว่าง 10 ถึง 200 นาโนวินาที ถ้าไม่มีการผิดหน้า เวลาเฉลี่ยในการอ้างอิงหน่วยความจำก็จะเท่ากับค่านี้ แต่ถ้าเกิดการผิดหน้า เราต้องอ่านหน้าที่ต้องการจากจานบันทึก แล้วจึงอ้างอิงตำแหน่งที่ต้องการซ้ำใหม่

ให้ p เป็นโอกาสที่จะเกิดการผิดหน้า (0 p 1) เราต้องการให้ค่า p ใกล้ 0 มากที่สุด คือ เกิดการผิดหน้าน้อยครั้งที่สุด

เวลาเฉลี่ยในการอ้างอิงหน่วยความจำ (effective access time)

= (1-p) x ma + p x เวลาที่ใช้จัดการการผิดหน้า (page fault time)

การผิดหน้ามีขั้นตอนดังนี้

1. รายงานข้อผิดพลาดไปยังระบบปฏิบัติการ
2. เก็บค่าต่าง ๆ ของรีจีสเตอร์และสถานะของกระบวนการ
3. ตรวจดูว่าสัญญาณขัดจังหวะนั้นเป็นการผิดหน้า
4. ตรวจดูว่าหน้าที่ต้องการถูกต้อง (อยู่ในขอบเขตที่มีสิทธิใช้) และหาค่าตำแหน่งของหน้านี้ในจานบันทึก
5. ทำคำร้องขอไปยังจานบันทึกให้อ่านหน้านั้นเข้ามายังพื้นที่ว่าง (free frame)

1. เข้าไปรอในแถวอุปกรณ์จนกระทั่งถึงคราวของเรา
2. อุปกรณ์จะหมุนและกวาดไปยังตำแหน่งที่ต้องการ
3. โอนถ่ายข้อมูลจากอุปกรณ์ไปยังพื้นที่ว่าง

1. ขณะที่รออยู่ตัวจัดตารางการทำงานอาจจัดให้กระบวนการอื่นทำงานไปก่อน
2. สัญญาณขัดจังหวะจากจานบันทึกว่าอ่านเสร็จแล้ว
3. เก็บค่าของรีจีสเตอร์และสถานะของกระบวนการอื่นที่กำลังทำงานอยู่
4. ตรวจดูว่าสัญญาณมาจากจานบันทึก
5. แก้ไขค่าในตารางเลขหน้าและตารางอื่น ๆ ที่เกี่ยวข้องเพื่อแสดงว่าหน้าที่ต้องการอยู่ในหน่วยความจำหลักแล้ว
6. เข้าไปรออยู่ในแถวพร้อมเพื่อรอเข้าใช้หน่วยประมวลผล
7. เมื่อถึงคราว บรรจุค่าต่าง ๆ ที่เก็บไว้ลงในรีจีสเตอร์และตารางเลขหน้าของกระบวนการ แล้วเริ่มทำคำสั่งเดิมที่หยุดไว้

บางขั้นตอนอาจไม่จำเป็นก็ได้ (เช่น ขั้นตอนที่ 5,6) เราสมมติว่า หน่วยประมวลผลกลางย้ายไปทำงานให้กระบวนการอื่นขณะที่เราคอยอุปกรณ์รับ-ส่งข้อมูล ทำให้ต้องมีการอ่านค่าต่าง ๆ เข้ามาใหม่ เมื่ออุปกรณ์ทำงานเสร็จ

เราอาจรวมขั้นตอนต่าง ๆ เป็น 3 ขั้นใหญ่ ๆ ในการจัดการการผิดหน้าได้ดังนี้

1. จัดการสัญญาณขัดจังหวะจากการผิดหน้า
2. อ่านหน้าที่ต้องการเข้ามา
3. ให้กระบวนการทำงานต่อ

ขั้นตอนที่ 1 และ 3 อาจทำให้สั้นที่สุดได้โดยการเขียนโปรแกรมอย่างรอบคอบเพียงไม่กี่ร้อยคำสั่ง ซึ่งใช้เวลาทำงานเพียง 1-100 ไมโครวินาที แต่การสับเปลี่ยนหน้าในขั้นตอนที่ 2 อาจกินเวลาถึง 24 มิลลิวินาที จานบันทึกปกติต้องใช้เวลาหมุนหา 8 มิลลิวินาที หาเซกเตอร์อีก 15 มิลลิวินาที และโอนถ่ายข้อมูลอีก 1 มิลลิวินาที ดังนั้นเวลาที่ใช้ในการจัดการการผิดหน้ามีค่าประมาณ 25 มิลลิวินาที (รวมเวลาทั้งฮาร์ดแวร์และโปรแกรมทำงาน) อย่าลืมว่าเราคิดเฉพาะเวลาที่เสียไปในอุปกรณ์เท่านั้น ไม่ได้รวมถึงเวลารอคอยในแถวอุปกรณ์ (กระบวนการอื่น ๆ ก็อาจเกิดการผิดหน้าได้เช่นกัน)

ถ้าเราให้เวลาเฉลี่ยในการจัดการการผิดหน้า (page fault time) เป็น 25 มิลลิวินาที และเวลาที่ใช้ในการอ้างอิงหน่วยความจำ (ma) เป็น 100 นาโนวินาที แล้ว

เวลาเฉลี่ยในการอ้างอิงหน่วยความจำ = (1-p) x (100 นาโนวินาที) + p x (25 มิลลิวินาที)

= (1-p) x 100 + (p x 25,000,000) นาโนวินาที

= 100 + 24,999,900 x p นาโนวินาที

จะเห็นได้ว่าเวลาเฉลี่ยในการอ้างอิงหน่วยความจำเป็นสัดส่วนโดยตรงกับ อัตราการผิดหน้า (p) ถ้า p = 1/1000 คือมีการผิดหน้า 1 ครั้งต่อการอ้างอิง 1000 ครั้ง จะได้เวลาเฉลี่ยในการอ้างอิงหน่วยความจำเท่ากับ 25 ไมโครวินาที (เทียบกับ 100 นาโนวินาที) จะเห็นได้ว่าระบบคอมพิวเตอร์ทำงานช้าลงถึง 250 เท่า เนื่องจากการจัดสรรหน้าตามคำร้องขอ ถ้าเราต้องการให้ระบบทำงานช้าลงเพียงไม่เกิน 10 % อาจคำนวณได้ดังนี้

110 > 100 + 25,000,000 x p

10 > 25,000,000 x p

p < 0.0000004

ดังนั้นเพื่อที่จะให้ระบบทำงานช้าลงอีกเล็กน้อยพอยอมรับได้ เราสามารถยอมให้เกิดการผิดหน้าได้เพียง 1 ครั้งต่อการอ้างอิง 2,500,000 ครั้ง

จะเห็นได้ว่าการทำให้อัตราการผิดหน้าต่ำที่สุดเป็นสิ่งจำเป็นอย่างยิ่งในระบบการจัดสรรหน้าตามคำร้องขอ มิฉะนั้นระบบทั้งระบบจะทำงานช้าลงอย่างมากมายมหาศาล

เราอาจปรับปรุงระบบให้ดีขึ้น โดยการให้การจัดสรรหน้าตามคำร้องขอทำในหน่วยเก็บโปรแกรมชั่วคราว (Backing Store or Swap Space) ซึ่งจะทำงานได้เร็วกว่าระบบแฟ้มข้อมูล (file system) เนื่องจากหน่วยเก็บโปรแกรมชั่วคราวมีการจองพื้นที่ขนาดใหญ่กว่า และระบบแฟ้มข้อมูลอาจอ่านแบบโดยอ้อม (indirect) และการค้นหาแฟ้มข้อมูลก็ช้ากว่าด้วย การเพิ่มประสิทธิภาพของระบบทำได้โดยการคัดลอกแฟ้มข้อมูลทั้งตัวลงในหน่วยเก็บโปรแกรมชั่วคราว เมื่อกระบวนการเริ่มทำงานและจัดสรรหน้าตามคำร้องขอจากหน่วยเก็บโปรแกรมชั่วคราวนี้แทน ในระบบที่มีพื้นที่ในหน่วยเก็บโปรแกรมชั่วคราวจำกัด ก็อาจทำได้โดยเริ่มทำการจัดสรรหน้าตามคำร้องขอจากระบบแฟ้มข้อมูลโดยตรง แต่เมื่อมีการสับเปลี่ยนหน้าออก ก็เขียนหน้าออกไปไว้ในหน่วยเก็บโปรแกรมชั่วคราวแทน การทำเช่นนี้ทำให้อ่านแฟ้มจากระบบแฟ้มข้อมูลเข้ามาเท่าที่จำเป็นเท่านั้น และต่อจากนั้นก็จะทำการสับเปลี่ยนหน้าในหน่วยเก็บโปรแกรมชั่วคราว วิธีนี้น่าจะให้ประสิทธิภาพสูงสุดซึ่งมีใช้ในระบบปฏิบัติการ UNIX BSD

การสับเปลี่ยนหน้า (Page Replacement)

จากที่กล่าวมาแล้วจะเห็นได้ว่า อัตราการผิดหน้าไม่ใช่ปัญหาใหญ่ เพราะแต่ละหน้ามีโอกาสจะเกิดการผิดหน้าได้เพียงครั้งเดียวเท่านั้น (เมื่อถูกอ้างอิงเป็นครั้งแรก) แต่การคิดหรือสมมติเช่นนั้นไม่เป็นความจริงเสมอไป ลองพิจารณาตัวอย่างกระบวนการหนึ่งมีขนาด 10 หน้า แต่ใช้จริงแค่ครึ่งเดียว ดังนั้นโดยใช้วิธีการจัดสรรหน้าตามคำร้องขอ ก็จะมีหน้าของกระบวนการที่อยู่ในหน่วยความจำเพียง 5 หน้าเท่านั้น เราจึงอาจเพิ่มจำนวนโปรแกรมให้ทำงานพร้อมกัน (increase degree of multiprogramming) เป็น 2 เท่า เช่น ถ้าหน่วยความจำจริงมีเนื้อที่ 40 หน้า เราอาจให้กระบวนการทำงานพร้อมกันได้ถึง 8 กระบวนการ แทนที่จะเป็น 4 กระบวนการ โดยกระบวนการแต่ละตัวมีขนาด 10 หน้า (แต่ใช้จริงเพียง 5 หน้า)

แต่เราให้จำนวนโปรแกรมที่ทำงานพร้อมกันเป็นเพียง 6 กระบวนการ เราก็จะเหลือเนื้อที่ว่างในหน่วยความจำจริงไว้เพื่อสำรอง 10 หน้า การเพิ่มจำนวนโปรแกรมที่ทำงานพร้อมกันให้มากขึ้น จะทำให้อัตรางานเสร็จสูงขึ้น และประสิทธิภาพในการใช้งานหน่วยประมวลผลกลางสูงขึ้นด้วย แต่อย่างไรก็ตามอาจเกิดเหตุการณ์ที่ทั้ง 6 กระบวนการต้องการใช้หน้าทั้ง 10 หน้าของตัวเองพร้อมกัน รวมเป็น 60 หน้า (แต่เรามีเนื้อที่จริงเพียง 40 หน้า) แม้ว่าเหตุการณ์เช่นนี้จะเกิดขึ้นยากก็ตาม แต่โอกาสที่จะเกิดจะเพิ่มสูงขึ้น เมื่อเราเพิ่มจำนวนโปรแกรมที่ทำงานพร้อมกันในระบบให้สูงขึ้น (อย่างในตัวอย่างนี้เราอาจเพิ่มเป็น 7-8 กระบวนการได้หรือไม่)

การเพิ่มจำนวนกระบวนการที่ทำงานพร้อมกันในระบบ ทำให้เกิดการจัดสรรหน่วยความจำเกินความจุจริง (Over allocation) 

แสดงความจำเป็นที่จะต้องมีการสับเปลี่ยนหน้า

 

เมื่อกระบวนการผู้ใช้พยายามอ้างอิงหน้าที่ไม่ได้อยู่ในหน่วยความจำจริง จะเกิดการผิดหน้าขึ้น ฮาร์ดแวร์ก็จะรายงานข้อผิดพลาดนี้ไปที่ระบบปฏิบัติการ ซึ่งจะตรวจดูที่ตารางข้อมูลว่าข้อผิดพลาดนี้ เป็นการผิดหน้า (หรือเป็นการอ้างอิงที่ผิดหน้าจริง ๆ) ก็จะนำหน้าที่ต้องการเข้ามาไว้ในหน่วยความจำหลัก แต่พบว่าไม่มีที่ว่างเหลือเลย ระบบปฏิบัติการมีทางเลือกดังนี้คือ

• เลือกหยุดการทำงานของกระบวนการผู้ใช้ที่ทำให้เกิดการผิดหน้า แต่ทว่าการจัดหน้าตามคำร้องขอเป็นความพยายามของระบบที่จะเพิ่มประสิทธิภาพ โดยที่ผู้ใช้ไม่ควรจะต้องรู้ว่ากำลังทำงานอยู่ในระบบแบ่งหน้า ดังนั้นการเลือกวิธีนี้จึงไม่เหมาะนัก

อีกทางหนึ่งคือ

• การย้ายกระบวนการออกไปพักชั่วคราวบางส่วนเพื่อเพิ่มเนื้อที่ว่างในหน่วยความจำและลดจำนวนกระบวนการที่ทำงานพร้อมกันในระบบลง ซึ่งเหมาะกับเหตุการณ์บางอย่าง แต่ก็ไม่ใช่วิธีที่ดีที่สุดในเวลานี้

ทางที่น่าจะดีที่สุด คือ การสับเปลี่ยนหน้า (Page Replacement) เมื่อไม่มีที่ว่างเหลือในหน่วยความจำหลัก ระบบจะเลือกสับเปลี่ยนหน้าที่อยู่ในหน่วยความจำหลักบางหน้าไปเก็บไว้ในจานบันทึกสำรองก่อน และแก้ไขตารางเลขหน้าตามเพื่อแสดงว่าหน้านั้น ๆ ไม่อาจใช้ได้ (เพราะไม่ได้อยู่ในหน่วยความจำหลัก) ที่ว่างนี้สามารถใช้เป็นที่ว่างสำหรับพื้นที่ที่ต้องการอันเนื่องมาจากการผิดหน้าในปัจจุบันได้ ดูรูปที่ข้างล่าง 

                                       แสดงการสับเปลี่ยนหน้า

ดังนั้นเราอาจแก้ไขขั้นตอนในการจัดการ “การผิดหน้า” (page fault) เสียใหม่ โดยรวมการสับเปลี่ยนหน้า (Page Replacement) เข้าไปด้วย ดังนี้

1. หาตำแหน่งของหน้าที่ต้องการบนจานบันทึก
2. หาเนื้อที่ว่างในหน่วยความจำ
3. ถ้ามีที่ว่าง ก็ใช้งานหน้านั้นได้เลย
4. ถ้าไม่มี ใช้ขั้นตอนวิธี การสับเปลี่ยนหน้า เพื่อเลือกผู้เสียสละ (หน้าที่จะถูกสับเปลี่ยนออกไป)
5. ย้ายหน้าที่เลือกออกไปเก็บไว้ในจานบันทึก แก้ไขตารางข้อมูลให้ถูกต้อง
6. อ่านหน้าที่ต้องการเข้ามาเก็บไว้ในเนื้อที่ว่างที่เลือกไว้ แก้ไขตารางข้อมูลให้ถูกต้อง
7. ให้กระบวนการที่หยุดรออยู่ทำงานต่อ

จะสังเกตเห็นว่า ถ้าไม่มีเนื้อที่ว่างจะเกิดการย้ายหน้า 2 ครั้ง (ย้ายออกและย้ายเข้า) ซึ่งเป็นผลให้เวลาที่ใช้ในการจัดการการผิดหน้า เพิ่มขึ้นเป็น 2 เท่า และเวลาเฉลี่ยในการอ้างอิงหน้าก็จะเพิ่มขึ้นอย่างมากด้วย

เวลาที่เสียไปนี้อาจลดลงได้โดยการเพิ่ม บิตแก้ไข (Modify bit หรือ Dirty bit) ลงไปที่แต่ละหน้า (เพิ่มฮาร์ดแวร์ช่วย) การแก้ไขข้อมูลใด ๆ ในหน้า บิตแก้ไขก็จะเปลี่ยนค่าเป็น “ถูกแก้ไข” เมื่อต้องการสับเปลี่ยนหน้าใดออกจากหน่วยความจำหลัก ระบบจะดูที่บิตแก้ไขก่อนว่ามีค่าเป็น “ถูกแก้ไข” หรือไม่

ถ้าถูกแก้ไขหมายความว่าหน้าในหน่วยความจำมีข้อมูลต่างไปจากในจานบันทึก จึงจำเป็นต้องย้ายข้อมูลออกไปทับข้อมูลเดิมในจานบันทึก แต่ถ้าบิตแก้ไขไม่ได้ถูกแก้ไข แสดงว่ายังไม่มีการเขียนข้อมูลใหม่ทับในหน้านี้เลย การสับเปลี่ยนหน้านี้ออกไปจึงไม่ต้องย้ายข้อมูลออกไปจริง ๆ เพราะข้อมูลในจานบันทึกก็เหมือนกับในหน่วยความจำ วิธีนี้จะใช้ได้ผลดีโดยเฉพาะกับหน้าที่เป็นแบบอ่านอย่างเดียว (read-only) เช่น หน้าที่เป็นส่วนของโปรแกรมไม่ใช่ข้อมูล หรือ ตัวแปร เป็นต้น การใช้บิตแก้ไขช่วย อาจทำให้เวลาที่ใช้ในการจัดการการผิดหน้าลดลงถึงครึ่งหนึ่ง ถ้าไม่มีการแก้ไขหน้านั้น ๆ

การสับเปลี่ยนหน้า (Page Replacement) เป็นเทคนิคพื้นฐานของการจัดสรรหน้าตามคำร้องขอ (Demand Paging) ทำให้หน่วยความจำทางตรรกะที่ผู้ใช้มองเห็นเป็นอิสระจากหน่วยความจำจริง (ทางกายภาพ) โดยสิ้นเชิง เราอาจสร้างหน่วยความจำเสมือนขนาดใหญ่มาก ๆ ได้ โดยแม้มีหน่วยความจำจริงขนาดเล็กก็ตาม การจัดสรรหน้าตามคำร้องขอทำให้หน่วยความจำทางตรรกะมีขนาดได้ไม่จำกัด เช่น โปรแกรมของผู้ใช้อาจมีขนาด 20 หน้า ทั้ง ๆ ที่หน่วยความจำจริงมีขนาดเพียง 10 หน้าเท่านั้น

ขั้นตอนวิธีการสับเปลี่ยนหน้าจะหาเนื้อที่ว่างให้ได้เสมอเมื่อต้องการ หน้าที่ถูกสับเปลี่ยนออกจะถูเขียนกลับไว้ในจานบันทึก ซึ่งถ้ามีการอ้างอิงหน้านี้อีก ก็จะเกิดการผิดหน้าขึ้น ทำให้หน้านี้ถูกนำกลับมาไว้ในหน่วยความจำอีก โดยสับเปลี่ยนกับหน้าอื่น ๆ ในหน่วยความจำ

ปัญหาหลักของวิธีการจัดสรรหน้าตามคำร้องขอ คือ ต้องมีขั้นตอนวิธีในการหาเนื้อที่ว่างหรือหน้าผู้เสียสละ และขั้นตอนวิธีในการสับเปลี่ยนหน้า ในระบบที่มีหลายกระบวนการทำงานพร้อมกัน เราต้องตัดสินใจว่าจะให้เนื้อที่สำหรับแต่ละกระบวนการกี่หน้า และเมื่อต้องการเนื้อที่ว่างเราก็ต้องตัดสินใจว่าจะเลือกหน้าใดออก การออกแบบขั้นตอนวิธีในการแก้ปัญหาเหล่านี้เป็นสิ่งสำคัญต่อระบบมาก เพราะเวลาที่เสียไปในการส่งข้อมูลไปและกลับจากจานบันทึกมีเป็นค่าใหญ่มาก การปรับปรุงขั้นตอนวิธีให้ดีขึ้นเพียงเล็กน้อย อาจทำให้ประสิทธิภาพของระบบโดยรวมดีขึ้นอย่างมากได้

ขั้นตอนวิธีการสับเปลี่ยนหน้า (Page-Replacement Algorithms)

มีวิธีการมากมายหลายแบบในการสับเปลี่ยนหน้า มากเสียจนระบบปฏิบัติการต่าง ๆ ที่สร้างขึ้นมา อาจมีวิธีการไม่ซ้ำกันเลยก็ได้ เราจะเลือกวิธีการใดดี ? โดยปกติเราควรเลือกวิธีที่ทำให้อัตราการผิดหน้าต่ำที่สุด

เราอาจทดสอบขั้นตอนวิธีเหล่านี้โดยการสร้างข้อมูล แล้วทดลองดูว่าวิธีใด เกิดการผิดหน้ากี่ครั้ง ข้อมูลที่สร้างขึ้นอยู่ในรูปของสายการอ้างอิง (Reference String) ตำแหน่งในหน่วยความจำ ซึ่งอาจสร้างขึ้นโดยการใช้ตัวผลิตเลขสุ่มหรือจดบันทึกมาจากระบบจริง ๆ ก็ได้ ข้อมูลนี้ถ้าจดบันทึกจากระบบจริง อาจมีปริมาณมากเกินไปได้ (เป็นล้าน ๆ ตำแหน่งต่อวินาที) ดังนั้นเราจึงต้องมีวิธีลดปริมาณข้อมูลลงโดย

1. การอ้างอิงตำแหน่งในหน้าเดียวกัน เราใช้หมายเลขหน้าแทน (เพราะโดยปกติขนาดของหน้าจะมีค่าคงที่ ซึ่งกำหนดโดยฮาร์ดแวร์ของระบบเอง)
2. ถ้ามีการอ้างอิงหน้าหมายเลข p แล้ว การอ้างอิงหน้า p อีกติด ๆ กัน ก็จะไม่เกิดการผิดหน้าอีก จะเกิดที่ครั้งแรกสุดเท่านั้น (เพราะเมื่อเกิดการผิดหน้า กระบวนการจะหยุดการทำงาน และระบบก็จะนำหน้า p เข้ามาในหน่วยความจำ ดังนั้นการอ้างอิงหน้า p ครั้งต่อ ๆ ไป จะไม่ทำให้เกิดการผิดหน้าอีก) เราจึงสามารถรวมการอ้างอิงหน้า p ที่ติด ๆ กัน เป็น 1 การอ้างอิงได้ ตัวอย่างเช่น เราจดบันทึกการอ้างอิงตำแหน่งของกระบวนการหนึ่งได้ดังนี้

0100 , 0432 , 0101 , 0612 , 0102 , 0103 , 0104 , 0101 , 0611 , 0102 , 0103 ,

0104 , 0101 , 0610 , 0102 , 0103 , 0104 , 0101 , 0609 , 0102 , 0105,

ถ้า 1 หน้ามีขนาด 100 ไบต์ สายการอ้างอิงจะกลายเป็น

1 , 4 , 1 , 6 , 1 , 6 ,1 , 6 , 1 , 6 , 1.

ในการคำนวณจำนวนครั้งของการผิดหน้าจากสายการอ้างอิงนี้ เราจำเป็นต้องรู้จำนวนเนื้อที่จริง (page frame) ที่มี ถ้ามีเนื้อที่จริงมากขึ้น จำนวนครั้งของการผิดหน้าก็จะลดลง จากตัวอย่างข้างต้น ถ้าเรามีเนื้อที่จริง 3 หน้าหรือมากกว่า ระบบจะเกิดการผิดหน้าเพียง 3 ครั้งเท่านั้น คือเกิดการผิดหน้าขึ้น ในครั้งแรกที่อ้างอิงถึงแต่ละหน้า ในทางตรงกันข้าม ถ้ามีเนื้อที่จริงเพียง 1 หน้า ก็จะเกิดการผิดหน้า 11 ครั้ง โดยปกติเมื่อจำนวนหน้าจริงมีมากขึ้น จำนวนการผิดหน้าก็จะลดลง 

แสดงกราฟการเปรียบเทียบระหว่างการผิดหน้ากับจำนวนหน้าจริง(frame)

เพื่อที่จะเปรียบเทียบขั้นตอนวิธีในการสับเปลี่ยนหน้าแต่ละแบบ เราจะใช้สายการอ้างอิงดังนี้ (โดยกำหนดให้มีเนื้อที่จริง 3 หน้า)

7 , 0 , 1 , 2 , 0 , 3 , 0 , 4 , 2 , 3 , 0 , 3 , 2 , 1 , 2 , 0 , 1 , 7 , 0 , 1

แบบมาก่อน-ออกก่อน (FIFO Algorithm)

วิธีการสับเปลี่ยนหน้าที่ง่ายที่สุดเห็นจะได้แก่ แบบมาก่อน-ออกก่อน (First-in-First-out) โดยจดเวลาที่หน้านั้น ๆ ถูกนำเข้ามาในหน่วยความจำหลัก เมื่อต้องการเลือกบางหน้าออก ก็จะเลือกจากหน้าที่อยู่มานานที่สุด (มาก่อน) ในทางปฏิบัติอาจไม่ต้องจดเวลาจริง ๆ เพียงแต่สร้างแถวคอย แบบมาก่อน-ออกก่อน (FIFO queue) สำหรับเก็บหมายเลขหน้าที่อยู่ในหน่วยความจำ แล้วเลือกหน้าออกจากหัวแถว เมื่อนำหน้าใหม่เข้ามาก็เอาหมายเลขมาไว้ที่ปลายแถว

จากสายการอ้างอิงที่เรากำหนดไว้ เริ่มที่หน่วยความจำ 3 หน้าของเราว่างเปล่า การอ้างอิง 3 หน้าแรก (7 , 0 , 1) จะเกิดการผิดหน้า และมีการนำหน้าที่ต้องการเข้ามาในหน่วยความจำ การอ้างอิงครั้งต่อไปคือ หน้า 2 จะถูกสับเปลี่ยนเข้ามาแทนหน้า 7 เนื่องจากหน้า 7 เข้ามาก่อนเป็นหน้าแรก ครั้งต่อไปเป็น 0 แต่หน้า 0 อยู่ในหน่วยความจำอยู่แล้ว จึงไม่เกิดการผิดหน้าและก็ไม่เกิดการสับเปลี่ยนหน้าด้วย ต่อไปหน้า 3 จะถูกสับเปลี่ยนเข้ามาแทนหน้า 0 และต่อไปหน้า 0 จะถูกสับเปลี่ยนเข้ามาแทนหน้า 1 ต่อไปเรื่อย ๆ ดังรูปที่ 9.8 แสดงให้เห็นหน้าในหน่วยความจริงทุก ๆ ครั้งที่เกิดการผิดหน้า การผิดหน้าทั้งหมดเท่ากับ 15 ครั้ง

 แสดงการสับเปลี่ยนหน้าแบบมาก่อน-ออกก่อน

 

แบบมาก่อน-ออกก่อนนี้สามารถเข้าใจได้ง่ายและเขียนโปรแกรมได้ง่ายด้วย แต่อาจไม่ให้ประสิทธิภาพดีเสมอไป หน้าที่ถูกสับเปลี่ยนออกไปอาจเป็นส่วนของโปรแกรมเริ่มต้น ซึ่งถูกใช้ในตอนต้น ๆ และไม่มีความต้องการอีกต่อไป หรือในทางตรงกันข้าม หน้าที่ถูกสับเปลี่ยนออก อาจเก็บค่าตัวแปรหลักของโปรแกรม ซึ่งใช้บ่อยมาก โดยถูกกำหนดค่าเริ่มต้นในตอนแรก ๆ ของโปรแกรม มีข้อสังเกตว่า ถึงแม้เราจะสับเปลี่ยนหน้าที่ใช้บ่อยออกไป แต่การทำงานของกระบวนการก็ยังคงถูกต้องเหมือนเดิม เพราะเมื่อหน้านั้น ถูกอ้างอิงอีก ก็จะถูกนำกลับเข้ามาใหม่ ซึ่งหมายความว่า วิธีการแบบที่ไม่ดี อาจเพิ่มอัตราการผิดหน้าและทำให้ระบบทำงานช้าลง แต่จะไม่ทำให้ระบบทำงานผิดพลาด วิธีการสับเปลี่ยนหน้า แบบมาก่อน-ออกก่อนนี้อาจมีปัญหาบ้าง ดังตัวอย่างสายการอ้างอิงต่อไปนี้

1 , 2 , 3 , 4 , 1 , 2 , 5 , 1 , 2 , 3 , 4 , 5.

เมื่อทดลองหาจำนวนการผิดหน้าเทียบกับจำนวนเนื้อที่ที่มีจะได้กราฟดังรูปข้างล่างดังนี้ 

การแสดงกราฟของการผิดหน้าสำหรับวิธีมาก่อน-ออกก่อนบนสายการอ้างอิง

จะสังเกตเห็นว่าเมื่อมีเนื้อที่ 4 หน้าเกิดการผิดหน้า 10 ครั้ง ซึ่งมากกว่าเมื่อใช้เนื้อที่ 3 หน้า (เกิดการผิดหน้าเพียง 9 ครั้ง) ผลลัพธ์ที่ไม่ปกตินี้ เรียกว่า ปรากฏการณ์เบลาดี้ (Balady’s anomaly) ซึ่งแสดงให้เห็นว่าขั้นตอนวิธีสับเปลี่ยนหน้าบางแบบอาจทำให้อัตราการผิดหน้าเพิ่มขึ้นได้แม้ว่าจะเพิ่มเนื้อที่ให้ เดิมเราคิดว่าการเพิ่มทรัพยากร (เพิ่มเนื้อที่) ย่อมทำให้ประสิทธิภาพของระบบดีขึ้น แต่ผลการค้นหว่า พบว่าไม่เป็นความจริงเสมอไป และเรียกว่าเป็น ปรากฏการณ์เบลาดี้

แบบที่ดีที่สุด (Optimal Algorithm)

หลังจากที่มีปรากฏการณ์เบลาดี้แล้ว นักวิจัยจึงพยายามมุ่งหาวิธีการสับเปลี่ยนหน้าที่ดีที่สุด ซึ่งจะมีอัตราการผิดหน้าต่ำที่สุดและย่อมไม่เกิดปรากฏการณ์เบลาดี้ด้วย ขั้นตอนวิธีแบบที่ดีที่สุดนี้เรียกว่า OPT หรือ MIN มีวิธีการดังนี้คือ “เลือกสับเปลี่ยนหน้าที่จะถูกเรียกใช้ในอนาคตอันไกลที่สุด” การใช้วิธีการแบบนี้ทำให้อัตราการผิดหน้าต่ำที่สุดสำหรับเนื้อที่ว่างขนาดหนึ่ง ๆ จากตัวอย่างสายการอ้างอิงข้างต้น จะเห็นว่า วิธีแบบที่ดีที่สุดนี้ทำให้เกิดการผิดหน้าทั้งหมด 9 ครั้ง ดังรูปที่ 9.10

แสดงการสับเปลี่ยนหน้าแบบที่ดีที่สุด

 

การอ้างอิงหน้าแรกทำให้เกิดการผิดหน้า 3 ครั้ง การอ้างอิงหน้าที่ 2 จะสับหน้าที่ 7 ออกเพราะหน้าที่ 7 จะใช้อีกในการอ้างอิงครั้งที่ 18 หน้าที่ 0 จะใช้อีกในการอ้างอิงครั้งที่ 5 และหน้าที่ 1 ใช้อีกทีครั้งที่ 14 การอ้างอิงหน้าที่ 3 จะสับเปลี่ยนหน้าที่ 1 เพราะหน้าที่ 1 จะเป็นหน้าสุดท้ายที่ถูกอ้างอิงอีกในอนาคตเทียบกับอีก 2 หน้าที่อยู่ในหน่วยความจำจริง โดยรวมจะเกิดการผิดหน้า 9 ครั้ง ดีกว่าแบบมาก่อนได้ก่อน ซึ่งมีการผิดหน้าถึง 15 ครั้ง ถ้าไม่คิดการผิดหน้า 3 ครั้งแรกซึ่งจะต้องเกิดอย่างแน่นอน (ไม่ว่าจะใช้ขั้นตอนวิธีแบบใด) จะเห็นว่าแบบที่ดีที่สุดนี้ดีกว่าแบบมาก่อน-ออกก่อน ถึง 2 เท่า แต่น่าเสียดายที่แบบที่ดีที่สุดนี้ยากที่จะสร้างได้จริง ๆ เพราะต้องรู้อนาคตว่าจะมีการอ้างอิงหน้าใด (เหมือนกับข้อจำกัดของการจัดตารางการทำงานแบบงานสั้นที่สุดได้ก่อน SJF) ดังนั้นแบบที่ดีที่สุดนี้ จึงมีไว้เพื่อการเปรียบเทียบเท่านั้น เช่น ถ้าเรามีขั้นตอนวิธีแบบใหม่ เราก็อาจเปรียบเทียบกับแบบที่ดีที่สุดนี้เพื่อจะได้ทราบว่า แบบใหม่มีประสิทธิภาพใกล้เคียงแบบที่ดีที่สุดเท่าใด

แบบใช้มานานสุด-ออกก่อน (LRU Algorithm)

เนื่องจากขั้นตอนวิธีแบบที่ดีที่สุดเป็นไปไม่ได้ในทางปฏิบัติ เราจึงมุ่งหาวิธีที่จะให้ผลใกล้เคียงแทน ความแตกต่างระหว่างแบบมาก่อน-ออกก่อน (FIFO) กับแบบที่ดีที่สุด (OPT) คือ แบบ FIFO ดูเวลาที่สับเปลี่ยนหน้าเข้ามาในหน่วยความจำ ส่วนแบบ OPT ดูเวลาที่หน้าถูกอ้างอิง ถ้าเราใช้ข้อมูลในอดีตที่ผ่านมาประมาการณ์อนาคตอันใกล้ เราอาจจะสับเปลี่ยนหน้าที่ไม่ได้ถูกอ้างอิงมาเป็นเวลานานที่สุด ซึ่งเรียกว่า แบบใช้มานานสุด-ออกก่อน (Least recently used algorithm – LRU)

ขั้นตอนวิธีแบบใช้นานสุด-ออกก่อน จะบันทึกเวลาที่แต่ละหน้าถูกอ้างอิง ครั้งล่าสุดไว้ เมื่อต้องการเลือกหน้าเพื่อสับเปลี่ยนออก ก็จะเลือกหน้าที่ไม่ได้ใช้มาเป็นเวลานานที่สุด (หน้าที่มีตัวเลขเวลาน้อยที่สุด) จะเห็นได้ว่าวิธีนี้มองย้อนเวลาไปในอดีต แทนที่จะมองไปในอนาคต

 แสดงการสับเปลี่ยนหน้าแบบใช้มานานสุด-ออกก่อน (LRU)

ใช้การสับเปลี่ยนหน้าแบบใช้มานานสุด-ออกก่อน เกิดการผิดหน้าทั้งหมด 12 ครั้ง จะสังเกตเห็นว่าในการผิดหน้า 5 ครั้งแรก จะเหมือนกับวิธีที่ดีที่สุด เมื่อมีการอ้างอิงหน้าที่ 4 วิธี LRU จะเลือกหน้า 2 ออก เพราะใช้มานานที่สุด (โดยหน้า 0 เพิ่งจะใช้ไป และหน้า 3 ใช้ก่อนหน้า 0 เล็กน้อย) โดยไม่อาจรู้อนาคตได้ว่าจะมีการอ้างอิงหน้า 2 ในครั้งต่อไป เมื่อเกิดการผิดหน้าจากการอ้างอิงหน้า 2 LRU ก็จะเลือกหน้า 3 ออก เพราะหน้า 3 ใช้มานานที่สุด (จาก 0 , 3 , 4) ถึงแม้ว่า LRU จะไม่รู้อนาคต แต่ก็ให้ผลรวมการผิดหน้าเพียง 12 ครั้ง ซึ่งดีกว่าแบบมาก่อน-ออกก่อน (15 ครั้ง) มาก

เนื่องจากการสับเปลี่ยนหน้าแบบใช้มานานสุด-ออกก่อน ให้ผลดีพอควรจึงเป็นที่นิยมใช้ ปัญหาหลัก จึงอยู่ที่การสร้างระบบหรือเขียนโปรแกรมวิธีนี้ เพราะจำเป็นต้องมีฮาร์ดแวร์ช่วยมากเพื่อช่วยบันทึกเวลาที่มีการอ้างอิงแต่ละหน้าครั้งล่าสุด ซึ่งอาจทำได้ 2 วิธีคือ

• ใช้ตัวนับ (counters) วิธีนี้ทำได้ง่าย ๆ โดยการเพิ่ม field เข้าไปในตารางเลขหน้า อีก field หนึ่ง เพื่อใช้เก็บเวลาที่หน้านั้นถูกอ้างอิง และกำหนดนาฬิกาเทียม (logical clock) หรือ ตัวนับ (counter) นาฬิกานี้จะเพิ่มค่าทุก ๆ ครั้งที่มีการอ้างอิงหน่วยความจำ เมื่อมีการอ้างอิงหน้าใด ระบบก็จะเอาเลขเวลาเขียนลงในช่องเก็บเวลาของหน้านั้น ๆ (ในตารางเลขหน้า) โดยวิธีนี้เราจะได้เวลาที่แต่ละหน้าถูกอ้างอิงครั้งล่าสุด เมื่อต้องการหน้าว่าง เราก็เพียงแต่เลือกหน้าที่มีเลขเวลาน้อยที่สุดเพื่อสับเปลี่ยนออก

จะเห็นได้ว่าวิธีนี้จะต้องมีการตรวจดูเลขเวลาในตารางเลขหน้าทั้งตาราง เพื่อที่จะหาค่าที่น้อยที่สุด เลขเวลาเหล่านี้จะต้องติดไปกับตารางเลขหน้า เมื่อมีการเปลี่ยนตาราง (เนื่องจากการจัดตารางการทำงานของหน่วยประมวลผลกลาง) นาฬิกาเทียมอาจเพิ่มค่าขึ้นเรื่อย ๆ จนเกินค่าสูงสุดที่จะรับได้ เราจึงต้องมีวิธีการจัดการเรื่องนี้ด้วย

• ใช้ stack เราอาจใช้ stack เก็บเลขหน้า แทนวิธีใช้นาฬิกาได้ โดยเมื่อมีการอ้างอิงหน้าใด เราก็จะเอาเลขหน้านั้นออกจาก stack แล้วมาวางไว้บนหัว stack ซึ่งจะทำให้ส่วนหัวของ stack เป็นเลขหน้าที่เพิ่งใช้ไป และด้านหางของ stack จะเป็นเลขหน้าที่ใช้มาแล้วนานที่สุด   

แสดงการใช้ stack เพื่อบันทึกการอ้างอิงหน้าที่ถูกใช้มาแล้วนานที่สุด

 

เนื่องจากต้องมีการเอาเลขหน้าออกจากกลาง stack จึงควรสร้าง stack โดยใช้ตัวชี้ 2 ทาง (Doubly linked list) ภายใน stack และมีตัวชี้ที่ส่วนหัว และส่วนหางของ stack ด้วย การเอาเลขหน้าออกจากกลาง stack ไปไว้บนส่วนหัว สามารถทำได้โดยการแก้ไขตัวชี้เหล่านี้ อย่างมากไม่เกิน 6 ตัว จะเห็นได้ว่าการแก้ไข stack ก็เสียเวลาเหมือนกัน แต่ไม่จำเป็นต้องค้นหาหน้าที่จะสับเปลี่ยนเลย เพราะสามารถเลือกหน้าที่อยู่ส่วนหางของ stack ได้ทันที (ซึ่งเป็นหน้าที่ใช้มานานที่สุด) วิธีนี้เหมาะกับการเขียนโปรแกรมถาวร หรือ โปรแกรมลงในฮาร์ดแวร์ (microcode)

ทั้งแบบที่ดีที่สุด และแบบใช้มานานสุด-ออกก่อน (OPT และ LRU) จะไม่เกิดปรากฏการณ์เบลาดี้ กลุ่มของแบบที่ไม่เกิดปรากฏการณ์เบลาดี้นี้เรียกว่า “กลุ่มแบบ stack” (Stack Algorithm) คือ แบบที่สามารถพิสูจน์ได้ว่า “เซตของหน้าที่อยู่ในหน่วยความจำจริง ขนาด n หน้า จะเป็นสับเซต ของเซตของหน้าที่อยู่ในหน่วยความจำจริงขนาด n + 1 หน้า”

ตัวอย่างสำหรับขั้นตอนวิธีแบบ LRU เซตของหน้าที่อยู่ในหน่วยความจำจริงขนาด n หน้า ก็คือ หน้าที่ถูกใช้ไปครั้งล่าสุด ก็จะยังคงเดิม เพียงแต่เพิ่มหน้าใหม่เข้ามาอีก 1 หน้า ดังนั้นแบบ LRU เป็นกลุ่มแบบ stack

จะเห็นได้ว่าการสร้างระบบหรือเขียนโปรแกรมโดยใช้ขั้นตอนแบบ LRU ต้องมีฮาร์ดแวร์ช่วย การเพิ่มนาฬิกาหรือการย้ายเลขหน้าใน stack จะเกิดขึ้นทุกครั้งที่มีการอ้างอิงหน่วยความจำ ถ้าเราใช้โปรแกรมช่วยแทนโดยส่งสัญญาณไปขัดจังหวะระบบให้โปรแกรมทำงานจะทำให้การอ้างอิงหน่วยความจำแต่ละครั้งเสียเวลาอีกอย่างน้อย 10 เท่าของการอ้างอิงปกติ ซึ่งหมายความว่าการทำงานของทั้งระบบจะช้าลง 10 เท่าด้วย ! ดังนั้นจึงไม่มีระบบใดยอมรับการใช้โปรแกรมช่วยแทนฮาร์ดแวร์ช่วยได้

  การเลียนแบบ LRU (LRU Approximation Algorithms)

ระบบส่วนใหญ่ไม่อาจจัดหาฮาร์ดแวร์มาช่วยในการสร้างการสับเปลี่ยนหน้าแบบ LRU ได้ บางระบบที่ไม่มีฮาร์ดแวร์ช่วยเลย ก็จำต้องใช้วิธีอื่น ๆ (เช่น FIFO) แทน หลายระบบมีฮาร์ดแวร์ช่วยเล็กน้อย โดยเพิ่ม บิตอ้างอิง (Reference bit) 1 บิต ลงในตารางเลขหน้า เมื่อหน้านั้น ๆ ถูกอ้างอิง (ไม่ว่าจะเป็นการอ่านหรือการเขียน) บิตนี้ก็จะถูกแก้ไขเป็น “ใช้แล้ว” (1)

เริ่มต้นระบบปฏิบัติการจะจัดตั้งค่าบิตอ้างอิง เป็น “ยังไม่ใช้” (0) เมื่อกระบวนการผู้ใช้อ้างอิงหน้า บิตอ้างอิงที่คู่กับหน้านี้ก็จะถูกแก้ค่าโดยฮาร์ดแวร์เป็น “ใช้แล้ว” (1) เมื่อเวลาผ่านไปเราจึงอาจตรวจดูได้ว่า หน้าใดบ้าง ถูกใช้แล้ว หน้าใด ยังไม่ใช้ โดยดูที่บิตอ้างอิงนี้ ถึงแม้ว่าเราจะไม่สามารถรู้ลำดับว่าหน้าใดถูกใช้ก่อน-หลัง แต่รู้เพียงว่าถูกใช้แล้วหรือยัง เราก็อาจประมาณการณ์หรือเลียนแบบวิธี LRU ได้

  แบบใช้บิตอ้างอิงหลายตัว (Additional-Reference-Bits Algorithm)

เราอาจจะเพิ่มข้อมูลในการเรียงลำดับโดยใช้บิตอ้างอิงหลายตัวเก็บค่าการอ้างอิงในแต่ละช่วงเวลา เช่น เก็บไว้ 8 บิต (1 ไบต์) ต่อหน้า (ในตารางเลขหน้า) และทุก ๆ ช่วงเวลา (เช่น ทุก ๆ 100 มิลลิวินาที) นาฬิกาปลุกที่ตั้งไว้จะส่งสัญญาณมาขัดจังหวะให้ระบบปฏิบัติการเลื่อนบิตอ้างอิง (8บิต) ของแต่ละหน้าไปทางขวา 1 บิต (shift right) ดังนั้นข้อมูลจากบิตอ้างอิง 8 บิตนี้ จะแสดงการอ้างอิงหน้านั้น ๆ ในช่วงเวลา 8 ช่วงที่ผ่านมา เช่น ถ้าค่าบิตอ้างอิงเป็น 00000000 แสดงว่าหน้านี้ไม่ถูกอ้างอิงเลยตลอด 8 ช่วงเวลาที่ผ่านมา ถ้าค่าบิตอ้างอิงเป็น 11111111 แสดงว่าหน้านี้ถูกอ้างอิงอย่างน้อย 1 ครั้ง ทุก ๆ ช่วงเวลา 8 ช่วงที่ผ่านมา

หน้าที่มีค่าบิตอ้างอิง 11000100 แสดงว่า ถูกอ้างอิงไปก่อนเมื่อเทียบกับหน้าที่มีค่าบิตอ้างอิงเป็น 01110111 ดังนั้นหน้าที่มีค่าบิตอ้างอิง (เมื่อคิดเป็นเลขจำนวนเต็มบวก) น้อยที่สุดก็จะเป็นหน้า LRU (ใช้มานานที่สุด) จะสังเกตเห็นว่า ค่าบิตอ้างอิงของแต่ละหน้าอาจมีค่าเท่ากันก็ได้ ซึ่งเราอาจเลือกย้ายออกไปทั้งหมดเลย หรือใช้วิธีมาก่อน-ออกก่อนมาช่วยก็ได้

จำนวนบิตอ้างอิงที่ใช้นี้อาจเป็นเท่าใดก็ได้ (ไม่จำเป็นต้องเป็น 8 บิต) ขึ้นอยู่กับฮาร์ดแวร์ที่มีและเลือกจำนวนที่สามารถแก้ไขค่าได้เร็วที่สุด หรืออาจมีน้อยบิตที่สุด คือ ไม่มีบิตแสดงอดีตเลย เหลือเพียงบิตอ้างอิง 1 บิต เช่น วิธี “ให้โอกาสอีกครั้ง” (Second Chance Algorithm) ที่จะกล่าวต่อไป

  
แบบให้โอกาสอีกครั้ง (Second Chance Algorithm)

วิธีการนี้ใช้การจัดเรียงแบบ FIFO (มาก่อน-ออกก่อน) เมื่อเลือกได้แล้วจะดูที่บิตอ้างอิง ถ้าบิตอ้างอิง มีค่าเป็น “0” ก็จะเปลี่ยนหน้านี้ออกไป ถ้าบิตอ้างอิงมีค่าเป็น “1” เราจะให้โอกาสหน้านี้อีกครั้งหนึ่ง โดยแก้ไขบิตอ้างอิงของหน้านี้ให้เป็น “0” และแก้ไขเวลามาถึง (เวลาที่หน้านี้ถูกนำเข้ามาในหน่วยความจำ) เป็นเวลาปัจจุบัน แล้วตรวจหาหน้าต่อไป ในการเรียงแบบ FIFO จะเห็นได้ว่าหน้านี้ (ซึ่งได้รับโอกาสอีกครั้งหนึ่ง) จะไม่ถูกเลือกสับเปลี่ยนออกไป จนกว่าหน้าอื่น ๆ ทั้งหมดจะถูกสับเปลี่ยนออก (หรือได้รับโอกาสอีกครั้งหนึ่ง) ส่วนหน้าที่ถูกอ้างอิงบ่อย ๆ บิตอ้างอิงก็จะถูกแก้เป็น “1” บ่อย ๆ จนไม่อาจถูกเลือกออกได้

เราอาจสร้างระบบตามขั้นตอนวิธีแบบให้โอกาสอีกครั้ง โดยใช้แถวคอยแบบวงกลม (บางทีเรียกว่าแบบนาฬิกา) มีตัวชี้ ชี้ไปยังหน้าที่ถูกเลือกในครั้งต่อไป เมื่อระบบต้องการหน้าว่าง ตัวชี้จะเลื่อนไปเรื่อย ๆ จนพบหน้าที่บิตอ้างอิงเป็น “0” โดยเมื่อเลื่อนผ่านหน้าใด ก็จะแก้ไขบิตอ้างอิงของหน้านั้นเป็น “0” ไปด้วย (แน่นอนเดิมต้องเป็น “1” มิฉะนั้นจะถูกเลือกทันที) ดูรูปที่ 9.13 ประกอบ

รูปที่ แสดงการสับเปลี่ยนหน้าแบบให้โอกาสอีกครั้ง

ในกรณีที่บิตอ้างอิงของทุก ๆ หน้าเป็น “1” หมด ตัวชี้ก็จะเลื่อนผ่านไปทั้งวงกลมเลย โดยให้โอกาสอีกครั้งกับทุก ๆ หน้า และวนกลับมายังหน้าแรก (ซึ่งตอนนี้บิตอ้างอิงเป็น “0” แล้ว) ดังนั้นถ้ามีการใช้ทุก ๆ หน้าบ่อยมาก แบบให้โอกาสอีกครั้ง ก็จะกลายมาเป็น แบบมาก่อน-ออกก่อน

แบบใช้บิตคู่ (Enhanced Second-Chance Algorithm)

ยังมีวิธีการสับเปลี่ยนหน้าอีกมาก อีกแบบหนึ่งที่ง่าย ๆ ก็คือ การใช้ “บิตคู่” บิตอ้างอิงและบิตแก้ไข (Reference Bit and Modify bit) คู่กัน และจัดหน้าเป็นกลุ่ม ๆ ดังนี้

• (0 , 0) แสดงว่า ไม่ถูกใช้และไม่ถูกแก้ไข - เป็นหน้าที่ดีที่สุดที่จะถูกแทนที่
• (0 , 1) แสดงว่า ไม่ได้ถูกใช้(เร็ว ๆ นี้) แต่ถูกแก้ไข – เป็นหน้าไม่ค่อยดีนักเพราะหน้านี้จำเป็นต้องถูกเขียนก่อนจะถูกแทนที่
• (1 , 0) แสดงว่า ถูกใช้แต่ไม่ได้แก้ไข – เป็นไปได้ว่าจะถูกใช้อีกครั้งเร็ว ๆ นี้
• (1 , 1) แสดงว่า ถูกใช้และถูกแก้ไข – เป็นไปได้ว่าจะถูกใช้อีกครั้งและจำเป็นต้องถูกเขียนก่อนที่จะถูกแทนที่

การเลือกหน้าออก จะเลือกที่กลุ่มล่างสุดก่อน (lowest nonempty class) โดยภายในกลุ่มอาจใช้วิธี มาก่อน-ออกก่อน หรือเลือกแบบสุ่มก็ได้

แบบนับ (Counting Algorithm)

แบบใช้น้อย-ออกก่อน (LFU Algorithm)

การสับเปลี่ยนหน้าแบบใช้น้อย-ออกก่อน (Least Frequently Used) ทำได้ โดยเก็บจำนวนครั้งที่หน้าถูกอ้างอิง และเลือกหน้า ที่ถูกอ้างอิงน้อยที่สุดออกก่อน เหตุผลง่าย ๆ ก็คือ หน้าที่ถูกอ้างอิงมากครั้ง น่าจะเป็นหน้าที่ต้องการใช้ในปัจจุบัน วิธีนี้มีข้อเสีย คือ หน้าบางหน้าอาจถูกอ้างอิงบ่อยมาก ในช่วงแรก ๆ ของการทำงาน แต่ต่อมาอาจไม่ถูกใช้อีกเลย หน้านี้ก็จะอยู่ในหน่วยความจำตลอดไป ทั้ง ๆ ที่ไม่ต้องการใช้อีกแล้ว (เพราะเลขจำนวนครั้งที่ถูกอ้างอิงมีค่ามาก) เราอาจแก้ไขปัญหานี้โดย เลื่อนบิตไปทางขวาทุก ๆ ช่วงเวลา ทำให้ค่าจำนวนครั้งลดลงได้

แบบใช้มาก-ออกก่อน (MFU Algorithm)

วิธีการสับเปลี่ยนหน้าอีกแบบหนึ่งก็คือ แบบใช้มาก-ออกก่อน (Most Frequently Used) โดยมีแนวคิดว่า หน้าที่มีจำนวนการใช้น้อยน่าจะเป็นหน้าที่เพิ่งถูกนำเข้ามาในหน่วยความจำ

เนื่องจากทั้งแบบใช้น้อย-ออกก่อนและแบบใช้มาก-ออกก่อน มีค่าใช้จ่ายสูง และให้ผลไม่ใกล้เคียงแบบ OPT เลย จึงไม่นิยมใช้
 

วิธีการช่วยเสริม (Page Buffering Algorithm)

นอกจากวิธีการสับเปลี่ยนหน้าแบบต่าง ๆ ที่กล่าวมาแล้ว ยังมีวิธีการช่วยเสริมหรือเพิ่มเติมให้วิธีหลักมีประสิทธิภาพมากขึ้น เช่น ระบบมักจะเก็บหน้าว่างไว้เป็นกลุ่ม (pool) (หลายหน้า) เมื่อเกิดการผิดหน้าจะมีการเลือก “ผู้เสียสละ” (แต่ยังไม่ย้ายออกไป) ระบบจะอ่านหน้าที่ต้องการเข้ามาในเนื้อที่ที่ว่างได้เลย (ไม่ต้องรอให้มีการย้ายหน้าเดิมออกไปก่อน) ทำให้ลดเวลาในการย้ายหน้าลงมาก เมื่อระบบมีเวลาว่างค่อยย้ายหน้าที่เลือกไว้ออกไป แล้วเอาเนื้อที่ว่างมาไว้ในกลุ่มหน้าว่าง

เราอาจขยายแนวคิดนี้ออกไปอีก โดยเก็บหมายเลขหน้าที่ถูกแก้ไขไว้ เมื่อระบบหรืออุปกรณ์สับเปลี่ยนหน้าว่างงาน ก็ให้คัดลอกหน้าที่ถูกแก้ไขนี้ไปทับค่าในจานบันทึก และเปลี่ยนบิตแก้ไขเป็น “0” วิธีนี้จะช่วยให้เมื่อต้องเลือกหน้าออก โอกาสที่หน้านั้น ๆ จะไม่ได้ถูกแก้ไข มีมากขึ้นทำให้ไม่ต้องเสียเวลาในการเขียนหน้าออกไป

หรืออาจเก็บหน้าว่างไว้เป็นกลุ่มและบันทึกไว้ด้วยว่าหน้าว่างใด มีข้อมูลของหน้าจริงใดอยู่ (เนื่องจากข้อมูลเดิมยังอยู่ ยังไม่ได้ถูกเขียนทับโดยหน้าใหม่) ดังนั้นถ้ากระบวนการต้องการหน้านี้อีก ก็อาจเรียกกลับมาใช้ได้ โดยไม่ต้องย้ายหน้าเข้าหรือออกไปยังจานบันทึก เมื่อมีการผิดหน้าระบบเพียงแต่ตรวจดูจากกลุ่มหน้าว่างนี้ว่ามีหน้าที่ต้องการอยู่หรือไม่ ? ถ้าไม่ก็คงต้องเลือกหน้าว่างมาหน้าหนึ่งและอ่านหน้าที่ต้องการจากบันทึกเข้ามา

วิธีการหลังนี้ใช้ในระบบปฏิบัติการ VAX/VMS เพื่อช่วยวิธีการหลัก ซึ่งเป็นแบบมาก่อน-ออกก่อน เมื่อแบบ FIFO สับเปลี่ยนหน้าที่ต้องการใช้บ่อยออกไปโดยบังเอิญ หน้านั้น ๆ ก็จะถูกนำกลับมาใช้ใหม่ โดยไม่ต้องอ่านเข้ามาอีก เพราะยังอยู่ในกลุ่มหน้าว่าง จึงเป็นการช่วยปรับปรุง ข้อเสียของแบบมาก่อน-ออกก่อน ให้ดีกว่าเดิม

ที่มา : http://bc.feu.ac.th/pichate/os_c9/chapter9.htm