การจัดตารางเวลา (ด้านคอมพิวเตอร์)

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

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

การจัดตารางเวลาเป็นพื้นฐานสำคัญของการคำนวณ และเป็นส่วนสำคัญของแบบจำลองการทำงาน ของระบบคอมพิวเตอร์ แนวคิดของการจัดตารางเวลาทำให้ คอมพิวเตอร์สามารถ ทำงานหลายอย่างพร้อมกันได้ ด้วยหน่วยประมวลผลกลาง (CPU) เพียงหน่วยเดียว

เป้าหมาย

โปรแกรมจัดตารางเวลาอาจตั้งเป้าหมายไว้หนึ่งอย่างหรือมากกว่านั้น ตัวอย่างเช่น:

เพิ่ม ผลผลิตให้สูงสุด(ปริมาณงานทั้งหมดที่เสร็จสมบูรณ์ต่อหน่วยเวลา)
ลด ระยะเวลารอคอยให้น้อยที่สุด (เวลาตั้งแต่การเตรียมงานพร้อมจนถึงจุดเริ่มต้นการทำงานครั้งแรก)
ลด ความล่าช้าหรือเวลาตอบสนองให้น้อยที่สุด(เวลาตั้งแต่การทำงานพร้อมจนกว่าจะเสร็จสิ้นในกรณีของกิจกรรมแบบกลุ่ม^{[ 1 ]}^{[ 2 ]}^{[ 3 ]}หรือจนกว่าระบบจะตอบสนองและส่งเอาต์พุตแรกให้กับผู้ใช้ในกรณีของกิจกรรมแบบโต้ตอบ) ^{[ 4 ]}
เพิ่ม ความยุติธรรมให้สูงสุด(จัดสรรเวลา CPU ให้แต่ละกระบวนการอย่างเท่าเทียมกัน หรือโดยทั่วไปแล้วจัดสรรเวลาที่เหมาะสมตามลำดับความสำคัญและภาระงานของแต่ละกระบวนการ)

ในทางปฏิบัติ เป้าหมายเหล่านี้มักขัดแย้งกัน (เช่น ปริมาณงานเทียบกับเวลาแฝง) ดังนั้น ตัวจัดตารางเวลาจะทำการหาจุดลงตัวที่เหมาะสม การวัดความชอบจะพิจารณาจากข้อกังวลใดข้อหนึ่งที่กล่าวมาข้างต้น ขึ้นอยู่กับความต้องการและวัตถุประสงค์ของผู้ใช้

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

ประเภทของตัวกำหนดตารางเวลาของระบบปฏิบัติการ

ตัวจัดตารางงาน (Scheduler) คือโมดูลของระบบปฏิบัติการที่ทำหน้าที่เลือกงานถัดไปที่จะเข้าสู่ระบบและกระบวนการถัดไปที่จะทำงาน ระบบปฏิบัติการอาจมีตัวจัดตารางงานได้ถึงสามประเภท ได้แก่ตัวจัดตารางงานระยะยาว (หรือที่เรียกว่าตัวจัดตารางงานรับเข้าหรือตัวจัดตารางงานระดับสูง) ตัวจัดตารางงานระยะกลางและตัวจัดตารางงานระยะสั้นชื่อเหล่านี้บ่งบอกถึงความถี่ในการทำงานของฟังก์ชันต่างๆ

ตัวกำหนดตารางเวลาของกระบวนการ

ตัวจัดตารางเวลาของกระบวนการเป็นส่วนหนึ่งของระบบปฏิบัติการที่ตัดสินใจว่ากระบวนการใดจะทำงานในช่วงเวลาใดเวลาหนึ่ง โดยปกติแล้วจะมีความสามารถในการหยุดกระบวนการที่กำลังทำงานอยู่ ย้ายไปไว้ท้ายคิวที่กำลังทำงานอยู่ และเริ่มต้นกระบวนการใหม่ ตัวจัดตารางเวลาดังกล่าวเรียกว่าตัวจัดตารางเวลาแบบแย่งชิงหากตัวจัดตารางเวลาไม่สามารถหยุดกระบวนการที่กำลังทำงานอยู่และเริ่มต้นกระบวนการใหม่ได้ ตัวจัดตารางเวลานั้นจะเป็นตัวจัดตารางเวลาแบบร่วมมือ^{[ 5 ]}

เราแบ่งประเภทระหว่าง การกำหนดตารางเวลา ในระยะยาวการกำหนดตารางเวลาในระยะกลางและการกำหนดตารางเวลาในระยะสั้นโดยพิจารณาจากความถี่ในการตัดสินใจ^{[ 6 ]}

การวางแผนระยะยาว

ตัวจัดตารางงานระยะยาวหรือตัวจัดตารางการรับเข้าทำงานจะตัดสินใจว่างานหรือกระบวนการใดควรได้รับการรับเข้าคิวพร้อมทำงาน (ในหน่วยความจำหลัก) กล่าวคือ เมื่อมีการพยายามเรียกใช้โปรแกรม การรับเข้ากลุ่มกระบวนการที่กำลังทำงานอยู่จะได้รับการอนุมัติหรือถูกเลื่อนออกไปโดยตัวจัดตารางงานระยะยาว ดังนั้น ตัวจัดตารางงานนี้จึงกำหนดว่ากระบวนการใดควรทำงานบนระบบ ระดับของการทำงานพร้อมกันที่สามารถรองรับได้ในแต่ละครั้ง – ไม่ว่าจะมีกระบวนการจำนวนมากหรือน้อยที่จะทำงานพร้อมกัน และวิธีการจัดการการแบ่งระหว่างกระบวนการที่เน้นการรับส่งข้อมูล (I/O-intensive) และกระบวนการที่เน้นการประมวลผล (CPU-intensive) ตัวจัดตารางงานระยะยาวมีหน้าที่รับผิดชอบในการควบคุมระดับของการทำงานหลายโปรแกรมพร้อมกัน

โดยทั่วไป กระบวนการส่วนใหญ่สามารถอธิบายได้ว่าเป็นกระบวนการที่เน้น I/Oหรือกระบวนการที่เน้น CPUกระบวนการที่เน้น I/O คือกระบวนการที่ใช้เวลาในการทำ I/O มากกว่าการคำนวณ ในทางตรงกันข้าม กระบวนการที่เน้น CPU จะสร้างคำขอ I/O ไม่บ่อยนัก และใช้เวลาในการคำนวณมากกว่า สิ่งสำคัญคือตัวจัดตารางเวลาในระยะยาวต้องเลือกส่วนผสมที่ดีของกระบวนการที่เน้น I/O และกระบวนการที่เน้น CPU หากกระบวนการทั้งหมดเน้น I/O คิวพร้อมทำงานจะว่างเปล่าเกือบตลอดเวลา และตัวจัดตารางเวลาในระยะสั้นจะมีงานทำน้อย ในทางกลับกัน หากกระบวนการทั้งหมดเน้น CPU คิวรอ I/O จะว่างเปล่าเกือบตลอดเวลา อุปกรณ์จะไม่ได้ถูกใช้งาน และระบบก็จะเสียสมดุลอีกครั้ง ดังนั้น ระบบที่มีประสิทธิภาพดีที่สุดจะมีส่วนผสมของกระบวนการที่เน้น CPU และกระบวนการที่เน้น I/O ในระบบปฏิบัติการสมัยใหม่ สิ่งนี้ใช้เพื่อให้แน่ใจว่ากระบวนการแบบเรียลไทม์ได้รับเวลา CPU เพียงพอที่จะทำงานให้เสร็จ^{[ 7 ]}

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

