完整word版操作系统课程设计页面置换算法C语言.docx
《完整word版操作系统课程设计页面置换算法C语言.docx》由会员分享，可在线阅读，更多相关《完整word版操作系统课程设计页面置换算法C语言.docx（20页珍藏版）》请在冰点文库上搜索。
完整word版操作系统课程设计页面置换算法C语言
页面置换算法
一．题目要求：
通过实现页面置换算法的FIFO和LRU两种算法，理解进程运行时系统是怎样选择换出页面的,对于两种不同的算法各自的优缺点是哪些。
要求设计主界面以灵活选择某算法，且以下算法都要实现
1）最佳置换算法（OPT）：
将以后永不使用的或许是在最长（未来）时间内不再被访问的页面换出.
2）先进先出算法（FIFO）：
淘汰最先进入内存的页面,即选择在内存中驻留时间最久的页面予以淘汰。
3）最近最久未使用算法（LRU）:
淘汰最近最久未被使用的页面.
4）最不经常使用算法（LFU）
二．实验目的:
1、用C语言编写OPT、FIFO、LRU，LFU四种置换算法。
2、熟悉内存分页管理策略。
3、了解页面置换的算法.
4、掌握一般常用的调度算法。
5、根据方案使算法得以模拟实现.
6、锻炼知识的运用能力和实践能力。
三、设计要求
1、编写算法，实现页面置换算法FIFO、LRU；
2、针对内存地址引用串，运行页面置换算法进行页面置换；
3、算法所需的各种参数由输入产生（手工输入或者随机数产生）；
4、输出内存驻留的页面集合，页错误次数以及页错误率；
四．相关知识：
1．虚拟存储器的引入：
局部性原理：
程序在执行时在一较短时间内仅限于某个部分；相应的，它所访问的存储空间也局限于某个区域，它主要表现在以下两个方面:
时间局限性和空间局限性.
2．虚拟存储器的定义：
虚拟存储器是只具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统。
3．虚拟存储器的实现方式：
分页请求系统，它是在分页系统的基础上，增加了请求调页功能、页面置换功能所形成的页面形式虚拟存储系统。
请求分段系统,它是在分段系统的基础上，增加了请求调段及分段置换功能后,所形成的段式虚拟存储系统。
4．页面分配：
平均分配算法，是将系统中所有可供分配的物理块，平均分配给各个进程。
按比例分配算法,根据进程的大小按比例分配物理块.
考虑优先的分配算法，把内存中可供分配的所有物理块分成两部分：
一部分按比例地分配给各进程；另一部分则根据个进程的优先权，适当的增加其相应份额后,分配给各进程。
5．页面置换算法：
常用的页面置换算法有OPT、FIFO、LRU、Clock、LFU、PBA等.
五、设计说明
1、采用数组页面的页号
2、FIFO算法,选择在内存中驻留时间最久的页面予以淘汰；
分配n个物理块给进程,运行时先把前n个不同页面一起装入内存，然后再从后面逐一比较，输出页面及页错误数和页错误率。
3、LRU算法，根据页面调入内存后的使用情况进行决策；
同样分配n个物理块给进程,前n个不同页面一起装入内存,后面步骤与前一算法类似。
选择置换算法，先输入所有页面号，为系统分配物理块,依次进行置换：
六．设计思想：
OPT基本思想：
是用一维数组page[pSIZE］存储页面号序列，memery[mSIZE］是存储装入物理块中的页面。
数组next[mSIZE］记录物理块中对应页面的最后访问时间.每当发生缺页时，就从物理块中找出最后访问时间最大的页面，调出该页，换入所缺的页面。
FIFO基本思想：
是用队列存储内存中的页面，队列的特点是先进先出，与该算法是一致的，所以每当发生缺页时，就从队头删除一页，而从队尾加入缺页。
或者借助辅助数组time[mSIZE］记录物理块中对应页面的进入时间，每次需要置换时换出进入时间最小的页面.
LRU基本思想：
是用一维数组page[pSIZE]存储页面号序列,memery[mSIZE]是存储装入物理块中的页面。
数组flag[10］标记页面的访问时间。
每当使用页面时,刷新访问时间。
发生缺页时,就从物理块中页面标记最小的一页，调出该页，换入所缺的页面。
七．流程图：
如下页所示
开始
载入页号序列，从第0个得到页号
将页号放入物理块中，编号加1
引用串编号大于物理块数?
否
页号在物理块中?
根据选择的置换算法完成置换
页号序列载完?
结束
否
否
是
是
是
六．运行结果：
1。
按任意键进行初始化:
2。
载入数据：
3。
进入置换算法选择界面：
4。
运算中延迟操作：
5。
三种算法演示结果：
八。
结论
通过这次课程设计，不仅让我了解了页面置换算法，开始我一味的进行调试,急切的想侥幸调试出来，但由于没有进行深入的考虑,我调试了很久都没没有成功，我仔细的分析题目，分析材料,在原由的基础上我进行了改正，我最后还是调试成功了，还是经过了一翻努力，这次操作系统实习，不仅让我对操作系统这门课程有了更深入的研究、对很多重要的概念有了巩固和掌握.通过努力，三个页面置换算法程序都已经完成，此时此刻,我心里多了些成就感.虽然自己所做的很少也不够完善,但毕竟也是努力的结果.主要有以下几点收获：
1。
通过对上网和看书查阅相关资料，使自己对C语言的基本框架有新的了解，加深了对可视化程序的认识。
2。
在使用C语言来实现功能时,不像以往用的其他语言，它比较简练，更容易理解,实用性很强。
3.先进先出页面置换和LRU以及OPT算法各有特点,但是实践起来却很大，使自己对页面置换算法有了新的认识。
一周半的课程设计就要结束了,不但对专业知识有了更深的理解，更使的自己认识到实践的重要性，理论、实践相结合才能达到很好的学习效果，特别是程序语言的学习。
六．源代码：
如下页所示【使用C语言】
#includeh〉
#include〈stdlib。
h>
/*全局变量＊/
intmSIZE；/*物理块数*/
intpSIZE;/＊页面号引用串个数＊/
staticintmemery［10]=｛0}；/＊物理块中的页号*/
staticintpage[100]={0}；/＊页面号引用串＊/
staticinttemp[100]［10]=｛0};/＊辅助数组*/
/＊置换算法函数＊/
voidFIFO（）;
voidLRU（）；
voidOPT（）;
/＊辅助函数＊/
voidprint（unsignedintt）;
voiddesignBy（）；
voiddownload（）;
voidmDelay（unsignedintDelay）；
/*主函数*/
voidmain（）
｛
inti，k，code;
printf（”┏━━━━━━━━━━━━━━━━━━━━━━━━━┓\n”）;
printf（"┃请按任意键进行初始化操作.。
。
┃\n”）；
printf（”┗━━━━━━━━━━━━━━━━━━━━━━━━━┛\n”）；
printf（”>〉〉”）；
getch（）;
system（"cls”）;
printf（"请输入物理块的个数（M〈=10）：
”）;
scanf（"％d”，&mSIZE）;
printf（”请输入页面号引用串的个数（P〈=100）：
”）；
scanf（"％d",＆pSIZE）;
puts（"请依次输入页面号引用串（用空格隔开）：
”）；
for（i=0；i〈pSIZE；i++）
scanf（"％1d”,＆page[i］）;
download（）；
system（”cls"）;
do{
puts（”输入的页面号引用串为：
”）；
for（k=0；k<=（pSIZE—1）/20;k++）
｛
for（i=20＊k;（i｛
if（（（i+1）%20==0）|｜（（（i+1）%20）&＆（i==pSIZE-1）））
printf（”％d\n”,page[i]）；
else
printf（"%d",page[i］）;
｝
｝
printf（”**＊＊*＊＊*＊＊＊＊*＊*＊＊＊＊****\n”）;
printf（”＊请选择页面置换算法：
\t\t\t*\n"）;
printf（"*———---——-————--—-—----—---—--———-——————-—＊\n”）;
printf（”＊1.先进先出（FIFO）＊\n”）；
printf（”*2。
最近最久未使用（LRU）*\n"）;
printf（"*3。
最佳（OPT）*\n”）；
printf（"＊4。
退出*\n”）;
printf（"*＊＊***＊*＊*****＊**＊＊＊＊*＊\n"）;
printf（”请选择操作：
［]\b\b"）;
scanf（”%d",&code）；
switch（code）
｛
case1：
FIFO（）；
break;
case2:
LRU（）;
break；
case3：
OPT（）;
break；
case4：
system（"cls”）;
exit（0）;
default:
printf（"输入错误,请重新输入：
”）;
｝
printf（"按任意键重新选择置换算法：
>>>"）；
getch（）;
system（”cls"）;
｝while（code！
=4）;
getch（）；
}
/*载入数据*/
voiddownload（）
{
inti；
printf（”╔════════════╗\n"）；
printf（”║正在载入数据,请稍候!
!
！
║\n”）;
printf（"╚════════════╝\n"）;
printf（"Loading..。
\n”）;
printf（"O"）；
for（i=0；i〈51；i++）
printf（"\b”）;
for（i=0;i<50;i++）
｛
mDelay（（pSIZE+mSIZE）/2）;
printf（">"）；
}
printf（”\nFinish.\n载入成功，按任意键进入置换算法选择界面：
>>〉"）；
getch（）；
}
/*设置延迟＊/
voidmDelay（unsignedintDelay）
{
unsignedinti;
for（；Delay〉0;Delay--）
{
for（i=0;i〈124；i++）
｛
printf（”\b"）;
｝
}
}
voidprint（unsignedintt）
｛
inti,j，k，l；
intflag；
for（k=0;k〈=（pSIZE—1）/20;k++）
｛
for（i=20*k；（i〈pSIZE）＆&（i〈20*（k+1））；i++）
｛
if（（（i+1）%20==0）｜｜（（（i+1）%20）＆&（i==pSIZE-1）））
printf（"%d\n”,page[i］）；
else
printf（”％d"，page[i］）;
｝
for（j=0;j〈mSIZE;j++）
{
for（i=20*k；（i〈mSIZE+20*k）&＆（i{
if（i>=j）
printf（”|%d|"，temp［i］［j]）；
else
printf（”｜|”）;
}
for（i=mSIZE+20＊k；（i{
for（flag=0，l=0；l〈mSIZE;l++）
if（temp［i］［l］==temp［i—1]［l］）
flag++;
if（flag==mSIZE）/*页面在物理块中*/
printf（""）；
else
printf（”|％d|",temp［i][j］）；
}
/＊每行显示20个＊/
if（i％20==0）
continue;
printf（"\n”）;
｝
｝
printf（"-——-—-——-———-———————-—-—-——------—----—-\n”）;
printf（"缺页次数：
%d\t\t"，t+mSIZE）；
printf（”缺页率：
%d/%d\n”,t+mSIZE，pSIZE）;
printf（"置换次数:
％d\t\t”,t）；
printf（"访问命中率：
%d％%\n"，（pSIZE—（t+mSIZE））*100/pSIZE）;
printf（"--—--——-—-———--------—-—-—----—-—------—\n"）；
}
/*计算过程延迟＊/
voidcompute（）
｛
inti;
printf（”正在进行相关计算，请稍候"）;
for（i=1；i<20；i++）
｛
mDelay（15）；
if（i%4==0）
printf（"\b\b\b\b\b\b\b\b\b\b\b\b"）;
else
printf（"Θ"）；
}
for（i=0;i++<30；printf（”\b”））;
for（i=0;i++<30；printf（”"））；
for（i=0；i++〈30；printf（”\b”））;
}
/*先进先出页面置换算法＊/
voidFIFO（）
｛
intmemery[10］={0}；
inttime［10]={0｝;/＊记录进入物理块的时间＊/
inti,j，k，m；
intmax=0;/＊记录换出页*/
intcount=0；/*记录置换次数*/
/＊前mSIZE个数直接放入＊/
for（i=0;i{
memery[i］=page[i］;
time［i］=i;
for（j=0;jtemp[i］[j］=memery[j];
}
for（i=mSIZE;i｛
/*判断新页面号是否在物理块中＊/
for（j=0，k=0；j{
if（memery［j]！
=page［i］）
k++；
｝
if（k==mSIZE）/*如果不在物理块中*/
｛
count++；
/*计算换出页＊/
max=time［0]〈time[1]?
0：
1;
for（m=2;mif（time［m］〈time[max]）
max=m；
memery［max]=page［i];
time[max］=i;/＊记录该页进入物理块的时间*/
for（j=0；jtemp[i］［j]=memery[j］;
}
else
{
for（j=0;jtemp［i]［j]=memery[j];
}
｝
compute（）；
print（count）；
｝
/*最近最久未使用置换算法＊/
voidLRU（）
｛
intmemery［10]={0};
intflag［10]={0}；/*记录页面的访问时间*/
inti,j，k，m;
intmax=0；/＊记录换出页*/
intcount=0;/＊记录置换次数*/
/*前mSIZE个数直接放入＊/
for（i=0；i｛
memery［i］=page[i］;
flag［i］=i;
for（j=0;jtemp［i］［j]=memery［j];
｝
for（i=mSIZE;i〈pSIZE;i++）
{
/*判断新页面号是否在物理块中＊/
for（j=0，k=0；j｛
if（memery[j］!
=page[i]）
k++；
else
flag[j］=i；/＊刷新该页的访问时间*/
｝
if（k==mSIZE）/＊如果不在物理块中*/
｛
count++；
/*计算换出页＊/
max=flag[0]〈flag[1]?
0：
1；
for（m=2;m〈mSIZE；m++）
if（flag［m]〈flag［max］）
max=m;
memery[max］=page[i］;
flag[max]=i;/*记录该页的访问时间*/
for（j=0；jtemp［i][j]=memery[j];
}
else
{
for（j=0;j〈mSIZE；j++）
temp［i][j]=memery[j］；
}
｝
compute（）;
print（count）;
}
/*最佳置换算法＊/
voidOPT（）
{
intmemery［10]={0}；
intnext［10］=｛0};/＊记录下一次访问时间*/
inti，j,k，l,m；
intmax；/*记录换出页*/
intcount=0；/＊记录置换次数＊/
/*前mSIZE个数直接放入*/
for（i=0;i〈mSIZE；i++）
｛
memery［i］=page[i］;
for（j=0；j〈mSIZE；j++）
temp［i]［j]=memery［j］;
}
for（i=mSIZE;i｛
/*判断新页面号是否在物理块中*/
for（j=0,k=0；j〈mSIZE；j++）
｛
if（memery［j]!
=page[i］）
k++；
}
if（k==mSIZE）/＊如果不在物理块中＊/
｛
count++；
/＊得到物理快中各页下一次访问时间＊/
for（m=0；m｛
for（l=i+1；l〈pSIZE；l++）
if（memery[m]==page[l]）
break；
next[m]=l；
}
/＊计算换出页*/
max=next[0]>=next［1］?
0:
1；
for（m=2;m〈mSIZE;m++）
if（next［m］>next［max]）
max=m;
/＊下一次访问时间都为pSIZE，则置换物理块中第一个*/
memery[max］=page[i];
for（j=0；j〈mSIZE;j++）
temp［i][j]=memery［j］；
}
else{
for（j=0；j〈mSIZE；j++）
temp[i］[j]=memery［j];
｝
｝
compute（）；
print（count）；
｝
升级会员 