操作系统课程设计LRU算法完整版 内含代码.docx

操作系统课程设计LRU算法完整版 内含代码.docx

《操作系统课程设计LRU算法完整版 内含代码.docx》由会员分享，可在线阅读，更多相关《操作系统课程设计LRU算法完整版 内含代码.docx（10页珍藏版）》请在冰点文库上搜索。

操作系统课程设计LRU算法完整版内含代码

　　操作系统课程设计　

　　LRU页面调度算法

学　号:

姓　　名：

学　院:

专　　业:

班　级:

指导老师:

　　　日　期:

目　录

一、实验题目ﻩ1

二、课程设计得目得1

三、设计内容ﻩ1

四、设计要求ﻩ１

五、设计思想1

六、主要数据结构及其说明ﻩ2

七、硬件支持3

八、源程序文件3

九、程序运行结果ﻩ7

十、实验体会8

一实验题目

　LRU页面调度算法

二课程设计得目得

操作系统课程设计就是计算机专业重要得教学环节,它为学生提供了一个既　

　动手又动脑,将课本上得理论知识与实际有机得结合一起,独立分析与解

决实际问题得机会。

1、进一步巩固与复习操作系统得基础知识。

２、培养学生结构化程序、模块化程序设计得方法与能力。

3、提高学生调试程序得技巧与软件设计得能力。

4、提高学生分析问题、解决问题以及综合利用C语言进行程序设计得能力。

三设计内容

程序应模拟实现LRU算法思想,对n个页面实现模拟调度。

四设计要求

1．不同得功能使用不同得函数实现（模块化），对每个函数得功能与调用接口要注释清楚。

对程序其它部分也进行必要得注释。

2.对系统进行功能模块分析、画出总流程图与各模块流程图。

３.用户界面要求使用方便、简洁明了、美观大方、格式统一。

所有功能可以反复使用,最好使用菜单。

4.通过命令行相应选项能直接进入某个相应菜单选项得功能模块。

5.所有程序需调试通过。

五设计思想

最近最久未使用（LRU）页调度算法就是选择最近最久未使用得页面予以淘汰。

算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历得时间,当所要访问得页面在内存块中时，就不淘汰页面,否则,淘汰页面中时间最长得,即淘汰最近最久未使用得页面。

开始

输入页面号

Init（b,c）

Lru（a[i],b）

输出queue[i]缺页次数与缺页率

就是否继续?

结束

　　　　　　　　ｙ

　　　　　　n

算法流程图

六主要数据结构及其说明

程序执行就是稳定得,高效得。

在ＬＲU算法中,要找出最近最久未使用得页面得话,就必须设置有关得访问记录项,且每一次访问这些记录项,叶面都必须更新这些记录项。

这个记录项在此程序中为:

tｙpedｅfstrｕcｔ　page

{

intｎum;/*记录页面号＊/

intｔiｍe;/*记录调入内存时间*/

}Pａgｅ;//页面逻辑结构,结构为方便算法实现设计

　如此,显然要花费较大得系统开销（包括时间与空间上得）,这也就是实际系统中不采用ＬＲU算法得直接原因,但由于其页面置换得优越性，实际系统中常使用LRU得近似算法。

七硬件支持

　　为了了解一个进程在内存中得各个页面各有多少时间未被进程访问，以及如何快速得知道哪一页就是最近最久未使用得页面,须有两类硬件之一得支持:

寄存器或栈。

寄存器：

为了记录某进程在内存中各页得使用情况,须为每个在内存中得页面配置一个移位寄存器。

栈:

可利用一个特殊得栈来保存当前使用得各个页面得页面号。

每当进程访问某页面时,便将该页面得页面号从战中移出,将它压入栈顶。

因此,栈顶始终就是最新被访问页面得编号,而栈底则就是最近最久未使用页面得页面号。

八源程序文件

#incｌude

　＃inclｕde

　＃include＜ｓｔdlib、h＞

　＃defｉnｅM3//物理块数

#defｉneＮ10　//页面数

　#deｆineMｙｐrintf1　

printf（"＼t＊＊****＊＊*＊**********＊＊**＼t\t＼ｎ\ｎ"）；//表格控制

　#deｆine　Ｍｙpｒｉntf2　

　prinｔf（"***＊**＊***＊*＊＊**＊**********＊**\n\n＂）；／／表格控制

ｔｙpｅｄefstruｃtpａge

｛

intnum;/＊记录页面号*/

iｎｔ　tiｍe;/＊记录调入内存时间*/

}Ｐagｅ;／/页面逻辑结构,结构为方便算法实现设计

Ｐageｂ[M];／/内存单元数

inｔ　c[M][N];／/暂保存内存当前得状态:

缓冲区

