บทที่ 8 การจัดการหน่วยความจำหลัก

(MEMORY MANAGEMENT)

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

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

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

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

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

8.1.1 การกำหนดตำแหน่ง (Address Binding)

ในจานบันทึกอาจมีกระบวนการหรือโปรแกรมหลายตัว ซึ่งรอคอยที่จะเข้าทำงานในหน่วยความจำหลัก เราเรียกกลุ่มกระบวนการนี้ว่า แถวคอยขาเข้า (Input Queue)

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

โดยปกติการกำหนดค่า (Blinding) ของโปรแกรมและข้อมูลจะเกิดขึ้นในขั้นตอนต่าง ๆ ดังนี้

8.1.2 การนำโปรแกรมลงสู่หน่วยความจำแบบสัมพัทธ์ (Dynamic Loading)

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

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

วิธีนี้ไม่จำเป็นต้องพึ่งคำสั่งพิเศษใด ๆ จากระบบปฏิบัติการ แต่ผู้ใช้ต้องเป็นผู้จัดการบริหารโปรแกรมเอง

8.1.3 การเชื่อมต่อโปรแกรมแบบสัมพัทธ์ (Dynamic Linking)

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

8.1.4 การแบ่งส่วน (Overlays)

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

1. ส่วนการแปลรอบที่ 1 (Pass 1) 70 KB

2. ส่วนการแปลรอบที่ 2 (Pass 2) 80 KB

3. ตารางสัญลักษณ์ (Symbol table) 20 KB

4. โปรแกรมย่อยร่วม (Common routines) 30 KB

200 KB

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

เราเพิ่มตัวควบคุมการแบ่งส่วน (overlay driver) (ขนาด 10 K) และรวมกับส่วนแรก A นำลงในหน่วยความจำหลัก หลังจากทำการแปลรอบที่หนึ่งเสร็จแล้ว ตัวควบคุมการแบ่งส่วนจะอ่านส่วน B ลงสู่พื้นที่ของส่วน A และส่งการควบคุมต่อไปยังการแปลรอบที่สอง จะเห็นได้ว่าส่วนแบ่ง A มีขนาด 120 K และส่วนแบ่ง B มีขนาด 130 K (ดูรูปประกอบ)

ดังนั้นเราสามารถทำการแปลภาษา assembly โดยใช้เนื้อที่หน่วยความจำหลักที่มีเพียง 150 K ได้ แต่อาจช้าลงเล็กน้อยเพราะต้องมีการอ่านส่วน B เข้ามาระหว่างการทำงานด้วย

8.2 ตำแหน่งที่ว่างทางกายภาพกับตำแหน่งที่ว่างทางตรรกะ

(Logical versus Physical Address space)

ตำแหน่งที่ถูกสร้างโดย CPU มักหมายถึงตำแหน่งทางตรรกะ ส่วนตำแหน่งในหน่วยความจำ (นั่นคือ มีโปรแกรมหนึ่งถูกนำเข้าสู่รีจีสเตอร์เก็บตำแหน่ง (address register) ของหน่วยความจำแล้ว) จะหมายถึง ตำแหน่งทางกายภาพ

ช่วง Compile-time และ Load-time จะมีตำแหน่งทางตรรกะและทายกายภาพเหมือนกัน แต่ช่วง Execution-time จะมีตำแหน่งทางตรรกะและทางกายภาพต่างกัน ด้วยเหตุนี้เราจึงมักอ้างถึงตำแหน่งทางตรรกะว่า ตำแหน่งเสมือน (virtual address) กลุ่มของตำแหน่งทางตรรกะทั้งหมดที่ถูกสร้างโดยโปรแกรมจะถูกเรียกว่า ตำแหน่งที่ว่างทางตรรกะ (logical address space) ส่วนกลุ่มของตำแหน่งที่ว่างทางกายภาพที่เกี่ยวข้องกับตำแหน่งทางตรรกะเหล่านั้น ถูกเรียกว่า ตำแหน่งที่ว่างทางกายภาพ (physical address space) ดังนั้นช่วง execution-time ตำแหน่งที่ว่างทางตรรกะและทางกายภาพจึงต่างกัน

การจับคู่ (mapping) ของตำแหน่งเสมือนกับตำแหน่งจริงทางกายภาพจะถูกทำโดยหน่วยจัดการหน่วยความจำ (memory-management unit (MMU)) ซึ่งเป็นฮาร์ดแวร์ตัวหนึ่ง การจับคู่ (mapping) จะได้อธิบายในหัวข้อถัดไปในภายหลัง ตอนนี้เราลองมาจับคู่ด้วย MMU อย่างง่าย โดยการนำหลักการของรีจีสเตอร์ฐาน (based-register) ในหัวข้อ 2.5.3

จากรูปรีจีสเตอร์ฐาน กลายเป็น รีจีสเตอร์สำหรับการย้ายตำแหน่ง (relocation register) การอ้างอิงตำแหน่งในหน่วยความจำทุกครั้งต้องนำค่าอ้างอิงมาบวกกับค่ารีจีสเตอร์ฐานเสียก่นอ เพื่อให้ได้ค่าตำแหน่งจริง เช่น ค่ารีจีสเตอร์ฐานเท่ากับ 14000 ผู้ใช้ต้องการอ่านค่าจากตำแหน่ง 346 ก็จะไปอ่านจากตำแหน่งจริงที่ 14000 + 346 = 14346 เป็นต้น

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

