Q: 为什么都说「进程切换」是个比较昂贵的操作,它昂贵在哪呢?

A:

首先,就是由用户态向内核态的切换。因为我们需要保存旧的进程的状态。其次,我们可能需要执行一个比较复杂的「调度算法」,挑选出一个合适的候选进程。除此之外,每一次进程的切换都会伴随着 CPU 高速缓存的失效。在新的进程被切换到 CPU 上开始运行之后,高速缓存需要从内存中动态装入一些和新的进程运行有关的信息。

Q: 在什么情况下需要进行进程的调度(切换)?

A:

进程切换发生的时候是必然会进行进程调度的,因为此时 CPU 空闲,需要让新的进程在上面运行。那么,什么场景下会发生进程间的切换呢?

  1. CPU 时间片消耗完:这种场景是较为普通和正常的,操作系统为了让所有的进程都能够得到 CPU 的资源,只分配每个进程一定的 CPU 时间片,当时间片消耗完后,进程正常退出,就需要调度新的进程上来。
  2. I/O 中断触发:当一个进程因触发 I / O 活动而阻塞之后,若相应的 I / O 设备完成了所需的任务,会向 CPU 发送 I / O 中断。此时,需要决定到底调度那类进程运行:阻塞之后满足条件的,随机的就绪进程,刚刚在运行的进程(被中断打断)
  3. 触发阻塞条件:一个进程可能会执行一些会阻塞自身的操作:如阻塞的系统调用,等待某一个资源的释放。此时,操作系统会将另外一个就绪的进程切换上来。

一般来说,一个进程的在运行期间过多的是在 CPU 上进行计算,那么它被认为「计算密集型」的。反之,如果大多数时间都消耗在了 I_O 等待上,那么它被认为是「I / O密集型」的。对于当前的 CPU 和 I_O 设备来说,我们可能需要的问题可能更多的和 I / O密集型的进程有关。因为 CPU 的发展速度是远大于 I / O 设备的。

Q: 什么是调度算法?都分为哪几种?

A:

调度算法是一种规则,调度程序依据它来调度进程到 CPU 上运行。调度算法可以大致分为两大类:1. 抢占式调度 2. 非抢占式调度。其实我们平常所说的「CPU 时间片消耗光,进程从 CPU 被切换下来」,指的就是抢占式调度。抢占式调度一般会规定一个时钟周期,当一个时钟周期结束之后,触发时钟中断,将控制权交给调度程序(scheduler),它会根据一定的规则挑选一个可运行的进程。而非抢占式调度则不会主动进行进程间的切换,除非进程自己进入阻塞状态或者它自己让出 CPU。否则,即使一个进程因中断导致暂时停止运行,在中断被处理掉之后,它仍然会在 CPU 上继续运行,而不会被切换。

所以,对于非抢占调度和抢占调度来说,它们唯一的区别,就是对中断的处理(时间中断或者其他事件类的中断)。除了通过「处理中断的方式」将调度算法分为两类之外,我们还可以根据调度算法所适配的系统将其分为三类:

  1. 用于批处理系统的
  2. 用于交互式系统的
  3. 用于实时系统的

对于不同的系统,在设计调度算法的时候会有不同的考量。比如批处理系统,基本不会在意终端用户的感受,只要保证批处理任务顺利进行即可。所以,非抢占或者说长时间才抢占的两种调度算法它都能接受。而对于交互式系统来说,抢占是必须要有的,因为它更加的通用,且要保证终端用户的感受。

Q: 调度算法的设计目标是什么?

A:

若不考虑特定类型的系统,有以下三个较为通用的目标:

  1. 公平性:保证可调度的进程都有机会在 CPU 上执行
  2. 抢占性:必须要有一定的措施可以响应「抢占性」的调度请求
  3. 平衡性:能够在现有的条件下,最大程度的提升 CPU 的使用率

Q: 对于批处理系统,有哪些调度算法?

A:

先来先服务

先来先服务是最好理解的一种调度算法。因为它实在是太符合人们「顺序处理」事情的习惯了,以至于我怀疑它能称得上是一种算法么。先来先服务将待执行的进程放入一个类似单链表的数据结构中,按照从头至尾的顺序运行。若一个进程被阻塞,则切换至另外一个进程。若阻塞的进程被重新唤醒,那么它将被加入到链表尾部,等待运行。

最短作业优先 && 最短剩余时间优先

将这两种调度算法放在一起说的原因是:两个算法的顺利执行都依赖于我们必须要事先知道每个进程的运行时间。

