บทที่3 การจัดเวลาซีพียู

การจัดเวลาซีพียู
(cpu Scheduling)
น.ต.เมธา สุนทรศารทูล
การจัดเวลาซีพียู (cpu Scheduling) เป็นหลักการทำงานหนึ่งของระบบปฏิบัติการที่ทำให้คอมพิวเตอร์มีความสามารถในการรันโปรแกรมหลายๆ โปรแกรมในเวลาเดียวกัน ซึ่งการแบ่งเวลาการเข้าใช้ซีพียูให้กับโปรเซสที่อาจถูกส่งมาหลายๆ โปรเซสพร้อมๆกัน ในขณะที่ซีพียูอาจมีจำนวนน้อยกว่าโปรเซส หรืออาจมีซีพียูเพียงตัวเดียว จะทำให้คอมพิวเตอร์สามารถทำงานได้ปริมาณงานที่มากขึ้นกว่าการที่ให้ซีพียูทำงานให้เสร็จทีละโปรเซส ในบทนี้ เราจะมาพูดถึงอัลกอริทึมพื้นฐานของการจัดเวลาซีพียูนี้ โดยจะพูดถึงวิธีการหลักๆ ที่แต่ละอัลกอริทึมมีแตกต่างกัน ข้อดีข้อเสีย และความเหมาะสมต่อระบบงานแบบต่างๆ เพื่อการเลือกใช้อย่างถูกต้อง
3.1 หลักความต้องการพื้นฐาน
จุดประสงค์ของการรันโปรแกรมหลายโปรแกรมคือ ความต้องการที่จะให้ซีพียูมีการทำงานตลอดเวลาเพื่อให้มีการใช้ซีพียูอย่างเต็มที่ และเต็มประสิทธิภาพ ซึ่งระบบคอมพิวเตอร์มีซีพียูตัวเดียว ในเวลาใดเวลาหนึ่งซีพียูจะทำงานได้เพียงงานเดียวเท่านั้น ถ้ามีหลายโปรแกรมหรือหลายงาน งานที่เหลือก็ต้องคอยจนกว่า จะมีการจัดการให้เข้าไปใช้ซีพียู
ความคิดและหลักการของการทำงานกับหลายโปรแกรมในขั้นพิ้นฐานนั้นค่อนข้างที่จะไม่ซับซ้อน แต่ละโปรแกรมจะถูกรันจนกระทั่งถึงจุดที่มันจะต้องคอยอะไรซักอย่างเพื่อใช้สำหรับการทำงานช่วงต่อไป ส่วนมากการคอยเหล่านี้ก็คือการทำงานที่เกี่ยวข้องกับอินพุต/เอาต์พุตนั้นเอง ในระบบคอมพิวเตอร์ที่มีความสามารถรันโปรแกรมได้ทีละโปรแกรม การทำงานของระบบก็จะไม่ซับซ้อน ซีพียูจะหยุดการทำงานในระหว่างที่คอยอินพุต/เอาต์พุตนี้ ซึ่งการคอยเหล่านี้เป็นการเสียเวลาโดยเปล่าประโยชน์ เพราะซีพียูไม่ได้ทำงานเลย
ส่วนหลักในการรันหลายโปรแกรม เราพยายามใช้เวลาเวลาที่ซีพียูต้องคอยนี้ทำงานอย่างอื่นต่อไป ดังนั้นเมื่อใดก็ตามที่ซีพียูต้องคอย และยังมีโปรแกรมในหน่วยความจำหลายโปรแกรมที่คอยการใช้ซีพียูอยู่ เราจะจัดให้ซีพียู ทำงานในโปรแกรมเหล่านั้นทันที ซึ่งระบบจะจัดการนำเอาโปรแกรมที่คอยอินพุต/เอาต์พุต ออกไปก่อน เพื่อที่จะให้โปรแกรมอื่นที่คอยใช้ซีพียูนี้ สามารถเข้ามาได้ ถ้าทำงานในแบบนี้ไปเรื่อยๆ ซีพียูก็จะได้มีงานเกือบตลอดเวลากับโปรแกรมหลายๆ โปรแกรมที่อยู่ในระบบ
การจัดเวลาให้กับซีพียูแบบนี้ เป็นหลักความต้องการพื้นฐานของระบบปฏิบัติการในคอมพิวเตอร์ ทรัพยากรที่คอมพิวเตอร์มีอยู่ในเครื่องๆหนึ่ง จะถูกจัดสรรการใช้ก่อนการนำไปให้โปรแกรมใดๆ ซีพียูเองก็ถือได้ว่าเป็นทรัพยากรของระบบคอมพิวเตอร์ชนิดหนึ่งที่มีความสำคัญมากที่สุด โดยซีพียูนี่เอง ที่จะเป็นศุนย์กลางของการสร้างระบบปฏิบัติการที่มีความสามารถในการรันหลายโปรแกรม

3.1.1 ช่วงเวลาอินพุต/เอาต์พุต และช่วงเวลาใช้ซีพียู (I/O) and CPU Burst Cycle)
ความสำคัญของการจัดเวลาของซีพียูนั้น ขึ้นอยู่กับคุณลักษณะของโปรเซส โดยทั่ว ๆ ไป การเอ็กซีคิวต์โปรเซส จะประกอบด้วยเวลาที่ใช้ซีพียู (CPU Burst Cycle) และเวลาที่คอยอุปกรณ์อินพุต/เอาต์พุต
(I/O) and CPU Burst Cycle) ในขณะที่มีการเอ็กซีคิวต์โปรเซส จะมีการสลับการทำงานระหว่าง 2 ช่วง เวลานี้ เท่านั้น และจะเกิดไม่พร้อมกัน และการเอ็กซีคิวต์มักจะเริ่มจาการใช้ซีพียู แล้วก็ตามด้วยหารอินพุต/เอาต์พุต เมื่อจบการรอคอยก็จะตามมาด้วยเวลาของซีพียู สลับกันไปเรื่อยๆ จนกว่าจะจบการเอ็กซีคิวต์ ซึ่งการเอ็กซีคิวต์นี้มักเป็นการใช้เวลาซีพียูเพื่อทำการจบหรือสิ้นสุดโปรเซสมากกว่าการรอคอยอินพุต/เอาต์พุต (ดูรูป 3.1)



รูป 3.1 การทำงานที่หลากหลายที่ใช้เวลาซีพียูและเวลาในการคอยอินพุต/เอาต์พุต [OSC6:P152]
จากการค้นคว้าที่ผ่านมา ได้มีการศึกษาถึงลักษณะช่วงเวลาของการใช้ซีพียูไว้จาสามารถมองเห็นคร่าวๆว่า ลักษณะของช่วงเวลาที่ใช้ซีพียูในแต่ละโปรเซสจะมีรูปแบบอย่างไร ถึงแม้ว่ารูปแบบของเวลาอาจจะมีความแตกต่างกันอยู่บ้าง แต่ก็มีแนวโน้มที่ว่า แต่ละโปรเซสมักจะมีคาบเวลาการเข้าใช้ซีพียูคล้ายๆกันในรูป 3.2

รูป3.2 ฮีสโตแกรมของเวลาซีพียู [OSC6:P153]

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

3.1.2 ตัวจัดการเวลาซีพียู (CPU Scheduler)
เมื่อใดก็ตามที่ซีพียูว่าง ระบบปฏิบัติการจะต้องเข้ามาเลือกโปรเซสตัวใดตัวหนึ่งที่คอยอยู่ในคิวเข้ามาใช้งานซีพียู การเลือกโปรเซสเพื่อเข้ามาใช้ซีพียูนี้ จะถูกจัดการด้วยส่วนที่เรียกว่า ตัวจัดการช่วงสั้น (Short – term Scheduler) หรือ ตัวจัดการเวลาซีพียู (CPU Scheduler) ตัวจัดการเวลานี้จะเลือกโปรเซสที่อยู่ในหน่วยความจำที่พร้อมในการเอ็กซีคิวต์ที่สุด เพื่อให้ครอบครองเวลาซีพียูและทรัพยากรที่เกี่ยวข้องกับโปรเซสนั้น
ติวของโปรเซสในหน่วยความจำนั้นไม่จำเป็นต้องเป็นแบบมาก่อนได้ก่อน (FIFO : First in First out) เสมอไป อาจจะเป็นไปตามลำดับความสำคัญ (Priority) โครงร่างต้นไม้(Tree) หรืออาจจะเป็นลิ้งลิสก็ได้ อย่างไรก็ตามโปรเซสทุกโปรเซสที่หร้อมใช้ซีพียู จะต้องมีโอกาสได้เข้าครอบครองเวลาซีพียูไม่เวลาใดก็เวลาหนึ่ง ซึ่งการเข้าและออกจากการครอบครองเวลาซีพียูแต่ละครั้ง จำเป็นต้องมีการเก็บข้อมูลไว้เสมอว่า เข้ามาแล้วได้ทำอะไรไปบ้าง ช่วงต่อไปจะทำอะไร เป็นต้น โดยใช้พื้นที่หน่วยความจำส่วนหนึ่งเก็บข้อมูลของแต่ละโปรเซสหลังเสร็จสิ้นการใช้ซีพียู พื้นที่หน่วยความจำที่มีชื่อว่า บล็อคควบคุมโปรเซส (PCB : Process Control Block)

3.1.3 การให้สิทธิการจัดเวลา (Preemptive Scheduling)
การตัดสินใจของซีพียูในการเลือกเอ็กซีคิวต์โปรเซสใดๆ ขึ้นอยู่กับสถานการณ์ดังนี้
1. เมื่อมีการเปลี่ยนสถานะของโปรเซสจากสถานะรัน ไปเป็นสถานะคอย เช่น ในสภาวะที่คอยอินพุต/เอาต์พุต หรือการคอยให้โปรเซสลูกเสร็จสิ้นไปก่อน เป็นต้น
2. เมื่อการเปลี่ยนสถานะของโปรเซสจากรัน เป็นสถานะพร้อม เช่นเมื่อมีอินเทอรัพต์เกิดขึ้น เป็นต้น
3. เทื่อมีการเปลี่ยนสถานะของโปรเซสจากสถานะคอย เป็นสถานะพร้อม เช่นเมื่อ อินพุต/เอาต์พุต เสร็จสิ้นไปแล้ว เป็นต้น
4. มื่อโปรเซสเสร็จสิ้นไปแล้ว