ระบบปฏิบัติการบางระบบจะอนุญาตให้เพิ่มงานใหม่ได้ก็ต่อเมื่อมั่นใจว่ากำหนดเวลาแบบเรียลไทม์ทั้งหมดจะยังคงสามารถทำได้กลไกการควบคุมการรับเข้า ใช้ คือ อัลกอริธึมฮิวริสติกเฉพาะที่ระบบปฏิบัติการใช้ในการยอมรับหรือปฏิเสธงานใหม่ ^{[ 8 ]}

การวางแผนระยะกลาง

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

In many systems today (those that support mapping virtual address space to secondary storage other than the swap file), the medium-term scheduler may actually perform the role of the long-term scheduler, by treating binaries as swapped-out processes upon their execution. In this way, when a segment of the binary is required, it can be swapped in on demand, or lazy loaded, also called demand paging.

Short-term scheduling

The short-term scheduler (also known as the CPU scheduler) decides which of the ready, in-memory processes is to be executed (allocated a CPU) after a clock interrupt, an I/O interrupt, an operating system call or another form of signal. Thus, the short-term scheduler makes scheduling decisions much more frequently than the long-term or mid-term schedulers – A scheduling decision will, at a minimum, have to be made after every time slice, and these are very short. This scheduler can be preemptive, implying that it is capable of forcibly removing processes from a CPU when it decides to allocate that CPU to another process, or non-preemptive (also known as voluntary or co-operative), in which case the scheduler is unable to force processes off the CPU.

Dispatcher

Another component that is involved in the CPU-scheduling function is the dispatcher, which is the module that gives control of the CPU to the process selected by the short-term scheduler. It receives control in kernel mode as the result of an interrupt or system call. The functions of a dispatcher involve the following:

Context switches, in which the dispatcher saves the state (also known as context) of the process or thread that was previously running; the dispatcher then loads the initial or previously saved state of the new process.
Switching to user mode.
Jumping to the proper location in the user program to restart that program indicated by its new state.

The dispatcher should be as fast as possible since it is invoked during every process switch. During the context switches, the processor is virtually idle for a fraction of time, thus unnecessary context switches should be avoided. The time it takes for the dispatcher to stop one process and start another is known as the dispatch latency.^[7]^{: 155}

Scheduling disciplines

ระเบียบวิธีจัดตารางเวลา (หรือเรียกว่านโยบายการจัดตารางเวลาหรืออัลกอริทึมการจัดตารางเวลา ) คืออัลกอริทึมที่ใช้ในการจัดสรรทรัพยากรระหว่างฝ่ายต่างๆ ที่ร้องขอพร้อมกันและแบบไม่พร้อมกัน ระเบียบวิธีจัดตารางเวลาถูกนำไปใช้ในเราเตอร์ (เพื่อจัดการการรับส่งข้อมูลแบบแพ็กเก็ต) รวมถึงในระบบปฏิบัติการ (เพื่อแบ่งปันเวลา CPUระหว่างเธรดและกระบวนการ ต่างๆ ) ไดรฟ์ดิสก์ ( การจัดตารางเวลา I/O ) เครื่องพิมพ์ ( ตัวจัดการคิวงานพิมพ์ ) ระบบฝังตัวส่วนใหญ่ และอื่นๆ

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

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

อัลกอริทึมการจัดตารางเวลาแบบพยายามอย่างเต็มที่ที่ง่ายที่สุด ได้แก่ การ จัดตารางเวลา แบบวนรอบ (round-robin ) , การจัดคิวแบบยุติธรรม ( fair queuing ) (อัลกอริทึมการจัดตารางเวลา แบบยุติธรรมสูงสุด-ต่ำสุด ), การจัดตารางเวลาแบบยุติธรรม ตามสัดส่วน (proportional-fair scheduling ) และ ปริมาณงานสูงสุด ( maximum throughput ) หาก มีการให้บริการที่มีคุณภาพที่แตกต่างกันหรือรับประกันได้แทนที่จะใช้การสื่อสารแบบพยายามอย่างเต็มที่ อาจใช้ การจัดคิวแบบยุติธรรมถ่วงน้ำหนัก (weighted fair queuing) ได้

ในเครือข่ายไร้สายวิทยุแพ็กเก็ตขั้นสูง เช่นระบบเซลลูลาร์HSDPA (High-Speed Downlink Packet Access) 3.5G การจัดตารางเวลาขึ้นอยู่กับช่องสัญญาณอาจถูกนำมาใช้เพื่อใช้ประโยชน์จากข้อมูลสถานะช่องสัญญาณหากสภาพช่องสัญญาณเอื้ออำนวยปริมาณงานและประสิทธิภาพสเปกตรัมของระบบอาจเพิ่มขึ้น ในระบบที่ก้าวหน้ายิ่งกว่า เช่นLTEการจัดตารางเวลาจะรวมเข้ากับการจัดสรรช่องสัญญาณแบบไดนามิก แบบแพ็กเก็ตต่อแพ็กเก็ตที่ขึ้นอยู่กับช่องสัญญาณ หรือโดยการกำหนดOFDMA multi-carriers หรือ ส่วนประกอบ การปรับสมดุลโดเมนความถี่ อื่นๆ ให้กับผู้ใช้ที่สามารถใช้งานได้ดีที่สุด^{[ 9 ]}

มาก่อนได้ก่อน

เข้าก่อนออกก่อน ( FIFO ) หรือที่รู้จักกันในชื่อมาก่อนได้ก่อน (FCFS) เป็นอัลกอริทึมการจัดตารางเวลาที่ง่ายที่สุด FIFO จะจัดลำดับกระบวนการตามลำดับที่เข้ามาในคิวพร้อมทำงาน วิธีนี้มักใช้สำหรับ...ตัวอย่างเช่น คิวงานดังที่แสดงไว้ในส่วนนี้

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

การจัดตารางเวลาตามลำดับความสำคัญ

การจัดลำดับความสำคัญตามกำหนด เวลาที่เร็วที่สุด (Earliest Deadline First หรือ EDF) หรือเวลาที่เหลือน้อยที่สุดเป็นอัลกอริธึมการจัดตารางเวลาแบบไดนามิกที่ใช้ในระบบปฏิบัติการแบบเรียลไทม์เพื่อจัดเรียงกระบวนการต่างๆ ในคิวลำดับความสำคัญ เมื่อใดก็ตามที่เกิดเหตุการณ์การจัดตารางเวลา (เช่น งานเสร็จสิ้น งานใหม่ถูกปล่อยออกมา ฯลฯ) ระบบจะค้นหาในคิวเพื่อหากระบวนการที่ใกล้ถึงกำหนดเวลาที่สุด ซึ่งจะเป็นกระบวนการถัดไปที่จะถูกกำหนดให้ดำเนินการ

ใครมีเวลาเหลือน้อยที่สุดก่อน

