การจัดเวลาซีพียู (CPU Scheduling)

ปรับปรุง : 2560-01-26 (เพิ่ม ถาม ตอบ)

สารบัญ :: #1 :: #2 :: #3 :: #4 :: #5 :: #6 :: #7 :: #8 :: #9 :: #10 :: #11 :: #12 :: Linux ::

การจัดการเวลาซีพียู

สาระการเรียนรู้
1. Scheduling Criteria
2. Scheduling Algorithms
3. Algorithm Evaluation

จุดประสงค์การสอน
1. เข้าใจหลักการของ Scheduling Criteria
2. สามารถอธิบายลักษณะของ Scheduling Algorithms แต่ละแบบได้
3. เข้าใจ Algorithm Evaluation
4. สามารถแสดงการทำงานของ Algorithms แต่ละแบบได้

แนะนำบทเรียน
หน่วยประมวลผลกลาง (CPU=Central Processing Unit) เป็นอุปกรณ์ที่มีความเร็วสูงที่สุด สามารถทำงานได้นับล้านคำสั่งในหนึ่งวินาที แต่อุปกรณ์ที่เชื่อมต่อไม่ได้เร็วเช่นนั้น และโปรเซสก็อาจไม่ได้ทำงานเสร็จในเวลาที่รวดเร็ว ดังนั้นโปรเซสทั้งหมดต้องถูกจัดตาราง (Scheduling) เพื่อเข้าไปอยู่ในหน่วยประมวลผลกลางช่วงเวลาหนึ่ง แล้วออกไปตามเงื่อนไข เช่น ทำงานเสร็จ อยู่นานเกินไป หรือออกไปทำงานที่คั่งค้าง เมื่อพร้อมก็ค่อยเข้าคิวต่อแถว เข้าใช้หน่วยประมวลผลกลางต่อไป

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

6.1 Scheduling Criteria 6.1.1 การใช้ประโยชน์หน่วยประมวลผลกลาง (CPU utilization)
6.1.2 ประมาณงาน (Throughput)
6.1.3 เวลาโดยรวม (Turnaround time)
6.1.4 เวลาคอย (Waiting time)
6.1.5 เวลาตอบสนอง (Response time)

6.2 Scheduling Algorithms หน้าที่ของตัวจัดคิวคือ คัดเลือกโปรเซสซึ่งรออยู่ในสถานะพร้อมที่เหมาะสมที่สุดให้เข้าไปอยู่ในสถานะรัน (ได้ครอบครองซีพียู) โดยแท้จริงแล้วการส่งโปรเซสที่ถูกเลือกแล้วให้เข้าไปอยู่ในสถานะรัน เป็นหน้าที่ของโปรเซสของ OS ที่ชื่อตัวส่ง (dispatcher) ในแง่การทำงานแล้วตัวจัดคิวจะเป็นผู้คัดเลือกโปรเซสและเรียกให้ตัวส่งส่งโปรเซสที่ถูกเลือกแล้วเข้าไปในสถานะรันเป็นความรับผิดชอบของตัวจัดคิว
6.2.1 การจัดเวลาแบบมาก่อนได้ก่อน (FCFS : First-come First-served Scheduling)
การจัดคิวแบบ FCFS (first-come-first-served) วิธีการคัดเลือกแบบ FCFS นี้เป็นวิธีที่ง่ายที่สุด คือ โปรเซสไหนเข้ามารอในคิวก่อนจะได้ครอบครองซีพียูก่อน ตามลำดับเวลาของการเข้ามาอยู่ในคิว คือ "มาก่อนได้ก่อน" โปรเซสที่ได้ครอบครองซีพียูจะทำงานไปจนเสร็จ ไม่มีระยะเวลาควอนตัมซึ่งจำกัดเวลาการครอบครองซีพียู แต่ถ้าโปรเซสมีการเรียกใช้งานอุปกรณ์อินพุต-เอาต์พุต หรือรอเหตุการณ์บางอย่าง โปรเซสนั้นต้องปลดปล่อยซีพียู และออกจากสถานะรันไปอยู่ในสถานะติดขัด เมื่อใดที่งานเสร็จสิ้นลงหรือเกิดเหตุการณ์ที่กำลังรออยู่ โปรเซสนั้นจึงค่อยกลับเข้าไปอยู่ต่อท้ายคิวของสถานะพร้อมใหม่อีกครั้ง
เราอาจแสดงการเปลี่ยนสถานะของโปรเซสโดยใช้การจัดคิวแบบ FCFS ซึ่งจะเห็นว่าแตกต่างกับรูปแสดงการเปลี่ยนสถานะของโปรเซสที่เคยกล่าวมาคือ ไม่มีการเปลี่ยนสถานะของโปรเซสจากสถานะรันมายังสถานะพร้อมโดยตรง
First Come First Served (FCFS): The simplest scheduling algorithm is FCFS. As each process becomes ready, it joins the ready queue. When the currently running process ceases to execute, the oldest process in the ready queue is selected for running.

