页面置换算法
功能:当缺页中断发生,并且物理内存已满时,选择内存中那个物理页面被替换的算法,尽量减少页面的换入换出。
有些页面需要常驻内存,页面锁定,操作系统的关键代码,时间关键进程
1 最优页面置换算法
当我们知道程序将要需要调用的页号的序列,当发生页面置换时,将时间上最后使用的页面置换出去。
示例
2 先进先出算法(FIFO)
当发生页面置换时候,最先加入内存的物理页面置换出去
示例
3最近最近未使用算法(LRU)
当发生页面置换的时候,将最久未使用的页面置换出去
示例
实现
4 时钟页面置换算法
系统维护一个环形表,页面的数据结构添加一个访问位的数据段(0表示最近未访问,1表示最近发生过访问),一个指针用来指向上一次置换的页面的下一个位置(默认位置为第一个页面),只有当发生页面置换时,指针才移动到被置换的页面的下一个位置。
当发生页面置换的时候,指针会判断当前页面的访问位是否为0,
若访问位为0,直接替换当前页面,并将其的访问位置为1,指针指向下一个位置;
若访问位为1,则指针向后移动,遇到访问位为1的页面,将其访问位置为0,直到遇到页面访问位为0的页面,则停止移动,将访问位为0的页面替换,访问位置为1,指针移动到下一个位置。
当页面命中时,将命中页面的访问位置为1,指针位置不变
示例