页面置换算法

功能:当缺页中断发生,并且物理内存已满时,选择内存中那个物理页面被替换的算法,尽量减少页面的换入换出。

有些页面需要常驻内存,页面锁定,操作系统的关键代码,时间关键进程

1 最优页面置换算法

 当我们知道程序将要需要调用的页号的序列,当发生页面置换时,将时间上最后使用的页面置换出去。

最优页面置换算法.jpg

示例

最优页面置换算法示例.jpg

2 先进先出算法(FIFO)

当发生页面置换时候,最先加入内存的物理页面置换出去

先进先出算法.jpg

示例

FIFO示例.jpg

3最近最近未使用算法(LRU)

当发生页面置换的时候,将最久未使用的页面置换出去

最近最久未使用算法.jpg

示例

LRU示例.jpg

实现

LRU实现.jpg

4 时钟页面置换算法

系统维护一个环形表,页面的数据结构添加一个访问位的数据段(0表示最近未访问,1表示最近发生过访问),一个指针用来指向上一次置换的页面的下一个位置(默认位置为第一个页面),只有当发生页面置换时,指针才移动到被置换的页面的下一个位置。

当发生页面置换的时候,指针会判断当前页面的访问位是否为0,

若访问位为0,直接替换当前页面,并将其的访问位置为1,指针指向下一个位置;

若访问位为1,则指针向后移动,遇到访问位为1的页面,将其访问位置为0,直到遇到页面访问位为0的页面,则停止移动,将访问位为0的页面替换,访问位置为1,指针移动到下一个位置。

当页面命中时,将命中页面的访问位置为1,指针位置不变

clock.jpg

示例

clock示例.jpg