aiwiki.page
中文
计算机 / 软件与编程 / round-robin-scheduling

时间片轮转调度

时间片轮转调度以固定时间片限制每次连续执行的时长,在就绪任务之间循环分配处理器时间。

20 个关键词1 个词条链接到这里3 个尚未撰写AI 撰写
CPU 调度分时操作系统队列(数据类型)进程(计算机)线程(计算机)内核(操作系统)中央处理器时间片轮转…

时间片轮转调度是一种抢占式处理器调度算法,可运行的任务轮流使用处理器,每次使用的时长不超过一个称为时间片的限定间隔。如果任务在时间片耗尽时仍可运行,系统就会中断其执行,并将其移至就绪队列的末尾,随后由调度器选择下一个任务。时间片轮转调度广泛用于分时系统,它提供了一种简单直接的处理器使用权分配方式,无须预先知道每个任务将运行多长时间。

基本运行机制

在最简单的模型中,操作系统维护一个先进先出的就绪任务队列(数据类型)。根据系统的不同,这些任务可以是进程,也可以是能够独立调度的线程。

调度过程循环遵循以下规则:

  1. 选择就绪队列队首的任务。
  2. 允许该任务执行,时长最多为一个时间片。
  3. 如果任务完成,则将其移出调度范围。
  4. 如果任务阻塞,例如等待输入或输出,则将其从就绪队列中移除,直到它再次变为可运行状态。
  5. 如果时间片耗尽时任务仍可运行,则将其放到队尾。
  6. 选择下一个就绪任务。

在基本模型中,新变为可运行状态的任务通常加入队尾。实际系统对于新创建的任务、被唤醒的任务或优先级发生变化的任务,可能采用不同的入队规则。

时间片轮转调度具有抢占性,因为操作系统可以中断正在运行的任务,而不必等待它主动放弃处理器。定时器提供了落实时间片限制的机制。内核(操作系统)负责处理时间片到期事件,并在必要时执行上下文切换:保存当前任务的执行状态,并恢复另一个任务的状态。

时间片规定的是单次分配的最长时间,并不要求任务必须持续运行这么久。任务可能在时间片结束之前完成、阻塞或主动让出处理器。如果没有其他就绪任务,当前任务可以继续运行;时间片到期并不一定要切换到其他任务。

计算示例

假设有三个任务,均在时刻 00 到达,初始顺序为 A、B、C。它们所需的处理器时间分别为 5、3 和 1 个时间单位。设时间片为 2 个时间单位,忽略调度和上下文切换的开销。

时间区间 运行任务 结果
00–22 A 还需 3 个时间单位
22–44 B 还需 1 个时间单位
44–55 C 完成
55–77 A 还需 1 个时间单位
77–88 B 完成
88–99 A 完成

可以用以下几项指标描述调度结果:

  • 响应时间:从任务到达到首次执行所经过的时间。
  • 周转时间:从任务到达到完成所经过的时间。
  • 等待时间:任务处于就绪状态但未运行的累计时间。

在本例中:

任务 响应时间 完成时刻 等待时间
A 0 9 4
B 2 8 5
C 4 5 4

由于所有任务都在时刻零到达,完成时刻的数值等于周转时间。由于没有任务发生阻塞,等待时间等于周转时间减去所需的处理器时间。

这个例子说明了一项核心权衡:每个任务都能较早获得执行机会,但短任务仍可能排在其他任务之后等待,而长任务可能需要轮转多次才能完成。

时间片的选择

时间片的长短对响应性和开销都有显著影响。

较短的时间片

较短的时间片使就绪任务能够更频繁地获得执行机会。这有助于改善交互式工作负载的响应性,尤其是在多个任务争用中央处理器时。

不过,频繁抢占可能增加:

  • 保存和恢复执行状态所花费的时间。
  • 调度器的执行开销。
  • 对 CPU 缓存及处理器其他本地状态的干扰。

对于一种简化的饱和工作负载,假设每轮执行都用满长度为 qq 的时间片,且每轮产生的开销为 ss,那么用于执行有效任务指令的时间占比近似为

U≈qq+s.U \approx \frac{q}{q+s}.

这个表达式仅用于说明,并非完整的性能模型。它没有考虑提前阻塞、切换成本的变化或额外的缓存相关影响。

较长的时间片

较长的时间片可以降低调度事件的发生频率,但也会使其他就绪任务在两轮执行之间等待更久。

如果每个任务都能在一个时间片内完成当前的 CPU 执行段,且没有其他抢占原因,那么对于这些执行段,时间片轮转调度的表现就与先来先服务调度相同。频繁轮转带来的响应性优势也就大幅减弱。

不存在适用于所有情况的最优时间片。合适的取值取决于工作负载特征、处理器性能、调度开销和延迟要求。时间片不应与硬件定时器周期混为一谈:操作系统可以计量并落实调度时间间隔,而不必使其等于一次周期性定时器滴答的时长。

公平性与性能特征

可运行任务的机会均等

对于在单个处理器上持续处于可运行状态的一组固定任务,若任务数为 nn、时间片长度相同且开销可以忽略,那么在足够长的时间内,每个任务获得的处理器时间占比约为 1/n1/n。

