《操作系统》实验五：页面置换算法模拟.doc

　 　 　 　　 实验五、 请求页式存储管理得模拟
［实验内容]:
熟悉虚拟存储管理得各种页面置换算法，并编写模拟程序实现请求页式存储管理得页面置换算法－——－最近最久未使用算法（ＬRU）,要求在每次产生置换时显示页面分配状态与缺页率。
［实验要求］:
1、运行给出得实验程序，查瞧执行情况，进而分析算法得执行过程,在理解FＩFO页面置换算法与最近最久未使用算法(LRＵ）置换算法后,给出最佳置换算法得模拟程序实现，并集成到参考程序中。
2、执行2个页面置换模拟程序,分析缺页率得情况。最好页框数与访问序列长度可调节,在使用同一组访问序列数据得情况下，改变页框数并执行2个页面置换模拟程序，查瞧缺页率得变化。
３、在每次产生置换时要求显示分配状态与缺页率.程序得地址访问序列通过随机数产生，要求具有足够得长度。最好页框数与访问序列长度可调节。
实验得执行结果如下图所示（左下图为FIFO执行结果，右下图为LRU执行结果）：

程序源代码：
#inclｕde　
＃inclｕdｅ ＂wｉndows、h”
#inclｕde
＃inclｕde ＜stdlｉb、ｈ〉
#include 〈fstream、h>
#include　＜ｉo、h〉
＃inｃlude
#iｎcludｅ
ｖoid inｉtiａｌｉｚe（）; 　 //初始化相关数据结构
voｉd creａteps（)；　　 　 /／随机生成访问序列
void dｉspｌａyｉnｆｏ()；　　 /／显示当前状态及缺页情况
ｖｏid fiｆo(）; 　　 　　 //先进先出算法
int　 fｉndpage(）； 　 //查找页面就是否在内存
voｉｄ　lru（）; 　 　 //最近最久未使用算法
ｉnt　 　invaｌidcoｕｎt ＝ ０； 　// 缺页次数
int　　 vpoinｔ; 　 　 　 //页面访问指针
int　 paｇefrａｍe［1０］；　　 // 分配得页框
ｉnt paｇehｉｓtoｒy[１0];　 //记录页框中数据得访问历史
int 　ｒｐoint; 　 　　 //页面替换指针
ｉｎt iｎｐｆlaｇ; 　 ／／缺页标志，0为不缺页，１为缺页
struct PagｅInfo 　　 //页面信息结构
{
　　 inｔ 　serial[1０0］;　 // 模拟得最大访问页面数，实际控制在20以上
　　int ｆｌag；　 　 // 标志位,0表示无页面访问数据
　　int 　disｅｆfeｃt； // 缺页次数
　 　iｎt ｔotal_ｐf; 　　 /／ 分配得页框数
　int ｔoｔaｌ＿pn;　 　 ／/ 访问页面序列长度
｝ ｐf_iｎfo；
/／//／／///／///////////／///////／////／/／／／/////／///／///////／／///／/////／///／
／/初始化相关数据结构
ｖoｉｄ inｉtialize(） 　 　 　
｛
ﻩinｔ　i，ｐf;
ﻩinpfｌag=0；　 　 　 　 　 　　／/缺页标志,0为不缺页，1为缺页
ﻩｐf_infｏ、diseffｅct =0; // 缺页次数
pf＿info、ｆlag　＝0；　 　／/ 标志位，0表示无页面访问数据
ﻩprintf("\ｎ请输入要分配得页框数:"）； // 自定义分配得页框数　
　scanf（"％ｄ"，＆pf）；
ﻩpｆ＿info、totaｌ＿pf =pｆ; 　
ｆｏｒ（i=０；i<１00;i++) 　 // 清空页面序列
ﻩ｛
　 　 pf_ｉnfｏ、seriａl［i]＝－１；
}
}
/////／//／////／/／//////／／///////／/／/／/////／///／//／////////／///////／/
//　随机生成访问序列
ｖoid　ｃｒｅａｔeps(ｖｏid　)
｛
iｎｔ　ｓ，i,ｐn；
　initiaｌize（）； 　／/初始化相关数据结构
prｉntf（”\ｎ请输入要随机生成访问序列得长度：”); ／/自定义随机生成访问序列得长度
sｃaｎf（＂％d＂，＆pn)；
sｒaｎd（ｒａnｄ（)）;　　 //初始化随机数队列得”种子”
s=(（float)　ｒand（)　/ ３2767） * 50 ＋ ｐn； ／／ 随机产生页面序列长度
ﻩｐf_inｆo、tｏtａl＿ｐｎ　= s；
ﻩｆor（ｉ=0；ｉ〈ｓ;i++） 　//产生随机访问序列
｛
ﻩｐf_ｉnfo、seriａl[i］=((fｌoaｔ) raｎd（） / ３2767） *　16 ;　　 //随机数得大小在0—１5之间 　　
｝
}
/////////／///／///／／／//／////////／//////／//／////////／/／／/////／/／/／///／////
/／ 显示当前状态及缺页情况
ｖoｉd displayｉnfo（ｖoｉｄ）
{
　　ｉｎt i，n；
　 if（vｐoint=＝0）
　{
ﻩ　 　prｉｎtf（＂\ｎ======＝＝=＝＝==页面访问序列=＝=＝======＝＝=\n”）；
　 　　 for(i=0； ｉ ｆor（n=0；n＜ｐf_ｉnfｏ、ｔｏtal_pf；n++) /／ 页框信息
{
　 if (pagefｒａme[ｎ］ 〉=0）
ﻩ 　prｉntｆ（”％3ｄ”,pageｆrame［n])；
eｌse
　　 pｒintf(”　 ”)；
}
　 printf(" >")；
if（inpfｌag==1) 　 //缺页标志,0为不缺页，1为缺页
　｛
ｐriｎtf（" =＝〉缺页 "）；　
　prｉntf（”缺页率％3.1ｆ＂，(ｆloat）（ｐf＿ｉｎfo、diｓｅffｅｃt）*1０0、00/vpoiｎt）;
　 ｝
　　printf(＂\n");
｝
/／／/////////////／/／////////／／//////／////／／///／//////／／/／//////／／////／//／
/／ 查找页面就是否在内存，1为在内存,0为不在即缺页
int　fｉndｐａge（ｉｎｔ pａge）
｛　
ﻩiｎt　n；
　for(ｎ＝0；ｎ〈pｆ_inｆo、ｔotａl_pｆ;n＋+)　
ﻩ{
pagehisｔoｒy[n] ＋+； // 访问历史加1
}
ﻩfor（n=0;n if　(pａｇefｒａme[n]=＝pａge　)
　　{
ﻩﻩ 　inｐｆlａg=0　；　　 //ｉnｐflag缺页标志,0为不缺页，1为缺页 　
　　pａgeｈｉstory[ｎ]=0；　 　//置访问历史为0
　rｅｔuｒn 1;
ﻩ ｝
}
ｉnpｆlaｇ=1； ﻩ/／页面不存在,缺页
　 returｎ　0;ﻩ 　
}
／/////／////／//／////／//////／/／//////／///////／////////////／///／////／////／／
// FIFO页面置换算法
ｖoid ｆｉfｏ(void)
｛
ｉｎt　n，count,psｔaｔe；
rpｏiｎｔ=0； 　　 　 // 页面替换指针初始化为０
invaｌｉdｃounｔ =　0； /／ 缺页数初始化为０
　　ｃｒｅateps（）； 　 　　 // 随机生成访问序列
coｕnt=0；　 　　　 　　 　 // 就是否装满就是所有得页框
　 fｏr（ｎ=０;n〈ｐf_info、ｔotａl_pf；n＋+) ／/ 清除页框信息
｛
　 pａｇeframe［n］=-1；
　 ｝
inｐflａg＝0； 　　//缺页标志，0为不缺页，1为缺页
　for（vpｏｉｎt=0;ｖpoｉnt＜ｐｆ_ｉnfo、total＿pn；vｐoint++） ／／ 执行算法
{ 　
ﻩ pｓｔate=ｆindｐage（ｐf_ｉnｆo、seｒｉａl［vpoｉｎｔ]）； //查找页面就是否在内存
ﻩ iｆ(ｃoｕnt＜ｐf＿info、totａｌ＿pf）　 　／/ 开始时不计算缺页
{
ﻩ if(ｐstａte==0） // 页不存在则装入页面
｛
ﻩ ｐagefrａme［rpoinｔ］=pf＿infｏ、ｓerｉａl［vpoinｔ］;ﻩ
ﻩﻩrｐoint=(rpoint+1) % pf＿infｏ、total_ｐf； ﻩ ﻩ
ﻩﻩﻩcount++;
ﻩ } 　　　 　 　 　
}ﻩ
ﻩ elsｅ 　 // 正常缺页置换
ﻩ　 ｛
ﻩﻩ if(ｐsｔate==０） // 页不存在则置换页面
ﻩﻩ　 ｛
ﻩ　 　ﻩpａgefｒamｅ[rｐoｉｎt］＝ｐf_ｉnfo、ｓｅｒial［vpｏｉnt］；ﻩ ﻩ
ﻩﻩﻩﻩrｐoiｎt=(rpｏｉnｔ+1) ％ pf_info、total＿ｐｆ；ﻩﻩ ﻩﻩ
ﻩ ﻩｐf_inｆo、ｄiｓeffect＋+; 　 // 缺页次数加1ﻩﻩ ﻩ ﻩ
　 ｝
ﻩ　 }
　 Sleｅｐ(1０)；　　

ﻩ　 ｄisplayinｆo(）； 　 /／ 显示当前状态
　 ｝ // 置换算法循环结束
ｇetcｈ(）;
retuｒn;
}
//////／/／／///／//／//////／/////／//／///／/////////／/／///／/／/／///／/／／／//
// 　ＬRU页面置换算法
void lru（voiｄ） 　 　 　 　 　 　 　 　　 　 　 　 　
｛
int n，count,pstａte，max； 　
ｒｐoint=0; 　 //　页面替换指针
　　iｎｖａlｉdcounｔ = 0； //　缺页次数初始化为0
　ｃreatｅps(）； 　 ／/ 随机生成访问序列
　 counｔ=０； 　 　 /／ 就是否装满所有得页框
　ｆoｒ（n=0；ｎ＜ｐf_info、ｔotａl_pf；n++)　
　{
ﻩ pａgｅframe[ｎ]=－1；　 　 // 清除页框信息
ﻩ　 pagｅｈisｔoｒｙ［n]＝0;　 　/／ 清除页框历史
　　}
　iｎpflag＝０； 　　 /／缺页标志，０为不缺页，1为缺页
　for（vpoint=0；vpoｉnt＜ｐf_ｉｎfo、tｏtaｌ＿ｐn;vｐoiｎt+＋) // 执行算法
　｛
pstatｅ=fiｎdpage(pf_inｆo、seｒial［vpｏint］); //查找页面就是否在内存
if（count〈ｐf＿iｎfo、tｏtａl_pf) ／/ 开始时不计算缺页
ﻩ　 { 　　
　 　　 　 if（pｓtaｔｅ==0) 　 /／ 页不存在则装入页面
ﻩ {
ﻩﻩﻩｐageframe［rpoiｎｔ］=pf_iｎｆo、serial[ｖpｏint]; //把要调入得页面放入一个空得页框里
ﻩﻩﻩrpoinｔ＝(rpoint+１） ％ pｆ_ｉnｆo、tｏtal_pf;ﻩ
ﻩﻩcount+＋；
ﻩﻩ }
｝
else // 正常缺页置换
　｛
ﻩ iｆ（ｐstate==０）/／ 页不存在则置换页面
　　{
　mａｘ=0；
　for（n=１;n〈pf_ｉｎｆｏ、ｔｏtaｌ_pf；n++)
ﻩﻩ　｛
ﻩﻩﻩ 　　ｉｆ(ｐageｈｉｓｔorｙ［n］＞pagehisｔｏrｙ[ｍａx］)
ﻩ ﻩ{
ﻩﻩ 　 max=n；
ﻩﻩ}
ﻩ }
ﻩ ﻩ rpoiｎｔ=maｘ;
ﻩ pagefｒame[rpoｉnt］=ｐf＿iｎfo、serｉaｌ［ｖpoiｎt］;
ﻩﻩ ｐagehisｔoｒｙ［rpoinｔ］=0；
ﻩﻩﻩ pf＿info、disｅfｆeｃt＋+；　　／/　缺页次数加１ ﻩ
ﻩ }
ﻩ ｝
　 Sｌeｅp(10）；
ﻩ　 diｓｐlayinfo（）； // 显示当前状态
} ﻩ／/ 置换算法循环结束
　 ＿geｔｃh(）;
　 　ｒeturn;
｝
／//／/////／/／/／///／／
/／最佳置换算法
　 自己完成
／////////／//////／/／//／/／/／／／//／／///／／／///////／／/////／//////／///////
//　　主函数
int　ｍaｉｎ(）
{
char　cｈ；
　　system(＂cｌｓ") ;
while　（ truｅ　） 　 　 　 　　 　　 　 　 　
{
　 printf（＂＊＊＊＊＊＊＊＊＊**＊＊＊＊＊*＊********＊*＊*＊*＊*＊＊＊*＊＊＊＊*＼n”）；
　 priｎtf(” 　若要执行FIFO页面置算法请按1\ｎ”）；
ｐrintf（” 　 　若要执行LＲＵ 页面置算法请按２\ｎ＂);
　 　ｐrintf（” 　 若要退出请按3\n")　；
　 ｐriｎｔｆ（”＊*＊＊**＊*＊＊**＊*＊**＊**＊*＊**＊*＊**＊＊＊＊****＊＊＊＊\ｎ＂）;
　 ｐrintｆ（ "Ｅnter ｙour choice （１ or ２ ｏｒ 3): ＂）； 　
do
｛ 　 //如果输入信息不正确,继续输入
　　 　 ｃh = （ｃhａr)getch(） ;
}whｉle（ｃh　！=　’1' ＆＆ ch　！= ’2'&& ｃh ！= '3'）；
printｆ(”＼n\ｎ您按得就是：%c ,现在为您执行对应操作.＂，cｈ）；
if(ch　== ’3'） ／／选择３,退出
{
　rｅtuｒｎ ０;
｝
ﻩｅｌsｅ　
{
ﻩif(cｈ =　'1’)　 /／选择1，ＦIFO
ﻩ ｛
ﻩ　　　pｒｉntｆ（"\n\n－—----—--—＊＊***执行ＦIFO算法＊***＊-—-——--—-—-＼n")；
　 　　　fifo(）;　
ﻩ}
ｅlｓe
ﻩ｛
ﻩ 　 printf(＂＼n\n—--－-—-－－—＊＊***执行LRU算法＊*＊＊＊—－-－－—-—－-\ｎ”);
　 　　 ／/lrｕ（）;
｝
｝
ｓｙstem（"cls”) ;
　｝
printf(”\n\nPresｓ Anｙ　Key To Contｉnuｅ:");
　getch（) ;
ｒetuｒn　0；
｝