请求调页存储管理方式的模拟.docx

请求调页存储管理方式的模拟.docx

《请求调页存储管理方式的模拟.docx》由会员分享，可在线阅读，更多相关《请求调页存储管理方式的模拟.docx（36页珍藏版）》请在冰点文库上搜索。

请求调页存储管理方式的模拟

《网络操作系统》

课程设计报告书

题目：

请求调页存储管理方式的模拟

学号：

学生姓名：

指导教师：

2010年12月10日

课程设计一：

请求调页存储管理方式的模拟

一、实验目的

二、实验内容

三、设计思路

四、文件系统结构的说明

五、数据结构的说明

六、程序流程图

七、源代码

八、运行结果以及分析

九、使用说明

十、总结

课程设计二：

通过DNS协议，可实现IP地址和主机名之间的转换

一、实验目的

二、实验内容

三、设计思路

四、文件系统结构的说明

五、源代码

六、运行结果以及分析

七、使用说明

八、总结

课程设计一

一：

实验目的

1．通过模拟实现请求页式存储管理的几种基本页面置换算法，了解虚拟储技术的特点。

2．通过对页面、页表、地址转换和页面置换过程的模拟，加深对请求调页系统的原理和实现过程的理解。

3．掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程，并比较它们的效率。

二：

实验内容

1．假设每个页面中可存放10条指令，分配给一个作业的内存块数为4

2．用C语言模拟一作业的执行过程。

该作业共有320条指令，即它的地址空间为32页，目前它的所有页都还未调入内存。

在模拟过程中，如果访问的指令已在内存，则显示其物理地址，并转下一条指令。

如果所访问的指令还未装入内存，则发生缺页，此时需记录缺页的次数，并将相应页调入内存。

如果4个内存块中均已装入该作业，则需进行页面转换。

最后显示其物理地址，并转下一条指令。

在所有320条指令执行完毕后，请计算并显示作业运行过程中发生的缺页率。

3．置换算法：

请分别考虑OPT、FIFO和LRU算法。

4．作业中指令的访问次序按下述原则生成：

50%的指令是顺序执行的

25%的指令是均匀分布在前地址部分

25%的指令是均匀分布在后地址部分

具体的实施办法：

①在[0,319]之间随机选取一条起始指令，其序号为m

②顺序执行下一条指令，即序号为m+1的指令

③通过随机数，跳转到前地址部分[0,m-1]中的某条指令处，其序号为m1；

④顺序执行下一条指令，即序号为m1+1的指令

⑤通过随机数，跳转到后地址部分［m1+2,319］中的某条指令处，其序号为m2;

⑥顺序执行下一条指令，即序号为m2+1的指令

⑦重复跳转到前地址部分、顺序执行、跳转到后地址部分、顺序执行的过程，直至执行320条指令。

三：

设计思路

因为在程序运行的过程中，当我们访问一个页面时，倘若此页面不在内存当中，我们就需要将其调入内存。

此时就产生了两个问题：

内存是否有空闲和倘若内存有空闲我们要将那个页面调出的问题。

这样的话就需要根据一定的算法来判断决定。

我们大家都知道，算法的好坏反映在程序执行的效率上面，所以我们要根据不同的情况调用不同的算法。

这里我们有三种置换算法：

1最佳置换算法（Optimal）2、先进先出法（FirstInFirstOut）3、最近最久未使用（LeastRecentlyUsed）。

所谓最佳置换算法，就是其所选择的被淘汰页是将来不再被使用，或者是在最远的将来才被访问的页面。

采用这种页面置换算法，保证有最少的缺页率。

但由于目前还无法预知一个进程在内存的若干个页面中，哪个在最长的时间内不会被访问，因而，现实中该算法是无法实现的。

因此在该算法的模拟过程中，页面访问次序必须是给定的，具体实现为：

对每一个物理块设置一个整数型的访问标志位，当需要置换物理块中的某一页时，将每一个物理块中的页面号与当前需调入页以后的每一页面号进行比较，若物理块中的页面号与所有的页面号都不同，则该页即为将来不再使用的页，将访问标记设置为1000，表示将来不会用，设置为一个很大数；若找到页号相同的则将其访问次序记入访问标记，比较访问标记，最大的即为最久不会被访问的，将其换出。

所谓先进先出法，就是总是淘汰最先进入内存的页面，既选择在内存中驻留时间最久的页面予以淘汰。