จะสังเกตเห็นว่า ในระบบนี้มีการกำหนดตำแหน่ง 2 แบบ คือตำแหน่งทางตรรกะ (ค่า 0 ถึง max) และตำแหน่งจริง (ทางกายภาพ ค่าจาก R ถึง R+max โดย R เป็นค่าตำแหน่งเริ่มต้น) โปรแกรมของผู้ใช้จะใช้ตำแหน่งทางตรรกะเท่านั้น และคิดว่ากระบวนการทำงานอยู่ในตำแหน่ง 0 ถึง max ส่วนระบบปฏิบัติการจะรู้มากกว่า และสามารถอ้างอิงตำแหน่งจริงโดยตรงได้ในช่วงผู้ควบคุม (Monitor mode) ข้อมูลต่าง ๆ ที่โปรแกรมผู้ใช้ส่งให้ระบบปฏิบัติการ (เช่น ที่พักข้อมูล ตัวแปรในการเรียกระบบ) จะต้องมีการย้ายตำแหน่ง หรือคำนวณหาค่าตำแหน่งจริงให้ถูกต้อง โดยเฉพาะอย่างยิ่งการเรียกใช้อุปกรณ์รับส่งข้อมูล เพราะโปรแกรมผู้ใช้ให้ค่าตำแหน่งทางตรรกะมา ระบบต้องจับคู่หาตำแหน่งจริงก่อนนำไปใช้งาน

แนวคิดเรื่องการใช้ตำแหน่งทางตรรกะในการอ้างอิงแทนตำแหน่งจริงนี้เป็นหัวใจของการจัดการหน่วยความจำหลัก

 
8.3 การสับเปลี่ยน (Swapping)

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

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

การสับเปลี่ยนงาน อาจเกิดในระบบที่ใช้ศักดิ์เป็นเกณฑ์ ในการจัดตารางการทำงาน (Priority based) เมื่อมีงานที่มีศักดิ์สูงเข้ามาในระบบ ตัวจัดการหน่วยความจำอาจสับเปลี่ยนให้งานที่มีศักดิ์ต่ำออกไปพักชั่วคราว แล้วให้งานศักดิ์สูงเข้าทำงานจนเสร็จก่อน จึงสับงานศักดิ์ต่ำกลับมาทำงานต่อไป บางครั้งเรียกวิธีนี้ว่า หมุนออกและหมุนเข้า (roll-out , roll-in)

จะเห็นได้ว่า เวลาที่ใช้ในการสับเปลี่ยนงานนี้ (context-switch time) ค่อนข้างมาก สมมติว่ากระบวนการผู้ใช้มีขนาด 100 K หน่วยเก็บโปรแกรมชั่วคราว (backing store) มีอัตราการถ่ายโอนข้อมูล 1 M ต่อวินาที ดังนั้นเวลาที่ใช้ในการถ่ายโอนกระบวนการผู้ใช้จะเท่ากับ 100 K / 1 M = 100 มิลลิวินาที และถ้าอัตราเฉลี่ยในการที่หัวอ่านเคลื่อนไปยังตำแหน่งที่ต้องการ (Latency Time) เป็น 8 มิลลิวินาที เวลาในการสับเปลี่ยนจะเป็น 100 + 8 = 108 มิลลิวินาที การสับเปลี่ยนงานมักต้องสับงานเก่าออก และสับงานใหม่เข้าแทนที่ ดังนั้นเวลารวมในการสับเปลี่ยนงานครั้งหนึ่ง ๆ จะเท่ากับ 216 มิลลิวินาที

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

  1. ห้ามสับเปลี่ยนงานที่รอคอยการรับส่งข้อมูล หรือ
  2. การรับส่งข้อมูลนั้นต้องใช้ที่พักข้อมูลภายในเนื้อที่ของระบบปฏิบัติการเท่านั้น และระบบจะส่งต่อให้กระบวนการ เมื่อกระบวนการกำลังทำงานอยู่ในหน่วยความจำหลักเท่านั้น

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

8.4 การจัดสรรพื้นที่ที่ติดกัน (Contiguous Allocation)

หน่วยความจำหลักมักถูกแบ่งออกเป็น 2 ส่วน ส่วนหนึ่งสำหรับผู้ใช้ อีกส่วนหนึ่งสำหรับโปรแกรมของระบบปฏิบัติการเอง ซึ่งอาจจะวางตัวยอยู่ในตำแหน่งล่างสุด (0000) หรือ ตำแหน่งบนสุด (FFFF) ของหน่วยความจำหลัก แต่โดยปกติแล้วตารางสัญญาณการขัดจังหวะ (interrupt vector) จะอยู่ในตำแหน่งล่างสุดของหน่วยความจำ ดังนั้นจึงเป็นการสะดวกและปลอดภัยกว่า ที่จะให้ระบบปฏิบัติการอยู่ในตำแหน่งล่างนี้ด้วย (ดูรูปประกอบ)

                                                                    0

ระบบปฏิบัติการ

 

โปรแกรมผู้ใช้

 

 

                                                                512 K

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

8.4.1 การจัดสรรเนื้อที่แบบเดี่ยว (Single-Partition Allocation)

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

8.4.2 การจัดสรรเนื้อที่แบบพหุ (Multiple-Partition Allocation)

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

ตัวอย่างเช่น ระบบมีหน่วยความจำหลักขนาด 2560 K มีโปรแกรมของระบบใช้พื้นที่อยู่ 400 K ส่วนว่างที่เหลืออีก 2160 K สำหรับผู้ใช้ สมมติให้ในแถวคอยขาเข้า (input queue) มีกระบวนการดังรูป

