操作系统

CPU调度

Posted by 刘知安 on 2019-10-26
文章目录
  1. CPU调度基本概念
  2. 调度算法评估准则
  3. 调度算法
    1. 1. 先来先服务算法（First Come First Service,FCFS）
    2. 2. 短进程优先算法（Shortes Process Next,SPN）
    3. 3. 最高响应比优先（Highest Response Ratio Next,HRRN）
    4. 4. 时间片轮转算法（Round-Robin,RR）
    5. 5. 多级反馈队列调度算法（Multi-Level Feedback Queue,MLFQ）

@[toc]

CPU调度基本概念

  • 进程切换
    进程切换即CPU资源在当前占用者之间的切换，也就是保存当前进程在PCB中的执行上下文（context），然后再恢复下一个进程的执行上下文。

  • CPU调度
    CPU调度其实可以分为两个部分：①进程调度②CPU资源调度，前者就是从就绪进程队列中选取一个进程准备运行，后者是从多个可用的CPU资源中分配给进程。

  • 内核调度进程的时机

  1. 进程从运行态切换到了等待状态（blocking）
  2. 进程被终结了，进入了退出状态。

调度算法评估准则

  • CPU使用率：CPU处于忙状态的时间百分比
  • 吞吐量（throughput）：单位时间内完成的进程数量
  • 周转时间（turn-around time）：进程从初始化到结束过程中的总时间（包括等待时间）
  • 等待时间：进程在就绪队列中的总时间
  • 响应时间（response time）：进程从提交请求到产生响应的时间

调度算法

1. 先来先服务算法（First Come First Service,FCFS）

该调度算法依据进程进入就绪状态的先后顺序维护一个队列，每次调度时从队首取出一个进程将之转入运行状态。
在这里插入图片描述

  • 优点：
    该算法的优点显而易见，就是实现方式比较简单了。
  • 缺点：
  1. 平均等待时间较长，且如果短进程排在后面时，平均周转时间也会较长。
  2. I/O资源和CPU资源的利用率较低。
  3. 不公平

    2. 短进程优先算法（Shortes Process Next,SPN）

    选择就绪队列中，执行时间最短的进程占用CPU进入运行状态。（这里有个问题，你怎么知道一个进程执行时间?），实际上，是按照进程的预期执行时间来排序。

在这里插入图片描述
SPN具有最优的平均周转时间，如下图所示，其中$C_i$表示第i个进程的执行时间：
在这里插入图片描述

  • 优点：
    该算法的优点是，具有最优的平均周转时间。
  • 缺点：
  1. 连续到来的短进程可能会使得长进程无法获得CPU资源
  2. 需要预知未来，也就是上面提到的，你怎么知道一个进程的执行时间是多少？于是需要进行预测。
  3. 不公平

至于如何预测，因为OS知道上一次该进程的CPU计算时间，因此可以采用滑动平均（exponential moving average）的方式来预测：

其中，$t{n}$表示第n次的CPU计算时间，$\tau{n+1}$表示第n+1次的CPU计算时间预估。如果将上式全部展开为关于变量$t$的式子的话，可以得到如下：

3. 最高响应比优先（Highest Response Ratio Next,HRRN）

该算法的思想是选择就绪队列中响应比最高的那个进程，响应比的定义如下：

其中，w表示进程的等待时间（waiting time），s表示进程的执行时间（service time）

该算法起始是对短进程优先算法的一个改进，在SPN中，有可能会造成长进程无限等待，而这里的响应比会使得等待时间越久的进程响应比越高，防止了无限期等待。

4. 时间片轮转算法（Round-Robin,RR）

在上述的1-3个算法中，每次都是选择一个进程，然后将之运行直至完毕（这里暂时不考虑抢占的问题），而这样的调度算法是不公平的。RR算法从一定程度上解决了这个问题：将CPU时间分片，每个进程每次只拿到1个时间片。大致的思想如下：和FCFS一样，按照进程到来的顺序给进程维护一个队列，每次从队列头取出一个进程运行，不过每个进程只运行一个时间片（即为q）。如果进程的执行时间小于q，那不用说，自然在一个时间片之间就完成进程执行并退出；如果一个时间片q的时间到了，进程还没执行完成，就把这个进程强制放入队列尾部，等待下一次分配到时间片。
在这里插入图片描述
下面是一个RR算法执行的具体示例：
在这里插入图片描述

  • 优点
    各进程之间被公平的对待，不会使得某个进程被无限延期执行的情况。
  • 缺点
  1. 基于时间片的思想，会产生一些额外的进程上下文切换，开销较大。所以，如何选择时间片q的大小也是一个关键，若q太小，自然上下文切换会非常频繁，加大系统开销；如果q太大，极限情况下就退化成了一个FCFS算法，又可能会造成平均周转时间太长。（一个经验规律是，选择的q使得上下文切换开销占系统开销的1%之内）
  2. 平均等待时间较差

下图是RR和FCFS的一个比较：
在这里插入图片描述

5. 多级反馈队列调度算法（Multi-Level Feedback Queue,MLFQ）

在OS中常常会遇到这样的问题，一些前台交互程序希望可以在较短时间内被处理完毕，而一些后台批处理任务似乎慢点也无关紧要，于是，可以采用维护多个队列的形式，在每个队列上可以采用不同的调度算法。而所谓的多级反馈队列，多级刚才解释了，就是维护多个队列；而反馈的意思是指，进程可以在不同队列之间移动。移动的规则如下：时间片在不同的队列中不一样，优先级最高的队列时间片最短，而优先级最低的队列时间片最长。如果一个进程在当前时间片内没有执行完毕，那么就把该进程降到下一个优先级的队列中去。可能文字表述有点绕，举个例子说明一下：
在这里插入图片描述
有如上图的多级反馈队列，数字序号越低的队列优先级最高（时间片最短），在上图中，相邻两个队列的时间片时长以2的幂增长。现在，如果有一个进程p到来了，这个进程的特点是，开始有一些交互操作，后面有一些很消耗CPU计算时长的操作，最开始，这个队列被放在第1级，得到了t0时间片，执行一个时间片t0后，进程没做完，这个时候OS会把该进程下移，放到第2级队列的队尾部去（如果在第2个队列中该进程又得到了时间片，执行流程类似。）

注意一下，这多个队列之间的CPU时间片分配也是被OS管理的，OS会给较高优先级队列比较多的CPU时间（例如，第1-4级队列占了70%的CPU时间，相邻队列之间的调用可以简单采用循环遍历的方式），剩下的CPU时间就分配给低优先级的队列就OK了。

  • 优点
  1. CPU密集型进程的优先级将下降的很快
  2. I/O密集型进程将停留在高优先级
  3. 各进程动态地将信息反馈给OS，便于OS维护
FEATURED TAGS
操作系统
FRIENDS