在该算法的模拟过程中，每当某一页面进入内存时（包括页面置换时页面的置入），物理块中各页面访问标记自动加一，置换后，将置换页面所在的物理块中访问标记减一；这样能防止当物理块访问标记出现两个以上相同的值的错误执行，更好地模拟了先进先出法。

所谓最近最久未使用，就是以最近的过去作为不久将来的近似，将过去最长一段时间里不曾被使用的页面置换掉。

在该算法的模拟过程中，每当物理块中的页面被访问时，便将其访问标记置为－1。

以后每执行一条指令，便将物理块中各页面的访问标记加一，需置换时访问标记最大的便是将要被置换的。

四：

文件系统结构的说明

#include

#include

#include

#include

#defineBsize4

typedefstructBLOCK//声明一种新类型——物理块类型

{

intpageNum;//页号

intaccessed;//访问字段，其值表示多久未被访问

}BLOCK;

intpc;//程序计数器，用来记录指令的序号

intm;//缺页计数器，用来记录缺页的次数

staticintrandom[320];//用来存储320条随机数

BLOCKblock[Bsize];//定义一大小为4的物理块数组

voidinit（）;//程序初始化函数

intfindExist（intcurpage）;//查找物理块中是否有该页面

intfindSpace（）;//查找是否有空闲物理块

intfindReplace（）;//查找应予置换的页面

voiddisplay（）;//显示

voidsuijishu（）;//产生320条随机数,显示并存储到random[320]

voidpagestring（）;//显示调用的页面队列

voidOPT（）;//OPT算法——最佳置换算法

voidLRU（）;//LRU算法——最近最久未使用算法

voidFIFO（）;//FIFO算法

五：

数据结构的说明

在本程序中，对于物理块使用了结构体。

最后主函数通过依次调用三种算法函数来实现功能。

头文件：

#include

#include

#include

#include

#defineBsize4

物理块：

typedefstructBLOCK//声明一种新类型——物理块类型

{

intpageNum;//页号

intaccessed;//访问字段，其值表示多久未被访问

}BLOCK;

六：

程序流程图——整体

六：

程序流程图——LRU

七：

源代码

#include

#include

#include

#include

#defineBsize4

typedefstructBLOCK//声明一种新类型——物理块类型

{

intpageNum;//页号

intaccessed;//访问字段，其值表示多久未被访问

}BLOCK;

intpc;//程序计数器，用来记录指令的序号

intm;//缺页计数器，用来记录缺页的次数

staticintrandom[320];//用来存储320条随机数

BLOCKblock[Bsize];//定义一大小为4的物理块数组

voidinit（）;//程序初始化函数

intfindExist（intcurpage）;//查找物理块中是否有该页面

intfindSpace（）;//查找是否有空闲物理块

intfindReplace（）;//查找应予置换的页面

voiddisplay（）;//显示

voidsuijishu（）;//产生320条随机数,显示并存储到random[320]

voidpagestring（）;//显示调用的页面队列

voidOPT（）;//OPT算法——最佳置换算法

voidLRU（）;//LRU算法——最近最久未使用算法

voidFIFO（）;//FIFO算法

voidinit（）//程序初始化函数

{

for（inti=0;i

{

block[i].pageNum=-1;

block[i].accessed=0;

pc=m=0;

}

}

intfindExist（intcurpage）//查找物理块中是否有该页面

{

for（inti=0;i

{

if（block[i].pageNum==curpage）

returni;//检测到内存中有该页面，返回block中的位置

}

return-1;

}

intfindSpace（）//查找是否有空闲物理块

{

for（inti=0;i

{

if（block[i].pageNum==-1）

returni;//找到空闲的block，返回block中的位置

}

return-1;

}

intfindReplace（）//查找应予置换的页面

{

intpos=0;

for（inti=0;i

{

if（block[i].accessed>block[pos].accessed）

pos=i;//找到应予置换页面，返回BLOCK中位置

}

returnpos;

}

voiddisplay（）

{

for（inti=0;i

{

if（block[i].pageNum!

=-1）

{printf（"%02d",block[i].pageNum）;}

}

cout<

}

voidsuijishu（）

{intflag=0;

printf（"请输入一个0~320之间的随机数：

\n"）;

scanf（"%d",&pc）;

printf（"-------按照要求产生的320个随机数：

-------\n"）;

for（inti=0;i<320;i++）

{

random[i]=pc;

if（flag%2==0）pc=++pc%320;//顺序执行下一条指令，即序号为m+1的指令

if（flag==1）pc=rand（）%（pc-1）;//通过随机数，跳转到前地址部分[0,m-1]中的某条指令处，其序号为m1

if（flag==3）pc=pc+1+（rand（）%（320-（pc+1）））;//通过随机数，跳转到后地址部分［m1+2,319］中的某条指令处，其序号为m2

flag=++flag%4;//如果4个内存块中均已装入该作业，则需进行页面转换

printf（"%03d",random[i]）;

if（（i+1）%10==0）cout<

}

}

