CPU调度策略

线程是CPU基本调度单位（如果os支持线程的话）.
CPU调度没有对错，只有好坏，即作出的选择是否合适 .
cpu调度策略 : 先来先服务,最短作业优先,最短剩余时间优先调度,最短剩余时间优先调度,轮转调度,多级队列调度,最高优先级调度,多级反馈队列调度 .

因素及准则

任务周转时间：即任务从新建进入os到该任务完成离开os所经历的全部时间
- 后台（非交互式）任务关注周转时间
任务响应时间：即从用户向程序发起一个交互操作到该任务响应这个操作之间经历的时间。例如单机菜单到弹出菜单这段时间。
- 前台（交互式）任务关注响应时间
系统吞吐量：即一段时间内计算机系统能完成的任务总数。（系统内耗时间少）
吞吐量和响应时间之间有矛盾
- 响应时间小 =》切换次数多 =》系统内耗大 =》吞吐量小

IO密集型和CPU密集型任务

CPU密集型，也即CPU约束型

1	\|--------CPU-------\|--IO--\|--------CPU-------\|--IO--\|

IO密集型，也即IO约束型

1	\|--CPU--\|--------IO--------\|--CPU--\|--------IO--------\|

特点：公平
先来后到，每次从就绪队列选择最先进入队列的进程，然后一直运行，直到进程退出或被阻塞，才会继续从队列中选择第一个进程接着运行
- 这似乎很公平，但是当一个长作业先运行了，那么后面的短作业等待的时间就会很长，不利于短作业。

实际上，任务不可能一下子同时出现在0时刻，os无法在0时刻决定出那个先调度那进程，因此实际上是 最短剩余时间优先调度
- 每次新任务到达时，选择剩余执行时间最短的进行运行。
- 是一种可抢占调度
对于旨在缩小平均周转时间的非交互式任务，SRTF看起来是个可以解决问题的调度算法。
- 不过存在一个问题：需要预测任务执行时间
  - 任务得到CPU之后将会执行的时间长度，只有任务完成以后
- 并且实际上也并不是只有非交互式任务，还存在交互式任务
  - SRTF中，任何任务要等到前面的任务全部执行完成以后才被调度，所以最差的用户响应时间可能很大

RR特点：可以保证用户响应时间，是交互式任务调度的解决方法
概念
- 每个进程被分配一个时间段，称为时间片（Quantum），即允许该进程在该时间段中运行。
流程
- 如果时间片用完，进程还在运行，那么将会把此进程从 CPU 释放出来，并把 CPU 分配另外一个进程；
- 如果该进程在时间片结束前阻塞或结束，则CPU立即进行切换；另外，时间片的长度就是一个很关键的点：
时间片长度
- 如果时间片设得太短会导致过多的进程上下文切换，降低了 CPU 效率，吞吐量变小。
- 如果设得太长又可能引起对短作业进程的响应时间变长。
- 时间片10-100ms,切换时间0.1-1ms(1%)

时间片轮转算法做了个假设，即让所有的进程同等重要，也不偏袒谁，大家的运行时间都一样。
但是，对于多用户计算机系统就有不同的看法了，它们希望调度是有优先级的，即希望调度程序能从就绪队列中选择最高优先级的进程进行运行，这称为最高优先级（Highest Priority First，HPF）调度算法。
进程的优先级可以分为，静态优先级或动态优先级：
- 静态优先级：创建进程时候，就已经确定了优先级了，然后整个运行时间优先级都不会变化；
- 动态优先级：根据进程的动态变化调整优先级，比如如果进程运行时间增加，则降低其优先级，如果进程等待时间（就绪队列的等待时间）增加，则升高其优先级，也就是随着时间的推移增加等待进程的优先级。
该算法也有两种处理优先级高的方法，非抢占式和抢占式：
- 非抢占式：当就绪队列中出现优先级高的进程，运行完当前进程，再选择优先级高的进程。
- 抢占式：当就绪队列中出现优先级高的进程，当前进程挂起，调度优先级高的进程运行。
但是依然有缺点，可能会导致低优先级的进程永远不会运行。

多级反馈队列（Multilevel Feedback Queue）
- 多级：
  - 不是单纯分成前台队列，后台队列，分成队列1，队列2，队列3。
  - 每个队列优先级从高到低，同时优先级越高时间片越短。
- 反馈
  - 任务应该在哪个队列是在执行过程中动态调整，不似乎一开始就确定的。

多级反馈队列
- 多级反馈队列之间的动态调整（反馈）近似实现了SRTF，降低周转时间，且不用预测时间
- 核心基础是RR，保证了任务响应时间
- 多级反馈队列之间的动态调整（反馈）可以综合交互式和非交互式任务调度