操作系统第五章课堂笔记，主要介绍了长程，中程和短程调度，CPU调度的方式和基本指标，以及几个常见的CPU调度算法。内容较多，尚未精修。根据目录索引所需即可。

CPU调度概述

• CPU调度是多任务操作系统的基础，目的是使得CPU尽可能用于执行指令，从而提高CPU效率。
• CPU调度概述：长程和短程调度，调度队列，中程调度，CPU脉冲周期，CPU调度方式，调度过程和时机，调度准则
• 在OS中，CPU调度可分为长程调度，中程调度，短程调度。
• CPU调度：因为进程间存在竞争，需要操作系统选择一个进程来进行这种转换。

长程，短程调度和中程调度

长程调度

• 长程调度：每个用户创建进程的初始状态是“新建”，处于新建状态的进程一般首先被放到外存的进程池中，当内存中进程的数量小于最多进程数时，操作系统的调度程序才从新建状态选择一个进入内存并转换为就绪状态。这种从“新建”状态转换到“就绪”状态的操作就是长程调度，又称为作业调度或高级调度。

短程调度

• 短程调度，又称为进程调度或低级调度。在就绪队列中可能存在不止一个进程，当CPU空闲时，操作系统需要从就绪队列中挑选一个进程让它运行。

长程调度与短程调度的比较：
每个进程在其生命周期中只有一次长程调度，而有成千上万次短程调度。
长程调度需要将进程的代码，数据从外存调到内存中来，IO操作耗时

中程调度

• 中程调度（交换）：从本质上讲，中程调度不属于进程管理的内容，而应该属于内存管理。即，一个进程在内存和外存间的换进换出，最大的目的是节省内存。当一个进程在内存中长期不运行时，会造成内存浪费。操作系统把这些进程从内存换出到外存，从而腾出内存空间供运行进程使用。当一个在外存的进程将要运行时，操作系统则执行换入操作，把这个进程从外存换入内存。
• 进程队列：为了方便进行CPU调度，操作系统需要对不同状态的进程进行组织和管理。为此，为某些特定的状态设立了一个或多个进程队列，用于管理这些进程。
  就绪队列：在主内存中处于就绪状态并等待执行的所有进程集合
  设备队列：等待某I/O设备的进程队列，所有的设备队列中的进程对应的状态都是等待状态。
  进程的执行过程实际上就是进程在各种队列之间的迁移。

CPU调度

• CPU调度由两个部分组成：调度程序，分派程序
  调度程序：根据某种策略选择内存中的一个就绪进程。
  分派程序：负责具体的进程切换工作，如下
• 过程：

1. 利用定时器把CPU的控制权转交CPU调度程序，让调度程序选择一个需要运行的进程。
2. 进行进程的上下文切换，把该进程从就绪状态转换到运行状态。
3. 系统切换到用户态，跳转到用户程序的适当位置并重新运行之。
   进程调度存在系统开销，即分派延迟–分派程序终止一个进程的运行并启动另一个进程运行所花的时间。

CPU调度的方式

CPU调度的方式有两种：非抢占式调度，抢占式调度

• 非抢占式调度：一旦把CPU分配给某进程后，系统不可以抢占已分配的CPU并分配给其他进程。只有进程资源释放CPU，才可把CPU分配给其他进程。
  优点：易实现，调度开销小，适合批处理系统
  缺点：响应时间长，不适合交互式系统。

• 抢占调度：调度程序可根据某种原则暂停某个正在执行的进程，将已分配给它的CPU重新分配给另一进程。
  优点：可防止单一进程长时间独占CPU
  缺点：系统开销大

• 抢占式和非抢占式调度的最大区别是运行的进程是否自愿放弃CPU。

• CPU调度发生的时机：
  1.从运行转到等待（非抢占式）
  2.从运行转到就绪（抢占式）
  3.从等待转到就绪（抢占式）
  4.终止运行（非抢占式）
  [解释]因为1和4是由于运行的进程不能运行了（由于需要进行同步I/O）或运行完了，所以该进程会主动放弃CPU。
  2是因为所有的从运行到就绪的转换必然不是运行进程的主动行为，而是调度程序的行为。
  3.当一个进程加入就绪队列后，根据某种策略，该进程比正在运行的进程更加有权运行，那么该进程会抢占正在运行的进程的CPU。