ระบบใช้วิธีจัดตารางการทำงานระยะยาวแบบมาก่อน-ได้ก่อน ดังนั้นเราสามารถจัดสรรพื้นที่ให้แก่ กระบวนการ P1 , P2 และ P3 ได้ทันที ดังแผนภาพของหน่วยความจำในรูป (a) จะเห็นว่ามีพื้นที่ว่างขนาด 260 K ซึ่งไม่เพียงพอกกับขนาดของกระบวนการ P4 ที่รออยู่ในแถวคอยขาเข้า ถ้าระบบใช้วิธีจัดตารางการทำงานแบบเวียนเทียน (round-robin) โดยส่วนแบ่งเวลามีค่าเท่ากับ 1 หน่วยเวลา ณ เวลาที่ 14 หน่วยเวลา กระบวนการ P2 จะทำงานเสร็จพื้นที่ที่ P2 ครอบครองอยู่จะว่างลง ดังรูป (b) กระบวนการ P4 จึงสามารถเข้ามาทำงานได้ ดังแสดงในรูป (c) และเมื่อกระบวนการ P1 ทำงานเสร็จ ณ เวลาหน่วยที่ 28 ดังรูป (d) กระบวนการ P5 ก็สามารถเข้ามาใช้พื้นที่ที่ว่างลงต่อไปได้ ดังรูป (e)

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

ปัญหาข้างต้น เป็นปัญหาในระบบที่มีการจัดสรรพื้นที่แบบยืดหยุ่น (Dynamic Storage Allocation) ระบบจะพยายามจัดหาพื้นที่ว่าง ตามที่ผู้ใช้ร้องขอ (ขนาด n ไบต์) โดยตรวจดูจากกลุ่มพื้นที่ว่างในหน่วยความจำหลัก มีวิธีการจัดหาพื้นที่ว่างนี้หลายวิธี แต่ละวิธีพยายามให้การจัดสรรพื้นที่มีประโยชน์สูงสุด วิธีที่นิยมได้แก่ First-Fit , Best-Fit และ Worst-Fit

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

 

8.4.3 การสูญเปล่าของพื้นที่ย่อยภายนอกและภายใน (External and Internal Fragmentation)

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

จากรูป (a) จะพบว่ามีพื้นที่ว่างขนาด 260 K ในระบบ ซึ่งพื้นที่มีขนาดเล็กเกินกว่าที่จะบรรจุกระบวนการ P4 หรือ P5 ได้ แต่อย่างไรก็ตามเมื่อระบบเข้าสู่สถานะที่ (c) จะมีพื้นที่ย่อยสูญเปล่าภายนอกถึง 560 K (=360 + 260) ซึ่งมีขนาดเพียงพอสำหรับกระบวนการ P5 แต่ระบบไม่สามารถนำกระบวนการ P5 บรรจุลงได้ เนื่องจากพื้นที่ขนาด 560 K ดังกล่าว มิได้เป็นพื้นที่ว่างต่อเนื่องกัน แต่กลับเป็นพื้นที่ว่าง 2 พื้นที่ แยกกันคือ 300 K และ 260 K ซึ่งแต่ละพื้นที่มีขนาดเล็กกว่ากระบวนการ P5

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

รูปข้างต้น แสดงปัญหาอีกข้อหนึ่ง จะเห็นได้ว่า ถ้าเรามีพื้นที่ว่างขนาด 18,464 ไบต์ และกระบวนการใหม่ต้องการ 18,462 ไบต์ แล้วเราจัดสรรให้พอดี 18,462 ไบต์ ก็จะเหลือพื้นที่ว่าง 2 ไบต์ การเก็บข้อมูลพื้นที่ว่าง 2 ไบต์นี้ ต้องเสียค่าใช้จ่ายสูงกว่าเนื้อที่ 2 ไบต์มาก ดังนั้นเรามักจัดสรรพื้นที่ว่างที่เหลือเล็กน้อยนี้ให้เป็นส่วนหนึ่งของพื้นที่ที่ร้องขอไปเลย ซึ่งพื้นที่ส่วนนี้ ก็จะสูญเปล่าไปเช่นกัน เราเรียกว่า การสูญเปล่าของพื้นที่ย่อยภายใน (Internal Fragmentation)

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

จะเห็นว่าพื้นที่ว่างเล็ก ๆ 3 ผืน ( คือ 100K 300K และ 260K) ได้ถูกย้ายมารวมให้เป็นพื้นที่ผืนเดียวที่มีขนาด 660K

การบีบอัดหน่วยความจำของระบบไม่อาจทำได้กับทุกระบบ สังเกตจากรูปข้างบน ที่มีการเคลื่อนย้ายกระบวนการ P4 และ P3 กระบวนการทั้ง 2 ต้องสามารถทำงานต่อได้ เมื่อเข้ามาอยู่ในพื้นที่ใหม่ โดยตำแหน่งอ้างอิงภายในทั้งหมดจะต้องถูกปรับปรุง กรณีที่การย้ายตำแหน่งเป็นแบบคงที่ (static) และเกิดขึ้นในขณะ Load-time เราจะไม่สามารถบีบอัดหน่วยความจำได้ เราสามารถบีบอัดหน่วยความจำเฉพาะกรณีที่ การย้ายตำแหน่งเป็นแบบสัมพัทธ์ (Dynamic) และเกิดขึ้นขณะ Execution-time เท่านั้น

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

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

จะพบว่าถ้าเราทำการบีบอัดหน่วยความจำ ตามขั้นตอนวิธีอย่างง่ายดังกล่าวข้างต้น เราต้องเคลื่อนย้ายทั้งกระบวนการ P3 และ P4 ซึ่งมีขนาดโดยรวมเท่ากับ 600K (=200K + 400K)