ทั้ง 4 สถานการณ์ดังกล่าวข้างต้น ในสถานการณ์ที่1 และ 4 นั้นเป็นสถานการณ์มราจะต้องมีการตัดสินใจทำอะไรอย่างใดอย่างหนึ่งโดยไม่สามารถหลีกเลี่ยงได้ เช่น ต้องไปเลือกโปรเซสใหม่เข้ามาเอ็กซีคิวต์ต่อไป เนื่องจากโปรเซสเดิมไม่ใช้ซีพียูอีกแล้ว แต่สำหรับสถานการณ์ที่ 2 และ 3 นั้น การตัดสินใจต้องอยู่บนพื้นฐานหรือกฎเกณฑ์ ของแต่ล่ะอัลกอริทึมที่ใช้ ซึ่งอาจทำให้มีการทำงานที่แตกต่างกันไป
การตัดสินใจที่เกิดขึ้นเนื่องจากสถานการณ์ 1 และ 4 การจัดเวลาซีพียูจะเป็นแบบไม่ให้สิทธิ์ก่อน (non preemptive) นอกนั้นจะเรียกว่าให้สิทธิ์ก่อน (preemptive) ภายใต้การทำงานแบบไม่ให้สิทธิ์ก่อนนี้ โปรเซสจะครอบครองเวลาซีพียูไปจนกว่าจะเสร็จ หรือเปลี่ยนสถานะตัวเองเป็นสถานะคอย การจัดเวลาซีพียูแบบนี้เป็นวิธีการที่ใช้อยู่ในระบบปฏิบัติการ window3.1 และ Apple Macintoch ซึ่งเป็นพียงวิธีการที่ใช้ได้เฉพาะกับแพล็ตฟอร์มของฮาร์ดแวร์เฉพาะแบบเท่านั้น เนื่องจากระบบปฏิบัติการนี้ไม่ต้องการในการใช้ฮาดแวร์พิเศษ เช่น ไทม์เมอร์ ในการนับคาบเวลาสำหรับการให้โปรเซสใดๆ ครอบครองเวลาซีพียูโปรเซสใดๆในระบบนี้สามารถครอบครองเวลาซีพียูได้จนกว่าจะหมดความต้องการ ถ้าระบบนี้ต้องการทำเป็นระบบมัลติยูเชอร์ การจัดเวลาแบบให้สิทธิก่อนจะเหมาะสมกว่า
แต่ปัญหาก็มีอยู่ว่าการจัดเวลาแบบให้สิทธิก่อนนั้นต้องใช้ทรัพยากรพิเศษเข้าช่วยเยอะเพื่อแก้ปัญกาต่างๆ ที่หลักเลี่ยงไม่ได้ที่มีอยู่มากมาย ทำให้ระบบมีราคาแพง คิดง่ายๆ อย่างเช่นในกรณีของโปรเซส 2 โปรเซสที่ใช้ข้อมูลร่วมกัน โปรเซสแรกอาจจะต้องหยุดรอในขณะที่อยู่ในระหว่างการอัปเดทขอ้มูล เนื่องจากคาบเวลามันหมดพอดี แล้วโปรเซสสองก็เข้ามาแทน ซึ่งโปรเซสที่สองนี้อาจจะต้องการที่จะอ่านข้อมูลที่โปรเซสแรกยังแก้ไขไม่เรียบร้อย ถึงแม้ว่าเหตุการณ์แบบนี้จะดูเป็นเรื่องธรรมดาสำหรับการแก้ไช แต่ในการทำงานจริงๆ แล้ว ระบบปฏิบัติการจะต้องมีตัวช่วยพิเศษมากมาย ดังกล่าวในบทต่อไปนี้
วิธีการจัดเวลาแบบให้สิทธิก่อนนั้นมีผลกระทบต่อการออกแบบ kernel ของระบบปฏิบัติการเป็นอย่างมาก เช่น ในระหว่างเกิด systemcall นั้น kernel อาจจะยังไม่ว่าง เช่นกำลังทำงานในการจัดคิวโปรเซสอยู่ แล้วอะไรจะเกิดขึ้นหากว่าโปรเซสทำให้หยุด และออกจากการครอบครองเวลาซีพียูแน่นอนความวุ่นวายต้องเกิดขึ้น ระบบปฏิบัติการบางตัวเช่น UNIX มีการแก้ปัญหาตรงจุดนี้โดยให้ systemcall สิ้นสุดเอง หรือไม่ก็คอยจนกว่าจะมีการบล็อคการทำงานของอินพุต/เอาต์พุตเกิดขึ้น แล้วจึงมีการทำคอนเท็กซ์สวิตซ์ ที่ทำเช่นนี้ก็เพราะว่า การออกแบบ kernel จะได้ไม่มีความยุ่งยากมาก ตัว kernel เองจะได้ไม่ไปจัดการโปรเซสอื่นๆ ถ้าโครงสร้างข้อมูลของ kernel ยังไม่อยู่ในสภาพสมบูรณ์ แต่ปัญหาก็คือการทำงานของ kernel แบบนี้ช้าเกินไป ทำให้ต้องมีการพัฒนาบางสิ่งบางอย่าง เพิ่มเติมเข้ามาอีก ดังกล่าวในย่อหน้าต่อไป

3.2.1 Dispatcher
คอมโพเนนต์ที่สำคัญอีกตัวหนึ่งที่เกี่ยวข้องกับฟังก์ชันในการจัดเวลาซีพียูก็คือสิ่งที่เรียกว่า Dispatcher ซึ่งเป็นโมดูลที่ทำหน้าที่ควบคุมการครอบครองซีพียูของโปรเซส ฟังก์ชันนี้ประกอบด้วย
- การย้าย Context
- การย้ายไป user mode
- กระโดดไปยังตำแหน่งที่เหมาะสมของโปรแกรม เพื่อที่จะเริ่มรันโปรแกรมนั้นใหม่อีกครั้ง


Dispatcher นี้ควรมีการทำงานที่เร็วที่สุดเท่าที่จะทำได้ เพราะว่ามันจะต้องทำงานทุกครั้งที่มีการย้ายโปรเซส ซึ่งเวลาที่ถูกใช้ไปกับการกระทำเช่นนี้เราเรียกว่า Dispatch Latency

3.2 ข้อพิจารณาในการจัดเวลา
อัลกอริทึมของการจัดเวลาซีพียู มีคุณสมบัติแตกต่างกันไป ซึ่งอาจจะมีการให้ความสำคัญกับโปรเซสอย่างมากกว่าโปรเซสอื่นๆ ดังนั้นการเลือกอัลกอริทึมสำหรับใช้ในสถาการณ์ต่างๆนั้น เราจำเป็นที่จะต้องพิจารณาถึงคุณสมบัติ เหล่านี้ให้ดีว่ามีข้อดีข้อเสีย อย่างไร
ข้อพิจารณาหลายข้อ ได้ถูกำหนดไว้เพื่อใช้ไปในการเปรียบเทียบอัลกอริทึมต่างๆ ซึ่งลักษณะข้อพิจารณาแต่ละชนิดนั้น สามารถสร้างความแตกต่างให้เห็นได้อย่างชัดเจนในการตัดสินว่าอัลกอริทึมใดดีที่สุด ข้อการพิจารณาดังกล่าวนี้มีดังนี้
- อรรถประโยชน์ของซีพียู (CPU utilization) คือคำนึงถึงการใช้ประโยชน์จากซีพียูอย่างสูงสุด โดยทำให้ซีพียูมีการทำงานมากที่สุดเท่าที่จะทำได้ คิดเป็นเปอร์เซนต์ระหว่าง 0-100% ซีพียูควรถูกใช้งานระหว่าง 40-90%
- ทรูพุต (Throughput) ถ้าหากว่าซีพียูทำงานตลอดเวลาก็หมายความว่างานก็กำลังถูกให้ให้เสร็จ ซึ่งเราสามารถวัดออกมาได้เป็นจำนวนงานที่เสร็จต่อหน่วยเวลา หรือเรียกว่าทรูอินพุต สำหรับงานที่ยาวมาก อัตราการทำงานหรือค่าอินพุต อาจจะเป็นหนึ่งงานต่อชั่วโมง และก็อาจจะเป็นไปได้ว่างานที่สั้น ก็จะทำให้ทรูอินพุตของระบบสามารถวัดได้ถึง 10 งานต่อวินาที
- เวลาทั้งหมด (Turnaround Time) คือช่วงเวลาทั้งหมดที่ใช้ในการทำงานใดงานหนึ่งตั้งแต่เริ่มต้นเข้าไปในระบบ จนงานถูกทำเสร็จเรียบร้อย ซึ่งจะรวมเอาเวลาที่จะต้องรอที่จะเข้าไปในหน่วยความจำ เวลาที่คอยอยู่ในคิว เวลาที่ใช้ซีพียู และเวลาของอินพุต/เอาต์พุต ทั้งหมดเข้าด้วยกัน
- เวลาคอย (Waiting Time) คือช่วงเวลาที่งานใดงานหนึ่งต้องรอการทำงานของตัวจัดเวลา โดยไม่รวมเวลาของการใช้ซีพียู และเวลาของการติดต่ออินพุต/เอาต์พุต ส่วนใหญ่ก็คือเวลาที่งานต้องคอยอยู๋ในคิว (Ready Queue) นั้นเอง
- เวลาตอบสนอง (Response Time)คือเวลาที่วัดระหว่างเวลาที่มีการเรียกร้องขอการกระทำใดๆต่อระบบแล้วมีการตอบรับกลับมา ซึ่งในบางโปรแกรมที่มีการติดต่อกับผู้ใช้ภายนอกมากๆ เวลารวมทั้งหมดอาจไม่ใช่จุดประสงค์หลักที่ต้องการ เพราะเมื่อมีการติดต่อกับโปรแกรมกับผู้ใช้งานภายนอกนั้น ระบบปฏิบัตืการจะสิ้นสุดการรับผิดชอบเมื่อการร้องขออินพุต/เอาต์พุต สิ้นสุดลง ต่อจากนั้นระบบปฏิบัติการก็จะไปจัดการเรื่องภายในเกี่ยวข้องกับซีพียู อุปกรณ์อินพุต/เอาต์พุตต่างๆที่ติดอยู่กับระบบเหล่านี้ก็จะเป็นผู้ติดต่อกับผู้ใช้งาน ดังนั้นเรื่องความเร็วของเวลาตอบสนองมักจะขึ้นอยู่กับอุปกรณ์ อินพุต/เอาต์พุตเหล่านี้ ตัวอย่างเช่น เครื่องพิมพ์ ซีพียูอาจใช้คำนวณใดๆสิ้นสุดแล้ว ได้มีการให้ผลลัพธ์ออกมา และซีพียูก็จะทำงานอื่นต่อไปแล้ว แต่ผลลัพธ์ที่ได้นี้อาจจะต้องใช้เวลาอีกซักระยะยาวกว่าผู้ใช้จะมองเห็นผลลัพธ์ปรากฎบนกระดาษอย่างนี้ เป็นต้น

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

3.3 อัลกอริทึมของการจัดเวลา (Scheduling Algorithms)
อัลกอริทึมสำหรับการจัดการเวลาในโปรเซสนั้น มีความสำคัญอยู่ที่การตัดสินว่าจะให้โปรเซสใดครอบครองเวลาซีพียูก่อน ซึ่งต่อไปนี้ เราจะมาศึกษากันว่ามีวิธีการใดบ้างที่ใช้ในการตัดสินใจคัดเลือกโปรเซส

3.3.1 การจัดเวลาแบบมาก่อนได้ก่อน (FCFS : First-come-First-Served)
ตรอบจนทุกวันนี้มีวิธีการในการจัดการเวลาที่ง่ายที่สุดสำหรับการคัดเลือกโปรเซสให้ครอบครอง ซีพียู ก็คือ อัลกอริทึมที่ใช้แนวคิดของการมาก่อนได้ก่อน ซึ่งมีหลักการง่ายๆ ก็คือ โปรเซสใดที่ร้องขอให้ซีพียูก่อนก็จะได้รับการจัดสรรให้ครอบครองเวลาซีพียูไปก่อน ซึ่งการสร้างอัลกอริทึมนี้ทำขึ้นมานั้นได้ไม่ยาก เพราะสามรถนำเอาหลักการของคิวมาก่อนได้ก่อน มาใช้ได้เลย เมื่อมีโปรเซสใดโปรเซสเข้ามาอยู่ในคิวแบบนี้ PCB ของงานก็ถูกเชื่อมไว้กับหางคิวเมื่อใดที่ซีพียูว่างลง โปรเซสใด PCB อยู่ในหัวของมันคิวก็จะถูกนำออกมาจากคิวให้เข้าครอบครองเวลาซีพียูได้เลย

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

สสมติว่างานมาถึงคิวตามลำดับดังนี้คือ p1 , p2 และ p3 แถวคอยในระบบ FIFO ก็จะมีลักษณะดังนี้

เวลาในการคอย p1 ในที่นี้จะมีค่า 0 วินาที และขิง p2 คือ24 วินาทีและ p3 คือ27 วินาที ค่าเฉลี่ยของการคอยในสถานการณ์เช่นนี้ก็จะเท่ากับ (0+24+27) /3 หรือ 17 วินที แต่ถ้าสมมติว่าโปรเซสเข้ามาในคิว FIFO ตามลำดบัใหม่ เช่น p3 , p2 และ p1 คิวก็จะมีลักษณะที่ต่างออกไปดังนี้



