操作系统上机作业（二）：LRU算法

本项目是一个基于 Qt designer 和 Python 的模拟 LRU算法 运算过程的展示。

图形化用户界面

相关文件

• MyGUI.ui

先在 Qt designer 上设计好界面，再导出成 ui 文件，用于直接调用。

算法实现

相关文件

• main.py

主要数据结构

• 使用字典 vis 记录某一编号的页面是否在内存中
• 使用字典 time 记录某一编号的页面上一次被处理机处理的时间
• 使用列表 phyblock 存储当前时刻处于内存中的页面的编号。

时间复杂度

依次处理每则信息，对于每一则信息有缺页中断、页面置换、页面已存在三种情况，最坏的情况是页面置换，需要遍历内存中已存在的所有页面，找到上一次被处理的时间最早的页面替换掉，因此算法总的时间复杂度为 $O(N\times K)$，其中 $N$ 为待处理信息总数， $K$ 为分配给该程序的物理块总数。