Linux进程调度:完全公平调度器CFS

对于分时操作系统来说,表面上看起来同时多个进程在运行,其实系统内部同一时间只有一个进程在运行,但进程是以比较快的速度在切换。这样就引入了进程切换和进程调度的概念了。进程调度应该是操作系统的核心功能了,它非常的复杂。

尽管刚出Linux开发为的是桌面操作系统,但现在服务器,嵌入式设备,个人pc都会使用它,不同领域对进程调度的差异非常大,所以要考虑整体的平衡性。Linux进程在调度器中被分为三种:

交互式进程:大量的人机交互,所以会有大量的睡眠状态,等待用户操作。例如:编辑器,这类进程需要比较高的响应速度。

批处理进程:这类进程需要大量的CPU资源,但是响应延迟可以忍受,比如:视频编码,算法;

实时进程:对调度延迟要求最高。比如:视频播放

在Linux中,线程和进程一视同仁,所以讲到进程调度,也包含了线程调度。

Linux调度器的简史

Linux进程调度,有一段非常有趣的历史。在2.5版本之前,Linux采用传统的UNIX调度算法。由于没有考虑到SMP,所以SMP不支持。性能表现就非常不好。

所以在后来的2.5版本中,进行了大改。采用了O(1)的算法,之所以O(1),因为它的运行时间是常量,与系统的任务数量是无关的。该调度器增加了对SMP的支持。但是在许多的桌面交互进程的响应时间却表现不是很好。

在之后的2.6版本中,调度器再一次的大的改动。2.6.23的版本中,完全公平调度器(CFS)最终成为Linux调度算法。

Linux的进程调度基于调度类。每个调度类都有一个特定优先级。每一个不同的调度类,都有不同的调度算法,就是为了满足不同的需要。也许手机中的Linux和服务器的Linux调度器准则也是不一样。

Linux内核有两个调度类:CFS和实时调度类。

CFS

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

为什么叫nice?当一个任务增加了它的nice,说明它的优先级降低了,进而对其他任务变得nice

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

假设有两个任务,它们具有相同的nice值。一个任务是 I/O 密集型而另一个为 CPU 密集型。通常,I/O 密集型任务在运行很短时间后就会阻塞以便等待更多的 I/O;而 CPU 密集型任务只要有在处理器上运行的机会,就会用完它的时间片。

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

实时调度

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

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

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

CFS 性能

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

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

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

总结

本文没有特别复杂的一些细节,只是把原理告诉大家。没有告诉进程权重的概念,觉得大部分不是做内核开发,没有必要掌握的太细。只需要把原理弄懂即可,也足够。

觉得不错,记得转发,关注!

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20190629A0C1FD00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。

扫码关注云+社区

领取腾讯云代金券