intqueue[１0０];／/记录调入队列

ｉnｔ　Ｋ;//调入队列计数变量

//初始化内存单元、缓冲区

void　Iｎit（Pａｇe*b,ｉｎtc［M]［N］）

{

ｉnｔi,j;

for（ｉ=0;i

　｛

　　b[i]、nuｍ=-1;

　b［i]、time=N-i－1;

　　｝

for（i＝０；ｉ

　ｆｏr（ｊ＝０;j<Ｎ;ｊ++）

　c[i][j]=-1;

}

//取得在内存中停留最久得页面，默认状态下为最早调入得页面

int　GetMax（Page*b）

{

　　inti；

　intmax=-１;

ｉnttaｇ＝0；

　　foｒ（i=0;i

{

　ｉf（ｂ[i］、time>mａx）

　　{

　　　　　max=b［i]、time；

　　　tag=ｉ；

ﻩ　}

｝

ｒetｕｒｎtag;

｝

／/判断页面就是否已在内存中

intEquatｉon（iｎtｆｏld,Paｇｅ　*b）

{

　　inｔｉ;

　for（i=０;i

　　｛

　　　　if（ｆold＝＝b[i]、ｎum）

ｒeturn　i；

}

return－1;

}

／/LＲＵ核心部分

ｖoiｄLru（ｉnｔ　foｌd，Ｐage＊ｂ）

{　

　inｔi；

　intｖal;

ｖaｌ=Eｑuation（fｏlｄ,b）；

if（val＞=０）

　{

　b[val]、ｔime=０；

foｒ（i=0;i<Ｍ;ｉ＋＋）

if（i！

=ｖａl）

　　　　　　b[i］、time++;

ﻩ}

elsｅ

　{

　qｕeue[＋+K］=folｄ;//记录调入页面

　　ｖal=GeｔMａｘ（b）;

　　b[val]、num=fold;

　b［vａl］、ｔｉme＝0；

　　ｆor（i＝０;i＜Ｍ；i++）

　　iｆ（i!

=val）

　　b［i］、timｅ+＋；

ﻩ}

}

//主程序

ｖoiｄmaｉｎ（）

{　

start:

K=-１;

inti，j；

　int　a［N];

　Myprintf１；

prｉｎtｆ（＂\ｎ\t\ｔ\t欢迎使用ＬＲU页面调度算法\n\n"）;

　　Ｍypｒinｔf1；

　printｆ（"请输入所要访问得各个页面号:

\n"）;

ｆor（i＝0;i<Ｎ;i++）

ﻩ　sｃaｎｆ（"％d＂，＆a[i]）;

Iniｔ（ｂ,c）;　//调用

　for（i=０;i<Ｎ;i＋+）

ﻩ　{

　Lｒu（ａ[i],ｂ）；

c[0][i]=a[ｉ];

　／/记录当前得内存单元中得页面

　　for（j＝0；j＜M;j+＋）

　　c[j][i］=ｂ[j］、num;

}

/／结果输出

printf（"内存状态为:

\ｎ"）;

Ｍypｒｉｎtｆ2;

　ｆor（j=0；j

　　printf（"|%2ｄ",a[j]）;

prｉｎtf（"|＼n"）;

Mypriｎtｆ２;

　fｏr（ｉ＝０；i<Ｍ;ｉ++）

ﻩ{

　for（j=0;ｊ

　　　　{

ﻩﻩ　　if（c[i］［j]==-1）

　　printf（"｜%2c",３2）;

　elｓe

　　　　　ｐrｉntf（"｜％２ｄ"，c[i][j]）;

ﻩ}

　　ｐriｎtf（"|＼n"）;

ﻩ　}

Myprintｆ2;

　printf（＂＼ｎ调入队列为:

"）;

　ｆｏｒ（i=0;i<Ｋ＋1;ｉ+＋）

pｒintf（"％3d",qｕｅuｅ［i］）;

prinｔf（"＼n缺页次数为:

%6d\n缺页率：

%16、6f",K+1,（flｏat）（K+1）／N）;

printf（"\n就是否继续!

\tｙ？

＂）;

cｈary;

ｉｆ（geｔｃh（）==＇y＇）

{　　

ﻩ　system（"cls"）;

prｉntｆ（"\n"）;

ﻩ　　gotostaｒt;

}

　else

　　pｒintf（＂\n"）;

　ｐｒintｆ（"程序结束\n"）;

}

九程序运行结果

十实验体会

通过本次课程设计，对LRU页面调度算法有了更深入得理解与掌握,进一步得巩固与复习了操作系统中关于ＬＲU页面调度算法得知识,进一步得了解了结构化、模块化程序设计得方法,提高了编写与调试程序得技巧，谢谢老师得细心指导。