จากสภาวการณ์สมมติที่สองนี้ เราก็จะได้ออกมาว่า เวลาคิวของ p3 เท่ากับ 0 วินาทีของ p2 เท่ากับ 3 วินาทีและของ p1 เท่ากับ 6 วินาที ซึ่งทำให้ค่าเฉลี่ยของการคอยมีค่าเท่ากับ (0+3+6) /3 =3 วินาทีเท่านั้น
จะเห็นได้ว่าถึงแม้จะมีโปรเซสเหมือนกันรอการเข้าครอบครองซีพียู แต่หากว่าลำดับการเข้าไปคิวมีความแตกต่างกันแล้ว ก็อาจจะทำให้ค่าเฉลี่ยของเวลาในการคอบมีความแตกต่างกันได้มาก นั้นก็คือเวลาของการคอยในแบบ FIFO นั้นยังคงไม่ดีพอ ถ้าหากว่าความต้องการใช้ซีพียูของแต่ละโปรเซสมีคาบเวลาที่แตกต่างกันมากดังตัวอย่างข้างต้น
จากตัวอย่างที่ผ่านมาเป็นเพียงตัวอย่างของโปรเซที่มีการขอเรียกในซีพียูครั้งเดียว สมมติว่า โปรเซสที่เข้ามีทั้งความต้องการซีพียู และ อินพุต/เอาต์พุต สลับกันไป โปรเซสที่ต้องการใช้ซีพียูในระบะเวลาสั้นๆ จะต้องเสียเวลาคอยโปรเซสที่ต้องใช้ซีพียู เป้นระยะเวลานานๆ ครั้งแล้วครั้งเล่า ถ้าหากมีการสลับกันระหว่างเวลาซีพียูและเวลาอินพุต/เอาต์พุต 100 ครั้ง ค่าเ)ลี่ยของเวลาในการคอบก็จะเป็นค่าเฉลี่ยที่นานที่สุด ตามตัวอย่างลำดับของโปรเซส p1 p2 p3 ดังกล่าว
ลักษณะการทำงานของการจัดเวลาซีพียูแบบมาก่อนได้ก่อนนี้ เป็นอัลกิริทึมแบบไม่ให้สิทธิ์ก่อน นั่นก็คือเมื่อโปรเซสใดครอบครองเวลาซีพียูแล้ว ซีพียูจะไม่มีโอกาสด้ว่าง จนกว่าความต้องการใช้ซีพียูของโปรเซสนั้นจะสิ้นสุดลงด้วยการสลับ ไปยังอินพุต/เอาต์พุต ซุ่งจะก่อให้เกิดปัญหาใหญ่ได้ ให้กับระบบคอมพิวเตอร์แบบแบ่งเวลาเพราะว่าผู้อิ่นๆ อาจจะต้องคอยเวลาให้โปรเซสตนเอง ซึ่งอาจจะแนโปรเซสที่สั้นๆ เสร็จพร้อมๆ กัน โปรเซสของผู้อื่นที่ใช้เวลายาวนานกว่ามากๆ เชื่อแน่ว่าผู้ใช้คอมพิวเตอร์ในระบบแบ่งเวลานี้คงไม่เห้นด้วยกับการทำงานในแบบนี้เป็นแน่

3.3.2 การจัดเวลาแบบงานสั้นทำก่อน (SJF : Short-Job-First-Scheduling)
จากการที่ได้พบเห็นปัญหาในหลักการของอัลกอริทึมมาก่อนได้ก่อน ทำให้มีการคิดค้นต่อไปว่าทำอย่างไรจึงจะเกิดความพอดีระหว่างโปรเซสที่ต้องการเวลาซีพียูสั้นๆ กับโปรเซสที่ต้องการซีพียูนานๆ ผลลัพธ์ก็คือ แนวความคิดที่จะทำให้โปรเซสที่ต้องการตาบเวลาของซีพียูในเวลาถัดไปสั้นที่สุด จะได้รับเลือกให้เข้ามาครอบครองซีพียูก่อน และถ้ามีโปรเซสหลายๆตัวที่มีคาบเวลาของซีพียูของช่วงเวลาช่าวงต่อไปเท่าๆกัน ก็จะใช้หลักการมาก่อนได้ก่อนมาใช้ในการคัดเลือก ซึ่งอาจมีชื่อเรียกการคัดงานแบบนี้ว่า สั้นที่สุดได้ใช้เวลาซีพียูไป เพราะแนวความคิดนี้จะมีการจัดคาบเวลาของซีพียูช่วงต่อไปเพียงช่วงเดียวมากกว่าการวัดรวมว่าตลอดทั้งโปรแกรมต้องการใช้ซีพียูนานเท่าไหร่ อย่างไรก็ตาม เราจะใช้ชื่อว่า SJF แทนเพื่อการอ้างอิงหลักการแบบนี้ต่อไป เนื่องจากว่า SJF เป็นชื่อที่เรียกใช้กันอย่างแพร่หลาย และใช้กันในหนังสือเล่มอื่นๆ อีกมากมาย

ทีนี้เรามาดูการทำงานของ SJF จากตัวอย่างดูบ้าง สมมติว่าเรามีโปรเซสที่มีเวลาซีพียูดังนี้


ถึงแม้ว่าลำกับการเข้ามาในคิวอาจจะเป็น p1 . p2 p3 และ p4 แต่การใช้หลักการของ SJF จะจัดคิวออกมาได้ในลักษณะแบบนี้



ค่าเฉลี่ยของการคอยของงานในระบบก็จะเท่ากับ (3+9+16)/4=7 วินาที ซึ่งถ้าหากว่าการใช้หลักการของมาก่อนได้ก่อน (FCFS) ค่าเฉลี่ยของการคอยก็จะเท่ากับ (6+14+21)/4 = 10.25 จะเห็นได้ว่ามีความแตกต่างกันถึง 3.25 วินาที
จากการทดลองพอว่า SJF จะให้ค่าเฉลี่ยของการคอยได้ต่ำที่สุด สำหรับชุดของโปรเซสใดๆ ก็ตามเพราะว่าการเลื่อนโปรเซสที่มีเวลาซีพียูน้อยสุดมาไว้หย้าคิว จะมีการลดเวลาการคอยโปรเซสทั่สั้นมากกว่าการเพิ่มเวลาของโปรเซสที่ยาวเสมอ ดังนั้นค่าเฉลี่ยของการคอยแบบนี้จึงต่ำสุด
สิ่งที่ยากมากสำหรับการใช้วิธี SJF ก็คือการวัดคาบเวลาของซีพียูถัดไปของแต่ละโปรเซสที่ร้องขอเวลาซีพียูเข้ามา ซึ่งในระบบการทำงานแบบแบ็ตซ์ เจ้าของโปรเซสจะต้องเป็นผู้บอกช่วงเวลาที่จำกัดของการใช้ซีพียู สำหรับโปรเซสให้กับระบบ เพื่อใช้เป็นข้อมูลอ้างอิงสำหรับการจัดการจัดลำดับดังกล่าว ซึ่งเจ้าของโปรเซสก็จะพยายามที่จะทำให้ค่าต่ำที่สุด เพื่อโอกาสในการเข้าไปใช้ซีพียูมาก่อนมากที่สุด แต่ถ้าคาบเวลาที่กำหนดไว้นี้มีค่าน่อยเกินไป ก็จะทำให้โปรแกรมนั้นไม่สามรถคำนวณสำเร็จได้ ซึ่งจะต้องเสียเวลามาเริ่มต้นกันใหม่อีก การจัดเวลาแบบ SJF นั้น เป็นวิธีการที่ใช้กันมากในระบบแบ็ตต์ หรือการจัดเวลาในช่วงยาว
อย่างไรก็ตาม ถึงแม้ว่า SJF จะมีข้อได้เปรียบในแง่ของค่าเฉลี่ยการคอย SJF ก็ยังคงมีปัญหาในการนำมาใช้การจัดเวลาช่าวงสั้น เพราะเราไม่สามารถรู้ได้ว่าความยาวของคาบเวลาการใช้ซีพียูในช่วงเวลาต่อไปของแต่ละโปรเซสเป็นเท่าใด วิธีการที่มักใช้เป้นแค่การประมาฯเอาเท่านั้น โดยปนะมาณเอาจากระบะเวลาของซีพียูในคาบเวลาที่ผ่านมาด้วยการหาค่าเฉลี่ย เป้นต้น
การประมาณค่าของคาบเวลาซีพียูมักจะหาค่าฉลี่ยแบบเอ็กโปเนนเชียล สมมติว่า Tn เป็นคาบเวลาของ nth เวลาที่ใช้ซีพียูและ tn+1 คือค่าประมาณสำหรับเวลาซีพียูคาบต่อไป และให้0 < α <1

จากสูตรดังกล่าวเป็นการห่าค่าเฉลี่ยแบบเอ็กโปเนนเชียล ระหว่างคาบเวลาในอดีต tn และคาบเวลาจริงที่เพิ่มจะผ่านไป Tn โดยมี α เป็นพารามิเตอร์ในการควบคุมความสำคัญของเวลาในอดีตและปัจจุบัน ซึ่งถ้า α = 1 ก็หมายความว่คาบเวลาที่เพิ่งผ่านไปมีความสำคัญที่สุด โดยไม่คำนึงถึงคาบเวลาช่วงอื่นๆ ในอดีตเลย แต่ถ้า α = 0 ก็หมายความว่า คาบเวลาในอดีตมีความสำคัญสูงสุด ซึ่งในความเป็นจริงแล้ว α = 0.5 เป็นค่าที่นิยมใช้กันมาก เพราะว่าข้อมูลในอดีตและปัจจุบันมีความสำคัญเท่ากัน ค่าเริ่มต้น t0 อาจกำหนดไว้ตายตัวที่ค่าใดค่าหนึ่ง อาจได้มาจากค่าเฉลี่ยของการทำงานที่ผ่านๆ มาก็ได้ รูป 3.3 แสดงให้เห็นว่า การทำงานคาบเวลาซีพียูนั้นมีลักษณะอย่างไร



รูป 3.3 ค่าจากการทำนายความยาวของเวลาซีพียู

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

ต่อไปนี้จะยกตัวอย่างเพื่อความเข้าใจในเรื่อง SJF แบบให้สิทธิ์ก่อน โดยสมมติให้มีโปรเซสที่จะเข้ามาในระบบ 4 โปรเซสดังนี้



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



อธิบายได้ว่า เมื่อโปรเซส P1 เข้ามาถึงเวลา 0 วินาที โปรเซส p1 ก็จะได้เข้าไปใช้ซีพียูทันทีเนื่องจากว่ายังไม่มีโปรเซสอื่นเข้ามา เมื่อถึงเวลาที่ 1 วินาที งาน p2 ซึ่งมีคาบเวลาซีพียูสั้นกว่า4วินาที
เมื่อเทียบ p1 ซึ่งยังเหลืออีก 7 วินาที ดังนั้นงาน p1 จึงถูกหยุดไว้ก่อนเพื่อ p2 จะได้เข้าไปใช้ซีพียู และเนื่องจากคาบเวลาความต้องการใช้ซีพียูของ p1 ยังเหลือมากกว่า p4 แต่น้อยกว่า p3 การจัดลำดับการเข้าใช้ซีพียู จึงออกมาตามรูปที่แสดงข้างต้น โดยถ้าให้ p2 แทรก p1 กลางคัน เวลารอคอยเฉลี่ยจะเท่ากับ ((10-1)+(1-1)+(17-2)+(5-3))/ 4 = 26/4 = 6.5 แต่ห้ามแทรกการคัน เวลารอคอยเฉลี่ยจะเท่ากับ ((0)+(8-1)+(17-2)+(12-3))/4 = 31/4 = 7.75 วินาที


3.3.3 การจัดเวลาตามลำดับความสำคัญ (Priority Scheduling)
วิธีการของอัลกอริทึมSJF สามารถมองได้อีกแง่หนึ่งว่าเป็นการจัดเวลาตามลำดับความสำคัญชนิดหนึ่งลำดับความสำคัญของแต่ละโปรเซสจะถูกกำหนดไว้โดยวิธีใดวิธีหนึ่ง เพื่อว่าการใช้ซีพียูจะมีการใช้โปรเซสที่มีลำดับความสำคัญที่สูงสุดเท่านั้น แต่ถ้ามีงานที่ลำดับความสำคัญเท่ากัน จะมีการนำมาก่อนได้ก่อนมาใช้
ในที่นี้วิธีการของ SJF ได้มีการกำหนดลำดับความสำคัญของโปรเซสด้วยคาบระยะเวลาของความต้องการใช้ซีพียูหรือเวลาการใช้ซีพียูของแต่ละโปรเซสเช่นโปรเซสใดมีคาบเวลาสั้นที่สุดก็จะมีลำดับความสำคัญมากที่สุด ทีนี้เมื่อเราพูดถึงความมากน้อยของลำดับความสำคัญ มันก็จะมีความจำเป็นที่จะต้องกำกับไว้ด้วยสัญลักษณ์ที่เปรียบเทียบกันได้เช่น ตัวเลขจำนวนนับ เป็นต้น แต่จะกำหนดให้มีกี่ลำดบัก็สุดแล้วแต่ผู้ออกแบบ อาจจะเป็น 0-9 หรือ 0-6789 ก็ได้และก็ไม่มีกฏตายตัวว่าเลขมากหรือน้อยจะมีความหมายในเรื่องของลำดับความสำคัญอย่างไร ซึ่งการไม่มีข้อตกลงในการใช้ระบบการกำกับของความสำคัญเหล่านี้ อาจก่อให้เกิดความสับสนขึ้นได้ ดังนั้นในหนังสือเล่มนี้จะมีการกำหนดว่าตัวเลขน้อยมีลำดับความสำคัญมาก เพื่อเป็นที่เข้าใจร่วมกัน
ตัวอย่างต่อไปนี้เป็นการแสดงถึงการจัดเวลาซีพียู แบบใช้ตัวเลขเป็นตัวบอกความสำคัญโดยมีตัวอย่างโปรเซส5 ตัวอย่างดังนี้



