操作系统之缺页中断
详解缺页中断—–缺页中断处理（内核、用户）_柯南的博客-CSDN博客_缺页中断
缺页是什么
进程毕竟是虚拟地址，真实映射的地址又可能就是在外存中
那又不能直接用外存，当真实指到那个地址的时候，就产生缺页中断
我也不懂
以上是我胡说的
我胡说对了
详解缺页中断—–缺页中断处理（内核、用户）_柯南的博客-CSDN博客_缺页中断
前面说过页表中可能存放的不止是物理地址，还有一些控制位，比如列举的读写bit位
现在再列举一个，缺页bit位，如果物理地址是内存的物理地址的话，那么该bit位为1，否则该bit位为0，发生缺页中断
再强调一遍，页表项中不止存有物理地址，还有一些控制位
dirty bit读写控制，1表示只能读，0表示既能读又能写
resident bit在不在内存位，1在内存中，0不在内存中触发缺页中断
used bit/ access bit在clock算法中用到
不在内存中可能在外存中，也可能是页表中没有记录，也可能根本就没有这个数据
缺页中断的原因
暂且跳过
缺页中断的处理方法
【清华大学】操作系统 陈渝 全113讲（上）_哔哩哔哩_bilibili
就是内存满了，需要读入新数据内存，把老数据置换出去
替换的方法是什么
希望尽可能减少这样的操作，提高速度，减少缺页中断的次数
有些数据要常驻内存，如操作系统，要用锁定的方法锁定这些资源
最优页面置换算法 OPT
对于目前保存在内存中的每个逻辑页面，计算下次访问前还需要多长时间，等待时间最长的替换出去
但操作系统不能预知未来发生的事情
只能把它当成一个评价标准
先进先出算法 First-In First-Out FIFO
选择内存中驻留时间最长的页面淘汰
维护一个链表，最长的页面放在链表头部，新进来的放在链表尾部，逐步淘汰头部
优点是执行简单，只需要维护一个列表，用一个单一指针就可以
性能较差，为什么
产生的缺页次数很多，可能驻留时间最久的页面是经常要访问的页面
Belady现象
Belady现象：给的物理页越多，按道理缺页次数越少，FIFO算法是给的物理页越多，缺页次数也越多，为什么？
最近最久未使用算法 Least Recently Used LRU
选择最久未被使用的页面进行淘汰，区分FIFO是完全不一样的
是个OPT的近似，基于过去推测未来（程序局部性原理：程序具有时间局部性和空间局部性）
怎么实现的
需要记录各个页面的使用时间顺序，开销比较大
链表实现：头部放刚刚使用过的节点，每用到一次，需要查找，找到的话从链表中找出来，放到头部，最后缺页中断发生的时候，淘汰末尾节点，找不到的话就直接放到头部即可。
和FIFO不一样，淘汰尾部节点
还可以用栈，访问某页，压入栈顶，向下查找，找到就删除掉，
淘汰的时候选栈底，它是最久未被使用的
迷惑，为什么不用queue
优点
效果好，局部原理
缺点
开销大，每访问一个页面都需要查找，查找很费事费时
时钟页面置换算法 Clock
LRU的近似，FIFO的改进
不精确记录访问的先后顺序，
页表项 访问位 access bit，页面装入内存时，该位初始化为0，程序访问后页表项该bit位置1，硬件完成，
粗略代替，如果该位为1，那么就证明最近访问过?
迷惑，访问过一次就置1，那么都访问过，不都置1吗
下面回答这个迷惑的问题
各个页面组织成环形链表，指针指向最古老的页面
缺页中断时，如果该指针的accessbit/usedbit为0立即淘汰，否则置0，指针下移直到找到被淘汰的页面，替换页面，指针指向下一个节点
这个环形类似于钟表面，因此是始终算法
需要一个环形链表和一个指针来实现
二次机会法 Enhanced Clock Alogrithm
Clock算法的缺点，没有区分读和写，读写都算访问
dirty bit，就是刚才的读写位，回顾，置1只能写，置0读写均可
dirty bit一直是0，如果做了一个写操作置1，读操作不改变
dirty bit也是硬件完成
区分读和写对页面置换算法有什么帮助？
如果内存中的数据为0，说明该页面在内存的生活周期都是读操作，那么它的数据和硬盘中存储的是一样的，因此淘汰该页也仅仅需要释放内存，不需要store函数存到硬盘中
如果dirty bit为1，那么释放页面需要更改硬盘中数据，更为费时
利用这个方法，优化Clock算法，减少对硬盘的访问
环形链表用access bit和dirty bit共同决定置换出的页面
如果ab和db都是0，都替换出去
如果ab0，db1，db清零，指针继续旋转
ab1，db0，ab清零，指针继续旋转
ab1，db1，ab清零，db不变
最不常用算法 Least Frequently Used LFU
选择最近访问次数最少的并进行淘汰
与LRU的区别，一个是最久没有访问，一个是访问次数最少
有一个页面在程序运行时访问很多次，后面一段时间内没有访问
每个页面有个计数器，缺页时遍历每一个页的技术器
增加了很大的内存开销
对计数器进行查找，查找时间和查找算法需要耗费很多资源
改进办法，每隔一段时间右移一位就是 / 2
每次发生缺页中断，所有计数清零？
其他关于缺页中断的补充
Belady现象
分配给一个正在运行的进程的页数越多，按道理产生缺页中断就越少，
但是有的时候出现缺页次数增加的异常情况
例如FIFO算法
这就暴露了FIFO算法的问题，它所替换的并不是以后不会被访问到的页面
链表没有任何变化，只要在页面中就可以，不会更新
LRU算法时没有Belady现象
LRU算法符合栈算法特点
FIFO算法不符合
FIFO LRU Clock算法比较