บทที่5การจัดการหน่วยของความจำ

บทที่ 5
การจัดการอยู่หน่วยความจำ(memory Management)
หนึ่งในปัญหาหลายๆข้อที่ยากต่อการออกแบบระบบปฏิบัติการ คือ การจัดการกับหน่วยความจำ ในอดีตการประหยัดเนื้อที่ของหน่วยความจำเป็นสิ่งที่จำเป็นในการออกแบบระบบปฏิบัติการ เพราะว่าในสมัย 10-20 ปีที่แล้ว คอมพิวเตอร์มีหน่วยความจำเพียงไม่กี่เมกะไบต์ (Mega byte)
และถ้าเราสามารถประหยัดเนื้อที่ของหน่วยความจำเพียงพันกว่าไบต์ได้ก็อาจจะสร้างความแตกต่างระหว่าง ความสำเร็จ หรือ ความล้มเหลวของการเรียกใช้โปรแกรมหนึ่งๆได้เลย เนื่องจากมีหน่วยความจำไม่เพียงพอให้โปรแกรมทำงานได้
ถึงแม้นว่าราคาของหน่วยความจำได้ลดลงอย่างมากในปัจจุบันเมื่อเทียบกับสมัยก่อน และขนาดของหน่วยความจำในเครื่องคอมพิวเตอร์รุ่นใหม่ๆก็มีขนาดเพิ่มขึ้นถึงระดับกิกะไบต์
(Giga byte) ก็ตาม ความต้องการหน่วยความจำของโปรแกรมและของโครงสร้างข้อมูลที่ต้องทำงาน
ร่วมกับโปรเซสหรือระบบปฏิบัติการก็ยังเป็นที่ต้องการอยู่อีกมาก ดังนั้นจึงเป็นหน้าที่หลัก
ของระบบปฏิบัติการที่จะต้องทำการจัดการหน่วยความจำ วึ่งเกี่ยวข้องกับการดึงหน่วยความจำ
ซึ่งแบ่งออกเป็น 2 ส่วนใหญ่ คือ การจัดการกับหน่วยความจำหลัก(memory Management)
และจัดการกับหน่วยความจำเสมือน(virtual memory Management)
5.1 หน่วยความจำหลัก(Main Memory)
จากบทที่ผ่านๆมา เราอาจกล่าวได้ว่า หน่วยความจำหลัก เป็นศูนย์กลางของการทำงานต่างๆของระบบคอมพิวเตอร์ในปัจจุบัน หน่วยความจำหลักในพื้นที่
เก็บข้อมูลขนาดเป้นไบต์(byte) โดยแต่ละไบต์จะมีแอดเดรส(address) บอกตำแหน่งของตัวเอง และโดยทั่วไปแล้วโปรแกรมเมอร์ล้วนแต่ต้องการระบบที่มีหน่วยความจำหลักแบบไม่จำกัด,
มีความเร็วสูง,และมีหน่วยความจำที่มีความเสถียรสูงหรือเป้นแบบไม่ถูกลบเลือน ซึ่งหมายความว่า
ถึงแม้นว่าระบบไฟฟ้าจะขัดข้องข้อมูลต่างๆในหน่วยความจำหลักเหล่านั้นก็ไม่สูญหายไปด้วย
นอกจากนี้เราเพิ่มไปด้วยว่า“ถ้ามีราคาถูกด้วยก็ยิ่งดี” แต่ในความเป็นจริงแล้วเทคโนโลยีปัจจุบัน
ไม่สามารถให้เราได้มากถึงขนาดนั้น ดังนั้นระบบคอมพิวเตอร์ในปัจจุบันจึงมีการแบ่งหน่วยความ
จำออกเป็นชั้นๆ(Memory hierarchy)ได้ดังนี้
1.หน่วยความจำขนาดเล็ก,มีความเร็วสูง,ราคาแพงมากและเป็นหน่วยความจำที่เป็นแบบลบเลือนได้
2.หน่วยความจำขนาดกลาง(ประมาณ 10-100 กิกะไบต์ขึ้นไป),มีความเร็วปานกลาง,ราคาปานกลาง
และเป็นหน่วยความจำที่เป็นแบบลบเลือนได้
3.หน่วยความจำขนาดใหญ่(ประมาณ 10-100 กิกะไบต์),ที่มีความเร็วต่ำราคาถูก,และเป็นดิสก์เก็บ
ข้อมูลที่เป็นแบบไม่ถูกลบเลือน
ส่วนของระบบปฏิบัติการ ที่ใช้ในการจัดการกับหน่วยความจำของลำดับชั้นต่างๆจะถูก
เรียกว่า ตัวจัดการหน่วยความจำซึ่งมีหน้าที่ในการตรวจสอบว่าส่วนใดของหน่วยความจำที่กำลังถูก
ใช้งาน,ส่วนใดที่วางอยู่,ทำหน้าที่จัดหน่วยความจำให้กับโปรเซสที่ทำงาน,เก็บหน่วยความจำเหล่า
นั้นกลับคืนสู่ระบบเมื่องานเสร็จ และจัดการสลับกับหน่วยความจำหลัก กับพื้นที่ฮาร์ดดิสก์ เมื่อหน่วยความจำหลักมีขนาดเล็กเกินไปที่จะให้โปรเซสทำงานได้
5.1.1 กระบวนการในการจัดการหน่วยความจำ
วิธีการและนโยบายที่ใช้ในการจัดการกับหน่วยความจำนั้น โดยทั่วไปจะต้องมีความ
สามารถพื้นฐาน หรือกระบวนการการจัดการทั้ง 5 วิธีดัง
1. การย้ายตำแหน่ง (Relocation)
2. การป้องกันพื้นที่(Protection)
3. การใช้พื้นที่ร่วมกัน(sharing)
4. การจัดการแบ่งโปรแกรมย่อย( Logical Organization)
5. การจัดการแบ่งทางกายภาพ(Physical Organization)
ก่อนที่เราจะเรียนรู้ถึงวิธีการจัดการกับหน่วยความจำแบบต่างๆเรามาเริ่มต้นที่นิยาม
และการทำงานของกระบวนการพื้นฐานเหล่านี้กัน
การย้ายตำแหน่ง (Relocation)
ในระบบปฏิบัติการเราสามารถทำงานหลายๆโปรแกรมพร้อมกันได้หรือมัลติโปรแกรมมิ่ง
นั้น โปรเซสต่างๆจะใช้ความจำหลักร่วมกัน ซึ่งโดยทั่วไปแล้วผู้ใช้งานจะไม่ทราบก่อนว่า ในขณะที่โปรแกรมของพวกเขาทำงานนั้น จะมีโปรแกรมอื่นๆ ใช้หน่วยความจำหลักอยู่หรือไม่
นอกจากนี้ เราคงต้องการให้ระบบให้ระบบสามารถสลับโปรแกรมที่ทำงานเข้าและออก(swap in and out) จากหน่วยความจำหลักได้ เพื่อให้การใช้งานโปรเซสเซอร์เป็นไปอย่างมีประสิทธิภาพ และเมื่อมีโปรแกรมใดถูกดึงออกไปจากพื้นที่แล้ว มันก้เป็นการยากที่เราจะบอกได้ว่า ระบบสามารถดึงโปรแกรมนั้นกับมาทำงานในพื้นที่เดิม
เนื่องจากเราไม่อาจทราบล่วงหน้าว่าโปรแกรมหนึ่งเข้าไปใช้งานหน่วยความจำหลักแล้ว
จะใช้พื้นที่ใด แล้วยังต้องอนุญาตให้โปรแกรมสามารถเปลี่ยนตำแหน่งภายในหน่วยความจำหลัก
นี้ได้ เนื่องจากการสลับที่ดังนั้นเราจะต้องสร้างเทคนิคที่ใช้ในการจัดการกับปัญหาดังกล่าวโดย
มีการกำหนดแอดเดรสของโปรแกรม



รูป 5.1 การกำหนดแอดเดรสให้กับโปรเซสในหน่วยความจำหลัก [OSID:P290]
จากรูป 5.1 ให้เราพิจารณาพื้นที่ใช้งานโปรเซสเราจะเห็นว่าระบบปฏิบัติการ จะต้องรู้ตำแหน่ง
ของข้อมูลตัวควบคุมโปรเซสและตำแหน่งเริ่มต้อนของโปรแกรม ระบบจึงสามารถเรียก
โปรแกรมนั้นมาทำงานได้ เนื่องจากระบบปฏิบัติการเป็นตัวจัดการกับหน่วยความจำ และรับผิด
ชอบในการนำดปรเซสต่างๆเข้ามาใช้งานในหน่วยความจำที่อยู่ของโปรแกรมจึงสามารถจัดการได้ง่ายนอกจากนั้นหน้าที่ของโปรเซสเซอร์และโปรแกรมระบบปฏิบัติการจะต้องมีความสามรถในการแปลงค่าตำแหน่งหน่วยความจำที่อ้างถึงในโปรแกรมไปเป็นตำแหน่งจริงในหน่วยความจำหลักได้
โดยปกติโปรแกรมของผู้ใช้งานจะต้องผ่าขั้นตอนหลายขั้นตอนในการเรียกใช้งาน ดังรูป 5.2



