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

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

   (VIRTUAL MEMORY) 

เราได้อธิบายวิธีการจัดการหน่วยความจำหลักแบบต่าง ๆ ซึ่งมีการใช้ในระบบคอมพิวเตอร์หลายระบบ วิธีการต่าง ๆ ที่กล่าวมามีหลักการเดียวกัน คือ พยายามให้มีกระบวนการอยู่ในหน่วยความจำหลัก พร้อม ๆ กันมากตัวที่สุด เพื่อให้สามารถทำงานแบบ multiprogramming ได้ ในระดับสูงที่สุด (high degree of multiprogramming) แต่ทุกแบบต้องนำกระบวนการทั้งตัวบรรจุลงในหน่วยความจำหลัก ก่อนที่จะให้กระบวนการทำงาน
หน่วยความจำเสมือน (Virtual Memory) เป็นวิธีการที่สามารถให้กระบวนการทำงานได้แม้จะไม่ได้อยู่ในหน่วยความจำหลักทั้งตัวก็ตาม ข้อดีหลักของวิธีนี้ที่เห็นได้ชัด คือ โปรแกรมของผู้ใช้อาจมีขนาดใหญ่กว่าหน่วยความจำจริงก็ได้ วิธีนี้สร้างหน่วยความจำทางตรรกะให้ดูเสมือนเป็นแถวลำดับ (Array) ขนาดใหญ่ โดยแยกภาพที่ผู้ใช้มองเห็นหน่วยความจำออกจากลักษณะจริงของฮาร์ดแวร์ ทำให้ผู้เขียนโปรแกรมสามารถเขียนโปรแกรมได้อย่างอิสระไม่ต้องกังวลถึงขนาดของหน่วยความจำอีกต่อไป การสร้างหน่วยความจำเสมือนไม่ใช่ของง่าย และอาจทำให้ประสิทธิผลของระบบลดลงได้อย่างมาก ถ้าไม่รอบคอบพอ ในบทนี้เราจะวิเคราะห์หน่วยความจำเสมือนในระบบจัดสรรหน้าตามคำร้องขอ (Demand Paging) เพื่อดูความซับซ้อนของระบบและค่าใช้จ่ายที่เกิดขึ้น
ความเป็นมา (Background)
เราจำเป็นต้องมีวิธีการจัดการหน่วยความจำหลักแบบต่าง ๆ ที่กล่าวมาแล้วในบทที่ 8 เพราะข้อจำกัดที่ว่ากระบวนการทั้งตัวจะต้องอยู่ในหน่วยความจำจริง ก่อนที่จะเริ่มทำงานได้ ซึ่งข้อจำกัดนี้ เป็นสิ่งจำเป็นและสมเหตุสมผล แต่ทำให้ขนาดของโปรแกรมถูกจำกัดด้วยขนาดของหน่วยความจำหลัก
ถ้าเราตรวจดูโปรแกรมทั่วไปจะพบว่า หลายส่วนของโปรแกรมไม่จำเป็นต้องใช้ เช่น

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

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

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

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

รูปที่ 1 แผนภาพแสดงหน่วยความจำเสมือนมีขนาดใหญ่กว่าหน่วยความจำทางกายภาพ

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

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

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

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

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

รูปที่ 4 ขั้นตอนในการจัดการการผิดหน้า (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) ดูรูปที่ 5 ประกอบ

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

 

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

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

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

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

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

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