แต่ในสถานการณ์นี้ เราอาจจะเคลื่อนย้ายเพียงกระบวนการ P4 ไปไว้บนกระบวนการ P3 ซึ่งเป็นการย้ายพื้นที่ขนาด 400K หรือเราอาจจะเคลื่อนย้ายกระบวนการ P3 มาไว้ใต้กระบวนการ P4 ซึ่งเป็นการย้ายพื้นที่ขนาดเพียง 200K จะเห็นได้ว่าในกรณีสุดท้ายนี้จะทำให้เกิดพื้นที่ว่างขนาดใหญ่ตรงกลางของพื้นที่หน่วยความจำหลักทั้งหมด แทนที่จะเป็นตอนท้าย นอกจากนี้ ถ้าเราเพิ่มการสังเกต (เพิ่มขั้นตอนวิธีให้ซับซ้อนขึ้น) จะเห็นว่า ถ้าในแถวคอยขาเข้ามีกระบวนการเหลืออยู่อีกเพียง 1 กระบวนการ (ที่ต้องการเข้ามาทำงานในระบบ) ซึ่งมีขนาดเพียง 450K เราก็อาจย้ายเพียงกระบวนการ P2 (ขนาด 100K) ไปไว้ที่ใดที่หนึ่ง ในหน่วยความจำ (เช่น ใต้กระบวนการ P4) ซึ่งถึงแม้ว่าการเคลื่อนย้ายดังกล่าวจะไม่ทำให้เกิดพื้นที่ว่างขนาดใหญ่ที่เป็นผืนเดียวกัน แต่ก็สามารถตอบสนองความต้องการ ด้านพื้นที่ของกระบวนการได้ (เพราะว่า ได้พื้นที่ว่างที่มีขนาดใหญ่เพียงพอ ที่จะบรรจุกระบวนการได้ทันท่วงที) จะเห็นว่าการหาวิธีการที่ดีที่สุด ในการบีบอัดหน่วยความจำหลักเป็นสิ่งที่ยากมาก

8.5 การแบ่งเป็นหน้า (Paging)

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

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

ระบบแบ่งเป็นหน้านี้ ต้องมีฮาร์ดแวร์ช่วย ดังรูป

ตำแหน่งทางตรรกะที่กระบวนการใช้จะถูกแบ่งเป็น 2 ส่วน หนึ่งคือ หมายเลขหน้า (Page number) p อีกส่วนหนึ่งเป็นระยะจากขอบหน้า (Page-offset) d หมายเลขหน้า ใช้เป็นตัวชี้ไปยังตารางเลขหน้า (Page table) ในตารางเลขหน้านี้จะมีค่าตำแหน่งจุดเริ่มต้น (Base Address) f ของหน้าจริงในหน่วยความจำหลัก ค่าตำแหน่งหน้าจริงนี้ รวมกับค่าระยะจากขอบหน้า (=f + d) จะเป็นตำแหน่งจริงในหน่วยความจำหลัก รูปถัดไปจะแสดงแผนภาพของหน่วยความจำทางตรรกะกับหน่วยความจำจริง

ขนาดของหน้ามักจะถูกกำหนดโดยฮาร์ดแวร์ โดยปกติจะมีขนาดเป็นเลขยกกำลัง 2 และนิยมใช้อยู่ระหว่าง 512 ไบต์ ถึง 16 เมกกะไบต์ ขึ้นอยู่กับสถาปัตยกรรมของเครื่องคอมพิวเตอร์นั้น ๆ ขนาด ถ้าขนาดของตำแหน่งว่างทางตรรกะคือ 2m และขนาดของหน้า (Page) คือ 2n ดังนั้นบิตด้านสูง (m n) ของตำแหน่งทางตรรกะ จะเป็นหมายเลขหน้า (Page number) ส่วนบิตล่าง n เป็น ระยะจากขอบหน้า (page offset) ดังนั้นตำแหน่งทางตรรกะเป็นดังนี้

page number         page offset

p

d

m n                         n

เมื่อ p เป็นดัชนีในตารางเลขหน้า (Page table) และ d คือ ตัวแทนภายในหน้า (Page)

เพื่อความเข้าใจ เราสมมติตัวอย่างง่าย ๆ โดยกำหนดให้ขนาดของหน้าเท่ากับ 4 ไบต์ ดูรูปถัดไปประกอบ

หน่วยความจำจริงมีขนาด 32 ไบต์ (รวม 8 หน้า) และสมมติให้หน่วยความจำทางตรรกะ (ในมุมมองของกระบวนการผู้ใช้) มี 4 หน้า (16 ไบต์) ตำแหน่งทางตรรกะ 0 จะแสดงค่าหมายเลขหน้า (Page number) 0 และระยะจากขอบ (Page offset) 0 จากหมายเลขหน้า 0 เทียบในตารางเลขหน้า (Page table) จะเห็นว่าตรงกับหน้าจริง (Frame) หมายเลข 5 ดังนั้นตำแหน่งทางตรรกะ 0 แปลงเป็นตำแหน่งจริงทางกายภาพ = (5 x 4) + 0 = 20 ตำแหน่งทางตรรกะ 3 (หน้า 0 ระยะห่าง 3) แปลงเป็นตำแหน่งจริง 23 (= (5 x 4) + 3) ตำแหน่งทางตรรกะ 4 คือ page 1 offset 0 เทียบกับตารางเลขหน้า page 1 จะเป็น frame 6 ดังนั้นตำแหน่งทางตรรกะ 4 แปลงเป็นตำแหน่งจริง 24 (= (6 x 4) + 0) และตำแหน่งทางตรรกะ 13 แปลงเป็นตำแหน่งจริง 9

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

