操作系统课程设计页面置换算法(LRU算法).doc

实验报告
题目

名称页面置换算法(LRＵ算法)
院系

信息学院

班级

110６4０2

完成时间

2013-0５—17
指导老师

肖赛男本次实验成绩组长

联系电话李国红

1827３7１６615
邮件地址[e-mail]组员（姓名，

学号)吕赟

110６４0２—３8
主要任务算法的组织，综合调度,程序运行界面的
实现
组员(姓名,

学号)蔡祥

110６４０2—09
主要任务
算法的实现，测试，实验报告的完成主
要
原
理
及
所
参
考
的
资
料
(
包
括
实
验
内
容
及
条
件
）实验原理：

页面置换算法(LRＵ算法）

假定一个能够存放M个页面的内存,当发生缺页时，调入一个页面，通过LRU算法求出应该置换出的页面号。输入一连串的页面号,程序自动选择调出的页面并计算缺页率。

设计页面置换算法,这里采用最近最久未使用置换算法LRU．LＲU算法的实现要归功于一个8位的寄存器的实现。

主要参考书

计算机操作系统原理西安大学出版社汤子瀛主编
操作系统电子工业出版社ＷiｌliamStａlliｎgs著

主
要
算
法
流
程
图
(
包
括
实
验
步
骤
）算法流程图:
输入页面访问序号
取访问页的页号
查夜表
是否缺页
否
置换出寄存器数组页
面标号最小的页面
是
按算法不同淘汰一页面
调入所访问的页面

实验说明:

执行程序时,当主存没有可用页面时,为了选择淘汰主存中的哪一页面,腾出１个空闲块以便存放新调入的页面。淘汰哪个页面的首要问题是选择何种置换算法。该程序采用LＲＵ方法选择,依置换策略选择一个可置换的页面并计算它们的缺页率以便比较。
本
实
验
涉
及
的
主
要
算
法
细
节
说
明
(
包
括
数
据
结
构
)＃include<mａth.h〉
#incｌude〈ｃonio。h〉
#defineM３
＃inｃluｄe〈stdｉｏ。h〉
intｒｅg[2]［M］;
ｉntcount;
intnum;
ｉntＮ；
/*****＊*＊初始化函数，数组reｇ[0]［i]存放页面号,初始化为－1，reg[1］［i]当作寄存器,初始化为0***＊＊＊*＊*/
voiｄinit（）{
intｉ；
ｃoｕｎt=０;ｎｕｍ=0;
N＝pow(2，7）；／********二进制数１0000０0０*＊********／
ﻩfｏr(i=0；i＜M;ｉ++)｛
ﻩreg［０][ｉ］=-1;
ﻩｒeg[1]［i]=0;
ﻩ }
ﻩ}
／***＊＊*＊＊＊寻找数组ａ中的最小值,返回最小值对应的下标＊＊＊*＊**＊**＊/
iｎtｍｉn（inta[]）｛
iｎtｉ，ｉndex＝0;
iｎtmiｎ=a［０］;
fｏｒ(i=1;i<M；i++)｛
ﻩ if(ｍin〉ａ[i]){
ﻩ min=ａ［i]；
index=ｉ；
ﻩ ﻩ｝
ﻩﻩ｝
ﻩreｔurｎｉnｄex;
ﻩ}
／**＊判断页面号x是否在数组中，如果在，返回对应的下标;否则返回－１*＊*/
intiｓIn（intx，iｎta[]){
intｉ;
intindex＝—1；
foｒ(i＝0;i〈M;ｉ++){
ﻩﻩｉf（a［ｉ]＝＝x)｛
ﻩ ﻩｉndex=i;
ﻩﻩﻩｂreak；
ﻩﻩ｝
ﻩ}
ﻩreturnｉndeｘ;
｝
/＊*＊*****＊*判断虚拟的内存中是否已经存满了页面，如果满了,则返回－1，没有满则返回找到空的对应的第一个下标**＊*＊**＊＊*＊**＊/
intｉｓFulｌ(inｔa[]){
inｔi，indeｘ=—1;
ﻩfor(i=0;i〈M;i++){
ﻩｉf（a[i]＝=－1){
ﻩ ﻩindex＝i；
ﻩ ｂreak；
}
｝
retｕrnｉndex；
ﻩ}
/＊***＊*＊***＊**页面置换方法*＊＊*＊****＊**＊***＊/
voidswａｐ(inｔｘ){
intｉ，ｋ，ｔemp,temp０;
ﻩintiｎdex=isＩn（x,reg［0］)；/****判断x是否在reg[0]数组中＊＊**＊＊*/
ﻩif（iｎdex!=—1){
ﻩ ｒeg［1]［ｉndｅx］=rｅg[１］［index]^N;/**reg［１］［index］异或二进制数1000000０*＊/
ﻩ｝
ｅlsｅ{
ﻩﻩtemp=iｓＦull(reｇ［0]）;
ﻩﻩiｆ(tｅmp！=－1)｛/***＊***内存没有满,直接调入页面＊＊***＊***＊＊*／
ﻩﻩｒeg［0］［temp］＝x;
ﻩ rｅｇ［1][temp]＝rｅg［1]［teｍｐ]^N；
ﻩ ｝
elseiｆ（temp==—1){
k=mｉn(rｅg［1]);/**置换出寄存器中