คล้ายกับ หลักการจัดลำดับงานที่เหลือเวลา น้อยที่สุดก่อน (Shortest Job First : SJF) กลยุทธ์นี้ช่วยให้ตัวจัดลำดับงานสามารถจัดลำดับกระบวนการที่มีเวลาประมวลผลเหลือน้อยที่สุดไว้ในลำดับถัดไป ซึ่งต้องอาศัยความรู้หรือการประมาณเวลาที่แม่นยำเกี่ยวกับเวลาที่ใช้ในการประมวลผลแต่ละกระบวนการ

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

การจัดตารางเวลาแบบลำดับความสำคัญคงที่แบบแทรกแซง

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

ค่าใช้จ่ายในการดำเนินงานไม่น้อย และก็ไม่มากเช่นกัน
FPPS ไม่มีข้อได้เปรียบเป็นพิเศษในแง่ของปริมาณงานเมื่อเทียบกับการจัดตารางเวลาแบบ FIFO
หากจำนวนลำดับชั้นมีจำกัด สามารถอธิบายได้ว่าเป็นชุดของคิวแบบ FIFO (First-In, First-Out) โดยแต่ละคิวแทนลำดับความสำคัญระดับหนึ่ง กระบวนการในคิวที่มีลำดับความสำคัญต่ำกว่าจะถูกเลือกก็ต่อเมื่อคิวที่มีลำดับความสำคัญสูงกว่าว่างเปล่าทั้งหมดแล้วเท่านั้น
เวลาในการรอและเวลาตอบสนองขึ้นอยู่กับลำดับความสำคัญของกระบวนการ กระบวนการที่มีลำดับความสำคัญสูงกว่าจะมีเวลาในการรอและเวลาตอบสนองที่น้อยกว่า
สามารถทำตามกำหนดเวลาได้โดยการให้ความสำคัญกับกระบวนการที่มีกำหนดเวลามากขึ้น
กระบวนการที่มีลำดับความสำคัญต่ำกว่าอาจประสบปัญหาการขาดแคลนทรัพยากรได้ หากมีกระบวนการที่มีลำดับความสำคัญสูงจำนวนมากรอคิวใช้ทรัพยากร CPU อยู่

การจัดตารางแบบหมุนเวียน

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

การจัดตารางเวลา RR เกี่ยวข้องกับค่าใช้จ่ายเพิ่มเติมจำนวนมาก โดยเฉพาะอย่างยิ่งเมื่อหน่วยเวลาเล็ก ๆ
การปรับสมดุลอัตราการประมวลผลระหว่าง FCFS/FIFO และ SJF/SRTF ทำให้งานที่ใช้เวลาน้อยกว่าเสร็จเร็วกว่าในรูปแบบ FIFO และกระบวนการที่ใช้เวลานานกว่าเสร็จเร็วกว่าในรูปแบบ SJF
เวลาตอบสนองเฉลี่ยดี เวลาในการรอขึ้นอยู่กับจำนวนกระบวนการ ไม่ใช่ความยาวเฉลี่ยของกระบวนการ
เนื่องจากระยะเวลารอคอยนาน ทำให้การส่งมอบงานตรงตามกำหนดนั้นทำได้ยากในระบบ RR แบบดั้งเดิม
ภาวะอดอยากจะไม่เกิดขึ้น เนื่องจากไม่มีการกำหนดลำดับความสำคัญ ลำดับการจัดสรรหน่วยเวลาจะขึ้นอยู่กับเวลาที่กระบวนการมาถึง คล้ายกับหลักการ FIFO (First In, First Out)
ถ้าช่วงเวลา (Time-Slice) ยาว จะใช้รูปแบบ FCFS/FIFO หรือถ้าสั้น จะใช้รูปแบบ SJF/SRTF

การจัดตารางคิวหลายระดับ

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

โปรแกรมจัดตารางเวลาที่ช่วยประหยัดเวลาและแรงงาน

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

ปัญหาการเพิ่มประสิทธิภาพการจัดตารางเวลา

มีปัญหาการจัดตารางเวลาหลายอย่างที่เป้าหมายคือการตัดสินใจว่างานใดควรไปที่สถานีใดในเวลาใด เพื่อให้ระยะเวลาดำเนินการ ทั้งหมด สั้นที่สุด:

การจัดตารางงานในโรงงาน – มี งาน $n$ ชิ้น และ สถานีที่เหมือนกัน $m$ สถานี แต่ละงานจะต้องดำเนินการบนเครื่องจักรเพียงเครื่องเดียว โดยทั่วไปถือว่าเป็นปัญหาแบบออนไลน์
การจัดตารางงานแบบเปิด – มี งาน $n$ งาน และ สถานีทำงาน $m$ สถานี โดยแต่ละงานควรใช้เวลาอยู่ที่แต่ละสถานีในลำดับที่อิสระ
การจัดตารางการผลิตแบบฟลอว์ช็อป – มี งาน $n$ ชิ้น และ สถานีที่แตกต่างกัน $m$ สถานี แต่ละงานควรใช้เวลาอยู่ที่แต่ละสถานีตามลำดับที่กำหนดไว้ล่วงหน้า

การกำหนดตารางเวลาด้วยตนเอง

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

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

การเลือกอัลกอริทึมการจัดตารางเวลา

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

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

การใช้งานตัวกำหนดตารางเวลาของกระบวนการระบบปฏิบัติการ

อัลกอริทึมที่ใช้อาจเรียบง่ายอย่างเช่นแบบวนรอบ (round-robin)ซึ่งแต่ละกระบวนการจะได้รับเวลาเท่ากัน (ตัวอย่างเช่น 1 มิลลิวินาที โดยปกติจะอยู่ระหว่าง 1 มิลลิวินาทีถึง 100 มิลลิวินาที) ในรายการแบบวนรอบ ดังนั้น กระบวนการ A จะทำงานเป็นเวลา 1 มิลลิวินาที จากนั้นกระบวนการ B จากนั้นกระบวนการ C แล้วกลับไปที่กระบวนการ A อีกครั้ง

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

OS/360 และรุ่นต่อมา

ระบบปฏิบัติการ IBM OS/360มีให้เลือกใช้กับตัวจัดตารางเวลา (scheduler) สามแบบที่แตกต่างกัน ความแตกต่างเหล่านี้มีมากจนมักถูกมองว่าเป็นระบบปฏิบัติการที่แตกต่างกันถึงสามระบบ:

ตัว เลือก Single Sequential Schedulerหรือที่รู้จักกันในชื่อPrimary Control Program (PCP)ช่วยให้สามารถดำเนินการงานตามลำดับในชุดงานเดียวได้
ตัว เลือก Multiple Sequential Schedulerหรือที่รู้จักกันในชื่อMultiprogramming with a Fixed Number of Tasks (MFT)ช่วยให้สามารถดำเนินการงานหลายงานพร้อมกันได้ การดำเนินการจะถูกควบคุมโดยลำดับความสำคัญ ซึ่งมีค่าเริ่มต้นสำหรับแต่ละสตรีม หรือสามารถร้องขอแยกต่างหากสำหรับแต่ละงานได้ MFT เวอร์ชัน II เพิ่มงานย่อย (เธรด) ซึ่งทำงานตามลำดับความสำคัญของงานหลัก แต่ละสตรีมงานจะกำหนดปริมาณหน่วยความจำสูงสุดที่งานใด ๆ ในสตรีมนั้นสามารถใช้ได้
ตัว เลือก การจัดตารางเวลาที่มีลำดับความสำคัญหลายรายการหรือการทำงานหลายโปรแกรมด้วยจำนวนงานที่เปลี่ยนแปลงได้ (MVT)จะมีงานย่อยตั้งแต่เริ่มต้น โดยแต่ละงานจะร้องขอลำดับความสำคัญและหน่วยความจำที่ต้องการก่อนที่จะดำเนินการ

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

