调度算法
调度算法：调度程序针对不同的应用场景（操作系统）采用不同的调度算法去调度进程
调度单位：线程是最小的调度单位；但是为了方便起见仍然使用进程的概念来描述调度的过程
调度时机 & 方式
调度时机：
初始态 -> 就绪态：
- 条件：进程获得相应的资源
- 描述：调度程序将进程从 ==作业队列==（磁盘）中调度进入 ==就绪队列== （内存）中
运行态 -> 阻塞态：
条件：(1) 进程需要相应的 I/O 资源 (2) 父进程创建子进程后需要等待（使用
wait()函数）描述：调度程序剥夺进程对处理器的控制权，调度到设备队列
问题：父进程在哪里等待子进程结束？磁盘等待队列 / 交换空间
运行态 -> 就绪态：
- 条件：时间中断发生
- 描述：进程主动放弃处理的控制权，被调度程序调度到就绪队列
阻塞态 -> 就绪态：
- 条件：(1)进程得到相应的 I/O 资源 (2) 子进程结束
- 描述：调度程序将进程调度到就绪队列中
运行态 -> 终止态
调度方式：
抢占式定义：==允许== 新的进程 ==抢占== 当前进程的处理器 ==使用权==
非抢占式定义：允许当前进程 ==持续使用== 处理器直到当前进程 ==主动放弃== 处理器使用权
调度规则
衡量指标：
处理器利用率：处理器计算的时间 ÷ 处理器运行的时间
尽可能使处理器处于繁忙的状态：如果处理器利用率较低长期调度程序会调入新的程序进入内存
吞吐量：==单位时间内进程完成的数量==
注：长进程数量越多系统的吞吐量显然越低，短进程数量越多系统的吞吐量显然越高
周转时间：进程运行的总时间
1. 运行时间 = 等待时间（在队列中的等待时间） + 执行时间（使用处理器的时间）
2 周转时间和吞吐量没有必然的联系；高吞吐量的调度算法可能造成较长的周转时间
等待时间：进程在各个队列中的等待时间之和
响应时间：提交第一个请求到输出第一个结果花费的时间
注：批处理操作系统就是等待处理器所有的计算完成才会使用 I/O 设备进行输出 -> 不是处理器边计算边输出 -> 没有交互性
调度规则：
注：通常对周转时间，等待时间，相应时间的平均值进行优化；也可以使用最大值，最小值，方差等计算方式进行优化
应用场景：
批处理系统：==吞吐量 + 周转时间 + 处理器利用率==
解释：批处理系统主要是使用 CPU 进行计算任务，不需要和用户进行交互，没有用户会烦躁地去等待
交互式系统：==响应时间==
批处理系统调度算法
先来先服务算法(FCFS)
内容：
- 每个新进程被调度进入就绪队列中时都被链接到 ==链表队列的尾部==
- 调度程序每次从 ==链表队列的首部== 调度进程进入处理器中
实现：采用链表队列实现
优点 & 缺点：
优点：每个进程获得处理器使用权的机会是 ==公平== 的
-
解释：短进程必须等待长进程执行结束才可以获得处理器的使用权
时间片：每个进程的时间片都是 ==不相同== 的
解释：因为每个进程都执行到它们主动放弃为止，而每个进程的执行时间显然是不一样的
细节：
护航效果：其余所有进程等待当前进程释放处理器的使用权
先来先服务算法 ==不适用于分时系统和实时系统==
解释：分时系统需要频繁地切换处理器执行的进程，不会等待进程完全执行结束
例子：
最短作业优先算法(SJF)
内容：
- 调度程序选择就绪队列中 ==执行时间最短== 的进程，将处理器的控制权交付给该进程
- 新的进程进入就绪队列时，如果执行时间 ==小于== 当前进程剩余的执行时间 -> 可以选择抢占当前进程的处理器使用权，也可以选择不抢占
分类：
抢占式算法：新的进程进入就绪队列中且执行时间小于当前进程的执行时间 -> 抢占当前进程的处理器使用权
非抢占式算法：新的进程进入就绪队列中，无论执行时间和当前进程的执行时间关系如何 -> 不允许抢占当前进程处理器使用权
优点 & 缺点：
缺点：(1) 调度程序 ==无法得知== 下个进程执行时间，难以选择执行时间最短的进程 (2) 容易出现 ==饥饿== 现象
解释：每个进程只有使用处理器执行结束后才可能知道到底执行了多久，进程是不会提前告诉操作系统需要执行多久的
时间片：每个进程的时间片都是 ==不相同== 的
执行时间预测：
引入：虽然没有办法提前精确预知每个进程的执行时间，但是可以通过之前进程的执行时间来预测下一个进程可能的执行时间
方式：==指数平均==
公式：==τ
n+1= $\alpha$ tn+ (1 - $\alpha$) τn==参数：
- τ
n+1：表示下一个进程的可能执行时间 - t
n：表示上一个进程的实际执行时间 - τ
n：表示上一个进程的预估执行时间 - $\alpha$：权重
- τ
细节：
- 最短作业优先是优先权算法的一种特例：仅以进程的执行时间作为计算优先级的标准
- 最短作业优先算法更 ==适合长期调度== 的过程，==不适合短期调度== 过程
交互式系统调度算法
优先权算法
内容：
- 调度程序选择就绪队列中 ==优先级最高== 的进程，将处理器的控制权交付给该进程
- 新的进程进入就绪队列时，如果优先级 ==高于== 当前进程优先级 -> 可以选择抢占当前进程的处理器使用权，也可以选择不抢占
分类：
- 抢占式算法：新的进程进入就绪队列中且优先级高于当前进程的优先级 -> 抢占当前进程的处理器使用权
- 非抢占式算法：新的进程进入就绪队列中，无论优先级的关系如何 -> 不允许抢占当前进程处理器使用权
优点 & 缺点：
- 优点：等待时间的平均值也是相对较短的
- 缺点：优先权算法可能造成饥荒（无穷堵塞）问题
优先级设置：(1) 静态优先级：在进程被创建的时候就设置优先级以后不再修改 (2) 动态优先级：进程在运行过程中可以动态修改其优先级
优先级决定因素
- 内部优先级：时限，内存要求，打开文件数量，平均 I/O 执行时间和平均 CPU 执行时间 -> 都可以用于计算进程的优先级
- 外部优先级：进程的重要性，操作系统和计算机的成本，赞助部门，其他因素 -> 也可以用于计算进程的优先级
饥荒：
- 描述：稳定的高优先级 ==进程流== 能够阻止 ==某个== 低优先级的进程执行，导致低优先级的进程始终无法获取或者长时间无法获取处理器使用权
- 方式：==老化==
- 定义：不断 ==增加== 长时间等待的进程的 ==优先级==
注：老化是解决饥荒的一种 ==方式==
细节：(1) 系统进程优先级 > 用户进程优先级 (2) 交互式进程优先级 > 非交互性进程优先级 (3) I/O 密集型进程优先级 > CPU 密集型进程优先级
时间片轮转法(RR)
内容：
调度程序为每个进程分配 ==固定== 的时间片
如果进程在时间片结束时仍在运行，调度程序会 ==剥夺== 当前进程的处理器使用权
优点 & 缺点：
- 优点：
- 缺点：
- 时间片轮转法的等待时间平均值相对较长
- 时间片的长度难以设置得非常合适
时间片
- 如果时间片长度设置过长 -> 时间片轮转法会退化为先来先服务算法
- 如果时间片长度设置过短 -> 调度程序会频繁执行上下文切换，会降低处理器的利用率
细节：
- 每个进程的执行时间都是相同的
- 进程的执行时间 ≤ 时间片的长度
- 进程 ==最长的等待时间 (n - 1) * 时间片==
多级队列调度
引入：
内容：
多级队列反馈调度
- 内容：