ในระบบการแบ่งเป็นหน้านี้ จะไม่มีการสูญเปล่าพื้นที่ย่อยภายนอก เพราะเนื้อที่ในหน่วยความจำที่ยังว่างอยู่ (แม้จะไม่ต่อเนื่องกัน) สามารถจะจัดให้กระบวนการที่ต้องการได้เสมอ แต่อาจมีการสูญเปล่าพื้นที่ย่อยภายในได้ เพราะการจัดสรรเนื้อที่จริงจัดให้ทีละหน้าเป็นจำนวนเต็ม ถ้ากระบวนการต้องการใช้เนื้อที่ไม่เป็นจำนวนเต็มหน้า หน้าสุดท้ายย่อมเหลือเศษ (มีพื้นที่บางส่วนว่างเปล่า แต่ถูกจัดสรรไปให้กระบวนการด้วย) ไม่เต็มหน้า เช่นขนาดของหน้า (Page) เป็น 2048 ไบต์ กระบวนการต้องการ 72,766 ไบต์ คิดเป็นพื้นที่ 35 หน้า (Frame) กับอีก 1086 ไบต์ ดังนั้นเราต้องจัดสรรเนื้อที่จริงให้ 36 หน้า (Frame) มีการสูญเปล่าพื้นที่ย่อยภายในหน้า = 2048 1086 = 962 ไบต์ ในกรณีที่เลวร้ายที่สุด กระบวนการหนึ่งอาจต้องการพื้นที่ n หน้ากับอีก 1 ไบต์ ซึ่งทำให้เกิดการสูญเปล่าพื้นที่ย่อยภายในไปเกือบ 1 หน้าเต็ม (เพราะต้องจัดสรรเนื้อที่ให้ n + 1 หน้า) ถ้าขนาดของกระบวนการไม่ขึ้นกับขนาดของหน้าแล้ว การสูญเสียพื้นที่ย่อยภายในเฉลี่ยจะเท่ากับครึ่งหน้าต่อกระบวนการ เมื่อเป็นเช่นนี้ เราจึงควรเลือก (ถ้าเลือกได้) ให้หน้ามีขนาดเล็กไว้ดีกว่า แต่การที่กระบวนการหนึ่งมีหลายหน้า (เพราะหน้ามีขนาดเล็ก) ทำให้ต้องใช้พื้นที่ในการเก็บตารางเลขหน้า (Page table) มากขึ้น เมื่อหน้ามีขนาดใหญ่ พื้นที่ในการเก็บตารางเลขหน้าก็จะลดลง

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

(a) หน้าจริงที่ว่างอยู่ก่อนการจัดสรร (b) หน้าจริงที่ว่างหลังการจัดสรร

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

8.5.2 โครงสร้างของตารางเลขหน้า (Structure of the Page Table)

8.5.2.1 ฮาร์ดแวร์ช่วย (Hardware support)

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

การใช้รีจีสเตอร์เก็บตารางเลขหน้า เหมาะสมกับระบบที่มีตารางเลขหน้าขนาดเล็ก (เช่น 256 ช่อง) แต่สำหรับระบบที่มีตารางเลขหน้าขนาดใหญ่มาก (เช่น 1 ล้านช่อง) การเก็บเลขหน้าในรีจีสเตอร์พิเศษจะไม่คุ้มค่าอีกต่อไป จำเป็นต้องเก็บตารางเลขหน้าไว้ในหน่วยความจำหลักแทนและใช้รีจีสเตอร์เก็บตัวชี้ไปยังตารางเลขหน้าแทน (Page-Table Base Register PTBR) การเปลี่ยนตารางเลขหน้าใหม่ก็เพียงเปลี่ยนค่าในรีจีสเตอร์ (ค่าตัวชี้) นี้เพียง 1 ตัว ช่วยลดเวลาที่ใช้ในการสับเปลี่ยนงานได้มาก

การเก็บตารางเลขหน้าในหน่วยความจำหลักนี้ ทำให้การอ้างอิงตำแหน่งในหน่วยความจำต้องทำเป็น 2 ขั้นตอน คือ ขั้นแรก เมื่อเราต้องการอ้างอิงตำแหน่งทางตรรกะ i เราต้องอ่านค่าในตารางเลขหน้าก่อน (โดยดูตำแหน่งตารางเลขหน้าจาก PTBR) เพื่อดูว่าตรงกับหน้าจริง หมายเลขใด ขั้นตอนนี้จะต้องอ่านหน่วยความจำหลัก 1 ครั้ง ขั้นที่สอง ใช้หมายเลขหน้าจริงที่ได้รวมกับค่าระยะจากของหน้า (Page offset) ใน i เป็นค่าตำแหน่งจริงที่ใช้ในการอ่านค่าที่ต้องการจากหน่วยความจำหลักอีกครั้งหนึ่ง รวม 2 ขั้นตอนต้องอ่านหน่วยความจำหลัก 2 ครั้ง ต่อการอ้างอิงตำแหน่งทางตรรกะ 1 ครั้ง ดังนั้นความเร็วในการอ้างอิงหน่วยความจำจะลดลงครึ่งหนึ่ง ซึ่งไม่อาจยอมรับได้ (ช้าลงถึง 50 %)

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

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

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

