进程调度
- 先来先服务调度算法
- 最短作业优先调度算法
- 高响应比优先调度算法
每次进行进程调度时，先计算「响应比优先级」，然后把「响应比优先级」最高的进程投入运行 - 时间片轮转调度算法
每个进程被分配一个时间段，称为时间片（Quantum），即允许该进程在该时间段中运行。如果时间片用完，进程还在运行，那么将会把此进程从 CPU 释放出来，并把 CPU 分配另外一个进程；
如果该进程在时间片结束前阻塞或结束，则 CPU 立即进行切换；
另外，时间片的长度就是一个很关键的点：
如果时间片设得太短会导致过多的进程上下文切换，降低了 CPU 效率；
如果设得太长又可能引起对短作业进程的响应时间变长。通常时间片设为20ms~50ms通常是一个比较合理的折中值。 - 最高优先级调度算法
进程的优先级可以分为，静态优先级或动态优先级：
静态优先级：创建进程时候，就已经确定了优先级了，然后整个运行时间优先级都不会变化；
动态优先级：根据进程的动态变化调整优先级，比如如果进程运行时间增加，则降低其优先级，如果进程等待时间（就绪队列的等待时间）增加，则升高其优先级，也就是随着时间的推移增加等待进程的优先级。
该算法也有两种处理优先级高的方法，非抢占式和抢占式
非抢占式：当就绪队列中出现优先级高的进程，运行完当前进程，再选择优先级高的进程。
抢占式：当就绪队列中出现优先级高的进程，当前进程挂起，调度优先级高的进程运行。
但是依然有缺点，可能会导致低优先级的进程永远不会运行。 - 多级反馈队列调度算法
- 设置了多个队列，赋予每个队列不同的优先级，每个队列优先级从高到低，同时优先级越高时间片越短；
- 新的进程会被放入到第一级队列的末尾，按先来先服务的原则排队等待被调度，如果在第一级队列规定的时间片没运行完成，则将其转入到第二级队列的末尾，以此类推，直至完成；
- 当较高优先级的队列为空，才调度较低优先级的队列中的进程运行。如果进程运行时，有新进程进入较高优先级的队列，则停止当前运行的进程并将其移入到原队列末尾，接着让较高优先级的进程运行；
可以发现，对于短作业可能可以在第一级队列很快被处理完。对于长作业，如果在第一级队列处理不完，可以移入下次队列等待被执行，虽然等待的时间变长了，但是运行时间也会更长了，所以该算法很好的兼顾了长短作业，同时有较好的响应时间。
内存页面置换算法
缺页中断
当 CPU 访问的页面不在物理内存时，便会产生一个缺页中断，请求操作系统将所缺页调入到物理内存。那它与一般中断的主要区别在于：
- 缺页中断在指令执行「期间」产生和处理中断信号，而一般中断在一条指令执行「完成」后检查和处理中断信号。
- 缺页中断返回到该指令的开始重新执行「该指令」，而一般中断返回回到该指令的「下一个指令」执行。
- 在 CPU 里访问一条 Load M 指令，然后 CPU 会去找 M 所对应的页表项。
- 如果该页表项的状态位是「有效的」，那 CPU 就可以直接去访问物理内存了，如果状态位是「无效的」，则 CPU 则会发送缺页中断请求。
- 操作系统收到了缺页中断，则会执行缺页中断处理函数，先会查找该页面在磁盘中的页面的位置。
- 找到磁盘中对应的页面后，需要把该页面换入到物理内存中，但是在换入前，需要在物理内存中找空闲页，如果找到空闲页，就把页面换入到物理内存中。
- 页面从磁盘换入到物理内存完成后，则把页表项中的状态位修改为「有效的」。
- 最后，CPU 重新执行导致缺页异常的指令。
上面所说的过程，第 4 步是能在物理内存找到空闲页的情况，那如果找不到呢？
找不到空闲页的话，就说明此时内存已满了，这时候，就需要**「页面置换算法」**选择一个物理页，如果该物理页有被修改过（脏页），则把它换出到磁盘，然后把该被置换出去的页表项的状态改成「无效的」，最后把正在访问的页面装入到这个物理页中。
- 最佳页面置换算法（OPT）：置换在「未来」最长时间不访问的页面
- 先进先出置换算法（FIFO）：选择在内存驻留时间很长的页面进行中置换
- 最近最久未使用的置换算法（LRU）：选择最长时间没有被访问的页面
- 时钟页面置换算法（Lock）
把所有的页面都保存在一个类似钟面的「环形链表」中，一个表针指向最老的页面。当发生缺页中断时，算法首先检查表针指向的页面：
- 如果它的访问位位是 0 就淘汰该页面，并把新的页面插入这个位置，然后把表针前移一个位置；
- 如果访问位是 1 就清除访问位，并把表针前移一个位置，重复这个过程直到找到了一个访问位为 0 的页面为止；
- 最不常用置换算法（LFU）：选择「访问次数」最少的那个页面
磁盘调度算法
- 先来先服务算法：移动磁道距离太长
- 最短寻道时间优先算法：可能导致饥饿
- 扫描算法：磁头在一个方向上移动，访问所有未完成的请求，直到磁头到达该方向上的最后的磁道，才调换方向，这就是扫描（Scan**）算法。**中间部分的磁道会比较占便宜，中间部分相比其他部分响应的频率会比较多，也就是说每个磁道的响应频率存在差异
- 循环扫描算法：只有磁头朝某个特定方向移动时，才处理磁道访问请求，而返回时直接快速移动至最靠边缘的磁道，也就是复位磁头，这个过程是很快的，并且返回中途不处理任何请求，该算法的特点，就是磁道只响应一个方向上的请求。
- LOOK 与 C-LOOK 算法：优化的思路就是磁头在移动到「最远的请求」位置，然后立即反向移动，不需要到达最开始的磁道，反向移动的途中会响应请求
C-LOOK，它的工作方式，磁头在每个方向上仅仅移动到最远的请求位置，然后立即反向移动，而不需要移动到磁盘的最始端或最末端，反向移动的途中不会响应请求