ถ้าเราใช้การจัดเวลาแบบการใช้ลำดับความสำคัญ เราจะสามารถจัดลำดับของโปรเซสให้เข้าไปทำงานในซีพียูได้ดังนี้

a>

ซึ่งค่าฉลี่ยของการคอยในคิวของแต่ละโปรเซสมีค่าเท่ากับ (1+6+16+18)/5 = 8.2 วินาที
การกำหนดลำดับความสำคัญของแต่ละโปรเซสสามารถกำหนดได้ภายใน และ ภายนอก การกำหนด ภายในคือ การกำหนดลำดับความสำคัญด้วยวิธีการใดหารหนึ่งจากการวัดและคำนวณคุณสมบัติบางอย่างของแต่ละโปรเซสที่สามารถวัดค่าได้ คุณสมบัติที่วัดค่าได้เหล่านี้เช่น เวลาของการกำจัดการใช้ซีพียู ความต้องการขนาดของหน่วยความจำ จำนวนไฟล์ที่ต้องเกี่ยวข้องหรือแม้แต่อัตราส่วนของจำนวนเวลา อินพุต/เอาต์พุตต่อเวลาซีพียูเป็นต้น ส่วนการกำหนดจากภายนอก หมายถึงการกำหนดลำดับความสำคัญของโปรเซสใดๆ จากวิธีการอื่นๆ นอกเหลือจากระบบปฏิบัติการ ตัวอย่างเช่น ราคาค่าเช่าเวลาซีพียู แหล่งที่มาของโปรเซส หรือความเร่งด่วนของโปรเซส เหล่านี้ล้วนสามารถนำมาเป็นตัวใช้สำหรับคำนวณค่าลำดับความสำคัญของโปรเซสก่อนที่ระบบปฏิบัติการจะรับเอาโปรเซสเข้ามานั่นเอง
การจัดเวลาแบบมีลำดับความสำคัญสามารถเป็นได้ทั้งแบบให้สิทธิ์ก่อนหรือไม่ให้สิทธิ์ก่อนก็ได้ โดยมีลักษณะการทำงานเหมือนกับ SJF ดังกล่าวมาแล้วทุกประการ
ปัญหาใหญ่ของการจัดการเวลาซีพียู โดยใช้ลำดับความสำคัญของโปรเซสมาเกี่ยวข้องก็คือโปรเซสที่มีลำดับความสำคัญต่ำอาจจะไม่มีโอกาสได้เข้าไปใช้ซีพียูเลย ถ้าหากว่าโปรเซสที่มีลำดับความสำคัญสูงกว่าอยู่เป็นจำนวนมาก ซึ่งโดยปกติแล้วโปรเซสที่มีลำดับความสำคัญสูงต่ำเหล่านี้ กว่าจะได้รับซีพียูมาทำงานก็อาจจะเป็นตีสองวันอาทิตย์หรือไม่ก็ถูกยกเลิกไปในที่สุด เพราะระบบคอมพิวเตอร์มีการตัดสินขัดและต้องเริ่มเปิดเครื่องกันใหม่

การแก้ปัญหาให้กับสถานการณ์ที่มีโปรเซสลงเหลือ เนื่องจากมีลำดับความสำคัญต่ำก็คือ การเพิ่มลำดับความสำคัญให้กับโปรเซสที่ยังไม่เสร็จเหล่านี้ตามระยะเวลาที่คอยอยู่ในคิว ตัวอย่างเช่น สมมคิว่าเรามีการออกแบบให้มีลำดับความสำคัญจาก 0-127 ขั้น เราอาจจะเพิ่มอัลกอริทึมพิเศษลงไปว่า ถ้าโปรเซสใดคอยการใช้ซีพียูครบ 15 นาที ก็ให้ลดตัวเลขลำดับขั้นลงทีละขั้น และจะลดลงเรื่อยๆ ทุก 15 นาที ซึ่งการกระทำแบบนี้ แม้โปรเซสที่เข้ามาในระบบมีลำดับความสำคัญต่ำสุด ที่ 127 ก็จะมีโอกาส เข้าไปในซีพียูภานในเวลาไม่เกิน 32 ชม. เพราะในที่สุดโปรเซสนี้ก็จะมีความสำคัญเท่ากับ 0
3.3.4 การจัดเวลาแบบวนรอบ (RR : Round-Robin Scheduling)

การจัดเวลาแบบวนรอบ (RR : Round-Robin Scheduling) เป็นวิธีการที่คิดขึ้นมาเพื่อใช้กับระบบคอมพิวเตอร์แบบแบ่งเวลาโดยเฉพาะ โดยมีลักษณะการทำงานแบบมาก่อนได้ก่อน(FCFS)แต่ให้มีกรรมวิธีของสิทธิ์ก่อนรวมอยู่ด้วย แต่ละโปรเซสที่เข้ามาในระบบจะถูกกำจัดเวลาการเข้าไปใช้ซีพียูเท่าๆกัน ซึ้งช่วงเวลานี้จะเป็นช่วงเวลาสั้นๆ เรียกว่า เวลาควันตัม (Quantum Time) หรือช่วงเวลา (Time Slice) ระยะเวลาควันตัมนี้ มีความยาวระหว่าง 10 ถึง 100 มิลลิวินาที และคิวที่ใช้ก็เป็นแบบวงกลม (Circular Queue) ตัวจัดเวลาจะมีการให้ซีพียูกับโปรเซสเซอร์ที่อยู่ในคิวแบบวนไปรอบๆ ในแต่ละคาบเวลาที่ให้นั้น โดยจะมีความยาวนานของการได้รับซีพียูมากที่สุดคือ 1 ควันตัม ถ้าโปรเซสไม่สามารถกระทำได้สำเร็จภายใน 1 ควันตัมนี้ โปรเซสจะต้องถูกกลับไปไว้คิวเช่นเดิม สถานภาพต่าง ๆ ของโปรเซสที่ยังทำไม่เสร็จก็จะถูกบันทึกไว้ เพื่อว่าเมื่อถึงโอกาสได้ครอบครองซีพียูอีก ก็จะได้เริ่มต้นรันต่อจากครั้งที่แล้วโดยไม่ต้องเริ่มใหม่ทั้งหมด
การสร้างระบบการทำงานแบบวนรอบ เราจะทำคิวที่พร้อมทำงาน(Ready Queue)เป็นแบบมาก่อนได้ก่อนไว้สำหรับเก็บโปรเซสต่างๆ โปรเซสที่เข้ามาใหม่จะถูกนำมาต่อไว้ที่หางของคิว ตัวจัดเวลาจะเลือกเอาโปรเซสที่อยู่ตรงหัวคิวออกมา แล้วกำหนดให้ไทม์เมอร์หยุดการให้เวลาซีพียูหลังจากนั้น 1 ควันตัม แล้วนำโปรเซสออกไปต่อที่หางคิว ถ้าหากว่าโปรแกรมยังไม่สิ้นสุดการทำงาน
โปรเซสบางโปรเซสอาจต้องการใช้ซีพียูน้อยกว่า 1 ควันตัม ในกรณีนี้โปรเซสที่เสร็จก่อนถึงเวลา 1 ควันตัม จะต้องให้ออกจากการครอบครองซีพียู เพื่อให้โปรเซสอื่นที่อยู่ตรงหัวคิวเข้ามาทำงานได้
เวลาเฉลี่ยของการคอยในกรรมวิธีของวนรอบจะค่อนข้างนาน ให้ลองพิจารณาตัวอย่างของการเอ็กซิคิวต์โปรเซส 3 โปรเซสดังต่อไปในแบบวนรอบ โดยที่โปรเซสทั้ง 3 เข้ามาถึงระบบพร้อมๆ กัน



สมมุติว่า เราใช้ควันตัมเท่ากับ 4 วินาที โปรเซส P1 ครอบซีพียูในครั้งแรก 4 วินาที แต่เวลาที่ต้องการจริงคือ 24 วินาที ดังนั้นโปรเซส P1 จึงเหลือเวลาที่ต้องการอีก 20 วินาที แต่เมื่อเวลาควันตัมแรกหมดลงที่วินาที
ที่ 4 โปรเซส P1 ก็จะออกจากการครอบครองซีพียู โปรเซส P2 ซึ่งเป็นโปรเซสที่อยู่ถัดไปในคิว ก็จะได้ครอบครองซีพียู แต่โปรเซส P2 ต้องการครอบครองซีพียูแค่ 3 วินาที ดังนั้นโปรเซส P2 จึงทำเสร็จก่อนที่เวลา
ของควันตัมจะหมดลง โปรเซส P3 ที่คอยอยู่ถัดไปจึงได้เข้าครอบครองซีพียู ที่เวลา 7 วินาที ผลของการทำงานแบบควันตัมต่อโปรเซสดังกล่าวสามารถแสดงได้ดังนี้


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

ถ้ามีโปรเซสอยู่ในคิวจำนวน n โปรเซส และระยะเวลาของควันตัมเท่ากับ q หน่วย แต่ละโปรเซสที่
อยู่ในคิวจะมีเวลาเฉลี่ยของการคอยไม่นานไปกว่า (n-1) x q หน่วย ก่อนที่จะได้รับการเข้าไปใช้ซีพียูอีกครั้ง
ตัวอย่างเช่น ถ้ามีโปรเซส 5 โปรเซส และระยะของควันตัมคือ 20 วินาที แต่ละโปรเซสจะต้องคอยในคิวโดย
เฉลี่ยประมาณไม่เกิน 80 วินาที ที่บอกว่าไม่เกินก็เพราะว่าการคอยอาจจะน้อยกว่านี้ ถ้าหากว่ามีโปรเซสใดๆ
สามารถทำงานเสร็จโดยใช้เวลาน้อยกว่าเวลาควันตัมนั่นเอง

ประสิทธิภาพของการวนรอบขึ้นอยู่กับการกำหนดขนาดของควันตัมเป็นอย่างยิ่ง ถ้าขนาดของควันตัม
ใหญ่หรือนานเกินไป ประสิทธิภาพของการวนรอบก็จะใกล้เคียงกับแบบมาก่อนได้ก่อน แต่ถ้าขนาดของควันตัม เล็กมากเกินไป ทรูพุต (throughput) ของระบบก็จะช้าลง เนื่องจากการนำเอาโปรเซสเข้าและออก
จากการครอบครองซีพียูจะต้องเสียเวลาบางส่วนในการทำ Dispatcher ซึ่งถ้าขนาดของควันตัมเล็กใกล้เคียงกับเวลาของ Dispatcher เวลาของระบบรวมก็จะหมดไปกับการเอาโปรเซสเข้าและออก (Context Switch)นั่นเอง
ในการทำระบบปฏิบัติการแบบการวนรอบนั้น การกำหนดขนาดของควันตัม เป็นเรื่องที่ติ้งทำกันอย่างพิถีพิถัน ซึ่งอาจจะต้องมีการทดลองใช้ขนาดขงควันหลายๆ ขนาดกับระบบที่ใช้จริง เนื่องจากความเร็วของซีพียู
และอุปกรณ์ต่างๆ ที่เกี่ยวข้องกับการทำ Context Switch มีความเร็วไม่เท่ากันในแต่ละคอมพิวเตอร์ส่วนใหญ่แล้วขนาดของควันตัมมักจะมีขนาดที่ใหญ่กว่าเวลาของ Context Switch พอสมควร เช่น ประมาณ 10 เท่า
เป็นต้น ซึ่งหมายความว่าถ้าเวลาของ Context Switch ที่ต้องใช้คือ 1 วินาที ขนาดของควันตัมควรจะเป็นที่
ประมาณ 10 วินาที เป็นต้น แต่นั่นไม่ใช่เป็นสูตรตายตัวสำหรับระบบงานคอมพิวเตอร์ทุกๆ เครื่อง การกำหนด
ขนาดที่เหมาะสมยังต้องคำนึงถึงลักษณะโปรเซส ความเร็วซีพียู และต้องการในลักษณะการตอบสนองของคอมพิวเตอร์ในสภาวการณ์ต่างๆ ประกอบกันด้วย