• CPU调度的核心任务是提高CPU的效率，也就是利用率。

CPU调度的基本指标

1. CPU利用率：固定时间内CPU运行时间的比例
2. 吞吐量：单位时间内运行完的进程数。
3. 周转时间：进程从提交到运行结束的全部时间
4. 等待时间：进程等待调度（不运行）的时间片总和
5. 响应时间：从进程提交到首次运行（而不是输出结果）的时间段，也就是第一段的等待时间
   周转时间=等待时间+运行时间
   响应时间<=等待时间

• CPU调度的目标：最大的CPU利用率，最大的吞吐量，最短的周转时间，最短的等待时间，最短的响应时间。为达到这些目标，最关键的是调度的算法，即就绪队列中哪个进程被选中运行。

CPU调度算法

先来先服务调度算法（FCFS）

• 策略：按照进程请求CPU的先后顺序使用CPU。
• 优点：实现简单，可使用FIFO队列实现
• 属于非抢占式调度。
• FCFS调度是公平的，因为系统内每个进程都有被调度的机会，不会被抢占。
• 适用于长程调度，后台批处理系统的的短程调度。
• 对长CPU脉冲的进程有利，对短CPU脉冲的进程不利。
  （甘特图：用于项目管理，将活动与时间联系起来）

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

策略

关联到每个进程下次运行的CPU区间长度，调度最短的进程。

模式

非抢占式和抢占式
非抢占式：一旦进程拥有了CPU，只有当该CPU脉冲时间结束才会让出CPU的控制权。
抢占式：当有比当前进程剩余时间片更短的进程到来时，新来的进程抢占当前进程获得CPU运行，这种调度算法也被称为最短剩余时间优先调度，简写为SRTF，系统开销大。

• 优点：
  1.具有最短的平均等待时间。
  2.存在饥饿问题。一个长进程很早被加入就绪队列，但又有很多短进程被加入就绪队列，则长进程可能很长时间得不到运行。

• 非抢占式SJF举例：
  

• 抢占式SJF举例：
  

指数平均法

• SJF调度算法通常用于作业调度。其难点在于如何知道下一个CPU区间的长度。在进程调度中实现SJF算法，可以通过预测下一个CPU区间长度来实现。假设下一个区间长度与以前的相似，通过先前的CPU区间及其指数平均可预测下一个区间长度。
  $${\tau }_{n+1}=\alpha t_n+(1-\alpha ){\tau }_n$$
  其中$t_n$为第n个区间长度的实际值，${\tau }_{n+1}$为下一次区间长度的预测值，参数$0<=\alpha <=1$

优先级调度算法（PR）

策略

为每个进程分配一个优先数，该数值为整数，然后按照进程的优先数来分配使用CPU。默认：小优先数具有高优先级。就绪队列的排队策略是优先级高在前，优先级低在后。

调度模式

抢占式调度和非抢占式调度
抢占式调度：当一个比正在运行的进程优先级更高的进程加入就绪队列后，该进程将抢占正在运行进程的CPU。当优先级相同时，采用先来先服务准则。

• 非抢占式PR举例：
  

优先级讨论

• 优先级算法中最重要的一点是优先级的设置。优先级的设置可参考不同的因素来设置，如时间极限，内存要求，进程重要性等；同时该值可以静态不变，也可以动态调整。
• 两类：动态优先级和静态优先级
• 静态优先级：在创建进程时就确定每个进程的优先数，并且在进程的整个执行期间保持不变。
• 优先数用某一范围内的整数来表示，如0–255中的某个整数。这样方法简单易行，系统开销小；但不够精确，可能会出现低优先级的进程长期没有被调度的情况，即饥饿问题。
• 动态进程：进程创建时的优先级随进程推进或等待时间增加而改变，以获得更好的调度性。
  例：高响应比优先调度算法（既考虑进程的等待时间，又考率进程的运行时间）
  优先数=响应比$R_p=\frac{等待时间}{运行时间}$
  优先数越大，优先级越高
  若等待时间相同，运行时间越短，优先级越高，类似于SJF
  若运行时间相同，优先级取决于等待时间，类似于FCFS
  长进程的优先级可随等待时间的增加而提高，最终可得到服务
