เจาะลึก Belady's Anomaly กับ FIFO, LRU และ Optimal ใน Python
เรียนรู้การทำงานและวิธีตรวจสอบอัลกอริทึมการแทนที่หน้าเว็บ (Page Replacement) สำหรับข้อสอบ GATE CS พร้อมสคริปต์ Python ในการเช็กผลลัพธ์
ภาพประกอบจากคลังภาพสต็อก ไม่ใช่ภาพจากเหตุการณ์จริง
- ข้อสอบ GATE CS มักออกโจทย์การแทนที่หน้าเว็บ (Page Replacement) โดยใช้สตริงอ้างอิงและจำนวนเฟรม
- ผู้เขียนได้พัฒนาสคริปต์ Python ขนาดเล็กเพื่อใช้ตรวจสอบและเปรียบเทียบผลลัพธ์ของนโยบาย FIFO, LRU และ Optimal
- นโยบาย FIFO สามารถแสดงปรากฏการณ์ Belady's Anomaly ได้ เมื่อเพิ่มจำนวนเฟรมแล้วอาจเกิด Page Fault มากขึ้น
- LRU มีคุณสมบัติ Stack Property ทำให้หน้าเว็บที่เก็บไว้ใน k เฟรม เป็นสับเซตของ k+1 เฟรมเสมอ
โจทย์เกี่ยวกับการแทนที่หน้าเว็บ (Page Replacement) ในข้อสอบ GATE สาขา Computer Science ส่วนใหญ่เป็นการนับจำนวนครั้ง โดยผู้สอบจะได้สตริงอ้างอิง (Reference String) จำนวนเฟรม และนโยบายการทำงาน จากนั้นต้องเขียนเรียงแถวตัวอักษร ซึ่งทักษะที่มีประโยชน์คือการมีกระบวนการทำที่รวดเร็วโดยไม่ต้องคิดซ้ำซ้อน พร้อมวิธีตรวจสอบความถูกต้องจากโจทย์ฝึกหัด
บทเรียนหน่วยความจำของ Schoolabe ในหัวข้อ GATE ได้ใช้สตริงอ้างอิงที่มี 3 เฟรมเป็นตัวอย่างประกอบการอธิบาย โดยตำราแนะนำให้ใช้วิธีนับ FIFO อย่างระมัดระวังด้วยคิว แต่ไม่ได้พิมพ์เฉลยคำตอบไว้ให้ นโยบายทั้งสามแบบพร้อมด้วยชุดตัวเลขจึงถูกนำมาเขียนเป็นสคริปต์ Python ในไฟล์เดียวที่สามารถคัดลอกไปรันต่อได้ทันที
ภาพประกอบจากคลังภาพสต็อก ไม่ใช่ภาพจากเหตุการณ์จริง
สำหรับการทำมือ ผู้เขียนจะเขียนเนื้อหาเฟรมทั้งหมดไว้ใต้การอ้างอิงทุกตัว ไม่ใช่แค่ระบุ F หรือ Hit สำหรับนโยบาย FIFO จะขีดเส้นใต้หน้าเว็บที่เก่าที่สุด ส่วน LRU จะเขียนเรียงลำดับเฟรมตามความสดใหม่ของการใช้งานทุกครั้ง แม้จะใช้วิธีที่ช้ากว่าแต่จะช่วยให้มองเห็นข้อผิดพลาดได้ง่ายเมื่อทำคำตอบผิดพลาด
ผลลัพธ์ของนโยบาย LRU ในตัวอย่างนี้ได้เจ็ดครั้งเช่นกัน แสดงให้เห็นว่า LRU ไม่ได้เหนือกว่า FIFO เสมอไปในทุกสตริงอ้างอิง ด้านนโยบาย Optimal ทำได้ห้าครั้งซึ่งถือเป็นขีดจำกัดล่าง (Offline Lower Bound) เนื่องจากต้องมองเห็นเหตุการณ์ในอนาคต ทำให้ระบบจริงไม่สามารถใช้งานได้จริง และหากการทำมือของผู้สอบได้ผลลัพธ์น้อยกว่าค่านี้ แสดงว่านับจำนวนผิดพลาดแน่นอน
ปรากฏการณ์ Belady's Anomaly ถือเป็นหนึ่งในจุดจับผิดที่สำคัญในระบบปฏิบัติการ โดยปกติแล้วการเพิ่มหน่วยความจำหรือจำนวนเฟรมควรจะลดอัตราการเกิด Page Fault ลง แต่สำหรับนโยบาย FIFO การเพิ่มเฟรมจาก 3 เป็น 4 อาจทำให้เกิดข้อผิดพลาดเพิ่มขึ้นหรือเท่าเดิมได้ในบางกรณี ขณะที่ LRU และ Optimal จะไม่พบปัญหานี้เนื่องจากมีคุณสมบัติ Stack Property การใช้งานสคริปต์ Python จึงช่วยให้วิศวกรซอฟต์แวร์และนักศึกษาเข้าใจพฤติกรรมเบื้องหลังของหน่วยความจำเสมือนได้ชัดเจนยิ่งขึ้นนอกเหนือจากการคำนวณบนกระดาษ
ตำราได้ระบุว่า FIFO สามารถแสดงปรากฏการณ์ Belady's Anomaly ได้ ซึ่งเป็นสถานการณ์ที่การเพิ่มจำนวนเฟรมทำให้เกิด Page Fault มากขึ้น และมักถูกใช้เป็นข้อสอบดักทาง โดยสตริงในบทเรียนขยายเพิ่มขึ้นอีกสามหน้าเป็น 1 2 3 4 1 2 5 1 2 3 4 5 ซึ่งเมื่อทดสอบ FIFO ด้วย 4 เฟรมก็ยังคงให้ผลลัพธ์เป็น 7 ครั้งเท่าเดิม
ในขณะที่นโยบาย LRU เมื่อใช้สตริงเดียวกัน จำนวน Page Fault จะลดลงจาก 10 เหลือ 8 ตามคาด เนื่องจากมีคุณสมบัติ Stack Property กล่าวคือ หน้าเว็บที่ LRU เก็บไว้ใน k เฟรมจะเป็นสับเซตของสิ่งที่เก็บไว้ใน k+1 เฟรมเสมอ แต่นโยบาย FIFO จัดเก็บตามลำดับการมาถึงไม่ใช่ตามการใช้งาน จึงไม่มีคุณสมบัติดังกล่าว
เพื่อหาคำตอบว่าปรากฏการณ์นี้เกิดขึ้นบ่อยแค่ไหน ผู้เขียนได้สุ่มสตริงความยาว 12 การอ้างอิงผ่านหน้า 1 ถึง 5 โดยใช้ Seed ที่กำหนดเพื่อให้ผู้อ่านจำลองผลลัพธ์ตามได้ พร้อมเปรียบเทียบการทำงานระหว่าง 3 เฟรมและ 4 เฟรม ข้อสังเกตสำคัญคือหากโจทย์ระบุว่าเป็น LRU หรือ Optimal ตัวคำตอบจะไม่ใช่ Belady's Anomaly แน่นอน เพราะมีเพียง FIFO เท่านั้นที่เกิดปัญหานี้ได้
ที่มา: Dev.to
พบข้อมูลผิดพลาดในบทความนี้? แจ้งปัญหาบทความนี้
ความคิดเห็น
แสดงความคิดเห็น