ในการวนรอบ (turnaround time) ก็เป็นอีกส่วนหนึ่งที่จะมีผลกระทบจากขนาดของควันตัม
จากตัวอย่างในรูปที่ 3.4 ด้านล่างนี้จะเห็นว่าเวลาในการวนรอบไม่จำเป็นที่จะต้องดีขึ้นจากการที่ขนาดของ
ควันตัมที่เพิ่มขึ้นเสมอไป ในทางปฏิบัติทั่วๆ ไปแล้ว ค่าเฉลี่ยนของเวลาในการวนรอบจะดีขึ้นถ้างานแต่ละงานสามารถทำเสร็จได้ภายในระยะเวลาของ 1 ควันตัม



รูป 3.4 แสดงเวลาวนรอบที่เปลี่ยนไปตามเวลาควันตัม [OSC6:P165]
จากตัวอย่างข้างต้น เรายังไม่มีการคิดเวลาของคอนเท็กซ์สวิตซ์ที่ต้องเสียไป เพราะถ้ามีการรวมเวลาของ
คอนเท็กซ์สวิตซ์แล้ว การลดขนาดของควันตัมในระดับหนึ่งก็จะทำให้เวลาในการวนรอบเพิ่มขึ้นได้เป็นอย่างมาก
แต่ถ้าขนาดของควันตัมใหญ่เกินไป ก็จะเป็นการทำงานคล้ายๆ มาก่อนได้ก่อนนั่นเอง ในทางปฏิบัติแล้ว ถ้าเราพอ
จะรู้ว่าแต่ละงานจะใช้เวลาซีพียูงานละเท่าใด เราก็จะสามารถกำหนดเวลาของควันตัมไว้ที่ประมาณ 80 % ของเวลาซีพียู

3.3.5 การจัดเวลาแบบคิวหลายระดับ (Multilevel Queue Scheduling)
เป็นการจัดเวลาของการนำโปรเซสเข้ามาครอบครองซีพียูอีกแบบหนึ่ง สำหรับระบบที่สามารถ
แบ่งระดับชั้นของงานได้อย่างชัดเจน เช่น งานที่เป็นฟอร์กราวนด์ (Foreground) หรืออินเตอร์แอ็กทีฟ
(Interactive) กับงานที่เป็นแบ็คกราวนด์ (Background) หรือแบ็ตซ์ (Batch) ซึ่งงานทั้งสองแบบนี้
ต้องการเวลาตอบสนอง (Response time) ที่แตกต่างกัน ซึ่งสามารถใช้ระบบการจัดเวลาที่แตกต่างกันได้
โดยทั่วไปแล้วงานที่เป็นฟอร์กราวนด์จะมีระดับชั้นความสำคัญเหนือกว่างานที่เป็นแบ็คกราวนด์
การจัดเวลาแบบคิวหลายระดับนี้จะใช้วิธีแบ่งคิวออกเป็นหลายๆ ระดับหมายถึงระดับโปรเซสที่มี
ความสำคัญแตกต่างกัน ซึ่งการแบ่งระดับความสำคัญของโปรเซสนั้น สามารถแบ่งได้หลายลักษณะไม่ว่าจะ
แบ่งตามขนาดของโปรเซสจำนวนหน่วยความจำที่ต้องใช้หรือจำนวนอินพุต/เอาต์พุต เป็นต้น
โดยที่แต่ละคิว ยังสามารถใช้หลักการของการจัดเวลาที่แตกต่างกันได้ด้วย เช่น งานที่เป็นฟอร์กราวนด์ก็อาจ
ใช้การจัดตารางแบบการวนรอบ(RR)ส่วนงานที่เป็นแบบแบ็คกราวนด์ก็อาจใช้วิธีการจัดตารางเวลาแบบมา
ก่อนได้ก่อน (FCFS) นอกจากนี้ยังมีการเพิ่มการจัดเวลาระหว่างคิวอีกด้วย ซึ่งอาจเป็นได้ทั้งแบบการจัด
ลำดับความสำคัญแบบคงที่ (fixed-priority preemptive scheduling) หรือ การจัดลำดับความ
สำคัญแบบเปลี่ยนแปลงได้ (variable-priority preemptive scheduling) ก็ได้ ซึ่งในแบบหลังนี้
โปรเซสอาจมีการปรับตัวเองในเรื่องของระดับความสำคัญด้วยการเลื่อนไปมาระหว่างคิวได้ ดังกล่าวในย่อ
หน้าถัดไป
ตัวอย่างลักษณะของการจัดลำดับความสำคัญแบบคงที่ที่มีคิว 5 คิวคือ
1. system process queue
2. interactive process queue
3. interactive editing process queue
4. batch 14 process queue
5. student process queue
ตามรูป 3.5 ดังนี้
ระดับความสำคัญสูงสุด (Highest priority)

ระดับความสำคัญต่ำสุด (Lowest priority)

รูป 3. 5 การจัดเวลาแบบคิวหลายระดับ [OSC6:P166]

แต่ละคิวจะมีความสำคัญเหนือกว่าคิวที่อยู่ด้านล่างถัดลงไปเสมอ นั่นก็คือโปรเซสที่คอยอยู่ในคิวที่มีความสำคัญต่ำจะมีโอกาสได้ออกมาใช้ซีพียูก็ต่อเมื่อคิวที่มีความสำคัญสูงกว่าไม่มีโปรเซสที่ต้องทำเหลืออยู่เท่านั้น หรือทำในขณะที่โปรเซสที่มีลำดับความสำคัญกำลังครอบครองซีพียู แล้วมีโปรเซสที่มีลำดับความสำคัญ
สูงกว่าเข้ามาคอยอยู่ในคิวที่สูงกว่า โปรเซสนี้ก็จะถูกนำออกมาจากซีพียูทันที
อย่างไรก็ตามเพื่อป้องกันไม่ให้โปรเซสที่อยู่ในคิวต่ำ ต้องคอยอยู่นานเกินไป หรืออาจจะไม่มีโอกาส
เข้าได้ไปใช้ซีพียูเลย เพราะว่าในคิวบน ๆ ไม่เคยว่างเลย ก็อาจจะต้องมีการกำหนดสัดส่วนเวลาให้กับแต่ละคิว
ในการทำงานเข้าไปในซีพียู เช่น การกำหนดให้เวลา 80 เปอร์เซ็นต์เป็นของโปรเซสที่ฟอร์กราวนด์ และอีก
20 เปอร์เซ็นต์เป็นของงานแบ็คกราวนด์เป็นต้น
ส่วนการทำงานแบบการจัดลำดับความสำคัญแบบเปลี่ยนแปลงได้นั้น อาจมีชื่อเรียกอีกอย่างได้ว่า
เป็นการทำงานแบบ Multilevel Feedback Queue Scheduling เพราะว่าโปรเซสในแต่ละคิวสามารถ
มีการเลื่อนชั้นระดับความสำคัญขึ้นหรือลงได้ ซึ่งเมื่อเปรียบเทียบกับแบบการจัดลำดับความสำคัญแบบคงที่แล้ว
อาจจะต้องเสียเวลาเพิ่มอีกนิดหน่อยในการคำนวณหาระดับความสำคัญใหม่ให้กับโปรเซส ซึ่งส่วนมาแล้วจะแบ่ง
ระดับความสำคัญตามระยะเวลาของซีพียู เช่น ทำงานได้ดี เวลาที่ซีพียูนานขึ้นก็อาจจะถูกลดชั้นลงมาสู่คิวที่มี
ลำดับความสำคัญต่ำได้ ซึ่งจะทำให้โปรเซสที่มีการใช้ซีพียูน้อยแต่มีอินพุต/เอาต์พุต หรืออินเทอร์แอ็กทีฟมาก ๆ
มีโอกาสเข้าไปอยู่ในคิวที่มรความสำคัญมากได้ วิธีนี้ยังเป็นการป้องกันไม่ให้มีโปรเซสที่มีความสำคัญน้อยถูกดองอยู่ในคิว เพราะโปรเซสที่อยู่ในคิวที่ต่ำก็สามารถเลื่อนขึ้นไปสู่คิวที่สูงขึ้นถ้าคอยอยู่นานเกินไป
จะพิจารณาตัวอย่างของ Multilevel Feedback Queue ดังรูป 3.6



มาก่อนได้ก่อน(FCFS)

รูป 3.6 Multilevel Feedback Queue [OSC6:P168]

เมื่อมีโปรเซสแรกเข้ามาในคิวแรก มันก็จะได้โอกาสเข้าไปครอบครองซีพียู ภายใต้การกำหนดขนาดของควันตัม 8 วินาที ซึ่งถ้ามันไม่สามารถเสร็จได้ภายในควันตัมที่กำหนดนี้ มันก็จะถูกลดชั้นลงไปอยู่ในคิวที่สองที่มีการกำหนดขนาดของควันตัมไว้ 16 วินาที และถ้าเมื่อไหร่คิวแรกไม่มีโปรเซสอยู่ โปรเซสที่อยู่ในคิวที่มีการกำหนดขนาดควันตัมไว้ 16 วินาที ก็จะมีโอกาสได้ไปครอบครองซีพียู และถ้าโปรเซสนี้ยังไม่เสร็จใน 16 วินาทีนี้
มันก็จะถูกลดชั้นลงมาอยู่ในคิวแบบมาก่อนได้ก่อน ซึ่งจะได้โอกาสครอบครองซีพียูก็ต่อเมื่อคิวควันตัมขนาด
8 วินาที และ 16 วินาทีว่างเท่านั้น อย่างไรก็ตามถ้ามีโปรเซสที่ถูกแช่อยู่ในคิวมาก่อนได้ก่อน (FCFS) นานเกินไป โปรเซสเหล่านี้ก็อาจมีโอกาสที่จะถูกนำกลับขึ้นไปยังคิวด้านบนได้เช่นกัน
หลักการทำงานแบบนี้จะให้ความสำคัญกับโปรเซสใดๆ ก็ตามที่มีเวลาซีพียูที่น้อยกว่าหรือเท่ากับ
8 วินาทีส่วนงานที่มีเวลาซีพียูมากกว่า 8 วินาที แต่น้อยกว่าหรือเท่ากับ 24 วินาทีมันก็จะตกลงมาอยู่ในคิว
มาก่อนได้ก่อน (FCFS)
สิ่งสำคัญที่ต้องคำนึงถึงเมื่อต้องการที่จะออกแบบการจัดเวลาแบบนี้ มีดังนี้คือ
1. จำนวนของคิว
2. วิธีของการจัดเวลาของแต่ละคิว
3. หลักเกณฑ์ในการตัดสินใจเพิ่มความสำคัญของโปรเซส
4. หลักเกณฑ์ในการตัดสินใจลดความสำคัญของโปรเซส
5. หลักเกณฑ์ในการตัดสินใจนำเอาโปรเซสที่ต้องการครอบครองซีพียูมาเข้าในคิว
การทำงานของ Multilevel Feedback Queue ดังกล่าวข้างต้นทำให้มันเป็นระบบการจัดเวลากันอย่างแพร่หลาย เพราะสามรถปรับเปลี่ยนสัดส่วนต่างๆ ให้เหมาะสมได้ง่ายกับระบบคอมพิวเตอร์ที่มันจะต้องทำการควบคุม แต่การที่มันมีค่าที่ต้องปรับเปลี่ยนเป็นจำนวนมากตามที่กล่าวมาทั้ง 5 ข้อข้างต้นนั้น ก็ทำให้การตัดสินใจหาค่าที่เหมาะสมเป็นสิ่งที่กระทำได้ไม่ง่ายนัก เนื่องจากเป็นการปรับแต่งที่ซับซ้อนมาก

