ขั้นตอนการสับเปลี่ยนหน้าPage-Replacement Algorithm

1.แบบมาก่อนออกก่อน(FIFO)

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

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

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

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

เพื่อให้เกิดการผิดหน้าต่ำสุดและย่อมไม่เกิดปรากฏการณ์เบลาดี้  คือสับเปลื่ยนหน้าที่ถูกเรียกใช้ในอนาคตอันไกลที่สุด 

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

3.มานานที่สุดออกก่อน(LRU Alorithm)

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

• ใช้ตัวนับ(Counters)

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

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

• ใช้stack

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

แบบOPT, LRU ไม่เกิดปรากฏการณ์เบลาดี้ กลุ่มของแบบที่ไม่เกิดเบลาดี้ เรียกว่า stack algorithm คือแบบที่พิสูจน์ได้ว่า"setของหน้าที่อยู่ในหน่วยความจำ n หน้า จะเป็นsubsetของsetของหน้าที่อยู่ในหน่วยความจำจริงขนาก n+1 หน้า"

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

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