6.2.2 การจัดเวลาแบบงานสั้นทำก่อน (SJF : Short-Job-First Scheduling)
การจัดคิวแบบ SJN (shortest job next) การคัดเลือกโปรเซสด้วยวิธีนี้ จะคัดเลือกเอาโปรเซสที่ต้องการเวลาในการทำงานน้อยที่สุด ทำให้โปรเซสที่ต้องการเวลาในการทำงานน้อยจบออกไปได้เร็วขึ้น จำนวนโปรเซสในระบบที่รออยู่ในคิวมีก็จะมีจำนวนลดลง และทำให้เวลาโดยเฉลี่ยในการทำงาน 1 งานเสร็จหรือเวลาครบงาน (turnaround time) น้อยลงแต่การจัดคิวแบบนี้เป็นผลเสียต่อโปรเซสที่ต้องการเวลาในการทำงานนาน
Shortest Process Next (SPN): Another approach to reducing the bias in favor of long processed inherent in FCFS is the SPN. This is a non-preemptive algorithm in which the process with the shortest expected processing time is selected next. Thus a short process will jump to the head of the queue past longer jobs.
Shortest Remaining Time (SRT): SRT algorithm is a preemptive version of SPN. In this case, the scheduler always chooses the process that has the shortest expected remaining processing time. When a new process joins the ready queue, it may in fact have a shorter remaining time than the currently running process. SRT does not have the bias in favor of long processes found in FCFS.

6.2.3 การจัดเวลาตามลำดับความสำคัญ (Priority Scheduling)
การจัดคิวแบบลำดับความสำคัญ (priority queue) คิวแบบลำดับความสำคัญมีลักษณะแตกต่างกับคิวธรรมดา ภายในคิวจะมีการจัดเรียงลำดับของโปรเซสต่าง ๆ ตามลำดับความสำคัญของโปรเซสนั้น โปรเซสที่อยู่ต้นคิวจะมีลำดับความสำคัญมากที่สุด และลดลงเรื่อย ๆ โปรเซสที่อยู่ท้ายคิวคือโปรเซสที่มีลำดับความสำคัญต่ำสุด การคัดเลือกโปรเซสจะเอาโปรเซสที่อยู่ต้นคิว (มีลำดับความสำคัญสูงสุด) เข้าไปครอบครองซีพียูก่อน ดังนั้นถึงแม้ว่าโปรเซสที่เข้าคิวทีหลังแต่มีลำดับความสำคัญสูงกว่าก็อาจได้เข้าไปครอบครองซีพียูก่อน โปรเซส E เข้าคิวเป็นโปรเซสหลังสุด แต่จะได้ครอบครองซีพียูก่อนโปรเซส C และ D

