内存页面置换调度和磁盘调度算法

页面置换算法的功能：当出现缺页异常，需调入新页面而内存已满时，选择被置换的物理页面，也就是说选择一个物理页面换出到磁盘，然后把需要访问的页面换入到物理页。

常见的页面置换算法：
1.最佳页面置换算法(OPT)
2.先进先出置换算法(FIFO)
3.最近最久未使用的置换算法(LRU)
4.时钟页面置换算法(Lock)
5.最不常用置换算法

$\textbf{最佳页面置换算法}$ ：
置换在 $\color{red}{未来}$ 最长时间不访问的页面

image.png

这是一个理想的算法，在实际系统中无法实现。因为程序访问页面时是动态的，我们是无法预知每个页面在「下一次」访问前的等待时间。

$\textbf{先进先出置换算法}$ ：选择在内存中驻留时间很长的页面中进行置换。

image.png

$\textbf{最近最久未使用的置换算法}$ ：当发生缺页时，选择最长时间没有被访问的页面进行置换。

这种算法近似最优置换算法，最优置换算法是通过「未来」的使用情况来推测要淘汰的页面，而 LRU 则是通过「历史」的使用情况来推测要淘汰的页面。
LRU算法是可以实现的，但是代价比较高。为了实现LRU,需要在内存中维护一个所有页面的链表，最近最多使用的页面在表头，最近最少使用的页面在表尾。

困难的是：在每次访问内存时都必须要更新整个链表。在链表中找到一个页面，删除它，然后把它移动到表头是一件非常耗时的操作。

$\textbf{最不常用算法}$ ：它表示的意思不是这个算法不常用，而是当发生缺页中断时，选择访问次数最少的那个页面，并将其淘汰。

$\textbf{时钟页面置换算法}$

$\color{red}{二、磁盘调度算法：}$
磁盘调度算法的目的：为了提高磁盘的访问性能，一般是通过优化磁盘的访问请求顺序来做到的。
$\color{blue}{磁盘访问时间}$ ：寻道时间 + 扇区移到磁头下面所经历的时间 + 传输时间 (指把数据从磁盘读出或向磁盘写入数据所经历的时间)

寻道时间是磁盘访问最耗时的部分，如果请求顺序优化的得当，必然可以节省一些不必要的寻道时间，从而提高磁盘的访问性能。

常见的磁盘调度算法有：
先来先服务算法
最短寻道时间优先算法
扫描算法
循环扫描算法
LOOK 与 C-LOOK 算法
假设下面有一个请求序列，每个数字代表磁道的位置：
98，183，37，122，14，124，65，67

image.png