CPU调度

  • 为什么要进行CPU调度
  • 调度算法？

这里我们重点了解一些调度算法

调度概念

进程对于CPU个数，资源不足，那么进程之间就会争夺CPU资源。怎么分配资源合理呢？

我们要求按照公平、高效的原则，选择进程将CPU分配给它

调度层次

我们有三级调度层次：作业调度（高级）、内存调度（中级）、进程调度（低级）

  • 作业调度：从外存尚处于后备队列的作业挑选一些，给它们分配内存、IO设备资源，并建立相应的进程；简而言之，作业调度是内存和辅存间的调度；每个作业只出入一次；一般多道批处理系统有作业调度，其他不需要
  • 内存调度：将暂时不能运行的进程调至外存等待，进程处于挂起态。进程们此时已有运行条件，当内存稍有空闲就决定将哪些挂起进程重新调入内存，将其状态改为就绪态。目的为了提高内存利用率和系统吞吐量
  • 进程调度：选择CPU分配，频率很高，几十ms一次

三者之间关系如下：

  • 作业调度为进程活动准备
  • 内存调度处于作业调度和进程调度之间
  • 作业调度次数最少，内存调度其次，进程调度频率最高
  • 进程调度最基本，不可或缺

调度实现

调度器：就是实现调度CPU的程序，三部分组成

  • 排队器：将所有就进程组织成一个或多个就绪队列；当有进程变为就绪态时，排队器就将它插入就绪队列
  • 分派器：根据调度算法，从就绪队列挑选进程，分配CPU
  • 上下文切换器：在CPU切换时，会发生两对上下文切换操作；第一对，当前进程上下文保存到PCB中，在装入分派程序的上下文，以便分派程序运行；第二对，移除分派程序的上下文，将新选进程的CPU现场信息装入CPU各个相应寄存器

上下文切换时，有大量的load和store指令，保存寄存器的内容；会花费较多时间

调度时机，切换过程

先请求调度，调度新就绪队列，发生进程切换；我们期望这样顺序执行进行调度，然而事实上有很多其他情况，不一定能顺序执行；因此我们需要明确CPU调度的事件：

  • 创建新进程，父子进程都处于就绪态，调度程序可以合法决定其中哪个先执行
  • 进程结束后，必须从就绪队列选某个程序运行，若没了就绪队列，则运行一个OS提供的闲逛进程
  • 进程因请求其他资源时，IO设备、信号量，被阻塞时，必须调度其他进程
  • IO设备完成后，发出IO中断，原先等待IO设备的进程变为就绪态；要决定时是新就绪态进程拿CPU，还是让中断发生时处于运行的进程继续执行
  • 某些更紧急任务（更高优先级）、时间片用完

不能进行进程调度切换的情况：

  • 在处理中断事件。
  • 需要完全屏蔽中断的原子操作：加锁、解锁、中断现场保护、恢复现场

进程调度方式

  • 非抢占式：保证正在执行的进程不被其他进程打断，直到该进程完成（正常结束或者异常终止），或者进入阻塞态；优点是系统开销小，但不能用于分时和实时系统

  • 抢占式：当一个进程A在CPU执行，运行调度程序根据某种原则让新来的更重要进程B，打断A，抢夺CPU资源；好处是提高了系统吞吐率和响应效率，主要有时间片、优先权、短进程有先等原则

还有闲逛进程，之前我们已经提到过，这是当就绪队列为空时，OS调闲逛程序；它的PID时0，优先级最低，只需要CPU资源，其他不需要

当我们存在内核级线程时，OS选择特定的线程分配cpu，这个过程需要完整的上下文切换、修改内存映像、高速缓存失效、导致若干数量级延迟。

调度目标

我们怎么衡量调度算法的性能？

  • CPU利用率：

  • 系统吞吐量：单位时间CPU完成作业的数量；长作业会消耗CPU时间很多，会降低系统吞吐量。

  • 周转时间：从作业提交到作业完成的总时间，是指作业在等待、就绪队列中排队、在CPU运行及IO操作花费的时间，公式如下

  • 等待时间：进程处于等待CPU时间之和

  • 响应时间：指用户提交请求到系统首次产生响应所用的时间。交互系统中周转时间不是最好的评价，一般采用响应时间

进程切换

我们来看看CPU调度时进程切换发生了什么？

上下文切换

