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

1、请求调页存储管理方式的模拟网络操作系统课程设计报告书题目：请求调页存储管理方式的模拟学号：学生姓名：指导教师：2010年 12月10日课程设计二：通过DNS协议，可实现 IP 地址和主机名之间的转换一、实验目的二、实验内容三、设计思路四、文件系统结构的说明五、源代码六、运行结果以及分析七、使用说明八、总结课程设计一一：实验目的1通过模拟实现请求页式存储管理的几种基本页面置换算法，了解虚拟储技术的特点。2通过对页面、页表、地址转换和页面置换过程的模拟，加深对请求调页系统的原理和实现过程的理解。3掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程， 并比较它们的效率。二：实验内

2、容1假设每个页面中可存放 10 条指令，分配给一个作业的内存块数为 42用 C 语言模拟一作业的执行过程。该作业共有 320 条指令，即它的地址空间为 32 页，目前它的所有页都还未调入内存。 在模拟过程中， 如果访问的指令已在内存， 则显示其物理地址， 并转下一条指令。如果所访问的指令还未装入内存，则发生缺页，此时需记录缺页的次数，并将相应页调入内存。 如果 4 个内存块中均已装入该作业，则需进行页面转换。最后显示其物理地址，并转下一条指令。在所有 320 条指令执行完毕后，请计算并显示作业运行过程中发生的缺页率。3置换算法：请分别考虑 OPT 、FIFO 和 LRU 算法。4作业中指令的访

3、问次序按下述原则生成：50% 的指令是顺序执行的25% 的指令是均匀分布在前地址部分25% 的指令是均匀分布在后地址部分具体的实施办法：在 0,319之间随机选取一条起始指令，其序号为 m顺序执行下一条指令，即序号为 m+1 的指令通过随机数， 跳转到前地址部分 0,m-1 中的某条指令处，其序号为 m1；顺序执行下一条指令， 即序号为 m1+1 的指令通过随机数，跳转到后地址部分 m1+2,319中的某条指令处，其序号为 m2; 顺序执行下一条指令， 即序号为 m2+1 的指令重复跳转到前地址部分、 顺序执行、跳转到后地址部分、顺序执行的过程， 直至执行 320 条指令。三：设计思路因为在程

4、序运行的过程中， 当我们访问一个页面时，倘若此页面不在内存当中， 我们就需要将其调入内存。此时就产生了两个问题： 内存是否有空闲和倘若内存有空闲我们要将那个页面调出的问题。这样的话就需要根据一定的算法来判断决定。我们大家都知道， 算法的好坏反映在程序执行的效率上面， 所以我们要根据不同的情况调用不同的算法。这里我们有三种置换算法： 1 最佳置换算法（Optimal ） 2、先进先出法（First In First Out ） 3、最近最久未使用 （Least RecentlyUsed）。所谓最佳置换算法，就是其所选择的被淘汰页是将来不再被使用， 或者是在最远的将来才被访问的页面。 采用这种页面

5、置换算法， 保证有最少的缺页率。 但由于目前还无法预知一个进程在内存的若干个页面中， 哪个在最长的时间内不会被访问， 因而，现实中该算法是无法实现的。因此在该算法的模拟过程中， 页面访问次序必须是给定的， 具体实现为： 对每一个物理块设置一个整数型的访问标志位， 当需要置换物理块中的某一页时，将每一个物理块中的页面号与当前需调入页以后的每一页面号进行比较， 若物理块中的页面号与所有的页面号都不同， 则该页即为将来不再使用的页，将访问标记设置为 1000，表示将来不会用， 设置为一个很大数； 若找到页号相同的则将其访问次序记入访问标记， 比较访问标记，最大的即为最久不会被访问的， 将其换出。所谓

6、先进先出法， 就是总是淘汰最先进入内存的页面，既选择在内存中驻留时间最久的页面予以淘汰。在该算法的模拟过程中， 每当某一页面进入内存时（包括页面置换时页面的置入） ，物理块中各页面访问标记自动加一， 置换后，将置换页面所在的物理块中访问标记减一； 这样能防止当物理块访问标记出现两个以上相同的值的错误执行， 更好地模拟了先进先出法。 所谓最近最久未使用，就是以最近的过去作为不久将来的近似， 将过去最长一段时间里不曾被使用的页面置换掉。 在该算法的模拟过程中， 每当物理块中的页面被访问时， 便将其访问标记置为 1。以后每执行一条指令， 便将物理块中各页面的访问标记加一，需置换时访问标记最大的便是将

