Ting's Blog

最少使用置换算法 (LFU, Least Frequently Used) 是一种基于页面访问频率的页面置换算法，其核心思想是将内存中使用频率最少的页面作为置换候选，确保较少被访问的页面优先被淘汰。LFU 算法适用于需要精确控制页面访问频率的场景，但在实际应用中常常因为实现复杂性和性能瓶颈而需要进行优化。

实际实现

最近最久未使用（LRU）算法 的实现可以通过移位寄存器或栈的方式完成。这两种方式各有特点：

1. 用移位寄存器实现 LRU

移位寄存器是一种硬件或软件模拟的寄存结构，通过移位操作记录页面访问的历史。实现过程如下：

• 每个页面框分配一个寄存器，初始值为 0。

• 每次页面访问时，将该寄存器的最高位置为 1，其余位依次右移。

• 未访问的页面寄存器位移后会逐渐变成更小的值。

• 页面置换时，选择寄存器值最小的页面，即最久未使用的页面。

这种实现方式简单直观，但寄存器的位数增加会带来更多硬件需求，因此通常适合于特定规模的小型系统【18】【19】。

2. 用栈实现 LRU

通过栈来管理页面访问，栈顶表示最近使用的页面，栈底表示最久未使用的页面：

• 每次页面被访问时，若其已在栈中，则将其从原位置移除并放到栈顶。

• 若页面不在栈中，则将其直接插入栈顶。

• 如果栈已满，移除栈底元素（最久未使用页面），然后插入新页面。

栈的实现可以通过链表实现动态插入删除操作，同时保证页面顺序的调整。相比移位寄存器，栈方法适合于较大规模的系统，灵活性更高，但需要额外的空间来存储栈【18】【19】。

以上两种方法在实际系统中应用时，还会因性能需求选择优化的数据结构（如哈希表结合链表），以便实现更高效的页面访问与置换管理。

移位寄存器（Shift Register）是一种数字电路，用于将数据按照一定规则在其存储单元之间移动。它是由一组触发器（Flip-Flop）组成的逻辑电路，每个触发器存储一个位数据。

记一下文章"关于"页的书写

插件地址codepzj/hexo-graph: hexo-graph，一个基于echarts，集成博客热力图，博客月份统计图，分类统计图，标签统计图的多元化插件。

总结

• 页面框是物理内存中的固定大小块，用于存储虚拟内存的页。

• 通过分页机制，操作系统可以高效管理内存，提高内存利用率，并支持更大的虚拟地址空间。

请求分页-物理块分配算法对比总结

在实际系统中，按比例分配算法和考虑优先权的分配算法更常见，因为它们能够更好地适应动态环境的需求。

请求分页-物理块分配策略

固定与可变

固定与可变的区别在于给进程分配的物理块数

即固定是指在给每个进程均分配固定数量的物理块

可变即根据进程的不同，分配不同数量的物理块

全局与局部

即，当进程执行是发生缺页后，换入换出操作执行的范围

局部 即，当进程要执行换入换出操作时，仅在操作系统为该进程分配的物理空间之内发生替换，而不会影响其他进程块

全局 即，当前进程需要换入缺页的部分时，不仅仅会挑选当前进程拥有的物理块，还可能会换出其他进程的物理块。