6.2.4 การจัดเวลาแบบวนรอบ (RR : Round-Robin Scheduling)
การจัดคิวแบบ RR (round-robin) การจัดคิวแบบ RR อาจเรียกว่าเป็นการจัดคิวแบบมีการวนรอบ ลักษณะการคัดเลือก โปรเซสในคิวจะเป็นแบบ FCFS คือ "มาก่อนได้ก่อน" แต่ต่างกันนิดหน่อยตรงที่การครอบครองซีพียูของโปรเซสในสถานะรันจะถูกจำกัดเวลาไว้ด้วยระยะเวลาควอนตัม ทำให้โปรเซสที่ต้องการเวลาในการทำงานนานจะต้องเปลี่ยนสถานะหมุนระหว่างสถานะพร้อมและสถานะรัน
การจัดคิวแบบ RR สามารถแก้ปัญหาการคอยนานของโปรเซสที่ต้องการเวลาทำงานน้อย ๆ ได้ลองกลับไปพิจารณาเหตุการณ์สมมติซึ่งกล่าวไว้ในหัวข้อที่แล้ว ถ้าระบบกำหนดเวลาควอนตัมเป็น 1 วินาที โปรเซส A ต้องมีการวนรอบเปลี่ยนสถานะระหว่างสถานะรันและสถานะพร้อม 15 ครั้ง โปรเซส B 1 ครั้ว โปรเซส C 10 ครั้ง เมื่อโปรเซส A เข้าไปอยู่ในสถานะรันครั้งแรกและกลับออกมา โปรเซส B จะได้ครอบครองซีพียูได้และ ทำงานเสร็จโปรเซส B จบและออกจากระบบไปเลยเหลือเพียง 2 โปรเซสที่อยู่ในคิวของสถานะพร้อม โปรเซสถัดไปที่จัดได้ครอบครองซีพียูคือ C โปรเซส C และ A จะสลับกันครอบครองซีพียูกันโปรเซสละ 1 วินาที จนกระทั่งโปรเซส C จบ เหลือโปรเซส A เพียงโปรเซสเดียว เป็นแผนภาพแสดงการสลับกันทำงานของโปรเซสทั้ง 3 และเป็นผลที่เกิดขึ้นจากการจัดคิวแบบ RR
Round Robin (RR): A straightforward way to reduce the penalty that short jobs suffer with FCFS is to use preemption based on a clock. The simplest such algorithm is round robin. A clock interrupt is generated at periodic intervals. When the interrupt occurs, the currently running process is placed in the ready queue, and the next ready job is selected on an FCFS basis. In the current project RR is implemented with time intervals of 1 and 4.

6.2.5 การจัดเวลาแบบคิวหลายระดับ (Multilevel Queue Scheduling)
เพื่อให้การจัดคิวเป็นไปอย่างมีประสิทธิภาพ จึงมีการนำหลาย ๆ เทคนิคมาประยุกต์เข้าด้วยกัน เป็นการจัดคำแบบวนรอบ ที่คำนึงถึงความสำคัญของงาน ทำให้งานที่มีความสำคัญเหมือนกันอยู่ในคิวเดียวกัน และให้งานสำคัญน้อย ๆ อยู่ในคิวที่สำคัญน้อยเช่นกัน

6.3 การประเมินอัลกอริทึม (Algorithm Evaluation) จากที่ได้ศึกษาอัลกอริทึมทั้ง 5 แบบ สำหรับการจัดเวลาซีพียูมาแล้ว ก็ต้องเลือกอัลกอริทึมที่จะใช้งาน สำหรับเลือกงานเข้าประมวลผล มีหลาย ๆ วิธีในการพิจารณาอัลกอริทึม ที่ต้องคำนึงถึง CPU utilization, Response time และ Throughput เพื่อให้ได้ผลออกมาดีที่สุด
หลักเกณฑ์การพิจารณาอัลกอริทึมเข้าประมวลผล
1. ให้ใช้ซีพียูสูงสุด โดยช่วงเวลาตอบสนองต่ำสุด
2. ให้มีเวลารวม หรือวนรอบที่เหมาะสม กับเวลาที่ต้องใช้ประมวลผลทั้งหมด
6.3.1 วิธีกำหนดโมเดล (Deterministic modeling)
วิธีนี้มีข้อจำกัดมากเกินไปสำหรับการนำมาใช้ในปัจจุบัน เพราะวิธีนี้จะเป็นวิธีที่ง่าย ได้ตัวเลขออกมาแน่นอน จากตัวอย่างข้อมูลจำนวนหนึ่งที่ป้อนเข้าไป แต่ผลลัพธ์ไม่มีความน่าเชื่อถือมากพอ เพราะในสถานการณ์จริงจะมีข้อมูลที่ซับซ้อนกว่ามาก เช่นเลือกอัลกอริทึมมาพิจารณา 3 แบบ คือ FCFS, SJF และ RR ซึ่งผลของการพิจารณาแต่ละอัลกอริทึมจะออกเป็นตัวเลขให้เลือก การเลือกเป็นสิ่งที่ตัดสินใจได้ง่าย แต่ไม่อาจไม่เหมาะที่จะใช้งานจริง