7、要被置换的。四：文件系统结构的说明#include #include#include#include#define Bsize 4typedef struct BLOCK/ 声明一种新类型物理块类型int pageNum;/ 页号int accessed;/访问字段，其值表示多久未被访问BLOCK;int pc;/ 程序计数器，用来记录指令的序号 int m;/ 缺页计数器，用来记录缺页的次数static int random320;/BLOCKblockBsize;用来存储 320 条随机数/定义一大小为 4 的物理块数组void init( );/程序初始化函数int findExist(

8、int curpage);/ 查找物理块中是否有该页面int findSpace( );/ 查找是否有空闲物理块 int findReplace( );/ 查找应予置换的页面void display ( );/ 显示void suijishu( );/产生 320 条随机数 ,显示并存储到 random320void pagestring( );/ 显示调用的页面队列void OPT( );/OPT算法最佳置换算法void LRU( );/ LRU算法最近最久未使用算法void FIFO( );/FIFO算法五：数据结构的说明在本程序中， 对于物理块使用了结构体。 最后主函数通过依次调用三种算

9、法函数来实现功能。头文件： #include #include#include#include#define Bsize 4物理块：typedef struct BLOCK/ 声明一种新类型物理块类型int pageNum;/ 页号int accessed;/访问字段，其值表示多久未被访问BLOCK;六：程序流程图整体开始接收键盘输入的数值提示输入数否判断输入值是据非法否在 1319是六：程序流程图 LRU开始是得到是是指令所修改内查找内存中该存中修 改 内存 中 该输出该内将所有物理 块 的结束否否内存中是七：源代码#include #include#include#include#defi

10、ne Bsize 4typedef struct BLOCK/ 声明一种新类型物理块类型int pageNum;/ 页号int accessed;/访问字段，其值表示多久未被访问BLOCK;int pc;/ 程序计数器，用来记录指令的序号 int m;/ 缺页计数器，用来记录缺页的次数static int random320;/BLOCKblockBsize;用来存储 320 条随机数/定义一大小为 4 的物理块数组void init( );/程序初始化函数int findExist(int curpage);/ 查找物理块中是否有该页面int findSpace( );/ 查找是否有空闲物理

11、块 int findReplace( );/ 查找应予置换的页面void display ( );/ 显示void suijishu( );/产生 320 条随机数 ,显示并存储到 random320void pagestring( );/ 显示调用的页面队列void OPT( );/OPT算法最佳置换算法void LRU( );/ LRU算法最近最久未使用算法void FIFO( );/FIFO算法void init( ) / 程序初始化函数for(int i=0;iBsize;i+)blocki.pageNum=-1;blocki.accessed=0;pc=m=0;int findExi

12、st(int curpage)/ 查找物理块中是否有该页面for(int i=0; iBsize; i+)if(blocki.pageNum = curpage ) return i;/ 检测到内存中有该页面，返回 block 中的位置return -1;int findSpace( )/ 查找是否有空闲物理块for(int i=0; iBsize; i+)if(blocki.pageNum = -1)return i;/ 找到空闲的 block ，返回 block中的位置return -1;int findReplace( )/ 查找应予置换的页面int pos = 0;for(int i=

13、0; iblockpos.accessed) pos = i;/ 找到应予置换页面，返回BLOCK 中位置return pos;void display( )for(int i=0; iBsize; i+)if(blocki.pageNum != -1)printf( %02d,blocki.pageNum);coutendl;void suijishu( ) int flag=0;printf( 请输入一个0320 之间的随机数：n);scanf(%d,&pc);printf(-按照要求产生的320 个随机数： -n);for(int i=0;i320;i+)randomi=pc;if(fl

14、ag%2=0)pc=+pc%320;/顺序执行下一条指令，即序号为 m+1 的指令 if(flag=1) pc=rand( )% (pc-1);/ 通过随机数，跳转到前地址部分 0,m-1 中的某条指令处，其序号为 m1if(flag=3)pc=pc+1+(rand( )%(320-(pc+1);/通过随机数，跳转到后地址部分m1+2,319中的某条指令处，其序号为 m2flag=+flag%4;/ 如果 4 个内存块中均已装入该作业，则需进行页面转换printf( %03d,randomi);if(i+1)%10=0)coutendl;/ 每个 页面中可存放 10 条指令void pages

15、tring( )for(int i=0;i320;i+)printf(%02d,randomi/10);/显示该页面if(i+1)%10=0) printf(n);/ 每个页面中可存放 10 条指令void OPT( )/*OPT 算法最佳置换算法 .最佳置换算法是 Blady 在理论上提出的一种算法。 其所选择的被淘汰页是将来不再被使用， 或者是在最远的将来才被访问的页面 .采用这种页面置换算法， 保证有最少的缺页率。但由于目前还无法预知一个进程在内存的若干个页面中， 哪个在最长的时间内不会被访问，因而，现实中该算法是无法实现的。因此在该算法的模拟过程中，页面访问次序必须是给定的， 具体实现

16、为： 对每一物理块设置一个整数型的访问标志位，当需要置换物理块中的某一页时， 将每一个物理块中的页面号与当前需调入页以后的每一页面号进行比较，若物理块中的页面号与所有的页面号都不同， 则该页即为将来不再使用的页， 将访问标记设置为 1000，表示将来不会用，设置为一个很大数；若找到页号相同的则将其访问次序记入访问标记， 比较访问标记， 最大的即为最久不会被访问的，将其换出。*/int exist,space,position ;int curpage;for(int i=0;i320;i+)if(i%100=0) getch( );pc=randomi;curpage=pc/10;exist