วินโดวส์

ระบบ MS-DOS และ Microsoft Windows รุ่นแรกๆ นั้นไม่ได้รองรับการทำงานแบบมัลติทาสกิ้ง ดังนั้นจึงไม่มีตัวกำหนดตารางเวลาWindows 3.1xใช้ตัวกำหนดตารางเวลาแบบไม่แทรกแซง ซึ่งหมายความว่าจะไม่ขัดจังหวะโปรแกรมต่างๆ โดยอาศัยโปรแกรมในการยุติการทำงานหรือแจ้งให้ระบบปฏิบัติการทราบว่าไม่ต้องการโปรเซสเซอร์อีกต่อไป เพื่อที่จะสามารถดำเนินการกับกระบวนการอื่นได้ ซึ่งโดยทั่วไปเรียกว่าการทำงานแบบมัลติทาสกิ้งแบบร่วมมือ Windows 95 ได้แนะนำตัวกำหนดตารางเวลาแบบแทรกแซงขั้นพื้นฐาน อย่างไรก็ตาม เพื่อรองรับระบบรุ่นเก่า จึงเลือกที่จะให้แอปพลิเคชัน 16 บิตทำงานโดยไม่ต้องแทรกแซง^{[ 10 ]}

ระบบปฏิบัติการ Windows NTใช้คิวป้อนกลับแบบหลายระดับ โดยกำหนดระดับความสำคัญไว้ 32 ระดับ ตั้งแต่ 0 ถึง 31 โดยระดับความสำคัญ 0 ถึง 15 เป็น ระดับความสำคัญ ปกติและระดับความสำคัญ 16 ถึง 31 เป็นระดับความสำคัญแบบเรียลไทม์ที่ไม่เข้มงวด ซึ่งต้องมีสิทธิ์ในการกำหนด ระดับ 0 สงวนไว้สำหรับระบบปฏิบัติการ ส่วนติดต่อผู้ใช้และ API ทำงานกับคลาสความสำคัญสำหรับกระบวนการและเธรดในกระบวนการนั้น จากนั้นระบบจะรวมคลาสเหล่านั้นเข้าด้วยกันเป็นระดับความสำคัญสูงสุด

เคอร์เนลอาจเปลี่ยนระดับความสำคัญของเธรดโดยขึ้นอยู่กับการใช้งาน I/O และ CPU และว่าเธรดนั้นเป็นแบบโต้ตอบหรือไม่ (เช่น รับและตอบสนองต่ออินพุตจากมนุษย์) โดยจะเพิ่มความสำคัญของกระบวนการแบบโต้ตอบและกระบวนการที่จำกัดด้วย I/O และลดความสำคัญของกระบวนการที่จำกัดด้วย CPU เพื่อเพิ่มการตอบสนองของแอปพลิเคชันแบบโต้ตอบ^{[ 11 ]}ตัวกำหนดตารางเวลาได้รับการแก้ไขในWindows Vistaเพื่อใช้รีจิสเตอร์ตัวนับรอบของโปรเซสเซอร์สมัยใหม่เพื่อติดตามจำนวนรอบ CPU ที่เธรดได้ดำเนินการอย่างแม่นยำ แทนที่จะใช้รูทีนการขัดจังหวะตัวจับเวลาช่วงเวลา^{[ 12 ]} Vista ยังใช้ตัวกำหนดตารางเวลาลำดับความสำคัญสำหรับคิว I/O เพื่อไม่ให้โปรแกรมจัดเรียงข้อมูลดิสก์และโปรแกรมอื่นๆ รบกวนการทำงานเบื้องหน้า^{[ 13 ]}

ระบบปฏิบัติการ Mac OS และ macOS แบบคลาสสิก

Mac OS 9 ใช้การจัดตารางเวลาแบบร่วมมือกันสำหรับเธรด โดยที่กระบวนการหนึ่งควบคุมเธรดแบบร่วมมือกันหลายเธรด และยังให้การจัดตารางเวลาแบบแทรกแซงสำหรับงานมัลติโปรเซสซิ่ง เคอร์เนลจัดตารางเวลางานมัลติโปรเซสซิ่งโดยใช้อัลกอริทึมการจัดตารางเวลาแบบแทรกแซง กระบวนการ Process Manager ทั้งหมดทำงานภายในงานมัลติโปรเซสซิ่งพิเศษที่เรียกว่างานสีน้ำเงินกระบวนการเหล่านั้นได้รับการจัดตารางเวลาแบบร่วมมือกันโดยใช้ อัลกอริทึมการจัดตารางเวลา แบบรอบโรบินกระบวนการหนึ่งจะมอบการควบคุมโปรเซสเซอร์ให้กับอีกกระบวนการหนึ่งโดยการเรียกฟังก์ชันบล็อกกิ้ง อย่างชัดเจน เช่น แต่ละกระบวนการมีสำเนาของ Thread ManagerWaitNextEventของตนเอง ซึ่งจัดตาราง ^เวลาเธรดของกระบวนการนั้นแบบร่วมมือกัน เธรดหนึ่งจะมอบการควบคุมโปรเซสเซอร์ให้กับอีกเธรดหนึ่งโดยการเรียกหรือ^[ 14 ^]YieldToAnyThreadYieldToThread

macOS ใช้คิวการตอบรับหลายระดับ โดยมีแถบลำดับความสำคัญสี่แถบสำหรับเธรด ได้แก่ ปกติ ลำดับความสำคัญสูงของระบบ โหมดเคอร์เนลเท่านั้น และแบบเรียลไทม์^{[ 15 ]}เธรดจะถูกกำหนดเวลาแบบแทรกแซง นอกจากนี้ macOS ยังรองรับเธรดที่กำหนดเวลาแบบร่วมมือกันในการใช้งาน Thread Manager ในCarbon อีก ด้วย ^{[ 14 ]}

เอไอเอ็กซ์

ใน AIX เวอร์ชัน 4 มีค่าที่เป็นไปได้สามค่าสำหรับนโยบายการจัดลำดับเธรด:

