操作系统实验4-请求分页存储管理模拟实验.doc

实验四
请求分页存储管理模拟实验
一：实验目得
通过对页面、页表、地址转换与页面置换过程得模拟,加深对请求分页存储管理系统得原理与实现技术得理解.
二：实验内容
假设每个页面可以存放１0条指令，分配给进程得存储块数为４。
用C语言或Ｐａscａｌ语言模拟一进程得执行过程。设该进程共有320条指令，地址空间为32个页面,运行前所有页面均没有调入内存。模拟运行时,如果所访问得指令已经在内存,则显示其物理地址,并转下一条指令;如果所访问得指令还未装入内存，则发生缺页，此时需要记录缺页产生次数，并将相应页面调入内存，如果４个内存块已满，则需要进行页面置换。最后显示其物理地址,并转下一条指令。在所有指令执行完毕后,显示进程运行过程中得缺页次数与缺页率.
页面置换算法：分别采用OPT、ＦIFＯ、LRＵ三种算法。
进程中得指令访问次序按如下原则生成：
50%得指令就是顺序执行得。
2５%得指令就是均匀分布在低地址部分.
25％得指令就是均匀分布在高地址部分.
三：实验类别
分页存储管理
四:实验类型
模拟实验
五：主要仪器
计算机
六：结果

OＰＴ:

ＬRU：

FIFO：

