Linux进程及其调度策略

作者:Vamei
原文:www.cnblogs.com/vamei/p/9364382.html

进程是操作系统虚拟出来的概念,用来组织计算机中的任务。它从诞生到随着CPU时间执行,直到最终消失。不过,进程的生命都得到了操作系统内核的关照。就好像疲于照顾几个孩子的母亲内核必须做出决定,如何在进程间分配有限的计算资源,最终让用户获得最佳的使用体验。内核中安排进程执行的模块称为调度器(scheduler)。这里将介绍调度器的工作方式。

进程状态

调度器可以切换进程状态(process state)。一个Linux进程从被创建到死亡,可能会经过很多种状态,比如执行、暂停、可中断睡眠、不可中断睡眠、退出等。我们可以把Linux下繁多的进程状态,归纳为三种基本状态。

图1 进程的基本状态

进程创建后,就自动变成了就绪状态。如果内核把CPU时间分配给该进程,那么进程就从就绪状态变成了执行状态。

在执行状态下,进程执行指令,最为活跃。正在执行的进程可以主动进入阻塞状态,比如这个进程需要将一部分硬盘中的数据读取到内存中。在这段读取时间里,进程不需要使用CPU,可以主动进入阻塞状态,让出CPU。

当读取结束时,计算机硬件发出信号,进程再从阻塞状态恢复为就绪状态。进程也可以被迫进入阻塞状态,比如接收到SIGSTOP信号。

调度器是CPU时间的管理员。Linux调度器需要负责做两件事:一件事是选择某些就绪的进程来执行;另一件事是打断某些执行中的进程,让它们变回就绪状态。不过,并不是所有的调度器都有第二个功能。

调度器在让一个进程变回就绪时,就会立即让另一个就绪的进程开始执行。多个进程接替使用CPU,从而最大效率地利用CPU时间。当然,如果执行中进程主动进入阻塞状态,那么调度器也会选择另一个就绪进程来消费CPU时间。

所谓的上下文切换(context switch)就是指进程在CPU中切换执行的过程。内核承担了上下文切换的任务,负责储存和重建进程被切换掉之前的CPU状态,从而让进程感觉不到自己的执行被中断。应用程序的开发者在编写计算机程序时,就不用专门写代码处理上下文切换了。

进程优先级

调度器分配CPU时间的基本依据,就是进程的优先级。根据程序任务性质的不同,程序可以有不同的执行优先级。根据优先级特点,我们可以把进程分为两种类别。

1、实时进程(Real-Time Process):优先级高、需要尽快被执行的进程。它们一定不能被普通进程所阻挡,例如视频播放、各种监测系统。

2、普通进程(Normal Process):优先级低、更长执行时间的进程。例如文本编译器、批处理一段文档、图形渲染。

普通进程根据行为的不同,还可以被分成互动进程(interactive process)和批处理进程(batch process)。互动进程的例子有图形界面,它们可能处在长时间的等待状态,例如等待用户的输入。一旦特定事件发生,互动进程需要尽快被激活。一般来说,图形界面的反应时间是50到100毫秒。批处理进程没有与用户交互的,往往在后台被默默地执行。

实时进程由Linux操作系统创造,普通用户只能创建普通进程。两种进程的优先级不同,实时进程的优先级永远高于普通进程。进程的优先级是一个0到139的整数。数字越小,优先级越高。其中,优先级0到99留给实时进程,100到139留给普通进程。

一个普通进程的默认优先级是120。我们可以用命令nice来修改一个进程的默认优先级。例如有一个可执行程序叫app,执行命令:

$nice -n -20 ./app

命令中的-20指的是从默认优先级上减去20。通过这个命令执行app程序,内核会将app进程的默认优先级设置成100,也就是普通进程的最高优先级。命令中的-20可以被换成-20至19中任何一个整数,包括-20 和 19。默认优先级将会变成执行时的静态优先级(static priority)。调度器最终使用的优先级根据的是进程的动态优先级:动态优先级 = 静态优先级 – Bonus + 5

如果这个公式的计算结果小于100或大于139,将会取100到139范围内最接近计算结果的数字作为实际的动态优先级。公式中的Bonus是一个估计值,这个数字越大,代表着它可能越需要被优先执行。如果内核发现这个进程需要经常跟用户交互,将会把Bonus值设置成大于5的数字。如果进程不经常跟用户交互,内核将会把进程的Bonus设置成小于5的数。

O(n)和O(1)调度器

下面介绍Linux的调度策略。最原始的调度策略是按照优先级排列好进程,等到一个进程运行完了再运行优先级较低的一个,但这种策略完全无法发挥多任务系统的优势。因此,随着时间推移,操作系统的调度器也多次进化。

