คุณพอจะมีเวลาว่างสัก 2-3 ชม.ไหม? ให้ Round Robin จัดการให้สิ

สวัสดีครับทุกท่านที่ได้เข้ามาอ่านบทความนี้ คุณคือผู้โชคดีสุดๆเลยครับที่จะได้ Algorithm เจ๋งๆที่จะช่วยให้คุณจัดการเวลางานของคุณในอนาคต เพื่อคำนวณว่าตัวคุณนั้นจะสามารถเคลียงานที่มีอยู่ภายในเวลากี่วัน กี่เดือน กี่ปี หรือกี่ชั่วโมงเพื่อในการรับงานต่อไปหรือวางแพลนในอนาตคว่าจะทำอะไรต่อ โดยจะใช้ Algorithm ของ CPU Scheduling นั้นคือ “Round Robin” นั่นเอง

ROUND ROBIN คืออะไร?

วิธีนี้ถูกออกแบบมาเพื่อใช้กับระบบที่ต้องรองรับรับผู้ใช้จำนวนมากเช่นระบบ time sharing โดยแต่ละ process จะสลับกันเข้าทำงานบน CPU ในระยะเวลาสั้น ๆ เท่า ๆ กันจนกว่างานของแต่ละ process จะเสร็จสมบูรณ์ ซึ่งช่วงเวลาที่กำหนดให้แต่ละ process เข้าทำงานได้จะเรียกว่า time quantum หรือ time slice ซึ่งโดยปรกติจะมีค่าตั้ง 10 ถึง 100 milliseconds ในกรณีที่ burst time ของ process น้อยกว่า time quantum เมื่อ process ทำงานเสร็จสิ้น CPU scheduler ก็จะจัดให้ process ที่อยู่ในลำดับเข้าทำงานต่อทันทีโดยไม่ต้องให้ครบเวลาตาม time quantum ที่ได้กำหนดไว้

คำนิยามของ Round Robin สรุปง่ายๆคือ

“Round-Robin Scheduling สลับให้แต่ละ process ได้ทำงานคนละหนึ่งช่วงเวลา“

โดยที่ตัวแปรที่สำคัญของ Round Robin ที่จะทำให้ Algorithm นี้ทำงานได้มีดังนี้

Burst Time
- เป็นค่าเวลาที่ Process นั้นต้องใช้เวลาทำงานเพื่อเสร็จ
Time Quantum
- เป็นค่าที่เอาไว้กำหนดว่าจะให้ Process แต่ละ Process ทำงานอย่างไร
Arrival Time
- เป็นค่าเวลาที่ Process นั้นเข้ามาในระบบ

Output ของ Round Robin จะมีดังนี้

Turn Around Time
- เป็นค่าเวลาที่ Process นั้นเข้ามาในระบบแล้วทำงาน(Burst Time)จนเสร็จ
Waiting Time
- เป็นค่าเวลาที่ Process นั้นรอในแต่ละครั้งที่จะได้เข้ามาทำงานอีกครั้ง

Example Round Robin

ตัวอย่างข้างล่าแสดงถึง process ที่มาถึงพร้อม ๆ กันในวินาทีที่ 0 และ burst บอกเวลาที่ใช้ในการทำงานบน CPU ตามลำดับ โดยกำหนดให้มี time quantum = 4

ผลการคำนวณสำหรับวิธี round robin จะมีค่าเฉลี่ยของ turnaround time เท่ากับ 12 และค่าเฉลี่ยของ waiting time เท่ากับ 5.66 วิธี round robin เป็นแบบ preemptive เท่านั้น ไม่ว่า process จะมาถึง ready queue พร้อม ๆ กัน หรือ process มาถึงต่างเวลากัน ส่วนตัวอย่างในกรณีที่ process มาถึงไม่พร้อมกัน เราจะแก้โจทย์เดิมโดยเพิ่มเวลาที่มาถึงของแต่ละ process เข้าไปด้วย ซึ่งจะมีการคำนวณดังนี้

ผลการคำนวณสำหรับวิธี round robin แบบที่ process เดินทางมาถึงไม่พร้อมกัน จะมีค่าเฉลี่ยของ turnaround time เท่ากับ 12 และค่าเฉลี่ยของ waiting time เท่ากับ 3.33

————————————————————————————————————————————————————

จบกันไปแล้วนะครับกับการทำงานของ Algorithm Round Robin ในส่วนถัดจากนี้เราจะมาดูถึงวิธีการนำ Algorithm นี้ไปใช้สำหรับการจัดตารางงานที่ได้กล่าวไว้ข้างต้นนะครับ

ในส่วนนี้เราจะนำ Algorithm Round Robin นี้มาเขียนในรูปแบบของภาษา C และ Python โดยหลักการทำงานของทั้งสองแบบจะแตกต่างกันดังนี้

ภาษา C จะสามารถรับค่า Input จากตัวผู้ใช้ได้
ภาษา Python จะสามารถรับค่าจากตัว Excel ได้

การทำงานโปรแกรมของภาษา C

หลักการทำงานของโปรแกรมคือ

ป้อนจำนวน Work ของเราที่ต้องการ
ป้อนจำนวนเวลาของ Work ที่คาดว่าจะเสร็จ (โดยค่าที่ป้อนไปคือค่าของ Burst Time)
ป้อนจำนวนเวลาว่าของแต่ละวันที่ต้องการทำงาน (โดยค่าที่ป้อนเข้าไปคือค่าของ Quantum Time)
โปรแกรมจะทำการ Run แล้วจะแสดงค่าของ Spend All Time ว่าใช้เวลาไปเท่าไรโดยจะแสดงจำนวน ชั่วโมงทั้งหมด และ จำนวนวันที่จะทำงานเสร็จ

Source Code In C

การทำงานโปรแกรมของภาษา Python

หลักการทำงานของโปรแกรมคือ

โปรแกรมจะทำการดึงค่าจาก Excel มาใช้
โปรแกรมจะทำการ Run แล้วจะแสดงค่าของ Spend All Time ว่าใช้เวลาไปเท่าไรโดยจะแสดงจำนวน ชั่วโมงทั้งหมด และ จำนวนวันที่จะทำงานเสร็จ

Source Code In Python

สรุป

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

ประโยชน์ที่ได้จากการทำโครงงาน

สามารถนำ Algorithm ต่างๆที่ได้จาก CPU Scheduling ไม่ว่าจะเป็น Round Robin , FCFS , Priority หรือแม้กระทั่ง Page Replacement นำมาสร้างโปรแกรมที่อาจจะใช้แก้ปัญหาในชีวิตประจำวันของเราก็ได้เนื่องจากมนุษย์ทุกคนล้วนจักต้องทำงานกันเป็นประจำอยู่แล้ว เพราะฉะนั้นแล้ววิชา Data Structure จึงเป็นวิชาที่สำคัญที่ควรค่าแก่การศึกษา

Part1