03-处理机调度

概念
- 调度：就是指有一堆任务需要处理，但是由于资源有限，不能同时处理，这就需要某种规则来就决定处理
```
 任务的顺序，调度就是用于安排处理顺序的。
```
- 处理机调度：就是从就绪队列中按照一定的算法选择一个进程并将处理机分配给它运行，以实现进程的并发
```
       执行
```
调度的三个层次：
- 高级调度（作业调度）
  1. 目的：由于内存空间有限，有时无法将用户提交的作业全部放入内存，因此就需要确定某种规则来决定
```
 将作业调入内存的顺序
```
  2. 定义：按照一定的原则从外存上处于后备队列的作业中挑选一个或多个作业，给他们分配内存等必要资
```
 源并建立相应的进程（建立PCB），以使它们获得竞争处理机的权力
```
  3. 高级调度是外存和内存之间的调度，每个作业只调入一次，调出一次。作业调入时会建立相应的PCB，作
    业调出时才会撤销PCB。
  4. 注意：高级调度主要是指调入问题，因为调入时间由操作系统确定，调出只有在作业运行结束才调出
- 中级调度（内存调度）
  1. 再引入虚拟存储技术之后，可以将暂时不需要执行的进程调至外存，等到它具备运行条件且内存又有空间
    的时候，再重新调入内存。这么做的目的是为了提高内存的利用率和系统的吞吐量
  2. 调到外存的进程会进入到挂起状态
  3. 中级调度就是要决定将哪个处于挂起状态的进程重新调入内存。值得注意的是，一个进程可能会被多次调
    入或调出内存，因此中级调度发生的频率可能要比高级调度发生的频率要高
  4. 挂起状态与七状态模型
    - 挂起状态：暂时调到外存等待的状态
    - 挂起状态可分为就绪挂起和阻塞挂起
    - 挂起与阻塞的区别
      两者都是暂时不能获得CPU服务，但是挂起状态将进程映像调到外存去了，而阻塞态的进程映像还在
      内存中。
    - 注意：除了终止态，其余都能转换为就绪挂起状态。
- 低级调度（进程调度）
  1. 主要任务是按照某种方法和策略从就绪队列中选取一个进程，将处理机分配给它
  2. 进程调度是操作系统中最基本的一种调度，在一般的操作系统中一般都会配置进程调度
    注意：进程调度的频率很高
进程调度的时机切换与过程调度方式
- 进程调度时机
  1. 进程主动放弃处理机
    - 进程正常终止
    - 运行过程中发生异常而终止
    - 进程主动请求阻塞
  2. 进程被动放弃处理机
    - 分给进程的处理机的时间片用完
    - 有更紧急的事件需要处理
    - 有优先级更高的进程进入就绪队列
  - 注意：不能进行进程的调度与切换的情况
    1. 在处理机处于中断的过程中
    2. 进程在操作系统内核程序临界区中
    3. 在原子操作过程中（原语）这是因为原子操作不能中断需要一气呵成
- 进程调度的方式
  1. 非剥夺调度方式，又称非抢占方式。只允许进程主动放弃处理机。在运行过程中即便有更加紧急的
    任务到达，当前进程依然会继续使用处理机，直到该进程终止或者主动要求进入处理状态
  2. 剥夺调度方式，又称抢占方式。就是说，当前进程进行时，有更加紧急的进程需要使用处理机时，会
    立即停止正在执行的进程，将处理机分配给紧急的进程
- 进程的切换与过程
  - 狭义的进程调度与进程切换的区别
    狭义的进程调度是只从就绪队列中选中一个要运行的进程。进程切换是指一个进程让出处理机，由另
    一个进程占用处理机的过程
  - 广义的进程调度：包含了选择一个进程以及进程切换的两个步骤
调度算法的评论指标
- CPU利用率：指CPU“忙碌”的时间占总时间的比例
- 系统吞吐量：单位时间内完成作业量（总共完成多少道作业/总共花了多少时间）
- 周转时间：是指从作业被提交给系统开始，到作业完成的这段时间间隔
  - 四个部分：
    作业在外存后备队列上等待作业调度的时间
    作业在就绪队列上等待进程调度的时间
    进程在CPU上执行的时间
    进程在等待I/O操作完成的时间
  - 平均周转时间：各作业周转时间之和/作业数
  - 带权周转时间：作业周转时间/作业实际运行时间
  - 平均带权周转时间：各作业带权周转时间之和/作业数
- 等待时间：指进程/作业处于等待处理状态时间之和，等待时间越长，用户满意度越低
- 响应时间：用户从提交请求到首次产生响应所用的时间
调度算法（先来先服务，最短作业优先，最高响应比优先）
1. 先来先服务算法（FCFS）（非抢占式）
  - 按照到达的先后顺序调度，事实上就是等待时间越久的越优先得到服务。
  - 算法规则：按照作业进程到达的先后顺序进行服务
  - 优点：公平，算法实现简单
  - 缺点：排在长作业（进程）后面的短作业需要等待很长时间，带权周转时间很大，对短作业来说用户体验
```
  不好。也就是说，对擦汗那个作业有利，对短作业不利
```
  - 不会导致饥饿
