通达学院专业课程设计I 题目1 OPT算法模拟实现题目2 文本编辑器专业学生姓名班级学号指导教师指导单位计算机学院、软件学院日期OPT算法模拟实现(OS类)一、课题内容和要求内容：学习虚拟存储机制中页面调度算法，通过编程模拟实现页面调度的OPT算法，进一步理解页面调度的OPT算法的概念及含义，提高对OPT页面调度算法的认识，同时提高自己动手实践的能力。

加深对主存与辅助存储器统一管理、逻辑地址与物理地址转换、页序列走向的装入和替换问题的理解，同时有利于对存储技术的理解。

要求：利用C语言或是C++设计编程，完成OPT算法的设计，表示页序列走向的装入和替换，算出缺页中断率。

二、概要设计OPT算法即最佳优先算法，实质是通过调页功能和页面置换功能，陆续把即将要运行的页面调入内存，并且把暂时不运行的页面从内存在删除，置换时以页面为单位，算出缺页次数和缺页率，缺页数用diseffect 表示，页面序列数m，初始值diseffect=0，缺页率= diseffect /m。

用C语言设计OPT算法的程序，可以模拟实现算法，在理论联系实际的基础上，分析各个OPT页面置换算法的直接访问或是缺页中断，然后替换的过程。

为了能实现OPT请求调页和置换功能，在VC++6.0上编程模拟实现。

该算法选择永不使用的或是在最长时间内不再被访问的页面进行置换，这是理想化算法，具有最好的性能，淘汰访问串中将来再也不出现的或者是在离当前最远的位置上出现的页，这样淘汰掉该页将不会造成因需要访问该页又立即把它调入的现象。

这种算法难以实现，因为它要求必须预先知道每一个进程的访问串。

实验中在对操作系统的整体把握上，将操作系统的OPT算法用于实践中去，模拟出页面调度算法得出缺页率。

具体实验程序流程图如下：三、详细设计给出一串页面序列的走向，每当发生缺页时，就从物理块中找出最后访问时间最大的页面，调出该页，换入所缺的页面。

实现它的装入和替换的过程，给出OPT页面调度算法的存储结构，算出缺页率。

下表所示是实验过程中举得例子，其中-1表示缺页。

（1）延时程序mDelay，应用在页面初始时延时显示初始界面信息：void mDelay(unsigned int Delay){unsigned int i;for(;Delay>0;Delay--){for(i=0;i<124;i++){printf(" \b");}}}（2） OPT算法的主要部分完成判定内存是否为空，若是在页面中直接访问，若不在判断是否需要置换，插入页面序列的下一个数的操作。

void OPT（）反映出页面置换的过程，并统计OPT页面置换算法的缺页情况。

其中缺页的次数为diseffect。