17、= findExist(curpage);if(exist=-1)space = findSpace ( );if(space != -1)blockspace.pageNum=curpage;display( );m=m+1;else for(int k=0;kBsize;k+)for(int j=i;j320;j+)if(blockk.pageNum!=randomj/10)/ 物理块中的页面号与所有的页面号都不同blockk.accessed= 1000;/ 将来不会用，设置为一个很大数else/找到页号相同的则将其访问次序记入访问标记blockk.accessed=j;break;po

18、sition=findReplace( );blockposition.pageNum = curpage;display( );m+;printf( 缺页次数 :%dn,m);cout缺页率:(m/320.0)*100%endl;void LRU()/*LRU 算法最近最久未使用算法.该算法以最近的过去作为不久将来的近似，将过去最长一段时间里不曾被使用的页面置换掉。在该算法的模拟过程中， 每当物理块中的页面被访问时，便将其访问标记置为 1以后每执行一条指令， 便将物理块中各页面的访问标记加一，需置换时访问标记最大的便是将要被置换的。*/int exist,space,position ;in

19、t curpage;for(int i=0;i320;i+)if(i%100=0) getch( );pc=randomi;curpage=pc/10;/ 每页十个指令exist = findExist(curpage);if(exist=-1)space = findSpace( );if(space != -1)blockspace.pageNum=curpage;display( );m=m+1;elseposition = findReplace( );blockposition.pageNum=curpage;display( );m+;else blockexist.accesse

20、d = -1;/ 恢复存在的并刚访问过的BLOCK 中页面 accessed为-1for(int j=0; j4; j+)blockj.accessed+;/ 每 执 行 一 条 指令，便将物理块中各页面的访问标记加一printf( 缺页次数 :%dn,m);cout缺页率:(m/320.0)*100%endl;void FIFO()/* 该算法总是淘汰最先进入内存的页面，既选择在内存中驻留时间最久的页面予以淘汰。在该算法的模拟过程中， 每当某一页面进入内存时（包括页面置换时页面的置入） ，物理块中各页面访问标记自动加一，置换后，将置换页面所在的物理块中访问标记减一； 这样能防止当物理块访问标

21、记出现两个以上相同的值的错误执行，更好地模拟了先进先出法；*/int exist,space,position ;int curpage;for(int i=0;i320;i+)if(i%100=0) getch( );pc=randomi;curpage=pc/10;exist = findExist(curpage);if(exist=-1)space = findSpace( );if(space != -1)blockspace.pageNum=curpage;display( );m=m+1;elseposition = findReplace( );blockposition.pa

22、geNum=curpage;display( );m+;blockposition.accessed-;for(int j=0; jBsize; j+)blockj.accessed+;/ 每当某一页面进入内存时（包括页面置换时页面的置入） ，物理块中各页面访问标记自动加一printf( 缺页次数 :%dn,m);cout缺页率:(m/320.0)*100%endl;void main( )intselect;cout 请输入第一条指令号 (0320)：;suijishu( );cout-对 应 的 调 用 页 面 队 列-endl;pagestring( );docout-endl;cout

23、* *endl;cout-1:OPT2:LRU3:FIFO4:退出 -endl;cout* *endl;cout-endl;coutselect;cout-endl;init( );switch(select)case 1:printf( 您选择的是最佳置换算法 OPT:n);printf(-n);OPT( );/ 输出结果break;case 2:printf( 您选择的是最近最久未使用置换算法 LRU:n);printf(-n);LRU( );/ 输出结果break;case 3:printf(您选择的是先进先出置换算法 FIFO:n);printf(-n);FIFO( );/ 输出结果b

