Multilevel Feedback Queue (MLFQ) เป็นอัลกอริธึมการตั้งเวลา CPU ที่รักษาคิวที่พร้อมใช้งานหลายคิว โดยแต่ละคิวมีระดับความสำคัญและค่าควอนตัมเวลาที่แตกต่างกัน กระบวนการใหม่เริ่มต้นที่คิวที่มีลำดับความสำคัญสูงสุด และขึ้นอยู่กับลักษณะการทำงาน กระบวนการเหล่านั้นอาจถูกเลื่อนระดับหรือลดระดับระหว่างคิว แนวทางการปรับตัวนี้สร้างสมดุลระหว่างความต้องการของทั้งกระบวนการโต้ตอบและกระบวนการที่ต้องใช้ CPU มาก
โครงสร้างคิวข้อเสนอแนะหลายระดับ คิว 0 (ลำดับความสำคัญสูงสุด) ควอนตัมเวลา:1 คิว 1 (ลำดับความสำคัญปานกลาง) ควอนตัมเวลา:2 คิว 2 (ลำดับความสำคัญต่ำสุด) CPU FCFS กระบวนการใหม่ ลดระดับหากเวลาหมดอายุ Aging:เลื่อนระดับหลังจากรอ กฎการเคลื่อนที่ของกระบวนการ ? กระบวนการใหม่เริ่มต้นในคิว 0 ? หากควอนตัมเวลาหมดลง ? ย้ายไปคิวล่างถัดไป ? กลไกการแก่ชราช่วยป้องกันความอดอยาก
MLFQ ทำงานอย่างไร
อัลกอริธึมทำงานโดยมีหลักการสำคัญดังต่อไปนี้:
-
การตั้งเวลาตามลำดับความสำคัญ คิวที่มีลำดับความสำคัญสูงกว่าจะเสิร์ฟก่อน
-
ควอนตัมเวลาที่แปรผันได้ คิวที่มีลำดับความสำคัญสูงกว่าจะมีส่วนแบ่งเวลาที่สั้นกว่า
-
การปรับลำดับความสำคัญแบบไดนามิก กระบวนการจะย้ายไปมาระหว่างคิวตามพฤติกรรม
-
กลไกการแก่ชรา ป้องกันความอดอยากโดยส่งเสริมกระบวนการรอคอยที่ยาวนาน
ตัวอย่าง
พิจารณาสามกระบวนการที่มีลักษณะดังต่อไปนี้:
โดยที่คิว 0 มีควอนตัมเวลา =1, คิว 1 มีควอนตัมเวลา =2 และคิว 2 โดยใช้ FCFS:
MLFQ ไทม์ไลน์การดำเนินการ P1 P2 P3 P2 P1 P2 P1 (คิว 2 - FCFS) 0 1 2 3 4 6 8 14 Q0 Q0 Q0 Q1 Q1 Q1 Q2
กรณีการใช้งาน
MLFQ มีประสิทธิภาพอย่างยิ่งในสถานการณ์ต่อไปนี้:
-
แอปพลิเคชันเชิงโต้ตอบ เว็บเบราว์เซอร์ โปรแกรมแก้ไขข้อความ และแอปพลิเคชัน GUI ได้รับประโยชน์จากเวลาตอบสนองที่รวดเร็วสำหรับการโต้ตอบของผู้ใช้
-
ระบบแบ่งเวลา ระบบที่มีผู้ใช้หลายรายซึ่งมีทั้งกระบวนการโต้ตอบและกระบวนการแบบแบตช์อยู่ร่วมกัน
-
ระบบเรียลไทม์ ระบบที่ต้องการระดับความสำคัญที่แตกต่างกันสำหรับงานที่สำคัญและไม่สำคัญ
-
แอปพลิเคชันเกม เกมจำเป็นต้องมีการจัดการอินพุตแบบตอบสนองในขณะที่จัดการงานเบื้องหลัง เช่น เสียงและเครือข่าย
ข้อดี
-
กระบวนการตอบสนองสั้นที่ได้รับการปรับปรุงได้รับความสนใจอย่างรวดเร็วในคิวที่มีลำดับความสำคัญสูง
-
การปรับลำดับความสำคัญแบบไดนามิกจะปรับให้เข้ากับรูปแบบพฤติกรรมของกระบวนการโดยอัตโนมัติ
-
กลไกการป้องกันความอดอยากทำให้แน่ใจได้ว่ากระบวนการที่รอนานจะได้รับเวลา CPU ในที่สุด
-
ปริมาณการประมวลผลที่ดีต้องการการประมวลผลแบบโต้ตอบและแบบเป็นชุดอย่างมีประสิทธิภาพ
-
ควอนตัมเวลาการกำหนดค่าที่ยืดหยุ่นและจำนวนคิวสามารถปรับให้เข้ากับปริมาณงานเฉพาะได้
ข้อเสีย
-
ความซับซ้อนในการใช้งาน การจัดการหลายคิวด้วยนโยบายที่แตกต่างกันจะเพิ่มความซับซ้อนของระบบ
-
ค่าโสหุ้ยที่สูงขึ้น &ลบ
