Scheduling Criteria
Scheduling Algorithms
Multiple-Processor Scheduling
Real-Time Scheduling
Algorithm Evaluation
Basic concepts
วัตถุประสงค์ในการจัดการของ multiprogramming mechanism คือต้องมี process กำลังใช้ CPU ในขณะหนึ่ง ๆ เสมอ เพื่อทำให้เกิด CPU Uitlisation สูงสุด อย่างไรก็ตามในสิ่งแวดล้อมแบบ uniprocess system จะมีเพียงหนึ่ง process เท่านั้น ที่สามารถใช้ CPU ได้ในขณะหนึ่ง ๆ และ process อื่น ๆ ต้องรอ เพื่อเข้าใช้ CPU ต่อเมื่อ CPU ว่างลงในการทำงานของระบบ multiprogramming จะต้องมีการกระจายโอกาสในการเข้าใช้ CPU ให้แก่หลายๆ process ซึ่งโดยทั่วไปจะจัดให้มี process หลายๆ process ใน memory เพื่อสามารถเข้าใช้ CPU ได้เมื่อ CPU ว่างลง (เมื่อ process ที่กำลังใช้ CPU เสร็จการทำงาน หรือขอใช้ I/O) อย่างไรก็ตามเนื่องจากในขณะใดๆ จะมีเพียง process เดียวเท่านั้น ที่สามารถเข้าใช้ CPU ได้ ดังนั้นจะต้องมีวิธีการจัดลำดับ การได้เข้าถึง CPU ของ process ที่รอ ใน memory ซึ่งการทำงานในส่วนนี้คือ หน้าที่ของ CPU Scheduler
แสดงการสลับลำดับของช่วงประมวลผลและช่วงรับส่งข้อมูล
แสดงฮิสโตรแกรมของช่วงเวลาประมวลผลScheduling Criteria
Criteria ที่ใช้ในการเลือก Algorithm หรือวิธีการสำหรับ implement ในส่วนของ CPU Scheduler มีหลายอย่างเช่น
1.CPU Utilisation วัตถุประสงค์หลัก หรือเป้าหมายหลักของการใช้ CPU ให้คุ้มค่านั่นคือ การต้องให้ CPU ทำงานตลอดเวลา ค่าตัวเลขที่ใช้ในการแสดง ค่าของ CPU Utilisation จะใช้ตัวเลขเป็นเปอร์เซ็นต์เช่น ค่า 0-100 % โดยปกติใน system ที่จัดอยู่ในประเภทของ lighty loaded system ค่าของ CPU Utilisation จะอยู่ในช่วงประมาณ 40 % ในขณะที่ heavily loaded system จะมีค่าของ CPU Utilisation ประมาณ 90 %
2.Througput คือ จำนวน process ที่ได้ทำงานเสร็จ (ได้รับบริการ) ในช่วงเวลาหนึ่งๆ เช่น 10 process/ชั่วโมง หรือ 1 process/ชั่วโมง
3.Turnaround Time คือ ระยะเวลาที่ใช้ในการ service แต่ละ process นับตั้งแต่ process นั้นถูกส่ง (submit) เข้าทำงานจนกระทั่ง user ได้ผลลัพธ์กลับมา (ใน Batch system จะเห็นได้ชัดเจนระหว่างความแตกต่างของ Througput และ Turnaround Time นั้นคือ
Turnaround Time = Waiting time to get into memory +
Waiting in ready queue+
Executing on the CPU+
Doing I/O )
4. Waiting time คือ เวลาที่ process ใช้ในการรอ ready queue
5. Response time คือ เวลาที่ process ใช้ในการตอบสนอง ต่อคำสั่งของ user โดย Response time ไม่จำเป็นต้องเท่ากับ Turnaround Time เสมอไป Response time จะมีความจำเป็นมากกว่า Turnaround Time ใน interactive system
Scheduling Algorithms
ทบทวน dcpu scheduling คือการทำงาน(ของ cpu scheduler)เกี่ยวกับ
- การตัดสินว่า process ไหนใน ready queue ได้ใช้ cpu
- ใช้ Algorithm ต่างๆในการตัดสินใจ
ซึ่งมีหลาย Algorithm เช่น
First come, First-Served Scheduling
Shortest-Job-First Scheduling
Priority Scheduling
Round-Robin Scheduling
Multilevel Queue Scheduling
Multilevel Feedback Queue Scheduling
รายละเอียดของแต่ละ Algorithm ดังจะได้กล่าวต่อไปนี้คือ
First-Come, First-Served Scheduling (FCFS)
FIFS เป็น Algorithm ที่ง่ายที่สุดในการจัด cpu ให้แก่ process (หรือจัด process เข้าใช้ cpu) โดยจัดตามลำดับก่อนหลังของ process ที่อยู่ใน ready queue
Average waiting time ของ FCFS จะสูงเมื่อเทียบกับการจักการในรูปแบบอื่น ซึ่ง average waiting time ของ process คือค่าเฉลี่ยของเวลาที่แต่ละ process ต้องรอเพื่อเข้าใช้ cpu นั่นเอง
ปัญหา ที่อาจจะเกิดขึ้นได้ในกรณีที่มี cpu bounded process กำลังใช้ cpu อยู่และมีหลาย I/O ิbounded process รอใช้ cpu ในขณะหนึ่งๆเนื่องจาก cpu bounded process ใช้เวลานานในการใช้ cpu ทำให้ process อื่นๆ ที่รอ I/O operation ทั้งหมดหรือส่วนใหญ่พร้อมที่จะเข้าใช้ cpu ต่อ (I/O operation complete) ทำให้ process ส่วนใหญ่ต้องรอใน ready queue (queue นี้จะยาว) และขณะเดียวกันจะไม่มี process ไหนขอใช้ I/O ได้จนกว่าจะได้กลับเข้าใช้ cpu อีกครั้งทำให้เกิดการว่างงานของ I/O device
ในที่สุดเมื่อ cpu bounded process สิ้นสุด cpu burst cycle และกลับสู่การร้องขอ I/O device (เพื่อใช้ I/O) process ที่อยู่ใน ready queue ได้รับการจัดสรรเข้าสู่ cpu แต่ใช้ cpu ไม่นานนักและในที่สุดทุก process จะกลับเข้าไปรอใน I/O device queue ทำให้เกิดการว่างงานของ cpu (cpu idle) จนกระทั่ง cpu bounded process พร้องที่จะเข้าใช้ cpu ต่อก็จะเกิด cycle เดิม นั้นคือ process อื่นต้องรอใน ready queue (เมื่อ I/O operation complete) อีกเช่นเคยเหตุการณ์นี้ก่อให้เกิด Low CPU Utilization FCFS เป็นการ implement ในรูปแบบของ nonpreemptive scheme และไม่เหมาะสมใน time-sharing system
Shortest-Job-First Scheduling (SJF)
วิธีการของ Algorithm นี้คือการจัดสรร cpu ให้แก่ process ที่ต้องการใช้ cpu ที่มี cycle ของการใช้ cpu สิ้นสุดก่อน (หรือการจัด process ที่ใช้ cpu น้อยๆใน cycle ถัดไปให้เข้าใช้ cpu ก่อน process ที่มี cpu burst cycle ยาว)
ปัญหา ใน short-term scheduling จะไม่สามารถทราบ next cpu burst time ที่แน่นอนได้นอกจากการประมาณค่า เช่น ประมาณค่าจาก cpu burst cycle ก่อน (ใน long-term scheduling อาจจะได้ค่าของ cpu burst time จากการกำหนดของ user ในช่วงของการ submit โปรแกรมนั้นๆเข้าสู่ ready queue)
SJF Algorithm เป็นได้ทั้ง preemptive และ nonpreemptive scheme ในกรณีที่ใช้รูปแบบของ preemtive scheme นั้นเมื่อมี job ใหม่เข้ามาสู่ ready queue ที่มี cpu burst time น้อยกว่า cpu burst time ส่วนของ process ที่กำลังใช้ cpu อยู่ process นั้นจะถูกขัดจังหวะ (preempt) และนำออกจาก cpu เพื่อให้ job ที่มี cpu burst time น้อยกว่าเข้าใช้ cpu แทนดังนั้นในบางครั้งวิธีการนี้จะเรียกว่า Shortest-Remaining-Time-First หากวิธีการ implement ของ SJF เลือกใช้รูปแบบของ nonpreemtive scheme job ที่เพิ่งเข้ามาสู่ ready queue ต้องรอจนกว่า process ที่กำลังรอใช้ cpu ปล่อย cpu ใน cycle นั้นก่อนจึงจะได้รับการจัดสรร cpu ถึงแม้ว่า cpu burst time จะน้อยกว่า process ที่กำลังใช้ cpu ก็ตาม
Priority Scheduling
เป็นการจัดลำดับ process ที่จะเข้าใช้ CPU ตามลำดับสิทธิ์ของแต่ละ process ดังนั้นในการจัดการ ในรูปแบบนี้ ทุก process จะมีค่าที่กำหนดสิทธิ์ (priority) ของตนเอง และ process ที่มีค่าสิทธิ์สูงสุด จะได้รับการจัดสรรค์ CPU ให้ใช้ในช่วงเวลานั้น ๆ และ process ที่มี priority รองลงมา จะได้รับการจัดสรรค์ CPU ให้ใช้ถัดไปตามลำดับ
ค่า priority กำหนดได้ทั้งจากภายใน (internallity defined) และจากภายนอก (externally defined) โดยที่การกำหนดจากภายในของระบบเอง สามารถทำได้โดยการ คำนวณจากค่าตัวแปรหรือค่าที่เกี่ยวข้องต่างๆ เช่น เวลา หรือ จำนวน memory ที่ process ต้องการ หรือแม้แต่จำนวนไฟล์ ที่ process ต้องการ ฯลฯ จะเห็นได้ว่าค่าเหล่านี้ขึ้นอยู่กับรูปแบบ และการทำงานของแต่ละ process และสามารคำนวณได้เมื่อ process นั้นๆ ใช้ทรัพยากรต่างๆ ของระบบ แต่ค่าลำดับสิทธิ์ ที่กำหนดจากภายนอก โดยทั่วไปจะเป็นการกำหนดจากขอบข่ายอื่นๆ ที่ไม่เกี่ยวข้องกับ การใช้ทรัพยากรของระบบโดยตรง เช่น การกำหนดความสำคัญของหน่วยงาน (เจ้าของ process) หรือค่าเช่าใช้ CPU ฯลฯ
ปัญหา สำคัญที่เกิดขึ้นเนื่องจากการใช้ algorithm นี้คือ การที่ process ต่างๆ ซึ่งมี priority ต่ำหรือต่ำมาก ไม่ได้รับการจัดสรร CPU เลย ถ้าหากในระบบนั้นๆ มี process ที่มีค่า priority สูง เข้ามาสู่ระบบตลอดเวลา เนื่องจาก process เหล่านี้จะได้รับการจัดสรร CPU เสมอ และ process ที่มี priority ต่ำ จะต้องรอจนกว่าไม่มี process อื่น ๆ ซึ่งมี priority สูงกว่าอีกแล้ว ปัญหาในรูปแบบนี้เรียกว่า "Indefinite blocking" หรือ "starvation"
เพื่อแก้ปัญหาดังกล่าวได้นำวิธีการที่เรียกว่า "Aging" มาช่วย นั่นคือ การกำหนดให้ ค่า priority สูงขึ้น เมื่อ process นั้นๆ ต้องรอ ใน ready queue เป็นเวลานาน เพื่อสามารถเข้าแข่งขัน เพื่อขอใช้ CPU ได้ด้วย วิธีการนี้จะทำให้ process ที่มีค่า priority ต่ำ สามารถเข้าใช้ CPU ได้
เมื่อเวลาผ่านไป (ไม่ต้องรอแบบไม่มีกำหนด)
Round-Robin Scheduling
เป็นการจัดสรรอีกรูปแบหนึ่งที่ถูกออกแบบมาสำหรับระบบ time sharing โดยที่การทำงาน คล้ายกับ FCFS Scheduling นั่นคือ process ได้รับการจัดลำดับ ใน ready queue ตามลำดับการเข้าสู่ระบบ (เข้าสู่ queue) แต่อย่างไรก็ตาม process ที่กำลังใช้ CPU สามารถใช้ CPU ได้ในระยะเวลาจำกัดในแต่ละครั้ง นั่นคือมีการกำหนดช่วงเวลา ที่แต่ละ process จะใช้ CPU ได้ เรียกว่า time quantum หรือ time slice เมื่อ process ใด ๆ ใช้ CPU ครบเวลา 1 time quantum แล้ว process นั้นจะต้องออกจาก CPU กลับไปสู่ ready queue ในลำดับถัดไป และ CPU จะได้รับการจัดสรร ให้แก่ process ในลำดับต้น queue ใน ready queue ต่อไป
ถึงแม้ว่าการจัดการในรูปแบบนี้ จะทำให้ process ต่างๆใน ready queue ได้รับการจัดสรรให้ใช้ CPU ในอัตราส่วนที่ใกล้เคียงกัน นั่นคือ แต่ละ process มีโอกาสได้เข้าใช้ CPU แน่นอน เมื่อเวลาผ่านไประยะหนึ่ง แต่ค่าเฉลี่ยในการรอคอยเข้าใช้ CPU ของการจัดในรูปแบบนี้จะค่อนข้างสูง
RR Scheduling เป็นการจัดการแบบ Preemptive เสมอ เนื่องจากแต่ละ process สามารถเข้าใช้ CPU ได้มากที่สุดหรือนานที่สุด เท่ากับระยะเวลาของ 1 quantum time เท่านั้น ในการเข้าใช้ CPU หนึ่งรอบ และ process ที่ถูกออกจาก CPU และกลับไปรอใน ready queue burst time มากกว่า 1 quantum time
ในการจัดการแบบนี้ สามารถประมาณเวลาที่แต่ละ process ต้องรอใน ready queue ได้เสมอ นั้นคือ
ถ้าให้ มี process ทั้งหมดใน ready queue คือ n process
quantum time คือ q นั้นคือแต่ละ process จะได้รับการจัดสรรให้ใช้ CPU ทุกๆ 1/n (รอบละ q milliseconds)
แต่ละ process จะรอนานที่สุดไม่เกิน (n-1)*q milliseconds ในแต่ละรอบ
ตัวอย่าง ถ้าให้มี process ใน ready queue ทั้งหมด 5 process และ quantum time คือ 20 milliseconds
จะได้ว่า แต่ละ process จะได้รับการจัดสรร CPU สูงสุด 20 milliseconds ในทุกๆ 100 milliseconds ในแต่ละรอบ (และ process จะรอไม่เกิน 80 milliseconds เพื่อเข้าใช้ CPU ในแต่ละครั้ง)
ประสิทธิภาพของการจัดสรร Scheduling แบบนี้ขึ้นอยู่กับขนาดของ quantum time เป็นหลัก ในกรณีที่ให้ quantum time กว้างมากเช่นมากกว่า CPU Burst time ของแต่ละ process จะได้ว่าการจัด CPU Scheduling ในกรณีนี้ก็คือ การจัดแบบ FCFS นั้นเอง แต่ถ้าให้ขนาดของ quantum time เล็กมาก (เช่น 1 milliseconds) แต่ละ process จะได้ รับการจัดสรร CPU ใน ระยะเวลาสั้นมากเช่นเดียวกัน ทำให้ user มีความรู้สึกว่า CPU ของตนเองโดยเฉพาะ (เนื่องจากได้รับการจัดสรร CPU ในช่วงระยะเวลาถี่มาก) และการจัดแบบนี้เรียกว่า process sharing
อย่างไรก็ตาม ในการกำหนดขนาดของ quantum time ใน RR Scheduling ต้องคำนึง overhead ที่จะเกิดจากการทำ Context Switching ด้วยเพื่อพิจารณาประสิทธิภาพโดยรวมของระบบ เนื่องจากถ้ากำหนด quantum time ขนาดเล็กจะก่อให้เกิด จำนวนครั้งของการเกิด Context Switching สูงมากกว่าในการกำหนดให้ ขนาดของ quantum time ใหญ่
นอกจากนี้ turn around time ของ process ก็ขึ้นอยู่กับขนาดของ Quantum time เช่นเดียวกัน ถ้าขนาดของ Quantum time เล็กมาก จำนวนของ Context Switching ที่เกิดขึ้นมากครั้ง จะเป็นตัวทำให้ turn around time ของ process เพิ่มขึ้นด้วยเช่นกัน และโดยปกติ turn around time ของ process ต่างๆ จะดีถ้า process สามารถ ทำงานได้เสร็จในช่วงของการได้รับการจัดสรร CPU ในรอบถัดไป (นั้นคือ burst time ที่เหลือจะน้อยกว่าขนาดของ quantum time จะไม่ต้องรอ CPU ในรอบถัดไปอีก)
การจัดตารางการทำงานแบบแถวคอยหลายระดับ (Multilevel Queue Scheduling)
ขั้นตอนวิธีในการจัดตารางการทำงานแบบคอยหลายระดับนี้ เริ่มจากการจัดแถวพร้อมของระบบออกเป็นหลายๆ แถวแยกจากัน ดังแสดงในรูป และกระบวนการที่เข้าสู่ระบบก็จะถูกกำหนดให้เข้าแถวที่แน่นอนตายตัว เพื่อเข้าไปใช้หน่วยประมวลผลกลาง ภายในแถวพร้อมแต่ละแถวก็จะมีการจัดตารางการทำงานของแต่ละแถวต่างหาก
นระบบมีแถวพร้อมอยู่ 5 แถว ดังนี้
- งานของระบบ
- งานแบบโต้ตอบ
- งานแก้ไขข้อมูล
- งานแบบกลุ่ม
- งานของนักศึกษา
การจัดตารางการทำงานแบบจัดลำดับหลายระดับแบบเลื่อนชั้นได้ (Multilevel Feedback Queue Scheduling)
การจัดตารางการทำงานแบบจัดลำดับหลายระดับแบบเลื่อนชั้นได้นี้ จะมีวิธีการในการทำงานที่แก้ข้อเสียดังกล่าว โดยเมื่อกระบวนการใดใช้เวลาในการทำงานกับหน่วยประมวลผลกลางนานเกินไป กระบวนการนั้นจะถูกย้ายลงไปในแถวที่มีค่าศักดิ์ต่ำกว่าแถวเดิม วิธีนี้จะทำให้กระบวนการที่เน้นการรับส่งข้อมูล และกระบวนการโต้ตอบถูกจัดอยู่ในแถวพร้อมที่มีศักดิ์สูงขึ้นในทำนองเดียวกันเมื่อกระบวนการใดกระบวนการหนึ่งรอคอยอยู่เป็นเวลานานมากแล้วในแถวที่มีศักดิ์ต่ำ กระบวนการนั้นก็สามารถที่จะย้ายไปต่อในแถวที่มีศักดิ์สูงขึ้นได้ ซึ่งวิธีการดังกล่าวเป็นรูปแบบหนึ่งของการเพิ่มศักดิ์ แสดงการจัดลำดับหลายระดับแบบเลื่อนชั้นได้
การทำงานโดยวิธีการจัดตารางการทำงานแบบจัดลำดับหลายระดับแบบเลื่อนชั้นได้นี้ ถูกกำหนดโดยพารามิเตอร์ดังนี้
จำนวนแถวพร้อม
ขั้นตอนวิธีในการจัดตารางการทำงานของแต่ละแถว
วิธีที่จะใช้ในการพิจารณาเพื่อที่จะยกระดับให้กระบวนการที่มีค่าศักดิ์สูงขึ้น
วิธีที่จะใช้ในการพิจารณาเพื่อที่จะลดระดับให้กระบวนการที่มีค่าศักดิ์น้อยลง
วิธีที่จะใช้ในการพิจารณาว่า เมื่อกระบวนการเช้ามาในระบบ ควรจะให้อยู่ในแถวใด
การจัดตารางการทำงานสำหรับหลายหน่วยประมวลผล (Multiple Processor Scheduling)
ถ้าหน่วยประมวลผลมีหลายแบบ วิธีการจัดตารางก็จะถูกจำกัดมาก แต่ละหน่วยประมวลผลก็จะมีแถวคอยเป็นของตนเอง เพราะกระยวนการต่างๆย่อมมีลักษณะเฉพาะที่จะทำงานได้ในหน่วยประมวลผลแบบหนึ่งแบบเดียว กระบวนการจึงต้องเข้าไปทำงานตามหน่วยประมวลผลที่เหมาะสม โดยแยกแถวคอยกันเอง
ถ้าหน่วยประมวลผลเป็นแบบเดียวกันหมด เราสามารถเฉลี่ยแบ่งงานกันทำได้ดีขึ้น โดยอาจให้มีแถวคอยแยกแต่ละหน่วยประมวลผล แต่วิธีนี้อาจทำให้หน่วยประมวลผลบางตัวว่างงาน ในขณะที่บางตัวงานหนัก เราจึงควรใช้แถวคอยร่วมแถวเดียวกันให้ทุกๆ กระบวนการเข้าแถวคอยเดียวกันหมด เมื่อมีหน่วยประมวลผลใดว่าง ก็จะให้รับงานไปจากแถวคอยนี้
การจัดแถวคอยร่วมนี้ อาจแบ่งได้เป็น 2 วิธี
- ให้หน่วยประมวลผลแต่ละตัวจัดตารางการทำงานเอง
- กำหนดให้หน่วยประมวลผลหนึ่งมีหน้าที่จัดตารางการทำงานโดยเฉพาะ
การจัดตารางการทำงานแบบตอบสนองฉับพลัน (Real Time Scheduling)
การจัดตารางการทำงานแบบตอบสนองฉับพลันนี้แบ่งเป็น 2 ประเภท คือ
1. Hard Real time System ต้องการเวลาที่คงที่แน่นอน ตายตัว
2. Soft Real time System เป็นระบบที่ทำงานโดยไม่ต้องมีเวลามาจำกัด
การประเมินอัลกอริทึม (Algorithm Evaluation)
วิธีการจัดตารางมีหลายวิธี แต่ละวิธีมีตัวแปรและลักษณะเฉพาะ ทำให้การเลือกวิธีที่เหมาะสมหรือดีที่สุดทำได้ยาก
ขั้นแรกจำเป็นต้องกำหนดคุณสมบัติก่อนว่า ต้องการคุณลักษณะใด มีค่าเท่าใด เช่น
ให้ได้ประสิทธิผลการใช้หน่วยประมวลผลสูงสุดที่เวลาตอบสนองนานที่สุด ไม่เกิน 1 วินาที
ให้มีอัตรางานเสร็จสูงที่สุด โดยที่วงรอบการทำงาน เป็นสัดส่วนโดยตรงกับการประมวลผลจริง
แสดงการประเมินของตัวจัดตารางของหน่วยประมวลผล
ไม่มีความคิดเห็น:
แสดงความคิดเห็น