รูป 5. 2 ขั้นตอนต่างๆ ในการเรียกใช้งานของโปรแกรม[OSC6:P275]
แอดเดรส ของหน่วยความจำภายในโปรแกรมของผู้ใช้อาจแสดงได้หลายแบบแตกต่างกัน
ตามขั้นตอนต่างๆ ในโปรแกรมต้นฉบับ ตัวอย่างเช่น ในโปรแกรมมีตัวแปร a และคอมไพเลอร์
แปลตัวแปรนี้เป็นแอดเดรสแบบย้ายได้ เช่น ให้ตัวแปรนี้อยู่ในแอดเดรสระยะห่าง16ไบต์จากจุดเริ่ม
ต้นของโปรแกรม เมื่อโปรแกรมถูกโหลดเข้าไปในหน่วยความจำตำแหน่งที่ 84000 ตัวโหลดเดอร์ก็จะทำหน้าที่แปลงค่าแอดเดรสแบบย้ายได้ของตัวแปรนั้น ไปเป็นแอดเดรสจริง
ทางกายภาพซึ่งคือตำแหน่ง 84016 นั่นเอง ดังนั้นค่าของที่อยู่นั้นจะแบ่ง ออกเป้น 2 ค่าคือ
1. Absolute Address หรือแอดเดรสแท้จริงของโปรเซสที่อยู่ในพาติชั่นของหน่วยความจำ
2. Relative Adress หรือแอดเดรสของคำสั่งหรือโปรแกรมของโปรเซสจากการคอมไพล์
การป้องกันพื้นที่ (Protection)
ระบบควรมีความสามารถในการป้องกันโปรเซสแต่ละงานไม่ให้ถูกรบกวน
ทั้งที่ตั้งใจ หรือไม่ก็ตามจากโปรเซสอื่นๆ ซึ่งหมายความว่า โปรแกรมในโปรเซสอื่นๆ ไม่ควรจะ
เรียกใช้งานในพื้นที่หน่วยความจำที่ใช้โดยโปรเซสหนึ่งๆได้ นอกจากได้รับอนุญาตโดยโปรเซสนั้น
และเราอาจเห็นได้ว่าการที่ระบบต้องการความสามารถในการย้ายแอดเดรสนั้นจะทำให้ความ
สามารถในการย้ายแอดเดรสนั้นจะทำให้ความสามารถในการป้องกันพื้นที่ยากขึ้นเนื่องจากการหาแอดเดรสของโปรแกรมในหน่วยความจำหลักเมื่อระบบทำการคอมไพล์โปรแกรมนั้นเป็นไปได้ยากมาก ยิ่งกว่านั้นภาษาโปรแกรมในปัจจุบันส่วนใหญ่จะอนุญาตให้โปรแกรมสามารถคำนวนหา
แอดเดรสในหน่วยความจำได้เองในขณะที่โปรแกรมกำลังทำงาน เช่น การสร้างตัวแปรอาเรย์แบบ
มีขนาดไม่คงที่ ดังนั้นแอดเดรสที่อ้างถึงหน่วยความจำที่ถูกสร้างโดยโปรเซสใดๆ จะต้องถกตรวจสอบในขณะที่โปรแกรมกำลังทำงาน เพื่อให้แน่ใจว่าแอดเดรสที่อ้างถึงนั้น
จะอยู่ภายในพื้นที่ที่โปรเซสนั้นได้รับเท่านั้น
เราสามารถดุวิธีการป้องกันพื้นที่ของโปรเซสได้ดังรูป 5.1 โดยปกติแล้วนั้น โปรเซส
ของผู้ใช้งานนั้นจะไม่สามารถเข้าถึงพื้นที่ของระบบปฏิบัติการได้ ทั้งส่วนที่เป็นโปรแกรมหรือข้อมูล พร้อมกันนั้น โดยปกติโปรแกรมในโปรเซสหนึ่งๆ ก็ไม่ควรเรียกใช้คำสั่งหรือข้อมูลทีอยู่ในโปรเซสอื่นได้ และโปรเซสเซอร์จะต้องมีความสามารถในการยกเลิกคำสั่งใดถ้ามีการละเมิดการป้องกันดังกล่าวใน๘ณะทำงานได้ เราจะเห็นได้ว่าการป้องกันพื้นที่หน่วยความจำนั้นเป็นหน้าที่ของโปรเซสเซอร์มากกว่าเป้นหน้าที่ของระบบปฏิบัติการ ทั้งนี้เนื่องจากระบบปฏิบัติการไม่สามารถคาดเดาถึงแอดเดรสทีอ้างถึงทั้งหมดของโปรแกรมได้ และแม้ว่าระบบจะสามารถทำการคาดเดาได้ กระบวนการดังกล่าวก็จะกินเวลาในการค้นหา
แอดเดรสที่อ้างถึงของโปรแกรมแต่ละตัวมากเกินไป ดังนั้นวิธีที่เป็นไปได้ในการตรวจสอบการแอ๊กเซสหน่วยความจำของแอดเดรสที่อ้างถึงโปรแกรม
เป็นส่วนหนึ่งของฮาร์ดแวร์ที่มีความสามารถในการจัดการ
การใช้พื้นที่ร่วมกัน(Sharing) กระบวนการในการป้องกันพื้นที่บางครั้งอาจจะต้องมีการยืดหยุ่นบ้างเพื่อที่
จะอนุญาติให้โปรเซสหลายๆตัวมาใช้พื้นที่หน่วยความจำเดียวกันได้ เช่น ถ้ามีโปรเซสกลุ่มหนึ่ง
เรียกใช้โปรแกรมเดียวกัน มันอาจเป็นการดีถ้าเราอนุญาตให้โปรเซสแต่ละตัวได้เข้าถึงโปรแกรม
ส่วนนั้นได้ และดีกว่าที่จะให้โปรเซสแต่ละตัวก้อปปี้ และเรียกใช้งานโปรแกรมนั้นแยกกัน
บางครั้งโปรเซสที่ทำงานร่วมกันในบางงานก็ต้องมีความสามารถในการแบ่งปันข้อมูลร่วมกันได้
ดังนั้นระบบการจัดการหน่วยความจำจะต้องอนุญาตให้ตัวควบคุมสามารถเข้าถึงหน่วยความจำที่เป็นส่วนที่ใช้งานร่วมกันได้โดยไม่ต้องใช้วิธีการป้องกันพื้นที่ ปละเราอาจจะเห็นได้ว่ากระบวนการ
ที่ใช้ในการย้ายแอดเดรสนั้นสนับสนุนความคิดของการใช้พื้นที่ร่วมกันด้วย
การจัดแบ่งโปรแกรมย่อย(Logical Organization)
โดยปกติ หน่วยความจำหลักของคอมพิวเตอร์นั้นจะถูกจัดให้อยู่ในรูปของพื้นที่1มิติ
เป้นเส้นตรง มีช่องว่างและประกอบขึ้นจากแถวของไบต์ หรือคำ ในขณะที่การจัดการแบบนี้
มีลักษณะที่ใกล้เคียงกับฮาร์ดแวร์จริงๆแต่สำหรับซอร์ฟแวร์ หรือโปรแกรมนั้นจะมีการ
จัดการที่แตกต่างกัน โดยโปรแกรมส่วนมากจะถูกแบ่งออกเป็นโมดูล หรือโปรแกรมย่อยเพื่อให้
สามารถใช้งานหน่อยความจำได้อย่างมีประสิทธิภาพสูงสุด วิธีการที่ระบบปฏิบัติการจัดการก็คือ จะไม่นำโปรแกรมย่อยลงหน่วยความพร้อมโปรแกรมหลักแต่จะนำลงเมือมีการเรียกใช้เท่านั้นโดยโปรแกรมย่อยนั้นจะถูกบันทึกไว้ในดิสก์ในรูปแบบที่ย้ายแอดเดรสได้เมื่อโปรแกรมต้องการเรียกดปรแกรมย่อยใดก็จะตรวจว่าโปรแกรมย่อยนั้นอยู่ในความจำแล้วหรือยังถ้ายังก็นำโปรแกรมย่อยนั้น
ลงสู่หน่วยความจำหลัก โดยย้ายแอดเดรสลงที่ที่เหมาะสม และย้ายการควบคุมไปไว้ที่โปรแกรม
ย่อยนั้น เพื่อทำงานต่อไป ประโยชน์ของวิธีจัดการแบ่งโปรแกรมย่อยนี้คือ
- โปรแกรมย่อยที่ไม่ได้ใช้งาน จะไม่ถูกนำลงสู่หน่วยความจำหลักให้เสียพื้นที่
เปล่าๆ ซึ่งเหมาะกับโปรแกรมย่อยที่ไม่ค่อยเกิดขึ้น เช่น โปรแกรมจัดการข้อผิดพลาดต่างๆ เป็นต้น วิธีการนี้จะทำให้โปรแกรมหลักที่ใช้งานจริงมรขนาดเล็กลงกว่าโปรแกรมทั้งหมดมาก
- โปรแกรมย่อย แต่ละตัวสามารถถูกเขียนและคอมไพล์แยกกันได้ โดยการเชื่อม
โยงโปรแกรมย่อยแต่ละตัวนั้นเป้นหน้าที่ของระบบเมื่อมีการเรียกใช้งาน
- โปรแกรมย่อยแต่ละตัวสามารถมีระดับการป้องกันที่แตกต่างกันได้ เช่น โปรแกรมย่อยนี้ อ่านได้อย่างเดียว ในขณะที่ตัวอื่นสามารถอ่านเขียน และเอ๊กซีคิวต์ได้
- โปรแกรมหลักสามารถใช้โปรแกรมย่อยๆเหล่านี้ร่วมกันได้
เครื่องมือที่ใช้ในการจัดการนี้ คือ การแบ่งเป็นเซ็กเม้นซึ่งเป็นเทคนิกของการจัดการหน่วยความจำ
หลัก โดยจะกล่าวถึงในหัวข้อต่อไปนี้
การจัดการแบ่งทางกายภาพ(Physical Organization)
ตามที่ได้กล่าวมา หน่วยความจำของระบบคอมพิวเตอร์ควรแบ่งแบบเป็น 2 ระดับ ได้แก่
หน่วยความจำหลัก หน่วยความจำสำรอง โดยหน่วยความจำหลักเป้นหน่วยความจำที่มีความเร็วใน
การแอ๊กเซสข้อมูลสูงและมีราคาแพง นอกจากนั้นยังเป็นหน่วยความจำแบบลบเลือนได้
ในขณะที่หน่วยความจำสำรองมีความเร็วช้าราคาถูก แต่เป้นความจำแบบไม่ลบเลือน ดังนั้นหน่วยความจำสำรองที่มีความจุมากสามารถนำมาใช้เป็นที่เก็บโปรแกรมข้อมูลเป็นเวลานานได้ ในขณะที่หน่วยความจำหลักที่มีขนาดความจุเล้ก จะเก็บโปรแกรมหรือข้อมูลทำงานเท่านั้น
ในระบบที่มีหน่วยความจำ 2 แบบ ระบบควรคำนึงถึงการจัดการ การเคลื่อนย้ายข้อมูล
ระหว่างหน่วยความจำทั้ง 2 โดยอาจยกความรับผิดชอบดังกล่าวไปให้โปรแกรมๆหนึ่ง
จัดการแต่ผลลัพธ์ที่ได้ส่วนใหญ่ จะไม่สามารถใช้งานได้ตามต้องการเพราะ
- หน่วยความจำหลักอาจมีไม่เพียงพอสำหรับโปรแกรมนั้น ซึ่งทำให้ผู้เขียนโปรแกรม
ต้องใช้วิธีการแบ่งส่วน โดยโปรแกรมและข้อมูลนั้นจะถูกแบ่งให้เป้นโปรแกรมย่อยๆ
ที่สามารถใช้งานพื้นที่ในหน่วยความจำเดียวกันได้ และหน่วยความจำหลัก
จะเป็นตัวที่ทำการสับเปลี่ยนโปรแกรมย่อยเข้าออกเมื่อต้องการ
- ในระบบมัลติโปรแกรมมิ่ง ที่สามารถทำงานโปรแกรมหลายๆตัว พร้อมกันได้นั้น โปรแกรมเมอร์จะไม่สามารถทราบได้เลยว่าพื้นที่หน่วยความจำจะว่างเมื่อใด และอยู่ที่ใด
จากที่ได้กล่าวมา เราจะเห็นว่าการย้ายข้อมูลระหว่างหน่ววความจำทั้ง2 นั้นควรเป็นหน้าที่ของระบบและการจัดการแบ่งด้านกายภาพเป้นกระบวนการหนึ่งที่จำเป้นของการจัดการกับหน่วยความจำอีกด้วย
ระบบโปรแกรมเดียว(Monoprogramming)
วิธีนี้เป็นวิธีที่ง่ายที่สุดเพราะกำหนดเพียง 1 โปรแกรมทำงาน ณ เวลา หนึ่ง ดังนั้นการใช้งานหน่วยความจำจะมีเพียง 1 โปรแกรมเท่านัน แบ่งได้ 3 แบบ ดังรูป 5.3

ทีส่วนบนของหน่วยความจำ หรือไดร์เวอร์ของอุปกรณ์ต่างๆ อยู่ส่วนบนของ ROM และระบบปฏิบัติการRAM ที่อยู่ด้านล่างของหน่วยความจำ
การจัดการหน่วยความจำแบบแรกจะพบมากในระบบคอมพิวเตอร์เมนเฟรม และมินิคอมพิว
เตอร์ในสมันต้นๆ แต่ไม่มีแล้วในปัจจุบันการจัดการแบบที่ 2 ถูกใช้ในเครื่องปาล์มและ
คอมพิวเตอร์ขนาดเล็ก ส่วนการจัดการแบบที่ 3 ใช้กันมากในพีซี ในยุคแรกๆโดยส่วนของหน่วยความจำที่เป็น Rom รู้จักกันในชื่อของ BIOS
ถ้าระบบคอมพิวเตอร์ทำงานในลักษณะอณุญาตให้มีเพียง 1 โปรเซสทำงาน ณ เวลา ใดๆ
ตัวอย่างเช่น เมื่อผู้ใช้พิมพ์คำสั่งMS-DOS ระบบปฏิบัติการก็จพทำการก็อปปี้โปรเซส
ที่เรียกใช้ดิสก์ไปยังหน่วยความจำหลักและทำงาน และเมื่อโปรเซสนั้นทำงานเสร็จ ระบบปฏิบัติการจะแสดงคอมมานต์พร้อมต์ และรอให้ผู้ใช้เรียกคำสั่งต่อไป เมื่อผู้ใช้พิมพำสั่งใหม่ ระบบปฏิบัติการก็จะก็อปปี้โปรแกรมใหม่ทับของเก่า
5.2.2 ระบบหลายโปรแกรมที่กำหนดขนาดพาร์ติชั่นคงที่(Multiprogramming with Fixed Partition)
ระบบคอมพิวเตอร์ส่วนใหญ่ในปัจจุบันจะอณุญาตให้มีหลายโปรเซสทำงานในเวลาเดียวกันได้
การที่โปรเซสหลายตัวทำงานพร้อมกัน หมายความว่าขณะที่โปรเซสหนึ่งกำลังรอการนำเข้า/
ส่งออกข้อมูลทำงานเสร็จนั้น โปรเซสอื่นก็ก้สามารถใช้งานโปรเซสเซอร์ได้ ดังนั้นการทำงาน
ในลักษระนี้จะเป็นการเพิ่มประสิทธิภาพการใช้งานของ ซีพียู และเป็นลักษณะการทำงาน
ของเครื่องเซิฟเวอร์ และลูกเครือข่ายในปัจจุบันอีกด้วย
การจัดการกับหน่วยความจำสามารถทำได้โดย แบ่งพื้นที่หน่วยความจำออกเป็น ก พาร์ติชั่น
ในการแบ่งพาร์ติชั่นนั้นสามารถทำได้เมื่อระบบเริ่มทำงาน เมื่อมีโปรเซสเข้ามาทำงานระบบจะจัดการกับโปรเซสเหล่านั้นเข้าแถวเพื่อนำไปใส่พร์ติชั่นที่เล็กที่สุด เนื่องจากเรากำหนดให้พาร์ติชั่นเหล่านี้มีขนาดตายตัว ระบบจะสูญเสียพื้นที่ ทีไม่ได้ใช้งาน
ในพาร์ติชั่นไป ซึ่งเราเรียกพื้นที่เหล่านี้ว่า การสูญเปล่าของพื้นที่ย่อยภายใน



รูป 5.4 (ก) การแบ่งพื้นที่แบบตายตัวและมีกรจัดคิวสำหรับพาร์ติชั่นแต่ละส่วน
(ข)การแบ่งพื้นที่ตายตัวและมีคิวการนำเข้าเพียงคิวเดียว

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



รูป 5.5 แถวของโปรเซสที่จะเข้าไปใช้งานในหน่วยความจำ