6.3.2 วิธีจัดเมเดลของคิว (Queueing models)
วิธีนี้มีปัญหาการคำนวณค่าเฉลี่ยของการกระจายในระบบที่มีความซับซ้อน เมื่อพิจารณาในระบบเครือข่ายที่แบ่งกลุ่มงานออกเป็นสถานี หรือสายการผลิตที่มีคิวของตนเอง ถ้าทราบเวลาที่ให้บริการของแต่ละสายการผลิต และรู้เวลาที่แต่ละงานเข้าคิว ก็จะหาค่าต่าง ๆ ได้ตามต้องการ วิธีนี้เรียกว่า queueing network analysis
จากตัวอย่างข้างต้นอาจใช้สูตร al = at * w (ค่าเฉลี่ยความยาวของคิว = ค่าเฉลี่ยของงานใหม่เข้ามา * ค่าเฉลี่ยการรอคอย) เช่น เวลาเฉลี่ยในคิวคือ 10 วินาที ถ้างานใหม่ต้องรอเข้าคิวประมาณ 2 วินาที และแต่ละงานต้องคอยเข้าหน่วยประมวลผล 5 วินาที

6.3.3 วิธีจำลองสถานการณ์ (Simulations)
วิธีนี้จะพัฒนาโปรแกรมคอมพิวเตอร์ขึ้นมา เสมือนเป็นหุ่นจำลอง พร้อมกำหนดสถาพแวดล้อม และตัวแปรคำนวณเวลาให้อยู่ในการควบคุม โดยเวลาของสถานการณ์กำหนดได้ 2 แบบคือ แบบสุ่ม หรือแบบข้อมูลจริง นอกจากนั้นยังต้องมี trace tape เก็บข้อมูลในช่วงเวลาต่าง ๆ และนำมาเปรียบเทียบ สำหรับวิธีการนี้ต้องอาศัยเวลา และค่าใช้จ่าย เพื่อให้ได้ผลลัพธ์ที่เที่ยงตรง

6.3.4 วิธีติดตั้งจริง (Implementation)
วิธีนี้ไม่นิยมปฏิบัติ แม้แบบจำลองจะไม่มีทางเหมือนจริง จึงมีแนวคิดว่าเขียนขึ้นมาใช้จริงเพื่อให้ได้ข้อมูลจริง แต่วิธีนี้ต้องลงทุนสูงมาก นอกจากต้องเขียนโปรแกรมของอัลกอริทึมแต่ละตัว ยังต้องใช้เวลา และแรงงานเปลี่ยนการทำงานของโปรแกรม การจัดการระบบเพื่อให้รองรับอัลกอริทึมแบบต่าง ๆที่จะนำมาทดลอง ซึ่งแต่ละอัลกอริทึมอาจต้องการฮาร์ดแวร์ที่พิเศษ และคอมพิวเตอร์ก็มิได้เปลี่ยนอุปกรณ์กันได้ง่าย

6.4 ปฏิบัติการเขียนอัลกอริทึม - ฝึกเขียน Scheduling แบบต่าง ๆ
- ค้นคว้าข้อมูลเกี่ยวกับ การจัดเวลาซีพียู จากอินเทอร์เน็ต แล้วทำรายงาน และส่งตัวแทนนำเสนอหน้าชั้น

ถาม - ตอบ ส่วนหนึ่งเรียบเรียงจากหนังสือของ รศ.ดร.กฤษดา ขันกสิกรรม

