时间片轮转调度
外观
![](http://upload.wikimedia.org/wikipedia/commons/thumb/7/76/Round_Robin_Schedule_Example.jpg/350px-Round_Robin_Schedule_Example.jpg)
时间片轮转调度(Round-Robin Scheduling) 是进程和网络调度程序常用的算法之一。[1] 这一方法将相等长度的时间片按照不变的顺序依次分配给每个进程[2],且在处理所有进程时不考虑任何优先级。这一算法简单并易于实现,并且不会产生饥饿问题。时间片轮转调度可以应用于其他调度问题,例如计算机网络中的数据包调度。它是一个操作系统概念。[3]
该算法的名称来自于其他领域通用的循环制原则,即每个参与者轮流获得相同分量的物品。
进程调度
[编辑]为了公平地调度进程,循环调度程序通常采用分时机制,为每个作业分配一个时间片或时间量[4] (CPU 时间),如果用完这一分配的时间还没有完成,则中断该进程。下次为该进程分配时间时,该进程将恢复执行。如果进程在其时间片内终止或将其状态更改为等待(或阻塞),则调度程序会选择就绪队列中的第一个进程来执行。
循环算法是一种抢占式算法,因为一旦时间片用尽,调度程序就会强制性的暂停进程的执行。
例如,如果时间片为100毫秒,而进程1完成的总时间为250毫秒,则循环调度程序将在100毫秒后暂停该进程,并让其他进程在CPU上占用时间。一旦其他线程都使用过一次相同的时间片(100毫秒),进程1将获得另一次CPU时间分配。这个过程一直将持续循环到进程结束并且不需要更多的CPU时间。
例子
[编辑]在时间片长度为100毫秒的系统中,考虑下表所列举的进程:
进程名称 | 开始时间(ms) | 执行时间(ms) |
---|---|---|
P0 | 0 | 250 |
P1 | 50 | 170 |
P2 | 130 | 75 |
P3 | 190 | 100 |
P4 | 210 | 130 |
P5 | 350 | 50 |
![时间片轮转调度](http://upload.wikimedia.org/wikipedia/commons/thumb/5/50/RoundRobin.jpg/400px-RoundRobin.jpg)
- ^ Arpaci-Dusseau, Remzi H.; Arpaci-Dusseau, Andrea C., Operating Systems: Three Easy Pieces [Chapter: Scheduling Introduction] (PDF), Arpaci-Dusseau Books, 2014 [2022-12-28], (原始内容存档 (PDF)于2018-10-13)
- ^ Stallings, William. Operating Systems: Internals and Design Principles. Pearson. 2015: 409. ISBN 978-0-13-380591-8.
- ^ Nash, Stacey L. Best scheduling software of 2022. Popular Science. 2022-06-11 [2022-07-07]. (原始内容存档于2022-12-28) (英语).
- ^ Silberschatz, Abraham; Galvin, Peter B.; Gagne, Greg. Process Scheduling 8th. John Wiley & Sons (Asia). 2010: 194. ISBN 978-0-470-23399-3.
5.3.4 Round Robin Scheduling