分页
页表及其作用
- 页表：操作系统中的一种数据结构，用于管理虚拟内存与物理内存之间的映射关系。
- 作用：实现虚拟地址到物理地址的转换，管理内存，提供内存保护，并支持虚拟化技术。
虚拟内存与物理内存
- 虚拟内存：为进程提供独立的地址空间，大小可能超过物理内存。
- 物理内存：计算机系统中实际存在的内存。
- 使用虚拟内存的好处：扩展内存容量、内存隔离、简化程序设计、提高性能。
虚拟地址到物理地址的映射
- 映射过程：通过页表转换虚拟地址为物理地址。
- 三级页表转换：逻辑地址转线性地址，再由线性地址转物理地址。
页面置换算法的功能
当出现缺页异常，需调入新页面而内存已满时，选择被置换的物理页面
最佳页面置换算法
最佳页面置换算法基本思路是，置换在未来最长时间不访问的页面。
缺页共发生了 7 次（空闲页换入 3 次 + 最优页面置换 4 次），页面置换共发生了 4 次。
无法预知每个页面在下一次访问前的等待时间。
最佳页面置换算法作用是为了衡量算法的效率，你的算法效率越接近该算法的效率，那么说明你的算法是高效的。
选择在内存驻留时间很长的页面进行中置换
最近最久未使用（LRU）的置换算法
根据历史推测要淘汰的页面，选择最长时间没有被访问的页面进行置换
- 开销比较大
实现方式
- 使用双向链表记录页面访问历史，链表头为最近使用的页面，尾部为最久未使用的页面。
- 访问页面时，若页面存在于链表中则将其移到头部；若不在链表中且缓存未满，则将页面插入头部，若缓存已满，则删除尾部页面并插入新页面。
时钟页面置换算法
环形链表
如果它的访问位位是0就淘汰该页面，并把新的页面插入这个位置，然后把表针前移一个位置
如果访问位是1就清除访问位，并把表针前移一个位置，重复这个过程直到找到了一个访问位为0的页面为止；
当发生缺页中断时，选择访问次数最少的那个页面，并将其淘汰。
访问计数器
定期减少访问的次数