เข้าก่อนออกก่อน (FIFO): เมื่อเธรดที่มีนโยบายนี้ถูกจัดตารางการทำงานแล้ว เธรดนั้นจะทำงานจนเสร็จสมบูรณ์ เว้นแต่จะถูกบล็อก เธรดนั้นจะสละการควบคุม CPU โดยสมัครใจ หรือมีเธรดที่มีลำดับความสำคัญสูงกว่าพร้อมที่จะทำงาน เธรดที่มีลำดับความสำคัญคงที่เท่านั้นที่สามารถใช้นโยบายการจัดตารางการทำงานแบบ FIFO ได้
การจัดตารางเวลาแบบ Round Robin: รูปแบบนี้คล้ายกับการจัดตารางเวลาแบบ Round Robin ของ AIX เวอร์ชัน 3 ซึ่งใช้ช่วงเวลา 10 มิลลิวินาที เมื่อเธรดแบบ Round Robin ควบคุมการทำงานในช่วงท้ายของช่วงเวลาดังกล่าว เธรดนั้นจะถูกย้ายไปอยู่ท้ายสุดของคิวเธรดที่สามารถเรียกใช้งานได้ตามลำดับความสำคัญ เฉพาะเธรดที่มีลำดับความสำคัญคงที่เท่านั้นที่สามารถใช้การจัดตารางเวลาแบบ Round Robin ได้
อื่นๆ: นโยบายนี้ถูกกำหนดโดย POSIX1003.4a ว่าเป็นนโยบายที่ขึ้นอยู่กับการใช้งาน ใน AIX เวอร์ชัน 4 นโยบายนี้ถูกกำหนดให้เทียบเท่ากับ RR ยกเว้นว่าจะใช้กับเธรดที่มีลำดับความสำคัญไม่คงที่ การคำนวณค่าลำดับความสำคัญของเธรดที่กำลังทำงานใหม่ทุกครั้งที่มีการขัดจังหวะสัญญาณนาฬิกา หมายความว่าเธรดอาจสูญเสียการควบคุมเนื่องจากค่าลำดับความสำคัญของมันสูงกว่าเธรดอื่นที่สามารถเรียกใช้งานได้ นี่คือพฤติกรรมของ AIX เวอร์ชัน 3

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

AIX 5 ใช้การกำหนดตารางเวลาแบบต่อไปนี้: FIFO, รอบโรบิน และรอบโรบินแบบยุติธรรม นโยบาย FIFO มีการใช้งานที่แตกต่างกันสามแบบ: FIFO, FIFO2 และ FIFO3 นโยบายรอบโรบินเรียกว่า SCHED_RR ใน AIX และรอบโรบินแบบยุติธรรมเรียกว่า SCHED_OTHER ^{[ 16 ]}

ลินุกซ์

ลินุกซ์ 1.2

Linux 1.2 ใช้นโยบายการจัดกำหนดการแบบวนรอบ^{[ 17 ]}

ลินุกซ์ 2.2

Linux 2.2 เพิ่มคลาสการจัดกำหนดการและการสนับสนุนการประมวลผลแบบสมมาตร (SMP) ^{[ 17 ]}

ลินุกซ์ 2.4

ในLinux 2.4 ^{[ 17 ]} มีการใช้ตัวจัดตารางเวลา O (n)ที่มีคิวป้อนกลับหลายระดับพร้อมระดับความสำคัญตั้งแต่ 0 ถึง 140 โดย 0–99 สงวนไว้สำหรับงานแบบเรียลไทม์ และ 100–140 ถือเป็น ระดับงาน ที่ดีสำหรับงานแบบเรียลไทม์ ควอนตัมเวลาสำหรับการสลับกระบวนการอยู่ที่ประมาณ 200 มิลลิวินาที และสำหรับงานที่ดีอยู่ที่ประมาณ 10 มิลลิวินาที ตัวจัดตารางเวลาจะทำงานผ่านคิวการทำงานของกระบวนการที่พร้อมใช้งานทั้งหมด โดยปล่อยให้กระบวนการที่มีลำดับความสำคัญสูงสุดทำงานก่อนและทำงานผ่านช่วงเวลาของตน หลังจากนั้นจะถูกวางไว้ในคิวหมดอายุ เมื่อคิวที่ใช้งานอยู่ว่างเปล่า คิวหมดอายุจะกลายเป็นคิวที่ใช้งานอยู่ และในทางกลับกัน

อย่างไรก็ตามการแจกจ่าย Linux ระดับองค์กรบางระบบ เช่นSUSE Linux Enterprise Serverได้แทนที่ตัวกำหนดตารางเวลานี้ด้วยการพอร์ตตัวกำหนดตารางเวลา O(1) (ซึ่งได้รับการดูแลโดยAlan Coxในชุดเคอร์เนล Linux 2.4-ac ของเขา) ไปยังเคอร์เนล Linux 2.4 ที่ใช้โดยการแจกจ่ายนั้น

ลินุกซ์ 2.6.0 ถึง ลินุกซ์ 2.6.22

ในเวอร์ชัน 2.6.0 ถึง 2.6.22 เคอร์เนลใช้ตัวกำหนดตารางเวลา O(1)ที่พัฒนาโดยIngo Molnarและนักพัฒนาเคอร์เนลคนอื่นๆ อีกมากมายในระหว่างการพัฒนา Linux 2.5 สำหรับเคอร์เนลจำนวนมากในช่วงเวลานี้Con Kolivasได้พัฒนาแพตช์เซ็ตที่ปรับปรุงการโต้ตอบกับตัวกำหนดตารางเวลานี้ หรือแม้กระทั่งแทนที่ด้วยตัวกำหนดตารางเวลาของเขาเอง

ลินุกซ์ 2.6.23 ถึง ลินุกซ์ 6.5

งานของ Con Kolivas โดยเฉพาะอย่างยิ่งการนำการจัดตารางเวลาที่เป็นธรรม มาใช้ ซึ่งเรียกว่าRotating Staircase Deadline (RSDL) เป็นแรงบันดาลใจให้ Ingo Molnár พัฒนาCompletely Fair Scheduler (CFS) เพื่อทดแทนตัวจัดตารางเวลา O(1) รุ่น ก่อนหน้า โดยให้เครดิต Kolivas ในประกาศของเขา^{[ 18 ]} CFS เป็นการนำตัวจัด ตารางเวลากระบวนการ คิวที่เป็นธรรมมาใช้เป็นครั้งแรกซึ่งใช้กันอย่างแพร่หลายในระบบปฏิบัติการทั่วไป^{[ 19 ]}

CFS ใช้ขั้นตอนวิธีจัดตารางเวลาแบบคลาสสิกที่ได้รับการศึกษามาอย่างดี เรียกว่าการจัดคิวอย่างเป็นธรรม (fair queuing ) ซึ่ง คิดค้นขึ้นครั้งแรกสำหรับเครือข่ายแพ็ก เก็ต การจัดคิว อย่างเป็นธรรมเคยถูกนำมาใช้กับการจัดตารางเวลาของ CPU มาก่อนแล้วในชื่อ การจัดตาราง เวลาแบบก้าว (stride scheduling ) ตัวจัดตารางเวลา CFS แบบจัดคิวอย่างเป็นธรรมมีความซับซ้อนในการจัดตารางเวลาเท่ากับโดยที่ $N$ คือจำนวนงานในคิวการทำงานการเลือกงานสามารถทำได้ในเวลาคงที่ แต่การแทรกงานกลับเข้าไปใหม่หลังจากที่ทำงานเสร็จแล้วต้องใช้การดำเนินการ เนื่องจากคิวการทำงานถูกนำไปใช้ในรูปแบบของต้นไม้แดง-ดำ (red–black tree ) $O(\log N)$ $O(\log N)$

