东南大学操作系统实验——实现LRU算法及其近似算法

编写程序实现LRU算法及其近似算法，并分析各算法的时间复杂度、空间复杂度和实现难度；通过随机生成页面访问序列，测试所实现算法的页错误率，并加以比较和分析。 此资源含完整代码和完整实验报告（加上你的学号姓名即可提交） 在本实验中，学生将深入理解操作系统的内存管理机制，特别是LRU（Least Recently Used，最近最少使用）页面置换算法。LRU算法是一种常见的虚拟内存管理策略，它根据页面的使用历史来决定替换哪个页面。当内存中的页面被新页面占用时，LRU算法会优先淘汰最近最久未使用的页面。 实验内容包括实现LRU算法的两种不同变体：计数器实现和栈实现。在计数器实现中，每个页面都有一个访问计数器，每当页面被访问时，计数器增加，淘汰时选择计数最小的页面。而在栈实现中，页面按访问顺序存储在栈中，最近访问的页面位于栈顶，淘汰最底部的页面。另外，实验还涉及了Additional-Reference-Bits Algorithm（附加引用位算法）和Second chance Algorithm（第二次机会算法），这些都是LRU的近似算法。 实验的主要数据结构是一个模板类`lru_cache`，它基于关联容器`std::unordered_map`和双向链表`std::list`实现。`unordered_map`用于快速查找页面，而`list`则保持页面的访问顺序。`put()`方法用于插入或更新页面，`get()`方法用于访问页面，如果页面不存在则抛出异常，`exists()`检查页面是否存在，`size()`返回缓存中页面的数量。当缓存满时，`put()`方法会淘汰最不常使用的页面。 实验的目的是让学生掌握LRU算法的原理，通过实际编程实现加深理解，并对比不同实现的复杂度和难度。时间复杂度方面，LRU算法通常表现为O(1)，因为查找、插入和删除操作都在平均情况下具有常数时间复杂度。空间复杂度取决于缓存的最大大小，即`_max_size`。实现难度在于如何有效地维护页面的访问顺序和页面映射。 实验过程包括随机生成页面访问序列，调用实现的算法来决定是否需要进行页面置换。通过统计页错误率，即因页面不在内存中而引起的缺页次数，可以评估各种算法的性能。通过对不同算法的页错误率比较，可以分析它们的优劣。 此外，Additional-Reference-Bits Algorithm利用每个页面的引用位来近似LRU，而Second chance Algorithm则通过修改FIFO（先进先出）算法，给予最近使用过的页面第二次机会，从而提高效率。这些近似算法在实现上可能比精确的LRU更简单，但可能会牺牲一定的性能。 这个实验旨在让学生通过实践了解并掌握LRU算法及其近似算法，通过分析和比较，提升对虚拟内存管理的理解和应用能力。