下面是算法主要代码：void OPT(int n,int m,STORAGE storage[N],PAGE page[M]){int i,j,k,full=0,diseffect=0,time[M],base=0,equal[N],times=0;//若full=n则内存满，time[M]是为实现置换所设置的page[M]的备份数据栈int t;for(i=0;i<m;i++){time[i]=page[i].pagenum;}//备份page[M]printf("当前内存中的页(-1代表无页):");for(j=0;j<n;j++)printf(" %d\t",storage[j].pagenum);printf("\n");for(i=0;i<m;i++){for(j=0;j<n;j++){if(storage[j].pagenum==page[i].pagenum){page[i].framenum=storage[j].framenum;page[i].status=1;base++; //从栈中删除已访问的页printf("直接访问，页%d已在帧%d中",page[i].pagenum,page[i].framenum);} //该页在内存，直接访问}if(page[i].status==0){diseffect++;if(full<n){for(j=0;j<n;j++){if(storage[j].status==0){storage[j].pagenum=page[i].pagenum;storage[j].status=1;page[i].framenum=storage[j].framenum;page[i].status=1;base++;//从栈中删除已访问的页printf("缺页中断，页%d装入帧%d中",page[i].pagenum,page[i].framenum);full++;break;}}} //有空闲页帧，调入内存并访问相关指令else{for(t=base+1;t<m;t++){times=0;for(k=0;k<n;k++)if(storage[k].pagenum==time[t]){equal[k]=1;break;}for(k=0;k<n;k++)if(equal[k]==1)times++;if(times==n-1)break;}for(k=0;k<n;k++){if(equal[k]!=1)j=k;else equal[k]=0; //清零}printf("缺页中断，页%d置换出页%d",page[i].pagenum,storage[j].pagenum);page[i].framenum=storage[j].framenum;storage[j].pagenum=page[i].pagenum;//取出页page[i].status=1;base++;//从栈中删除已访问的页}//无空闲的页帧，置换出老页}//缺页中断printf("\t\t当前内存中的页:");for(j=0;j<n;j++)printf("%d\t",storage[j].pagenum);printf("\n");}printf("\n\n");以下是源程序代码：#include <stdio.h>#include <stdlib.h>#define N 100#define M 10000typedef struct{int pagenum;int framenum;int status; //若status=0则不在内存}PAGE;typedef struct{int pagenum;int framenum;int status; //若status=0则空闲}STORAGE;void OPT();void download();void designBy();void mDelay(unsigned int Delay);void download(){//int i;printf("╔═════════════════════╗\n");printf("║等待进入算法界面... ║\n");printf("╚═════════════════════╝\n");printf("Loading...\n");mDelay(2000);printf(" \0");}void mDelay(unsigned int Delay) //延时{unsigned int i;for(;Delay>0;Delay--){for(i=0;i<124;i++){printf(" \b");}}}/*显示设计者信息*/void designBy(){system("cls"); //清屏system("color FD");printf("┏━━━━━━━━━━━━━━━━━━━━━━━━━┓\n");printf("┃课程设计：OPT页面置换算法┃\n");printf("┃┃\n");printf("┃┃\n");printf("┃学号：12345678 ┃\n");printf("┃┃\n");printf("┃┃\n");printf("┃姓名：**** ┃\n");printf("┣━━━━━━━━━━━━━━━━━━━━━━━━━┫\n");}void OPT(int n,int m,STORAGE storage[N],PAGE page[M]){int i,j,k,full=0,diseffect=0,time[M],base=0,equal[N],times=0;//若full=n则内存满，time[M]是为实现置换所设置的page[M]的备份数据栈int t;for(i=0;i<m;i++){time[i]=page[i].pagenum;} //备份page[M]printf("当前内存中的页(-1代表无页):");for(j=0;j<n;j++)printf(" %d\t",storage[j].pagenum);printf("\n");for(i=0;i<m;i++){for(j=0;j<n;j++){if(storage[j].pagenum==page[i].pagenum){page[i].framenum=storage[j].framenum;page[i].status=1;base++; //从栈中删除已访问的页printf("直接访问，页%d已在帧%d中",page[i].pagenum,page[i].framenum);} //该页在内存，直接访问}if(page[i].status==0){diseffect++;if(full<n){for(j=0;j<n;j++){if(storage[j].status==0){storage[j].pagenum=page[i].pagenum;storage[j].status=1;page[i].framenum=storage[j].framenum;page[i].status=1;base++;//从栈中删除已访问的页printf("缺页中断，页%d装入帧%d中",page[i].pagenum,page[i].framenum);full++;break;}}}//有空闲页帧，调入内存并访问相关指令else{for(t=base+1;t<m;t++){times=0;for(k=0;k<n;k++)if(storage[k].pagenum==time[t]){equal[k]=1;break;}for(k=0;k<n;k++)if(equal[k]==1)times++;if(times==n-1)break;}for(k=0;k<n;k++){if(equal[k]!=1)j=k;else equal[k]=0; //清零}printf("缺页中断，页%d置换出页%d",page[i].pagenum,storage[j].pagenum);page[i].framenum=storage[j].framenum;storage[j].pagenum=page[i].pagenum;//取出页page[i].status=1;base++;//从栈中删除已访问的页}//无空闲的页帧，置换出老页}//缺页中断printf("\t\t当前内存中的页:");for(j=0;j<n;j++)printf("%d\t",storage[j].pagenum);printf("\n");}printf("\n\n");printf(" 缺页率为：%.3f\n\n",(float)diseffect/m);}void main(){int n,m,i;PAGE page[M];STORAGE storage[N];designBy(); /*显示设计者信息后开始*/download();//mDelay(1500);system("cls");system("color 0E");printf("分配的内存页帧:\n");scanf("%d",&n);for(i=0;i<n;i++){storage[i].framenum=i;storage[i].pagenum=-1;storage[i].status=0;}printf("访问的页面序列数:\n");scanf("%d",&m);printf("访问的页面序列:\n");for(i=0;i<m;i++){scanf("%d",&page[i].pagenum);page[i].status=0;}OPT(n,m,storage,page);}四、测试数据及其结果分析输入以下的页面序列，定义物理块数为3，按照表格的分析，可得缺页数为5，则缺页率=5/12=0.417,验证和程序设计的结果一致。