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

  • 时间:
  • 浏览:0

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

应用程序具体情况

调度器都需用切换应用程序具体情况(process state)。另另4个 Linux应用程序从被创建到死亡,原困 会经过你这些 种具体情况,比如执行、暂停、可中断睡眠、不可中断睡眠、退出等。朋友都需用把Linux下繁多的应用程序具体情况,归纳为某种基本具体情况。

  • 就绪(Ready): 应用程序原困 获得了CPU以外的所有必要资源,如应用程序空间、网络连接等。就绪具体情况下的应用程序等到CPU,便可立即执行。
  • 执行(Running):应用程序获得CPU,执行应用程序。
  • 阻塞(Blocked):当应用程序原困 等待图片某个事件而无法执行时,便放弃CPU,所处阻塞具体情况。

 

图1 应用程序的基本具体情况

应用程序创建后,就自动变成了就绪具体情况。原困 内核把CPU时间分配给该应用程序,这样 应用程序就从就绪具体情况变成了执行具体情况。在执行具体情况下,应用程序执行指令,最为活跃。正在执行的应用程序都需用主动进入阻塞具体情况,比如你你这些 应用程序需用将一帕累托图硬盘中的数据读取到内存中。在这段读取时间里,应用程序不需用使用CPU,都需用主动进入阻塞具体情况,让出CPU。当读取后来刚开始时,计算机硬件发出信号,应用程序再从阻塞具体情况恢复为就绪具体情况。应用程序也都需用被迫进入阻塞具体情况,比如接收到SIGSTOP信号。

调度器是CPU时间的管理员。Linux调度器需用负责做两件事:一件事是选则你这些 就绪的应用程序来执行;另一件事是打断你这些 执行中的应用程序,让它们变回就绪具体情况。不过,并是是否是是所有的调度器是是否是是第四个功能。有的调度器的具体情况切换是单向的,还可不后能 让就绪应用程序变成执行具体情况,还可不后能 把正在执行中的应用程序变回就绪具体情况。支持双向具体情况切换的调度器被称为抢占式(pre-emptive)调度器。

调度器在让另另4个 应用程序变回就绪时,就会立即让从前 就绪的应用程序后来刚开始执行。多个应用程序接替使用CPU,从而最大速率地利用CPU时间。当然,原困 执行中应用程序主动进入阻塞具体情况,这样 调度器也会选则从前 就绪应用程序来消费CPU时间。所谓的上下文切换(context switch)本来 指应用程序在CPU中切换执行的过程。内核承担了上下文切换的任务,负责储存和重建应用程序被切换掉完后 的CPU具体情况,从而让应用程序感觉还可不后能 自己的执行被中断。应用应用程序的开发者在编写计算机应用程序时,就不需要专门写代码处里上下文切换了。 

应用程序的优先级

调度器分配CPU时间的基本办法,本来 应用程序的优先级。根据应用程序任务性质的不同,应用程序都需用有不同的执行优先级。根据优先级特点,朋友都需用把应用程序分为某种类别。

  • 实时应用程序(Real-Time Process):优先级高、需用尽快被执行的应用程序。它们一定还可不后能 被普通应用程序所阻挡,同类视频播放、各种监测系统。
  • 普通应用程序(Normal Process):优先级低、更长执行时间的应用程序。同类文本编译器、批处里一段文档、图形渲染。

普通应用程序根据行为的不同,还都需用被分成互动应用程序(interactive process)和批处里应用程序(batch process)。互动应用程序的例子有图形界面,它们原困 所处长时间的等待图片具体情况,同类等待图片用户的输入。一旦特定事件所处,互动应用程序需用尽快被激活。一般来说,图形界面的反应时间是500到5000毫秒。批处里应用程序这样 与用户交互的,往往在后台被默默地执行。

实时应用程序由Linux操作系统创造,普通用户还可不后能 创建普通应用程序。某种应用程序的优先级不同,实时应用程序的优先级永远高于普通应用程序。应用程序的优先级是另另4个 0到139的整数。数字越小,优先级越高。其中,优先级0到99留给实时应用程序,5000到139留给普通应用程序。

