操作系统(含课程设计),平时作业2020秋华工答案

华南理工大学

2020秋季“操作系统”课程平时作业

一、题目: 页面置换算法模拟实验

二、目的

分别采用最佳(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

int s[]={4,3,2,1,4,3,5,4,3,2,1,5};//用户需求页顺序12

int b[4];//物理块

int a[4][12];//最后输出显示

int q=0;//缺页次数

//最佳置换算法寻找物理块中最长时间不使用的页，参数值为当前用户需求页的数量-1，返回值为物理块中需要替换的页位置

int findLong(int f){

//物理块中第x块中的页面是最长时间不使用的页

int x=0;

//当前物理块下次使用的间隔

int y=0;

//查找第一个物理块的页面下次使用间隔

int j = 0 ;

for(j=f+1;j<12;j++){

if(b[0]==s[j]){

//获取下次使用间隔

y=j-f;

break;

}else if(j==12){

//如果查找完所有需求页都没有则为最长时间不使用的页直接返回物理块位置。

return 0;

}

}

//查找第二个物理块的页面下次使用间隔

for(j=f+1;j<12;j++){

if(b[1]==s[j]){

//获取下次使用间隔

if(j-f>y){

//如果该物理块的页面下次使用间隔比上一个物理块更大则替换

y=j-f;

x=1;

}

break;

}else if(j==12){

//如果查找完所有需求页都没有则为最长时间不使用的页直接返回物理块位置。

return 1;

}

}

//查找第三个物理块的页面下次使用间隔

for(j=f+1;j<12;j++){

if(b[2]==s[j]){

//获取下次使用间隔

if(j-f>y){

//如果该物理块的页面下次使用间隔比上一个物理块更大则替换

y=j-f;

x=2;

}

break;

}else if(j==12){

//如果查找完所有需求页都没有则为最长时间不使用的页直接返回物理块位置。

return 2;

}

}

//查找第四个物理块的页面下次使用间隔

for(j=f+1;j<12;j++){

本文来源：https://www.bwwdw.com/article/vise.html