บทที่5 CPU Scheduling

posted on 18 Aug 2008 05:08 by 490702464037

แนวความคิดพื้นฐาน (Basic Concept)

                แนวคิดของ Multiprogramming ที่สัมพันธ์กันอย่างง่าย คือ กระบวนการจะทำงานจนกระทั่งถึงเวลาต้องรอ ระบบปฏิบัติการจะเอาหน่วยประมวลผลกลางออกมาจากกระบวนการนั้น และให้หน่วยประมวลผลกลางแก่กระบวนการอีกกระบวนการหนึ่งแทน

แสดงการสลับลำดับของช่วงประมวลผลและช่วงรับส่งข้อมูล

ถึงแม้ว่าช่วงเวลาประมวลผลของแต่ละกระบวนการจะมีค่าแตกต่างกัน แต่โดยส่วนใหญ่จะให้ผลคล้ายกราฟในรูป ดังนี้

แสดงฮิสโตรแกรมของช่วงเวลาประมวลผล

ตัวจัดตารางการทำงานของหน่วยประมวลผลกลาง (CPU Scheduler)

                เมื่อหน่วยประมวลผลกลางว่างง ระบบก็จะเลือกกระบวนการจากแถวพร้อม เพื่อให้ทำงานในหน่วยประมวลผลกลางต่อไป โดยใช้ตัวจัดตารางระยะสั้น หรือตัวจัดตารางการทำงานของหน่วยประมวลผล

                ในการจัดตารางหน่วยประมวลผลกลาง ระบบจะต้องตัดสินใจหรือเลือกเมื่อมีเหตุการณ์หนึ่งเกิดขึ้น คือ

1.       เมื่อกระบวนการเปลี่ยนสถานะจาก กำลังทำงาน ไปเป็น กำลังรอคอย

2.       เมื่อกระบวนการเปลี่ยนสถานะจาก กำลังทำงาน ไปเป็น สถานะพร้อม

3.       เมื่อกระบวนการเปลี่ยนสถานะจาก กำลังรอคอย ไปเป็น สถานะพร้อม

4.       เมื่อกระบวนการสิ้นสุด

ตัวส่งต่อ (Dispatcher)

                เป็นโปรแกรมที่ย้ายการควบคุมไปยังกระบวนการใหม่ โดยมีขั้นตอนดังนี้

1.       เปลี่ยนงาน

2.       เปลี่ยนไปเป็นช่วงผู้ใช้

3.       ย้ายการควบคุมไปที่บรรทัดคำสั่งในโปรแกรมผู้ใช้ เพื่อรีสตาร์ทโปรแกรมนั้น

เกณฑ์ในการจัดตาราง (Scheduling Criteria)

วิธีการจัดตารางการทำงานของหน่วยประมวลผลกลางที่แตกต่างกัน ซึ่งเราจะเลือกใช้วิธีการต่างๆให้เหมาะสมกับแต่ละสถานการณ์ มีดังนี้

·         ประสิทธิผลการใช้หน่วยประมวลผลกลาง

·         อัตราปริมาณงาน

·         วงรอบการทำงาน

·         เวลารอคอย

·         เวลาตอบสนอง

การจัดตารางการทำงานแบบมาก่อน – ได้ก่อน (First Come Served Scheduling/ FCFS)

                กระบวนการใดได้ร้องขอหน่วยประมวลผลกลางก่อน ก็จะได้รับหน่วยประมวลผลกลางตามที่ร้องขอ โดยขั้นตอนวิธีในการทำงานดังนี้

                     กระบวนการ (Process)                                             เวลาทำงาน (Burst Time)

P                                                                                                           24

P                                                                                                           3

P                                                                                                           3

P

P

P

·         การรอคอยของกระบวนการ  P = 24, P = 3, P = 3

·         เวลารอคอยโดยเฉลี่ย (0 + 24 + 27) / 3 = 17

การจัดตารางการทำงานแบบงานสั้นที่สุดได้ก่อน (Short Job First Scheduling / SJF)

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

                                 กระบวนการ (Process)                        เวลาทำงาน (Burst Time)

P                                                                     6

P                                                                     8

P                                                                     7

P₄                                                                                      3

P₄