长 春 大 学 课程设计纸
目 录
共 8 页 第 1 页
┊
┊
┊
┊
┊
┊
┊
┊
┊
┊
┊
┊
┊
装
┊
┊
┊
┊
┊
订
┊
┊
┊
┊
┊
线
┊
┊
┊
┊
┊
┊
┊
┊
┊
┊
┊
┊
┊
长 春 大 学 课程设计纸
LRU 算法
1 前言
操作系统(OS)是配置在计算机硬件上的第一层软件,是对硬件系统的
首次扩充。它在计算机系统中占据了重要的地位;而其他的诸如汇编程序、编
译程序、数据库管理系统等系统软件,以及大量的应用软件,都将依赖于操作
系统的支持,取得它的服务。操作系统已成为现在计算机系统、多处理机系统 ,
计算机网络、多媒体系统以及嵌入式系统中都必须配置的、最重要的系统软件 。
其主要任务是为多道程序的运行提供良好的运行坏境,以保证多道程序能有条
不紊地、高效地运行,并能最大程度地提高系统中各种资源的利用率和方便用
户的使用。
2 系统功能简介
LRU 算法是根据页面调入调入内存后的使用情况进行决策的,其中选择
最近最久未使用的页面予以淘汰。具体过程是赋予每个页面一个访问字段,用
来记录一个页面自上次被访问以来所经历的时间 T,当须淘汰一个页面时,选
择现有页面中 T 值最大的,即最近最久未使用的页面予以淘汰。
3 设计主要内容
3.1 设计分析
3.1.1 需求分析
根据设计得出最近最久未使用算法赋予每个页面一个访问字段,用来记
录一个页面自上次被访问以来所经历的时间 T,在设计程序的时候可以根据该
时间 T 的大小来判断哪个页面是最近最久未使用的(即该置换的页面),并且
如何将此页面进行置换完成最近最久未使用置换算法的全过程。
3.1.2 总体设计
共 8 页 第 2 页
┊
┊
┊
┊
┊
┊
┊
┊
┊
┊
┊
┊
┊
装
┊
┊
┊
┊
┊
订
┊
┊
┊
┊
┊
线
┊
┊
┊
┊
┊
┊
┊
┊
┊
┊
┊
┊
┊
长 春 大 学 课程设计纸
功能结构图:
图 2-1. 功能概图
设计思想:
本程序以 Lru()为核心函数,通过该函数调用其它函数来实现页面置换
算 法 , 并 判 断 物 理 块 是 否 已 满 和 物 理 块 中 是 否 存 在 相 同 的 页 面 , 用
GetMax()判断需要置换的页面,在主程序中先调用 Lru()函数,然后将需
要输出的数据进行算法置换,最后通过格式化的输出方法在控制台中输出!
3.2 详细设计
本程序定义了 m 为物理块数,n 为要访问的页面数。通过主函数判断 n 的
数值是否大于 10,若大于 10 直接退出程序,否则通过调用 LRU()函数判断
页面状态,如果存在相同的页面,当前的页面 time 值置 0,如果不存在相同页
面,就判断当前的页面状态,此时,物理块未满直接进行页面调入,物理块已
满,则找出 time 值最大的页面再进行调入,重新判断 n 的值。
运行流程图 2-2 所示:
共 8 页 第 3 页
┊
┊
┊
┊
┊
┊
┊
┊
┊
┊
┊
┊
┊
装
┊
┊
┊
┊
┊
订
┊
┊
┊
┊
┊
线
┊
┊
┊
┊
┊
┊
┊
┊
┊
┊
┊
┊
┊
初始化内存
判断置换页
面
页 面 调 入
调出
显示
总程序