การจัดตารางเวลา Round Robin ที่ปรับให้เหมาะสมสำหรับเวลามาถึงกระบวนการที่เปลี่ยนแปลงได้

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

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

Round Robin ทำงานอย่างไรกับเวลาที่มาถึงต่างกัน

เมื่อกระบวนการมีเวลามาถึงที่แตกต่างกัน อัลกอริทึมจะทำตามขั้นตอนเหล่านี้:

• กระบวนการเข้าสู่คิวที่พร้อมตามเวลาที่มาถึง

• CPU ทำหน้าที่กระบวนการแรกที่มีอยู่สำหรับระยะเวลาควอนตัม

• หากกระบวนการเสร็จสิ้นภายในควอนตัม กระบวนการจะยุติลง

• หากไม่เสร็จสิ้นจะย้ายไปยังจุดสิ้นสุดของคิวที่พร้อม

• ผู้มาใหม่เข้าร่วมคิวที่พร้อมและรอถึงตาของพวกเขา

• การสลับบริบทจะบันทึกสถานะของกระบวนการที่ยึดไว้ล่วงหน้า

คุณสมบัติหลัก

• ป้องกันความอดอยาก ทุกกระบวนการจะได้รับเวลา CPU ในที่สุด

• การกำหนดเวลาที่ยุติธรรม ควอนตัมเวลาที่เท่ากันสำหรับทุกกระบวนการ

• เวลาตอบสนองที่ดี เหมาะสำหรับระบบโต้ตอบและเรียลไทม์

• ค่าใช้จ่ายในการสลับบริบท ควอนตัมที่เล็กลงจะเพิ่มต้นทุนการสลับ

ตัวอย่าง 1 เวลาควอนตัม =2

พิจารณาสามกระบวนการที่มีเวลามาถึงและระเบิดต่างกัน:

แผนภูมิแกนต์ ? รอบโรบิน (ควอนตัม =2) P1 P2 P3 P1 P2 P3 0 2 4 6 8 9 14

การดำเนินการทีละขั้นตอน

การคำนวณเวลาเฉลี่ย

เวลาตอบสนองเฉลี่ย =(8 + 8 + 12) / 3 =9.33 หน่วย

เวลารอเฉลี่ย =(4 + 5 + 5) / 3 =4.67 หน่วย

ตัวอย่าง 2 เวลาควอนตัม =4

ด้วยขนาดควอนตัมที่ใหญ่กว่า:

แผนภูมิแกนต์ ? รอบโรบิน (ควอนตัม =4) P2 P3 P1 P2 P3 P1 0 4 8 12 15 20 24

เวลาตอบสนองเฉลี่ย =(22 + 15 + 19) / 3 =18.67 หน่วย

เวลารอเฉลี่ย =(14 + 8 + 10) / 3 =10.67 หน่วย

บทสรุป

การกำหนดเวลา Round Robin พร้อมเวลาที่มาถึงที่แตกต่างกันทำให้มีการจัดสรร CPU ที่ยุติธรรมในขณะที่จัดการการมาถึงของกระบวนการแบบไดนามิก ขนาดควอนตัมมีผลอย่างมากต่อประสิทธิภาพ ? ควอนตัมขนาดเล็กปรับปรุงเวลาตอบสนองแต่เพิ่มค่าใช้จ่ายในการสลับบริบท ในขณะที่ควอนตัมขนาดใหญ่อาจลดความยุติธรรมแต่ปรับปรุงปริมาณงาน