另另4个 普通应用程序的默认优先级是120。朋友都需用用命令nice来修改另另4个 应用程序的默认优先级。同类有另另4个 可执行应用程序叫app,执行命令:

命令中的-20指的是从默认优先级上减去20。通过你你这些 命令执行app应用程序,内核会将app应用程序的默认优先级设置成5000,也本来 普通应用程序的最高优先级。命令中的-20都需用被添加-20至19中任何另另4个 整数,包括-20 和 19。默认优先级原困 变成执行时的静态优先级(static priority)。调度器最终使用的优先级根据的是应用程序的动态优先级:

动态优先级 = 静态优先级 – Bonus + 5

原困 你你这些 公式的计算结果小于5000或大于139,原困 取5000到139范围内最接近计算结果的数字作为实际的动态优先级。公式中的Bonus是另另4个 估计值,你你这些 数字越大,代表着它原困 越需用被优先执行。原困 内核发现你你这些 应用程序需用老会 跟用户交互,原困 把Bonus值设置成大于5的数字。原困 应用程序不老会 跟用户交互,内核原困 把应用程序的Bonus设置成小于5的数。

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

下面介绍Linux的调度策略。最原始的调度策略是按照优先级排列好应用程序,等到另另4个 应用应用程序完了再运行优先级较低的另另4个 ,但你你这些 策略完整版无法发挥多任务系统的优势。或者 ,随着时间推移,操作系统的调度器也多次进化。

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

O(n)调度器把时间分成少量的微小时间片(Epoch)。在每个时间片后来刚开始的完后 ,调度器会检查所有所处就绪具体情况的应用程序。调度器计算每个应用程序的优先级,或者 选则优先级最高的应用程序来执行。一旦被调度器切换到执行,应用程序都需用不被打扰地用尽你你这些 时间片。原困 应用程序这样 用尽时间片,这样 该时间片的剩余时间会增加到下另另4个 时间片中。

O(n)调度器在每次使用时间片前是是否是是检查所有就绪应用程序的优先级。你你这些 检查时间和应用程序中应用程序数目n成正比,这也正是该调度器复杂度为O(n)的原困 。当计算机中含少量应用程序在运行时,你你这些 调度器的性能原困 被大大降低。也本来 说,O(n)调度器这样 很好的可拓展性。O(n)调度器是Linux 2.6完后 使用的应用程序调度器。当Java语言逐渐流行后,原困 Java虚拟原困 创建少量应用程序,调度器的性能现象变得更加明显。

为了处里O(n)调度器的性能现象,O(1)调度器被发明者人了出来,并从Linux 2.6内核后来刚开始使用。顾名思义,O(1)调度器是指调度器每次选则要执行的应用程序的时间是是否是是另另4个 单位的常数,和系统中的应用程序数量无关。从前 ,就算系统中含少量的应用程序,调度器的性能本来 会下降。O(1)调度器的创新之所处于,它会把应用程序按照优先级排好,贴到 特定的数据内控 中。在选则下另另4个 要执行的应用程序时,调度器不需要遍历应用程序,就都需用直接选则优先级最高的应用程序。

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

(140–priority)×20毫秒

优先级120及以上的应用程序时间片为:

(140–priority)×5 毫秒

O(1)调度器会用另另4个 队列来存贴到 程。另另4个 队列称为活跃队列,用于存储哪些待分配时间片的应用程序。从前 队列称为过期队列,用于存储哪些原困 享用过时间片的应用程序。O(1)调度器把时间片从活跃队列中调出另另4个 应用程序。你你这些 应用程序用尽时间片,就会转移到过期队列。当活跃队列的所有应用程序都被执行完后 ,调度器就会把活跃队列和过期队列对调,用同样的办法继续执行哪些应用程序。