สมมติว่า พาร์ติชั่นที่ 2 ขนาด 200 เกิดช่องว่างอยู่ วิธีมาก่อนได้ก่อนนี้ งานขนาด 70 จะถูกเลือกให้เข้าไปใช้และที่ไม่เลือกงานขนาด 220 เพราะว่ามีขนาดใหญ่กว่าขนาดของพาร์ติชั่นนั้น
วิธีนี้ทำงานเร็วแต่อาจจะทำให้เกิดความสูญเปล่าของพื้นที่ย่อยได้หลังจากใช้งานไปได้ระยะหนึ่ง
เนื่องจากการออกแบบการทำงานแบบนี้ไม่ต้องการให้ระบบเปลืองพื้นที่ขนาดใหญ่แก่งานที่มีขนาดเล็ก ดังนั้นวิธีการออกแบบระบบให้สามารถค้นหา และเลือกงานในคิวที่มีขนาดใหญ่ที่สุดที่สามารถใช้งานพื้นที่นั้นได้ดังนั้นในรูปที่ 5.5 วิธีการนี้จะเลือกงานขนาด 180 เข้าไปใช้พาร์ติชั่น เพราะว่ามีขนาดใหญ่ที่สุดที่จะใช้พาร์ติชั่นนี้ได้ วิธีการนี้จะทำให้ระบบได้ใช้งานหน่วยความจำได้อย่างมีประสิทธิภาพ แต่สังเกตว่าวิธีการดังกล่าวจะคัดค้านไม่ให้งานที่มีขนาดเล็ก ได้ใช้งานพาร์ติชั่นที่มีอยู่ ซึ่งโดยส่วนใหญ่แล้วงานที่มีขนาดเล็กนั้นจะเป็นงานที่ทำอยู่ตลอดเวลาและต้องการได้รับการบริการ หรือเซอร์วิสที่ดีจากระบบ เช่น การเชคค่าฮาร์ดแวร์ต่างๆ ของระบบเป็นต้น
วิธีการจัดการกับปัญหาดังกล่าวสามารถทำได้โดย
1. ให้สร้างพาร์ติชั่นที่มีขนาดเล็กสักกลุ่มหนึ่งที่เราจะให้งานที่มีขนาดเล็กทำงานได้เท่านั้นหรือ เราจะกำหนดว่างานที่เลือกเข้ามาใช้งานนั้นจะถูกมองข้ามได้ไม่เกินจำนวนครั้งที่กำหนดตัวอย่างเช่น ถ้าเรากำหนดให้งานแต่ละตัวที่ถูกมองข้ามได้ ไม่เกิน 3 ครั้งดังนั้นมีการตรวจสอบงานนั้นครั้งแรก และไม่เลือกงานนั้นเข้าไปใช้งาน งานนนั้นจะถูกตรวจสอบ 1 ครั้ง และเพิ่มขึ้นเรื่อยๆ เมื่อมีการมองข้ามไปอีก จนกระทั่งครั้งที่ 4จะต้องเลือกงานนั้นเข้าไปทำงานการจัดการแบ่งหน่วยความจำแบ่งพาร์ติชั่นแบบตายตัวและมีวิธีการจัดการกับโปรเซสที่เข้ามาใช้งานดังกล่าว เป้นวิธีการที่ง่ายและไม่ซับซ้อนต่อการสร้างโปรแกรมปฏิบัติการ อย่างไรก้ตามวิธีการนี่ยังมีข้อเสียดังต่อไปนี้
- พาร์ติชั่นที่กำหนดให้มีขนาดและจำนวนที่ตายตัวเมื่อเริ่มทำงานนั้น จะเป็นตัวจำกัดจำนวนของโปรเซสสามารถทำงานในระบบ
- เนื่องจากระบบมีการกำหนดของพาร์ติชั่นแบบตายตัว ดังนั้นงานมีขนาดเล็กจะไม่สามารถใช้พื้นที่ของพาร์ติชั่นได้อย่างมีประสิทธิภาพ ถึงแม้นว่าในบางระบบจะสามารถรู้จำนวนพื้นที่ทั้งหมดของแต่ละงานที่ต้องการก่อนทำงานก็ตามที
ระบบที่เคยใช้วิธีการจัดการของหน่วยความจำแบบนี้ ได้แก่ ระบบปฏิบัติการ ในเครื่องแบบเมนเฟรมของบริษัท IBM แต่ปัจจุบันระบบปฏิบัติงานต่างๆ ไม่ค่อยนิยมใช้วิธีนี้
5.2.3 ระบบที่กำหนดขนาดของพาร์ติชั่นให้เปลี่ยนแปลงได้
จากหัวข้อที่ผ่านมาเราได้เห็นถึงปัญหา และข้อด้อยของการกำหนดพาร์ติชั่นแบบคงที่แล้ว ในการป้องกันปัญหาดังกล่าวจำเป็นต้องใช้เทคนิคการจัดการหน่วยความจำที่ซับซ้อนยุ่งยากกว่าเดิม หนึ่งในระบบปฏิบัติการที่สำคัญ คือ ระบบปฏิบัติการที่ใช้ในเครื่องเมนเฟรมของบริษัท IBM เป็นต้น การแบ่พาร์ติชั่นแบบเปลี่ยนแปลงได้ ทั้งขนาดและจำนวนของพาร์ติชั่น และเมื่อมีโปรเซสเข้ามาใช้งาน หน่วยความจำหลักจถูกแบ่งพาร์ติชั่นให้พอดีกับดปรเซสนั้นต้องการใช้งาน ตัวอย่าง ถ้าเรามีหน่วยความจำหลักทั้งหมด 1 MB ดังรูป 5.6



รูป 5.6 การแบ่งพาร์ติชั่นแบบเปลี่ยนแปลงได้
- เริ่ม ในรูป ก มีบางส่วนของหน่วยความจำหลักที่ใช้งานสำหรับระบบปฏิบัติการ นอกนั้นหน่วยความจำหลักยังคงว่างอยู่
- เมื่อโปรเซส 3 งานโหลดเข้ามาใช้งาน ระบบจะสรรห่วยความจำเริ่มต้นจากตำแหน่งสิ้นสุดของหน่วยความจำหลักที่ระบบปฏิบัติการใช้งานอยู่ โดยจัดสรรพื้นที่ให้พอดีกับโปรเซสแต่ละตัวต้องการ ดังรุป ข ค ง
- ขณะที่โปรเซสทั้ง 3 กำลังทำงาน ลีโปรเซสที่4 ขนาด 128 k โหลดเข้ามาจะสังเกตได้ว่ารูป ง นั้นหน่วยความจำจะเหลือพื้นที่ว่าง แต่มีค่าน้อยกว่าพื้นที่ที่โปรเซสจะทำงานได้
- ในรูป จ ระบบปฏิบัติการทำการดึงโปรเซสที่ 2 อกจากหน่วยความจำหลักจึงทำให้มีพื้นที่เพียงพอที่จะทำให้โปรเซสที่ 4 เข้าไปใช้งานได้ ดังรูป ฉ
- สมมติต่อมาโปรเซสที่อยู่ในหน่วยความจำหลักทั้งสา ยังไม่สามารถทำงานได้แต่โปรเซสที่ 2ต้องการที่จะทำงาน แต่พื้นที่ในหน่วยความจำหลักไม่เพียงพอให้โปรเซสที่ 2ทำงาน ระบบจึงดึงโปรเซส1 ออกมา ดังรูป ข
- จากนั้นระบบปฏิบัติการจึงโหลดโปรเซสที่ 2 เข้าไปใช้งานอีกครั้งหนึ่ง ดังแสดงในรูป ข
จากในตัวอย่าง เราอาจจะเห็นว่าระบบน่าจะทำงานได้ดีในระดับหนึ่ง แต่ในความเป็นจริงแล้ว เมื่อระบบทำงานได้ซักระยะหนึ่ง เราพบว่ามีช่องว่างเกิดขึ้นอย่างมากมายในหน่วยความจำหลัก และจะทำให้การใช้งานหน่วยความจำหลักนี้มีประสิทธิภาพที่น้อยลงไป เราเรียกช่องเล็กๆว่า การสูญเปล่าของพื้นที่ย่อยภายนอกเนื่องจากพื้นที่ภายนอกพาร์ติชั่นในหน่วยความจำหลักเกิดช่องว่างและไม่สามารถนำมาใช้ประโยชน์ได้
วิธีการป้องกันปัญหา การสูญเปล่าพื้นที่ย่อยภายนอก คื การอัดบีบอัดพื้นที่เปล่า เหล่านั้น โดยระบบปฏิบัติการสามารถเลื่อนพื้นที่ของโปรเซสต่างๆ ที่ใช้งานให้มาชิดกัน ซึ่งจะทำให้พื้นที่ว่างเปล่าเหลือพาร์ติชั่นที่มี ขนาด 256 k ดังรูป 5.7 ที่อาจจะเพียงพอให้โปรเซสต่อไปเข้ามาใช้งาน



รูป 5.7 แต่การบีบอัดที่มีความยุ่งยาก ใช้เวลาทำงานมากเปลืองเวลาการทำงาน เพราะการบับอัดนี้จำเป็นต้องใช้วีการย้ายตำแหน่งของข้อมูล วึ่งต้องมีความสามารถในการย้ายโปรแกรมหนึ่งไปยังโปรแกรมหนึ่งในหน่วยความจำหลัก โดยไม่ให้บอกจุดตำแหน่งการแอ้กเซสข้อมูลนั้น ผิดพลาดไปด้วย ตัวอย่าง ในเครื่องคอมพิวเตอร์ที่มีความเร็วในการ ก้อปปี้ 4 ไบต์ ต่อ 40 นาโนวินาที จะใช้เวลาในการบีบอัดหน่วยความจำขนาด 256 MB ซึ่งเป็นเวลาค่อนข้างนานทีเดียว
5.2.4 การจัดสรรทรัพยากรระบบบัดดี้ (Buddy System)
ในระบบบัดดี้นี้ หน่ยวความจำจะถูกแบ่งออกเป็นพาร์ติชั่นที่มีขนาดเท่ากับ 2k โดย L <= K <= U เพราะการกำหนดเอ็ดเดรสในหน่วยความจำหลักมักจะใช้เลขฐาน 2 และ
2L = ขนาดของพาร์ติชั่นที่เล็กที่สุดที่สามารถจัดสรรได้
2U = ขนาดของพาร์ติชั่นที่ใหญ่ที่สุดที่สามารถจัดสรรได้ โดยปกติขนาด 2U นี้เท่ากับขนาดของหน่วยความจำทั้งหมดที่ยังว่างอยู่
การทำงานเริ่มต้นจาก กำหนดให้ขนาดพื้นที่ว่างทั้งหมดมีค่าเป็นพาร์ติชั่นเดียวขนาด 2U และ ถ้ามีโปรเซสร้องขอพื้นที่ S ซึ่งมีขนาดอยู่ระหว่าง 2U1 < S <= 2U ก็ให้พื้นที่นั่นกับโปรเซสดังกล่าว แต่ถ้ามีน้อยกว่าหรือเท่ากับ 2U1 ให้แบ่งพาร์ติชั่นนั้นออกเป็นสองส่วนขนาด 2U1 และทำการเช็คต่อว่า 2U2 < S <= 2U1 หรือไม่ กระบวนการดังกล่าวจะทำงานต่อไปจนกระทั่งพาร์ติชั่นที่เล็กที่สุดที่มีขนาดใหญ่กว่าหรือเท่ากับ S ถูกสร้างขึ้นมาและจัดสรรให้กับโปรเซสดังกล่าว


รูป 5.8 ตัวอย่างการแบ่งพาร์ติชั่นแบบระบบบัดดี้ [OSID:P301]

จากรูปที่ 5.8 เป็นตัวอย่างของการจัดสรรพื้นที่ 1 MB โดย
• เริ่มแรกให้มีโปรเซส A ขนาด 100KB เข้ามาใช้งานโดยทำให้พื้นที่ 1 MB ถูกแบ่งออกเป็น 2 ส่วนขนาด 512 KB แต่พื้นที่ A ก็ยังน้อยกว่า 256K จึงทำให้พื้นที่ส่วนแรกของ 512K ถูกแบ่งออกเป็น 2 ส่วน ส่วนขนาด 256K และต่อมาพื้นที่ส่วนแรกก็ถูกแบ่งออกเป็น 2 ส่วน อีกขนาด 128K คราวนี้มีการตรวจสอบว่า 64< A < 128 หรือไม่ ซึ่งคำตอบคือ “ใช่” ดังนั้นพื้นที่ 1 ใน 2 ส่วนนั้นก็จะถูกจัดสรรให้กับ A ไป
• ต่อมาโปรเซส B ขนาด 256k เข้ามาใช้งาน ซึ่งมีการแบ่งพาร์ทิชั่นเป็นขนาด 256k อยู่แล้ว จึงได้ใช้งานส่วนนั้นไป
• โปรเซส C ขนาด 64k ก็มีการทำงานเช่นเดียวกับ A คือมีการแบ่งพาร์ทิชั่น 128k ออกเป็น2 ส่วน และใช้งาน 1 จาก 2 ส่วนที่ถูกแยกออกได้
• การทำงานจะมีลักษณะเหมือนเดิม คือ มีการแบ่งและรวมพาร์ติชั่นที่ใช้งานเสร็จแล้วเข้าไว้ด้วยกัน ตัวอย่างเช่น เมื่อโปรเซส E ทำงานเสร็จ จะมีการรวมพาร์ติชั่นทั้ง 2 ของ 128k เป็น 256k แต่มีพาร์ติชั่นที่ว่างด้านข้างขนาด 256K จึงถูกรวมกันอีก เป็น 512k



รูป 5.9 การใช้ลิงค์ลิสต์ควบคุมการทำงานระบบบัดดี้

เราจะเห็นได้ว่าระบบบัดดี้มีการจัดการกับลิสต์ที่ตัวเองมีดังนี้
 ระบบจะมีลิสต์ของพื้นที่ว่าง โดยแต่ละโหนด (node) จะต้องมีขนาด 2
 พื้นที่ว่างจะสามารถถูกแยกออกจากโหนด 2(i+1) โดยมีการแบ่งพื้นที่นั้นออกเป็น 2 ส่วนที่มีขนาด 2i ได้
 และเมื่อมีการรวมพื้นที่ว่างของคู่โหนดใด ๆ ขนาด 2 i โหนดนั้นก็จะถูกรวมเป็นโหนดเดียวขนาด 2(i+1)

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


5.3.1 การจัดการแบบบิตแมพ (Memory Manager with Bitmaps)
การจัดการแบบบิตแมพนี้ หน่วยความจำจะถูกแบ่งออกเป็น ยูนิต โดยแต่ละยูนิตจะมีขนาดใหญ่หรือเล็กก็ได้ เช่น มีขนาด 1 ไบต์ หรือ หลายร้อยกิโลไบต์ก็ได้ แต่ในแต่ละยูนิตนั้นจะแทนค่า 1 บิตเสมอ (นั่นคือ ถ้าหน่วยความจำมี 1000 ยูนิต ก็จะมี 1000 บิต) และเรียก บิต เหล่านี้ว่าระบบบิตแมพนั้นเอง (มีค่า0.01) โดยที่
ถ้าบิตแมพ มีค่าเท่ากับ 1 แสดงว่ายูนิตที่เป็นบิตนั้นเป็นตัวแทนอยู่ ไม่ว่าง (มีโปรเซสอยู่)
ถ้าบิตแมพ มีค่าเท่ากับ 0 แสดงว่ายูนิตที่เป็นบิตนั้นเป็นตัวแทนว่างอยู่ (ไม่มีโปรเซสอยู่)

การจัดการบิตแมพเป็นวิธีที่ใช้ในการตรวจสอบพื้นที่ของหน่วยความจำที่ง่าย เพราะขนาดของบิตแมพนั้นจะคงที่ และขึ้นอยยู่กับขนาดของยูนิตและขนาดของหหน่วยความจำทั้งหมด การจัดการแบบนี้มีข้อเสีย คือ
1. ทำให้เกิดการสูญเสียพื้นที่ภายใน (Internal Fragmentation) ในยูนิตสุดท้ายได้
2. ทำให้เกิดการสูญเสียพื้นที่ภายนอก (External Fragmentation)ได้ ซึ่งสามารถดูได้จากค่า 0 ที่กระจายอยู่ในตารางบิตแมพ
3. การนำโปรเซสที่ต้องการ k ยูนิต เข้ามาใช้งานในหน่วยความจำ ระบบจะต้องหา 0 เป็นจำนวน k บิตติคกันในบิตแมพ และการค้นหาจะใช้เวลามากพอสมควร เนื่องจากในการทำงานนั้นอาจจะทำให้ขอบเขตของไบต์ในแมพนั้นเปลี่ยนแปลงได้

