调度算法

进程调度算法

见进程管理小节

内存页面置换算法

缺页异常

缺页中断和一般的中断有些区别，它会在指令执行期间产生和处理中断信号，而非指令执行完成后；且在缺页中断返回后，重新执行原指令，而一般指令返回到下一条指令

其具体流程是：

1. CPU读写某个物理地址，MMU查找页表，若有效则加载，否则产生缺页异常中断
2. OS收到中断，执行handler，在磁盘中找该页，然后把它换入到内存中的某个空闲页，标记PTE为有效
3. 重新执行原指令

若无空闲页，则需根据 内存页置换算法 换出一个页到磁盘中，常见的算法有这几种：

OPT 最佳页面置换算法

选择内存中未来最长时间不被访问的页进行替换，但页何时被访问是无法预知的，所以不可行

它一般用于衡量置换算法的效率，越接近OPT越好

FIFO 先进先出

LRU 最久未使用

理论可以实现，但是在链表中找到它，然后移动到表头比较费时，很少用

时钟页面置换算法

维护一个环形链表，表针指向最老的页，需要置换页时：

• 检查当前访问位，为1则递增表针指向下一个页，直到为0，置换这个页

LFU 最不常用

将访问次数最少的页淘汰，为每个页维护一个访问计数，每次被访问+1，需要置换时淘汰掉计数最小的

LFU 只考虑了频率没考虑总时间，且增加一个计数器以及找最不常访问的页都是非常耗时的

前者的一个解决方法是，定时折半访问次数

磁盘调度算法

对于机械硬盘，一般通过优化磁盘的访问顺序提高性能。寻道和转盘是最耗费时间的操作

FCFS：耗费大量时间寻址

SSF：最短寻道时间，贪心。但可能造成饥饿

扫描：按请求序列中的一个方向移动到边缘，过程中响应请求，然后反向扫描。中间的磁道响应较快，存在频率差异

循环扫描：扫描一个方向到边缘后，直接回到起始位置，中间不处理任何请求。速度比较平均

LOOK：扫描一个方向到最远请求，反向移动过程中会响应请求
C-LOOK：LOOK+反向移动过程中不会响应请求，公平的LOOK