首页 > 编程笔记 > 操作系统笔记

Linux进程调度策略(CFS调度)详解

Linux 进程调度有一个有趣历史。在 2.5 版本之前,Linux 内核采用传统 UNIX 调度算法。然而,由于这个算法并没有考虑 SMP 系统,因此它并不足够支持 SMP 系统。此外,当有大量的可运行进程时,系统性能表现欠佳。

在内核 V2.5 中,调度程序进行了大改,采用了称为 O(1) 的调度算法,它的运行时间为常量,与系统内任务数量无关。O(1) 调度程序也增加了对 SMP 系统的支持,包括处理器亲和性和处理器间的负载平衡。然而,在实践中,虽然在 SMP 系统上 O(1) 调度程序具有出色的性能,但是在许多桌面计算机系统上交互进程的响应时间却欠佳。

在内核 V2.6 的开发中,调度程序再次修改;在内核 V2.6.23 的发布中,完全公平调度程序(CFS)成为默认的 Linux 调度算法。

Linux 系统的调度基于调度类。每个类都有一个特定优先级。内核针对不同的调度类,采用不同的调度算法,以便满足系统与进程的需要。例如,用于 Linux 服务器的调度准则,也许不同于移动设备的。为了确定应运行哪个进程,调度程序从最高优先级调度类中选择具有最高优先级的任务。

Linux 标准内核实现两个调度类:采用 CFS 调度算法的默认调度类实时调度类。这里分别讨论这些。当然,新调度类也可添加。

CFS 调度程序并不采用严格规则来为一个优先级分配某个长度的时间片,而是为每个任务分配一定比例的 CPU 处理时间。每个任务分配的具体比例是根据友好值来计算的。友好值的范围从 -20 到 +19,数值较低的友好值表示较高的相对优先级。具有较低友好值的任务,与具有较高友好值的任务相比,会得到更高比例的处理器处理时间。默认友好值为 0。

友好一词源自如下想法:当一个任务增加了它的友好值,如从 0 至 +10,该任务通过降低优先级,进而对其他任务更加友好。

CFS 没有使用离散的时间片,而是采用目标延迟,这是每个可运行任务应当运行一次的时间间隔。根据目标延迟,按比例分配 CPU 时间。除了默认值和最小值外,随着系统内的活动任务数量超过了一定阈值,目标延迟可以增加。

CFS 调度程序没有直接分配优先级。相反,它通过每个任务的变量 vruntime 以便维护虚拟运行时间,进而记录每个任务运行多久。虚拟运行时间与基于任务优先级的衰减因子有关,更低优先级的任务比更高优先级的任务具有更高衰减速率。对于正常优先级的任务(友好值为 0),虚拟运行时间与实际物理运行时间是相同的。

因此,如果一个默认优先级的任务运行 200ms,则它的虚拟运行时间也为 200ms。然而,如果一个较低优先级的任务运行 200ms,则它的虚拟运行时间将大于 200ms。同样,如果一个更高优先级的任务运行 200ms,则它的虚拟运行时间将小于 200ms。当决定下步运行哪个任务时,调度程序只需选择具有最小虚拟运行时间的任务。此外,一个更高优先级的任务如成为可运行,就会抢占低优先级任务。

下面分析一下 CFS 调度程序是如何工作的。假设有两个任务,它们具有相同的友好值。一个任务是 I/O 密集型而另一个为 CPU 密集型。通常,I/O 密集型任务在运行很短时间后就会阻塞以便等待更多的 I/O;而 CPU 密集型任务只要有在处理器上运行的机会,就会用完它的时间片。

因此,I/O 密集型任务的虚拟运行时间最终将会小于 CPU 密集型任务的,从而使得 I/O 密集型任务具有更高的优先级。这时,如果 CPU 密集型任务在运行,而 I/O 密集型任务变得有资格可以运行(如该任务所等待的 I/O 已成为可用),那么 I/O 密集型任务就会抢占 CPU 密集型任务。

Linux 也实现了实时调度。采用 SCHED_FIFO 或 SCHED_RR 实时策略来调度的任何任务,与普通(非实时的)任务相比,具有更高的优先级。

Linux 采用两个单独的优先级范围,一个用于实时任务,另一个用于正常任务。实时任务分配的静态优先级为 0〜99,而正常任务分配的优先级为 100〜139。

这两个值域合并成为一个全局的优先级方案,其中较低数值表明较高的优先级。正常任务,根据它们的友好值,分配一个优先级;这里 -20 的友好值映射到优先级 100,而 +19 的友好值映射到 139。图 1 显示了这个方案。

Linux系统的调度优先级
图 1 Linux系统的调度优先级

CFS 性能

Linux CFS 调度程序釆用高效算法,以便选择运行下个任务。每个可运行的任务放置在红黑树上(这是一种平衡的、二分搜索树,它的键是基于虚拟运行时间的)。这种树如下图所示:

红黑树
图 2 红黑树
 
当一个任务变成可运行时,它被添加到树上。当一个任务变成不可运行时(例如,当阻塞等待 I/O 时),它从树上被删除。一般来说,得到较少处理时间的任务(虚拟运行时间较小)会偏向树的左侧;得到较多处理时间的任务会偏向树的右侧。

根据二分搜索树的性质,最左侧的结点有最小的键值;从 CFS 调度程序角度而言,这也是具有最高优先级的任务。由于红黑树是平衡的,找到最左侧结点会需要 O(lgN) 操作(这里 N 为树内结点总数)。不过,为高效起见,Linux 调度程序将这个值缓存在变量 rb_leftmost 中,从而确定哪个任务运行只需检索缓存的值。

所有教程

优秀文章