2. 短作业优先算法（SJF，Shortest Job First）
  - 算法规则：最短的作业/进程先得到服务（所谓的最短是指要求服务最短）
  - 可用于作业调度，也可以用于进程调度。用于进程调度时称为“短进程优先（SPF Shortest Process First）”
  - SJF和SPF是非抢占式算法，但是也有抢占式版本——最短剩余时间优先算法
  - 抢占式的短作业/进程优先调度算法（最短剩余时间优先算法）的平均等待时间，平均周转时间最少
  - 优点：“最短的”平均等待时间，平均周转时间
  - 缺点：不公平。对短作业有利对长作业不利。
  - 可能出现饥饿现象
  - FCFS与FJS的对比
    FCFS在每次调度的时候选择一个等待时间最长的进程来服务，但是没有考虑到作业的执行时间，导致了对短作业
    不友好的问题
    FJS选择一个执行时间最短的作业为其服务。但是又完全不考虑对作业的等待时间，因此导致对长作业的不友好
    甚至会造成饥饿问题
3. 最高响应比优先算法（HRRN Highest Response Ratio Next）
  - 算法思想：要综合考虑作业/进程的等待时间和执行时间
  - 算法规则：在每次调度时，会先计算各个作业/进程的响应比，选择作业/进程响应比高的为其服务
    响应比=（等待时间 + 要求服务时间）/要求服务时间
  - 作业调度，进程调度
  - 非抢占式算法
  - 优点：综合考虑了等待时间和运行时间（要求服务时间），等待时间相同时，要求服务时间短的优先
```
  要求服务时间相同时，等待时间长的有先
```
  - 不会导致饥饿
4. 时间片轮转调度算法（RR Round-Robin）
  - 轮流让就绪队列中的进程一次执行一个时间片（每次选择的都是排在就绪队列队头的进程）
  - 算法思想：公平的、轮流的为各个进程服务，让每个进程在一定时间间隔内都可以得到响应
  - 算法规则：按照进程到达就绪队列的顺序，轮流让各个进程执行一个时间片的时间，如果在一个时间片内未执行
```
      完，则剥夺处理机，将进程重新放到就绪队列队尾重新排队
```
  - 若在一个时间片内未完成进程，则会被剥夺处理机，所以这个算法属于抢占式算法
  - 优点：公平，响应快，适用于分时操作系统
  - 取点：由于高频率的进程切换，因此有一定的开销：不区分任务的紧急程度
  - 注意：如果时间片太大，那么每个进程有可能在一个时间片就能执行完成，那么时间片轮转算法就会转换为先来先
```
  服务调度算法，并且还会增大进程的响应时间。
  进程调度、切换是有时间代价的（保存，恢复运行环境），如果时间片太小，会导致进程切换过于频繁，那
  么系统需要花大量时间来处理进程切换，从而导致实际用于执行进程时间比例减少
```
5. 优先级调度算法（优先数越大，优先级越高）
  - 非抢占式的优先级调度算法：每次调度时选择当前已到达且优先级最高的进程，当进程主动放弃处理机时发生调度
  - 抢占式的优先级调度算法：每次调度时选择当前已到达且优先级最高的进程。当前进程主动放弃处理机时发生调度
```
                  另外，当就绪队列发生改变时也需要检查是否会发生抢占（是否有优先级较高的进程）
```
  - 算法思想：越来越多的计算机应用场景需要根据任务的紧急程度来决定处理顺序
  - 算法规则：调用时选择优先级高的进程/作业
  - 优点：用优先级区分紧急程度，重要程度，适用于实时操作系统。可以灵活调整对各种作业的偏好程度
  - 缺点：若源源不断的优先级高的进程进来，可能会导致饥饿状态
  - 补充：
    1. 根据系统的优先级是否可以改变分类
      - 静态优先级：创建进程是确定之后一直不发生改变
      - 动态优先级：创建进程时会有一个初始值，之后会根据情况动态的调整优先级
    2. 如何设置进程的优先级
      - 系统进程的优先级高于用户进程
      - 前台进程的优先级高于后台进程
      - 操作系统更偏好I/O型进程（如果优先I/O型进程，那么IO设备可能会优先投入工作）
    3. 什么时候设置优先级（在动态优先级的情况下）
      - 从追求公平，提升资源利用率等角度
      - 如果进程在就绪队列等待很长时间，可以提升优先级
      - 如果进程占用处理机很长时间，可以降低其优先级
6. 多级反馈队列调度算法
  - 算法思想：对其他算法的2折中权衡
  - 算法规则：
    - 设置多级就绪队列，各级队列优先级从高到低，时间片从小到大
    - 新锦城到达时，先进入第1级队列，按照FCFS原则排队等待被分配时间片。若用完时间片进程还未结束，则进程
      进入下一级队列队尾。如果此时已经在最下级队列，则重新放回最下级队列队尾
    - 只有K级队列为空时，才会为k+1级对头的进程分配时间
  - 用于进程调度
  - 抢占式算法;如果在更上级队列中同一个进程优先级高的进程，那么会抢占处理机
  - 优点：公平，快响应，灵活调整偏好度，断金城只用较少时间可以完成
  - 一般没有缺点，不过可能导致饥饿