ถาม	การจัดการโปรเซส มีเกณฑ์อะไรที่ต้องพิจารณาบ้าง
ตอบ	1. Throughput 2. Response time 3. Turnaround time 4. Waiting time 5. CPU efficiency 6. Fairness 7. Preemtive scheduling policy 8. Non-Preemtive scheduling policy
ถาม	ในการจัดการโปรเซสแล้ว เกณฑ์พิจารณา Throughput คืออะไร
ตอบ	จำนวนโปรเซสที่ทำงานได้ในหนึ่งหน่วยเวลา
ถาม	ในการจัดการโปรเซสแล้ว เกณฑ์พิจารณา Response time คืออะไร
ตอบ	เวลาตอบสนองจากระบบ
ถาม	ในการจัดการโปรเซสแล้ว เกณฑ์พิจารณา Turnaround time คืออะไร
ตอบ	เวลาทั้งหมด ตั้งแต่เริ่มต้น ไปจนถึงสิ้นสุดโปรเซส
ถาม	ในการจัดการโปรเซสแล้ว เกณฑ์พิจารณา Waiting time คืออะไร
ตอบ	เวลารอคอยการประมวลผล
ถาม	ในการจัดการโปรเซสแล้ว เกณฑ์พิจารณา CPU efficiency คืออะไร
ตอบ	หน่วยประมวลผลทำงานอย่างมีประสิทธิภาพ กับงานที่ใช้งานหน่วยประมวลผล ไม่ทำงานกับการเรียกใช้อุปกรณ์โดยไม่จำเป็น
ถาม	ในการจัดการโปรเซสแล้ว เกณฑ์พิจารณา Fairness คืออะไร
ตอบ	เกิดความยุติธรรมกับทุกโปรเซส
ถาม	ในการจัดการโปรเซสแล้ว เกณฑ์พิจารณา Preemtive scheduling policy คืออะไร
ตอบ	เป็นนโยบายที่กำหนดให้โปรเซสอื่นเข้ามาแซงคิวได้ (interrupt)
ถาม	ในการจัดการโปรเซสแล้ว เกณฑ์พิจารณา Non-preemtive scheduling policy คืออะไร
ตอบ	เป็นนโยบายการป้องกันการแซงคิว ที่รับรองว่าจะดำเนินโปรเซสไปจนจบ
ถาม	FCFS คืออะไร
ตอบ	คำที่ย่อมาจาก First Come First Server เป็นอัลกอริทึมในการจัดตารางโปรเซสแบบหนึ่ง มีลักษณะมาก่อน บริการก่อน
ถาม	SJN คืออะไร
ตอบ	คำที่ย่อมาจาก Short Job Next เป็นอัลกอริทึมในการจัดตารางโปรเซสแบบหนึ่ง มีลักษณะทำงานสั้นที่สุดก่อน และใช้ Non-preemptive scheduling policy
ถาม	Priority Scheduling คืออะไร
ตอบ	เป็นอัลกอริทึมในการจัดตารางโปรเซสแบบหนึ่ง มีลักษณะทำงานตามลำดับความสำคัญ และใช้ Non-preemptive scheduling policy
ถาม	SRT คืออะไร
ตอบ	คำที่ย่อมาจาก Shortest Remaining Time เป็นอัลกอริทึมในการจัดตารางโปรเซสแบบหนึ่ง มีลักษณะทำงานที่เหลือเวลาต้องทำน้อยที่สุดก่อน
ถาม	RR คืออะไร
ตอบ	คำที่ย่อมาจาก Round Robin เป็นอัลกอริทึมในการจัดตารางโปรเซสแบบหนึ่ง มีลักษณะจัดลำดับงานตามความสำคัญ และแบ่งเป็นหลายแถว และใช้ Preemtive scheduling policy ให้งานถูกขัดจังหวะได้ มี Time slice หรือ Time quantum ให้แต่ละงานเข้าครองหน่วยประมวลผล
ถาม	Multiple level queue คืออะไร
ตอบ	เป็นอัลกอริทึมในการจัดตารางโปรเซสที่เชื่อมโยงอัลกอริทึมอื่น แบ่งออกเป็นกลุ่ม แต่ละกลุ่มจะมีการจัดตารางโปรเซสของตนเอง อาจเป็นแบบ Batch หรือ FCFS หรือ SJN ก็ได้
ถาม	การติดตาย (Deadlock) คืออะไร
ตอบ	สภาวะที่โปรเซสมากกว่า 1 ต้องการใช้ทรัพยากร แต่ทรัพยากรมีอยู่จำกัด ทำให้ไม่สามารถจัดสรรทรัพยากรได้
ถาม	การติดตาย มีกรณีใดบ้าง
ตอบ	1. การร้องขอไฟล์ 2. การติดต่อฐานข้อมูล 3. การจองใช้อุปกรณ์ 4. การใช้อุปกรณ์หลายชิ้น 5. การทำ spooling 6. การใช้แชร์ดิสก์
ถาม	Mutual exclusion คืออะไร
ตอบ	การกีดกั้นการใช้ทรัพยากรจากความพยายามใช้ทรัพยากรที่มีอยู่จำกัดร่วมกัน
ถาม	Resource holding คืออะไร
ตอบ	การถือครองทรัพยากร หรือความเป็นเจ้าของในทรัพยากรนั้น
ถาม	Non-preemtive คืออะไร
ตอบ	การไม่อนุญาตให้เกิดการแทรกแซง
ถาม	Circular wait คืออะไร
ตอบ	การรอคอยไปเรื่อย ๆ เป็นวง ที่ไม่มีจุดสิ้นสุด
ถาม	กลยุทธ์การจัดการติดตาย มีกี่วิธี อะไรบ้าง
ตอบ	มี 3 วิธี 1. Prevention โดยควบคุมไม่ให้การติดตายเกิดขึ้น 2. Avoidance ด้วย Banker's algorithm ประกอบด้วย สถานะปลอดภัย (Safe state) และไม่ปลอดภัย (Unsafe state) ผ่านการควบคุมการถือครอง คิดค้นโดย Edsger W. Dijkstra 3. Detection and recovery
ถาม	อัลกอริทึมการจัดตาราง (Scheduling Algorithms) มีกี่แบบ อะไรบ้าง
ตอบ	มี 5 แบบ 1. การจัดเวลาแบบมาก่อนได้ก่อน (FCFS : First-come First-served Scheduling) 2. การจัดเวลาแบบงานสั้นทำก่อน (SJF : Short-Job-First Scheduling) 3. การจัดเวลาตามลำดับความสำคัญ (Priority Scheduling) 4. การจัดเวลาแบบวนรอบ (RR : Round-Robin Scheduling) 5. การจัดเวลาแบบคิวหลายระดับ (Multilevel Queue Scheduling)