อัตราส่วนของการพบหมายเลขหน้าที่ต้องการในรีจีสเตอร์เสริมต่อจำนวนการอ้างอิงทั้งหมด เรียกว่า อัตราส่วนการชน (Hit Ratio) เช่นมีอัตราส่วนการชนเป็น 80 % หมายความว่าหมายเลขหน้าที่ต้องการอยู่ในรีจีสเตอร์เสริม 80 % ของการอ้างอิงหน่วยความจำ ถ้าให้การค้นหาหมายเลขหน้าในรีจีสเตอร์เสริมเสียเวลา 20 นาโนวินาที และเวลาที่ใช้ในการอ่านหน่วยความจำเป็น 100 นาโนวินาที การอ้างอิงหน่วยความจำ โดยที่พบหมายเลขหน้าในรีจีสเตอร์เสริม จะเสียเวลาเท่ากับ 100 + 20 = 120 นาโนวินาที แต่ถ้าไม่พบในรีจีสเตอร์เสริม (เสียวเลาค้นหาไปแล้ว 20 นาโนวินาที แต่ไม่พบ) จะต้องอ่านหน่วยความจำอีก 2 ครั้ง (2 x 100 = 200 นาโนวินาที) จึงเสียเวลาไปรวม 20 + 200 = 220 นาโนวินาที การหาเวลาเฉลี่ยต้องคิดอัตราส่วนการชนเข้าไปด้วย ดังนั้น

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

= (0.80 x 120) + (0.20 x 220) = 140 นาโนวินาที

จากตัวอย่างนี้ จะพบว่า การอ้างอิงหน่วยความจำหลักช้าลงกว่าการอ่านโดยตรง 40 % (จาก 100 เป็น 140 นาโนวินาที) ถ้าให้อัตราส่วนการชนเป็น 98 %

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

= (0.98 x 120) + (0.02 x 220) = 122 นาโนวินาที

ลดเวลาที่เสียไปในการอ้างอิงหน่วยความจำหลักเป็นช้าลงกว่าแบบโดยตรงเพียง 22 %

จำนวนรีจีสเตอร์เสริมย่อยมีผลโดยตรงต่ออัตราส่วนการชน จากการทดลองพบว่าการใช้รีจีสเตอร์เสริมระหว่าง 16 ถึง 512 ตัว สามารถให้อัตราส่วนการชน 80 ถึง 98 %

8.5.2.2 การป้องกัน (Protection)

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

มีบิตอีกตัวที่มักจะติดอยู่กับแต่ละช่องในตารางเลขหน้า คือ valid-invalid bit ถ้าบิตเป็น valid แสดงว่าค่าที่ชี้ไปยังตำแหน่งว่างทางตรรกะของกระบวนการเป็นหน้าที่ถูกต้อง ถ้าบิตเป็น invalid แสดงว่าค่าที่ชี้ไปยังตำแหน่งว่างทางตรรกะของกระบวนการนั้นไม่ถูกหน้า ดังนั้นตำแหน่งที่ผิดจะถูกจับได้โดยการใช้ valid-invalid bit ตัวอย่างเช่น ในระบบที่มี 14 bit (0 ถึง 16,383) แล้วเรามีโปรแกรมที่ต้องใช้ตำแหน่ง 0 ถึง 10,468 กำหนดให้ขนาดของหน้าเป็น 2 K ดังรูป

ตำแหน่งในหน้า 0 ถึง 5 ถูกจับคู่ในตารางหน้าได้เป็นปกติ แต่มีบางกระบวนการพยายามจะสร้างตำแหน่งในหน้า 6 หรือ 7 อย่างไรก็ตามจะพบว่าบิตถูกกำหนดเป็น invalid คอมพิวเตอร์ก็จะแจ้งให้ระบบปฏิบัติการทราบว่ามีการอ้างอิงผิดหน้า

สังเกตได้ว่าโปรแกรมดังกล่าวใช้พื้นที่ถึงตำแหน่ง 10,468 เพราะฉะนั้น การอ้างอิงที่เกินกว่านั้นน่าจะไม่ถูก แต่การอ้างอิงในหน้า 5 อยู่ในช่วง 2 K เพราะฉะนั้น การเข้าถึงตำแหน่ง 12,287 ยังถือว่างถูกต้อง แต่ตำแหน่งจาก 12,288 ถึง 16,838 ถึงจะไม่ถูกต้อง ปัญหานี้ถือเป็นปัญหาการสูญเสียพื้นที่ย่อยภายในของการแบ่งหน้า

กระบวนการทั่วไป ส่วนใหญ่ใช้เนื้อที่เพียงเล็กน้อยก็พอเพียงต่อการทำงานแล้ว ดังนั้นถ้าเราสร้างตารางเลขหน้าทั้งตารางให้แต่ละกระบวนการก็จะเป็นการเสียเนื้อที่ไปโดยเปล่าประโยชน์ บางระบบจึงมีฮาร์ดแวร์เสริมอีกเรียกว่า รีจีสเตอร์ขอบเขตของตารางเลขหน้า (Page-Table Length Register PTLR) เพื่อเก็บขนาดของตารางเลขหน้า ถ้ามีการอ้างอิงตำแหน่งเกินขนาดของตารางเลขหน้านี้ไป ก็จะเกิดข้อผิดพลาดไปยังระบบปฏิบัติการ

8.5.3 การแบ่งหน้าแบบหลายระดับ (Multilevel Paging)