โปรแกรม Brain Fuck Schedulerซึ่งสร้างโดย Con Kolivas เช่นกัน เป็นอีกทางเลือกหนึ่งนอกเหนือจาก CFS

ลินุกซ์ 6.6

ในปี 2023 Peter Zijlstra เสนอให้เปลี่ยน CFS ด้วย ตัวจัดตาราง เวลาแบบกำหนดเส้นตายเสมือนที่เร็วที่สุดที่เข้าเกณฑ์ (EEVDF) ^{[ 20 ]}^{[ 21 ]}จุดมุ่งหมายคือเพื่อขจัดความจำเป็นในการใช้แพตช์ความหน่วงแฝง ของ CFS ^{[ 22 ]}

ลินุกซ์ 6.12

Linux 6.12 เพิ่มการสนับสนุนส่วนขยายตัวกำหนดเวลาที่สามารถเพิ่มได้จากพื้นที่ผู้ใช้กลไกนี้เรียกว่า sched_ext โปรแกรม eBPFสามารถโหลดลงในเคอร์เนลเพื่อใช้นโยบายการกำหนดเวลาได้^{[ 23 ]}ตัวกำหนดเวลาเหล่านี้สามารถแทนที่ตัวกำหนดเวลาเริ่มต้นได้^{[ 24 ]}

ฟรีบีเอสดี

FreeBSDใช้คิวป้อนกลับแบบหลายระดับที่มีลำดับความสำคัญตั้งแต่ 0–255 โดย 0–63 สงวนไว้สำหรับการขัดจังหวะ 64–127 สำหรับครึ่งบนของเคอร์เนล 128–159 สำหรับเธรดผู้ใช้แบบเรียลไทม์ 160–223 สำหรับเธรดผู้ใช้แบบแบ่งเวลา และ 224–255 สำหรับเธรดผู้ใช้ที่ไม่ได้ใช้งาน นอกจากนี้ เช่นเดียวกับ Linux มันใช้การตั้งค่าคิวที่ใช้งานอยู่ แต่ยังมีคิวที่ไม่ได้ใช้งานอีกด้วย^{[ 25 ]}

เน็ตบีเอสดี

NetBSDใช้คิวป้อนกลับแบบหลายระดับที่มีลำดับความสำคัญตั้งแต่ 0–223 โดย 0–63 สงวนไว้สำหรับเธรดแบบแบ่งเวลา (ค่าเริ่มต้น นโยบาย SCHED_OTHER) 64–95 สำหรับเธรดผู้ใช้ที่เข้าสู่พื้นที่เคอร์เนล 96–128 สำหรับเธรดเคอร์เนล 128–191 สำหรับเธรดเรียลไทม์ของผู้ใช้ (นโยบาย SCHED_FIFO และ SCHED_RR) และ 192–223 สำหรับ การ ขัดจังหวะ ซอฟต์แวร์

โซลาริส

Solarisใช้คิวป้อนกลับแบบหลายระดับที่มีลำดับความสำคัญตั้งแต่ 0 ถึง 169 ลำดับความสำคัญ 0–59 สงวนไว้สำหรับเธรดแบบแบ่งเวลา 60–99 สำหรับเธรดระบบ 100–159 สำหรับเธรดแบบเรียลไทม์ และ 160–169 สำหรับการขัดจังหวะที่มีลำดับความสำคัญต่ำ แตกต่างจาก Linux ^{[ 25 ]}เมื่อกระบวนการเสร็จสิ้นโดยใช้ควอนตัมเวลา กระบวนการนั้นจะได้รับลำดับความสำคัญใหม่และใส่กลับเข้าไปในคิว Solaris 9 ได้แนะนำคลาสการจัดกำหนดการใหม่สองคลาส ได้แก่ คลาสลำดับความสำคัญคงที่และคลาสส่วนแบ่งที่เป็นธรรม เธรดที่มีลำดับความสำคัญคงที่จะมีช่วงลำดับความสำคัญเดียวกันกับคลาสแบบแบ่งเวลา แต่ลำดับความสำคัญของเธรดเหล่านั้นจะไม่ถูกปรับแบบไดนามิก คลาสการจัดกำหนดการที่เป็นธรรมใช้ส่วนแบ่ง CPU เพื่อจัดลำดับความสำคัญของเธรดสำหรับการตัดสินใจในการจัดกำหนดการ ส่วนแบ่ง CPU บ่งชี้สิทธิ์ในทรัพยากร CPU โดยจะถูกจัดสรรให้กับชุดของกระบวนการ ซึ่งเรียกรวมกันว่าโครงการ^{[ 7 ]}

สรุป

ระบบปฏิบัติการ	การยกเลิกสิทธิ์	อัลกอริทึม
อามิกา โอเอส	ใช่	การจัดตารางเวลาแบบหมุนเวียนตามลำดับความสำคัญ
ฟรีบีเอสดี	ใช่	คิวข้อเสนอแนะหลายระดับ
เคอร์เนลลินุกซ์ก่อนเวอร์ชัน 2.6.0	ใช่	คิวข้อเสนอแนะหลายระดับ
เคอร์เนลลินุกซ์ 2.6.0–2.6.23	ใช่	ตัวกำหนดตารางเวลา O(1)
เคอร์เนลลินุกซ์ 2.6.23–6.6	ใช่	โปรแกรมจัดตารางเวลาที่ยุติธรรมอย่างสมบูรณ์
เคอร์เนลลินุกซ์ 6.6 และเวอร์ชันที่ใหม่กว่า	ใช่	การจัดตารางเวลาแบบเสมือนจริงก่อนกำหนดเวลาที่มีสิทธิ์เร็วที่สุด (EEVDF)
ระบบปฏิบัติการ Mac OS รุ่นคลาสสิกก่อนปี 9	ไม่มี	ตัวจัดตารางเวลาแบบร่วมมือ
แมคโอเอส 9	บาง	ตัวจัดตารางเวลาแบบแย่งชิงสำหรับงาน MP และแบบร่วมมือสำหรับกระบวนการและเธรด
ระบบปฏิบัติการ macOS	ใช่	คิวข้อเสนอแนะหลายระดับ
เน็ตบีเอสดี	ใช่	คิวข้อเสนอแนะหลายระดับ
โซลาริส	ใช่	คิวข้อเสนอแนะหลายระดับ
วินโดวส์ 3.1x	ไม่มี	ตัวจัดตารางเวลาแบบร่วมมือ
Windows 95 , 98 , Me	ครึ่ง	ตัวจัดตารางเวลาแบบแย่งชิงสำหรับกระบวนการ 32 บิต และแบบร่วมมือสำหรับกระบวนการ 16 บิต
ระบบปฏิบัติการ Windows NT (รวมถึง 2000, XP, Vista, 7 และ Server)	ใช่	คิวข้อเสนอแนะหลายระดับ

ดูเพิ่มเติม

Notes

