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

《网络操作系统》课程设计报告书题目：请求调页存储管理方式的模拟学号：学生姓名：指导教师：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、先进先出法（FirstInFirstOut）3、最近最久未使用（LeastRecentlyUsed）。所谓最佳置换算法，就是其所选择的被淘汰页是将来不再被使用，或者是在最远的将来才被访问的页面。采用这种页面置换算法，保证有最少的缺页率。但由于目前还无法预知一个进程在内存的若干个页面中，哪个在最长的时间内不会被访问，因而，现实中该算法是无法实现的。因此在该算法的模拟过程中，页面访问次序必须是给定的，具体实现为：对每一个物理块设置一个整数型的访问标志位，当需要置换物理块中的某一页时，将每一个物理块中的页面号与当前需调入页以后的每一页面号进行比较，若物理块中的页面号与所有的页面号都不同，则该页即为将来不再使用的页，将访问标记设置为1000，表示将来不会用，设置为一个很大数；若找到页号相同的则将其访问次序记入访问标记，比较访问标记，最大的即为最久不会被访问的，将其换出。所谓先进先出法，就是总是淘汰最先进入内存的页面，既选择在内存中驻留时间最久的页面予以淘汰。在该算法的模拟过程中，每当某一页面进入内存时（包括页面置换时页面的置入），物理块中各页面访问标记自动加一，置换后，将置换页面所在的物理块中访问标记减一；这样能防止当物理块访问标记出现两个以上相同的值的错误执行，更好地模拟了先进先出法。所谓最近最久未使用，就是以最近的过去作为不久将来的近似，将过去最长一段时间里不曾被使用的页面置换掉。在该算法的模拟过程中，每当物理块中的页面被访问时，便将其访问标记置为－1。以后每执行一条指令，便将物理块中各页面的访问标记加一，需置换时访问标记最大的便是将要被置换的。四：文件系统结构的说明#includeiostream.h#includestdlib.h#includeconio.h#includestdio.h#defineBsize4typedefstructBLOCK//声明一种新类型——物理块类型{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算法五：数据结构的说明在本程序中，对于物理块使用了结构体。最后主函数通过依次调用三种算法函数来实现功能。头文件：#includeiostream.h#includestdlib.h#includeconio.h#includestdio.h#defineBsize4物理块：typedefstructBLOCK//声明一种新类型——物理块类型{intpageNum;//页号intaccessed;//访问字段，其值表示多久未被访问}BLOCK;六：程序流程图——整体开始接收键盘输入的数值判断输入值是否在1~319得到指令执行的顺序输出指令执行顺序和页面调用顺序是提示输入数据非法否选择页面调度算法调用LRU算法1调用FIFO算法2结束3六：程序流程图——LRU开始得到执行指令指令所在页是否在内存中修改内存中该页所在的物理块的Accessed的值-1查找内存中accessed值最大的物理块，置换内存中是否有空闲物理块修改内存中该页所在的物理块的Accessed的值-1输出该内存块的物理地址将所有物理块的accessed的值加1结束是否是否是是七：源代码#includeiostream.h#includestdlib.h#includeconio.h#includestdio.h#defineBsize4typedefstructBLOCK//声明一种新类型——物理块类型{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;iBsize;i++){block[i].pageNum=-1;block[i].accessed=0;pc=m=0;}}intfindExist(intcurpage)//查找物理块中是否有该页面{for(inti=0;iBsize;i++){if(block[i].pageNum==curpage)returni;//检测到内存中有该页面，返回block中的位置}return-1;}intfindSpace()//查找是否有空闲物理块{for(inti=0;iBsize;i++){if(block[i].pageNum==-1)returni;//找到空闲的block，返回block中的位置}return-1;}intfindReplace()//查找应予置换的页面{intpos=0;for(inti=0;iBsize;i++){if(block[i].accessedblock[pos].accessed)pos=i;//找到应予置换页面，返回BLOCK中位置}returnpos;}voiddisplay(){for(inti=0;iBsize;i++){if(block[i].pageNum!=-1){printf(%02d,block[i].pageNum);}}coutendl;}voidsuijishu(){intflag=0;printf(请输入一个0~320之间的随机数：\n);scanf(%d,&pc);printf(-------按照要求产生的320个随机数：-------\n);for(inti=0;i320;i++){random[i]=pc;if(flag%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,random[i]);if((i+1)%10==0)coutendl;//每个页面中可存放10条指令}}voidpagestring(){for(inti=0;i320;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;i32