页面置换算法：

1、页面置换算法的功能目标:

1.1 举例：

2、局部页面置换算法：

2.1最优页面置换算法：

基本思路：当一个缺页中断发生时，对于保存在内存当中的每一个逻辑页面，计算在它的下一次访问之前，还需要等待多长时间，从中选择等待时间的最长的那个，作为被置换的页面；
这只是一种理想情况，实际中无法实现，因为操作系统无法得知每一个页面需要等待多长时间之后才会被再次访问；
可以用作其它算法的性能评价依据。

例子:

2.2先进先出算法(FIFO)：

例子：

2.3最近最久未使用算法(LRU—Least Recently Used)：

（1）概念：

区别于FIFO算法，FIFO算法替换的是在内存中驻留时间最长的页面，是根据页面驻留时间长短来区分的；

而最近最久未使用算法对应的是页面的访问，是根据最近页面访问来决定的。

（2）例子：

通过栈来实现LRU算法（记录页面的访问次数及顺序）：

2.4时钟页面置换算法(Clock)：

（1）概念：

时钟页面置换算法需要用到页表中的访问位，当一个页面被装入内存时，设置为0，一旦被访问就设置为1（置1的操作是由硬件来完成的）；各个页面组织成一个环形链表，指针指向最老的页面，当发生缺页中断时，去看指针指向的最老的页面的访问位，为0则淘汰。

Clock算法因为只增加了一个used bit(一位)，因此总的来说比LRU算法更节省资源空间。

（2）时钟置换过程：

首先内存中存放了5个页面，每个页面的第一位为驻留位(判断该页是否存在于内存中)，第二位是访问位(判断该页最近是否被访问过，用于页面置换)，第三位是页帧号(用于查找对应的物理页面)。

当需要访问Page6时，首先会看内存中是否还有空间，因为没有空间就需要用到页面置换，查看指针指向的最老的页(这里为Page 0)，由于Page 0的访问位为1(表示最近刚刚被访问过)，因此会将Page 0的访问位置0然后接着顺时针继续查找，遇到访问位为1则置0，直到遇到访问位为0的为止。当遇到访问为为0的页面后就会进行替换，将新的页面的访问位置1然后指针指向下一个页面。

！注意：如果没有发生缺页异常，比如说需要访问Page 4，内存中恰好存在，会由硬件将对应页面的访问位置1，但是指针不会移动！！！

（3）实例：

2.5二次机会法(Enhanced Clock algorithm)：

（1）概念：

修改了Clock算法，新增了一个 drity bit位，该位主要用于记录页面访问过程中是否被修改过。

对于那些只读的页，它们的dirty bit为0，那么当used bit也为0的时候会直接被替换掉，当used为1时会将used bit 置0；

对于某些进行了修改的页面，修改过后它们的 dirty bit 会被置1，但是此时即使used bit 为0也仅仅会将used bit 置0，不会将该页给替换掉；而对于used bit 和　dirty bit 都为1 的页面，只会将used bit 置0；

这种做法保证了某些被修改过的页面不会轻易被替换掉，因为替换的过程是非常耗时的，操作系统需要将该页的数据写回到外存中来保证数据的统一。而对于只读的页面，由于数据始终是统一的，操作系统会将它们直接释放掉。

（2）实例：

2.6 最不常用算法(LFU —- Least Frequently Used)：

（1）概念：

LFU算法是根据页面数据访问的频率来决定替换哪个页面的。

2.7Belady现象及原因：

(1) Belady现象：

在采用FIFO 算法时，有时会出现分配的物理页面数增加，缺页率反而提高的异常现象；

(2) Belady现象的原因：

FIFO算法的置换特征与进程访问内存的动态特征是矛盾的，与置换算法的目标是不一致的(即替换较少使用的页面)，而FIFO算法替换调的是贮存在内存中时间最长的页面，因此，被它置换出去的页面不一定是进程不会访问的。

(3) Belady现象实例(增加了物理页面数，缺页率反而提高)：

FIFO算法只会体现页面存在内存中的时间，不会体现页面何时被访问的时间先后。

为什么FIFO算法会产生Belady现象，而LRU算法不会产生Belady现象：

解答：因为LRU算法符合栈算法的特点，而FIFO算法不符合栈算法的特点。栈算法的特点是给予的物理页帧越多，所产生的缺页中断次数就越少。

(4) LRU、FIFO和Clock算法的比较：

3、全局页面置换算法：

3.1 工作集模型：

（1）工作集模型[对程序局部性的分析与体现]:

（2）例子：

（3）工作集与常驻集的差异：

工作集：一个进程当前正在使用的逻辑页面的集合，该程序在访问过程中需要的页面是哪些，这些页面可以存在于内存中也可以不存在于内存中。可以用一个二元函数 W(t,^)来表示：

t是当前的执行时刻

^称为工作集窗口（working-set window），即一个定长的页面访问的时间窗口（^是不变的）

w(t,^)=在当前的时刻t之前的 ^时间窗口当中的所有页面所组成的集合(随着t的变化，该集合也在不断地变化)；

| W(t,^) |,值工作集的大小，集页面的数目；

常驻集：在当前时刻，进程实际驻留在内存当中的页面集合。

工作集是进程在运行过程中固有的性质，而常驻集取决于系统分配给进程的物理页面的数目，以及所采用的页面置换算法；

如果一个进程的整个工作集都在内存当中，即常驻集包含或者等于工作集，那么进程将很顺利地进行，而不会产生太多的缺页中断（直到工作集发生剧烈的变动，从而过渡到另外一个状态）；

当进程常驻集的大小达到某个数目以后，再给它分配更多的物理页面，缺页率也不会明显的下降。