แนะนำเว็บไซต์ (Website guide) + http://www.utdallas.edu/~ilyen/animation/cpu/program/manual.html (มี .java)
+ http://mathcom.uru.ac.th/~Kachane/OS/slide/OS_03_2.ppt อ.คเชนทร์ ซ่อนกลิ่น

เอกสารอ้างอิง (Reference) [1] Abraham silverschatz, Peter baer galvin, "Operating system concept", John wiley & Sons, New York, 2003.
[2] Milan Milenkovic, "Operating systems: concepts and design", McGraw-Hill inc., New York, 1992.
[3] William stallings, "Operating system", Prentice hall, New York, 1999.
[4] ไพศาล โมลิสกุลมงคล และคณะ, "ระบบปฏิบัติการ", สำนักพิมพ์ดวงกมลสมัย, กรุงเทพฯ, 2545.
[5] พิเชษฐ์ ศิริรัตนไพศาลกุล, "ระบบปฏิบัติการ (Operating system)", บริษัท ซีเอ็ดยูเคชั่น จำกัด., กรุงเทพฯ, 2546.
[6] ดร.ยรรยง เต็งอำนวย, "ระบบปฏิบัติการ (Operating system)", บริษัท ซีเอ็ดยูเคชั่น จำกัด., กรุงเทพฯ, 2541.
[7] ประชา พฤกษ์ประเสริฐ, "ระบบปฏิบัติการ", บริษัท ซัคเซส มีเดีย จำกัด., กรุงเทพฯ, 2549.
[8] วศิน เพิ่มทรัพย์, "คู่มือ MS-DOS", พี.เอ็น.การพิมพ์, กรุงเทพฯ, 2545.
[9] ชนินทร์ เชาวมิตร, "คู่มือยูนิกซ์เดสก์ทอป", บริษัท ซีเอ็ดยูเคชั่น จำกัด., กรุงเทพฯ, 2538.
[10] รศ.ดร.กฤษดา ขันกสิกรรม, "ระบบปฏิบัติการ (Operating Systems)", อาง้วนการพิมพ์, นครสวรรค์, 2555.

"Imagination is more important than knowledge" - Albert Einstein

http://goo.gl/72BPC