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