对于最短作业优先算法来说,我们可以考虑这样一个例子:现在有 A, B, C, D 四个进程,四个进程的运行时间分别为 5, 4, 4, 3。 按照正常的顺序,四个进程顺序执行花费的总时间为 5+(4+5)+ (4+5+4)+(3+4+4+5)= 43, 平均时间为 10。如果将例子中具体的数值换为变量,四个进程运行的时间分别为 a, b, c, d, 则总时间为 a + (a+b) + (a+b+c) + (a +b+c+d) = 4a + 3b + 2c +d, 平均时间为 a+ 3/4b + 1/2c + 1/4d。 仔细观察就会发现,在运行总时间不变的情况下,按照对平均时间最终取值的影响程度从大到小排序, a 是影响最大的一个,bcd 依次降低。那么如果我们将 a, b, c, d 的取值按照从小到大来安排,最终的平均运行时间就是最优的。

但是最短作业优先算法的一个致命缺陷就是它不能动态的调整进程执行的顺序,因为它是一个非抢占式调度的算法。所以,最短剩余时间优先算法就在它的基础上做了改进:若有新的进程进入就绪队列的时候,对比它的执行时间和当前进程剩余的时间大小,选择较小的一个调度至 CPU 运行。

Q: 对于交互式系统,有哪些调度算法?

A:

轮转调度

轮转调度就是我们常说的 round robin 的形式,它维护一个就绪进程的队列,分配给每个进程一个时间片,若某个进程在时间片内被阻塞,则 CPU 会进行进程切换,从就绪队列选取下一个顺位的进程调度上来。此外,若在规定的时间片内,某个进程一直在运行。当时间片被消耗完的时候,CPU 也会进行上述的切换动作

对于这里的抢占行为,笔者觉得应该是通过中断来完成的。如周期性的时钟中断实现的抢占可以保证一个进程不会占用 CPU 太久,而一些事件类的中断如 I / O 中断,将通过给 CPU 发送中断信号的形式来通知它进行处理,此时调度程序也将获得机会,根据已有的策略来运行一个就绪的进程。

轮转调度的实现是比较简单的,但是它也有一个不好控制的地方:时间片的长度。如果时间片长度设置的过长,可能对于短时任务的进程就不是很友好,甚至会出现饥饿的现象。如果时间片设置的太短,那么进程间切换的开销也会消耗相当多的 CPU 资源(保存和恢复进程状态,更新各种表格,清除并重新载入高速缓存)。

优先级调度

轮转调度的设计是处在一个特定的前提下的:就绪队列中的每个进程优先级都是相同的。但是很多时候,在一个操作系统中有一部分进程是比较重要的,需要优先来运行,有一部分进程是次要的,可以缓一些时间再运行。基于这种考虑,操作系统给出了名为「优先级调度」的调度算法。

既然是以优先级为调度,那么自然要将进程分类。为此,一种可能的实现是:按照优先级的划分设置多个就绪进程的队列。将不同优先级的进程放入到相应的队列中。比如, 对于 I / O 密集型的进程我们应该尽快分配给他 CPU,以便它能够尽快的进入 I / O 等待的状态,从而能够和其他进程并行执行。所以它的优先级就会被指定的比较高。那么在同一个优先级的队列中我们应该按照什么样的算法去弹出进程呢?答案当然是「轮转调度」,因为轮转调度本身就是为了优先级相同的进程提供的一种较为公平的调度算法。

在优先级调度算法中,我们通常会按照优先级从高到低的顺序处理就绪队列中的进程,如先把高优先级队列中的进程调度完,然后再处理次优先级的。但是有一点需要注意,进程的优先级不仅仅需要在创建时就指定,在之后的运行过程中要能有动态调整的能力,不然的话,有些低优先级的进程可能会被饿死。

最短进程优先

这里的最短进程优先算法是借鉴了批处理系统中最短作业优先算法。通过上面的描述我们可以知道,最短进程优先优先在交互式系统中比较难以把控的就是进程的运行时间。因为终端用户有权利运行多样的进程,操作系统不可能像批处理系统一样,在任务没执行之前就准确的估计了任务的执行时间。但是,在交互式系统中,我们可以动态的估计一个进程剩余的运行时间,从而将这个「预估时间」作为依据进行进程调度,这种技术叫做「老化」。如一个进程第一次执行时间为t0,第二次为t1, 通过计算加权和的方式可以估计出它下一次的运行时间为 a*t0 + (1-a) * t1。而加权系数的选择决定了在计算进程运行时间的过程中,想要多快忘记它之前的运行时间。