ข้อ 3 หน้า 107 CPU Scheduling-1

ก.ย. 19

Posted by

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

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

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

Image

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

  • 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โดยที่ทุกโปรเซสถูกรับเข้ามาในะบบพร้อมกัน Image Imageจาก Gantt Chart จะเห็นว่า • โปรเซส P1ต้องรอเป็นเวลา 3 หน่วยเวลา • โปรเซส P2ต้องรอเป็นเวลา 16 หน่วยเวลา • โปรเซส P3ต้องรอเป็นเวลา 9 หน่วยเวลา • โปรเซส P4ต้องรอเป็นเวลา 0 หน่วยเวลา • ค่าเฉลี่ยของเวลาที่ใช้ในการรอ คือ (3+16+9+0)/4 = 7 หน่วยเวลา

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

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

  • ให้ตัวเลขที่มีค่าน้อยที่สุด แสดงถึงลำดับความสำคัญน้อยที่สุด
  • ให้ตัวเลขที่มีค่ามากที่สุด แสดงถึงลำดับความสำคัญมากที่สุด หรือ
  • ให้ตัวเลขที่มีค่าน้อยที่สุด แสดงถึงลำดับความสำคัญมากที่สุด
  • ให้ตัวเลขที่มีค่ามากที่สุด แสดงถึงลำดับความสำคัญน้อยที่สุด

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

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

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

Image

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

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

Posted on กันยายน 19, 2012, in Uncategorized. Bookmark the permalink. ใส่ความเห็น.

ใส่ความเห็น