先来看Linux 2.4内核推出的O(n)调度器。O(n)这个名字,来源于算法复杂度的大O表示法。大O符号代表这个算法在最坏情况下的复杂度。字母n在这里代表操作系统中的活跃进程数量。O(n)表示这个调度器的时间复杂度和活跃进程的数量成正比。

O(n)调度器把时间分成大量的微小时间片(Epoch)。在每个时间片开始的时候,调度器会检查所有处在就绪状态的进程。调度器计算每个进程的优先级,然后选择优先级最高的进程来执行。一旦被调度器切换到执行,进程可以不被打扰地用尽这个时间片。如果进程没有用尽时间片,那么该时间片的剩余时间会增加到下一个时间片中。

O(n)调度器在每次使用时间片前都要检查所有就绪进程的优先级。这个检查时间和进程中进程数目n成正比,这也正是该调度器复杂度为O(n)的原因。当计算机中有大量进程在运行时,这个调度器的性能将会被大大降低。也就是说,O(n)调度器没有很好的可拓展性。O(n)调度器是Linux 2.6之前使用的进程调度器。

为了解决O(n)调度器的性能问题,O(1)调度器被发明了出来,并从Linux 2.6内核开始使用。顾名思义,O(1)调度器是指调度器每次选择要执行的进程的时间都是1个单位的常数,和系统中的进程数量无关。这样,就算系统中有大量的进程,调度器的性能也不会下降。

O(1)调度器的创新之处在于,它会把进程按照优先级排好,放入特定的数据结构中。在选择下一个要执行的进程时,调度器不用遍历进程,就可以直接选择优先级最高的进程。

和O(n)调度器类似,O(1)也是把时间片分配给进程。优先级为120以下的进程时间片为:

(140–priority)×20毫秒

优先级120及以上的进程时间片为:

(140–priority)×5 毫秒

O(1)调度器会用两个队列来存放进程。一个队列称为活跃队列,用于存储那些待分配时间片的进程。另一个队列称为过期队列,用于存储那些已经享用过时间片的进程。

O(1)调度器把时间片从活跃队列中调出一个进程。这个进程用尽时间片,就会转移到过期队列。当活跃队列的所有进程都被执行过后,调度器就会把活跃队列和过期队列对调,用同样的方式继续执行这些进程。

上面的描述没有考虑优先级。加入优先级后,情况会变得复杂一些。操作系统会创建140个活跃队列和过期队列,对应优先级0到139的进程。一开始,所有进程都会放在活跃队列中。

然后操作系统会从优先级最高的活跃队列开始依次选择进程来执行,如果两个进程的优先级相同,他们有相同的概率被选中。执行一次后,这个进程会被从活跃队列中剔除。如果这个进程在这次时间片中没有彻底完成,它会被加入优先级相同的过期队列中。当140个活跃队列的所有进程都被执行完后,过期队列中将会有很多进程。调度器将对调优先级相同的活跃队列和过期队列继续执行下去。过期队列和活跃队列,如图2所示。

图2 过期队列和活跃队列(需要替换)

我们下面看一个例子,有五个进程,如表1所示。

表1 进程

Linux操作系统中的进程队列(run queue),如表2所示。

表2 进程队列

那么在一个执行周期,被选中的进程依次是先A,然后B和C,随后是D,最后是E。

注意,普通进程的执行策略并没有保证优先级为100的进程会先被执行完进入结束状态,再执行优先级为101的进程,而是在每个对调活跃和过期队列的周期中都有机会被执行,这种设计是为了避免进程饥饿(starvation)。所谓的进程饥饿,就是优先级低的进程很久都没有机会被执行。

我们看到,O(1)调度器在挑选下一个要执行的进程时很简单,不需要遍历所有进程。但是它依然有一些缺点。进程的运行顺序和时间片长度极度依赖于优先级。比如,计算优先级为100、110、120、130和139这几个进程的时间片长度,如表3所示。

表3 进程的时间片长度

从表格中你会发现,优先级为110和120的进程的时间片长度差距比120和130之间的大了10倍。也就是说,进程时间片长度的计算存在很大的随机性。O(1)调度器会根据平均休眠时间来调整进程优先级。该调度器假设那些休眠时间长的进程是在等待用户互动。这些互动类的进程应该获得更高的优先级,以便给用户更好的体验。一旦这个假设不成立,O(1)调度器对CPU的调配就会出现问题。

完全公平调度器

从2007年发布的Linux 2.6.23版本起,完全公平调度器(CFS,Completely Fair Scheduler)取代了O(1)调度器。CFS调度器不对进程进行任何形式的估计和猜测。这一点和O(1)区分互动和非互动进程的做法完全不同。

CFS调度器增加了一个虚拟运行时(virtual runtime)的概念。每次一个进程在CPU中被执行了一段时间,就会增加它虚拟运行时的记录。在每次选择要执行的进程时,不是选择优先级最高的进程,而是选择虚拟运行时最少的进程。完全公平调度器用一种叫红黑树的数据结构取代了O(1)调度器的140个队列。红黑树可以高效地找到虚拟运行最小的进程。

