模拟 LRU 页面置换算法

题目介绍

本题目要求模拟操作系统中使用的LRU（最近最少使用）页面置换算法。LRU算法是一种性能优异的页置换策略，它根据页面的使用频率来决定哪些页面应该被置换出物理内存。当一个页面被访问时，如果物理内存已满，LRU算法会替换掉最长时间未被访问的页面。

本题可参考第七章 操作系统常用算法中的LRU 页面置换算法

题目要求

  • 实现 lru_page_replacement 函数，模拟LRU页面置换算法。
  • 处理页面访问序列，并根据物理内存的页框数量进行页面置换。
  • 每次页面访问后，输出当前物理内存中的页面状态。

输入

  • 第一行：虚拟内存页访问序列（以逗号分隔的整数）。
  • 第二行：物理内存的页框数量（整数）。

输出

  • 每次页面访问后的物理内存状态，格式为 Access:<page>,Frames:[<frame1>,<frame2>,...]。

示例

  • 输入： 
    0,1,2,0,1,3,0
3
  • 输出： 
    Access:0,Frames:[0,-1,-1]
Access:1,Frames:[0,1,-1]
Access:2,Frames:[0,1,2]
Access:0,Frames:[0,1,2]
Access:1,Frames:[0,1,2]
Access:3,Frames:[0,1,3]
Access:0,Frames:[0,1,3]

代码介绍

main.c

主函数文件，用于处理命令行参数并调用 lru_page_replacement 函数。它使用 strdup 函数复制输入的页面访问序列，并检查内存分配是否成功。

int main (int argc, char *argv[]) {
    // ...
    lru_page_replacement(queue_frames, num);
    return EXIT_SUCCESS;
}

lru.c

应包含 lru_page_replacement 函数的实现，但当前为空，需要编写。该函数需要模拟LRU页面置换算法。

void lru_page_replacement(char *queue_frames, int num) {
    // TODO
}

lru.h

包含 lru_page_replacement 函数的声明和任何必要的数据结构。

详细提示信息

LRU算法逻辑

  • 使用数据结构（如链表或哈希表）来跟踪页面的访问顺序和内存中的页面状态。
  • 遍历页面访问序列，对于每个页面访问：
    • 如果页面已加载在内存中，更新其为最近访问的状态。
    • 如果页面未加载，检查是否有足够的空闲页框：
      • 如果有，加载页面。
      • 如果没有，根据LRU算法找到并置换最长时间未被访问的页面，然后加载新页面。

内存管理

  • 确保使用合适的数据结构来有效模拟页面的加载和置换过程。

输入处理

  • 在 main.c 中，解析命令行参数，获取页面访问序列和页框数量。

输出格式化

  • 在每次页面访问后，按照要求的格式输出当前内存状态。

测试

  • 编译程序，并使用示例输入进行测试，验证输出的正确性。

注意事项

  • 确保 lru_page_replacement 函数正确实现LRU置换逻辑。
  • 注意内存分配和释放，避免内存泄漏。
  • 确保输出格式与题目要求一致。
  • 参与者需要根据题目要求，完成 lru_page_replacement 函数的实现，确保能够正确模拟LRU页面置换算法。通过这个练习，可以加深对操作系统内存管理和页面置换算法的理解。