วันพุธที่ 19 กันยายน พ.ศ. 2555

ข้อ3 หน้า107

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

1.มาก่อนบริการก่อน(FCFS : First-come First-served Scheduling)


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

ปัญหาที่อาจะเกิดขึ้น
Convoy effect : การทำงานของอัลกอริทึมนี้ดูเหมือนเป็นการยุติธรรมที่ให้สิทธิการเข้าใช้ซีพียู แก่โปรเซสที่เข้ามาอยู่ในคิวพร้อมก่อน แต่ในกรณีที่ในคิวพร้อมของระบบมีทั้งโปรเซสที่เน้นซีพียู และโปรเซสที่เน้น I/O จะพบว่า โปรเซสที่เน้น I/O จะต้องเสียเวลารอนานมาก เพื่อเข้าใช้งานซีพียูในระยะเวลาที่ไม่นานมากนัก ซึ่งจะทำให้เกิดปัญหา Convoy effect คือ เหตุการณ์ที่โปรเซสขนาดเล็กในระบบ จะต้องเสียเวลารอโปรเซสขนาดใหญ่ที่ครอบครองซีพียูเป็นเวลานานการทำงานของอัลกอริทึมนี้ เป็นการทำงานที่ไม่สามารถขัดจังหวะ หรือแทรกกลางคันได้ (Non-Preemptive process)  ซึ่งจะไม่เหมาะกับระบบที่ต้องมี

การแบ่งส่วนการทำงาน ให้งานแต่ละงานได้ใช้ซีพียูอย่างทั่วถึง

ตัวอย่าง ให้พิจารณาระบบที่ประกอบไปด้วย 3 โปรเซสที่ถูกรับเข้ามาในระบบ เรียงตามลำดับ คือ P1, P2 และ P3 โดยที่แต่ละโปรเซสต้องการใช้ซีพียูเป็นเวลาตามที่กำหนด ให้หาค่าเฉลี่ยของเวลารอ เมื่อกำหนดให้ใช้อัลกอริทึมแบบมาก่อนบริการก่อน


การรอของแต่ละโปรเซส สามารถแสดงได้ด้วย Gantt Chart ดังนี้

• P1เข้ามาในระบบและได้รับการจัดสรรให้ใช้ซีพียูทันที จึงไม่ต้องเสียเวลาในการรอซีพียู ดังนั้นเวลาในการรอซีพียู = 0 หน่วยเวลา 
• P2ต้องรอจนกว่า P1ทำงานเสร็จเรียบร้อยและคืนซีพียูให้กับระบบ ดังนั้นเวลาในการรอซีพียู = 24 หน่วยเวลา
• P3ต้องรอจนกว่า P2ทำงานเสร็จเรียบร้อยและคืนซีพียูให้กับระบบ ดังนั้นเวลาในการรอซีพียู = 27 หน่วยเวลา
• ดังนั้นค่าเฉลี่ยของเวลาที่ใช้ในการรอซีพียู คือ (0+24+27)/3 = 17 หน่วยเวลา

2.งานสั้นทำก่อน (Shortest-Job First Scheduling : SJF)

อัลกอริทึมของงานสั้นทำก่อน จะพยายามลดค่าเฉลี่ยของเวลาครบวงงาน และค่าเฉลี่ยของเวลารอ โดยกำหนดให้โปรเซสที่ต้องการใช้ซีพียูเป็นระยะเวลาน้อยได้เข้าใช้ซีพียูก่อนโปรเซสที่ต้องการใช้ซีพียูเป็นระยะเวลานาน

ปัญหาที่อาจเกิดขึ้น
ข้อมูลในด้านเวลาที่จะต้องใช้ทำงานของแต่ละกระบวนการ สำหรับการจัดตารางการทำงานในระยะยาว ในระบบการทำงานแบบกลุ่ม เราสามารถใช้ข้อจำกัดเวลาที่ผู้ใช้บอกเป็นเกณฑ์ได้ ซึ่งผู้ใช้ก็จะถูกบังคับโดยอัตโนมัติ ให้ประมาณการข้อจำกัดเวลานี้ อย่างใกล้เคียงที่สุด เพราะยิ่งสั้นยิ่งมีโอกาสเข้าทำงานก่อน (แต่ถ้าสั้นเกินไป ระบบจะแจ้งข้อผิดพลาด ใช้เวลาเกินข้อจำกัดซึ่งผู้ใช้ต้องวนกลับไปเริ่มส่งงานมาใหม่) โดยปกติแล้วจึงนิยมใช้ SJF ในการจัดตารางการทำงานในระยะยาว
แม้ว่า SJF จะดีที่สุด แต่ก็ไม่สามารถนำไปใช้กับการจัดตารางการทำงานในระยะสั้น เพราะเราไม่มีทางรู้เวลาที่แต่ละกระบวนการ จะต้องทำงานจริง ๆ ทางออกก็คือ พยายามประมาณวิธี SJF โดยการพยากรณ์ค่าว่าเวลาที่กระบวนการจะต้องทำงานจากค่าในอดีต แล้วจัดตารางการทำงาน ด้วยค่าพยากรณ์นี้แทน
วิธี SJF นี้อาจทำเป็นแบบให้แทรกกลางคัน (preemptive) หรือ ห้ามแทรกกลางคัน (nonpreemptive) ก็ได้ เมื่อกระบวนการใหม่เข้ามาในแถวคอย ขณะที่กระบวนการหนึ่งกำลังทำงานอยู่ ถ้ากระบวนการใหม่มีเวลาที่จะต้องทำงานสั้นกว่า เวลาที่เหลือ ของกระบวนการที่กำลังทำงาน 