voidpagestring（）

{

for（inti=0;i<320;i++）

{

printf（"%02d",random[i]/10）;//显示该页面

if（（i+1）%10==0）printf（"\n"）;//每个页面中可存放10条指令

}

}

voidOPT（）/*OPT算法——最佳置换算法.最佳置换算法是Blady在理论上提出的一种算法。

其所选择的被淘汰页是将来不再被使用，或者是在最远的将

来才被访问的页面.采用这种页面置换算法，保证有最少的缺页率。

但由于目前还无法预知一个进程在内存的若干个页面中，哪个在最长的

时间内不会被访问，因而，现实中该算法是无法实现的。

因此在该算法的模拟过程中，页面访问次序必须是给定的，具体实现为：

对每一

物理块设置一个整数型的访问标志位，当需要置换物理块中的某一页时，将每一个物理块中的页面号与当前需调入页以后的每一页面号进行

比较，若物理块中的页面号与所有的页面号都不同，则该页即为将来不再使用的页，将访问标记设置为1000，表示将来不会用，设置为一个

很大数；若找到页号相同的则将其访问次序记入访问标记，比较访问标记，最大的即为最久不会被访问的，将其换出。

*/

{

intexist,space,position;

intcurpage;

for（inti=0;i<320;i++）

{

if（i%100==0）getch（）;

pc=random[i];

curpage=pc/10;

exist=findExist（curpage）;

if（exist==-1）

{

space=findSpace（）;

if（space!

=-1）

{

block[space].pageNum=curpage;

display（）;

m=m+1;

}

else{

for（intk=0;k

{

for（intj=i;j<320;j++）

{

if（block[k].pageNum!

=random[j]/10）//物理块中的页面号与所有的页面号都不同{

block[k].accessed=1000;

}//将来不会用，设置为一个很大数

else//找到页号相同的则将其访问次序记入访问标记

{

block[k].accessed=j;

break;

}

}

}

position=findReplace（）;

block[position].pageNum=curpage;

display（）;

m++;

}

}

}

printf（"缺页次数:

%d\n",m）;

cout<<"缺页率:

"<<（m/320.0）*100<<"%"<

}

voidLRU（）/*LRU算法——最近最久未使用算法.该算法以最近的过去作为不久将来的近似，将过去最长一段时间里不曾被使用的页面置换掉。

在该算法的模拟过程中，每当物理块中的页面被访问时，便将其访问标记置为－1

以后每执行一条指令，便将物理块中各页面的访问标记加一，需置换时访问标记最大的便是将要被置换的。

*/

{

intexist,space,position;

intcurpage;

for（inti=0;i<320;i++）

{

if（i%100==0）getch（）;

pc=random[i];

curpage=pc/10;//每页十个指令

exist=findExist（curpage）;

if（exist==-1）

{

space=findSpace（）;

if（space!

=-1）

{

block[space].pageNum=curpage;

display（）;

m=m+1;

}

else

{

position=findReplace（）;

block[position].pageNum=curpage;

display（）;

m++;

}

}

elseblock[exist].accessed=-1;//恢复存在的并刚访问过的BLOCK中页面accessed为-1

for（intj=0;j<4;j++）

{block[j].accessed++;}//每执行一条指令，便将物理块中各页面的访问标记加一

}

printf（"缺页次数:

%d\n",m）;

cout<<"缺页率:

"<<（m/320.0）*100<<"%"<

}

voidFIFO（）/*该算法总是淘汰最先进入内存的页面，既选择在内存中驻留时间最久的页面予以淘汰。

在该算法的模拟过程中，每当某一页面进入内存时（包括页面置换时页面的置入），物理块中各页面访问标记自动加一，置换后，将置换页面

所在的物理块中访问标记减一；这样能防止当物理块访问标记出现两个以上相同的值的错误执行，更好地模拟了先进先出法；

*/