5.3.2 การจัดการแบบลิงค์ลิสต์ (Memory Management with Linked Lists)
วิธีการตรวจสอบพื้นที่ของหน่วยความจำอีกวิธีหนึ่งคือ การใช้ลิงค์ลิสต์เก็บข้อมูลพสร์ติชั่น ในหน่วยความจำทั้งที่ว่าง หรือที่ถูใช้งานอยู่
ลิงค์ลิสต์ของพาร์ติชั่นนั้นจะถูกจัดเรียงตามแอ็ดเดรส มีข้อดีคือ เมื่อมีโปรเซสใดหยุดทำงาน หรือ ถูกดึงออกจากหน่วยความจำ การเปลี่ยนแปลงของลิสต์สามารถทำได้ง่าย โดยปกติแลล้วโปรเซสหนึ่ง ๆ จะมีพาร์ติชั่นด้านข้างอยู่ 2 พาร์ติชั่น (ยกเว้นพาร์ติชั่นที่อยู่ส่วนบน/ล่างสุด ของหน่วยความจำ) และพาร์ติชั่นที่อยู่โดยรอบนี้จะเป็นพาร์ติชั่นที่ว่างหรือกำลังถูกใช้งานอยู่ก็ได้ ซึ่งจะทำให้ได้รูปแบบการทำงาน 4 กรณี ดังรูป 5.11





รูปที่ 5.10 รูปแบบการทำงานทั้ง 4 แบบ ของการหยุดทำงานของโปรเซส x (MOS:P200)



รูป 5.11 ตัวอย่างกานำโปรเซสเข้ามาใช้งานหน่วยความจำตามวิธีต่าง ๆ

1. First-Fit เป็นวิธีที่ง่ายที่สุด เริ่นต้นเนื่อที่ว่างจากต้นลิสต์ก่อนเสมอ โดยไปค้นทีละโหนดและจะนำโหนดที่ว่างและมีขนาดพอต่อโปรเซสไปทำงานก่อน วิธีนี้เร็วแต่ไม่ดี
2. Next-Fit คล้ายกับวิธีแรก แต่การหาที่ว่างจะเริ่มต้นจากโหนดที่หยุดลงจากการค้นหาครั้งก่อนหน้านั้นจนเจอโหนดที่มีที่ว่างพอสำหรับโปรเซส แต่ประสิทธิภาพของการทำงานนั้นไม่ดีไปกว่าแบบแรกเลย
3. Best-Fit หาเนื้อที่ว่างโดยค้นทั้งลิสต์ เพื่อหาเนื้อที่ว่างที่มีขนาดเท่ากัน หรือ ใกล้เคียงกับขนาดของโปรเซสจริง มีข้อเสีย คือ ใช้เวลานานเพราะต้องนำทุกโหนด ไปเปรียบเทียบกับโปรเซสเพื่อหาขนาดที่เหมาะสม และทำให้เกิดช่องว่างเล็กๆ ภายในหน่วยความจำเป็นจำนวนมาก วิธีที่จะทำให้การค้นหาเร็วขึ้นคือ การเรียงลิสต์ตามลำดับจากขนาดเล็กไปใหญ่ ถ้าพบว่าที่ว่างที่โปรเซสนั้นลงได้ ก็ให้ใช้ได้เลยเพราะว่าที่ว่างหลังจาหนั้นก้จะมีค่าใหญ่กว่าแน่นอน จึงเป็นการปรหยัดเวลาไม่ต้องนำโปรเซสไปเปรียบเทียบกับทุกโหนด
4. Worst-Fit เป็นวิธีป้องกันไม่ให้เกิดปัญหาการเกิดเนื้อที่ว่างเล็กๆ เป็นจำนวนมากอย่าง Best-Fit เริ่มต้นเนื้อที่ว่างโดยค้นทั้งลิสต์ และหาโหนดที่ว่างที่มีขนาดใหญ่ที่สุดในลิสต์ เพื่อใส่โปรเซสใหม่เข้ามา แต่จะมีข้อเสียเหมือน Best-Fit
5. Quick-Fit มีลิงค์ลิสต์มากกว่า 1 ลิสต์ โดยแต่ละลิงค์ลิสต์จะประกอบไปด้วยโหนดที่มีขนาดเท่ากันซึ่งพาร์ติชั่นส่วนนั้นจะว่างหรือไม่ก็ได้

5.4 หน่วยความจำเสมือน (Virtual Memory)
หน่วยความจำเสมือนเป็นวิธีหนึ่งที่สามารถทำให้โปรเซสทำงานได้ ถึงแม้ว่าโปรเซสนั้นจะไม่ได้อยู่ในหน่วยความจำหลักทั้งหมด โดยระบบปฏิบัติการจะทำหน้าที่เก็บบางส่วนของโปรแกรมที่กำลังทำงานไว้ในหน่วยความจำหลัก และเก็บส่วนที่เหลือไว้ในฮาร์ดดิสก์ ตัวอย่างเช่น โปรแกรมที่ต้องการหน่วยความจำ 100 MB สามารถทำงานบนเครื่องที่มีหน่วยความจำ 64 MB ได้โดยการเลือกเอาบางส่วนของโปรแกรมขนาด 64 MB เข้ามาทำงานในหน่วยความจำหลัก และบางส่วนเก็ยไว้ในฮาร์ดดิสก์และทำการสลับเปลี่ยนไปมาเมื่อมีบางส่วนของโปรแกรมต้องการทำงาน
ข้อดีของวิธีนี้ คือ โปรแกรมของผู้ใช้สามารถมีขนาดใหญ่กว่าหน่วยความจำจริงได้ เพราะวิธีนี้จะสร้างหน่วยความจำทางตรรก ให้ดูเสมือนว่ามีหน่วยความจำเป็นแถวขนาดใหญ่ โดยแยกภาพที่ผู้ใช้มองเห็นหน่วยความจำออกจากลักษณะจริงของฮาร์ดแวร์ ทำให้ผู้เขียนโปรแกรม ทำการเขียนโปรแกรมได้อิสระมากขึ้นไม่ต้องกังวลถึงขนาดของหน่วยความจำอีกแต่ไป แต่การสร้างหน่วยความจำไม่ใช่ของง่าย อาจทำให้ประสิทธิภาพของระบบทำงานได้ช้าลงมาก

5.5 การแบ่งเป็นหน้า (Paging)
การที่ระบบต้องใช้หน่วยความจำเสมือนส่วนใหญ่จะใช้เทคนิคที่เรียกว่า การแบ่งเป็นหน้า หรือ เพจจิ่ง
การแบ่งหน่วยความจำหลักออกเป็นพาร์ติชั่นที่มีขนาดเล็กและเท่ากัน เรียกว่า เฟรม หรือ เพจเฟรม และการแบ่งโปรแกรมในดิสก์ที่จะเข้ามาใช้งานเป็นชิ้นเล็กๆ เรียกว่า หน้า โดยทุกหน้าจะมีขนาดเท่ากันเท่ากันหมด และมีเลื่อนใขว่า
1. ขนาดของ 1 หน้า จะต้องเท่ากับขนาดของ 1 เฟรม เสมอ
2. ใน 1 เฟรม จะมีการนำเอาแค่ 1 หน้า มาใส่ได้เท่านั้น เช่น หน่วยวามจำหลัก 1 MB และแบ่งออกเป็น 4 เฟรม ดังนั้น ขนาดของเฟรมคือ 256 KB และ หน้าในดิสก์เท่ากับ 256 KB เหมือนกัน



ในรูปที่ 5.15 แสดงการใช้หน้าของแต่ละเฟรม ในขณะใดขณะหนึ่งบางเฟรมในหน่วยความจำจะถูกใช้งาน และบางเฟรมก็ว่าง โดยรายชื่อของเฟรมที่ว่างก็จะถูกบันทึกโดยระบบปฏิบัติการ ในรูปที่ 5.15(ข)โปรแกรม A ที่เก็บในดิสก์ประกอบด้วย 4 หน้า และเมื่อโปรแกรม A ถูกโหลดเข้าในหน่วยความจำหลักก็จะถูกเก็บไว้ใน 4 เฟรมแรกของหน่วยความจำหลัก จากนั้นก็มีการโหลดโปรแกรม B ที่มี 3 หน้า และโปรแกรม C ที่มี 4 หน้าตามลำดับ จากนั้นโปรแกรม B ถูกสั่งให้คอยและถูกสลับออกไปจากหน่วยความจำหลัก ดังในรูปที่ 5.15(จ) และโปรแกรม D ที่มี 5 หน้าก็ถูกโหลดเข้ามาใช้งาน ดังในรูปที่ 5.15 (ฉ)
วิธีการทำให่การจัดการแบบแบ่งหน้าสามารถทำได้ง่ายขึ้นโดย เริ่มจากแบ่งขนาดของเฟรมและขนาดของหน้าให้เป็นค่า ยกกำลังของเลขฐาน 2 ซึ่งวิธีนี้แอ็ดเดรสทางตรรกจะแสดงเป็นเลขที่หน้า และระยะจากขอบหน้า (offset) ดังแสดงในรูปที่ 5.17 แสดงการเปรียบเทียบวิธีการคิดแอ็ดเดรสทางตรรกแบบต่าง



รูปที่ 5.17 แอ็ดเดรสทางตรรก [OSID:P306]
สมมติว่าในรูปนี้ใช้แอ็ดเดรส แบบ 16 บิต และแต่ละหน้ามีขนาด 1K หรือ1,024 ไบต์ ถ้าแอ็ดเดรสเปรียบเทียบ มีค่า 1502 ซึ้งแปลงเป็นเลขฐาน2 คือ 0000010111011110 เนื่องจากแบ่งแต่ละหน้าให้มีขนาด 1k ดังนั้น ระยะจากขอบหน้าหรือ offset จะใช้ทั้งหมด 10 บิต (210 = 1024) จะทำให้เหลือ 6 บิตที่แสดงเลขหน้า (16-10 = 6 บิต) ดังรูป 5.17(ข) ซึ่งแสดงเปรียบเทียบ 1502 ป็นระยะจากขอบหน้า 478(0111011110) บนหน้าที่ 1 (000001) ซึ่งรวมกันเป็นที่อยู่ 16 บิต คือ 0000010111011110 ซึ่งผลลัพธ์ของการกำหนดขนาดของหน้าเป็นค่าของเลขยกกำลัง 2 ดังกล่าวจะทำให้
1. โปรแกรมเมอร์ไม่จำเป็นต้องสนใจแอ็ดเดรสทางตรรกเลย เพราะว่าแอ็ดเดรสทางตรรกของโปรแกรมนั้นมีค่าเท่ากับแอ็ดเดรสเปรียบเทียบอยู่แล้ว (logical address=relative address)
2. การทำงานของฮาร์ดแวร์ในการแปลงที่อยู่นั้นจะทำได้ง่ายขึ้นเพราะว่าที่อยู่จะถูกเขียนอยู่ในรูปของ n+m บิต โดยบิตทางด้านซ้ายมือสุดจำนวน n บิต เป็นเลขที่หน้า และ บิตทางด้านขวามือจำนวน m บิตเป็นระยะจากขอบหน้า ในตัวอย่างก่อนหน้านี้ n=6 และ m=10 โดยการแปลงที่อยู่สามารถทำได้เป็นขั้นตอนดังนี้
 แยกเลขที่หน้าโดยนำบิตทางด้านซ้ายมือจำนวน n บิต ออกมาจากที่อยู่ทางตรรก
 ใช้เลขที่หน้าเป็นตัวตั้งในตารางหน้าของโปรแกรม เพื่อนำไปใช้ค้นหาเลขที่เฟรม k ต่อไป
 ที่อยู่ทางกายภาพของเฟรมนั้นคือ k x 2m และที่อยู่ทางกายภาพของหน่วยความจำหลักที่เทียบ ก็คือตัวเลขที่ได้บวกกับระยะจากขอบหน้า



รูป 5.18 ตัวอย่างของการแปลงแอ็ดเดรสทางตรรกเป็นแอ็ดเดรสทางกายภาพ



รูป 5.19 การแปลงแอ็ดเดรส [OSID:P326]
5.5.1 ตารางหน้า (Page Table)
ตารางหน้า(PageTable)นั้นเป็นการแมพค่าของแอ็ดเดรสทางตรรกไปหาค่าเลขที่เฟรมที่อยู่ในหน่วยความหลักซึ่งในทางคณิตศาสตร์ เราอาจจะกล่าวได้ว่าตารางหน้านี้เป็นฟังก์ชั่นที่รักค่าของแอ็ดเดรสทางตรรกเป็นอินพุต (Input) และให้ค่าแอ็ดเดรสทางกายภาพออกมา (Output) ซึ่งสิ่งที่ฟังก์ชั่นดังกล่าวทำก้คือแทนแอ็ดเดรสของเพจที่เป็นแอ็ดเดรสทางจรรกด้วยแอ็ดเดรสของเฟรม แต่ถึงแม้นการอธิบายข้างต้นจะดูเหมือนง่ายแต่ปัญหาที่พบมีอยู่ 2 หัวข้อคือ
1 ตารางหน้าส่วนใหญ่จะมีขนาดใหญ่
2 การแมพค่าแอ็ดเดรสดังกล่าวจะต้องทำด้วยความเร็วสูง
โดยในหัวข้อแรกนั้น ในระบบคอมพิวเตอร์ปัจจุบันจะใช้แอ็ดเดรสอย่างต่ำประมาณ 32 บิต ถ้าเรากำหนดให้แต่ละหน้ามีขนาด 4 KB ก็จะทำให้ระบบมีหน้าทั้งหมด 1 ล้านหน้า (232-12 = 220 = 1 ล้าน) และในระบบที่เป็นแบบ 64 บิต ก็จะทำให้มีจำนวนหน้ามากประมาณเกินกว่าที่จะนำไปใช้หมด (212 หน้า) และในหัวข้อที่สองนั้นเป็นผลพวงมาจากการแมพระหว่างแอ็ดเดรสทางตรรกและแอ็ดเดรสทางกายภาพนั้นจะต้องทำทุก ๆ ครั้งเมื่อมีการอ้างถึงแอ็ดเดรสจริงในหน่วยความจำหลัก โดยส่วนใหญ่ใน 1 คำสั่งนั้นจะประกอบไปด้วย ตัวแปร และเครื่องหมายดังนั้นใน 1 คำสั่งโปรแกรมอาจจะต้องเรียกตารางหน้าเข้ามาแมพเป็นจำนวน 1,2 หรือ มากกว่านั้น และถ้าเรากำหนดให้ในแต่ลำคำสั่งจะใช้เวลาเพียง 4 nsec ตารางหน้านั้นจะต้องมีความสามารถในการสืบค้นได้เร็วมากกว่า1 nsec เพื่อป้องกันปัญหาคอขวด (bottleneck)