ในระบบคอมพิวเตอร์สมัยใหม่สนับสนุนในเรื่องพื้นที่ว่างทางตรรกะขนาดใหญ่มาก ๆ ได้ (232 ถึง 264) ฉะนั้นตารางหน้าก็จะใหญ่ตามไปด้วย ตัวอย่างเช่น ถ้าระบบที่มีพื้นที่ว่างทางตรรกะแบบ 32 บิต ถ้าขนาดของหน้าในแต่ละระบบคือ 4 K (212) ดังนั้นตารางหน้าต้องมีเป็นล้านช่อง (232 / 212) วิธีแก้อย่างง่าย คือแบ่งตารางหน้าออกเป็นชิ้นเล็ก ๆ วิธีหนึ่งคือ ใช้วิธีแบ่งหน้าเป็น 2 ระดับ ดูรูป

กลับไปที่ตัวอย่าง ที่ระบบ 32 บิต ขนาดของหน้า 4 K ตำแหน่งทางตรรกะถูกแบ่งโดยหมายเลขหน้า (Page number) มี 20 บิต ระยะจากขอบ (Page offset) มี 12 บิต แล้วเราแบ่งตารางหน้าออกอีกจะได้หมายเลขหน้า (Page number) เหลือ 10 บิต และ ระยะจากขอบ (Page offset) อีก 10 บิต ดังภาพ

page number             page offset

P1

P2

d

                                                  10            10                12

ซึ่ง P1 คือ ดัชนีที่มาจากตารางเลขหน้าภายนอก (outer page table) และ P2 คือ ตัวแทนภายในหน้าของตารางหน้าภายนอก

การแปลตำแหน่งทำได้ดังรูป

สถาปัตยกรรมของ VAX สนับสนุนการแบ่งหน้าเป็น 2 ระดับ VAX เป็นเครื่อง 32 บิต ที่มีขนาดของหน้าเป็น 512 ไบต์ ตำแหน่งทางตรรกะถูกแบ่งเป็น 4 ส่วนเท่า ๆ กัน แต่ละส่วนมี 230 ไบต์ แต่ละส่วน (section) เป็นตัวแทนของตำแหน่งว่างทางตรรกะของกระบวนการที่แตกต่างกัน 2 บิตแรกใช้แทน section อีก 21 บิตแทนหมายเลขหน้าทางตรรกะของ section นั้น 9 บิตที่เหลือแทน ระยะจากขอบ (page offset) ในหน้านั้น ดังภาพ

         section                     page                     offset

s

p

d

                                        2                             21                             9

s แทน หมายเลขส่วน (section)

p แทน ดัชนีในตารางเลขหน้า

d คือ ตัวแทนภายในหน้า

8.5.4 ตารางเลขหน้าแบบผกผัน (Inverted Page Table)

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

ตัวอย่างเช่นในระบบ IBM RT ตำแหน่งเสมือนในระบบประกอบไปด้วย

<process-id, page-number, offset>

แต่ละช่องของตารางเลขหน้าแบบผกผันคือ คู่ของ <process-id, page-number> เมื่อมีการอ้างอิงหน่วยความจำ ส่วนของตำแหน่งเสมือนซึ่งประกอบไปด้วย <process-id, page-number> จะถูกนำเสนอไปที่ระบบย่อยของหน่วยความจำ ตารางเลขหน้าแบบผกผันจะถูกค้นหาคู่ทันที ถ้าพบคู่จะบอกว่าอยู่ที่ช่อง i ดังนั้นตำแหน่งทางกายภาพ <i, offset> ก็จะถูกสร้างขึ้น ถ้าไม่พบคู่ดังกล่าว ก็บอกว่าเกิดการผิดพลาด

8.5.5 การใช้หน้าร่วม (Shared Pages)

ข้อดีอีกข้อหนึ่งของวิธีแบ่งเป็นหน้า ก็คืออาจใช้หน้าร่วมกันได้ ซึ่งมีประโยชน์มากในระบบแบบปันส่วน (Time-sharing) ลองคิดดูว่า ถ้ามีผู้ใช้ 40 คน กำลังใช้ระบบพร้อมกัน และใช้ text editor แก้ไขแฟ้มข้อมูลอยู่ โดยที่โปรแกรมนี้ใช้เนื้อที่โปรแกรม 150 K และเนื้อที่เก็บข้อมูล 50 K สำหรับผู้ใช้ 40 คน เราต้องใช้เนื้อที่ในหน่วยความจำถึง 40 x (150+50) = 8000 K แต่ถ้าส่วนของโปรแกรมสามารถใช้ร่วมกันได้ (ไม่เปลี่ยนแปลง Reentrant) ดังรูป

ในรูปจะเห็น text editor ขนาด 3 หน้า (หน้าละ 150 K) และมีกระบวนการผู้ใช้ 3 คนใช้ร่วมกันอยู่ โปรแกรมส่วนที่ไม่มีการแก้ไขระหว่างการทำงาน (Reentrant Code หรือ Pure Code) นี้ สามารถใช้งานร่วมกันได้หลาย ๆ กระบวนการในเวลาเดียวกัน โดยแต่ละกระบวนการมีรีจีสเตอร์ และข้อมูลภายในของตนเองสำหรับการทำงาน เราจึงอาจเก็บโปรแกรมในหน่วยความจำจริงไว้เพียงชุดเดียว ตารางเลขหน้าของแต่ละกระบวนการจะชี้ไปยังหน้าจริงที่เดียวกัน โดยจะแตกต่างกันเฉพาะส่วนที่เป็นข้อมูล ดังนั้นเราใช้เนื้อที่จริงเพียง 150+(40x50) = 2150 K แทนที่จะเป็น 8000 K

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

 

8.6 การแบ่งเป็นตอน (Segmentation)

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

8.6.1 วิธีพื้นฐาน (Basic Method)

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

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