^C. L., Liu; James W., Layland (January 1973). "Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment". Journal of the ACM. 20 (1). ACM: 46–61. doi:10.1145/321738.321743. S2CID 207669821. We define the response time of a request for a certain task to be the time span between the request and the end of the response to that request.
^Kleinrock, Leonard (1976). Queueing Systems, Vol. 2: Computer Applications (1 ed.). Wiley-Interscience. p. 171. ISBN 047149111X. For a customer requiring x sec of service, his response time will equal his service time x plus his waiting time.
^Feitelson, Dror G. (2015). Workload Modeling for Computer Systems Performance Evaluation. Cambridge University Press. Section 8.4 (Page 422) in Version 1.03 of the freely available manuscript. ISBN 9781107078239. Retrieved 2015-10-17. if we denote the time that a job waits in the queue by t_w, and the time it actually runs by t_r, then the response time is r = t_w + t_r.
^Silberschatz, Abraham; Galvin, Peter Baer; Gagne, Greg (2012). Operating System Concepts (9 ed.). Wiley Publishing. p. 187. ISBN 978-0470128725. In an interactive system, turnaround time may not be the best criterion. Often, a process can produce some output fairly early and can continue computing new results while previous results are being output to the user. Thus, another measure is the time from the submission of a request until the first response is produced. This measure, called response time, is the time it takes to start responding, not the time it takes to output the response.
^Paul Krzyzanowski (2014-02-19). "Process Scheduling: Who gets to run next?". cs.rutgers.edu. Archived from the original on 2023-08-02. Retrieved 2023-06-19.
^Raphael Finkel (1988). "Chapter 2: Time Management". An Operating Systems Vade Mecum. Prentice Hall. p. 27.
^ ^a ^b ^c Abraham Silberschatz ; Peter Baer Galvin; Greg Gagne (2013). แนวคิดระบบปฏิบัติการเล่ม 9. John Wiley & Sons, Inc. ISBN 978-1-118-06333-0.
^ Robert Kroeger (2004). "การควบคุมการเข้าถึงสำหรับแอปพลิเคชันเรียลไทม์ที่เขียนโดยอิสระ" . UWSpace. http://hdl.handle.net/10012/1170 . ส่วน "2.6 การควบคุมการเข้าถึง". หน้า 33.
^ Guowang Miao ; Jens Zander; Ki Won Sung; Ben Slimane (2016). พื้นฐานของเครือข่ายข้อมูลเคลื่อนที่ . สำนักพิมพ์มหาวิทยาลัยเคมบริดจ์ . ISBN 978-1107143210.
^ระบบปฏิบัติการ Windows รุ่นแรกๆที่ Wayback Machine (ดัชนีเก็บถาวร)
^ Sriram Krishnan. "เรื่องราวของโปรแกรมจัดตารางเวลาสองตัวใน Windows NT และ Windows CE" . เก็บถาวรจากต้นฉบับเมื่อวันที่ 22 กรกฎาคม 2012
^ "การบริหารจัดการ Windows: ภายในเคอร์เนลของ Windows Vista: ตอนที่ 1" . Technet.microsoft.com . 2016-11-14 . สืบค้นเมื่อ2016-12-09 .
^ "สำเนาที่เก็บถาวร" . blog.gabefrost.com . เก็บถาวรจากต้นฉบับเมื่อวันที่ 19 กุมภาพันธ์ 2008 . เรียกดูเมื่อวันที่ 15 มกราคม 2022 .{{cite web}}: CS1 maint: archived copy as title ( link )
^ ^a ^b "บันทึกทางเทคนิค TN2028: สถาปัตยกรรมมัลติเธรด" . developer.apple.com . สืบค้นเมื่อ2019-01-15 .
^ "การจัดตารางเวลา Mach และอินเทอร์เฟซเธรด" . developer.apple.com . สืบค้นเมื่อ2019-01-15 .
^ [1] เก็บถาวรเมื่อ 2011-08-11 ที่ Wayback Machine
^ ^a^b^c Jones, M. (2018-09-18) [เผยแพร่ครั้งแรกเมื่อ 2009-12-14]. "ภายในตัวจัดตารางเวลาที่ยุติธรรมอย่างสมบูรณ์ของ Linux 2.6" developer.ibm.com . สืบค้นเมื่อ2024-02-07 .
^ Molnár, Ingo (13 เมษายน 2550). "[แพทช์] แกนหลักของตัวกำหนดตารางเวลาแบบโมดูลาร์และตัวกำหนดตารางเวลาที่ยุติธรรมอย่างสมบูรณ์ [CFS]" . linux-kernel (รายชื่อผู้รับจดหมาย).
^ Tong Li; Dan Baumberger; Scott Hahn. "การจัดตารางเวลาที่เป็นธรรมสำหรับมัลติโปรเซสเซอร์ที่มีประสิทธิภาพและปรับขนาดได้โดยใช้ Round-Robin แบบถ่วงน้ำหนักแบบกระจาย" (PDF) . Happyli.org . สืบค้นเมื่อ2016-12-09 .
^ "EEVDF Scheduler อาจพร้อมใช้งานร่วมกับ Linux 6.6" Phoronix สืบค้นเมื่อ31 สิงหาคม 2023
^ "EEVDF Scheduler ผสานรวมเข้ากับ Linux 6.6 แล้ว การจัดตารางเวลาคลัสเตอร์ไฮบริดของ Intel ถูกนำกลับมาใช้ใหม่" . www.phoronix.com . สืบค้นเมื่อ2024-02-07 .
^ "ตัวจัดตารางเวลา CPU EEVDF สำหรับ Linux [LWN.net]" . LWN.net . สืบค้นเมื่อ2023-08-31 .
^ "Sched_ext ผสานรวมสำหรับ Linux 6.12 - นโยบายการจัดตารางเวลาเป็นโปรแกรม BPF" . www.phoronix.com . สืบค้นเมื่อ2025-02-10 .
^ "ตัวกำหนดตารางเวลา CPU แบบเสียบปลั๊กได้ - openSUSE Wiki" . en.opensuse.org . สืบค้นเมื่อ2025-02-10 .
^ ^a ^b "การเปรียบเทียบเคอร์เนลของ Solaris, Linux และ FreeBSD" (PDF) . เก็บถาวรจากต้นฉบับ(PDF)เมื่อวันที่ 7 สิงหาคม 2551

อ่านเพิ่มเติม

ระบบปฏิบัติการ: สามส่วนง่ายๆโดย Remzi H. Arpaci-Dusseau และ Andrea C. Arpaci-Dusseau สำนักพิมพ์ Arpaci-Dusseau Books, 2014 บทที่เกี่ยวข้อง: การจัดตารางเวลา: บทนำคิวป้อนกลับหลายระดับ การจัดตารางเวลาตามสัดส่วนการจัดตารางเวลาสำหรับโปรเซสเซอร์หลายตัว
การอภิปรายโดยสังเขปเกี่ยวกับอัลกอริธึมการจัดตารางงาน
ทำความเข้าใจเคอร์เนลของลินุกซ์: บทที่ 10 การจัดตารางเวลาของกระบวนการ
Kerneltrap: บทความเกี่ยวกับตัวกำหนดตารางเวลาของเคอร์เนล Linux
การตรวจสอบและปรับแต่ง CPU ของ AIX
บทนำของ Josh Aas เกี่ยวกับการใช้งานตัวจัดตารางเวลา CPU ใน Linux 2.6.8.1
Peter Brucker, Sigrid Knust. ผลลัพธ์ความซับซ้อนสำหรับปัญหาการจัดตารางเวลา[2]
TORSCHE Scheduling Toolbox สำหรับ Matlabเป็นชุดเครื่องมือสำหรับการจัดตารางเวลาและอัลกอริธึมกราฟ
การสำรวจเกี่ยวกับการจัดตารางเวลาแพ็กเก็ตของเครือข่ายโทรศัพท์มือถือ
การจัดการคลัสเตอร์ขนาดใหญ่ที่ Google ด้วย Borg