七：程序
＃ iｎclude〈stdio、h〉
＃　ｉnclｕde〈ｓtdlib、h〉
＃　include〈ｃｏnio、ｈ＞
＃ defｉne blocknｕm ４//页面尺寸大小
int ｍ; //程序计数器，用来记录按次序执行得指令对应得页号
sｔaｔiｃ inｔ　ｎum［３20]； //用来存储3２0条指令
ｔｙpedef sｔruct BLOCK ／/声明一种新类型—－物理块类型
{
ﻩint ｐagenum; ／/页号
ﻩint ａｃcesｓｅd;　／/访问量，其值表示多久未被访问
}BLOCK；
BLOCK blｏck［blｏcknum］； ／/定义一大小为8得物理块数组
void init（） /／程序初始化函数，对blｏck初始化
｛
for（ｉnt i=0;i＜ｂloｃknum;i+＋)　
ﻩ{　
bｌｏｃｋ[ｉ]、ｐａgｅnum＝—1；
bｌock［ｉ］、accｅsｓed=0；
ﻩm=0;
｝
｝
ｉｎt ｐａｇｅＥxist（ｉnt　curpagｅ)/／查找物理块中页面就是否存在，寻找该页面curpage就是否在内存块bｌoｃｋ中,若在，返回块号
｛
ﻩfor（int i=0；　i<bｌocknum; i+＋)
ﻩ{
ﻩﻩｉf(bｌock［i］、ｐagｅnｕm　＝＝ cuｒpaｇe　）
ﻩﻩｒeturn i； //在内存块blｏck中,返回块号
ﻩ｝
ｒetuｒn -1;
}
ｉnｔ findSpace（）／/查找就是否有空闲物理块，寻找空闲块bｌock，返回其块号
｛
foｒ(int　ｉ=0；ｉ<bｌocknｕm;i＋+)
ﻩ｛
ｉf（blｏｃｋ[i］、paｇenum=＝－1)
ﻩｒeｔuｒn　i； ／／找到了空闲得ｂlｏcｋ,返回块号
｝　
ﻩrｅｔurｎ -1；
｝
int findReplａcｅ(）//查找应予置换得页面
{
ﻩint ｐoｓ = 0;
ﻩｆor（int i＝0；i〈ｂlocｋnｕm；ｉ++)
{　
if(blｏｃk［ｉ]、ａｃcessed 〉　blｏck［pos]、aｃceｓsｅd）
ﻩpos　= ｉ； //找到应该置换页面，返回BＬOCK中位置　
ﻩ｝
reｔurn pｏs；
｝
voｉd displaｙ(）//显示物理块中得页面号
｛ ﻩ
ﻩfor(int i=0;　i〈bｌocknｕm; i＋＋）
ﻩ｛
ﻩ if(blocｋ[ｉ］、ｐａｇenum !=　-1）
ﻩ｛
ﻩﻩ priｎtf（” ％02d　 "，block［ｉ]、paｇenum）;
ﻩﻩﻩprintf("%p 　|”，＆blocｋ[ｉ]、pagｅnum）；
ﻩﻩ｝
｝
ｐrｉｎtf（"\n＂）;
｝
vｏid　rａｎdaｍ（)/／产生320条随机数,显示并存储到ｎｕm[３２0]
｛
int ｆlａｇ=0;
pｒintｆ（”请为一进程输入起始执行指令得序号(0~320）:\n”)；
ﻩscanｆ（"%d",＆ｍ）；//用户决定得起始执行指令
ｐriｎｔｆ（"*＊＊**＊进程中指令访问次序如下：(由随机数产生)＊*＊*＊＊＊＼n"）;
fｏr（int　i=0；i〈３2０；ｉ＋+）
｛/／进程中得320条指令访问次序得生成
ﻩﻩnum[ｉ]＝m;//当前执行得指令数，
ﻩﻩｉf（flag％２==0）
ﻩ m＝++m％３２０；//顺序执行下一条指令
ﻩﻩｉf（flag==１）
ﻩﻩm＝rａnd（）％（m-1)；//通过随机数,跳转到低地址部分[0，m—1］得一条指令处，设其序号为ｍ1
ｉf(flag＝=3）
ﻩﻩm=m+1＋(rand()%(３2０－（m+1）)）；//通过随机数,跳转到高地址部分［ｍ1+2，3１９]得一条指令处，设其序号为m2
ﻩﻩfｌag＝＋+ｆｌag%４；
ﻩ prｉntｆ（” %0３d”,num［i］)；／/输出格式:3位数
ﻩﻩiｆ（（i+１）%1０==0） ／/控制换行，每个页面可以存放１０条指令,共32个页面
ﻩprintf（”\n”）；
｝　
｝
ｖoid pageｓtrｉng（) //显示调用得页面序列,求出此进程按次序执行得各指令所在得页面号并显示输出
｛
ｆor（int　i＝0;i〈３２0；i++）
ﻩ｛
printf(” ％０２d＂,nuｍ[i］／１0);//输出格式：２位数
if((ｉ＋1）%10==0)//控制换行，每个页面可以存放10条指令,共32个页面
ﻩﻩ ｐｒintf("＼n”);
}
｝
void　OPＴ() //最佳替换算法
{　
ﻩinｔ n=0；//记录缺页次数
inｔ exist，space，posiｔｉon；
ﻩinｔ ｃurpaｇe;//当前指令得页面号
ﻩfｏr(int i＝０;i＜３2０；ｉ＋＋）
ﻩ｛　
ﻩm=num［i］;
ﻩcurpage=ｍ/10;
ﻩﻩeｘiｓt=ｐageExist（cuｒｐage);
ﻩ if(exist==-1)
ﻩﻩ{ ／/当前指令得页面号不在物理块中
space＝findＳpace（）；
ﻩﻩif(sｐａｃe ！= -１）
ﻩﻩ ｛　//当前存在空闲得物理块
ﻩﻩ ｂloｃk［ｓｐａce]、pagenuｍ　＝ cｕｒpaｇe；　/／将此页面调入内存
ﻩﻩ ﻩdiｓｐlay（）;／/显示物理块中得页面号
ﻩ ﻩn++;/／缺页次数+1
ﻩ｝
ﻩ ﻩelｓe
ﻩ ﻩ{ ／/当前不存在空闲得物理块，需要进行页面置换
foｒ（inｔ　k=0；k＜blocknum；k++）
ﻩﻩﻩﻩ{
ｆor（int　j=i；ｊ〈３２０；j＋+）
ﻩ {//找到在最长(未来)时间内不再被访问得页面
ﻩﻩﻩﻩ if(block［k］、pagenum！= ｎｕｍ［j]/1０）
ﻩﻩﻩ {
ﻩ ﻩ bloｃk［ｋ］、acｃeｓseｄ =　1０00;
ﻩ ﻩﻩ } //将来不会被访问,设置为一个很大数
ﻩ ﻩﻩ else
ﻩ ﻩﻩ{ //将来会被访问,访问量设为ｊ
ﻩﻩ ﻩｂlｏcｋ[ｋ］、ａｃｃessｅd = j；
ﻩ ﻩﻩ ﻩﻩbｒeak;
ﻩ ﻩﻩﻩ ｝
ﻩ ﻩﻩ}
ﻩ }
ﻩ posiｔｉon = ｆiｎdReｐlａｃe（）；//找到被置换得页面 ，淘汰
ﻩ block［ｐosｉtｉon］、pａgenum = ｃurpａｇｅ；// 将新页面调入
dispｌay();
ﻩﻩ n++； //缺页次数+１
ﻩ｝
｝
ﻩ｝
ﻩpｒintf(”缺页次数：％ｄ\n＂,n);
printｆ(＂缺页率：％f％％＼n"，（n／320、0）＊100）；
}
void LＲU() //最近最久未使用算法
{
inｔ n=0；//记录缺页次数
ﻩiｎt ｅxｉｓt,ｓｐacｅ，ｐosition ;
ﻩｉnｔ curpaｇe；／/当前指令得页面号
ﻩｆｏｒ（ｉｎt i=0；i＜320;i++）
ﻩ{　
ﻩm＝num［i]；
ﻩﻩcuｒｐagｅ=m／10；
ﻩ ｅxist = pageＥｘiｓt(curpａge);
ﻩｉｆ（ｅxist＝=-1）
ﻩﻩ｛ //当前指令得页面号不在物理块中
ｓｐaｃe = fｉnｄSpace（）;
ﻩﻩ if（sｐａcｅ ！= —１)
ﻩ{ //当前存在空闲得物理块
ﻩ ﻩｂｌock［spａce]、pagenum =　ｃｕrｐage；　//将此页面调入内存
ﻩ ﻩ ｄisplay（）；//显示物理块中得页面号
ﻩ n++;／／缺页次数+1
ﻩﻩ ｝
else
｛ //当前不存在空闲得物理块，需要进行页面置换
ﻩﻩ pｏsｉｔioｎ ＝ finｄＲeｐlace(）；　
ﻩ bｌocｋ[positｉon]、paｇenum　＝ cｕrｐａge；　
ﻩﻩ diｓplaｙ(）;
ﻩ n++；　//缺页次数+1
ﻩ｝
ﻩﻩ}
elsｅ
ﻩﻩbｌｏck［exｉsｔ］、acｃesｓed = -１；//恢复存在得并刚访问过得ＢLOCK中页面ａccessｅｄ为-１
for(int j=0; j<blockｎum； j＋+)
ﻩﻩ｛//其余得accessed++
ﻩﻩｂlｏｃk［ｊ］、acｃｅssed+＋;
｝
ﻩ}
prｉntf("缺页次数:%d\n”,n）；
ﻩpriｎｔf("缺页率：％f%％\n",（n／３20、0）*10０);
｝
voｉd FIFO（）
{
int　n=0;//记录缺页次数
int　eｘist，spacｅ，ｐositｉｏn ;
ﻩ iｎｔ cｕrｐaｇe；/／当前指令得页面号
　iｎt　blｏckpｏinter=－１;
　for（iｎｔ i=０;i<３20；ｉ++）
ﻩ　｛　
ﻩ m=num［i］;
　cｕrpａge=m／１0；
ﻩ　exｉst　= pageＥｘist(ｃｕrpａge）；　
ﻩ iｆ(eｘiｓｔ＝=－１）
　｛ ／/当前指令得页面号不在物理块中
ﻩ spaｃe = fｉｎdＳpaｃe（);
ﻩﻩ 　if（space　！＝　-1)
ﻩ { ／/当前存在空闲得物理块
ﻩﻩ blocｋpoiｎter＋+;
ﻩﻩ ﻩ ｂlock［spａcｅ]、ｐａｇｅnｕm=curpagｅ; /／将此页面调入内存
ﻩ n++;//缺页次数＋1
ﻩﻩ ﻩ diｓｐlay(）;//显示物理块中得页面号
ﻩ ｝
ﻩ else
ﻩ { /／ 没有空闲物理块,进行置换
ﻩﻩﻩﻩ　pｏsitｉon = （++blockpｏintｅr）％4;
ﻩ block[positｉon]、ｐaｇｅnum ＝ cuｒｐａge； ／/将此页面调入内存
ﻩﻩ　n＋+；
ﻩ ﻩ disｐｌay（）；
ﻩ ｝
ﻩ }
｝
ｐrｉｎtf(＂缺页次数:％d＼n＂,n）;
printf（＂缺页率:%ｆ%%\n",(n/3２0、0)*100）；
}
void ｍain(）
{
ﻩint choice;
ﻩpriｎtf（"＊＊＊＊*＊＊*＊*＊＊请求分页存储管理模拟系统*＊＊*＊＊＊＊＊＊*＊*\n")；
ﻩrandａm（);
ｐｒintf(＂＊＊*＊*＊＊*****此进程得页面调用序列如下***＊＊＊＊*＊＊＊**＊\n”）;
pageｓtriｎｇ（）;
ﻩwｈilｅ（choicｅ　！=　４)
｛　
ﻩﻩprinｔf(＂****＊*＊＊1:OPT ２：LRU 3:ＦＩFO 4：退出＊＊*＊＊＊***\n”）;
ﻩprintf（"请选择一种页面置换算法:”）;
ﻩ ｓｃａnf("%d＂,＆cｈoｉcｅ）；
ﻩ iｎit();
ﻩswitch（choiｃe)
ﻩ ｛
ﻩ cａｓe 1:
ﻩﻩﻩｐｒintf(”最佳置换算法OPT：\n")；
ﻩpｒintf("页面号 物理地址 页面号 物理地址　 　页面号 物理地址 页面号 物理地址＼n"）;
ﻩﻩﻩOPＴ（）；
ﻩ break；
ﻩ cａse 2：
ﻩﻩ ｐrinｔf("最近最久未使用置换算法LRＵ:\n"）；
ﻩ ｐrｉntf("页面号 物理地址　　页面号 物理地址 页面号 物理地址 页面号 物理地址＼n＂）;
ﻩ ＬRU()；
ﻩﻩﻩｂreaｋ；
ﻩﻩcaｓe 3：
ﻩ printf("先进先出置换算法FＩＦＯ：\n＂）；
ﻩpｒiｎｔf（＂页面号　　物理地址 页面号 　物理地址 页面号 物理地址　 页面号 　物理地址\ｎ＂);
ＦIFO(）；
ﻩﻩbreａk;
ﻩ ｝
}
}