顶端的描述这样 考虑优先级。加入优先级后,具体情况会变得复杂你这些 。操作系统会创建140个活跃队列和过期队列,对应优先级0到139的应用程序。一后来刚开始,所有应用程序是是否是是贴到 活跃队列中。或者 操作系统会从优先级最高的活跃队列后来刚开始依次选则应用程序来执行,原困 另另4个 应用程序的优先级相同,朋友有相同的概率被选中。执行一次后,你你这些 应用程序会被从活跃队列中剔除。原困 你你这些 应用程序在这次时间片中这样 彻底完成,它会被加入优先级相同的过期队列中。当140个活跃队列的所有应用程序都被执行完后 ,过期队列中原困 有你这些 应用程序。调度器将对调优先级相同的活跃队列和过期队列继续执行下去。过期队列和活跃队列,如图2所示。

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

朋友下面看另另4个 例子,有四个应用程序,如表1所示。

表1 应用程序



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

表2 应用程序队列

这样 在另另4个 执行周期,被选中的应用程序依次是先A,或者 B和C,后来是D,最后是E。

注意,普通应用程序的执行策略并这样 保证优先级为5000的应用程序会先被执行完进入后来刚开始具体情况,再执行优先级为101的应用程序,本来 在每个对调活跃和过期队列的周期中是不原困 被执行,你你这些 设计是为了处里应用程序饥饿(starvation)。所谓的应用程序饥饿,本来 优先级低的应用程序后来都这样 原困 被执行。

朋友看过,O(1)调度器在选则下另另4个 要执行的应用程序时很简单,不需用遍历所有应用程序。或者 它依然有你这些 缺点。应用程序的运行顺序和时间片长度极度依赖于优先级。比如,计算优先级为5000、110、120、1500和139这几个应用程序的时间片长度,如表3所示。

表3 应用程序的时间片长度

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

完整版公平调度器

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

CFS调度器增加了另另4个 虚拟运行时(virtual runtime)的概念。每次另另4个 应用程序在CPU中被执行了一段时间,就会增加它虚拟运行时的记录。在每次选则要执行的应用程序时,是是否是是选则优先级最高的应用程序,本来 选则虚拟运行时相当于 的应用程序。完整版公平调度器用某种叫红黑树的数据内控 取代了O(1)调度器的140个队列。红黑树都需用高效地找到虚拟运行最小的应用程序。

朋友先通过例子来看CFS调度器。或者我我一台运行的计算机中从前 拥有A、B、C、D四个应用程序。内核记录着每个应用程序的虚拟运行时,如表4所示。

表4 每个应用程序的虚拟运行时

系统增加另另4个 新的应用程序E。新创建应用程序的虚拟运行时不需要被设置成0,而会被设置成当前所有应用程序最小的虚拟运行时。这能保证该应用程序被较快地执行。在从前 的应用程序中,最小虚拟运行时是应用程序A的1 000纳秒,或者 E的初始虚拟运行是是否是是被设置为1 000纳秒。新的应用程序列表如表5所示。

表5 新的应用程序列表

或者我我调度器需用选则下另另4个 执行的应用程序,应用程序A会被选中执行。应用程序A会执行另另4个 调度器决定的时间片。或者我我应用程序A运行了2500纳秒,那它的虚拟运行时增加。而你这些 的应用程序这样 运行,你这些 虚拟运行时不变。在A消耗完时间片后,更新后的应用程序列表,如表6所示。

表6 更新后的应用程序列表

都需用看过,应用程序A的排序下降到了第三位,下另另4个 将要被执行的应用程序是应用程序E。从本质上看,虚拟运行时代表了该应用程序原困 消耗了几个CPU时间。原困 它消耗得少,这样 理应优先获得计算资源。

按照上述的基本设计理念,CFS调度器能让所有应用程序公平地使用CPU。听起来,这让应用程序的优先级变得毫无意义。CFS调度器也考虑到了你你这些 点。CFS调度器会根据应用程序的优先级来计算另另4个 时间片因子。同样是增加2500纳秒的虚拟运行时,优先级低的应用程序实际获得的原困 还可不后能 500纳秒,而优先级高的应用程序实际获得原困 有500纳秒。从前 ,优先级高的应用程序就获得了更多的计算资源。

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

欢迎阅读“骑着企鹅采树莓”系列文章