操作系统课程设计说明书 -基于Linux的模拟存储器管理的设计与实现

操作系统课程设计说明书学院、系：软件学院专业软件工程设计题目：基于Linux的模拟存储器管理的设计与实现需求分析设计目的存储器管理是操作系统的重要功能之一，其中的页面置换算法是虚拟存储管理实现的关键，通过本次实验理解内存页面调度的机制，在模拟实现FIFO、LRU、NRU和OPT几种经典页面置换算法的基础上，比较各种置换算法的效率和优缺点，从而了解虚拟存储实现的过程。设计内容和要求在内存开辟两块存储空间，分别模拟内存和外存，大小分别是8M，25M。给定三个文件A，B，C，大小分别是4.2M，8M和9.8M。模拟其并发执行过程。每个进程在内存中固定分配4个页面，缺页时分别采用四种置换算法（FIFO,LRU,NUR,OPT）进行置换。假定页面大小为512K，进程执行时页面调度顺序要求手动输入。可以在屏幕上输出各进程页面置换过程（以图表形式描述）以及每种页面置换算法的缺页率和置换率，并对比各算法的优劣。要求在Linux平台下，使用C语言进行开发。总体设计程序的主框架采用数组的方式来实现，每个进程在内存里分配的4个页面就是是个一个数组的4个数，然后用二维数组是，第一维表示这个数组中包含的数，而第二维则是实现了一个计数的功能，每个算法中的作用基本相同。输入的序列也作为一个数组来实现的（由于不会使用动态的数组，在使用的时候还需要输入序列的个数，然后系统会分别提示输入序列中的第一个数）置换算法FIFO算法是先调入内存的页，先被置换出去。我们用数组P[]来代表内存中的4个块。输入的序列存放在一个数组Xulie[]中，当执行一个页面的时候，先检测此页面是否在内存中，假如存在，给出提示；假如不在，将4个页面依次的调入内存中或者将4个块依次置换。定义了一个用于的计数的变量x,用x=(x+1)%4用实现4个内存块的循环置换，实现了FIFO算法。LRU算法是最佳最久未使用，即前边最近未被使用的页面优先被置换出去。我们用了二维p[][2]来代表内存中的4个块，p[][0]代表页面，p[][1]代表一个计数，4个内存块的计数初始为0，1，2，3，当执行一个页面的时候，就将代表那个页面的计数总体加1，以此来标记最近最久未使用的页面OPT算法是最佳转换算法，即向后看，最将要使用的页面优先被转换出去。我们用数组P[][2]来代表内存中的4个块，P[][0]代表页面，P[][1]存在两种状态0，1，初始为0，当要置换页面的时候检测后面的页面序列，当检测到其中的一个页面的时候就将那个页面的块的计数变为1，直到检测出其中的三个页面或者将整个页面序列都检测完，就将最前边计数为0的页面置换出去。NUR算法。我们用数组P[][2]来代表内存中的4个块，P[][0]代表页面，P[][1]存在两种状态0，1，初始为0，当执行完一个一个页面后，就将此页面块的计数变为1，每执行4个页面就将其初始化为0，当置换页面时就将最前边计数为0的页面置换。3．详细设计FIFO置换算法模块voidFRun(intn,intX[]){floatqueyelv,zhihuanlv;inti,j,x;intP[4]={0,0,0,0};intqueye=0;intzhihuan=0;x=0;for(i=0;i<n;i++){if((P[0]==X[i])||(P[1]==X[i])||(P[2]==X[i])||(P[3]==X[i])){printf("执行的%d号页面在内存中\n",X[i]);}else{if(P[x]==0){printf("将第%d号页面调入内存",X[i]);queye++;}else{printf("将%d号页面置换为%d号页面",P[x],X[i]);zhihuan++;queye++;}P[x]=X[i];x=(x+1)%4;printf("%d%d%d%d\n",P[0],P[1],P[2],P[3]);}}printf("本次执行过程缺页次数为%d，置换次数为%d\n",queye,zhihuan);queyelv=(float)queye/n;zhihuanlv=(float)zhihuan/n;printf("本次执行的缺页率为%f,置换率为%f\n",queyelv,zhihuanlv);}NUR置换算法模块voidNRun(intn,intX[]){inti,j,cunzai;floatzhihuanlv,queyelv;intmange=0;intqueye=0;intzhihuan=0;inta=0;intP[4][2]={{0,0},{0,0},{0,0},{0,0}};for(i=0;i<n;i++){cunzai=0;if(i%4==0){P[0][1]=0;P[1][1]=0;P[2][1]=0;P[3][1]=0;}for(j=0;j<4;j++){if(P[j][0]==X[i]){printf("要执行的%d号页面在内存中\n",X[i]);P[j][1]=1;cunzai=1;}}if(cunzai==0){if(mange<4){printf("将%d号页面调入内存中",X[i]);P[mange][0]=X[i];P[mange][1]=1;mange++;queye++;}else{if(P[0][1]==0)a=0;else{if(P[1][1]==0)a=1;else{if(P[2][1]==0)a=2;else{if(P[3][1]==0)a=3;}}}printf("将%d页置换为%d页",P[a][0],X[i]);P[a][0]=X[i];P[a][1]=1;queye++;zhihuan++;}printf("%d%d%d%d\n",P[0][0],P[1][0],P[2][0],P[3][0]);}}printf("本次执行过程缺页次数为%d，置换次数为%d\n",queye,zhihuan);queyelv=(float)queye/n;zhihuanlv=(float)zhihuan/n;printf("本次执行的缺页率为%f,置换率为%f\n",queyelv,zhihuanlv);}LRU置换算法模块voidLRun(intn,intX[]){floatqueyelv,zhihuanlv;intj,i,q;intqueye=0;intzhihuan=0;intP[4][2]={{0,0},{0,1},{0,2},{0,3}};intm=3;intcunzai;for(i=0;i<n;i++){cunzai=0;for(j=0;j<4;j++){if(P[j][0]==X[i]){printf("要执行的%d号页面在内存中\n",X[i]);m++;P[j][1]=m;cunzai=1;}}if(cunzai==0){q=Bijiao(P[0][1],P[1][1],P[2][1],P[3][1]);if(P[q][1]<4){printf("将%d号页面调入内存中",X[i]);queye++;}if(P[q][1]>=4){printf("将%d号页面置换为%d号页面",P[q][0],X[i]);queye++;zhihuan++;}P[q][0]=X[i];m++;P[q][1]=m;printf("%d%d%d%d\n",P[0][0],P[1][0],P[2][0],P[3][0]);}}printf("本次执行缺页次数为%d，置换次数为%d\n",queye,zhihuan);queyelv=(float)queye/n;zhihuanlv=(float)zhihuan/n;printf("本次执行的缺页率为%f,置换率为%f\n",queyelv,zhihuanlv);}intBijiao(inta,intb,intc,intd){intm,n,x;if(a>b)m=b;elsem=a;if(c>d)n=d;elsen=c;if(m>n)x=n;elsex=m;if(x==a)return0;if(x==b)return1;if(x==c)return2;if(x==d)return3;}OPT置换算法模块voidORun(intn,intX[]){floatqueyelv,zhihuanlv;inti,j,cunzai;intshu;intmange=0;inta=0;intqueye=0;intzhihuan=0;intP[4][2]={{0,0},{0,0},{0,0},{0,0}};for(i=0;i<n;i++){P[0][1]=0;P[1][1]=0;P[2][1]=0;P[3][1]=0;shu=0;cunzai=0;if((P[0][0]==X[i])||(P[1][0]==X[i])||(P[2][0]==X[i])||(P[3][0]==X[i])){printf("要执行的%d号页面在内存中\n",X[i]);cunzai=1;}if(cunzai==0){if(mange<4){printf("将%d号页面调入内存中",X[i]);P[mange][0]=X[i];mange++;queye++;}else{j=i+1;while(shu<3){if(P[0][1]==0){if(P[0][0]==X[j]){P[0][1]=1;shu++;}}if(P[1][1]==0){if(P[1][0]==X[j]){P[1][1]=1;shu++;}}if(P[2][1]==0){if(P[2][0]==X[j]){P[2][1]=1;shu++;}}if(P[3][1]==0){if(P[3][0]==X[j]){P[3][1]=1;shu++;}}j++;if(j==n)break;}if(P[0][1]==0)a=0;else{if(P[1][1]==0)a=1;else{if(P[2][1]==0)a=2;else{if(P[3][1]==0)a=3;}}}printf("将%d号页面置换为%d号页面",P[a][0],X[i]);P[a][0]=X[i];queye++;zhihuan++;}printf("%d%d%d%d\n",P[0][0],P[1][0],P[2][0],P[3][0]);}}printf("本次执行缺页次数为%d，置换次数为%d\n",queye,zhihuan);queyelv=(float)queye/n;zhihuanlv=(float)zhihuan/n;printf("本次执行的缺页率为%f,置换率为%f\n",queyelv,zhihuanlv);}主模块voidmain(){intg,x,z,Acaozuo,Bcaozuo,Ccaozuo,Ashu,Bshu,Cshu;intAxulie[100],Bxulie[100],Cxulie[100];printf("----------------------------------\n");printf("^_^存储器管理模拟系统^_^\n");printf("----------------------------------\n");printf("---提示：本系统共执行3个文件进程---\n---A进程有9个页面---\n---B进程有16个页面---\n---C进程有20个页面---\n");printf("---四种调度算法模拟:---\n");printf("---操作号算法---\n");printf("---1先进先出算法---\n---2最近最久未使用算法---\n---3最佳置换算法---\n---4NUR算法---\n");printf("----------------------------------\n");printf("----------------------------------\n");printf("请输入A文件序列的个数：");scanf("%d",&Ashu);printf("请输入A文件进程的调度序列（1—9号）\n");for(g=0;g<Ashu;g++){do{printf("请输入第%d个序列号",g+1);scanf("%d",&Axulie[g]);}while((Axulie[g]<1)||(Axulie[g]>9));}do{printf("请输入执行A文件的调度算法操作号\n操作号：");scanf("%d",&Acaozuo);}while((Acaozuo!=1)&&(Acaozuo!=2)&&(Acaozuo!=3)&&(Acaozuo!=4));printf("----------------------------------\n");printf("请输入B文件序列的个数：");scanf("%d",&Bshu);printf("请输入B文件进程的调度序列（1—16号）\n");for(x=0;x<Bshu;x++){do{printf("请输入第%d个序列号",x+1);scanf("%d",&Bxulie[x]);}while((Bxulie[x]<1)||(Bxulie[x]>16));}do{printf("请输入执行B文件的调度算法操作号\n操作号：");scanf("%d",&Bcaozuo);}while((Bcaozuo!=1)&&(Bcaozuo!=2)&&(Bcaozuo!=3)&&(Bcaozuo!=4));printf("----------------------------------\n");printf("请输入C文件序列的个数：");scanf("%d",&Cshu);printf("请输入C文件进程的调度序列（1—20号）\n");for(z=0;z<Cshu;z++){do{printf("请输入第%d个序列号",z+1);scanf("%d",&Cxulie[z]);}while((Cxulie[z]<1)||(Cxulie[z]>20));}do{printf("请输入执行C文件的调度算法操作号\n操作号：");scanf("%d",&Ccaozuo);}while((Ccaozuo!=1)&&(Ccaozuo!=2)&&(Ccaozuo!=3)&&(Ccaozuo!=4));printf("----------------------------------\n");printf("----------------------------------\n");printf("----------------------------------\n");printf("A文件的调度过程：\n");if(Acaozuo==1){FRun(Ashu,Axulie);}else{if(Acaozuo==2){LRun(Ashu,Axulie);}else{if(Acaozuo==3){ORun(