上下文用PCB表示，包括CPU寄存器的值、进程状态和内存管理信息等

  • 先挂起一个进程，将CPU上下文保存到PCB ，包括程序计数器和其他寄存器
  • 将PCB移入队列，就绪、在某事件阻塞等队列
  • 选择另一个进程执行，并更新其PCB
  • 恢复新进程的CPU上下文
  • 跳转到新进程PCB中的程序计数器所指向的位置执行

上下文切换要耗费大量的CPU事件

模式切换和上下文切换是不同的：模式切换在用户态和内核态之间，上下文切换只发生在内核；

经典调度算法

FCFS（先来先服务）

作业调度中，FCFS每次从后备队列中挑选最先进入队列的一个或几个作业，调入内存，分配资源，创建相应的进程

进程调度中，FCFS同理，直到运行完进程或者发生阻塞结束

FCFS属于不可剥夺算法 ，当一个长作业先来系统，后面短作业要等很长事件，因此不能作为分时和实时系统的主要调度策略。

优点：有利于CPU繁忙型作业，对长作业有利，算法简单

缺点： 效率低，对短作业不友好，不利于IO繁忙的作业

SJF（短作业优先）和SPF 调度算法

SJF挑选运行事件最短的作业，将它们调入内存；在调度进程也是如此，运行时间短的进程优先

缺点：

  • 对长作业不利，系统优先调度短作业，可能导致长作业长期不被调度，造成饥饿
  • 该算法没有考虑作业的紧迫程度，不能及时处理紧迫作业
  • 作业的长短是根据用户提供的估计执行时间而定，而不是真正的运行时间

SPF（短进程优先）默认是非抢占式，当然也可以是抢占式的

SJF的平均等待时间、平均周转时间是最优的

高相应比优先调度算法

这是对FCFS和SJF算法的平衡，同时考虑了每个作业的等待时间和估计的运行时间。自然是挑选响应比最高的作业投入内存：

特点：

  • 作业等待时间相同，那么服务时间短，相应比高，利于短作业，SJF
  • 服务时间相同，等待时间越长，响应比越高，FCFS
  • 长作业，响应比随时间增加而提高，克服饥饿现象

优先级调度算法

  • 非抢占式优先级:
  • 抢占式优先级：
  • 静态优先级：优先级在创建进程确定，在进程整个运行期间保持不变；优先级依据为进程类型、进程对资源要求、用户要求；简单易行，开销小；不够精确
  • 动态优先级：优先级会随时间变化，比如等待时间越长，优先级越高

一般的，系统进程>用户进程，交互进程>非交互进程，IO进程（频繁使用IO）>计算型进程（频繁使用CPU）

RR（时间轮转）

分时系统里，OS将所有就绪进程按FCFS拍成就绪队列，然后比如每隔30ms产生一次时钟中断，激活调度程序，将CPU分配给队列队首 的进程。进程事情没做完，时间片到了，也停止

特点：

  • 时间片大小对系统性能影响很大
  • 时间片很大，那就跟FCFS没区别
  • 时间片很小，频繁切换进程，CPU开销增大，用于处理进程本身的CPU时间占比减少

多级队列调度算法

我们可以在OS里设置多个就绪队列，不同性质的进程分配到不同就绪队列，每个队列可以采用不同的调度算法。

队列本身也可以设置优先级。在多CPU系统中给，可以为每个CPU设置一个单独的就绪队列

多级反馈队列调度

我们主要实现多级反馈队列调度的方式如下：

  • 设置多个就绪队列，每个队列有不同的优先级
  • 赋予各个队列的进程时间片大小各不相同，优先级越高的队列，每个进程时间片越小
  • 每个队列采用FCFS。新进程来到内存后，先来队列1末尾等待。到我的小进程A了，欸，在队列1的时间片没运行完；怎么办？A只能跑到队列2的末尾，如果队列2的时间片里还没运行完；A就跑到队列3里，依次类推
  • 按队列优先级调度；只有队列1空了，才调度队列2；若CPU在执行队列i 中的进程B,发现前面的空的队列突然又有什么大佬人物（进程）来了，我们CPU只好把刚刚的进程B推到队列I的末尾，赶忙去服务那位大佬了

可见多级反馈队列调度结合了时间片轮转和优先级调度，有以下优势

  • 终端型作业用户：短作业优先
  • 短批处理作业用户：周转时间较短
  • 长批处理作业用户：经过前面几个队列得到部分执行，不会饥饿