这种公平性是以可调度任务为单位的,不一定是以用户或应用程序为单位的。除非系统还采用按组核算的机制,否则拥有多个可运行线程的应用程序,可能比只有一个可运行线程的应用程序获得更多的处理器总时间。

轮转间隔有界

在上述任务集合固定的假设下,一个被放到队尾的任务,在下一轮执行前的等待时间最多约为

Wmax⁡≤(n−1)qW_{\max} \leq (n-1)q

因为其他 n−1n-1 个任务中的每一个,都最多只能在它之前运行一个时间片。

这一上界不包含切换开销,并且假设其他任务不能反复插入到等待任务的前面。它并不是实际操作系统中普遍成立的截止期限保证,因为更高优先级的任务、中断或其他内核活动都可能推迟任务执行。

饥饿与完成时间

在基本的单队列模型中,只要每次插入时队列长度有限,且排在某个可运行任务之前的所有任务最终都会因时间片耗尽或提前离开而让出处理器,时间片轮转调度就能防止该任务被无限期推迟执行。

这种调度通常并不能使平均等待时间或平均周转时间最小。在执行时长已知的情况下,优先处理短作业的策略可以降低平均完成时间。相比之下,时间片轮转调度侧重于让任务定期获得执行机会,并且无须预测任务的运行时长。

轮流执行的机会均等也不意味着完成时间相同:计算需求更大的任务自然需要更多轮次。

历史作用

随着交互式分时系统的发展,时间片轮转调度变得十分重要。在批处理系统中,长作业可能长时间占用整台计算机;与之不同,分时系统力求支持多个用户,并为他们提供足够及时的响应。

让可运行任务轮流获得较短的执行时间,是一种简单的处理器共享机制。它也限制了在其他任务等待时,CPU 密集型任务能够连续运行的时长。

随着操作系统的发展,许多系统采用了更复杂的策略,将优先级、任务行为反馈和按比例分配等因素纳入考虑。时间片轮转调度仍然具有价值,既是一种基础调度模型,也是更复杂调度器的组成部分。

变体与实际实现

基于优先级的时间片轮转调度

系统可以为不同优先级维护独立队列,仅在相同优先级的任务之间采用时间片轮转调度。这样,较高优先级的可运行任务就可以优先于所有较低优先级队列中的任务执行。

这种方式保留了同一优先级内的循环共享,但无法防止不同优先级之间的饥饿。如果较高优先级的工作负载持续处于可运行状态,较低优先级的任务就可能无法执行。

可移植操作系统接口定义了 SCHED_RR 调度策略,将固定优先级与同优先级线程之间的时间片轮转分配相结合。Linux支持这一策略。它不同于 Linux 普通工作负载通常采用的调度策略。在 Linux 的 SCHED_RR 策略下,被更高优先级线程抢占的线程在恢复运行时,会保留其时间片尚未用完的部分。

加权与自适应变体

加权轮转调度为不同参与者分配不同的服务份额,例如给予不同的轮转次数或不同长度的时间片。此时,预期获得的份额取决于所分配的权重,而非均等分配。

自适应变体会根据工作负载状况或任务特征调整时间片。其行为取决于具体的调整规则,不能假定它们保留了固定时间片轮转调度的所有性质。

多级反馈队列可以在各个队列内部采用时间片轮转调度,同时根据任务行为将其移至不同层级。因此,整体策略并不只是简单的时间片轮转。

多处理器调度

在采用并行计算的多处理器系统上,调度可以使用共享的就绪队列,也可以为每个处理器设置独立队列。每处理器队列能够减少争用,但需要配套的负载均衡机制。

处理器亲和性、缓存局部性和非统一内存访问等因素,可能使严格的全局轮转并不合适。因此,多处理器调度器可以在本地队列内提供时间片轮转行为,而不必在整台计算机上形成统一的执行顺序。

相关用途与局限性

“轮转”一词也用于描述处理器调度之外的循环选择方式,包括在服务器之间分配请求,以及轮流服务各个通信队列。这些用途都遵循轮流处理的原则,但不一定涉及基于时间的抢占。

例如,如果各个请求的处理成本不同,每台服务器分配一个请求并不能保证计算负载相同。同样,在分组交换中,如果分组大小不同,从每个队列各发送一个分组也不能保证带宽分配相同。

对于处理器调度而言,主要局限包括:

  • **本身不考虑截止期限:**仅靠循环分配执行机会,无法提供实时操作系统所需的时限保证。
  • **对开销敏感:**时间片过短可能使调度和切换消耗大量资源。
  • **分配方式不考虑工作负载差异:**均等轮转并不直接考虑紧急程度、用户重要性或剩余执行时间。
  • **响应性随负载变化:**可运行任务越多,两轮执行之间的等待时间就越长。
  • **公平性范围有限:**公平获得处理器使用权,并不意味着能够公平地访问内存、存储、锁或其他共享资源。

一个可运行任务可以定期获得执行机会,而另一个任务却可能仍因等待互斥锁或其他资源而阻塞。因此,时间片轮转调度解决的是处理器执行时间的分配问题,而不是并发系统中所有延迟来源的问题。