• 缺点：每次调度之前，都需要计算响应比，增加系统开销

优缺点

• 优点：实现简单，考虑了进程的紧迫程度，策略灵活，可模拟其他算法
• 缺点：饥饿问题–低优先级的进程可能永远得不到运行

解决方法

• 老化 – 随进程等待时间的延长提高其优先数

时间片轮转调度算法（RR）

介绍

专为分时系统设计，类似于FCFS，但增加了抢占。
原理：把一段时间分割成若干个小碎片，每个需要运行的进程获得一个碎片运行，也就是在这段时间内，每个进程都得到运行。
举例：
1.首先设置时间片（小单位的CPU时间，通常为10-100毫秒）
2.调度：将就绪队列看为循环队列，为每个进程分配不超过一个时间片的CPU。时间片用完后，该进程将被插入就绪队列末尾。

• RR算法的平均等待时间较长；但响应时间要比其他算法短。
• 时间片轮转调度算法的性能很大程度上依赖于时间片的大小。若时间片非常大，那么RR算法等同于FCFS算法。若时间片很小，那么该算法相当于共享处理器，会增加进程的上下文切换时间，即系统开销增大。因此，多数操作系统准则是时间片大于10倍的进程上下文切换时间。

FCFS和SJF主要适用于长程调度。
优先级调度算法和时间片轮转调度算法适用于短程调度。
批处理系统需要短的等待时间，交互式系统需要短的响应时间。

多级队列调度（MLQ）

可针对不同的进程使用不同的调度算法。
允许系统中存在多个就绪队列，每个就绪队列有自己的调度算法。
关键点：
1.需要确定就绪队列的数量
2.需要确定新进程进入哪个队列
3.需要确定每一队列的调度算法

CPU空闲时，先调度哪个队列中的进程呢？
1）固定优先级，前台运行完再运行后台（可能有饥饿问题）
2）给定时间片（如80%时间执行前台RR算法，20%时间执行后台FCFS算法）

多级反馈队列调度（MLFQ）

• 多级反馈队列调度是多级队列调度的沿伸。
• 多级队列调度算法中一旦一个进程进入了某个队列，那么它在运行过程中不能加入其它队列，也就是不能在不同队列间移动。
• 而多级反馈队列的核心是：进程在其运行过程中，能在不同队列间移动。
• 多级反馈队列调度除了要考虑多级反馈队列调度考虑的三个问题，还要考虑 决定进程升级（低级队列到高级队列）的方法，决定进程降级（高级队列到低级队列）的方法

以上讨论的是单核单处理器的调度方法。

多处理器调度

• 对称多处理器（SMP）
  SMP是目前的主流处理器架构，每个处理器决定自己的调度方案。
• 非对称多处理器（ASMP）
  一般仅一个处理器能处理系统数据结构，减轻对数据的共享需求。
• 负载平衡：将任务平均分配给各个处理器
• 亲和性：进程在某个给定的CPU上尽量长时间地运行而不被迁移到其他处理器的倾向性。
  软亲和性：进程通常不会在处理器之间频繁迁移。
  硬亲和性：进程不会在处理器之间迁移。

单队列多核调度方法

• 系统中有一个就绪队列，当任意一个CPU空闲时，就从就绪队列中选择一个进程到该CPU上运行。
• 优点：容易从单核调度算法推广到多核/多处理器。实现简单，负载均衡。
• 缺点：不具有亲和性，一个进程可能在不同时候被调度到不同的CPU。多核 同时访问一个队列，会有加锁问题，从而严重影响调度的性能。

多队列调度方法

• 系统有多个就绪队列，一般每个CPU一个，每个就绪队列有自己的调度算法，并且每个就绪队列的调度相对独立。
• 优点：亲和性好，不需要加锁
• 缺点：负载不均衡

小知识点

1. 控制内存中运行进程的数量的调度是长程调度。
2. 为什么等待到就绪是抢占式调度？
3. 一个进程在其生命周期中，一般来说等待时间大于响应时间。
   响应时间：从进程提交到首次运行的时间段；
   等待时间：进程等待调度(不运行)的时间片总和。
   所以响应时间小于等待时间
4. 亲和性问题在单核单处理器中不需要考虑。