3.4 การจัดเวลาของมัลติเพิลโปรเซสเซอร์ (Multiple-Processor Scheduling)
ที่ผ่านมาได้มีการกล่าวถึงการจัดการเวลาสำหรับระบบคอมพิวเตอร์ที่มีซีพียูเพียงตัวเดียว แต่ถ้าจะต้องออกแบบระบบปฏิบัติการสำหรับคอมพิวเตอร์ที่มีซีพีอยู่หลายตัว การออกแบบต่าง ๆ ก็จะยิ่งเพิ่มความ
ซับซ้อนขึ้นไปอีกมากจากในอดีตถึงปัจจุบันก็ได้มีการทดลองวิธีการจัดเวลาหลายๆ แบบที่พอจะเป็นไปได้แต่ก็ยังไม่สามารถสรุปได้ว่าวิธีไหนเป็นวิธีที่ดีที่สุด ซึ่งก็ไม่แตกต่างไปจากการหาวิธีที่ดีที่สุดสำหรับจัดการกับระบบที่มี
ซีพียูเพียงตัวเดียวเลยดังนั้นในย่อหน้าต่อไป เราก็จะมาศึกษากันถึงวิธีการเป็นบางส่วนที่เป็นไปได้และใช้กันอย่าง
แพร่หลาย ในระบบที่มีซีพียูหลายตัวกัน และเราก็จะจำกัดปัญหาของเราอยู่เพียงแค่ว่าซีพียูที่มีหลายตัวนี้เป็นซีพียู
ที่มีลักษณะการทำงานเหมือนกันทุกประการ ซึ่งสำหรับระบบที่มีซีพียูที่แตกต่างกันนั้น ก็จะมีการกล่าวถึงในบทต่อไป
สิ่งที่ควนคำนึงเป็นอันดับแรกก็คือการแชร์โหลดให้กับซีพียู (Load Sharing)เพื่อให้ซีพียูแต่ละตัวมีงานทำมากพอๆกันซึ่งวิธีการง่ายๆ ก็คือการจัดให้ระบบคิวมีเพียงระบบเดียว ไม่ว่าจะมีซีพียูกี่ตัวก็ตามวิธีนี้จะมีการนำโปรเซสออกจากคิว เพื่อไปใช้งานซีพียูทันทีที่มีซีพียูตัวใดตัวหนึ่งว่างงาน และพบว่าในคิวยังมีโปรเซสรออยู่
การทำงานในลักษณะที่มีซีพียูหลายตัวต่างก็มีระบบการจัดการเวลาของตัวเอง จะต้องมีการออกแบบอย่างระมัดระวังในเรื่องของการที่โปรเซสแต่ละโปรเซสอาจจะต้องการใช้ข้อมูลในฐานข้อมูลในเวลาเดียวกัน
รวมทั้งต้องระวังไม่ให้ซีพียูที่ว่างงานพร้อมกัน เลือกเอาโปรเซสจากคิวใช้ร่วมกันอยู่พร้อมกัน ซึ้งอาจจะทำให้มีการดึงเอาโปรเซสเดียวกันเข้าไปทำก็ได้ การแก้ปัญหาด้วยการปล่อยงานที่ดึงออกจากคิวพร้อมกับซีพียูตัวอื่นๆทิ้งไปก็ยังสามารถก่อปัญหาในเรื่องที่โปรเซสถูกปล่อยทิ้งออกจากซีพียูพร้อมๆ กันหมด ซึ่งอาจทำให้โปรเซสนั้นหายไปจากระบบเลยก็ได้
การแก้ปัญหาดังกล่าวจึงหนีไม่พ้นที่จะต้องเพิ่มความซับซ้อนเข้าไปในระบบอีกจนได้ เช่น การทำให้มีระดับของซีพียูที่แตกต่างกัน ถึงแม้ว่าจะเป็นซีพียูที่เหมือนกันก็ตาม วิธีการคือการให้ซีพียูตัวใดตัวหนึ่งเป็นตัวควบคุมสั่งการต่อซีพียูอีกตัวหนึ่งถัดไปอีก 1 ตัว และตัวถัดไปก็ควบคุมต่อไปเรื่อยๆ เพื่อไม่ให้มีการเข้าไปถึงโปรเซสจากคิวพร้อมๆ กัน โดยการจัดระบบซีพียูลักษณะนี้จะมีชื่อเรียกว่า Master-slave structure
ในระบบคอมพิวเตอร์บางระบบที่มีการพัฒนาเพื่อให้ได้ประสิทธิภาพสูงสุด ได้มีการใช้ซีพียู แยกต่างหากระหว่างงานภายในของระบบ เช่น พวกการจัดเวลาและการจัดการระบบอื่นๆ ออกจากพวกงานอินพุต/เอาต์พุตทั้งหลาย และกับงานที่เป็นของผู้ใช้ซึ่งการทำงานแยกกันของซีพียูแบบนี้ ทำให้การออกแบบระบบปฏิบัติการ เพราะว่าซีพียูตัวอื่นๆ ไม่ว่าจะมีกี่ตัวก็ตาม จะเข้าถึงได้เฉพาะข้อมูลของผู้ใช้ภายนอกเท่านั้น

3.5 การจัดเวลาแบบเรียลไทม์ (Real – Time Scheduling)
ในบทแรกๆ เราได้มีการพูดถึงระบบปฏิบัติการแบบเรียลไทม์ ว่ามันจะเป็นแนวความคิดของระบบคอมพิวเตอร์ที่มีความต้องการสูง ดังนั้นในย่อหน้านี้เราก็จะมาพูดถึงว่า ระบบการจัดเวลาแบบไหนที่สมควรเลือกใช้ในระบบปฏิบัติการแบบเรียลไทม์นี้
การทำงานแบบเรียลไทม์นั้นแบ่งออกเป็นสองประเภทคือ
• Hard Real-time
• Soft Real-time

Hard real-time คือระบบที่สามารถทำงานใดงานหนึ่งให้เสร็จตามเวลาที่กำหนดได้ ซึ่งงานที่จะรับเข้ามาแต่ละงานนั้นจะมีความต้องการของเวลาที่ต้องการให้เสร็จมาด้วย ดังนั้นตัวจัดเวลาจะต้องเป็นตัดสินใจว่าจะรับงานเข้ามาทำหรือไม่ ซึ่งถ้าหากว่าตัดสินใจรับงานใดๆ เข้ามาทำก็หมายความว่า งานนั้นได้รับการรับรองว่าจะถูกทำให้เสร็จได้ภายในเวลาที่กำหนดมา ซึ่งงานที่ถูกปฏิเสธก็หมายความว่า เวลาที่กำหนดมานั้นเร็วเกินกว่าที่สภาวะของระบบในขณะนั้นจะทำได้ทัน ซึ่งการที่จะสามารถตัดสินใจแบบนี้ได้นั้น ระบบปฏิบัติการจะต้องรู้แน่นอนว่าการทำงานของฟังชันก์ต่างๆของตัวระบบปฏิบัติการใช้เวลาเท่าใดแต่จะเป็นการยากมากถ้าหากระบบคอมพิวเตอร์มีการใช้ สื่อจัดเก็บข้อมูล หรือหน่วยความจำเสมือน ซึ่งจะได้กล่าวในบทต่อไปว่าทำไมจึงไม่สามารถกำหนดเวลาการใช้หน่วยความจำสำรองเหล่านี้ได้แน่นอน ดังนั้นระบบ Hard Real-time มักจะทำงานกับโปรแกรมเฉพาะที่ได้รับการใช้ฮาร์ดแวร์ของระบบทั้งหมด เพื่อทำงานหรือคำนวณให้กับงานใดงานหนึ่งอย่างเฉพาะเจาะจง ทำให้ระบบนี้จึงประกอบไปด้วยสิ่งที่จำเป็นในการทำงานที่ได้รับมอบหมายเท่านั้น ซึ่งอาจจะมีฟังก์ชันการทำงานในส่วนต่างๆ ไม่ครบถ้วนเหมือนกับระบบคอมพิวเตอร์ที่สร้างขึ้นมาให้สามารถรับงานหลายๆงานที่แตกต่างกัน
Soft Real-time คือระบบที่ข้อจำกัดต่างๆ ไม่เข้มงวดเท่ากับระบบ Hard Real time มันอาจเป็นเพียงระบบแบ่งเวลาที่ธรรมดาที่มีการให้ระดับความสำคัญแก่งานบางประเภท หรืองานที่ถูกเลือกไว้ล่วงหน้าว่าเป็นงานเร่งด่วน ซึ่งอาจทำให้เกิดปัญหาของการทำงานในระดับต่ำ ๆ อาจไม่ได้รับเวลาของซีพียูเลยดังที่เคยกล่าวไว้แล้วในหลักการของการจัดลำดับความสำคัญแบบคงที่ (Fix priority) อย่างไรก็ตามอย่างน้อยเราก็สามารถสร้างการทำงานที่ให้การตอบสนองของระบบเข้าใกล้แบบ Hard time แต่สามารถสนับสนุนงานอื่นๆ ได้อีกหลายงาน อันจะทำให้การใช้ระบบมีความคุ้มค่ากว่า และในสถานการณ์จริงแล้ว ระบบ Hard real-time จะมีราคาแพงกว่า Soft Real-time มากในแง่ของต้นทุนต่องานที่ผลิตได้ อย่างไรก็ตาม งานบางชนิดก็มีความสำคัญมากถึงขั้นที่ว่าราคาของระบบที่จะใช้ไม่เป็นปัจจัยหลัก เช่น งานทางด้านการบิน หรือกิจการด้านทางทหาร เป็นต้น
การสร้าง Soft real-time จะต้องมีการออกแบบอย่างระมัดระวังเพิ่มจาก priority Queue ปกติโดยมีกฎเพิ่มดังนี้

1. งานที่เป็นเรียลไทม์จะต้องได้รับความสำคัญสูงสุดเหนืองานอื่นๆ ทั้งหมดที่ไม่ใช่เรียลไทม์ และจะไม่มีวันที่งานแบบเรียลไทม์จะถูกลดขั้นลงไปอยู่ในคิวที่มีลำดับความสำคัญที่ต่ำกว่านี้ แม้ว่าระบบคิวแบบลำดับความสำคัญที่ใช้อาจเป็นแบบ Priority Feedback Queue ก็ตาม
2. เวลาของการทำ Context Switch และ Dispatcher ต้องสั้นมากๆ ยิ่งสั้นเท่าไร ก็จะยิ่งทำให้งานที่เป็น เรียลไทม์ สามารถเข้าไปใช้ซีพียูได้เร็วขึ้นเท่านั้น

ในส่วนของกฎข้อที่ 1 นั้นเราอาจสามารถสร้างออกมาใช้งานได้ไม่ยาก แต่การที่ทำให้กฎข้อที่ 2 สามารถกระทำได้อย่างแน่นอนมักเป็นเรื่องที่ยาก เนื่องจากว่าระบบปฏิบัติการที่เคยออกแบบกันมาทั้งหลายรวมทั้งระบบ UNIX นั้นถูกบังคับให้คอย System Call ทุกชนิดเสร็จสิ้น ก่อนหรือไม่ก็ต้องคอยให้เกิดการ บล็อกอินพุต/เอาต์พุตเสียก่อนที่จะมีการทำ และมักจะใช้เวลานาน เพราะบาง System call อาจจะกินเวลานานมาก และ บล็อกอินพุต/เอาต์พุต บางตัวก็มักจะทำงานได้ช้า