เพื่อความสะดวกชื่อตอน มักใช้ตัวเลขแทนเรียกว่า เลขตอน (segment-number) โดยปกติตัวแปลภาษา assembly หรือตัวแปลภาษาชั้นสูงอื่น ๆ จะแบ่งโปรแกรมเป็นตอน ๆ โดยอัตโนมัติ เช่น ตัวแปลภาษาปาสคาล อาจแบ่งตอนเป็น

ตอนที่ 1 เก็บตัวแปรร่วม (Global variables)

ตอนที่ 2 เป็นเนื้อที่สำหรับการเรียกโปรแกรมย่อย เพื่อใช้เก็บค่าตัวแปรต่าง ๆ และตำแหน่งในการเรียกกลับ

ตอนที่ 3 เก็บคำสั่งของโปรแกรมย่อยต่าง ๆ

ตอนที่ 4 เก็บตัวแปรภายใน (Local variables) สำหรับโปรแกรมย่อย

8.6.2 ฮาร์ดแวร์ (Hardware)

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

ตำแหน่งทางตรรกะแบ่งได้เป็นสองส่วน คือ หมายเลขตอน(segment number) s และระยะจากขอบ (offset) d เราใช้หมายเลขตอนเป็นตัวชี้ไปยังข้อมูลในตารางเลขตอน ข้อมูลแต่ละช่องในตารางเลขตอนมีค่าฐาน (base) และขอบเขตของตอน (limit) ระยะจากขอบ d จะมีค่าระหว่าง 0 จนถึงค่าขอบเขตของตอน ถ้า d มากกว่าขอบเขตของตอนแล้ว จะเกิดข้อผิดพลาด รายงานไปยังระบบปฏิบัติการ (อ้างอิงตำแหน่งออกนอกตอน) ถ้าค่า d ไม่เกินค่าขอบเขตของตอน ฮาร์ดแวร์ก็จะนำค่า d ไปบอกกับฐานเป็นค่าตำแหน่งจริง จะเห็นได้ว่าตารางเลขตอน ก็คือ แถวลำดับ (array) ของรีจีสเตอร์ฐาน และขอบเขต

ตัวอย่างในรูปถัดไป มี 5 ตอน หมายเลข 0 จนถึง 4 แต่ละตอนเก็บอยู่ในหน่วยความจำทางกายภาพ ดังแสดงในรูป

ตารางเลขตอนจะมีค่าฐานและขอบเขตของแต่ละตอน เช่น ตอนที่ 2 มีค่าฐานหรือตำแหน่งเริ่มต้นที่ 4300 และค่าขอบเขต 400 ไบต์ ดังนั้นการอ้างอิงไบต์ที่ 53 ของตอนที่ 2 จะเป็นค่าตำแหน่งจริง 4300 + 53 = 4353 ตำแหน่งทางตรรกะของตอนที่ 3 ไบต์ที่ 852 เท่ากับตำแหน่งจริง 3200 + 852 = 4052 การอ้างอิงตำแหน่งไบต์ที่ 1222 ของตอนที่ 0 จะทำให้เกิดข้อผิดพลาด รายงานไปยังระบบปฏิบัติการ เพราะค่า 1222 เกินกว่าค่าขอบเขต (> 1000 ไบต์ของตอนที่ 0)

8.6.3 การสร้างตารางเลขตอน (Implementation of Segmentation Tables)

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

ถ้าโปรแกรมหนึ่งแบ่งเป็นตอน ๆ จำนวนมาก เราก็ไม่สามารถเก็บตารางเลขตอนในรีจีสเตอร์พิเศษได้ ต้องเก็บตารางเลขตอน(ขนาดใหญ่)ไว้ในหน่วยความจำหลักแทน แล้วใช้รีจีสเตอร์พิเศษ เก็บตัวชี้ไปยังตารางเลขตอนอีกที (Segment Table Base Register STBR) เนื่องจากโปรแกรมต่าง ๆ มีจำนวนตอนไม่เท่ากัน เราจึงอาจเก็บค่าจำนวนตอนไว้ในรีจีสเตอร์พิเศษเรียกว่า Segment Table Length Register (STLR) เช่น ตำแหน่งทางตรรกะเป็น (s,d) เราต้องตรวจดูว่า s < STLR หรือไม่ (หมายเลขตอนไม่เกินจำนวนตอนที่มีจริง) แล้วอ่านค่าข้อมูลจากตารางเลขตอนในหน่วยความจำที่ตำแหน่ง (STBR + s) เมื่อได้ข้อมูลเลขฐานและขอบเขตแล้ว ก็ทำเหมือนเดิมคือ ตรวจว่า d < ขอบเขตหรือไม่ แล้วเอาค่า d บวกกับค่าฐานเป็นตำแหน่งจริงในหน่วยความจำหลัก

เหมือนกับการแบ่งเป็นหน้า การอ่านหน่วยความจำ 2 ครั้งต่อการอ้างอิงตำแหน่งครั้งหนึ่ง ทำให้ระบบทำงานช้าลง 2 เท่า จึงมีการใช้รีจีสเตอร์เสริมหลายตัวช่วยเก็บค่าที่เพิ่งจะใช้ไป และเช่นเดียวกัน เราใช้รีจีสเตอร์เสริมไม่มากนัก ก็สามารถลดเวลาเฉลี่ยในการอ้างอิงหน่วยความจำลงเป็นไม่เกิน 10 หรือ 15 % จากการอ้างอิงแบบโดยตรง

8.6.4 การป้องกันและการใช้ตอนร่วมกัน (Protection and Sharing)

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

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

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


8.6.5 การสูญเปล่าพื้นที่ย่อย (Fragmentation)

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

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

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