一、缺⻚异常(缺⻚中断)
缺⻚异常(缺⻚中断)
当 CPU 访问的⻚⾯不在物理内存时,便会产⽣⼀个缺⻚中断,请求操作系统将所缺⻚调⼊到物理内存。就需要「⻚⾯置换算法」选择⼀个物理⻚,把它换出到磁盘,最后把正在访问的⻚⾯装⼊到这个物理⻚中。
⻚⾯置换算法的功能是,当出现缺⻚异常,需调⼊新⻚⾯⽽内存已满时,选择被置换的物理⻚⾯,也就是说选择⼀个物理⻚⾯换出到磁盘,然后把需要访问的⻚⾯换⼊到物理⻚。
二、最佳⻚⾯置换算法
最佳⻚⾯置换算法基本思路是,置换在「未来」最⻓时间不访问的⻚⾯。
所以,该算法实现需要计算内存中每个逻辑⻚⾯的「下⼀次」访问时间,然后⽐较,选择未来最⻓时间不访问的⻚⾯。
这很理想,但是实际系统中⽆法实现,因为程序访问⻚⾯时是动态的,我们是⽆法预知每个⻚⾯在「下⼀次」访问前的等待时间。所以,最佳⻚⾯置换算法作⽤是为了衡量你的算法的效率,你的算法效率越接近该算法的效率,那么说明你的算法是⾼效的。
三、先进先出置换算法
选择在内存驻留时间很⻓的⻚⾯进⾏中置换,这个就是「先进先出置换」算法的思想。
跟最佳⻚⾯置换算法⽐较起来,先进先出置换算法性能差了很多。
四、最近最久未使⽤的置换算法
最近最久未使⽤(LRU)的置换算法的基本思路是,发⽣缺⻚时,选择最⻓时间没有被访问的⻚⾯进⾏置换,也就是说,该算法假设已经很久没有使⽤的⻚⾯很有可能在未来较⻓的⼀段时间内仍然不会被使⽤。
这种算法近似最优置换算法,最优置换算法是通过「未来」的使⽤情况来推测要淘汰的⻚⾯,⽽ LRU 则是通过「历史」的使⽤情况来推测要淘汰的⻚⾯。
LRU实现的代价很⾼。需要在内存中维护⼀个所有⻚⾯的链表,最近最多使⽤的⻚⾯在表头,最近最少使⽤的⻚⾯在表尾。在每次访问内存时都必须要更新「整个链表」。在链表中找到⼀个⻚⾯,删除它,然后把它移动到表头是⼀个⾮常费时的操作
五、时钟⻚⾯置换算法
时钟⻚⾯置换算法就可以两者兼得,它跟 LRU 近似,⼜是对 FIFO 的⼀种改进。
该算法的思路是,把所有的⻚⾯都保存在⼀个类似钟⾯的「环形链表」中,⼀个表针指向最⽼的⻚⾯。
当发⽣缺⻚中断时,算法⾸先检查表针指向的⻚⾯:
如果它的访问位位是 0 就淘汰该⻚⾯,并把新的⻚⾯插⼊这个位置,然后把表针前移⼀个位置;
如果访问位是 1 就清除访问位,并把表针前移⼀个位置,重复这个过程直到找到了⼀个访问位为 0 的⻚⾯为⽌;
六、最不常⽤算法(LFU)
当发⽣缺⻚中断时,选择「访问次数」最少的那个⻚⾯,并将其淘汰
但还有个问题,LFU 算法只考虑了频率问题,没考虑时间的问题,⽐如有些⻚⾯在过去时间⾥访问的频率很⾼,但是现在已经没有访问了,⽽当前频繁访问的⻚⾯由于没有这些⻚⾯访
问的次数⾼,在发⽣缺⻚中断时,就会可能会误伤当前刚开始频繁访问,但访问次数还不⾼的⻚⾯。