รูป 5.20 การทำงานของตารางหน้า [MOS:P206]
ความต้องการตารางที่ใหญ่และการแมพค่าที่เร็วนั้นเป็นสิ่งที่สำคัญเมื่อเราสร้างสร้างระบบคอมพิวเตอร์หนึ่ง ๆ การออกแบบระบบอย่างง่าย ๆ ของการใช้ตารางหน้าเพียง 1 ตาราง ที่ประกอบไปด้วยอาค์เรย์ของรีจิสเตอร์(registerเป็นหน่วยความจำพิเศษ)ที่เร็ว(ไว้เก็บค่าของหน้าแต่ละอันที่ถูกจัดเรียงโดยเลขที่หน้า) ดังแสดงในรูปที่ 5.20
เมื่อมีโปรเซสหนึ่งเริ่มทำงานระบบปฏิบัติการจะทำการโหลดรีจิสเตอร์ด้วยคาราหน้าของ โปรเซสนั้น ๆ โดยทำการก็อบปี้จากหน่วยความจำหลัก ก็จะทำให้เราไม่ต้องอ้างถึงหน่วยความจำอีกในขณะที่โปรเซสกำลังทำงานและข้อดีของวิธีนี้ก็คือ เป็นวิธีที่ง่ายและไม่ต้องทำการอ้างถึงหน่วยความจำอีกเมื่อทำการแมพแอ็ดเดรส แต่ข้อเสียก็คือ ถ้าตารางของหน้ามีขนาดใหญ่ก็จะให้ระบบมีประสิธิภาพในการทำงานต่ำลงเพราะการโหลดตารางหน้างทั้งหมดนั้นจะใช้เวลานาน

รูป 5.21 (ก) ฟิลด์ในตารางหน้าที่มี 32 บิต (ข) ตารางหน้า 2 ลำดับ [MOS:P208]

การแก้ปัญหาของการเก็บตารางที่มีขนาดใหญ่ในหน่วยความจำหลักตลอดเวลาก็คือ การใช้ตารางหน้าหลายลำดับ ตัวอย่างของการใช้ตารางแบบนี้แสดงดังในรูปที่ 5.21 ในระบบที่มีแอ็ดเดรสเท่ากับ 32 บิตนั้น เราสามารถแบ่งออกเป็น 3 ฟิลด์ โดย 10 บิต แรกเป็นฟิลด์ PT1, 10 บิตต่อมาเป็น PT2 และ 12 บิตสุดท้ายเป็นฟิลด์กำหนดระยะจากขอบหน้า (offset) และเนื่องจากระยะจากขอบหน้ามี 12 บิต ก็จะทำให้แต่ละหน้ามีขนาด 4 KB และมีทั้งหมด 230 หน้า
ความลับของวิธีกาใช้ตารางแบบหลายลำดับก็คือเพื่อเป็นการป้องกันไม่ให้ระบบเก็บตารางหน้าไว้ในหน่วยความจำตลอดเวลา ตัวอย่างเช่น ในโปรเซสที่ต้องการพื้นที่ 12 MB นั้น เราอาจจะทำการแบ่งเป็นพื้นที่ด้านล่าง 4 MB สำหรับตัวโปรแกรม, พื้นที่ต่อมาอีก 4 MB สำหรับเก็บผลลัพธ์ ในรูปที่ 5.21 (ข) นั้นเราจะเห็นว่าตารางแบบ 2 ลำดับ แบ่งเป็น ตารางลำดับแรกทางด้านซ้ายมือที่มี 1024 ช่อง ซึ่งมาจาก 10 บิต ของฟิลด์ PT1 เมื่อแอ็ดเดรสทางตรรกถูกเรียกเข้ามา ตัวจัดการหน่วยความจำ หรือ MMU (Memory Management Unit) นั้น จะดึงฟิลด์ดังกล่าวออกมาและใช้ค่าที่อ่านได้เป็นแอนเด็กซ์ในตารางชั้นบนสุด และในแต่ละช่องของตารางแรกจะมีทั้งหมด 1024 ช่องของตารางที่สอง (PT2) สมมุติว่าแต่ละช่องในตารางที่ 2 นั้นแทนค่า 4 M ก็จะทำให้มีจำนวนพื้นที่ทั้งหมดเท่ากับ 4 GB จุดที่น่าสนใจเกี่ยวกับรูปที่ 5.21 ก็คือ ถึงแม้นว่าที่อยู่นั้นจะประกอบไปด้วย 1 ล้านหน้า แต่ในตัวอย่างดังกล่าวนั้น จะเก็บตารางหน้าที่ต้องการเพียง 4 ตารางเท่านั้น คือตารางลำดับแรก, ตารางลำดับที่สองระหว่าง 0 ถึง 4 M และ ระหว่าง 4M ถึง 8M และตารางบนอีก 4M นอกจากตาราง 2 ลำดับชั้นดังกล่าวแล้ว ระบบยังสามารถมีตารางหลาย ๆ ชั้นได้อีก เช่น 3, 4 หรือมากกว่า การสร้างตารางที่มีลำดับชั้นมากขึ้นจะทำให้ความซับซ้อนของการจัดการมีมากขึ้นด้วย
คราวนี้เรามาพิจารณาในรายละเอียดถึงโครงสร้างของตารางหน้ากันว่าประกอบไปด้วยอะไรบ้าง โดยทั่วไปแล้วฟิลด์ในตารางหน้านั้นจะแตกต่างกันไปตามการออกแบบของแต่ละระบบ แต่ข้อมูลส่วนใหญ่ที่นำเสนอนั้นจะคล้าย ๆ กัน โดยในรูปที่ 5.22 จะเป็นตัวอย่างโครงสร้างของตารางหน้าโดยขนาดของตารางจะขึ้นอยู่กับระบบคอมพิวเตอร์แต่ละประเภท แต่ปัจจุบันจะมีค่าเท่ากับ 32 บิต โดยมีรายละเอียดของแต่ฟิลด์มีดังนี้

รูป 5.22Entry ในตารางหน้า [MOS:P210]
PageFrameNumber เป็นฟิลด์ที่มีความสำคัญมากที่สุดเพราะฟิลด์นี้ใช้ในการเก็บข้อมูลว่า หน้านี้จะไปอยู่ในเฟรมเลขที่อะไรในหน่วยความจำหลัก
Present/absent มีขนาด 1 บิตใช้บอกว่าหน้านี้ในปัจจุบันอยู่ (Present) หรือ ไม่อยู่ (absent) ในหน่วยความจำหลักหรือไม่ โดยถ้ามีการกำหนดเป็น 1 คือ มีอยู่ในหน่วยความจำหลัก และ 0 บิต คือ ไม่มีอยู่ในหน่วยความนจำหลัก ถ้ามีการพยายามเข้าถึงข้อมูลของหน้าที่บิตนี้กำหนดเป็น 0 แล้ว ก็จะทำให้เกิดปัญหาการผิดหน้าได้ (Page fault)
Protection เป็นบิตที่เก็บข้อมูลเกี่ยวกับการป้องกันหน้าว่าหน้านี้มีการป้องกันในการเรียกใช้งานอย่างไร เช่น ให้อ่านได้อย่างเดียว(Read Only), อ่านและเขียนได้ (Read/Write) หรือเอ็กซิคิวต์ได้ (Execute) ซึ่งการป้องกันนี้ใช้ 3 บิตก็พอ เช่น R (Read), W (Write), E (Execute) เป็น 000,001,010,011,.. เป็นต้น
Modified ใช้ในการเก็บข้อมูลเกี่ยวกับการใช้งานของหน้านั้น ว่าหน้าที่เข้าไปอยู่ในหน่วยความจำหลัก และที่ถูกใช้งานแล้วนั้นมีการถูกบันทึกใหม่ หรือมีการปรับเปลี่ยนค่าหรือไม่ โดย กำหนดเป็น 0 ถ้าไม่มีการถูกบันทึกหรือปรับปรุงเปลี่ยนค่า และถูกกำหนดเป็น 1 ถ้ามีการถูกบันทึกหรือปรับปรุงเปลี่ยนแปลงค่า บิตนี้รู้จักกันในอีกชื่อหนึ่งว่า เดอตี้บิต (dirty bit) เพราะเป็นบิตที่รพบบปฏิบัติการใช้ในการตรวจสอบสถานะของหน้า โดยถ้าหน้าไหนถูกเปลี่ยนแปลงก็จะเป็นบิตที่สกปรก ที่จะต้องถูกเขียนกลับลงในดิสก์เป็นต้น
Referenced ใช้บอกว่าหน้าที่เข้าไปอยู่ในหน่วยความจำหลักนี้ ถูกเรียกใช้บ้างหรือไม่ (มีค่าเป็น 0 หรือ 1) ถ้าถูกกำหนดเป็น 0 คือ หน้านั้นยังไม่ถูกเรียกใช้งานตั้งแต่ถูกโหลดเข้ามาในหน่วยความจำหลัก และกำหนดเป็น 1 สำหรับ หน้าที่ถูกเรียกใช้งานแล้ว และบิตนี้จะเป็นบิตที่สำคัญสำหรับกระบวนการสับเปลี่ยนหน้า (Page Replacement) ที่เราจะเรียนรู้ในหัวข้อต่อไป
Caching disabled เป็นบิตที่ใช้กำหนดว่าเราไม่ต้องการเก็บค่าแคซสำหรับหน้านั้น โดยทั่วไปบิตนี้จำหสำคัญสำหรับ หน้า ที่ถูกแมพเข้ากับริจิสเตอร์ของอุปกรณ์ เช่นในกรณีที่ระบบปฏิบัติการจะต้องรออุปกรณ์ภายนอกตอบสนองคำสั่งอยู่ตลอดเวลา
เนื่องจากขนาดตารางหน้านั้นขึ้นอยู่กับจำนวนหน้าที่มี กล่าวคือ 1 แถวของตารางจะเท่ากับ 1 หน้าของโปรเซส ถ้าโปรเซสมีขนาดใหญ่มาก ๆ ตารางหน้าก็มีขนาดใหญ่ไปด้วยซึ่งจะทำให้การทำงานในการแมพที่อยู่นั้นช้าลง วิธีการแก้ก็คือ การทำตารางหน้าย้อนกลับ (inverted page table) โดยในระบบคอมพิวเตอร์หนึ่ง ๆ จะมีตารางหน้าย้อนกลับ ได้แค่ 1 ตารางเท่านั้น เพราแต่ละแถวในตารางหน้าย้อนกลับนั้น จะเป็นตัวแทนของเฟรม ในหน่วยความจำหลัก ตัวอย่างเช่น ในระบบที่ใช้ที่อยู่แบบ 64 บิต โดยแต่ละหน้ามีขนาด 4KB (212) และมีขนาดของหน่วยความจำหลักเท่ากับ 256 MB (228) ซึ่งทำให้ตารางนี้มีทั้งหมด 65,536 แถว (2 28-12 = 216 = 65536) โดยในแต่ละแถวจะทำหน้าที่เก็บข้อมูลของ โปรเซส และเลขที่หน้าที่ใช้งานอยู่ในเฟรมในหน่วยความจำหลักดังนั้นแต่ละแถวของตารางแบบย้อนกลับนี้จะประกอบด้วย
Process Id เป็นหมายเลขโปรเซสที่อยู่ในเฟรมนั้น
 Flag Bit จะแสดงถึงสถานะของโปรเซสที่อยู่ในเฟรม ซึ่งมี Referenced Bit, Modified
Bit และ Present/Absent Bit อย่างในตารางหน้า
 Page No จะแสดงหมายเลขหน้าของโปรเซสนั้นที่เข้ามารอยู่ในเฟรมนี้
 Counter จะเก็บค่าทุกครั้งที่โปรเซสเซอร์ หรือซีพียูทำการเรียกใช้
และอาจทำการบันทึกว่าถูกเรียกใช้งานครั้งสุดท้ายเมื่อไหร่ด้วย

ถึงแม้ว่าตารางหน้าแบบย้อนกลับนี้จะช่วยให้เราประหยัดพื้นที่ได้เมื่อแอ็ดเดรสในหน่วย ความจำเสมือนนั้นมีจำนวนมากกว่าแอ็ดเดรสในหน่วยความจำหลัก แต่วิธีดังกล่าวก็มีข้อเสียเช่นกันคือ การแปลงแอ็ดเดรสเสมือนไปแอ็ดเดรสจริงทางกายภาพนั้นทำได้ยากขึ้น เมื่อมี โปรเซส n อ้างถึง หน้า p ฮาร์ดแวร์จะไม่สามารถทำการค้นหาแอ็ดเดรสจริง โดยการใช้ p เทียบเป็นอินเด็กซ์ของตารางได้อีกต่อไป ตรงกันข้าม วิธีการค้นหาจะต้องทำการสืบค้นทุกแถวในตารางหน้าย้อนกลับ ซึ่งการค้นหาทุกแถวในตารางขนาด 64 K นั้นจะทำให้การทำงานในระบบ ช้าลงพอสมควร

