อัลกอริทึมการกำหนดเวลา Round Robin พร้อมตัวอย่าง

Round-Robin Scheduling คืออะไร?

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

ในการจัดตารางงานแบบ Round-robin งานที่พร้อมทำงานแต่ละงานจะทำงานทีละงานในคิวแบบวนรอบในช่วงเวลาที่จำกัด อัลกอริทึมนี้ยังช่วยให้การทำงานของกระบวนการต่างๆ ปราศจากปัญหาการรอคอย (starvation) อีกด้วย

ลักษณะของการจัดตารางเวลาแบบ Round-Robin

ต่อไปนี้เป็นคุณลักษณะที่สำคัญของ Round-Robin Scheduling:

• Round robin เป็นอัลกอริทึมแบบตัดหน้า (pre-emptive algorithm)
• ซีพียูจะเปลี่ยนไปยังกระบวนการถัดไปหลังจากช่วงเวลาที่กำหนดไว้ ซึ่งเรียกว่าช่วงเวลาควอนตัม/ช่วงเวลาแบ่งส่วน (time quantum/time slice)
• กระบวนการที่ถูกจองล่วงหน้าจะถูกเพิ่มไปยังจุดสิ้นสุดของคิว
• Round robin เป็นโมเดลแบบผสมผสานที่ทำงานโดยอาศัยสัญญาณนาฬิกา
• ช่วงเวลาที่ใช้ในการประมวลผลควรมีค่าต่ำสุด ซึ่งเป็นค่าที่กำหนดไว้สำหรับงานเฉพาะที่ต้องประมวลผล อย่างไรก็ตาม ค่านี้อาจแตกต่างกันไปในแต่ละระบบปฏิบัติการ
• เป็นอัลกอริทึมแบบเรียลไทม์ที่ตอบสนองต่อเหตุการณ์ภายในระยะเวลาที่กำหนด
• อัลกอริทึมแบบ Round Robin เป็นหนึ่งในอัลกอริทึมที่เก่าแก่ที่สุด ยุติธรรมที่สุด และง่ายที่สุด
• เป็นวิธีการจัดตารางเวลาที่ใช้กันอย่างแพร่หลายในระบบปฏิบัติการแบบดั้งเดิม

ตัวอย่างการจัดกำหนดการแบบ Round-robin

พิจารณาสามกระบวนการต่อไปนี้:

ขั้นตอน 1) การดำเนินการเริ่มต้นด้วยกระบวนการ P1 ซึ่งมีเวลาระเบิด 4 ในที่นี้ ทุกกระบวนการจะดำเนินการเป็นเวลา 2 วินาที P2 และ P3 ยังอยู่ในคิวรอ

ขั้นตอน 2) เมื่อเวลา = 2, P1 จะถูกเพิ่มเข้าไปที่ท้ายคิว และ P2 จะเริ่มทำงาน

ขั้นตอน 3) เมื่อเวลา = 4, P2 ถูกขัดจังหวะและถูกเพิ่มเข้าไปที่ท้ายคิว P3 เริ่มทำงาน

ขั้นตอน 4) เมื่อเวลา = 6, P3 ถูกขัดจังหวะและถูกเพิ่มเข้าไปที่ท้ายคิว P1 เริ่มทำงาน

ขั้นตอน 5) เมื่อเวลา t = 8, P1 มีเวลาประมวลผลสูงสุด 4 หน่วย การประมวลผลเสร็จสิ้นแล้ว P2 เริ่มการประมวลผล

ขั้นตอน 6) P2 มีระยะเวลาการทำงานสูงสุด 3 หน่วย มันได้ทำงานไปแล้ว 2 ช่วงเวลา ที่เวลา = 9 การทำงาน P2 เสร็จสิ้น จากนั้น P3 จะเริ่มทำงานจนกว่าจะเสร็จสิ้น

ขั้นตอน 7) เรามาคำนวณเวลาการรอเฉลี่ยสำหรับตัวอย่างข้างต้นกัน

Wait time
P1 = 0 + 4 = 4
P2 = 2 + 4 = 6
P3 = 4 + 3 = 7

ข้อดีของการจัดตารางงานแบบวนรอบ (Round-robin Scheduling)

ต่อไปนี้คือข้อดี/ประโยชน์ของวิธีการจัดตารางงานแบบหมุนเวียน:

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

ข้อเสียของการจัดตารางเวลาแบบ Round-robin

ต่อไปนี้คือข้อเสียของการใช้การจัดตารางเวลาแบบ Round-robin:

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

เวลาแฝงกรณีที่เลวร้ายที่สุด

คำนี้ใช้กับเวลาสูงสุดที่ใช้ในการปฏิบัติงานทั้งหมด

• dt = หมายถึงเวลาที่ตรวจพบเมื่อมีการเพิ่มงานลงในรายการ
• st = หมายถึงเวลาในการเปลี่ยนจากงานหนึ่งไปอีกงานหนึ่ง
• et = หมายถึงเวลาในการดำเนินการของงาน

สูตร:

Tworst = {(dti+ sti + eti ), + (dti+ sti + eti )2 +...+ (dti+ sti + eti )N., + (dti+ sti + eti  + eti) N} + tISR
tISR = sum of all execution times

คำถามที่พบบ่อย