我们先通过例子来看CFS调度器。假如一台运行的计算机中本来拥有A、B、C、D四个进程。内核记录着每个进程的虚拟运行时,如表4所示。

表4 每个进程的虚拟运行时

系统增加一个新的进程E。新创建进程的虚拟运行时不会被设置成0,而会被设置成当前所有进程最小的虚拟运行时。这能保证该进程被较快地执行。在原来的进程中,最小虚拟运行时是进程A的1 000纳秒,因此E的初始虚拟运行时会被设置为1 000纳秒。新的进程列表如表5所示。

表5 新的进程列表

假如调度器需要选择下一个执行的进程,进程A会被选中执行。进程A会执行一个调度器决定的时间片。假如进程A运行了250纳秒,那它的虚拟运行时增加。而其他的进程没有运行,所以虚拟运行时不变。在A消耗完时间片后,更新后的进程列表,如表6所示。

表6 更新后的进程列表

可以看到,进程A的排序下降到了第三位,下一个将要被执行的进程是进程E。从本质上看,虚拟运行时代表了该进程已经消耗了多少CPU时间。如果它消耗得少,那么理应优先获得计算资源。

按照上述的基本设计理念,CFS调度器能让所有进程公平地使用CPU。听起来,这让进程的优先级变得毫无意义。CFS调度器也考虑到了这一点。CFS调度器会根据进程的优先级来计算一个时间片因子。同样是增加250纳秒的虚拟运行时,优先级低的进程实际获得的可能只有200纳秒,而优先级高的进程实际获得可能有300纳秒。这样,优先级高的进程就获得了更多的计算资源。

以上就是调度器的基本原理,以及Linux用过的几种调度策略。调度器可以更加合理地把CPU时间分配给进程。现代计算机都是多任务系统,调度器在多任务系统中起着顶梁柱的作用。

原文发布于微信公众号 - Java架构沉思录(code-thinker)

原文发表时间:2018-11-26

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏深度学习计算机视觉

操作系统知识梳理共9次缺页

第一章:概述 什么是操作系统? 是一段一直运行在计算机上的程序 是资源的分配者 向上管理软件向下管理硬件 为用户提供良好接口 中断的概念? 中断指当出现需要时,...

29050
来自专栏Debian社区

HAProxy用法详解 最详细中文文档

(1)HAProxy 是一款提供高可用性、负载均衡以及基于TCP(第四层)和HTTP(第七层)应用的代理软件,支持虚拟主机,它是免费、快速并且可靠的一种解决方案...

53530
来自专栏landv

16位和32位的80X86汇编语言的区别

22620
来自专栏嵌入式程序猿

【速来围观】IAR环境下代码覆盖率功能的使用

在设计测试程序,验证是否所有的代码都被执行到时,就要考虑到代码覆盖率,IAR环境下的代码覆盖率是一个在这方面很有用的功能,且使用方便,今天我们就来讲讲这一功能如...

45360
来自专栏GreenLeaves

Nginx学习系列四默认负载均衡轮询及Ip_hash等常用指令介绍

Upstream模块是Nginx中一个核心模块,当客户端访问Nginx服务器的时候,Nginx会从服务器列表中选取压力小的服务器,然后分配给客户端进行访问.这个...

24520
来自专栏开发与安全

linux环境常用的性能监控和协助开发调试工具

linux有诸多优秀的工具帮助我们分析服务器各项性能指标和协助开发调试工作。下面只列举比较基础的命令,且一般是集成在linux环境中而不需再次安装的...

46010
来自专栏北京马哥教育

高性能服务端漫谈

一、背景 进入多核时代已经很久了,大数据概念也吵得沸沸扬扬,不管你喜欢不喜欢,不管你遇到没遇到,big-data或bigger-data都必须正视. 处理大数...

32580
来自专栏JackieZheng

Nodejs学习笔记(二)——Eclipse中运行调试Nodejs

前篇《Nodejs学习笔记(一)——初识Nodejs》主要介绍了在搭建node环境过程中遇到的小问题以及搭建Eclipse开发Node环境的前提步骤。本篇主要介...

29890
来自专栏Vamei实验室

调度器简介,以及Linux的调度策略

进程是操作系统虚拟出来的概念,用来组织计算机中的任务。但随着进程被赋予越来越多的任务,进程好像有了真实的生命,它从诞生就随着CPU时间执行,直到最终消失。不过,...

17520
来自专栏抠抠空间

python中的Redis键空间通知(过期回调)

Redis是一个内存数据结构存储库,用于缓存,高速数据摄取,处理消息队列,分布式锁定等等。

1.5K50

扫码关注云+社区

领取腾讯云代金券