วิธีการแก้ปัญหาดังกล่าวสามารถทำได้โดยการใช้วิธี TLBs (Translation Lookaside Buffers) ถ้า TLB สามารถเก็บหน้าที่ถูกใช้งานบ่อย ๆ การแปลงแอ็ดเดรสก็สามารถทำได้เร็วเหมือนกับที่เราทำในตารางหน้าธรรดาได้ซึ่งเราจะเรียนรู้ในรายละเอียดในหัวข้อย่อยต่อไปอย่างไรก็ตามการใช้ตารางแบบย้อนกลับนี้จำเป็นต้องใช้ซอฟแวร์ช่วยในการสืบค้น ซึ่งคือการใช้ตารางแฮช และฟังก์ชั่นแฮช (Hash Function เป็นฟังก์ชั่นที่ใช้ในการแปลงข้อมูลที่มีความยาวมาก เป็นบิตที่มีจำนวนน้อยลงและค่าแฮชของข้อมูลแต่ละค่าไม่ควรมีค่าเหมือนกัน) ในการแปลงแอ็ดเดรสเสมือน ดังในรูปที่ 5.24 และหน้าที่อยู่ในหน่วยความจำที่มี่ค่าแฮชเหมือนกันก็จะมีค่าเชื่อมต่อเข้าหากัน (chained)

5.5.2 บัฟเฟอร์ค้นหาที่อยู่ (Translation Lookaside Buffer)
โดยทั่วไปแล้วเมื่อมีการอ้างถึงหน่วยความจำเสมือนทุกๆครั้งจะมีการเรียกหาหน่อยความจำหลักถึง 2 ครั้ง คือ มีการดึงแถวของตารางหน้า และการดึงข้อมูลที่ต้องการออกมาจากหน่วยความจำ ดังนั้น การทำงานของหน่วยความจำ เสมือนจะใช้เวลาในการเข้าถึงหน่วยความจำเป็น 2 เท่า วิธีการป้องกันปัญหาดังกล่าวสามารถทำได้โดย ใช้แคชหรือหน่วยความจำพิเศษในการเก็บแถวของตารางหน้า ที่เราเรียกกันว่า บัฟเฟอร์ค้นหาที่อยู่(TLB) โดยแคชนี้จะทำหน้าที่เก็บแถวของตารางหน้าที่พึ่งใช้เรียกใช้งานเสร็จ โดยการทำงานของบัฟเฟอร์นี้สามารถแสดงได้ดังรูปที่ 5.25



เมื่อมีการให้ค่าแอดเดรสเสมือนกับระบบ โปรเซสเซอร์จะทำการสืบค้นในตาราง TLB ถ้าพบแถวที่ต้องการในตารางหน้า (TLB hit) เราก็สามารถเก็บเลขที่เฟรมและแปลงเป็นแอดเดรสจริงได้เลย แต่ถ้าไม่พบแถวที่ต้องการ(TLB miss)โปรเซสเซอร์ หรือซีพียูก็จะต้องใช้เลขที่หน้าไปเปรียบเทียบกับอินเด็กซ์ของตารางหน้า เพื่อหาแถวที่ต้องการ และซีพียูก็จะทำหน้าที่เพิ่ม TLB ให้มีแถวของตารางหน้าใหม่นี้ด้วย นอกจากนั้น เนื่องจาก TLB จะเก็บข้อมูลของบางแถวจากหน้าตารางเท่านั้น ทำให้เราไม่สามารถเรียงลำดับแถวของ TLB ด้วยเลขที่หน้าได้ ดั้งนั้นค่าของฟิลด์ในแถวของ TLB จะต้องมีเลขที่หน้ากำกับด้วย การค้นหาเลขที่หน้าใน TLB ของดปรเซสเซอร์นั้นจะเป็นการแมพรวม (associative mapping) ซึ่งแตกต่างจากการแมพโดยตรงอย่างที่ทำกันในตารางหน้า ดังแสดงในรูปที่ 5.26 ดังนั้นการออกแบบ TLB จะต้องพิจารณาถึงวิธีการจัดการกับค่าของแถวที่อยู่ในตาราง และ วิธีการแทนที่ค่าของแถวใหม่เข้าไปในตาราง



5.6 การสับเปลี่ยนหน้า (Page replacement algorithms)
ในการออกแบบระบบปฏิบัติการโดยทั่วไปนั้น หัวข้อย่อยของการจัดการหน่วยความจำ จะรวมถึง การสับเปลี่ยนหน้า(replacement policy) ด้วยเสมอ ซึ่งจะเกี่ยวข้องกับการเลือกหน้าในหน่วยความจำที่จะถูกแทนที่ด้วยหน้าใหม่ที่นำเข้ามา ในบางครั้งหัวข้อนี้ก็ยากที่จะอธิบาย เพราะมันจะเกี่ยวเนื่องกับแนวความคิด และคำถามหลายๆรูปแบบเช่น
• มีจำนวนเฟรมเท่าไหร่ที่สามารถให้กับโปรเซสเซอร์แต่ละตัวได้
• กลุ่มของหน้าถูกพิจารณาให้สับเปลี่ยนหน้านั้นควรถูกจำกัดหรือไม่ เพื่อป้องกันไม่ให้โปรเซสที่ทำให้เกิดการผิดหน้า(page fault)ทำงาน
• ในกลุ่มของหน้าที่เราพิจารณา เราจะเลือกหน้าใดที่นำไปสับเปลี่ยน
ในหัวข้อที่1และ2จะเกี่ยวข้องกับการจัดการภายใน(Reident Set Management)ซึ่งเป็นการจัดการที่เกี่ยวข้องกับนโยบายที่เราสามารถกำหนดเองได้ เพื่อให้ระบบปฏิบัติการสามารถตัดสินใจว่า “ต้องการนำหน้าของโปรเซสเข้ามาเท่าไหร่ในหน่วยความจำ”หรือว่า“ต้องการให้หน่วยความจำหลักกับโปรเซสบางตัวเป็นจำนวนเท่าไหร่”โดยเราอาจพิจรณาจากหัวข้อต่อไปนี้
• ถ้าเราให้หน่วยความจำแก้โปรเซสใดๆน้อยเท่าไหร่ก็จะทำให้มีจำนวนโปรเซสเข้ามาใช้งานหน่วยความจำมากขึ้นเท่านั้นซึ่งจะทำให้ความน่าจะเป็นของระบบปฏิบัติการที่จะสามารถค้นพบโปรเซสอย่างน้อยหนึ่งโปรเซสที่พร้อมที่จะทำงานมากขึ้น และจะทำให้เราเสียเวลาในการสลับหน้าน้อยลง
• ถ้ามีจำนวนหน้าของโปรเซสหนึ่งๆที่สามารถอยู่ในหน่วยความจำหลักน้อย(จำนวนเฟรมน้อย)ก็จำทำให้อัตราการเกิดผิดหน้าสูงมากขึ้น เพราะว่าความสัมพันธ์ระหว่างอัตราการผิดหน้าและจำนวนเฟรมในหน่วยความจำเป็นแบบไฮเพอร์บอลา(hyperbola)
• นอกเหนือจากการกำหนดขนาดของหน้าคงที่แล้ว การให้หน่วยความจำเพิ่มกับโปรเซสใดโปรเซสหนึ่งจะไม่มีผลกระทบต่ออัตราการผิดหน้ามากนัก



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

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



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

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

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

5.6.2 วิธีสับเปลี่ยนแบบให้โอกาสครั้งที่สอง (Second Chance Page Replacement Algorithm)
เราสามารถปรับปรุงวิธีแบบมาก่อน-ออกก่อน (FIFO) ได้โดยการป้องกันการเปลี่ยนหน้าที่ถูกเรียกช้งานบ่อยออกไป ซึ่งเราสามารถทำได้โดยเช็คที่บิต Referenced (R) ของหน้าที่เข้ามานานที่สุด ถ้าบิต R มีค่าเป็น 0 ก็แสดงว่าหน้านั้นเก่าและไมได้ถูกเรียกใช้งานเลย ระบบก็สามารถทำการสับเปลี่ยนได้ทันที แต่ถ้าบิต R มีค่าเท่ากับ 1 ก็ให้กำหนดให้บิต R นั้นเป็น 0 ลนำหน้านั้นกลับไปเข้าแถวใหม่อีกครั้ง พร้อมกับทำการเปลี่ยนแปลงของหน้านั้นใหม่เหมือนดังหน้านั้นพึ่งเข้ามาในหน่วยความจำ จากนั้นก็ทำการค้นหาหน้าที่จะถูกสับเปลี่ยนต่อไป