การแก้ปัญหาชั้นต้นก็คือเราต้องยอมให้สามารถหยุด System Call ได้รับสำรับ System Call ที่ใช้เวลานานบางตัว ด้วยการใส่ preemption point ลงไปใน system call ที่ยาว ๆ เหล่านี้ เพื่อที่จะให้มันหยุดตรวจสอบว่ามีงานแบบ เรียลไทม์คอยอยู่หรือเปล่า และถ้ามีก็ให้ไปทำงานเรียลไทม์ก่อน แล้วจึงกลับมาทำ system call ที่เหลืออยู่ให้เสร็จ อย่างไรก็ตามการใส่ preemption point ก็ยังมีข้อจำกัดที่ไม่สามรถใส่ลงไปได้ในขณะที่ข้อมูลของ Kernel กำลังถูกเปลี่ยนแปลง ซึ่งทำให้บางครั้งไม่สามารถทำให้ dispatch latency เล็กลงมากๆ ได้
อย่างไรก็ตามการปกป้องโครงสร้างข้อมูล จากการเรียกใช้งานโดยงานที่มีลำดับความสำคัญสูง ในขณะที่งานที่มีลำดับความสำคัญต่ำกำลังใช้อยู่ ทำให้งานที่มีลำดับความสำคัญสูงจำเป็นต้องคอยงานที่มีลำดับความสำคัญต่ำกำลังใช้อยู่ ทำให้งานที่มีลำดับความสำคัญสูงจำเป็นต้องคอยงานที่มีลำดับความสำคัญต่ำเหล่านี้ เหตุการณ์เช่นนี้ทำให้ดูเหมือนว่างานที่กำลังใช้โครงสร้างข้อมูลอยู่นั้นมีลำดับความสำคัญสูงที่สุด เราเรียกเหตุการณ์นี้ว่า Priority Inversion ซึ่งสามารถเกิดขึ้นได้เป็นสายยาวๆ เมื่อมีงานมาก ๆ เข้ามาซึ่งปัญหาเหล่านี้ก็ จะสามารถแก้ได้ด้วยวิธี
Priority-inheritance protocol นั่นคืองานที่มีลำดับความสำคัญต่ำๆ ก็จะได้รับความสำคัญสูงเท่ากับงานที่คอยใช้โครงสร้างข้อมูลอันเดียวกันอยู่ วิธีนี้จะทำให้งานที่มีลำดับความสำคัญต่ำๆ มีโอกาสเสร็จได้เร็วขึ้นและปล่อยการใช้โครงสร้างข้อมูลแล้ว ก็จะถูกตั้งค่าให้มีลำดับความสำคัญกลับมาเท่าเดิม
3.6 การคัดเลือกอัลกอริทึมสำหรับการจัดเวลาซีพียู
เมื่อเราได้ทำการรู้จัก อัลกอริทึม สำหรับการจัดเวลาซีพียูกันแล้ว ก็มีคำถามว่าเราจะเลือกอัลกอริทึมแบบไหน สำหรับระบบคอมพิวเตอร์ใดระบบหนึ่ง จากที่ได้ศึกษามาก็จะเห็นว่าการเลือกอัลกอริทึมที่ดีที่สุดนั้นเป็นเรื่องยากมาก
ปัญหาแรกที่เราจะต้องคิดถึงก็คือ เรื่องของการกำหนดคุณสมบัติสำหรับการเปรียบเทียบในกระบวนการคัดเลือกจากหัวข้อ 3.2 จะเห็นว่าหลักเกณฑ์ในการกำหนดคุณสมบัติเพื่อการเปรียบเทียบอัลกอริทึมต่างๆนั้น มักจะมาจากอรรถประโยชน์ของซีพียู (CPU utilization) เวลาตอบสนอง (Response time) และทรูพุต (Throughput) ซึ่งเราต้องมีการให้ค่าความสำคัญของแต่ละคุณสมบัติไว้ด้วย
หลักเกณฑ์การพิจารณาอาจกำหนดได้เป็นตัวอย่างดังนี้
• ให้มีการใช้ซีพียูสูงสุด โดยให้สามารถมีช่วงเวลาตอบสนองที่ไม่นานไปกว่า 1 วินาที
• ให้มีทรูพุตสูงสุด โดยที่เวลาวนรอบเป็นอัตราส่วนโดยตรงอย่างพอเหมาะกับเวลาที่ต้องใช้ในการรันทั้งหมด
เราอาจจะกำหนดหลักเกณฑ์ต่างๆ ให้มากกว่านี้ได้ ขึ้นอยู่กับว่า เราต้องการอะไร หรืออะไรคือสิ่งที่ดีที่สุดสำหรับระบบคอมพิวเตอร์ที่ให้มา อย่างไรก็ตาม การกำหนดหลักเกณฑ์ การพิจารณาเหล่านี้มักเป็นสิ่งที่ยากมาก เพราะว่าเรามักจะไม่ทราบ หรือทราบไม่แน่นอนว่าความต้องการที่แท้จริงของระบบคอมพิวเตอร์แต่ละระบบนั้นคืออะไร ดังนั้น สิ่งที่เราสามารถทำได้ในบทเรียนนี้ ก็คือการสมมุติว่า เราทราบความต้องการของระบบคอมพิวเตอร์แล้ว และเราสามารถกำหนดหลักเกณฑ์การพิจารณาได้ว่ามีอะไรบ้าง
เมื่อเรามีหลักเกณฑ์การพิจารณาอย่างครบถ้วนแล้ว เราก็จะมาเรียนรู้กันว่าเรามีวิธีการอย่างไรบ้างในการเปรียบเทียบและพิจาณาเพื่อที่จะเลือกอัลกอริทึมที่ดีที่สุด
3.6.1 Deterministic Modeling
วิธีนี้เป็นวิธีการคัดเลือกที่เรียกว่า analytic evaluation ซึ่งจะนำเอาอัลกอริทึมชนิดต่างๆ และลักษณะของงาน มาสร้างสูตร เพื่อใช้ในการคำนวณหาตัวเลขของประสิทธิภาพที่สามารถวัดและเปรียบเทียบได้
ตัวอย่างต่อไปนี้เราสมมติให้ว่ามีงาน 5 โปรเซสนี้มาถึงระบบที่เวลา 0 วินาที ตามลำดับที่ให้ไว้ในตารางโดยมีระยะเวลาของเวลาซีพียูตามกำหนด

โปรเซส เวลา
P1
P2
P3
P4
P5 10
29
3
7
12

อัลกอริทึมที่จะนำมาพิจารณาสมมติว่ามี 3 ชนิด คือมาก่อนได้ก่อน(FCFS), งานสั้นได้ทำก่อน (SJF)และเวลาวนรอบ (RR) โดยมีควันตัม = 10 วินาที ถ้าเราจะพิจาณาว่าอัลกอริทึมชนิดใดที่จะให้ค่าเฉลี่ยของการคอยต่ำสุด เราก็จะมีวิธีคำนวณดังนี้
สำหรับ FCFS



เวลาของการคอยคือ FCFS ก็คือ (0+10+39+42+49)/5 =28 วินาที1
เวลาการคอยของ SJF ก็คือ (10+32+0+3+20)/5 = 13 วินาที
สำหรับ RR เราจะมีลำดับการ RUN งานดังนี้



เวลาของคอยของ RR ก็คือ (0+32+20+23+40)/5 = 23 วินาที

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

