存储器管理：页面置换算法与LFU策略

“其它置换算法-第四章 存储器管理” 在计算机系统中，存储器管理是操作系统的重要组成部分，主要关注如何有效地分配和使用有限的内存资源。本章主要讨论了存储器的层次结构、程序的装入和链接，以及各种存储管理方式，特别是页面置换算法。其中，重点关注了“最少使用”（LFU：Least Frequently Used）置换算法。 4.8.4 其它置换算法 - 最少使用（LFU）置换算法 LFU算法是一种页面置换策略，它的核心思想是在内存中的页面被访问时，记录其访问频率。当需要替换页面时，选择最近使用最少的页面进行淘汰。LFU算法通常使用移位寄存器来跟踪页面的访问频率。每次访问一个页面，就将该页面的移位寄存器最高位设为1，然后每隔一定时间（例如100毫秒）将所有寄存器右移，这样低频率访问的页面的移位寄存器值会更小。在最近一段时间内，移位寄存器总和（∑Ri）最小的页面被视为使用最少的页面，从而被替换出去。 存储器的层次结构 存储器层次结构包括CPU寄存器、主存储器和辅助存储器（如磁盘）。寄存器和高速缓存位于顶端，提供最快但有限的存储空间。主存储器位于中间，速度较慢但容量较大，而辅助存储器容量最大但访问速度最慢。高速缓存（如L1、L2和L3缓存）位于主存和寄存器之间，通过预加载常用数据来减少主存访问次数，提高性能。磁盘缓存则利用主存空间临时存储频繁访问的磁盘数据，进一步优化I/O操作。 程序的装入和链接 程序的执行过程包括编译、链接和装入。编译阶段，源代码被转换为目标模块；链接阶段，目标模块与所需库函数合并形成一个装入模块；装入阶段，装入模块被加载到内存中。装入方式有绝对装入、可重定位装入和运行时装入，分别适用于不同环境和需求。 4.1 存储器的层次结构 - CPU寄存器：提供最快的数据访问，但容量极小。 - 主存储器：存储运行中的程序和数据，访问速度次之，容量比寄存器大。 - 高速缓存：介于主存和寄存器之间，提高内存访问速度。 - 辅助存储器：如磁盘，容量最大，但访问速度慢。 4.2 程序的装入和链接 - 绝对装入：程序在编译时确定在内存中的位置。 - 可重定位装入：程序在装入时根据内存空闲位置动态调整地址。 - 运行时装入：程序在运行时才装入内存，允许动态加载和卸载。 页面置换算法是虚拟存储器管理的关键，LFU算法是其中的一种策略，旨在优化内存资源的使用，提高系统性能。其他常见的页面置换算法还包括最近最久未使用（LRU）、最佳（OPT）等。这些算法的选择和实现直接影响着系统的效率和响应时间。