课程设计课程设计名称：计算机操作系统课程设计专业班级：计算机科学与技术班学生姓名：学号：指导教师：课程设计时间： 2010.12.20 ～ 2010.12.24计算机科学与技术专业课程设计任务书一需求分析请求调页存储管理方式的模拟是基于LRU算法的设计而设计的，通过学习计算机操作系统中的请求调页存储管理方式的几种算法，我选择了最近最久未使用算法即LRU算法实现请求调叶存储管理，通过具体的程序来模仿LRU的工作机制。

二概要设计1．数据结构依据给定的数据信息,数组必须以结构体实现,结构类型的层次结构如下: typedef struct BLOCK//声明一种新类型——物理块类型{int pagenum;//页号int accessed;//访问字段，其值表示多久未被访问}BLOCK;2．函数原型清单:Void main();//主函数void init(int Bsize); //程序初始化函数int findExist(int curpage);//查找物理块中是否有该页面int findSpace(int Bsize);//查找是否有空闲物理块int findReplace();//查找应予置换的页面void display(int Bsize);//显示void suijishu(int r);//产生320条随机数,显示并存储到temp[320]void pagestring();//显示调用的页面队列void LRU(int Bsize);// LRU算法3．全局变量：int Bsize;int pc;//程序计数器，用来记录指令的序号int n;//缺页计数器，用来记录缺页的次数static int temp[320];//用来存储320条随机数BLOCK block[Bsize]; //定义一大小为4的物理块数组三运行环境(软硬件环境)硬件:CPU,主板,内存,显示器,硬盘,显卡,键盘等等.软件:WINDOWS XP, Visual c++应用软件.四开发工具和编程语言开发工具:Visual c++编程语言:c语言五详细设计#include <iostream.h>#include<stdlib.h>#include<conio.h>#include<stdio.h>typedef struct BLOCK//声明一种新类型——物理块类型{int pagenum;//页号int accessed;//访问字段，其值表示多久未被访问}BLOCK;int Bsize;BLOCK block[32]; //模拟内存块int pc;//程序计数器，用来记录指令的序号int n;//缺页计数器，用来记录缺页的次数static int temp[320];//用来存储320条随机数//*************************************************************void init(int Bsize); //程序初始化函数int findExist(int curpage);//查找物理块中是否有该页面int findSpace(int Bsize);//查找是否有空闲物理块int findReplace();//查找应予置换的页面void display(int Bsize);//显示void suijishu(int r);//产生320条随机数,显示并存储到temp[320] void pagestring();//显示调用的页面队列void LRU(int Bsize);// LRU算法//************************************************************* void init(int Bsize){int i;for(i=0;i<Bsize;i++){block[i].pagenum=-1;block[i].accessed=0;pc=n=0;}}//------------------------------------------------------------- int findExist(int curpage,int Bsize){int i;for(i=0;i<Bsize; i++){if(block[i].pagenum == curpage )return i;//检测到内存中有该页面，返回block中的位置}return -1;}//------------------------------------------------------------- int findSpace(int Bsize){int i;for(i=0; i<Bsize; i++){if(block[i].pagenum == -1)return i;//找到空闲的block，返回block中的位置}return -1;}//------------------------------------------------------------- int findReplace(int Bsize){int i,pos = 0;for(i=0; i<Bsize; i++){if(block[i].accessed >block[pos].accessed)pos = i;//找到应予置换页面，返回BLOCK中位置}return pos;}//------------------------------------------------------------- void display(int Bsize){if(Bsize==4){int i;for(i=0; i<Bsize; i++){if(block[i].pagenum != -1){ printf(" %02d",block[i].pagenum);}}printf("\n");}}//------------------------------------------------------------- void suijishu(int r){int i,flag=0;pc=r;printf("****按照要求产生的320个随机数：*******\n");for(i=0;i<320;i++){temp[i]=pc;if(flag%2==0) pc=++pc%320;if(flag==1) pc=rand()% (pc-1);if(flag==3) pc=pc+1+(rand()%(320-(pc+1)));flag=++flag%4;printf(" %03d",temp[i]);if((i+1)%10==0) printf("\n");}}//------------------------------------------------------------- void pagestring(){int i;for(i=0;i<320;i++){printf(" %02d",temp[i]/10);if((i+1)%10==0) printf("\n");}}//-------------------------------------------------------------void LRU(int Bsize){int exist,space,position ;int i,j,curpage;init(Bsize);for(i=0;i<320;i++){pc=temp[i];curpage=pc/10;exist = findExist(curpage,Bsize);if(exist==-1){space = findSpace(Bsize);if(space != -1){block[space].pagenum = curpage;display(Bsize);n=n+1;}else{position = findReplace(Bsize);block[position].pagenum = curpage;display(Bsize);n++;}}else block[exist].accessed = -1;//恢复存在的并刚访问过的BLOCK中页面accessed为-1for(j=0; j<4; j++){block[j].accessed++;}}if(Bsize==4)printf("（LRU）算法在不同内存容量下的命中率为\n");printf("内存容量为%d",Bsize);printf("的缺页次数:%d",n);printf("缺页率:%f",(n/320.0)*100);printf("%%");printf("命中率:%f",(1-n/320.0)*100);printf("%%");printf("\n");}//------------------------------------------------------------- //************************************************************* void main(){int t,i,j=1,select;printf("请输入第1条指令号(0~320)：");scanf("%d",&i);while(i>320||i<0){printf("你输入有误,请重新输入！\n");printf("请输入第1条指令号(0~320)：");scanf("%d",&i);}while(i>=0&&i<=320){suijishu(i);printf("*****对应的调用页面队列*******\n");pagestring();printf("******************************\n");init(i);printf("最近最久未使用置换算法LRU:\n");printf("******************************\n");for(t=4;t<=32;t++)LRU(t);j=j+1;printf("请输入第%d条指令号(0~320)[输入-1结束]：",j);scanf("%d",&i);}}六调试分析(1).刚开始进行编译时,出现了86个错误和警告,吓了自己一跳,于是就静下心来一点一点分析程序,发现自己竟然那么粗心,不是少了括号就是少了分号,还有一些语法错误,经过慢慢的修改,程序最终顺利运行出来.(2).在调试过程中,有时会显示没有错误和警告,但程序会无法执行,或执行到中间就无法在执行了,于是我就用F10进行调试,发现可能出错的子函数,然后进行仔细分析改正,调试成功.七测试结果图1 输入错误数字的提示信息图2随机产生的320个数图3对应的调用页面的队列图4 LRU算法（1）图5 LRU算法（2）图6 LRU算法（3）图7 LRU算法（4）图8 LRU算法（5）和计算最近最少使用（LRU）算法在不同内存容量下的命中率八参考文献[1] 谭浩强《C程序设计》第三版北京清华大学出版社[2] 丁华伟《C语言程序设计系统》第三版北京清华大学出版社[3] 严蔚敏《数据结构》C语言版北京清华大学出版社课程设计总结本程序能通过输入第一条指令号（用3位整数代表指令号），产生320个随机数，并以每行10个显示出来。