3.6.2 โมเดลการจัดคิว
ลักษณะของงานที่เข้ามาในระบบคอมพิวเตอร์นั้นมักจะมีลักษณะที่ไม่แน่นอน ในแต่ละวันที่มีการใช้ระบบคอมพิวเตอร์นั้น งานต่างๆ ที่เข้ามาอาจมีลักษณะที่ไม่ซ้ำกันเลย อย่างไรก็ตามมีสิ่งหนึ่งที่เราสามารถทำนายหรือกำหนดได้ นั้นคือการกระจายของเวลาในการใช้ซีพียู และของการใช้อินพุต/เอาต์พุตซึ่งเราสามารถที่จะกำหนดแบบคร่าวๆได้ ซึ่งก็เช่นเดียวกันกับเวลาของการมาถึงระบบของงานต่างๆ ที่เราสามารถกำหนดไว้แบบการกระจายเช่นกัน จากการกำหนดค่ากระจายดังกล่าว ก็จะทำให้เราสามารถที่จะคำนวณว่าค่าเฉลี่ยนของทรูพุต การใช้งานซีพียู เวลาคอย หรือคุณสมบัติอื่นๆ ได้อีกมาก
ระบบคอมพิวเตอร์สามารถอธิบายได้ว่าเป็นระบบเน็ตเวิร์คของการให้บริการแบบสถานีหรืออาจมองได้เป็นสายงานกานผลิต โดยที่แต่ละสถานีจะมีคิวของตัวเอง ไม่ว่าจะเป็นตัวซีพียูหรืออุปกรณ์ต่างๆ ถ้าเรารู้ว่าเวลาของการให้บริการของแต่ละสถานีนั้นนานแค่ไหน และรูว่าเวลาที่งานต่างๆ จะเข้าที่คิว เราก็จะสามารถคำนวณหาค่าที่ต้องการต่างๆ ได้แล้ว วิธีนี้จึงมีชื่อเรียกว่าการวิเคราะห์การจัดคิวแบบเน็ตเวิร์ค
สำหรับตัวอย่างในเรื่องนี้ สมมุติให้ n คือค่าเฉลี่ยนความยาวของคิว โดยไม่รวมงานที่กำลังทำอยู่ ให้ w คือค่าเฉลี่ยนของเวลาที่ต้องคอยในคิว ให้ เป็นค่าเฉลี่ยนของเวลาที่งานใหม่จะเข้ามาในระบบ เช่น 3 งานต่อวินาที เป็นต้น ต่อจากนั้นเราก็จะสามารถคำนวณได้ว่าในขณะที่งานใดงานหนึ่งคอยเป็นเวลา w งานใหม่ก็จะเข้ามาเป็นจำนวน
x w ดังนั้น n = x w
สูตรดังกล่าวมีชื่อเรียกว่า Little’s Formula สูตรนี้มีความหมายในการคำนวณเพราะว่ามันสามารถใช้อัลกอริทึมใดๆ ก็ได้ ที่เรารู้ค่าเฉลี่ยการกระจายของเวลาในการมาถึงระบบของงาน และอย่างน้อยเราก็สามารถคำนวณหาค่าของตัวใดตัวหนึ่งใน 3 ตัวแปร n,w และ นี้ถ้าเรารู้ค่าของตัวแปรอีกสองตัว ตัวอย่างเช่น ถ้าเรารู้ว่าจะมีงานเข้าในระบบ 7 งานต่อวินาทีโดยเฉลี่ย และถ้ามีจำนวนงานอยู่ในแถวคอย 14 ตัว เราก็จะสามารถทราบได้ว่าค่าเฉลี่ยของการคอยในแถวคอยจะเป็นเวลา 2 วินาที
การใช้การวิเคราะห์การจัดคิวเป็นวิธีที่มีประโยชน์มาก เพราะสามารถใช้คำนวณหาค่าตัวเลขต่างๆเช่น เวลาเฉลี่ยนของการคอยแต่ละอัลกอริทึมเอาไว้เปรียบเทียบกัน อย่างไรก็ตามวิธีนี้ยังมีปัญหาอยู่ตรงที่สามารถที่ใช้คำนวณอัลกอริทึมไม่ได้ทั้งหมด และยังมีปัญหาเรื่องของการคำนวณค่าเฉลี่ยของการกระจายต่างๆ อยู่เพราะว่าถ้าหากระบบหรืออัลกอริทึมที่ใช้มีความซับซ้อนมาก การตั้งสูตรเพื่อคำนวณค่าที่ถูกต้องจริงๆ มักจะทำได้ยากตามไปด้วย ดังนั้นการตั้งค่าตัวเลขของค่าเฉลี่ยในการกระจาย มักมีการกำหนไว้อย่างง่ายๆ ซึ่งอาจทำให้ผลการคำนวณไม่เที่ยงตรงเท่าที่ควร
3.6.3 วิธีการจำลองระบบ (Simulations)
การที่เราจะเลือกวิธีการ หรือเลือกอัลกอริทึมที่ถูกจ้องต่อระบบใดๆ อย่างเป็นจริงจังแล้ว เราสามารถใช้วิธีการของการจำลองแบบ (Simulation) ซึ่งวิธีการนี้จะสามารถคำนวณตัวเลขต่างๆ ออกมาได้อย่างเที่ยงตรงมากขึ้น
การทำการจำลองระบบในที่นี้จะเกี่ยวข้องกับการใช้โปรแกรมคอมพิวเตอร์ ซึ่งจะต้องมีการเขียนโปรแกรมเพื่อใช้เป็นตัวแทนหรือหุ่นจำลองของระบบต่างๆ ในคอมพิวเตอร์ นอกจากนี้ยังต้องมีการเขียนโปรแกรมเพื่อเป็นตัวแทนของสิ่งแวดล้อมที่เกี่ยวข้องกับระบบคอมพิวเตอร์นั้นๆ อีกด้วย
สิ่งสำคัญในการสร้างแบบจำลองระบบคอมพิวเตอร์นี้ก็คือการมีตัวแปรที่เป็นตัวแทนของเวลา เพื่อเป็นสิ่งที่อ้างตำแหน่งหรือเป็นหลักการในการสร้างเหตุการณ์ต่างๆ ให้เกิดขึ้น (ตัวแปรเวลานี้จะมีค่าเพิ่มขึ้นเรื่อยๆตามเวลาที่เปลี่ยนไป) หรือไม่ก็เปลี่ยนตามเหตุการณ์ที่จะเกิดขึ้น ซึ่งเหตุการณ์ต่างๆ ในคอมพิวเตอร์ที่เกี่ยวข้องกับเวลาทั้งหมดจะต้องใช้ตัวแปรเวลาตัวเดียวกัน
เวลาของเหตุการณ์ต่างๆ ที่จะเกิดขึ้นในแบบจำลองนี้สามารถกระทำได้สองแบบ แบบแรกก็คือใช้วิธีสุ่มเราจะต้องเขียนโปรแกรมขึ้นมาก็สามารถสร้างงาน สร้างเวลาของซีพียู สร้างเวลาที่จะเข้ามาในระบบ ตามกฎของความน่าจะเป็น โดยเราสามารถกำหนดค่าเฉลี่ยของการกระจายในการค่าสุ่มเหล่านี้ได้ โดยที่ลักษณะของการกระจายสามารถที่จะเป็นแบบไหนก็ได้ เช่น อาจจะเป็นแบบที่ UNIFORM หรือ เป็น exponential หรือแบบ Poisson
หรือเป็นการใช้ข้อมูลจริงจากระบบจริง ซึ่งนั้นก็หมายความว่า เราได้ใช้ระบบจริงที่จะนำเอาอัลกอริทึมที่จะได้นำไปใช้จริงๆ โดยสามารถหามาได้จากการใช้ trace tape
Trace tape จะประกอบไปด้วยข้อมูลของการทำงานจริงของคอมพิวเตอร์ ที่เราต้องการจะหาอัลกอริทึมที่ดีที่สุด ข้อดีของการใช้ข้อมูลจริงคือ เราจะได้ผลลัพธ์ของการเปรียบเทียบอัลกอริทึมที่ถูกต้องมากกว่าการใช้วิธีสุ่มค่าการกระจายของทฤษฏีความน่าจะเป็น อย่างไรก็ตามถ้าหากว่าระบบมีความยุ่งยากซับซ้อนมาก การใช้วิธีการของความน่าจะเป็นก็ยังเป็นสิ่งที่จำเป็น
การทำแบบจำลองเพื่อการเปรียบเทียบอัลกอริทึมนี้ อาจจะต้องอาศัยเวลาในการทำงานค่อนข้างมากเพื่อให้ได้มาซึ่งผลลัพธ์ที่เที่ยงตรงทำให้วิธีนี้อาจมีราคาสูง และยิ่งทำให้การจำลองแบบมีความถูกต้องมากเท่าใด ก็จะยิ่งทำให้เสียเงินและเวลามากขึ้นเท่านั้น ดังนั้นผู้ที่จะใช้วิธีการจำลองแบบจะต้องตัดสินใจก่อนว่า จะใช้การจำลองแบบที่มีความละเอียดสูงแค่ไหนที่พอเพียงต่อการตัดสินใจ โดยไม่ทำให้เสียเงินและเวลามากเกินความจำเป็น
3.6.4 วิธีการสร้างขึ้นมาจริงๆ
อย่างไรก็ตามการสร้างแบบจำลอง ก็ยังคงเป็นการจำลองแบบที่ไม่มีทางจะเหมือนจริงได้ สิ่งที่ดีกว่าก็คือการสร้างอัลกอริทึมชนิดๆต่างๆ เพื่อทดลองใช้กับโปรแกรมจัดการระบบจริงๆ ในระบบคอมพิวเตอร์ที่ใช้งานในสิ่งแวดล้อมจริงๆ
เหตุผลหลักที่ทำให้วิธีการนี้จะไม่เป็นแนวทางที่นิยมปฏิบัติคือ จะใช้ต้นทุน หรือการลงทุนสูงมาก เพราะนอกจากจะต้องเขียนโปรแกรมของอัลกอริทึมแต่ละแบบแล้ว ยังต้องมีการใช้เวลาและแรงงานในการเปลี่ยนการทำงานของโปรแกรมจัดการระบบเพื่อให้สามารถรองรับอัลกอริทึมแบบต่างๆ ที่จะนำมาทดลองยิ่งไปกว่านั้นแต่ละอัลกอริทึมอาจยังต้องการระบบฮาร์ดแวร์พิเศษที่แตกต่างกันออกไป ทำให้ต้องมีระบบคอมพิวเตอร์ที่ต้องสามารถปรับเปลี่ยนได้ ซึ่งก็ไม่ใช่เรื่องที่จะทำกันได้ง่ายๆ ภายใต้ต้นทุนที่จำกัด และที่เป็นปัญหาที่สุดก็คงหนีไม่พ้นปัญหาที่อาจจะมาจากผู้ใช้คอมพิวเตอร์นั่นเอง เพราะคงมีผู้ใช้ไม่มากนักที่จะยอมเสียเวลาทำงานจริงมาเสี่ยงกับระบบคอมพิวเตอร์ที่อยู่ในขั้นทดลอง
และถึงแม้ว่าเราจะมีวิธีการที่ดีสำหรับการแก้ปัญหาดังกล่าวข้างต้น คำถามก็ยังมีต่อไปว่า ผลที่ได้จากการทดลองจะทำให้การตัดสินใจถูกต้องแค่ไหน เพราะเราจะมีความมั่นใจได้อย่างไรว่า เราได้ทำการทดลองอัลกอริทึมต่างๆ ได้ครบถ้วนต่อทุกสถานการณ์ที่จะเกิดขึ้น ซึ่งคำตอบก็เห็นได้ชัดเจนอยู่แล้วว่าเป็นไปไม่ได้ เนื่องจากว่างานหรือลักษณะของปัญหาที่จะนำเข้ามานั้นมีโอกาสที่จะเปลี่ยนแปลงได้เสมอ และเป็นการเปลี่ยนแปลงในทางที่ไม่สามารถล่วงรู้ได้ และตัวผู้ใช้เองก็อาจจะมีการปรับปรุงโปรแกรมของตนเอง เพื่อให้มีความเหมาะสมกับอัลกอริทึมที่ใช้ จุดประสงค์ก็เพียงเพื่อให้โปรแกรมของตนสามารถมีโอกาสเข้าใช้ซีพียูมากกว่าโปรแกรมของผู้อื่นๆตัวอย่างง่ายๆ ก็คือ การที่ผู้เขียนโปรแกรมงานให้มาขนาดเวลาซีพียูสั้นๆ ถ้าหากรู้ว่าระบบคอมพิวเตอร์ที่จะใช้งานใช้อัลกอริทึมแบบงานสั้นได้ทำก่อน (SJF) เป็นต้น
ทางออกที่ดีที่สุดก็คือการที่สามารถทำให้ระบบคอมพิวเตอร์ใดๆ สามารถที่จะเปลี่ยนแปลงและปรับเปลี่ยนอัลกอริทึมที่จะใช้โดยผู้ควบคุม การเปลี่ยนแปลงนี้บางส่วนอาจสามารถกระทำได้ในระหว่างการใช้งานซึ่งบางส่วนก็อาจจะสามารถกระทำได้เฉพาะช่วงที่เปิดเครื่องเท่านั้น การทำให้ระบบคอมพิวเตอร์ใดๆ สามารถปรับเปลี่ยนอัลกอริทึมได้นี้เป็นที่ต้องการของระบบคอมพิวเตอร์แทบทุกระบบ เพราะว่างานในแต่ละวันหรือแต่ละช่วงเวลามักมีความต้องการระบบปฏิบัติการที่แตกต่างกัน ถึงแม้จะรู้กันดีว่าการปรับเปลี่ยนเหล่านี้เป็นความต้องการแต่ในทุกวันนี้ระบบคอมพิวเตอร์ที่สามารถยอมให้มีการปรับแต่งระบบปฏิบัติการได้นั้นก็ยังคงมีอยู่เป็นจำนวนน้อยมาก
สรุป
การจัดเวลาซีพียู(CPU Scheduling) เป็นงานของการจัดเวลาใช้งานซีพียูโดยมีหน้าที่หลักก็คือการตัดสินใจเลือกงานเข้ามาใช้งาน โดยมี Dispatcher เป็นเครื่องมือในการนำเอางานที่ได้รับคัดเลือกนี้เข้าและออกจากการใช้ซีพียู
การมาก่อน(FCFS) เป็นอัลกอริทึมแบบให้สิทธิ์ก่อน(Preemptive) ที่ง่ายที่สุดสำหรับการจัดเวลาซีพียู แต่ก็เป็นระบบการจัดการที่ทำให้งานที่ต้องการใช้ ซีพียูเพียงแค่ระยะเวลาสั้นๆต้องคอยงานที่ใช้ซีพียูนานๆ ส่วนงานสั้นได้ทำก่อน(SJF) ก็เป็นอัลกอริทึมที่สารมารถเป็นทั้งแบบให้สิทธิ์ก่อน(Preemptive) และไม่ให้สิทธิ์ก่อน(nonpreemptive) SJF จะให้ค่าเฉลี่ยของการรอคอย(Waiting Time) สั้นที่สุด แต่ในการใช้งานจริงจะก็มีปัญหาในเรื่องของการวัดระยะซีพียูถัดไปของแต่ละงาน SJF มีการทำงานคล้ายกับการมีลำดับขั้นความสำคัญของงาน(Priority) โดยงานที่มีเวลาซีพียูสั้นๆ จะเป็นงานที่มีความสำคัญมาก ทำให้มีโอกาสเข้าไปใช้ซีพียูก่อน ซึ่งอาจทำให้เกิดปัญหาการตกค้างของงานที่มีความสำคัญต่ำถ้าหากว่าระบบคอมพิวเตอร์มีงานมาก การแก้ไขก็ด้วยการใช้วิธีเพิ่มความสำคัญให้กับงานตามระยะเวลาที่ต้องคอย
อัลกอริทึมแบบวนรอบ(RR : Round-Robin) ก็เป็นระบบการจัดเวลาแบบให้สิทธิ์ก่อนเหมาะสมกับระบบคอมพิวเตอร์แบบแบ่งเวลา หรือการทำงานแบบอินเตอร์แอ็กทีฟเพราะจะทำให้มีเวลาวนรอบ(Turnaround Time) ที่คงที่แน่นอน เนื่องจากว่า RR มีการกำหนดช่วงเวลาที่จำกัดในการเข้าใช้ซีพียูของแต่ละงานที่คงที่ที่เรียกว่าเวลาควันตัม(Quantum Time) ซึ่งงานทุกงานจะมีโอกาสได้รับซีพียูมาใช้อย่างมากก็เพียงแค่ระยะเวลาของควันตัมที่กำหนดเท่านั้น ซึ่งการกำหนดค่าของควันตัมนี้ ต้องมีการกำหนดให้พอดี ถ้ามีการกำหนดที่ยาวเกินไปการทำงานก็จะมีประสิทธิภาพมใกล้เคียงกับ FCFS แต่ถ้าควันตัมถูกกำหนดใว้สั้นเกินไป ระบบก็จะเสียเวลาไปกับการนำงานเข้าและออก หรือเวลาในการทำ Context Switch มากเกินไปจนทำให้ทรูพุตของระบบต่ำลง
คิวแบบหลายระดับ (Multilevel Queue) อาจมีการรวมเอาอัลกอริทึมหลายชนิดเข้าใว้ด้วยกันเพื่อให้สามารถรองรับระบบงานที่มีงานหลายประภทมากขึ้นโดยจะให้บนิการแก่งานต่างๆอย่างเท่าเทียมกันตามระดับความสำคัญของงานนั้นๆ และการใช้คิวแบบ Multilevel Feedback ก็จะยอมให้มีการปรับเปลี่ยนระดับความสำคัญของตัวงานได้ด้วยการยอมให้งานสามารถเลื่อนขึ้นหรือลงในคิวแบบหลานระดับเพื่อแก้ปัญหาของการที่งานบางชนิดจะไม่มีโอกาสได้รับซีพียูมาใช้เลย
การตัดสินใจว่าจะนำเอาอัลกอริทึมชนิดไหนมาใช้ก็มีวิธีการอยู่มากมาย การใช้วิธีคำนวณจากสูตรนั้นมีประโยชน์ในการคำนวณหาประสิทธิภาพของระบบโดยรวมแบบคร่าวๆ ในขณะที่วิธีการจำลองแบบหรือSimulation นั้นจะสามารถทำให้การตัดสินใจมีความถูกต้องมากขึ้น แต่ก็ต้องแลกมาด้วยแรงงานและเวลา ซึ่งจะทำให้มีผลกระทบต่อต้นทุนที่จะต้องสูงขึ้น แต่ในบางระบบคอมพิวเตอร์ที่ต้องการประสิทธิภาพสูงสุดโดยไม่สนใจว่าต้องใช้ต้นทุนเท่าไร วิธี Simulation ก็จะต้องเป็นเรื่องีท่หลีกเลี่ยงไม่ได้ อย่างไรก็ตาม วิธีที่ดีที่สุดก็คือการสร้างอัลกอริทึมต่างๆ ขึ้นมาและทดลองใช้ระบบคอมพิวเตอร์ที่ทำงานกับงานจริง
ในปัจจุบันสิ่งที่เป็นความต้องการของระบบคอมพิวเตอร์ก็คือ ความต้องการที่จะให้ระบบปฏิบัติการมีความสามารถในการปรับเปลี่ยนหรือปรับแต่งอัลกอริทึมที่ใช้ได้ตามลักษณะของงานที่เปลี่ยนแปลงไป