ดังนั้นเราอาจแก้ไขขั้นตอนในการจัดการ “การผิดหน้า” (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 หน้าเท่านั้น
ขั้นตอนวิธีการสับเปลี่ยนหน้าจะหาเนื้อที่ว่างให้ได้เสมอเมื่อต้องการ หน้าที่ถูกสับเปลี่ยนออกจะถูเขียนกลับไว้ในจานบันทึก ซึ่งถ้ามีการอ้างอิงหน้านี้อีก ก็จะเกิดการผิดหน้าขึ้น ทำให้หน้านี้ถูกนำกลับมาไว้ในหน่วยความจำอีก โดยสับเปลี่ยนกับหน้าอื่น ๆ ในหน่วยความจำ
ปัญหาหลักของวิธีการจัดสรรหน้าตามคำร้องขอ คือ ต้องมีขั้นตอนวิธีในการหาเนื้อที่ว่างหรือหน้าผู้เสียสละ และขั้นตอนวิธีในการสับเปลี่ยนหน้า ในระบบที่มีหลายกระบวนการทำงานพร้อมกัน เราต้องตัดสินใจว่าจะให้เนื้อที่สำหรับแต่ละกระบวนการกี่หน้า และเมื่อต้องการเนื้อที่ว่างเราก็ต้องตัดสินใจว่าจะเลือกหน้าใดออก การออกแบบขั้นตอนวิธีในการแก้ปัญหาเหล่านี้เป็นสิ่งสำคัญต่อระบบมาก เพราะเวลาที่เสียไปในการส่งข้อมูลไปและกลับจากจานบันทึกมีเป็นค่าใหญ่มาก การปรับปรุงขั้นตอนวิธีให้ดีขึ้นเพียงเล็กน้อย อาจทำให้ประสิทธิภาพของระบบโดยรวมดีขึ้นอย่างมากได้
9.5 ขั้นตอนวิธีการสับเปลี่ยนหน้า (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 ครั้ง โดยปกติเมื่อจำนวนหน้าจริงมีมากขึ้น จำนวนการผิดหน้าก็จะลดลง ดังรูปกราฟที่ 7

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

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

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

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

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

 

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

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

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

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

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

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

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

รูปที่ 11 ใช้การสับเปลี่ยนหน้าแบบใช้มานานสุด-ออกก่อน เกิดการผิดหน้าทั้งหมด 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 จะเป็นเลขหน้าที่ใช้มาแล้วนานที่สุด (ดูรูปที่ 12)

รูปที่ 12 แสดงการใช้ 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 เท่าด้วย ! ดังนั้นจึงไม่มีระบบใดยอมรับการใช้โปรแกรมช่วยแทนฮาร์ดแวร์ช่วยได้
9.5.4 การเลียนแบบ LRU (LRU Approximation Algorithms)
ระบบส่วนใหญ่ไม่อาจจัดหาฮาร์ดแวร์มาช่วยในการสร้างการสับเปลี่ยนหน้าแบบ LRU ได้ บางระบบที่ไม่มีฮาร์ดแวร์ช่วยเลย ก็จำต้องใช้วิธีอื่น ๆ (เช่น FIFO) แทน หลายระบบมีฮาร์ดแวร์ช่วยเล็กน้อย โดยเพิ่ม บิตอ้างอิง (Reference bit) 1 บิต ลงในตารางเลขหน้า เมื่อหน้านั้น ๆ ถูกอ้างอิง (ไม่ว่าจะเป็นการอ่านหรือการเขียน) บิตนี้ก็จะถูกแก้ไขเป็น “ใช้แล้ว” (1)
เริ่มต้นระบบปฏิบัติการจะจัดตั้งค่าบิตอ้างอิง เป็น “ยังไม่ใช้” (0) เมื่อกระบวนการผู้ใช้อ้างอิงหน้า บิตอ้างอิงที่คู่กับหน้านี้ก็จะถูกแก้ค่าโดยฮาร์ดแวร์เป็น “ใช้แล้ว” (1) เมื่อเวลาผ่านไปเราจึงอาจตรวจดูได้ว่า หน้าใดบ้าง ถูกใช้แล้ว หน้าใด ยังไม่ใช้ โดยดูที่บิตอ้างอิงนี้ ถึงแม้ว่าเราจะไม่สามารถรู้ลำดับว่าหน้าใดถูกใช้ก่อน-หลัง แต่รู้เพียงว่าถูกใช้แล้วหรือยัง เราก็อาจประมาณการณ์หรือเลียนแบบวิธี LRU ได้
9.5.4.1 แบบใช้บิตอ้างอิงหลายตัว (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) ที่จะกล่าวต่อไป
9.5.4.2 แบบให้โอกาสอีกครั้ง (Second Chance Algorithm)
วิธีการนี้ใช้การจัดเรียงแบบ FIFO (มาก่อน-ออกก่อน) เมื่อเลือกได้แล้วจะดูที่บิตอ้างอิง ถ้าบิตอ้างอิง มีค่าเป็น “0” ก็จะเปลี่ยนหน้านี้ออกไป ถ้าบิตอ้างอิงมีค่าเป็น “1” เราจะให้โอกาสหน้านี้อีกครั้งหนึ่ง โดยแก้ไขบิตอ้างอิงของหน้านี้ให้เป็น “0” และแก้ไขเวลามาถึง (เวลาที่หน้านี้ถูกนำเข้ามาในหน่วยความจำ) เป็นเวลาปัจจุบัน แล้วตรวจหาหน้าต่อไป ในการเรียงแบบ FIFO จะเห็นได้ว่าหน้านี้ (ซึ่งได้รับโอกาสอีกครั้งหนึ่ง) จะไม่ถูกเลือกสับเปลี่ยนออกไป จนกว่าหน้าอื่น ๆ ทั้งหมดจะถูกสับเปลี่ยนออก (หรือได้รับโอกาสอีกครั้งหนึ่ง) ส่วนหน้าที่ถูกอ้างอิงบ่อย ๆ บิตอ้างอิงก็จะถูกแก้เป็น “1” บ่อย ๆ จนไม่อาจถูกเลือกออกได้
เราอาจสร้างระบบตามขั้นตอนวิธีแบบให้โอกาสอีกครั้ง โดยใช้แถวคอยแบบวงกลม (บางทีเรียกว่าแบบนาฬิกา) มีตัวชี้ ชี้ไปยังหน้าที่ถูกเลือกในครั้งต่อไป เมื่อระบบต้องการหน้าว่าง ตัวชี้จะเลื่อนไปเรื่อย ๆ จนพบหน้าที่บิตอ้างอิงเป็น “0” โดยเมื่อเลื่อนผ่านหน้าใด ก็จะแก้ไขบิตอ้างอิงของหน้านั้นเป็น “0” ไปด้วย (แน่นอนเดิมต้องเป็น “1” มิฉะนั้นจะถูกเลือกทันที) ดูรูปที่ 13 ประกอบ

รูปที่ 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 สับเปลี่ยนหน้าที่ต้องการใช้บ่อยออกไปโดยบังเอิญ หน้านั้น ๆ ก็จะถูกนำกลับมาใช้ใหม่ โดยไม่ต้องอ่านเข้ามาอีก เพราะยังอยู่ในกลุ่มหน้าว่าง จึงเป็นการช่วยปรับปรุง ข้อเสียของแบบมาก่อน-ออกก่อน ให้ดีกว่าเดิม