What is the best algorithm? FCFS or RR ?

Processes Scheduling คืออะไร ?

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

CPU Scheduling มีอะไรบ้าง ? 

  1. First Come First Serve  มาก่อนบริการก่อน
  2. Shortest Job First งานเล็กทำก่อน
  3. Shortest Remaining Time First งานเล็กทำก่อนถ้ามาพร้อมกัน
  4. Round Robin ทำงานเป็นรอบๆ วนไปเรื่อยๆ
  5. Priority เรียงลำดับความสำคัญ

โดยในการวิจัยนี้ เปรียบเทียบระหว่าง First Come First Serve กับ Round Robin

First Come First Serve 

คือ Algorithm เรียบงานที่สุด มาก่อนทำก่อน เปรียบเสมือนการนต่อคิวซื้อของ โดยไม่มีงานไหนแทรกเข้าได้ระหว่างการทำงาน แต่ใช้เวลานานมาก เพราะถ้ามีงานที่ใช้เวลานานมาก งานอื่นๆจะรอนาน ทำให้ค่า Waiting Time สูงด้วย

3

Round Robin

คือ Algorithm ที่ไม่เหมือนกับ Algorithm อื่นๆ ซึ่ง จะมีค่าๆหนึ่งที่เรียกว่า Time Quantum คือ เวลาที่ใช้ต่อ 1 Process ซึ่ง งานแต่ละงานที่เข้ามาจะใช้เวลาประมวณเท่ากับ         Time Quantum เมื่อครบเวลาที่กำหนดจะถูกส่งไปคิวสุดท้ายแล้วรับงานต่อไปวนรอบไปเรื่อยๆ จนเสร็จทุกงาน โดย Time Quantum จะมีค่าประมาณ 10 – 100 ms แต่ถ้ามีค่ามากเกินไปจะเหมือนกับเป็น FCFS

6

โดยการวิจัยเราทำการจำรองการทำงานของทั้ง 2 Algorithm ด้วยโปรแกรมจจำลองเผื่อหาค่า Waiting Time ของทั้งคู่ เพื่อเทียบว่าตัวไหนทำงานเร็วที่สุด

หน้าต่างของโปรแกรม

โปรแกรมจำรองนี้สามารถนำข้อมูลจากไฟล์ Excel เข้าโปรแกรมได้ดังนี้

Import File Excel 

การ Import File Excel เข้ามาในโปรแกรมเพื่อจำรองกรณีมีงานเข้ามาตามลำดับเป็นจำนวนมาก และ ง่ายต่อการใช้งาน

เมื่อดึงข้อมูลลเข้าโปรแกรมมาแล้วจะแสดงงานทั้งหมดและเวลาที่ใช้ และ เวลาที่งานเข้า จากนั้นเราสามารถเลือกได้ว่าอยากจะให้งานทั้งหมดนี้ผ่านการจัดการด้วย FCFS หรือ RR

First Come First Serve Scheduling

ในหน้าต่างช่องแรก แสดงถึง การทำงานของ FCFS โดยทำงานแรกจนเสร็จแล้วไปงานอื่นเมื่อจัดการด้วย FCFS จนเสร็จทั้งหมด โปรแกรมจะประมวณค่าเฉลี่ยของเวลาที่รอ             ( Average Waiting Time ) และเวลาที่รอจนทำเสร็จ ( Turn Around Time ) ได้ค่าดังรูป

Round Robin Scheduling 

ในหน้าต่างช่องแรก แสดงถึงการทำงาน RR โดยทำงานเป็นรอบๆ ซึ่งก่อนกด Round Robin ต้องป้อนค่า Time Quantum ก่อนถึงจะทำการประมวณได้ ถ้ากำหนด 4 ทุกๆงานจะทำแค่ 4 แล้วหยุดไปทำงานอื่นต่อ

Flow Chart

First Come First Serve

Round Robin

Algorithm ของ FCFS

Algorithm ของ RR

วิธีนำไฟล์ Excel เข้าโปรแกรม

ในภาษา VB.net นั้น การแยกเป็น Subclass จะแยกเป็น เหตุการณ์ เช่นดังรูป จะเป็น เหตุการณ์ที่เราคลิกที่ปลุ่ม Button1_Click หมายถึง เมื่อคุณคลิก Button1 จะให้เกิดเหตุการณ์ ตามที่เขียนโคด้ ลงไป โดยในการท างานของโค้ดฟังชั่นนี้ ส่วนมากจะพบปัญหา Excel กับ VB.net ไม่สามารถ Reference หากันได้ จ าเป็นต้องติดตั้งโปรแกรมเสริม เพื่อสามารถลองรับได้ ตรงนี้ เพียงติดตั้งครั้งเดียว ก็สามารถใช้งาน Vb.exe ได้ทุกที่ไม่จ าเป็นต้องติดตั้งใหม่

What is Best Algorithm ? FCFS or RR ?

เมื่อเราทำงานประมวณผลทั้ง 2 Algorithm แล้ว Avg Waiting Time ของ FCFS น้อยกว่า RR และ Avg Turn Around time ของ FCFS น้อยกว่า RR เหมือนกัน เหตุผลที่ RR ช้ากว่า FCFS เพราะเสียเวลาในการสับงานไปๆมาๆทุกครั้ง

สรุป

FCFS เป็นอัลกอริทึมเลยง่ายต่อการใช้งาน และ ยุติธรรมที่สุด ใครมาก่อนทำงานก่อน

RR เป็นอัลกอริทึมที่ถูกพัฒนาเพื่อให้การทำงานที่รวดเร็วและรองานต่องานเร็ว

แต่ในความเป็นจริง การที่เราจะเลือกใช้อัลกอริทึมในการทำต่างๆ ขึ้นอยู่กับว่า ชิ้นงานนั้นๆเหมาะกับอัลกอริทึมนั้นๆจริงๆ อย่างเช่น การแสดงผลหน้าจอหรือรูปภาพ ถ้าเรานำชิ้นงานถูกทำด้วย RR จะดูเหมือนว่ารูปภาพจะแสดงผลได้เร็ว แต่จะค่อยๆชัดเจนขึ้น แต่ถ้านำไปใช้ใน FCFS เม็ดสีจะแสดงชัดครั้งแรกและไล่ทำเม็ดสีต่อไปเรื่อยๆ

งานไหนที่ Round Robin ดีกว่า FCFS

นำ Round Robin ไปใช้ใน Website จะมีประสิทธิภาพดีกว่า FCFS เพราะ การเปิด Website หลายๆหน้าพร้อมกันและมีข้อมูลปริมาณมาก การที่ใช้ Round Robin จะทำให้การแสดงผลของข้อมูลรวดเร็วกว่าใช้ FCFS

YouTube Preview Image
  •  
  •  
  •  
  •  
  •  
  •  
PHISEK WONGTEERAROJ
at GlurGeek.Com

Leave a Reply