东莞理工学院城市学院
《计算机操作系统》课程设计
题 目： 采用
LFU
算法仿真请求分页系统
专 业： 软件工程
年 级： 20 12
级
小组成员： 陈炜杰、陈敬东
指导教师： 彭义春 老师
时 间： 201 4 . 12 . 24 —201 4 . 12 . 26
地 点： 7B310
东莞理工学院城市学院计算机与信息科学系制
2012 年 5 月
摘要
无论是在批处理系统还是分时系统中，用户进程数一般都多于处理机数、这将导
致他们互相争夺处理机。另外，系统进程也同样需要使用处理机。但是处理机在某一
时刻只能执行一个进程，这就引入了进程调度这一机制！进程调度程序按一定的策略，
动态地把处理机分配给处于就绪队列中的某一个进程，以使之执行。
进程调度的主要功能是按照一定的策略选择一个处于就绪状态的进程，使其获得
处理机执行。应根据不同的系统设计目的，选择最佳合适的饿进程调度算法。而此次
系统中用到的算法有优先级调度算法，时间片轮转算法！
当发生缺页中断时，如果操作系统内存中没有空闲页面，则操作系统必须在内存
选择一个页面将其移出内存，以便为即将调入的页面让出空间，而 LFU 算法便是将近
期使用最少的页面作为淘汰页。轮转调度算法即让就绪队列上的每个进程每次运行一
个时间片，因此每个进程每次大约都获得同样的处理机时间。
目录
1. 概述.................................................................................................................................................4
2. 课程设计任务及要求.....................................................................................................................5
2.1 设计任务...............................................................................................................................5
2.2 设计要求...............................................................................................................................5
3. 算法及数据结构.............................................................................................................................6
3.1 算法的总体思想...................................................................................................................6
3.2 数据结构模块.......................................................................................................................7
3.2.1 功能............................................................................................................................7
3.2.2 数据结构....................................................................................................................7
3.3 近期最少使用（LFU）算法模块.......................................................................................8
3.3.1 功能............................................................................................................................8
3.3.2 数据结构....................................................................................................................8
3.3.3 算法............................................................................................................................8
3.4 时间片轮转调度模块.........................................................................................................10
3.4.1 功能..........................................................................................................................10
3.4.2 数据结构..................................................................................................................10
3.4.3 算法..........................................................................................................................10
4. 程序设计与实现...........................................................................................................................11
4.1 程序流程图.........................................................................................................................11
4.2 程序代码.............................................................................................................................11
4.3 实验结果.............................................................................................................................13
5. 结论...............................................................................................................................................16
6. 收获、体会和建议.......................................................................................................................17
7. 参考文献.......................................................................................................................................18
1. 概述
设计目的：用高级语言编写和调试一个内存分配程序，加深对内存分配算法的理解。
虚拟存储技术就是从逻辑上扩充内存容量从而加快速度，近期最少使用（ LFU）算法是将
最近时期使用最少的页面作为淘汰页，这些页在开始时使用次数很多，但以后就不再使用
而这类页将会长时间留在内存中，因此把这些页替换出去从而产生空闲页面。
2. 课程设计任务及要求
2.1
2.1
设计任务
设计任务
采用近期最少使用（LFU）算法仿真请求分页系统
分工：
陈敬东：查找资料，将近期最少使用（LFU）算法以及时间片轮转调度（RR）算法结
合，按照题目要求一步步完善系统功能。
陈炜杰：查找相关资料，然后编写近期最少使用（LFU）算法。实现到算法之后，再
合并到陈敬东的主函数中区，得到整体的程序，协助陈敬东一起修改程序，编写报告。
2.2
2.2
设计要求
设计要求
进程调度算法：采用（1）近期最少使用（LFU）算法（2）时间片轮转法
1) 实现请求分页存储管理方式的页面置换算法：近期最少使用算法（LFU）
2) 内存物理块数固定为 15 个，对多个作业采用可变分配全局置换的策略分配物理块
3) 作业数量与作业大小（10-20 页）可在界面进行设置
4) 所有作业按 RR 算法进行调度，时间片长度为 1 秒
5) 可为每个作业随机产生引用的页面串，也可以人工输入引用的页面串，页面串长度
50---100，要求必须包括作业所有的页面，可作为样例数据保存
6) 可读取样例数据（要求存放在外部文件中）进行作业数量、作业大小、页面串长度
的初始化
7) 要求采用可视化界面，模拟内存分配和使用情况图，可在运行过程中随时暂停，查
看当前内存物理块使用情况。
8) 每次全部作业运行结束后，要求打印出访问命中率
