网络操作系统课程设计.doc

网络操作系统课 程 设 计 报 告 书题 目：请求调页存储管理方式的模拟 DNS协议模拟实现 学 号：081007111 2010 年 12 月 1 日目录 五、请求调页存储管理方式的模拟1 设计思想说明-32 文件系统结构的说明-43 数据结构的说明-54 各模块的算法流程图-55 程序清单：注意加注释-76 使用说明书-187 体会，建议-19七、DNS协议模拟实现 1 程序源码-202 操作步骤-223 运行结果-23 五、请求调页存储管理方式的模拟通过对页面、页表、地址转换和页面置换过程的模拟，加深对请求调页系统的原理和实现过程的理解。题目要求1假设每个页面中可存放10条指令，分配给作业的内存块数为4。2用C语言或C+语言模拟一个作业的执行过程，该作业共有320条指令，即它的地址空间为32页，目前它的所有页都还未调入内存。在模拟过程中，如果所访问的指令已在内存，则显示其物理地址，并转下一条指令。如果所访问的指令还未装入内存，则发生缺页，此时需记录缺页的次数，并将相应页调入内存。如果4个内存块均已装入该作业，则需进行页面置换，最后显示其物理地址，并转下一条指令。在所有320指令执行完毕后，请计算并显示作业运行过程中发生的缺页率。3置换算法：请分别考虑最佳置换算法（OPT）、先进先出（FIFO）算法和最近最久未使用（LRU）算法。4作业中指令的访问次序按下述原则生成；50%的指令是顺序执行的；25%的指令是均匀分布在前地址部分；25%的指令均匀分布在后地址部分。具体的实现办法是：（1）在0，319之间随机选取一条起始执行指令，其序号为m；（2）顺序执行下一条指令，其序号为m+1条指令；（3）通过随机数，跳转到前地址部分0，m-1中的某条指令处，其序号为m1；（4）顺序执行下一条指令，即序号为m1+1的指令；（5）通过随机数，跳转到后地址部分m1+2,319中的某条指令处，其序号为m2；（6）顺序执行下一条指令，则序号为m2+1的指令；（7）重复跳转到前地址部分，顺序执行，跳转到后地址部分；顺序执行的过程，直至执行320条指令。1 设计思路 在进程运行过程中，若其所要访问的页面不在内存时，需把它们调入内存，但内存已无空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据，送磁盘的对换区中。但应将哪个页面调出，所以需要根据一定的算法来确定。在这一过程中，选择换出页面的算法称为页面置换算法。一个好的页面置换算法，应具有较低的页面更换频率。页面置换算法的好坏，将直接影响到系统的性能。以下分别是实验要求的两个页面置换算法的介绍及其设计思想。（1）先进先出法该算法总是淘汰最先进入内存的页面，既选择在内存中驻留时间最久的页面予以淘汰。在该算法的模拟过程中，每当页面被置换进入内存时，将置换页面所在的物理块中访问标记设为-1；并且每执行一次指令，便将物理块的访问标记自动加1，需要置换时将访问标记最大的物理块中的页面置换出去，这样能防止当物理块访问标记出现两个以上相同的值的错误执行，更好地模拟了先进先出法；（2）最近最久未使用 该算法以最近的过去作为不久将来的近似， 将过去最长一段时间里不曾被使用的页面置换掉。在该算法的模拟过程中，每当物理块中的页面被访问时（包括原先存在的和后来置换进入的页面），便将其物理块访问标记置为1。以后每执行一条指令，便将物理块中各页面的访问标记加1，需置换时访问标记最大的便是将要被置换的。2文件系统结构的说明3数据结构的说明4各模块的算法流程图（1）整体流程图（2）LRU算法流程图（3）LRU算法流程图5 程序清单#include<iostream.h>#include<stdlib.h>#include<conio.h>#include<stdio.h>#define Bsize 4typedef struct BLOCK /声明一种新类型物理块类型 int pagenum; /页号int accessed; /访问标识符，其值表示多久未被访问BLOCK;int pc; /程序计数器，用来记录指令的序号int n; /缺页计数器，用来记录缺页的次数static int temp320; /用来存储320条随机数BLOCK blockBsize; /定义一大小为4的物理块数组/*void init(); /程序初始化函数int findExist(int curpage); /查找物理块中是否有该页面int findSpace(); /查找是否有空闲物理块int findReplace(); /查找应予置换的页面void display(); /显示void suijishu(); /产生320条随机数,显示并存储到temp320void pagestring(); /显示调用的页面队列void LRU(); / LRU算法void FIFO(); /FIFO算法/*void init() /初始化物理块 for(int i=0;i<Bsize;i+) blocki.pagenum=-1; /空闲物理块 blocki.accessed=0; pc=n=0; /-int findExist(int curpage) /查找物理块中是否有该页面 for(int i=0; i<Bsize; i+)if(blocki.pagenum = curpage ) return i; /检测到内存中有该页面，返回block中的位置 return -1; /没有则返回-1/-int findSpace() /查找是否有空闲物理块 for(int i=0; i<Bsize; i+) if(blocki.pagenum = -1) return i; /找到空闲的block，返回block中的位置 return -1; /找不到则返回-1/-int findReplace() /查找应予置换的页面 int pos = 0; for(int i=0; i<Bsize; i+) if(blocki.accessed >blockpos.accessed) pos = i; /找到应予置换页面，返回BLOCK中位置 return pos;/-void display(int space) /显示 for(int i=0; i<Bsize; i+) if(blocki.pagenum != -1) /物理块不空 printf(" %02d ",blocki.pagenum); cout<<"调入的页面是："<<blockspace.pagenum<<" 其物理块的地址是："<<&blockspace; cout<<endl;/-void suijishu(int pc) /产生随机数 int flag=0; cout<<"*按照要求产生的320个随机数：*"<<endl; for(int i=0;i<320;i+) tempi=pc;if(flag%2=0) pc=+pc%320; /产生50%的顺序执行指令（flag=0或2时顺序执行） if(flag=1) pc=rand()% (pc-1); /产生25%的均匀分布在前地址部分指令 if(flag=3) pc=pc+1+(rand()%(320-(pc+1); /产生25%的均匀分布在后地址部分指令 flag=+flag%4;printf(" %03d",tempi); if(i+1)%10=0) cout<<endl; /-void pagestring() /显示调用的页面队列 for(int i=0;i<320;i+) printf(" %02d",tempi/10); if(i+1)%10=0) cout<<endl;/-void LRU() / LRU算法（最近最少使用算法）int exist,space,position ;int curpage; for(int i=0;i<320;i+) if(i%100=0) getch(); /getch直接从键盘获取键值pc=tempi; /指令在数组中的位置 curpage=pc/10; /指令所在页面 exist = findExist(curpage); /查找物理块中是否有该页面,若有返回物理块号 if(exist=-1) /物理块中不存在该页space = findSpace(); /查找是否有空闲物理块 if(space != -1) /有空闲物理块blockspace.pagenum = curpage; display(space); n=n+1; else /无空闲物理块，则寻找置换页面 position = findReplace(); /查找应予置换的页面 blockposition.pagenum = curpage; blockposition.accessed = -1; /恢复刚调入的BLOCK中页面accessed为-1 display(position); n+; else blockexist.accessed = -1;/恢复存在的并刚访问过的BLOCK中页面accessed为-1for(int i=0; i<Bsize; i+) if(blocki.pagenum != -1) /物理块不空printf(" %02d ",blocki.pagenum);cout<<"指令已经存在！ 其物理块地址为："<<&blockexist<<endl; for(int j=0; j<4; j+) /物理块中各页面的访问标记加1 blockj.accessed+;cout<<"缺页次数:"<<n<<endl;cout<<"缺页率:"<<(n/320.0)*100<<"%"<<endl;/-void FIFO() /FIFO算法（先进先出算法）int exist,space,position ;int curpage; for(int i=0;i<320;i+) if(i%100=0) getch(); /getch直接从键盘获取键值pc=tempi; curpage=pc/10; exist = findExist(curpage); /查找物理块中是否有该页面 if(exist=-1) /物理块中不存在该页 space = findSpace(); /查找是否有空闲物理块 if(space != -1) /有空闲物理块blockspace.pagenum = curpage; display(space); n=n+1; else /无空闲物理块，则寻找置换页面 position = findReplace(); /查找应予置换的页面 blockposition.pagenum = curpage; display(position); n+; blockposition.accessed=-1; /置换页面所在的物理块中访问标记设为-1 else /若存在该页 for(int i=0; i<Bsize; i+) if(blocki.pagenum != -1) /物理块不空printf(" %02d ",blocki.pagenum);cout<<"指令已经存在！ 其物理块地址为："<<&blockexist<<endl; for(int j=0; j<Bsize; j+) /物理块中各页面访问标记自动加1 blockj.accessed+; cout<<"缺页次数:"<<n<<endl;cout<<"缺页率:"<<(n/320.0)*100<<"%"<<endl;/*void main() int select; cout<<"请输入第一条指令号(1319)：" cin>>pc; /随机选取一条起始执行指令 if(pc>=1&&pc<=319) suijishu(pc); /产生随机数 cout<<"*对应的调用页面队列*"<<endl; pagestring(); /显示调用的页面队列 do cout<<"*"<<endl; cout<<"-1:LRU 2:FIFO 3:退出 -"<<endl; cout<<"*"<<endl; cout<<" 请选择一种页面置换算法:" cin>>select; cout<<"*"<<endl; init(); switch(select) case 1:cout<<"最近最久未使用置换算法LRU:"<<endl; cout<<"*"<<endl; LRU(); break; case 2:cout<<"先进先出置换算法FIFO:"<<endl; cout<<"*"<<endl; FIFO(); break; default: ; while(select!=3); else cout<<"输入非法数据！"6使用说明书本程序能通过输入第一条指令号（用3位整数代表指令号），产生320个随机数，并以每行10个显示出来。再把这320个随机数转换成对应的页面号，并以每行10个显示出来。然后，通过输入选择键，分别执行两个置换算法。各个置换算法能显示页面置换的情况，如果所访问的指令已在内存，则显示“该指令已经存在”并显示其物理地址；如果所访问的指令还未装入内存，则显示“调入的页面是。”，并显示其调入后的物理地址。所有指令执行完毕后显示缺页次数，和缺页率。基本实现了对请求调页存储器管理方式的模拟。本程序的另一个亮点是使用getch( )使程序的执行过程能够暂停。本程序基本实现了实验要求，自我感觉程序不够精练，可读性不高，还要进一步改进。6. 运行结果及分析7体会，建议通过本次操作系统实验，使我们对操作系统这门课程有了更进一步的认识和了解，通过模拟实现请求页式存储管理的几种基本页面置换算法，了解虚拟储技术的特点。通过对页面、页表、地址转换和页面置换过程的模拟，加深对请求调页系统的原理和实现过程的理解。本实验的难点之一在于如何用c语言按要求模拟生成随机指令，即50%的指令是顺序执行的，25%的指令是均匀分布在前地址部分，25%的指令是均匀分布在后地址部分，小组花了大量时间讨论和研究该算法，并参考了相关的资料、运用了随机函数，最终通过一个函数suiji(int pc)予以实现。第二，如何较好地模拟出先进先出算法（FIFO）、最近最少使用算法（LRU）也花费了较多时间。在本次设计过程中，用到了许多C+的基本知识和操作系统的基本原理，是对平时所学知识的一次考验，尽管这些知识都学过，但运用到实际时，却不知从何下手，而且错误不断，往往为了找一个错误而花了大量的时间，这是专业知识掌握不够，缺乏实践动手能力的表现。在设计的过程中我们发现了许多自己的不足之处，对以前所学过的知识理解得不够深刻，掌握得不够牢固，以后还要多加努力。总之，通过该实验，我们了解到编写程序不是首要任务，而是一种实现手段。我们最重要的是如何做好需求分析和理清思路，做出正确、简洁的流程设计，这样可以达到事半功倍的效果。七、DNS协议模拟实现DNS协议为应用层协议，可实现IP地址和主机名之间的转换。参考程序如下：1程序源代码：#include<winsock.h>#include<stdio.h>#include<string.h> #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); if(pHostent=NULL)/错误处理/ printf("Error：%un",WSAGetLastError(); return -1; /解析返回的主机地址信息：别名、地址类型、地址长度，并打印/ hostent& he=*pHostent; printf("name=%snaliase=%snaddrtype=%dnlength=%dn",he.h_name,he.h_aliases,he.h_addrtype,he.h_length); sockaddr_in sa;/打印主机每一个网卡的 IP地址/ for (int nAdapter=0; he.h_addr_listnAdapter; nAdapter+) memcpy(&sa.sin_addr.s_addr,he.h_addr_listnAdapter,he.h_length); printf("Address：%sn",inet_ntoa(sa.sin_addr); /显示 lP地址/ printf("n"); unsigned long addr; char hostaddr50; printf("请输人服务器IP地址："); /输入一个服务器的IP地址/ scanf("%s",hostaddr); addr=inet_addr(hostaddr); /将 lP地址转化为网络字节序/ pHostent=gethostbyaddr(char *)&addr,4,AF_INET); /利用IP地址获得主机名人/ if(pHostent=NULL)/错误处理/ printf("Error：%un",WSAGetLastError(); return -1; hostent& hel=*pHostent; printf("主机名为;%snaliases=%snaddrtype=%dnlength=%dn",he.h_name,he.h_aliases,he.h_addrtype,he.h_length); /打印返回的主机信息/ WSACleanup(); /结束windows sockets API/ return 0; 2操作步骤：1输入百度主机域名：2 输入百度服务器地址：61.135.169.105得到主机名:3 运行结果