24、reak;default: ;while(select!=4);/ 每页分配 4 个内存块八：运行结果及分析九：使用说明1、首先进入程序，在 0320 之间随意挑选一个数输入，按回车键。2、程序产生 320 个随机数。3、开始选择一种置换算法进行页面的置换。输入置换算法前面的数字，回车。4、回车，得到置换算法的结果。5、换做其他的算法，依然回车，得到置换算法的结果。6、完成后选择退出。 。十：总结1、通过这次操作系统课程设计的编写，我学到了很多。刚开始见到设计要求时， 我有点没有思路。通过从网上参考了一些资料以后， 我开始慢慢的了解了程序设计中的一些问题。 首先：我对OPT 、FIFO 和 L

25、RU 算法三种算法有了一定的了解。其次，在分析题目要求的时候，对于如何将作业中指令的访问次序按一定原则生成的问题我没有一点思路。 最后，在仔细的看了一些类似的题目代码以后， 我终于有了一定的理解。 原来在实现的时候，通过先顺序执行一条随机指令，譬如该指令为 M0 ，然后开始顺序执行下一条指令 M0+1 ，紧接着通过跳转函数跳转到地址部分 0，M-1 中的某条指令处，其序号记为 M1 ，然后再次顺序执行下一条指令，即序号为 M1+1 的指令，最后通过跳转函数跳转到地址部分M1+2,319中的某条指令处， 其序号为 M2, ，然后通过重复执行跳转到前址， 顺序执行，跳转到后址，顺序执行的方法实现了

26、 50% 的指令是顺序执行的； 25% 的指令是均匀分布在前地址部分； 25% 的指令是均匀分布在后地址部分的目的。其中跳转函数上我复习了以前的rand 函数。2、其次，在实现设计要求功能的时候，对于那些页面跳转，页面置换的细节内容通过使用 if(i+1)%10=0) coutendl;flag=+flag%4;来实现。期间的参数值的返回问题也需要考虑，以免弄错了。3、关于这次程序设计，我学到的还有很多，譬如说在先进先出 (FIFO) 算法中，如何通过“当某一页面进入内存时（包括页面置换时页面的置入），物理块中各页面访问标记自动加一，置换后，将置换页面所在的物理块中访问标记减一”的方法来防止当

27、物理块访问标记出现两个以上相同的值的错误执行问题。 还有在最佳置换算法中对于不将来不再使用的页面， 将其访问标记设置为 1000 的方法。以及一些计算比如缺页率计算问题我也学习到了很多。4、由于时间关系，对于一些细节问题我没有能够考虑好，比如说输入控制，以后一定做好。5、通过本次的课程设计，我意识到了自己的编程能力还很差，以后必须通过练习来提高自己的能力。另外，对于自己的思路老是打不开的问题，我认识到，这也是专业知识掌握的不够扎实， 缺乏实际操作的问题。以后我一定努力改正。 同时，我认识到了，程序设计，不仅仅要的是编程能力，对于设计全局的把握， 整体的思考， 以及算法的深入理解分析也是必不可少

28、的， 这也是我以后个人需要特别注意学习的地方。 总之，通过这次的设计作业，我学习到了很多很多。课程设计二一：实验目的通过 DNS协议，可实现 IP 地址和主机名之间的转换。通过该程序可以得到：(1)获取本机名 (gethostname()函数 )/(2)获得给定主机名的IP 地址 (gethostbyname()函数 )(3)获得给定 IP 地址的主机名 (gethostbyaddr() 函数)二：实验内容设计一个简单的 Winsock 网络程序，模拟 UDP 数据报，加深对 DNS 作用的理解。三：设计思路1、启动Visual C+ ，进入集成开发环境 ;2、建立一个“ Win32 Cons

29、ole Application类型的工程，工程名自拟 ;3、在该工程下，新建一个源程序文件，即选择“C+ SourceFile ，文件名自拟 ;4、输入以下源程序 (注释部分可不必输入 );四：文件系统结构的说明#include#include#include#pragma comment(lib,ws2_32.lib)五：源代码#include#include#include#pragma comment(lib,ws2_32.lib)/主文件 /int main()WORDwVersionRequested=MAKEWORD(1,1);WSADATAwsaData;/初始化windows

30、sockets API/if(WSAStartup(wVersionRequested,&wsaData)printf(WSAStartupfailed%sn,WSAGetLastError(); return -1;char hostname256;/ 获得本主机名 / intres=gethostname(hostname,sizeof(hostname);if(res!=0)/ 错误处理 /printf(Error:%un,WSAGetLastError();return -1;printf( 本主机名为： %sn,hostname);/打印本主机名字 /printf( 请输入一个主机域名 :); /输入一个主机的域名 /scanf(%s,hostname);/ 利用主机名获得