操作系统含课程设计平时作业秋华工答案.docx
《操作系统含课程设计平时作业秋华工答案.docx》由会员分享，可在线阅读，更多相关《操作系统含课程设计平时作业秋华工答案.docx（18页珍藏版）》请在冰点文库上搜索。
操作系统含课程设计平时作业秋华工答案
华南理工大学
2021秋季“操作系统”课程平时作业
一、题目:
页面置换算法模拟实验
二、目的
分别采用最佳（Optimal）置换算法、先进先出（FIFO）页面置换算法和最近最少使用（LRU）置换算法对用户输入的页面号请求序列进行淘汰和置换，从而加深对页面置换算法的理解。
三、内容和要求
认真阅读教材（计算机操作系统（第四版），汤小丹，西安电子科技大学出版社）P162页5.3节页面置换算法的实现思想，编写一个页面转换算法模拟程序用于处理进程的页面访问序列串。
请用C/C++语言（编程语言不限）编一个页面置换算法模拟程序。
用户通过键盘输入分配给进程的物理内存块总数，再输入用户页面号请求序列，然后分别采用最佳（Optimal）置换算法、先进先出（FIFO）页面置换算法和最近最少使用（LRU）置换算法三种算法对页面请求序列进行处理，最后按照课本P163-P165页图所示的置换图格式输出每次页面请求后各物理块内存放的页面号，并算出总的缺页率（缺页次数/总的请求次数）。
程序编写完成后，实验时请输入页面号请求序列为4、3、2、1、4、3、5、4、3、2、1、5，当分配给进程的物理块数分别为3块和4块时，试用自己编写的模拟程序进行页面转换并输出置换图和缺页次数、缺页率，最后比较三种页面置换算法的优缺点。
三种页面置换算法的思想可参考教材P162-P15页。
四、实验要求：
每人完成一份平时作业报告。
报告分设计思想、数据定义、处理流程、源程序、运行结果截图、设计体会等部分。
1）给出数据定义和详细说明；
2）给出实现思想和设计流程；
3）调试完成源程序；
4）屏幕观察运行结果；
5）总结自己的设计体会；
编程语言及操作系统平台不限。
五、提交内容
本平时作业每个人必须单独完成。
最后需提交的报告内容包括：
数据定义、算法思路及流程图、源程序（关键代码需要注释说明）、运行截图、心得体会或者总结。
将以上内容编写为一个WORD文档（.DOC）上传到教学管理系统。
平时作业严禁抄袭。
发现抄袭（重复率97%以上）一律以不及格论。
课作业内容要完整，一定要有数据定义、算法思路、流程图、心得体会、运行输出信息截屏等内容，如果只提交源代码则大作业成绩记为不合格。
一、设计思想及实现思路
在进程运行过程中，若其所要访问的页面不在内存，而需把它们调入内存，但内存已无空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据送到磁盘的对换区中。
但应将哪个页面调出，须根据一定的算法来确定。
通常，把选择换出页面的算法称为页面换算法。
1.最佳（Optimal）置换算法
最佳置换算法是一种理想化的算法，它具有最好的性能，但实际上是无法实现的。
通常使用最佳置换算法作为标准，来评价其他算法的优劣。
实现思路：
本次实验为模拟最佳置换算法，所以用户需求页顺序视为已知序列4、3、2、1、4、3、5、4、3、2、1、5，首先前三次调用不需要置换页面，第4次开始则需要开始判断当前每个物理块中的页面在未来调用的间隔是多少，取需求页面间隔最长的物理块置换即可。
2.先进先出（FIFO）页面置换算法
FIFO算法是最早出现的置换算法。
该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。
该算法实现简单，只需要把一个进程已调入内存的页面按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。
但该算法与进程实际运行的规律不相适应，因为在进程中，有些页面经常被访问，比如，含有全局变量、常用函数、例程等的页面，FIFO算法并不能保证这些页面不被淘汰。
实现思路：
该算法实现较为简单，只需设置一个变量保存最老页面的位置即可，需要置换的时候直接替换最老页面。
3.最近最久未使用（LRU）置换算法
最近最久未使用的页面置换算法是根据页面调入内存后的使用情况作出决策的。
由于无法预测各页面将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU置换算法是选择最近最久未使用的页面予以淘汰。
实现思路：
记录每个物理块的使用间隔，需要置换的时候就更换使用间隔最长的物理块的页面。
二、源程序（运算所需数据说明已在程序中注释）和运行输出截图
1.最佳（Optimal）置换算法
#include
ints[]={4,3,2,1,4,3,5,4,3,2,1,5};//用户需求页顺序12
intb[4];//物理块
inta[4][12];//最后输出显示
intq=0;//缺页次数
//最佳置换算法寻找物理块中最长时间不使用的页，参数值为当前用户需求页的数量-1，返回值为物理块中需要替换的页位置
intfindLong（intf）{
//物理块中第x块中的页面是最长时间不使用的页
intx=0;
//当前物理块下次使用的间隔
inty=0;
//查找第一个物理块的页面下次使用间隔
intj=0;
for（j=f+1;j<12;j++）{
if（b[0]==s[j]）{
//获取下次使用间隔
y=j-f;
break;
}elseif（j==12）{
//如果查找完所有需求页都没有则为最长时间不使用的页直接返回物理块位置。
return0;
}
}
//查找第二个物理块的页面下次使用间隔
for（j=f+1;j<12;j++）{
if（b[1]==s[j]）{
//获取下次使用间隔
if（j-f>y）{
//如果该物理块的页面下次使用间隔比上一个物理块更大则替换
y=j-f;
x=1;
}
break;
}elseif（j==12）{
//如果查找完所有需求页都没有则为最长时间不使用的页直接返回物理块位置。
return1;
}
}
//查找第三个物理块的页面下次使用间隔
for（j=f+1;j<12;j++）{
if（b[2]==s[j]）{
//获取下次使用间隔
if（j-f>y）{
//如果该物理块的页面下次使用间隔比上一个物理块更大则替换
y=j-f;
x=2;
}
break;
}elseif（j==12）{
//如果查找完所有需求页都没有则为最长时间不使用的页直接返回物理块位置。
return2;
}
}
//查找第四个物理块的页面下次使用间隔
for（j=f+1;j<12;j++）{
if（b[3]==s[j]）{
//获取下次使用间隔
if（j-f>y）{
//如果该物理块的页面下次使用间隔比上一个物理块更大则替换
y=j-f;
x=3;
}
break;
}elseif（j==12）{
//如果查找完所有需求页都没有则为最长时间不使用的页直接返回物理块位置。
return3;
}
}
returnx;
}
/*最佳置换算法
被淘汰页是以后不再使用或者最长时间不使用的
因不能预知未来会使用哪个页面所以无法实现
模拟实验的条件为已知用户所有需求页
*/
voidopt（）{
//模拟用户需求页面操作
intj=0;
for（j=0;j<12;j++）{
//内存未满则直接调入内存
if（j<4）{
b[j]=s[j];
}elseif（b[0]!
=s[j]&&b[1]!
=s[j]&&b[2]!
=s[j]&&b[3]!
=s[j]）{
//如果需求页在内存中则不需要更换，否则就需要查找更换位置
b[findLong（j）]=s[j];
//记录缺页次数
q++;
}
//输出显示
a[0][j]=b[0];
a[1][j]=b[1];
a[2][j]=b[2];
a[3][j]=b[3];
}
//以下为输出显示
printf（"需求页:
"）;
for（j=0;j<12;j++）{
printf（"%d",s[j]）;
}
printf（"\n物理块1:
"）;
for（j=0;j<12;j++）{
printf（"%d",a[0][j]）;
}
printf（"\n物理块2:
"）;
for（j=0;j<12;j++）{
if（j==0）{
printf（""）;
}else{
printf（"%d",a[1][j]）;
}
}
printf（"\n物理块3:
"）;
for（j=0;j<12;j++）{
if（j<2）{
printf（""）;
}else{
printf（"%d",a[2][j]）;
}
}
printf（"\n物理块4:
"）;
for（j=0;j<12;j++）{
if（j<3）{
printf（""）;
}else{
printf（"%d",a[3][j]）;
}
}
printf（"\n"）;
printf（"最佳置换算法的缺页数%d\n",q）;
//输出缺页率
intqyl=q/12.0*100;
printf（"最佳置换算法的缺页率为%d%%",qyl）;
}
intmain（）
{
opt（）;
return0;
}
当物理块数为3时输出结果为：
当物理块数为4时输出结果为：
2.先进先出（FIFO）页面置换算法
#include
ints[]={4,3,2,1,4,3,5,4,3,2,1,5};//用户需求页顺序12
intb[3];//物理块
inta[3][12];//最后输出显示
intq=0;//缺页次数
/*FIFO置换算法
被淘汰页是最老的页面
*/
voidfifo（）{
//最老的页面的物理块位置
intf=0;
//模拟用户需求页面操作
intj=0;
for（j=0;j<12;j++）{
//内存未满则直接调入内存
if（j<3）{
b[j]=s[j];
//如果需求页在内存中则不需要更换，否则就需要查找更换位置
}elseif（b[0]!
=s[j]&&b[1]!
=s[j]&&b[2]!
=s[j]）{
//更换最老的页面,并记录当前老的页面
b[f]=s[j];
f++;
if（f>2）{
f=0;
}
//记录缺页次数
q++;
}
//输出显示
a[0][j]=b[0];
a[1][j]=b[1];
a[2][j]=b[2];
}
//以下为输出显示
printf（"需求页:
"）;
for（j=0;j<12;j++）{
printf（"%d",s[j]）;
}
printf（"\n物理块1:
"）;
for（j=0;j<12;j++）{
printf（"%d",a[0][j]）;
}
printf（"\n物理块2:
"）;
for（j=0;j<12;j++）{
if（j==0）{
printf（""）;
}else{
printf（"%d",a[1][j]）;
}
}
printf（"\n物理块3:
"）;
for（j=0;j<12;j++）{
if（j<2）{
printf（""）;
}else{
printf（"%d",a[2][j]）;
}
}
printf（"\n"）;
printf（"先进先出置换算法的缺页数%d\n",q）;
//输出缺页率
intqyl=q/12.0*100;
printf（"先进先出置换算法的缺页率为%d%%",qyl）;
}
intmain（）
{
fifo（）;
return0;
}
当物理块数为3时输出结果为：
当物理块数为4时输出结果为：
3.最近最久未使用（LRU）置换算法
#include
ints[]={4,3,2,1,4,3,5,4,3,2,1,5};//用户需求页顺序12
intb[4];//物理块
inta[4][12];//最后输出显示
intq=0;//缺页次数
intl[4];//记录物理块中页面的使用间隔
intlo=0;//当前最未使用的页面的物理块位置
//更新使用间隔并记录当前最未使用的页面的物理块位置,参数为当前使用页面的物理块位置
voidupdateTime（intu）{
intj;
for（j=0;j<4;j++）{
if（j==u）{
l[j]=0;
}else{
//使用间隔加1
l[j]++;
}
}
lo=0;
//记录当前最未使用的页面的物理块位置
for（j=0;j+1<4;j++）{
if（l[j]lo=j+1;
}
}
}
/*LRU置换算法
被淘汰页是最老的页面
*/
voidlru（）{
//模拟用户需求页面操作
intj=0;
for（j=0;j<12;j++）{
//内存未满则直接调入内存
if（j<4）{
b[j]=s[j];
updateTime（j）;
//如果需求页在内存中则不需要更换但是页面使用间隔也要刷新，否则就需要查找更换位置
}elseif（b[0]==s[j]）{
updateTime（0）;
}elseif（b[1]==s[j]）{
updateTime
（1）;
}elseif（b[2]==s[j]）{
updateTime
（2）;
}elseif（b[3]==s[j]）{
updateTime（3）;
}else{
b[lo]=s[j];
updateTime（lo）;
//记录缺页次数
q++;
}
//输出显示
a[0][j]=b[0];
a[1][j]=b[1];
a[2][j]=b[2];
a[3][j]=b[3];
}
//以下为输出显示
printf（"需求页:
"）;
for（j=0;j<12;j++）{
printf（"%d",s[j]）;
}
printf（"\n物理块1:
"）;
for（j=0;j<12;j++）{
printf（"%d",a[0][j]）;
}
printf（"\n物理块2:
"）;
for（j=0;j<12;j++）{
if（j==0）{
printf（""）;
}else{
printf（"%d",a[1][j]）;
}
}
printf（"\n物理块3:
"）;
for（j=0;j<12;j++）{
if（j<2）{
printf（""）;
}else{
printf（"%d",a[2][j]）;
}
}
printf（"\n物理块4:
"）;
for（j=0;j<12;j++）{
if（j<3）{
printf（""）;
}else{
printf（"%d",a[3][j]）;
}
}
printf（"\n"）;
printf（"最久未使用置换算法的缺页数%d\n",q）;
//输出缺页率
intqyl=q/12.0*100;
printf（"最久未使用置换算法的缺页率为%d%%",qyl）;
}
intmain（）
{
lru（）;
return0;
}
当物理块数为3时输出结果为：
当物理块数为4时输出结果为：
三、各算法比较及学习心得体会
从各算法运算结果可以看出最佳置换算法缺页率是最低，但实际上是无法实现的，因为我们无法预知用户未来会使用到什么页面，剩下的两种，从设计思想来看，最近最久未使用算法是要优于先进先出算法的。
不过由于用户的使用情况是无法预知的，所以需要根据使用场景和硬件条件来选择合适的算法。
经过本次课程设计，完成题目“常用页面置换算法原理模拟实验”，熟悉了的常用基本命令，理解并掌握了UNIX提供的vi编辑器来编译C程序，学会利用gcc、gdb编译、调试C程序。
做课程设计是为了对平时学习的理论知识与实际操作相结合，在理论和实践上进一步巩固已学基本理论及应用知识并加以综合提高,学会将知识应用于实际的方法，提高分析和解决问题的能力。
在做课程设计的过程中，深深感觉到自身所学知识的有限。
有些题目书木上没有提及，所以就没有去研究过，做的时候突然问觉得自己真的有点无知，虽然现在去看依然可以解决问题，但还是浪费了许多，这一点是必须在以后的学习中加以改进的地方，同时也要督促自己在学习的过程中不断的完善自我。
在设计过程中的思考和讨论，对现有知识能够运用计算机来解决现实生活中的实际问题确立了信心，对模块化程序设计思想有了比较清晰的印象，为今后的程序设计奠定了一定的心理和技术上的准备。
这次课程设计加强了我对计算机操作系统的认识，对我个人而言是对所学课程内容掌握情况的一次自我验证。
通过课程设计提高了我对所学知识的综合应用能力，全面检查并掌握所学的内容，培养独立思考，在分析问题、解决问题的过程中，更是获得一种成功的喜悦。
升级会员 