调度算法
1. 进程调度算法
进程调度算法用来将空闲的CPU时间片分配到进程上执行，常见的进程调度算法有：
先来先服务调度算法：每次从就绪队列选择最先进入队列的进程，直到进程退出或被阻塞再重新选择，适用于CPU繁忙型作业
最短作业优先调度算法：每次从就绪队列选择运行时间最短的进程，直到进程退出或被阻塞再重新选择，有利于提高系统的吞吐量
高响应比优先调度算法：每次从就绪队列选择
优先级 = (等待时间 + 要求服务时间)/要求服务时间最大的进程，权衡了短作业和长作业时间片轮转调度算法：每个进程被分配时间片
一般20ms-50ms，允许进程在时间片内运行，未运行完则会切换下一进程，时间片太长会导致短作业进程响应时间变长，太短会导致进程上下文切换频繁，降低CPU效率最高优先级调度算法：每次从就绪队列选择优先级最高的进程，具有抢占式（出现高优先级进程立刻切换）和非抢占式（当前进程必须运行完）两种处理方法
- 静态优先级：优先级分配后不会改变
- 动态优先级：随着等待时间增加进程优先级
多级反馈队列调度算法：时间片轮转算法和最高优先级算法的结合，兼顾了长短作业，同时有较好的响应时间
- 多级：表示有多个队列，每个队列优先级从高到低，同时优先级越高时间片越短
- 反馈：表示如果有新的进程加入优先级高的队列时，立刻停止当前正在运行的进程，转而去运行优先级高的队列
此时新任务会先放在优先级最高的队列，如果一次调度没有执行完就会依次下发到后续优先级低的队列中
2. 内存页面置换算法
当CPU访问的页面不在物理内存时，会产生缺页中断，请求操作系统将缺页调入物理内存。缺页中断不同于一般的中断，产生于指令执行期间（为了检查缺页），并返回到指令开始的位置（重新执行）
在上述缺页中断的流程中，当物理内存中没有空闲页时，就会触发内存页面置换算法，选择一个物理页将其换入磁盘，并将访问页放入物理页。内存页面置换算法的目标是尽量减少换出和换入的次数，常见的算法有：
- 最佳页面置换算法（OPT）
OPT的思路是置换在未来最长时间不访问的页面，但实际上程序是动态的，无法预知每个内存页在下次访问前的等待时间
- 先进先出置换算法（FIFO）
FIFO的思路是置换在内存中驻留时间最长的页面
- 最近最久未使用置换算法（LRU）
LRU的思路是置换最长时间没有被访问的页面，LRU在实现上，需要在内存中维护一个所有页面的链表，最近最多使用的页面在表头，最近最少使用的页面在表尾。在每次访问内存时都需要对链表进行更新，所以开销较大。
- 时钟页面置换算法（Lock）
Lock在LRU和FIFO的思路上进行了改进，使其更容易实现。Lock的访问位记录了当前页面是否被访问过，Lock将所有的页面都保存在环形链表中，使用指针指向最老的页面，当缺页中断时：
- 指针访问的是0则置换该页面，并将指针前移一个位置
- 指针访问的是1则清除访问位，并将指针前移一个位置，直到找到访问位为0
- 最不常用算法（LFU）
LFU的思路是置换访问次数最少的页面。在LFU的实现上，需要增加计数器，并对链表上的所有计数找到最小的值，和LRU一样，这样的方式效率太低了。
3. 磁盘调度算法
磁盘的寻道时间是磁盘访问最耗时的部分，磁盘调度算法通过优化磁盘的访问请求顺序来提高磁盘的性能。
假设磁盘磁道是1-100，此时请求的序列是30、10、40、60、50、20、80
- 先来先服务
即按照序列的先后顺序进行访问，然而这会导致磁道的访问过于分散，总磁道距离较大。
- 最短寻道时间优先
即优先选择距离当前磁头位置最近的下一个点的算法
- 扫描算法
磁头在相同方向上移动，直到访问到磁道的末尾才调转方向
- 循环扫描算法
磁头只在相同的方向上移动，返回的时候直接跳转到开始的位置
- LOOK、C-LOOK算法
磁头移动到最远的位置即反向移动，称之为LOOK算法。而C-LOOK则是类似于循环扫描的算法，返回的时候不会响应请求