วิธีการนี้เรียกว่า “เป็นการให้โอกาสครั้งที่สอง” กับหน้าที่เข้ามานานแต่ถูกเรียกใช้งานบ่อยนั่นเอง ในรูปที่ 5.30 (ก) เราจะเห็นได้ว่า A ถึง H นั้นจะถูกเก็บไว้ในลิค์ลิสต์ และ ถูกจัดเรียงโดยเวลาที่หน้าเหล่านี้เข้ามา ในหน่วยความจำ สมมุติว่าการผิดหน้าเกิดขึ้นเมื่อเวลาเท่ากับ 20 หน้าที่อยู่มานานที่สุดคือ หน้า A ซึ่งเข้ามาตั้งแต่เวลาเท่ากับ 0 (เมื่อโปรเซสเริ่มแรกทำงาน) ถ้าบิต R ในหน้า A มีค่าเป็น 0 หน้า A ก็จะถูกสับเปลี่ยนออกไป (โดยอาจจะมีการเขียนลงดิสก์ ถ้ามีการเปลี่ยนแปลง หรือ ทิ้งไปเฉย ๆ ถ้าไม่มีอะไรเปลี่ยนแปลง ซึ่งสามารถดูได้เข้ามาลิสต์ก็ถูกเปลี่ยนเป็นเวลาปัจจุบันคือ 20 พร้อมกันนั้น บิต R ก็ถูกลบเป็น 0 หน้าที่จะถูกเช็คเพื่อ สับเปลี่ยนออกต่อไปคือ หน้า B

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

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



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

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



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



• การเรียก 3 หน้าแรกเข้ามาใช้งานทำให้เกิดการผิดหน้า 3 ครั้ง
• การเรียกหน้า 2 จะสับหน้า 7 ออก เพราะหน้า 7 นั้นจะใช้งานอีกครั้ง เป็นลำดับที่ 18, หน้า 0 จะใช้งานอีกเป็นลำดับที่ 5 และหน้า 1 อยู่ในลำดับที่ 14
• การเรียกหน้า 3 ก็จะสับเปลี่ยนน้า 1 ออก เพราะ หน้า 1 เป็นหน้าสุดท้ายที่จะถูกเรียกใช้งาน (ลำดับที่ 8 จาก หน้าที่ 3) ในขณะที่หน้า 0 จะถูกเรียกเป็นลำดับที่ 1 และ หน้า 2 เป็นลำดับที่ 3 เมื่อเทียบจากตำแหน่งที่หน้า3 กำลังเข้าใช้งาน
วิธีนี้จะทำให้เกิดการผิดหน้า 9 ครั้ง ซึ่งดีกว่าวิธีแบบมาก่อน-ออกก่อนมาก (มีการผิดหน้า 15 ครั้ง) ถ้าเราไม่คิดการผิดหน้า 3 ครั้งแรก ซึ่งจะต้องเกิดขึ้นอย่างแน่นอน (ไม่ว่าจะวิธีใดๆ) จะเห็นได้ว่า แบบที่ดีที่สุดนี้ดีกว่าแบบ FIFO ได้ถึง 2 เท่า แต่น่าเสียดายที่วิธีแบบที่ดีที่สุดนี้ยากที่จะสร้างได้จริงๆ เพราะเราต้องรู้ในอนาคตว่าจะมีการเรียกหน้าใดเมื่อไหร่ ดังนั้น วิธีแบบที่ดีที่สุดนี้ จึงมีไว้เพื่อใช้ในการเปรียบเทียบเท่านั้น เช่น ถ้าเรามีวิธีการหรืออัลกอริทึ่มแบบใหม่ เราก็อาจเปรียบเทียบกันแบบที่ดีที่สุดนี้เพื่อจะได้ทราบว่า วิธีการแบบใหม่มีประสิทธิภาพใกล้เคียง แบบที่ดีที่สุดเท่าใด
5.6.5 การสับเปลี่ยนแบบที่ไม่ได้ใช้งาน-ออกก่อน (NRU: Not Recently Used)
เราสามารถนำวิธีการสับเปลี่ยนแบบวงรอบนาฬิกามาเพิ่มประสิทธิภาพในการทำงาน โดยการพิจารณาบิตที่สำคัญในตารางหน้าเพิ่มขึ้นอีกหนึ่งบิต ซึ่งก็คือวิธีแบบที่ไม่ได้ใช้งาน-ออกก่อน(NRU) เนื่องจากระบบปฏิบัติการสามารถทำการเก็บข้อมูลสถิติว่า หน้าใดที่กำลังถูกใช้ หรือ ที่ไม่ได้ใช้งาน ได้จากบิตในแถวของตารางหน้าที่แสดงสถานะ การทำงานของแต่ละหน้า (สามารถดูรายละเอียดก่อนหน้าที่หัวข้อ 5.5.1) บิต Referenced จะถูกกำหนดเป็น 1 เมื่อหน้านั้นถูกเรียกใช้งาน และ บิต Modified จะถูกกำหนดเป็น 1 เมื่อหน้านั้นมีการเปลี่ยนแปลง บิตทั้งสองนั้นเป็นฟิลด์ที่อยู่ในแถวของตารางหน้า และจะถูกเปลี่ยนแปลงค่าทุกครั้งเมื่อมีการเรียกใช้งาน หรือ ถูกอ้างอิงถึงดังนั้นการกำหนดค่าต่างๆ ควรเป็นหน้าที่ของฮาร์ดแวร์ เมื่อบิตเหล่านั้นถูกกำหนดเป็น 1 เมื่อใด บิตนั้นก็จะมีค่าเท่ากับ 1 จนกว่าระบบปฏิบัติการจะกำหนดกลับเป็น 0 โดยใช้ซอร์ฟแวร์
บิต R และ M ทั้งสองนี้สามารถนำกลับมาใช้ในการสร้างวิธีการสับเปลี่ยนหน้าแบบใหม่ได้ดังนี้ เมื่อโปรเซสหนึ่งๆ เริ่มทำงาน บิตทั้งสองในทุกๆ หน้าจะถูกกำหนดเป็น 0 โดยระบบปฏิบัติการ เมื่อครบวงรอบของระยะ เวลาหนึ่งๆ เช่น จาการแทรกของอินเทอร์รัพต์ (clock interrupt) บิต R ก็จะถูกทำความสะอาด หรือ ถูกกำหนดค่าเป็น 0 เพื่อเป็นตัวแยกหน้าที่ไม่ได้ถูกเรียกใช้งานออกจากหน้าอื่นๆ เมื่อมีการผิดหน้าเกิดขึ้น ระบบปฏิบัติการจะทำการตรวจสอบทุกหน้าและแบ่งหน้าเหล่านั้นออกเป็น 4 กลุ่มขึ้นอยู่กับค่าของบิต R และบิต M ดังนี้
กลุ่มที่ 0: ไม่ถูกเรียกใช้งาน และ ไม่มีการเปลี่ยนแปลงค่า
กลุ่มที่ 1: ไม่ถูกเรียกใช้งาน แต่ มีการเปลี่ยนแปลงค่า
กลุ่มที่ 2: ถูกเรียกใช้งาน แต่ ไม่มีการเปลี่ยนแปลงค่า
กลุ่มที่ 3: ถูกเรียกใช้งาน และ มีการเปลี่ยนแปลงค่า
ถึงแม้นจะดูเหมือนว่า ไม่มีทางเป็นไปได้ที่จะมีหน้าอยู่ในกลุ่มที่ 1 แต่ มันก็อาจจะเกิดขึ้นได้ ในกรณีที่หน้าในกลุ่มที่ 3 นั้นถูกระบบปฏิบัติการทำการกำหนดบิต R เป็น 0 เมื่อครบวงรอบของระยะเวลาหนึ่งๆ ซึ่งระบบปฏิบัติการไม่ได้กำหนดบิต M เป็น 0 ด้วย เพราะเราต้องการข้อมูลที่ว่าหน้านั้นจะต้องถูกเขียนทับกลับลงไปในดิสก์ด้วยหรือไม่ จึงทำการเคลียร์บิต R แต่ ไม่แตะต้อง บิต M และทำให้หน้านั้นอยู่ในกลุ่มที่ 1
วิธีแบบที่ไม่ได้ใช้งาน-ออกก่อน (NRU) นี้จะสุ่มเอาหน้าออกจากกลุ่มลำดับต่ำสุด (เช่นกลุ่มที่ 1 มีลำดับต่ำกว่ากลุ่มที่ 2 และ 3 ตามลำดับ) ที่มีหน้าของโปรเซสอยู่ นอกจากนั้น วิธีการนี้ยังดูเหมือนว่าจะพยายามที่จะนำเอาหน้าที่ถูกเปลี่ยนแปลงแต่ไม่ได้ถูกเรียกใช้งานหรืออ้างอิงถึง ออกทุกครั้งที่มีการครบวงรอบนาฬิกา (ประมาณ 20 msec) มากกว่าหน้าที่ไม่มีการเปลี่ยนแปลงแต่ถูกเรียกใช้งานบ่อย ข้อเด่นของวิธี NRU คือง่ายที่จะทำความเข้าใจ, ไม่ยากเกินไปที่จะนำมาใช้งานจริง และ มีประสิทธิภาพค่อนข้างดี (ถึงแม้นจะมี่เท่ากับแบบที่ดีที่สุด) และเป็นวิธีที่ใช้งานในระบบปฏิบัติการของเครื่อง Macintosh
5.6.6 การสับเปลี่ยนแบบใช้งานน้อยที่สุด-ออกก่อน (Least Recently Used)
เนื่องจากวิธีแบบที่ดีที่สุด เป็นไปไม่ได้ในทางปฏิบัติ เราจึงมุ่งหาวิธีที่จะให้ผลได้ใกล้เคียงแทน ความแตกต่างระหว่างแบบมาก่อน-ออกก่อน (FIFO) กับแบบที่ดีที่สุด (OPT) คือแบบ FIFO จะดูเวลที่สับเปลี่ยนหน้าเข้ามาในหน่วยความจำ ส่วนแบบ OPT จะดูเวลาที่หน้าถูกเรียกใช้งาน ถ้าเราใช้ข้อมูลในอดีตที่ผ่านมา ประมาณการอนาคตอันใกล้ เราอาจจะสับเปลี่ยนหน้าที่ไม่ได้ถูกเรียกใช้งาน เป็นเวลานานที่สุด ซึ่งเรียกว่าแบบใช้งานน้อยที่สุดออกก่อน (LRU)
วิธีการแบบใช้งานน้อยที่สุด-ออกก่อน จะบันทึกเวลาที่แต่ละหน้าถูกอ้างอิงครั้งล่าสุดไว้ เมื่อต้องการเลือกหน้า เพื่อสับเปลี่ยนออก ก็จะเลือกหน้าที่ไม่ได้ใช้มาเป็นเวลานานสุด (หน้าที่มีตัวเลขของเวลาน้อยที่สุด) จะเห็นได้ว่าวิธีการนี้ ได้มองย้อนเวลาไปในอดีต แทนที่จะมองไปในอนาคต ถึงแม้นว่า LRU น่าจะใช้งานได้ดีทางทฤษฏีแต่ก็ไม่ง่ายนักในทางปฏิบัติ เนื่องจากการใช้ LRU นั้น ระบบจะต้องสร้างลิงค์ลิสต์ของทุกๆ หน้าในหน่วยความจำ ที่มีหน้าที่ใช้งานน้อยที่สุดอยู่ที่หัวแถวและหน้าที่ใช้งานบ่อยอยู่ท้ายสุด และความยากของวิธีนี้ก็อยู่ที่ว่าลิสต์จะต้องทำการปรับเปลี่ยนทุกครั้งที่มีการอ้างอิงถึง หรือ มีการเรียกใช้งานในหน่วยความจำ ซึ่งการค้นหาหน้าในลิสต์, การทำการลบ, หรือ การย้ายหน้าไปมานั้น ล้วนแต่เป็นการทำงานที่ต้องใช้เวลาของโปรเซสเซอร์ทั้งสิ้น
อย่างไรก็ตาม การใช้ LRU ด้วยฮาร์ดแวร์พิเศษก็อาจจะเป็นทางเลือกอีกทางหนึ่ง โดยเราอาจจะพิจารณาจากตัวอย่างที่ง่ายที่สุดก่อน ซึ่งวิธีนี้จะใช้ฮาร์ดแวร์ที่มีตัวนับ หรือ counter (C) แบบ 64 บิต ที่จะทำการเพิ่มค่าทุกครั้งที่มีการเรียกใช้งาน นอกจากนี้ในตารางหน้าของแต่ละหน้าจะต้องมีฟิลด์ขนาดใหญ่ที่สามารถใส่ค่าของตัวนับนี้ได้ หลังจากที่มีการอ้างอิงหน่วยความจำในแต่ละครั้ง ค่า C ก็จะถูกบันทึกลงในตารางหน้าของหน้านั้นๆ เมื่อมีการผิดหน้า ระบบปฏิบัติการจะต้องทำการตรวจสอบทุกค่าของ C ในตารางหน้า เพื่อค้นหาหน้าที่มีค่า C น้อยที่สุด ซึ่งหน้านั้นก็คือหน้าที่ใช้งานน้อยที่สุดนั่นเอง
เรามาลองดูตัวอย่างของการใช้ LRU ด้วยฮาร์ดแวร์ดังกล่าว โดยสมมุติให้ในระบบเรามี n เฟรม ซึ่งทำให้ฮาร์ดแวร์นั้นจะต้องดูแลเมตทริกซ์ n*n บิต ซึ่งมีค่าเริ่มต้นเป็น 0 หมด เมื่อใดก็ตามเฟรม k เป็น 0 เมื่อมีการตรวจสอบ แถวที่มีค่าของบิตรวมกันน้อยที่สุดก็คือ แถวที่ถูกเรียกใช้งานน้อยที่สุด การทำงานของ อัลกอริทึ่มนี้จะแสดงในรูปที่ 5.33 โดยให้มีระบบมี 4 เฟรม และมีการอ้างอิงถึงหน้าต่างๆ ตามลำดับดังนี้
0 1 2 3 2 1 0 3 2 3


หลังจากที่หน้า 0 ถูกอ้างอิงถึง เราจะได้ดังในรูป 5.34(ก) และหลังจากที่หน้า 1 ถูกอ้างอิงถึง เราก็จะได้เมตทริกซ์ดังในรูป 5.34(ข) ตามลำดับ หลังจากที่ทุกหน้าได้ทำงานเสร็จเราจะได้เมตทริกซ์ในรูป 5.34(ญ) ซึ่งมีค่าของแถวที่ 1 รวมกันน้อยที่สุด ดังนั้นเมื่อมีการผิดหน้าเกิดขึ้น หน้าที่อยู่ในเฟรมที่ 1 ก็จะถูกเลือกออกเพราะไม่ได้ถูกเรียกใช้งานนานที่สุด แต่ถ้าเมตทริกซ์สุดท้ายได้ดังในรูปที่ 5.35 ก็ให้เราหาผลรวมของเฟรม 0 และ เฟรมที่ 3 ดังนี้
Frame 0 = (0 1 0 0) = 4 (ฐานสิบ)
Frame 3 = (0 0 1 0) = 2 (ฐานสิบ)
ก็ให้เลือกหน้าเฟรมที่ 3 ออก เพราะมีค่าน้อยกว่าเฟรมที่ 0
5.6.7 เปรียบเทียบวิธีการสับเปลี่ยนหน้าแบบต่างๆ
รูปที่ 5.35 เป็นตัวอย่างที่เปรียบเทียบวิธีการสับเปลี่ยนหน้าแบบ OPT, LRU, FIFO และ CLOCK โดย สมมุติว่าในระบบมีทั้งหมด 3 เฟรม


5.7 การแบ่งเป็นเซ็กเมนต์ (Segmentation)
เป็นวิธีการหนึ่งที่มีลักษณะการทำงานคล้ายกับการแบ่งเป็นหน้าของโปรเซส แต่ในวิธีนี้การแบ่งเป็นเซ็กเมนต์ หรือ Segmentation นั้น จะแบ่งโปรเซส หรือโปรแกรมออกเป็นส่วนๆ โดยแต่ละส่วนนั้นไม่จำเป็นต้องมีความยาวเท่ากัน (แต่ก็อาจจะมีการกำหนดให้อยู่ภายใต้ขนาดที่ใหญ่ที่สุดที่ระบบกำหนด) เช่นเดียวกับการแบ่งเป็นหน้าการแปลงแอ็ดเดรสทางตรรกเป็นแอ็ดเดรสจริงในหน่วยความจำจะต้องใช้ข้อมูล 2 ส่วนคือ เลขที่ของเซ็กเมนต์ และ ระยะเริ่มต้นจากเซ็กเมนต์นั้น (offset) ดังในรูปที่ 5.37
เนื่องจากการแบ่งเป็นเซ็กเมนต์ทำให้เกิดชิ้นส่วนที่ไม่เท่ากัน ซึ่งจะเหมือนการแบ่งหน่วยความจำแบบเปลี่ยนแปลงขนาดได้ ( Dynamic partitioning) แต่ข้อแตกต่างคือ โปรแกรมหนึ่งๆ อาจจะมีหลายส่วน (หรือหลายเซ็กเมนต์) ที่สามารถใช้งานในหลายๆ พาร์ติชั่นได้ และ ในพาร์ติชั่นเหล่านี้ก็ไม่จำเป็นต้องติดกันด้วย การแบ่งเป็นเซ็กเมนต์นี้จะช่วยลดปัญหาการสูญเสียพื้นที่ภายใน (Internal fragmentation) แต่จะมีการสูญเสียพื้นที่ภายนอกอยู่ เหมือนการแบ่งพาร์ติชั่นแบบเปลี่ยนแปลงขนาดได้นั่นเอง อย่างไรก็ตามเนื่องจากโปรเซสถูกแบ่งออกเป็นชิ้นเล็กๆ การสูญเสียพื้นที่ภายนอกก็ควรจะเล็กตามลงไปด้วย
ในขณะที่การแบ่งเป็นหน้านั้น โปรอกรมเมอร์จะไม่สามารถมองเห็นและมีส่วนร่วมได้ แต่การแบ่งเป็นเซ็กเมนต์นั้นโปรแกรมเมอร์จะสามารถมองเห็นมีส่วนร่วมในการจัดการกับโปรแกรมและข้อมูลของตนได้ โดยปกติโปรแกรมเมอร์หรือ คอมไพล์เลอร์จะทำการแบ่งโปรแกรมและข้อมูลออกเป็นส่วนๆเอง เช่นการใช้โมดูลในการเขียนโปรแกรม (Module) ผลของการแบ่งหน่วยความจำเป็นส่วนๆ ที่ไม่เท่ากัน จึงทำให้ความสัมพันธ์ระหว่างที่อยู่ทางตรรกกับที่อยู่จริงเป็นความสัมพันธ์ที่ค่อนข้างซับซ้อน โดยอาจจะใช้ตารางของเซ็กเมนต์ (segmentation table) เก็บรายละเอียดของแต่ละโปรเซสและที่อยู่เริ่มต้นของที่ว่างในหน่วยความจำ นอกจากเราจะเก็บจุดเริ่มต้นของเซ็กเมนต์ภายในแถวของตารางแล้ว เราจะต้องเก็บค่าความยาวของเซ็กเมนต์นั้นๆ ด้วย เพื่อเป็นการยืนยันว่าระบบจะไม่ใช้แอ็ดเดรสที่ไม่ถูกต้อง
เมื่อโปรเซสหนึ่งๆ เริ่มต้นทำงาน ที่อยู่ของตารางเซ็กเมนต์จะถูกโหลดเข้าไปในรีจิสเตอร์พิเศษซึ่งถูกควบคุมโดยฮาร์ดแวร์จัดการหน่วยความจำ ตัวอย่างเช่น ที่อยู่ n+m บิต ที่มีบิตทางด้านซ้ายมือสุด n บิต เป็นตัวบอกเลขที่ของเซ็กเมนต์ และ บิตทางด้านขวามือสุด m บิต เป็นตัวกำหนดระยะห่างจากขอบเซ็กเมนต์ ในรูปที่ 5.38 กำหนดให้ n=4 และ m=12 ดังนั้นขนาดใหญ่ที่สุดของเซ็กเมนต์ที่จะมีได้คือ 212 = 4096 และมีขั้นตอนของการแปลงแอ็ดเดรสดังนี้
• แยกตัวเลขบอกเซ็กเมนต์ทางด้านซ้ายมือจำนวน n บิต ออกจากแอ็ดเดรสทางตรรก
• ใช้ตัวเลขบอกเซ็กเมนต์เป็นอินเด็กซ์ในตารางของเซ็กเมนต์ เพื่อหาจุดเริ่มต้นแอ็ดเดรสจริงทางกายภาพของเซ็กเม้นนั้นๆ
• ทำการเปรียบเทียบระยะห่างจากขอบเซ็กเมนต์ (offset : m บิตทางขวามือ) กับขนาดความยาวของเซ็กเมนต์นั้น ถ้าระยะห่างนั้นมากกว่าความยาวของเซ็กเมนต์ ก็จะได้ที่อยู่ที่ไม่ถูกต้อง
• ถ้าระยะห่างนั้นน้อยกว่าความยาวของเซ็กเมนต์ ก็สามารถหาที่อยู่ของเซ็กเมนต์นั้นได้จาก ผลรวมของจุดเริ่มต้นของเซ็กเมนต์กับ ระยะ ห่างจากขอบของเซ็กเมนต์


จากรูปที่ 5.38 เราได้แอ็ดเดรสทางตรรกเป็น 0001001011110000 ซึ่งอยู่ในเซ็กเมนต์เลขที่ 1 และมีระยะห่างจากขอบเซ็กเมนตืเท่ากับ 752 สมมุติว่าส่วนนี้อยู่ในหน่วยความจำหลักเริ่มต้นจากแอ็ดเดรสจริง 0010000000100000 ดังนั้น แอ็ดเดรสจริงของเซ็กเมนต์นี้จะเป็น

0010000000100000 + 001011110000 = 0010001100010000

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



ในระบบที่มีการแบ่งเป็นเซ็กเมนต์นั้น เราทราบว่าโปรเซสแต่ละตัวจะมีตางรางของเซ็กเมนต์ (Segmentationtable) เป็นของตัวเอง และเมื่อทุกส่วนของเซ็กเมนต์ถูกโหลดเข้าไปในหน่วยความจำหลัก ตารางเซ็กเมนต์ของโปรเซสก็จะถูกสร้างขึ้นมา และถูกโหลดไว้ในหน่วยความจำหลัก แต่ละแถวของตารางจะประกอบไปด้วยที่อยู่เริ่มต้นของเซ็กเมนต์นั้นในหน่วยความจำหลัก และความยาวของเซ็กเมนต์นั้น เมื่อเรานำวิธีการแบ่งเซ็กเมนต์มาใช้กับหน่วยความจำเสมือน เราก็จำเป็นต้องใช้วิธีการเดียวกันกับที่ได้กล่าวมาแล้วข้างต้น แต่ตารางของเซ็กเมนต์นั้นจะซับซ้อนมากขึ้น ดังในรูปที่ 5.39 เพราะอาจจะมีเซ็กเมนต์บางส่วนของโปรเซสอยู่ในหน่วยความจำหลักหรือไม่ก็ได้ ดังนั้นเราจึงต้องการ 1 บิต (P) เป็นฟิลด์ของตารางที่จะบอกว่าเซ็กเมนต์ดังกล่าวอยู่ในหน่วยความจำหลักหรือไม่ถ้าบิตนั้นมีค่าเป็น 1 จะแสดงว่าเซ็กเมนต์นั้นอยู่ในหน่วยความจำหลักแล้ว แถวดังกล่าวก็จะต้องมีที่อยู่เริ่มต้นและความยาวของเซ็กเมนต์
อีก 1 บิตที่น่าสนใจในตารางเซ็กเมนต์ คือ บิตที่ใช้ในการเช็คความเปลี่ยนแปลง (Modified bit) ซึ่งจะทำหน้าที่เหมือนกับบิต Modified ในวิธีการแบ่งเป็นหน้า (paging) ซึ่งถ้าเซ็กเมนต์ใดมีการเปลี่ยนแปลง ตั้งแต่เมื่อเซ็กเมนต์นั้นถูกโหลดเข้าไปอยู่ในหน่วยความจำ ก็ให้ทำการเขียนเซ็กเมนต์นั้นกลับลงสู่ดิสก์เมื่อมีการสับเปลี่ยนเซ็กเมนต์ที่อยู่ในเฟรม นอกจากนี้ระบบสามารถเพิ่มเติมบิตควบคุมอื่นๆ ได้อีก เช่น บิตที่ใช้สำหรับการป้องกันการเข้าถึงข้อมูลในเซ็กเมนต์ที่ต้องการเป็นต้น
วิธีการพื้นฐานที่ใช้สำหรับอ่านคำจากหน่วยความจำ จะเกี่ยวข้องกับการเปลี่ยนแปลงที่เสมือน หรือแอ็ดเดรสทางตรรกที่ประกอบไปด้วยตัวเลขบอกเซ็กเมนต์ และระยะห่างจากขอบเซ็กเมนต์ ไปเป็นที่อยู่จริงทางกายภาพ โดยใช้ตารางเซ็กเมนต์ช่วย เนื่องจากตารางเซ็กเมนตืมีขนาดไม่คงที่ และขึ้นอยู่กับขนาดของโปรเซส ดังนั้นเราจึงไม่สามารถนำตารางนี้ไปเก็บไว้ในรีจิสเตอร์ได้ (จึงต้องเก็บไว้ในหน่วยความจำหลัก)


รูปที่ 5.40 จะแสดงถึงวิธีการทำงานของฮาร์ดแวร์ เมื่อมีโปรเซสบางตัวกำลังทำงาน รีจิสเตอร์จะทำหน้าที่เก็บที่อยู่เริ่มต้นของตารางเซ็กเมนต์สำหรับโปรเซสนั้น ตัวเลขบอกเซ็กเมนต์ของที่อยู่เสมือนจะใช้เป็นอินเด็กซ์ของตารางนั้นและใช้เป็นตัวค้นหาตำแหน่งจุดเริ่มต้นของเซ็กเมนต์นั้นในหน่วยความจำหลัก และค่าเริ่มต้นนี้จะถูกรวมกับค่าของระยะห่างจากขอบเซ็กเมนต์เพื่อที่จะผลิตที่อยู่จริงที่ต้องการต่อไป
5.7.2 การรวมวิธีการแบ่งเป็นหน้ากับการแบ่งเป็นเซ็กเมนต์เข้าด้วยกัน
ทั้งวิธีการแบ่งเป็นหน้า (Paging) และวิธีการแบ่งเป็นเซ็กเมนต์ (segmentation) จะมีข้อดีของแต่ละวิธีที่แตกต่างกัน ข้อดีของการแบ่งเป็นหน้าคือ การปกปิดไม่ให้โปรแกรมเมอร์มองเห็นการทำงานของมัน, การป้องกันการสูญเสียพื่นที่ภายนอก (external fragmentation) และจะทำให้ระบบใช้หน่วยความจำหลักอย่างมีประสิทธิภาพ นอกจากนี้ เนื่องจากหน้าของโปรเซสที่ถูกสลับเข้าและออกจากหน่วยความจำนั้น มีขนาดคงที่ และเท่ากัน จึงมีความเป็นไปได้ที่เราจะพัฒนาอัลกอริทึ่มที่ซับซ้อนเพื่อนำไปใช้ในการจัดการกับหน่วยความจำ ดังที่เคยกล่าวมาแล้วในหัวข้อเกี่ยวกับการสับเปลี่ยนหน้าในแบบต่างๆ
ส่วนการแบ่งเป็นเซ็กเมนต์นั้น โปรแกรมเมอร์สามารถมองเห็นการทำงานของการแบ่งเป็นเซ็กเมนต์ได้ และมีข้อดีตามที่กล่าวไปก่อนหน้า รวมทั้งความสามารถในการจัดกับโครงสร้างข้อมูลที่มีขนาดไม่คงที่, การทำโปรแกรมเป็นโมดูล, การสนับสนุนการแบ่งปันและการป้องกันเซ็กเมนต์ การรวมข้อดีของทั้งสองวิธีนั้น ในบางระบบจะใช้ฮาร์ดแวร์เป็นตัวช่วย และ ซอฟต์แวร์ของระบบปฏิบัติการจะต้องทำได้ทั้งสองวิธี
ในระบบที่มีการทำงานร่วมกันระหว่างการแบ่งเป็นหน้า และการแบ่งเป็นเซ็กเมนต์นั้น พื้นที่ใช้งานของผู้ใช้จะถูกแบ่งออกเป็นเซ็กเมนต์จำนวนหนึ่ง ตามที่โปรแกรมเมอร์กำหนด และแต่ในเซ็กเมนต์จะถูกแบ่งออกเป็นหน้าๆ ที่มีขนาดคงที่ และมีความยาวเท่ากับเฟรมในหน่วยความจำ ถ้าเซ็กเมนต์ใดมีความยาวน้อยกว่าขนาดของหน้า เซ็กเมนต์นั้นก็มีแค่ 1 หน้า จากมุมมองของโปรแกรมเมอร์นั้น แอ็ดเดรสทางตรรกจะประกอบไปด้วยเลขที่ของเซ็กเมนต์ และระยะห่างจากขอบของเซ็กเมนต์ และถ้ามองจากมุมของระบบ ระยะห่างจากขอบของเซ็กเมนต์ ก็จะประกอบไปด้วยเลขที่หน้า และระยะห่างจากขอบหน้าภายในเซ็กเมนต์นั่นเอง

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



จากรูปที่ 5.41 ได้แนะนำรูปแบบของตารางเซ็กเมนต์ และตารางหน้า อย่างที่เคยได้กล่าวไปแล้ว ในตารางเซ็กเมนต์จะมีค่าความยาวของเซ็กเมนต์ และฟิลด์ฐาน (Base field) ที่ใช้อ้างอิงถึงตารางหน้า บิตตรวจการใช้งานและการเปลี่ยนแปลงนั้นไม่จำเป็นที่จะต้องใช้ เพราะ การทำงานในส่วนนี้จะทำในระดับหน้า บิตควบคุมแบบอื่นๆ ก็อาจจะนำมาใช้ได้เพื่อการป้อง และ การแบ่งปันทรัพยากร แถวในตารางหน้าก็เป็นสิ่งที่จำเป็นของระบบการแบ่งเป็นหน้า โดยเลขที่หน้าจะถูกจับคู่กับเลขที่ของเฟรมในหน่วยความจำ
5.8 สรุป
หนึ่งในงานที่สำคัญและซับซ้อนของการออกแบบระบบปฏิบัติงานก็คือ การจัดการกับหน่วยความจำ การจัดการกับหน่วยความจำก็จะเกี่ยวข้องกับการดูแลหน่วยความจำหลักเสมือนเป็นทรัพยากรที่จะต้องถูกจัดสรรและ แบ่งปันระหว่างโปรเซสต่างๆ การใช้โปรเซสเซอร์ และ อุปกรณ์รับ-ส่งข้อมูลให้มีประสิทธิภาพนั้น เราจำเป็นต้องนำโปรเซสเข้าไปใช้งานในหน่วยความจำให้มากที่สุดเท่าที่จะทำได้ และการอนุญาตของระบบให้โปรแกรมเมอร์สามารถเขียนโปรแกรมทำงานที่มีขนาดเท่าใดก็ได้
การที่เราจะทำตามข้อเสนอที่กล่าวมาได้นั้น เราจะต้องใช้หน่วยความจำเสมือน เพราะในระบบที่มีหน่วยความจำเสมือนนั้นแอ็ดเดรสที่อ้างอิงถึงจะเป็นแอ็ดเดรสทางตรรกซึ่งสามารถเปลี่ยนแปลงเป็นแอ็ดเดรสจริงเมื่อโปรเซสกำลังทำงานได้ (at run-time) การจัดการดังกล่าวทำให้โปรเซสเซอร์สามารถอยู่ในหน่วยความจำหลัก หรืออยู่ในที่ใดก็ได้ (เช่นในฮาร์ดดิสก์) ที่สามารถทำการสลับโปรเซสเหล้านั้นให้เข้ามาทำงานได้ แนวความคิดของหน่วยความจำเสมือนนี้จะอนุญาตให้โปรเซสแยกส่วนเป็นชิ้นเล็กๆ ได้ และ ชิ้นส่วนเล็กๆของโปรเซส ไม่จำเป็นที่จะต้องอยู่ติดกันในหน่วยความจำหลักขณะที่ทำงาน และยิ่งกว่านั้นคือ โปรเซสยังสามารถทำงานได้ โดยไม่จำเป็นต้องให้ชิ้นส่วนเล็กๆทั้งหมดของโปรเซสนั้นอยู่ในหน่วยความจำหลักด้วย
เครื่องมือพื้นฐานที่ใช้ในการจัดการกับหน่วยความจำ ได้แก่ การแบ่งเป็นหน้า (paging) และการแบ่งเป็นเซ็กเมนต์ (segmentation) การแบ่งเป็นหน้านั้นโปรเซสแต่ละตัวจะถูกแบ่งเป็นหน้าที่มีขนาดเล็กและคงที่ ส่วนการแบ่งเป็นเซ็กเมนต์นั้นจะเป็นการแบ่งที่มีขนาดไม่คงที่ ดังนั้นการรวมวิธีการทั้งสองเข้าด้วยกันจึงเป็นสิง่ที่ดีเพราะเป็นการรวมข้อดีของทั้งสองเข้าด้วยกัน