การจัดตารางงาน

การจัดตารางงาน

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

ทำไมเราต้องจัดตารางงาน?

- เพื่อไม่ให้ซีพียูว่าง

- เพื่อให้โพรเซสได้มีโอกาสใช้ซีพียูอย่างสม่ำเสมอ

- เพื่อให้เกิดความสมดุล

ประเภทของตารางงาน

เราสามารถแบ่งตารางงานเป็น 3 ประเภทดังนี้

ตารางงานระยะสั้น (Short term scheduler) มีการสลับงานบ่อย ใช้กับช่วงเวลาที่มีโพรเซสงานหนาแน่น
ตารางงานระยะกลาง (Medium term xcheduer) มีการสลับงานปานกลาง ใช้กับช่วงเวลาที่มีโพรเซสงานปานกลาง
ตารางงานระยะยาว (Long term scheduler) มีการสลับงานน้อย ใช้กับช่วงเวลาที่มีโพรเซสงานน้อย

นอกจากการแบ่งตารางงานตามความถี่ในการสลับงาน เรายังสามารถแบ่งตารางงานตามกฏเกณฑ์ในการทำงานได้ 2 ประเภทดังนี้
- ตารางงานทีไม่อนุญาตให้แทรกงาน(Non-preemptive scheduling)
- ตารางงานที่อนุญาติให้แทรกงานได้ (Preemptive scheduling)
ธรรมชาติของโพรเซส

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

• โพรเซสจะประกอบด้วยการใช้งานซีพียู และการรอข้อมูลจากอุปกรณ์ต่อพ่วง
• ช่วงที่โพรเซสใช้งานซีพียู เราเรียกช่วงนั้นว่า CPU burst times
• ช่วงที่โพรเซสรอข้อมูลจากอุปกรณ์ต่อพ่วง เราเรียกช่วงนั้นว่า l/O burst times
• โพรเซสจะมีการสลับไปมาระหว่าง CPU burst และ l/O burst ตลอด
• โพรเซสแต่ละโพรเซสจะใช้ CPU burst ต่างกันขึ้นกับตัวเองของโพรเซสนั้น และการจัดตารางงานของระบบ
• โดยปกติทุกๆ โพรเซสจะมีการใช้ CPU burst ถี่ในช่วงแรก และช่วงหลังจะใช้ CPU burst เพียงเล็กน้อย

หลักการจัดตารางงาน (Scheduling Criteria)

ในการจัดตารางงานมีเกณฑ์วัดประสิทธิภาพระบบ ดังนี้

CPU utilization คือ การทำงานของซีพียู

Throughput คือ จำนวนงานเสร็จใน 1 หน่วยเวลา

Turnaround time คือ เวลาที่สูญเสียไปในการทำงาน

Waiting time คือ เวลาที่ใช้รอคิวในสถานะ ready

Response time คือ เวลาที่ใช้รอการตอบรับ

Fairness คือ การแบ่งซีพียูให้กับทุกงานอย่างเหมาะสม เท่าเทียมกัน

วิธีการจัดตารางงาน (Scheduling Algorithms)

ในการจัดตารางงานให้กับโพรเซสเราจะมีวิธีและหลักการจัดหลายๆ แบบ ดังนี้

First-Come, First-Served (FCFS) Scheduling เป็นการจัดตารางงานแบบง่ายที่สุด ยุติธรรมสูง เพราะเรียงลำดับตามคิว ใครมาก่อนก็ได้ก่อน

Shortest-Job-First (SJF) Scheduling SJF จะมีทั้งแบบ Non-preemptive และ Preemptive ซึ่งจะมีความต่างกันดังนี้

Non-preemptive(ไม่มีการแทรกงาน)

Preemptive (มีการแทรกงาน)

Priority Scheduling

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

Round-Robin Scheduling

หรือเราใช้ตัวย่อว่า RR การจัดตารางงานในลักษณะนี้ถูกออกแบบมาเพื่อใช้กับระบบจัดแบ่งเวลา ซึ่งระบบดังกล่าวจะแบ่งช่วงเวลาให้แต่ละงานใช้ซีพียูครั้งละ 10-100 มิลลิวินาที

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

Multi-level Queue Scheduling

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

Multiple-Processor Scheduling

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

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

สรุปประเด็นในการจัดตารางงาน

• การจัดตารางงานให้ซีพียู คือกระบวนการคัดเลือกงานที่ต่อแถวรอคิวอยู่ขึ้นมาทำงานตามข้อกำหนดที่ตั้งไว้
• FCFS เป็นตารางงานแบบง่ายที่สุด แต่ไม่ดีถ้างานเล็กไปอยู่ข้างหลังงานใหญ่
• SJF เป็นตารางงานที่มีค่าเฉลี่ย waiting time ต่ำสุด
• Priority scheduling คือ SJF แบบพิเศษที่มีการกำหนดลำดับความสำคัญให้กับงาน
• ทั้ง SJF และ Priority มีปัญหาเดียวกันคือ การแช่งานความสำคัญต่ำค้างอยู่ในคิว ไม่สามารถทำงานนั้นเสร็จได้
• RR เป็นการกำหนดตารางเวลาแบบแบ่งช่วงเวลาเข้าใช้ซีพียูจะไม่อนุญาตให้งานใดๆ ใช้ซีพียูเกินเวลาที่กำหนด
• ปัญหาหลักของ RR คือการกำหนดเวลาเข้าใช้ซีพียู ถ้ากำหนดกว้างเกินไประบบจะกลายเป็น FCFS แต่ถ้าไม่แคบเกินไป งานก็จะต้องทำหลายรอบจนเสร็จ
• FCFS มีแต่แบบ Non-preemptive ไม่มีการแทรกงาน
• RR มีแต่แบบ Preemptive คือแทรกงานได้
• SJF และ Priority เป็นได้ทั้งแบบ Non-preemptive และ Preemptive
• Multi-level queue algorithm คือการแยกคิวเป็นหลายๆ คิว แต่ละคิวมีลำดับความสำคัญไม่เท่ากัน
• Multi-level feedback queues คือ คิวที่อนุญาตให้งานสามารถเปลี่ยนคิวไปอยู่คิวอื่นได้