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

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

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

• Round robin เป็นอัลกอริทึมแบบรับล่วงหน้า
• CPU จะถูกเปลี่ยนไปยังกระบวนการถัดไปหลังจากช่วงเวลาที่กำหนดไว้ ซึ่งเรียกว่าควอนตัมเวลา/สไลซ์เวลา
• กระบวนการที่ถูกจองล่วงหน้าจะถูกเพิ่มไปยังจุดสิ้นสุดของคิว
• Round robin เป็นรุ่นไฮบริดซึ่งขับเคลื่อนด้วยนาฬิกา
• การแบ่งเวลาควรเป็นขั้นต่ำ ซึ่งกำหนดให้กับงานเฉพาะที่ต้องดำเนินการ อย่างไรก็ตาม OS อาจแตกต่างกันไป
• เป็นอัลกอริธึมแบบเรียลไทม์ที่ตอบสนองต่อเหตุการณ์ภายในระยะเวลาที่กำหนด
• Round Robin เป็นหนึ่งในอัลกอริธึมที่เก่าแก่ที่สุด ยุติธรรมที่สุด และง่ายที่สุด
• วิธีการตั้งเวลาที่ใช้กันอย่างแพร่หลายในระบบปฏิบัติการแบบดั้งเดิม

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

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

คิวกระบวนการ	ระเบิดเวลา
P1	4
P2	3
P3	5

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

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

ขั้นตอน 3) ณ เวลา=4 P2 จะถูกจองล่วงหน้าและเพิ่มเมื่อสิ้นสุดคิว P3 เริ่มดำเนินการ

ขั้นตอน 4) ณ เวลา=6 P3 จะถูกจองล่วงหน้าและเพิ่มเมื่อสิ้นสุดคิว P1 เริ่มดำเนินการ

ขั้นตอน 5) ณ เวลา=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

นี่คือข้อดี/ประโยชน์ของวิธีการจัดกำหนดการแบบ Round-robin:

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

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

นี่คือข้อเสีย/ข้อเสียของการใช้การกำหนดเวลาแบบ Round-robin:

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

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

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

• dt = ระบุเวลาในการตรวจจับเมื่อมีการนำงานเข้าสู่รายการ
• st = แสดงถึงการสลับเวลาจากงานหนึ่งไปอีกงานหนึ่ง
• et = ระบุเวลาดำเนินการงาน

สูตร:

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

สรุป

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