{

intexist,space,position;

intcurpage;

for（inti=0;i<320;i++）

{

if（i%100==0）getch（）;

pc=random[i];

curpage=pc/10;

exist=findExist（curpage）;

if（exist==-1）

{

space=findSpace（）;

if（space!

=-1）

{

block[space].pageNum=curpage;

display（）;

m=m+1;

}

else

{

position=findReplace（）;

block[position].pageNum=curpage;

display（）;

m++;

block[position].accessed--;

}

}

for（intj=0;j

block[j].accessed++;//每当某一页面进入内存时（包括页面置换时页面的置入），物理块中各页面访问标记自动加一

}

printf（"缺页次数:

%d\n",m）;

cout<<"缺页率:

"<<（m/320.0）*100<<"%"<

}

voidmain（）

{

intselect;

cout<<"请输入第一条指令号（0~320）：

";

suijishu（）;

cout<<"-------对应的调用页面队列-------"<

pagestring（）;

do

{

cout<<"----------------------------------------"<

cout<<"****************************************"<

cout<<"------1:

OPT2:

LRU3:

FIFO4:

退出------"<

cout<<"****************************************"<

cout<<"----------------------------------------"<

cout<<"请选择一种页面置换算法:

\n";

cin>>select;

cout<<"----------------------------------------"<

init（）;

switch（select）

{

case1:

printf（"您选择的是最佳置换算法OPT:

\n"）;

printf（"----------------------------------------\n"）;

OPT（）;//输出结果

break;

case2:

printf（"您选择的是最近最久未使用置换算法LRU:

\n"）;

printf（"----------------------------------------\n"）;

LRU（）;//输出结果

break;

case3:

printf（"您选择的是先进先出置换算法FIFO:

\n"）;

printf（"----------------------------------------\n"）;

FIFO（）;//输出结果

break;

default:

;

}

}while（select!

=4）;//每页分配4个内存块

}

}

八：

运行结果及分析

九：

使用说明

1、首先进入程序，在0~320之间随意挑选一个数输入，按回车键。

2、程序产生320个随机数。

3、开始选择一种置换算法进行页面的置换。

输入置换算法前面的数字，回车。

4、回车，得到置换算法的结果。

5、换做其他的算法，依然回车，得到置换算法的结果。

6、完成后选择退出。

。

十：

总结

1、通过这次操作系统课程设计的编写，我学到了很多。

刚开始见到设计要求时，我有点没有思路。

通过从网上参考了一些资料以后，我开始慢慢的了解了程序设计中的一些问题。

首先：

我对OPT、FIFO和LRU算法三种算法有了一定的了解。

其次，在分析题目要求的时候，对于如何将作业中指令的访问次序按一定原则生成的问题我没有一点思路。

最后，在仔细的看了一些类似的题目代码以后，我终于有了一定的理解。

原来在实现的时候，通过先顺序执行一条随机指令，譬如该指令为M0，然后开始顺序执行下一条指令M0+1，紧接着通过跳转函数跳转到地址部分［0，M-1］中的某条指令处，其序号记为M1，然后再次顺序执行下一条指令，即序号为M1+1的指令，最后通过跳转函数跳转到地址部分［M1+2,319］中的某条指令处，其序号为M2,，然后通过重复执行跳转到前址，顺序执行，跳转到后址，顺序执行的方法实现了50%的指令是顺序执行的；25%的指令是均匀分布在前地址部分；25%的指令是均匀分布在后地址部分的目的。

其中跳转函数上我复习了以前的rand函数。

2、其次，在实现设计要求功能的时候，对于那些页面跳转，页面置换的细节内容通过使用

if（（i+1）%10==0）cout<

flag=++flag%4;

来实现。

期间的参数值的返回问题也需要考虑，以免弄错了。

3、关于这次程序设计，我学到的还有很多，譬如说在先进先出（FIFO）算法中，如何通过“当某一页面进入内存时（包括页面置换时页面的置入），物理块中各页面访问标记自动加一，置换后，将置换页面所在的物理块中访问标记减一”的方法来防止当物理块访问标记出现两个以上相同的值的错误执行问题。

还有在最佳置换算法中对于不将来不再使用的页面，将其访问标记设置为1000的方法。

以及一些计算比如缺页率计算问题我也学习到了很多。

4、由于时间关系，对于一些细节问题我没有能够考虑好，比如说输入控制，以后一定做好。

5、通过本次的课程设计，我意识到了自己的编程能力还很差，以后必须通过练习来提高自己的能力。

另外，对于自己的思路老是打不开的问题，我认识到，这也是专业知识掌握的不够扎实，缺乏实际操作的问题。

以后我一定努力改正。

同时，我认识到了，