ตัวอย่าง พิจารณาระบบที่ประกอบด้วยโปรเซส P1, P2, P3 และ P4โดยที่ทุกโปรเซสถูกรับเข้ามาในะบบพร้อมกัน




จาก Gantt Chart จะเห็นว่า
• โปรเซส P1ต้องรอเป็นเวลา 3 หน่วยเวลา 
• โปรเซส P2ต้องรอเป็นเวลา 16 หน่วยเวลา
• โปรเซส P3ต้องรอเป็นเวลา 9 หน่วยเวลา
• โปรเซส P4ต้องรอเป็นเวลา 0 หน่วยเวลา
• ค่าเฉลี่ยของเวลาที่ใช้ในการรอ คือ (3+16+9+0)/4 = 7 หน่วยเวลา

3.ลำดับความสำคัญ (Priority Scheduling)

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

ปัญหาที่อาจเกิดขึ้น
กรณีที่อัลกอริทึมทำงานแบบ Preemptive จะทำให้เกิดปัญหาสำคัญ คือ การอดตาย (Starvation) คือ โปรเซสที่มีลำดับความสำคัญต่ำกว่า ถูกโปรเซสที่มีลำดับความสำคัญสูงกว่าแย่งซีพียูไปใช้งาน ทำให้โปรเซสที่มีลำดับความสำคัญต่ำไม่มีโอกาสเข้าไปใช้ซีพียู 

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


ตัวอย่าง 

เมื่อกำหนดให้ ตัวเลขที่มีค่าน้อยที่สุดมีลำดับความสำคัญสูงที่สุด การจัดลำดับ
ของซีพียูจะเป็นไปตามลำดับค่าความสำคัญ คือ P
2
, P
5
, P
1
, P
3
, P
4

การจัดลำดับของซีพียูจะเป็นไปตามลำดับค่าความสำคัญ คือ P2, P5, P1, P3, P4

ดังนั้น ค่าเฉลี่ยของเวลาที่ใช้ในการรอ คือ (13+0+19+26+8)/5  เท่ากับ 13.2 หน่วยเวลา




4.วิธีวนรอบ (Round-Robin Scheduling : RR)

อัลกอริทึมนี้ถูกออกแบบมาเพื่อใช้ส าหรับระบบแบ่งเวลา โดยมีการทำงานเหมือนอัลกอริทึมแบบมาก่อนบริการก่อน แต่กำหนดให้โปรเซสใช้ซีพียูในเวลาที่จำกัด เรียกว่า เวลาควอนตัม (Quantum time)  หรือ การแบ่งเวลา 

ตัวอย่าง ระบบคอมพิวเตอร์มีโปรเซสทั้งหมด 3 โปรเซส แต่ละโปรเซสมีเวลาเข้าระบบ และเวลาที่ต้องการใช้ซีพียู ดังนี้
โปรเซส P1 เข้าระบบเมื่อเวลา 0.0 และต้องการใช้ซีพียู 8 หน่วยเวลา
โปรเซส P2 เข้าระบบเมื่อเวลา 0.4 และต้องการใช้ซีพียู 4 หน่วยเวลา
โปรเซส P3 เข้าระบบเมื่อเวลา 1.0 และต้องการใช้ซีพียู 1 หน่วยเวลา
เมื่อกำหนดให้ใช้การจัดลำดับใช้งานซีพียูแบบวนรอบ ที่มีเวลาควอนตัมเท่ากับ 2.0 หน่วยเวลา ให้แสดงวิธีทำเพื่อคำนวณหาเวลาครบวงงานเฉลี่ย



Thank you

ไม่มีความคิดเห็น:

แสดงความคิดเห็น