[liu1973-1] C. L., Liu; James W., Layland (January 1973). "Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment". Journal of the ACM. 20 (1). ACM: 46–61. doi:10.1145/321738.321743. S2CID 207669821. We define the response time of a request for a certain task to be the time span between the request and the end of the response to that request.

[kleinrock1976-2] Kleinrock, Leonard (1976). Queueing Systems, Vol. 2: Computer Applications (1 ed.). Wiley-Interscience. p. 171. ISBN 047149111X. For a customer requiring x sec of service, his response time will equal his service time x plus his waiting time.

[feitelson2014-3] Feitelson, Dror G. (2015). Workload Modeling for Computer Systems Performance Evaluation. Cambridge University Press. Section 8.4 (Page 422) in Version 1.03 of the freely available manuscript. ISBN 9781107078239. Retrieved 2015-10-17. if we denote the time that a job waits in the queue by t_w, and the time it actually runs by t_r, then the response time is r = t_w + t_r.

[silberschatz2012-4] Silberschatz, Abraham; Galvin, Peter Baer; Gagne, Greg (2012). Operating System Concepts (9 ed.). Wiley Publishing. p. 187. ISBN 978-0470128725. In an interactive system, turnaround time may not be the best criterion. Often, a process can produce some output fairly early and can continue computing new results while previous results are being output to the user. Thus, another measure is the time from the submission of a request until the first response is produced. This measure, called response time, is the time it takes to start responding, not the time it takes to output the response.

[5] Paul Krzyzanowski (2014-02-19). "Process Scheduling: Who gets to run next?". cs.rutgers.edu. Archived from the original on 2023-08-02. Retrieved 2023-06-19.

[6] Raphael Finkel (1988). "Chapter 2: Time Management". An Operating Systems Vade Mecum. Prentice Hall. p. 27.

[Galvin-7] Abraham Silberschatz ; Peter Baer Galvin; Greg Gagne (2013). แนวคิดระบบปฏิบัติการเล่ม 9. John Wiley & Sons, Inc. ISBN 978-1-118-06333-0.

[8] Robert Kroeger (2004). "การควบคุมการเข้าถึงสำหรับแอปพลิเคชันเรียลไทม์ที่เขียนโดยอิสระ" . UWSpace. http://hdl.handle.net/10012/1170 . ส่วน "2.6 การควบคุมการเข้าถึง". หน้า 33.

[Miao-9] Guowang Miao ; Jens Zander; Ki Won Sung; Ben Slimane (2016). พื้นฐานของเครือข่ายข้อมูลเคลื่อนที่ . สำนักพิมพ์มหาวิทยาลัยเคมบริดจ์ . ISBN 978-1107143210.

[10] ระบบปฏิบัติการ Windows รุ่นแรกๆที่ Wayback Machine (ดัชนีเก็บถาวร)

[11] Sriram Krishnan. "เรื่องราวของโปรแกรมจัดตารางเวลาสองตัวใน Windows NT และ Windows CE" . เก็บถาวรจากต้นฉบับเมื่อวันที่ 22 กรกฎาคม 2012

[12] "การบริหารจัดการ Windows: ภายในเคอร์เนลของ Windows Vista: ตอนที่ 1" . Technet.microsoft.com . 2016-11-14 . สืบค้นเมื่อ2016-12-09 .

[13] "สำเนาที่เก็บถาวร" . blog.gabefrost.com . เก็บถาวรจากต้นฉบับเมื่อวันที่ 19 กุมภาพันธ์ 2008 . เรียกดูเมื่อวันที่ 15 มกราคม 2022 .{{cite web}}: CS1 maint: archived copy as title ( link )

[appletn2028-14] "บันทึกทางเทคนิค TN2028: สถาปัตยกรรมมัลติเธรด" . developer.apple.com . สืบค้นเมื่อ2019-01-15 .

[15] "การจัดตารางเวลา Mach และอินเทอร์เฟซเธรด" . developer.apple.com . สืบค้นเมื่อ2019-01-15 .

[16] [1] เก็บถาวรเมื่อ 2011-08-11 ที่ Wayback Machine

[:0-17] Jones, M. (2018-09-18) [เผยแพร่ครั้งแรกเมื่อ 2009-12-14]. "ภายในตัวจัดตารางเวลาที่ยุติธรรมอย่างสมบูรณ์ของ Linux 2.6" developer.ibm.com . สืบค้นเมื่อ2024-02-07 .

[18] Molnár, Ingo (13 เมษายน 2550). "[แพทช์] แกนหลักของตัวกำหนดตารางเวลาแบบโมดูลาร์และตัวกำหนดตารางเวลาที่ยุติธรรมอย่างสมบูรณ์ [CFS]" . linux-kernel (รายชื่อผู้รับจดหมาย).

[dwrr-19] Tong Li; Dan Baumberger; Scott Hahn. "การจัดตารางเวลาที่เป็นธรรมสำหรับมัลติโปรเซสเซอร์ที่มีประสิทธิภาพและปรับขนาดได้โดยใช้ Round-Robin แบบถ่วงน้ำหนักแบบกระจาย" (PDF) . Happyli.org . สืบค้นเมื่อ2016-12-09 .

[20] "EEVDF Scheduler อาจพร้อมใช้งานร่วมกับ Linux 6.6" Phoronix สืบค้นเมื่อ31 สิงหาคม 2023

[21] "EEVDF Scheduler ผสานรวมเข้ากับ Linux 6.6 แล้ว การจัดตารางเวลาคลัสเตอร์ไฮบริดของ Intel ถูกนำกลับมาใช้ใหม่" . www.phoronix.com . สืบค้นเมื่อ2024-02-07 .

[22] "ตัวจัดตารางเวลา CPU EEVDF สำหรับ Linux [LWN.net]" . LWN.net . สืบค้นเมื่อ2023-08-31 .

[23] "Sched_ext ผสานรวมสำหรับ Linux 6.12 - นโยบายการจัดตารางเวลาเป็นโปรแกรม BPF" . www.phoronix.com . สืบค้นเมื่อ2025-02-10 .

[24] "ตัวกำหนดตารางเวลา CPU แบบเสียบปลั๊กได้ - openSUSE Wiki" . en.opensuse.org . สืบค้นเมื่อ2025-02-10 .

[opensolaris-queue-25] "การเปรียบเทียบเคอร์เนลของ Solaris, Linux และ FreeBSD" (PDF) . เก็บถาวรจากต้นฉบับ(PDF)เมื่อวันที่ 7 สิงหาคม 2551

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

เวลา

[ 15 ]

[ 16 ]

[ 18 ]

[ 19 ]

[ 20 ]

[ 21 ]

[ 22 ]

[ 23 ]

[ 24 ]

[ 25 ]