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

网络操作系统课 程 设 计 报 告 书题 目：请求调页存储管理方式的模拟 学 号： 学生姓名： 指导教师： 2010 年 12 月 10 日目录课程设计一：请求调页存储管理方式的模拟一、实验目的二、实验内容三、设计思路四、文件系统结构的说明五、数据结构的说明六、程序流程图七、源代码八、运行结果以及分析九、使用说明十、总结课程设计二：通过DNS协议，可实现IP地址和主机名之间的转换一、实验目的二、实验内容三、设计思路四、文件系统结构的说明五、源代码六、运行结果以及分析七、使用说明八、总结课程设计一一：实验目的1通过模拟实现请求页式存储管理的几种基本页面置换算法，了解虚拟储技术的特点。2通过对页面、页表、地址转换和页面置换过程的模拟，加深对请求调页系统的原理和实现过程的理解。3掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程，并比较它们的效率。二：实验内容1假设每个页面中可存放10条指令，分配给一个作业的内存块数为42用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、先进先出法（First In First Out） 3、最近最久未使用（Least Recently Used）。所谓最佳置换算法，就是其所选择的被淘汰页是将来不再被使用，或者是在最远的将来才被访问的页面。 采用这种页面置换算法， 保证有最少的缺页率。但由于目前还无法预知一个进程在内存的若干个页面中，哪个在最长的时间内不会被访问，因而，现实中该算法是无法实现的。因此在该算法的模拟过程中，页面访问次序必须是给定的，具体实现为：对每一个物理块设置一个整数型的访问标志位，当需要置换物理块中的某一页时，将每一个物理块中的页面号与当前需调入页以后的每一页面号进行比较，若物理块中的页面号与所有的页面号都不同，则该页即为将来不再使用的页，将访问标记设置为1000，表示将来不会用，设置为一个很大数；若找到页号相同的则将其访问次序记入访问标记，比较访问标记，最大的即为最久不会被访问的，将其换出。所谓先进先出法，就是总是淘汰最先进入内存的页面，既选择在内存中驻留时间最久的页面予以淘汰。在该算法的模拟过程中，每当某一页面进入内存时（包括页面置换时页面的置入），物理块中各页面访问标记自动加一，置换后，将置换页面所在的物理块中访问标记减一；这样能防止当物理块访问标记出现两个以上相同的值的错误执行，更好地模拟了先进先出法。所谓最近最久未使用，就是以最近的过去作为不久将来的近似， 将过去最长一段时间里不曾被使用的页面置换掉。在该算法的模拟过程中，每当物理块中的页面被访问时，便将其访问标记置为1。以后每执行一条指令，便将物理块中各页面的访问标记加一，需置换时访问标记最大的便是将要被置换的。四：文件系统结构的说明#include #include#include#include#define Bsize 4typedef struct BLOCK/声明一种新类型物理块类型 int pageNum;/页号 int accessed;/访问字段，其值表示多久未被访问BLOCK; int pc;/程序计数器，用来记录指令的序号int m;/缺页计数器，用来记录缺页的次数 static int random320;/用来存储320条随机数BLOCK blockBsize; /定义一大小为4的物理块数组void init( ); /程序初始化函数int findExist(int curpage);/查找物理块中是否有该页面int findSpace( );/查找是否有空闲物理块int findReplace( );/查找应予置换的页面void display ( );/显示void suijishu( );/产生320条随机数,显示并存储到random320void pagestring( );/显示调用的页面队列void OPT( );/OPT算法最佳置换算法void LRU( );/ LRU算法最近最久未使用算法void FIFO( );/FIFO算法五：数据结构的说明在本程序中，对于物理块使用了结构体。最后主函数通过依次调用三种算法函数来实现功能。头文件：#include #include#include#include#define Bsize 4物理块：typedef struct BLOCK/声明一种新类型物理块类型 int pageNum;/页号 int accessed;/访问字段，其值表示多久未被访问BLOCK; 六：程序流程图整体六：程序流程图LRU开始是得到执行指令是否是指令所在页是否在内存中否内存中是否有空闲物理块查找内存中accessed值最大的物理块，置换修改内存中该页所在的物理块的Accessed的值-1是修改内存中该页所在的物理块的Accessed的值-1输出该内存块的物理地址将所有物理块的accessed的值加1结束七：源代码#include #include#include#include#define Bsize 4typedef struct BLOCK/声明一种新类型物理块类型 int pageNum;/页号 int accessed;/访问字段，其值表示多久未被访问BLOCK; int pc;/程序计数器，用来记录指令的序号int m;/缺页计数器，用来记录缺页的次数 static int random320;/用来存储320条随机数BLOCK blockBsize; /定义一大小为4的物理块数组void init( ); /程序初始化函数int findExist(int curpage);/查找物理块中是否有该页面int findSpace( );/查找是否有空闲物理块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 findExist(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=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(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中的某条指令处，其序号为m2flag=+flag%4;/如果4个内存块中均已装入该作业，则需进行页面转换 printf( %03d,randomi); if(i+1)%10=0) coutendl;/每个页面中可存放10条指令 void pagestring( ) for(int i=0;i320;i+) printf( %02d,randomi/10);/显示该页面 if(i+1)%10=0) printf(n);/每个页面中可存放10条指令 void OPT( )/*OPT算法最佳置换算法.最佳置换算法是Blady在理论上提出的一种算法。其所选择的被淘汰页是将来不再被使用，或者是在最远的将 来才被访问的页面.采用这种页面置换算法， 保证有最少的缺页率。但由于目前还无法预知一个进程在内存的若干个页面中，哪个在最长的 时间内不会被访问，因而，现实中该算法是无法实现的。因此在该算法的模拟过程中，页面访问次序必须是给定的，具体实现为：对每一 物理块设置一个整数型的访问标志位，当需要置换物理块中的某一页时，将每一个物理块中的页面号与当前需调入页以后的每一页面号进行 比较，若物理块中的页面号与所有的页面号都不同，则该页即为将来不再使用的页，将访问标记设置为1000，表示将来不会用，设置为一个 很大数；若找到页号相同的则将其访问次序记入访问标记，比较访问标记，最大的即为最久不会被访问的，将其换出。*/ 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; 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; position = findReplace( ); blockposition.pageNum = curpage; display( );m+; printf(缺页次数:%dn,m);cout缺页率:(m/320.0)*100%endl;void LRU( )/*LRU算法最近最久未使用算法.该算法以最近的过去作为不久将来的近似， 将过去最长一段时间里不曾被使用的页面置换掉。在该算法的模拟过程中，每当物理块中的页面被访问时，便将其访问标记置为1以后每执行一条指令，便将物理块中各页面的访问标记加一，需置换时访问标记最大的便是将要被置换的。*/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.pageNum = curpage; display( );m+; else blockexist.accessed = -1;/恢复存在的并刚访问过的BLOCK中页面accessed为-1for(int j=0; j4; j+)blockj.accessed+;/每执行一条指令，便将物理块中各页面的访问标记加一 printf(缺页次数:%dn,m);cout缺页率:(m/320.0)*100%endl;void FIFO( )/*该算法总是淘汰最先进入内存的页面，既选择在内存中驻留时间最久的页面予以淘汰。在该算法的模拟过程中，每当某一页面进入内存时（包括页面置换时页面的置入），物理块中各页面访问标记自动加一，置换后，将置换页面所在的物理块中访问标记减一；这样能防止当物理块访问标记出现两个以上相同的值的错误执行，更好地模拟了先进先出法；*/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; else position = findReplace( ); blockposition.pageNum = curpage; display( );m+;blockposition.accessed-; for(int j=0; jBsize; j+) blockj.accessed+;/每当某一页面进入内存时（包括页面置换时页面的置入），物理块中各页面访问标记自动加一 printf(缺页次数:%dn,m);cout缺页率:(m/320.0)*100%endl;void main( ) int select;cout请输入第一条指令号(0320)：;suijishu( );cout-对应的调用页面队列-endl;pagestring( );do cout-endl;cout*endl;cout-1:OPT 2:LRU 3:FIFO 4:退出-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( );/输出结果break; default: ; while(select!=4);/每页分配4个内存块 八：运行结果及分析九：使用说明1、首先进入程序，在0320之间随意挑选一个数输入，按回车键。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) coutendl;flag=+flag%4;来实现。期间的参数值的返回问题也需要考虑，以免弄错了。3、关于这次程序设计，我学到的还有很多，譬如说在先进先出(FIFO)算法中，如何通过“当某一页面进入内存时（包括页面置换时页面的置入），物理块中各页面访问标记自动加一，置换后，将置换页面所在的物理块中访问标记减一”的方法来防止当物理块访问标记出现两个以上相同的值的错误执行问题。还有在最佳置换算法中对于不将来不再使用的页面，将其访问标记设置为1000的方法。以及一些计算比如缺页率计算问题我也学习到了很多。4、由于时间关系，对于一些细节问题我没有能够考虑好，比如说输入控制，以后一定做好。5、通过本次的课程设计，我意识到了自己的编程能力还很差，以后必须通过练习来提高自己的能力。另外，对于自己的思路老是打不开的问题，我认识到，这也是专业知识掌握的不够扎实，缺乏实际操作的问题。以后我一定努力改正。同时，我认识到了，程序设计，不仅仅要的是编程能力，对于设计全局的把握，整体的思考，以及算法的深入理解分析也是必不可少的，这也是我以后个人需要特别注意学习的地方。总之，通过这次的设计作业，我学习到了很多很多。课程设计二一：实验目的通过DNS协议，可实现IP地址和主机名之间的转换。通过该程序可以得到：(1)获取本机名(gethostname()函数)/(2)获得给定主机名的IP地址(gethostbyname()函数)(3)获得给定IP地址的主机名(gethostbyaddr()函数)二：实验内容设计一个简单的Winsock网络程序，模拟UDP数据报，加深对DNS作用的理解。三：设计思路1、启动 Visual C+，进入集成开发环境;2、建立一个“Win32 Console 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() WORD wVersionRequested=MAKEWORD(1,1); WSADATA wsaData;/初始化 windows sockets API/ if(WSAStartup(wVersionRequested,&wsaData) printf(WSAStartup failed%sn,WSAGetLastError(); return -1; char hostname256;/获得本主机名/ int res=gethostname(hostname,sizeof(hostname); if(res!=0)/错误处理/ printf(Error:%un,WSAGetLastError(); return -1; printf(本主机名为：%sn,hostname); /打印本主机名字/ printf(请输入一个主机域名:); /输入一个主机的域名/ scanf(%s,hostname);/利用主机名获得主机的地址/ hostent* pHostent=gethostbyname(hostname);