บทที่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₄

P₁

P₃

P₂

· การรอคอยของกระบวนการ P₁ = 3, P₂ = 16, P₃ = 19, P₄ = 0

· เวลารอคอยโดยเฉลี่ย (3 + 16 + 9 + 0) / 4 = 7

การจัดตารางการทำงานแบบศักดิ์สูงได้ก่อน (Priority Scheduling)

กระบวนการที่จะได้เข้าใช้หน่วยประมวลผลกลาง คือ กระบวนการที่มีศักดิ์สูงที่สุด ถ้ากระบวนการใดมีศักดิ์เท่ากันแล้วระบบจะให้กระบวนการที่มีศักดิ์เท่ากันนั้นทำงานแบบมาก่อนได้ก่อน

กระบวนการ (Process) เวลาทำงาน (Burst Time) ศักดิ์ (Priority)

P₁ 10 3

P₂ 1 8

P₃ 2 7

P₄ 1 3

P₅ 5 2

P₂

P₅

P₁

P₃

P₄

· เวลารอคอยโดยเฉลี่ย (6 + 0 + 16 + 18 + 1) / 5 = 8.2

การจัดตารางการทำงานแบบเวียนเทียน (Round Robin Scheduling / RR)

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

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

P₁ 24

P₂ 3

P₃ 3

P₁

P₂

P₃

P₁

การจัดตารางการทำงานแบบแถวคอยหลายระดับ (Multilevel Queue Scheduling)

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

ในระบบมีแถวพร้อมอยู่ 5 แถว ดังนี้

งานของระบบ
งานแบบโต้ตอบ
งานแก้ไขข้อมูล
งานแบบกลุ่ม
งานของนักศึกษา

แสดงการจัดตารางแบบแถวคอยหลายระดับ

การจัดตารางการทำงานแบบจัดลำดับหลายระดับแบบเลื่อนชั้นได้ (Multilevel Feedback Queue Scheduling)

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

แสดงการจัดลำดับหลายระดับแบบเลื่อนชั้นได้

การทำงานโดยวิธีการจัดตารางการทำงานแบบจัดลำดับหลายระดับแบบเลื่อนชั้นได้นี้ ถูกกำหนดโดยพารามิเตอร์ดังนี้

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

การจัดตารางการทำงานสำหรับหลายหน่วยประมวลผล (Multiple Processor Scheduling)

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

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

การจัดแถวคอยร่วมนี้ อาจแบ่งได้เป็น 2 วิธี

ให้หน่วยประมวลผลแต่ละตัวจัดตารางการทำงานเอง
กำหนดให้หน่วยประมวลผลหนึ่งมีหน้าที่จัดตารางการทำงานโดยเฉพาะ

การจัดตารางการทำงานแบบตอบสนองฉับพลัน (Real Time Scheduling)

การจัดตารางการทำงานแบบตอบสนองฉับพลันนี้แบ่งเป็น 2 ประเภท คือ

Hard Real time System ต้องการเวลาที่คงที่แน่นอน ตายตัว
Soft Real time System เป็นระบบที่ทำงานโดยไม่ต้องมีเวลามาจำกัด

การประเมินอัลกอริทึม (Algorithm Evaluation)

วิธีการจัดตารางมีหลายวิธี แต่ละวิธีมีตัวแปรและลักษณะเฉพาะ ทำให้การเลือกวิธีที่เหมาะสมหรือดีที่สุดทำได้ยาก

ขั้นแรกจำเป็นต้องกำหนดคุณสมบัติก่อนว่า ต้องการคุณลักษณะใด มีค่าเท่าใด เช่น

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

edit @ 18 Aug 2008 07:38:07 by

11 Comments