实现LRU算法及近似算法的实验报告

"东南大学操作系统实验要求学生实现LRU页面置换算法及其近似算法，包括LRU的计数器实现、栈实现、Additional-Reference-Bits Algorithm和Second-chance Algorithm。实验目标是理解和比较不同算法的复杂度、实现难度以及页错误率。实验流程包括随机生成页面访问序列并运用实现的算法进行测试。主要数据结构是LRU缓存类，采用关联容器存储键值对，使用列表来维护最近使用顺序。" 在操作系统的虚拟内存管理中，LRU（Least Recently Used）页面置换算法是一种常见的策略，它选择最近最少使用的页面进行替换。在本实验中，学生需要编写程序实现LRU的两种不同实现方式：计数器和栈。计数器实现通常涉及到每个页面的访问计数，当内存满时，淘汰计数值最小的页面。而栈实现则利用栈的后进先出特性，将最近访问的页面移到栈顶，当需要替换时，淘汰栈底的页面。 此外，实验还涉及了两个近似算法：Additional-Reference-Bits Algorithm和Second-chance Algorithm。Additional-Reference-Bits Algorithm是在每个页面标志位增加一个参考位，如果页面被访问，则参考位翻转，置换时优先考虑参考位为1的页面。Second-chance Algorithm则使用一个FIFO（先进先出）队列，当需要替换页面时，如果当前页面被访问过，则将其移至队尾，否则直接淘汰。 实验的核心部分是编写测试程序，通过随机生成的页面访问序列，模拟实际的内存操作，计算并比较各个算法的页错误率。页错误率是衡量算法性能的重要指标，它表示由于页面不在内存中导致的缺页次数与总页面访问次数之比。 在数据结构方面，LRU Cache类使用了C++的模板类，包含了一个大小为_max_size的关联容器（如unordered_map）来快速查找页面，以及一个列表（list）来维护页面的顺序。当插入新的键值对时，首先检查该键是否已存在，如果存在则更新其在列表中的位置，然后从容器和列表中删除旧的键值对。如果容器已满，新插入的键值对将替换最不常使用的页面。 通过这个实验，学生不仅能够深入理解LRU算法的原理，还能掌握如何用编程语言实现这些算法，同时对比分析不同算法的优劣，进一步巩固了对虚拟内存管理的理解。