第一篇：计算机操作系统实验4页面置换算法
实验4 页面置换算法（2学时）
一、实验目的
通过实验加强对虚拟存储管理中页面置换算法的理解和掌握。
二、实验内容
编写程序实现虚拟存储管理中OPT,FIFO,LRU页面置换算法。
三、实验要求
1、任意给出一组页面访问顺序（如页面走向是1、2、5、7、5、7、1、4、3、5、6、4、3、2、1、5、2）。
2、分配给该作业一定的物理块（如3块、4块等）。
3、利用OPT,FIFO,LRU页面置换算法模拟页面置换过程并计算其缺页率。
4、每访问一个页面均需给出内存中的内容（内存中的页面号），若有淘汰还需给出淘汰的页面号。
5、通过给出特殊的页面访问顺序，分配不同的物理块，利用FIFO算法计算其缺页率，进一步理解Belady现象。
6、（附加）实现CLOCK置换算法，修改位可在确定页面号时直接任意给出。
程序代码（java）
package wcm4;
import java.util.LinkedList;import java.util.Scanner;
public class Test {
/**
* @param args
*/ LinkedList ll=new LinkedList();int a;int leng;int[] all={1,2,5,7,5,7,1,4,3,5,6,4,3,2,1,5,2};//int[] free=new int[all.length];
Object o=new Integer(a);public static void main(String[] args){
public void begin(){ System.out.println(“请选择测试类型：”);System.out.println(“1 OPT;2 FiFO;3 LRU;4 CLOCK;5退出”);
} public void need(){ System.out.println(“请输入分配给该作业的物理块数：”);Scanner sc=new Scanner(System.in);leng=sc.nextInt();Scanner sc=new Scanner(System.in);int choose=sc.nextInt();while(choose!=5){
} switch(choose){ case 1:this.opt();break;case 2:this.fifo();break;case 3:this.lru();break;case 4:this.clock();break;} System.out.println(“请选择测试类型：”);System.out.println(“1 OPT;2 FiFO;3 LRU;4 CLOCK;5退出”);sc=new Scanner(System.in);choose=sc.nextInt();// TODO Auto-generated method stub Test t=new Test();t.begin();
}
}
public void fifo(){ ll=new LinkedList();this.need();
int a=0;for(int i=0;i o=all[i];if(!ll.contains(o)){ } if(ll.size() } ll.add(o);o=ll.poll();a++;else{ o=null;} this.print();} System.out.println(“FIFO的缺页率为：”);System.out.println(a);System.out.println(“——”);System.out.println(all.length); } public void opt(){//最佳置换算法 //leng=0;ll=new LinkedList();this.need();int a=0;//int temp=0;//int[] b=new int[leng]; for(int i=0;i int[] b=new int[leng];o=all[i];if(!ll.contains(o)){ if(ll.size() ll.add(o); } o=null;} else{ for(int j=i;j Object o1=new Integer(all[j]); } for(int k=0;k } if(ll.get(k).equals(o1)){ } if(b[k]==0){ b[k]=j;//待替换的页在以后第一次出现的位置 } } if(b[leng-1]==0){ o=ll.set(leng-1, o);a++;} else{ int temp=0; } for(int m=0;m if(b[m]==0){ temp=m;break;} else if(b[m]>b[temp]){ } temp=m; } o=ll.set(temp, o);//替换以后离得最远的 a++;} else{ } o=null;this.print();} System.out.println(“OPT的缺页率为：”);System.out.println(a);System.out.println(“——”);System.out.println(all.length); public void lru(){//最近最久未使用 } public void clock(){//简单clock ll=new LinkedList();this.need();int a=0;int[] b=new int[leng];for(int i=0;i o=all[i];if(!ll.contains(o)){ if(ll.size() o=all[i];if(!ll.contains(o)){ if(ll.size() } ll.add(o);o=ll.poll();a++;} else{ ll.add(o);ll.remove(o);o=null;} this.print();} System.out.println(“OPT的缺页率为：”);System.out.println(a);System.out.println(“——”);System.out.println(all.length); } } else{ for(int j=0;j<=ll.size();j++){ if(b[j%ll.size()]==0){ } } } else{ int temp1=j%ll.size(); } o=ll.set(temp1, o); b[temp1]=0;//改变该位的标记位 break; b[j%ll.size()]=1;a++;} else{ int temp=ll.indexOf(o);//找到该位 b[temp]=0;o=null;} this.print();System.out.println(“标记位为：”);for(int k=0;k public void print(){ Object[] op=ll.toArray();for(int i=0;i ”);System.out.println(o);//System.out.println();System.out.print(op[i]);} } 计算机工程学院 实验报告书 课程名：《 操作系统原理A 》 题 目： 虚拟存储器管理 页面置换算法模拟实验 班 级： 学 号： 姓 名： 评语： 成绩： 指导教师： 批阅时间： ****年**月**日 一、实验目的与要求 1.目的： 请求页式虚存管理是常用的虚拟存储管理方案之一。通过请求页式虚存管理中对页面置换算法的模拟，有助于理解虚拟存储技术的特点，并加深对请求页式虚存管理的页面调度算法的理解。 2.要求： 本实验要求使用C语言编程模拟一个拥有若干个虚页的进程在给定的若干个实页中运行、并在缺页中断发生时分别使用FIFO和LRU算法进行页面置换的情形。其中虚页的个数可以事先给定（例如10个），对这些虚页访问的页地址流（其长度可以事先给定，例如20次虚页访问）可以由程序随机产生，也可以事先保存在文件中。要求程序运行时屏幕能显示出置换过程中的状态信息并输出访问结束时的页面命中率。程序应允许通过为该进程分配不同的实页数，来比较两种置换算法的稳定性。 二、实验说明 1．设计中虚页和实页的表示 本设计利用C语言的结构体来描述虚页和实页的结构。 pn pfn time pn pfn next 虚页结构 实页结构 在虚页结构中，pn代表虚页号，因为共10个虚页，所以pn的取值范围是0—9。pfn代表实页号，当一虚页未装入实页时，此项值为-1；当该虚页已装入某一实页时，此项值为所装入的实页的实页号pfn。time项在FIFO算法中不使用，在LRU中用来存放对该虚页的最近访问时间。 在实页结构中中，pn代表虚页号，表示pn所代表的虚页目前正放在此实页中。pfn代表实页号，取值范围（0—n-1）由动态指派的实页数n所决定。next是一个指向实页结构体的指针，用于多个实页以链表形式组织起来，关于实页链表的组织详见下面第4点。 2．关于缺页次数的统计 为计算命中率，需要统计在20次的虚页访问中命中的次数。为此，程序应设置一个计数器count，来统计虚页命中发生的次数。每当所访问的虚页的pfn项值不为-1，表示此虚页已被装入某实页内，此虚页被命中，count加1。最终命中率=count/20*100%。 3．LRU算法中“最近最久未用”页面的确定 为了能找到“最近最久未用”的虚页面，程序中可引入一个时间计数器countime，每当要访问一个虚页面时，countime的值加1，然后将所要访问的虚页的time项值设置为增值后的当前countime值，表示该虚页的最后一次被访问时间。当LRU算法需要置换时，从所有已分配实页的虚页中找出time值为最小的虚页就是“最近最久未用”的虚页面，应该将它置换出去。 4．算法中实页的组织 因为能分配的实页数n是在程序运行时由用户动态指派的，所以应使用链表组织动态产生的多个实页。为了调度算法实现的方便，可以考虑引入free和busy两个链表：free链表用于组织未分配出去的实页，首指针为free_head，初始时n个实页都处于free链表中；busy链表用于组织已分配出去的实页，首指针为busy_head，尾指针为busy_tail，初始值都为null。当所要访问的一个虚页不在实页中时，将产生缺页中断。此时若free链表不为空，就取下链表首指针所指的实页，并分配给该虚页。若free链表为空，则说明n个实页已全部分配出去，此时应进行页面置换：对于FIFO算法要将busy_head 所指的实页从busy链表中取下，分配给该虚页，然后再将该实页插入到busy链表尾部；对于LRU算法则要从所有已分配实页的虚页中找出time值为最小的虚页，将该虚页从装载它的那个实页中置换出去，并在该实页中装入当前正要访问的虚页。 三、程序流程图 四、主要程序清单 #include #include /*全局变量*/ int mSIZE; /*物理块数*/ int pSIZE; /*页面号引用串个数*/ static int memery[10]={0}; /*物理块中的页号*/ static int page[100]={0}; /*页面号引用串*/ static int temp[100][10]={0}; /*辅助数组*/ /*置换算法函数*/ void FIFO(); void LRU(); void OPT(); /*辅助函数*/ void print(unsigned int t); void designBy(); void download(); void mDelay(unsigned int Delay); /*主函数*/ void main() { int i,k,code; printf(“请输入物理块的个数(M<=10)：“); scanf(“%d“,&mSIZE); printf(“请输入页面号引用串的个数(P<=100)：“); scanf(“%d“,&pSIZE); puts(“请依次输入页面号引用串(连续输入，无需隔开)：“); for(i=0;i scanf(“%1d“,&page[i]); download(); do { puts(“输入的页面号引用串为：“); for(k=0;k<=(pSIZE-1)/20;k++) { for(i=20*k;(i { if(((i+1)%20==0)||(((i+1)%20)&&(i==pSIZE-1))) printf(“%d＼n“,page[i]); else printf(“%d “,page[i]); } } printf(“* * * * * * * * * * * * * * * * * * * * * * *＼n“); printf(“* 请选择页面置换算法：＼t＼t＼t *＼n“); printf(“* -----------------------------------------*＼n“); printf(“* 1.先进先出(FIFO) 2.最近最久未使用(LRU) *＼n“); printf(“* 3.退出 *＼n“); printf(“* * * * * * * * * * * * * * * * * * * * * * *＼n“); printf(“请选择操作：[ ]＼b＼b“); scanf(“%d“,&code); switch(code) { case 1: FIFO(); break; case 2: LRU(); break; case 3: OPT(); break; case 4: system(“cls“); //system(“color 0A“); exit(0); default: printf(“输入错误，请重新输入：“); } printf(“按任意键重新选择置换算法：>>>“); getchar(); } while (code!=4); getchar(); } /*载入数据*/ void download() { printf(“＼nFinish.＼n载入成功!“); } /*设置延迟*/ void mDelay(unsigned int Delay) { unsigned int i; for(;Delay>0;Delay--) { for(i=0;i<124;i++) { printf(“ ＼b“); } } } /*显示设计者信息*/ void print(unsigned int t) { int i,j,k,l; int flag; for(k=0;k<=(pSIZE-1)/20;k++) { for(i=20*k;(i { if(((i+1)%20==0)||(((i+1)%20)&&(i==pSIZE-1))) printf(“%d＼n“,page[i]); else printf(“%d “,page[i]); } for(j=0;j { for(i=20*k;(i if(i>=j) printf(“ |%d|“,temp[i][j]); else printf(“ | |“); } for(i=mSIZE+20*k;(i { for(flag=0,l=0;l if(temp[i][l]==temp[i-1][l]) flag++; if(flag==mSIZE)/*页面在物理块中*/ printf(“ “); else printf(“ |%d|“,temp[i][j]); } /*每行显示20个*/ if(i%20==0) continue; printf(“＼n“); } } printf(“----------------------------------------＼n“); printf(“缺页次数：%d＼t＼t“,t+mSIZE); printf(“缺页率：%d/%d＼n“,t+mSIZE,pSIZE); printf(“置换次数：%d＼t＼t“,t); printf(“访问命中率：%d%%＼n“,(pSIZE-(t+mSIZE))*100/pSIZE); printf(“----------------------------------------＼n“); } /*计算过程延迟*/ void compute() { int i; printf(“正在进行相关计算，请稍候“); for(i=0;i++<30;printf(“＼b“)); for(i=0;i++<30;printf(“ “)); for(i=0;i++<30;printf(“＼b“)); } /*先进先出页面置换算法*/ void FIFO() { int memery[10]={0}; int time[10]={0}; /*记录进入物理块的时间*/ int i,j,k,m; int max=0; /*记录换出页*/ int count=0; /*记录置换次数*/ /*前mSIZE个数直接放入*/ for(i=0;i { memery[i]=page[i]; time[i]=i; for(j=0;j temp[i][j]=memery[j]; } for(i=mSIZE;i { /*判断新页面号是否在物理块中*/ for(j=0,k=0;j { if(memery[j]!=page[i]) k++; } if(k==mSIZE) /*如果不在物理块中*/ { count++; /*计算换出页*/ max=time[0] for(m=2;m if(time[m] max=m; memery[max]=page[i]; time[max]=i; /*记录该页进入物理块的时间*/ for(j=0;j temp[i][j]=memery[j]; } else { for(j=0;j temp[i][j]=memery[j]; } } compute(); print(count); } /*最近最久未使用置换算法*/ void LRU() { int memery[10]={0}; int flag[10]={0}; /*记录页面的访问时间*/ int i,j,k,m; int max=0; /*记录换出页*/ int count=0; /*记录置换次数*/ /*前mSIZE个数直接放入*/ for(i=0;i { memery[i]=page[i]; flag[i]=i; for(j=0;j temp[i][j]=memery[j]; } for(i=mSIZE;i { /*判断新页面号是否在物理块中*/ for(j=0,k=0;j { if(memery[j]!=page[i]) k++; else flag[j]=i; /*刷新该页的访问时间*/ } if(k==mSIZE) /*如果不在物理块中*/ { count++; /*计算换出页*/ max=flag[0] for(m=2;m if(flag[m] max=m; memery[max]=page[i]; flag[max]=i; /*记录该页的访问时间*/ for(j=0;j temp[i][j]=memery[j]; } else { for(j=0;j temp[i][j]=memery[j]; } } compute(); print(count); } /*最佳置换算法*/ void OPT() { int memery[10]={0}; int next[10]={0}; /*记录下一次访问时间*/ int i,j,k,l,m; int max; /*记录换出页*/ int count=0; /*记录置换次数*/ /*前mSIZE个数直接放入*/ for(i=0;i { memery[i]=page[i]; for(j=0;j temp[i][j]=memery[j]; } for(i=mSIZE;i { /*判断新页面号是否在物理块中*/ for(j=0,k=0;j { if(memery[j]!=page[i]) k++; } if(k==mSIZE) /*如果不在物理块中*/ { count++; /*得到物理快中各页下一次访问时间*/ for(m=0;m { for(l=i+1;l if(memery[m]==page[l]) break; next[m]=l; } /*计算换出页*/ max=next[0]>=next[1]?0:1; for(m=2;m if(next[m]>next[max]) max=m; /*下一次访问时间都为pSIZE,则置换物理块中第一个*/ memery[max]=page[i]; for(j=0;j temp[i][j]=memery[j]; } } if(k==mSIZE) /*如果不在物理块中*/ { count++; /*得到物理快中各页下一次访问时间*/ for(m=0;m { for(l=i+1;l if(memery[m]==page[l]) break; next[m]=l; } /*计算换出页*/ max=next[0]>=next[1]?0:1; for(m=2;m if(next[m]>next[max]) max=m; /*下一次访问时间都为pSIZE,则置换物理块中第一个*/ memery[max]=page[i]; for(j=0;j temp[i][j]=memery[j]; } } 五、程序运行结果 ①FIFO ②LRU 六、实验体会 在做该次作业的时候，通过对课本相关内容的温习，以及对自己在网络上找到的一些资源的了解。我对操作系统中页面调度的算法有了很大程度的了解，加深了对课程上知识的理解，也懂得了如何在程序中将这些算法实现，在程序中基本上实现了所要求的算法以及相关的性能分析，基本上实现了课程的要求。 这次作业也暴露了自己在某些方面的不足之处，自己的语言功底有一定的不足，以及一开始对某个算法不够熟悉，将算法实现设计的比较复杂，此次自己的程序存在一些思想上的漏洞，反映出此次程序设计的要求有了一定的限制。 实验5 页面置换算法 一、实验题目：页面置换算法（请求分页） 二、实验目的： 进一步理解父子进程之间的关系。 1）理解内存页面调度的机理。2）掌握页面置换算法的实现方法。3）通过实验比较不同调度算法的优劣。4）培养综合运用所学知识的能力。 页面置换算法是虚拟存储管理实现的关键，通过本次试验理解内存页面调度的机制，在模拟实现FIFO、LRU等经典页面置换算法的基础上，比较各种置换算法的效率及优缺点，从而了解虚拟存储实现的过程。将不同的置换算法放在不同的子进程中加以模拟，培养综合运用所学知识的能力。 三、实验内容及要求 这是一个综合型实验，要求在掌握父子进程并发执行机制和内存页面置换算法的基础上，能综合运用这两方面的知识，自行编制程序。 程序涉及一个父进程和两个子进程。父进程使用rand()函数随机产生若干随机数，经过处理后，存于一数组Acess_Series[]中，作为内存页面访问的序列。两个子进程根据这个访问序列，分别采用FIFO和LRU两种不同的页面置换算法对内存页面进行调度。要求： 1）每个子进程应能反映出页面置换的过程，并统计页面置换算法的命中或缺页情况。 设缺页的次数为diseffect。总的页面访问次数为total_instruction。缺页率 = disaffect/total_instruction 命中率 = 1-disaffect/total_instruction 2）将为进程分配的内存页面数mframe 作为程序的参数，通过多次运行程序，说明FIFO算法存在的Belady现象。 四、程序流程图 开始创建子进程1创建子进程2 结束 子进程1逻辑页面读完？N命中？N内存页面满？Y命中次数+1YY最先进入的进程退出内存页面N当前调入页面进入内存页面退出 2逻辑页面读完？N命中？N内存页面满？N当前调入页面进入内存页面Y被访问次数最少的进程退出内存页面Y命中次数+1，命中页面访问数+1Y退出 五、运行结果及其说明 FIFO: LRU: ： 六、回答以下问题： ① 父进程、子进程之间的并发执行的过程 父进程与子进程之间的并发执行宏观并行，微观串行。从宏观来说，父进程创建子进程1，子进程1和父进程同时执行，直到父进程创建子进程2遇到wait()函数挂机为止，当子进程1结束父进程和子进程2并发执行到再次遇见wait()函数是挂起等待子进程2结束，到子进程2结束返回父进程父进程继续执行至结束。从微观来说，父进程先执行至创建子进程1，接下来父进程挂起执行子进程1知道子进程1结束回到父进程；父进程继续执行到创建子进程2再次挂起，执行子进程2，直到子进程2结束回到父进程继续执行至结束。 ② 通过完成实验，根据你的体会，阐述虚拟存储器的原理。虚拟存储器实际上是用来解决作业大而内存小的问题，他通过页面置换算法来提供远大于内存地址空间的地址范围，针对不同的程序将不同的数据页面读取到虚拟存储器中用来实现。 ③ 写出FIFO算法中出现Belady现象的内存页面访问序列。 4个内存页面数： 序列2 2 5 3 3 1 3 1 2 5 5 2 3个内存页面数： 序列2 1 3 2 1 4 3 1 3 1 5 5 7次命中，命中率为0.58 6次命中，命中率为0.5 七、程序源代码、文档注释及文字说明 #include main(){ srand(time(0));int pid1, pid2, fd[2], Acess_Series[12], temp;float effect, rate = 0;char str1[100], str2[100];struct M_Frame { int page_no; char flag;};struct M_Frame one_frame[4];one_frame[0].page_no = 0;one_frame[1].page_no = 0;one_frame[2].page_no = 0;one_frame[3].page_no = 0;effect = 0;int i = 0;printf(“内存访问页面序列:”);for(;i<12;i++){ Acess_Series[i] = rand()% 5 + 1; printf(“%d ”, Acess_Series[i]);} while((pid1 = fork())==-1);if(pid1 == 0){ int no = 0; int pno = 0; printf(“FIFO页面置换算法:n”); for(;no<12;no++) { printf(“调入的页面号是%d ”, Acess_Series[no]); int k = 0; for(;k <= Frame;k++) { if(one_frame[k].page_no == Acess_Series[no]){ effect++;printf(“命中n”);break;} if(one_frame[k].page_no == 0) { one_frame[k].page_no = Acess_Series[no]; printf(“未命中n”); break; } if(k == Frame) { int j = 1; for(;j <= Frame;j++) { one_frame[j1].page_no;one_frame[t1].page_no = one_frame[j].page_no; } one_frame[Frame].page_no = Acess_Series[no]; printf(“未命中n”); } } printf(“内存情况为:%d |%d |%d |%dn”, one_frame[0].page_no, one_frame[1].page_no, one_frame[2].page_no, one_frame[3].page_no); } rate = effect / 12; printf(“命中次数：%fn”, effect); printf(“命中率：%fn”, rate); } wait(0); exit(0);} } 操作系统课程第七次实验报告 姓名 学号 系 计算机 任课教师 指导教师 评阅教师 实验地点 综合楼B102 实验时间 2012-9-26 实验课表现 出勤和个人表现Q1(15+15（组长评分）=30分) 得分： 实验 总分 (Q1+Q2+Q3+Q4) 实验完成情况Q2(45分(组长与教师评分的加权平均)) 得分： 实验编号与实验名称： 实验七、常用页面置换算法模拟实验 实验目的： 通过模拟实现请求页式存储管理的几种基本页面置换算法，了解虚拟存储技术的特点，掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程，并比较它们的效率。 实验内容及要求（详见实验讲义与实验指导书）： 要求： 1）要求用你熟悉的程序设计语言编写和调试一个页面置换模拟程序；要求在主函数中测试。 2）实验报告中必须包括：设计思想、数据定义（包括详细说明）、处理流程（详细算法描述和算法流程图）、源代码、运行结果、体会等部分。 3）必须模拟本实验内容中提到的算法中的至少2种页面置换算法。 4） 比较不同页面置换算法的效率 内容：编写一个程序，使用以下页面置换算法中的某2种分别模拟一个分页系统，并统计同一个页面访问序列情况下不同页面置换算法引发的缺页中断次数。 1、第二次机会算法（Second Chance） 2、最近最少使用算法（Least Recently Used，LRU） 3、最不常用算法（Not Frequently Used，NFU） 4、最近未使用算法（Not Recently Used，NRU） 5、时钟页面置换算法 6、老化算法（aging） 页框的数量固定为4，虚拟页面数为8。实验输入为访问页面序列，比如0，1，3，2，7，1 实验用到的软件（：） DevC++,Visio 实验内容及关键步骤（代码）Q3（15分） 得分： 流程图：输入页面访问序列 取访问的页号 查页表 是否缺页？ 是 置缺页标志flag为’*’ 按算法不同淘汰一页面 调入所访问的页面 否 FIFO算法流程图 LRU算法流程图： 函数关系解释图： 实现结果： 图1 图2 代码： #include #include #define MEMORY_SIZE /*物理块数*/ #define PROESS_SIZE /*页面号引用串个数*/#include #include /*全局变量*/ int mSIZE=4; int pSIZE=8; static int memery[4]={0}; /*物理块中的页号*/ static int page[8]={0}; /*页面号引用串*/ static int temp[8][4]={0}; /*辅助数组*/ /*置换算法函数*/ void FIFO(); void LRU(); void OPT(); void designBy(); /*辅助函数*/ void print(unsigned int t); /*主函数*/ int main() { int i,k,code; designBy(); system(“color 0A“); puts(“请依次输入页面号(8个)：“); for(i=0;i scanf(“%1d“,&page[i]); system(“cls“); system(“color 0E“); do{ puts(“输入的页面号引用串为：“); for(k=0;k<=(pSIZE-1)/20;k++) { for(i=20*k;(i { if(((i+1)%20==0)||(((i+1)%20)&&(i==pSIZE-1))) printf(“%d＼n“,page[i]); else printf(“%d “,page[i]); } } printf(“* * * * * * * * * * * * * * * * * * * * * * *＼n“); printf(“* 请选择页面置换算法：＼t＼t＼t *＼n“); printf(“* ----------------------------------------- *＼n“); printf(“* 1.先进先出(FIFO) 2.最近最久未使用(LRU) *＼n“); printf(“* 3.退出 *＼n“); printf(“* * * * * * * * * * * * * * * * * * * * * * *＼n“); printf(“请选择操作：[ ]＼b＼b“); scanf(“%d“,&code); switch(code) { case 1: FIFO(); break; case 2: LRU(); break; case 3: system(“cls“); system(“color 0A“); exit(0); default: printf(“输入错误，请重新输入：“); } printf(“按任意键重新选择置换算法：>>>“); getch(); system(“cls“); }while (code!=3); getch(); } void print(unsigned int t) { int i,j,k,l; int flag; for(k=0;k<=(pSIZE-1)/20;k++) { for(i=20*k;(i { if(((i+1)%20==0)||(((i+1)%20)&&(i==pSIZE-1))) printf(“%d＼n“,page[i]); else printf(“%d “,page[i]); } for(j=0;j { for(i=20*k;(i if(i>=j) printf(“ |%d|“,temp[i][j]); else printf(“ | |“); } for(i=mSIZE+20*k;(i { for(flag=0,l=0;l if(temp[i][l]==temp[i-1][l]) flag++; if(flag==mSIZE)/*页面在物理块中*/ printf(“ “); else printf(“ |%d|“,temp[i][j]); } /*每行显示20个*/ if(i%20==0) continue; printf(“＼n“); } } printf(“----------------------------------------＼n“); printf(“缺页次数：%d＼t＼t“,t+mSIZE); printf(“缺页率：%d/%d＼n“,t+mSIZE,pSIZE); printf(“置换次数：%d＼t＼t“,t); printf(“访问命中率：%d%%＼n“,(pSIZE-(t+mSIZE))*100/pSIZE); printf(“----------------------------------------＼n“); } /*先进先出页面置换算法*/ void FIFO() { int memery[10]={0}; int time[10]={0}; /*记录进入物理块的时间*/ int i,j,k,m; int max=0; /*记录换出页*/ int count=0; /*记录置换次数*/ /*前mSIZE个数直接放入*/ for(i=0;i { memery[i]=page[i]; time[i]=i; for(j=0;j temp[i][j]=memery[j]; } for(i=mSIZE;i { /*判断新页面号是否在物理块中*/ for(j=0,k=0;j { if(memery[j]!=page[i]) k++; } if(k==mSIZE) /*如果不在物理块中*/ { count++; /*计算换出页*/ max=time[0] for(m=2;m if(time[m] max=m; memery[max]=page[i]; time[max]=i; /*记录该页进入物理块的时间*/ for(j=0;j temp[i][j]=memery[j]; } else { for(j=0;j temp[i][j]=memery[j]; } } print(count); } /*最近最久未使用置换算法*/ void LRU() { int memery[10]={0}; int flag[10]={0}; /*记录页面的访问时间*/ int i,j,k,m; int max=0; /*记录换出页*/ int count=0; /*记录置换次数*/ /*前mSIZE个数直接放入*/ for(i=0;i { memery[i]=page[i]; flag[i]=i; for(j=0;j temp[i][j]=memery[j]; } for(i=mSIZE;i { /*判断新页面号是否在物理块中*/ for(j=0,k=0;j { if(memery[j]!=page[i]) k++; else flag[j]=i; /*刷新该页的访问时间*/ } if(k==mSIZE) /*如果不在物理块中*/ { count++; /*计算换出页*/ max=flag[0] for(m=2;m if(flag[m] max=m; memery[max]=page[i]; flag[max]=i; /*记录该页的访问时间*/ for(j=0;j temp[i][j]=memery[j]; } else { for(j=0;j temp[i][j]=memery[j]; } } // compute(); print(count); } /*显示设计者信息*/ void designBy() { printf(“┏━━━━━━━━━━━━━━━━━━━━━━━━━┓＼n“); printf(“┃㊣ 实验七：页面置换算法 ㊣┃＼n“); printf(“┃ 学号：1001010042 ┃＼n“); printf(“┃ 姓名：黄浩全 4.9.9.0>┃＼n“); printf(“┣━━━━━━━━━━━━━━━━━━━━━━━━━┫＼n“); } 实验过程中遇到的问题解决办法与实验体会Q4（需手写，10分） 得分： 1、在FIFO算法可以很容易用数组实现，而LRU算法可以用数组实现，不过用结构体会更明显简单。结构体成员变量可以记录页号进入的时间，和最近使用的记录。相对比数组更容易理解和实现。 2:首先，FIFO（先进先出）算法和LRU（最近未使用算法）两者之间，FIFO算法明显会比LRU容易理解，而且比LRU算法较容易实现，但在性能方面，LRU的确在优化方面做的比较理想。再且在考虑页框和页表号之间的问题用代码可以容易模拟，但是真是在物理内存块中是如何实现，那确实是很难以理解，需要真正理解到内存内部的知识才知道这两个算法是怎么实现的。 评阅教师特殊评语： 评阅教师： 日 期： 《计算机操作系统》 课 程 设 计 报 告 题 目： 银行家算法 班 级： XXXXXXXXXXXXXXXX 姓 名： XXM 学 号： XXXXXXXXXXXX 指导老师: XXXXXXXXXXXXXX 设计时间: XXXXXXXXXXXXXXX 一.设计目的 1、掌握死锁概念、死锁发生的原因、死锁产生的必要条件; 2、掌握死锁的预防、死锁的避免; 3、深刻理解死锁的避免：安全状态和银行家算法; 二.银行家算法 1.简介 银行家算法是一种最有代表性的避免死锁的算法。在避免死锁方法中允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次分配资源的安全性，若分配不会导致系统进入不安全状态，则分配，否则等待。为实现银行家算法，系统必须设置若干数据结构。 2.数据结构 1）可利用资源向量Available 是个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目。如果Available[j]=K，则表示系统中现有Rj类资源K个。2）最大需求矩阵Max 这是一个n×m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max[i,j]=K，则表示进程i需要Rj类资源的最大数目为K。3）分配矩阵Allocation 这也是一个n×m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation[i,j]=K，则表示进程i当前已分得Rj类资源的 数目为K。4）需求矩阵Need 这也是一个n×m的矩阵，用以表示每一个进程尚需的各类资源数。如果Need[i,j]=K，则表示进程i还需要Rj类资源K个，方能完成其任务。Need[i,j]=Max[i,j]-Allocation[i,j].3.算法原理 操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程本次申请的资源数是否超过了该资源所剩余的总量。若超过则拒绝分配资源，若能满足则按当前的申请量分配资源，否则也要推迟分配。 三.算法实现 1.初始化 由用户输入数据，分别对可利用资源向量矩阵AVAILABLE、最大需求矩阵MAX、分配矩阵ALLOCATION、需求矩阵NEED赋值。 2.银行家算法 在避免死锁的方法中，所施加的限制条件较弱，有可能获得令人满意的系统性能。在该方法中把系统的状态分为安全状态和不安全状态，只要能使系统始终都处于安全状态，便可以避免发生死锁。 银行家算法的基本思想是分配资源之前，判断系统是否是安全的；若是，才分配。设进程cusneed提出请求REQUEST [i]，则银行家算法按如下规则进行判断。(1)如果REQUEST [cusneed] [i]<= NEED[cusneed][i]，则转（2)；否则，出错。(2)如果REQUEST [cusneed] [i]<= AVAILABLE[cusneed][i]，则转（3)；否则，出错。(3)系统试探分配资源，修改相关数据： AVAILABLE[i]-=REQUEST[cusneed][i];ALLOCATION[cusneed][i]+=REQUEST[cusneed][i];NEED[cusneed][i]-=REQUEST[cusneed][i];(4)系统执行安全性检查，如安全，则分配成立；否则试探险性分配作废，系统恢复原状，进程等待。 3.安全性检查算法 (1)设置两个工作向量Work=AVAILABLE;FINISH(2)从进程集合中找到一个满足下述条件的进程，FINISH==false;NEED<=Work;如找到，执行（3)；否则，执行（4)(3)设进程获得资源，可顺利执行，直至完成，从而释放资源。Work+=ALLOCATION;Finish=true;GOTO 2(4)如所有的进程Finish= true，则表示安全；否则系统不安全。 4.算法流程图 1)初始化算法流程图 2)银行家算法流程图： 3)安全性算法流程图： 4.代码（C语言） #include /*M个进程对N类资源最大资源需求量*/ int MAX[M][N]={{7,5,3},{3,2,2},{9,0,2},{2,2,2},{4,3,3}};/*系统可用资源数*/ int AVAILABLE[N]={10,5,7};/*M个进程对N类资源最大资源需求量*/ int ALLOCATION[M][N]={{0,0,0},{0,0,0},{0,0,0},{0,0,0},{0,0,0}}; /*M个进程已经得到N类资源的资源量 */ int NEED[M][N]={{7,5,3},{3,2,2},{9,0,2},{2,2,2},{4,3,3}}; /*M个进程还需要N类资源的资源量*/ int Request[N]={0,0,0}; void main(){ int i=0,j=0;char flag; void showdata();void changdata(int);void rstordata(int);int chkerr(int);showdata();enter:{ printf(“请输入需申请资源的进程号（从0到”); printf(“%d”,M-1); printf(“）:”); scanf(“%d”,&i);} if(i<0||i>=M){ printf(“输入的进程号不存在，重新输入!n”); goto enter;} err:{ printf(“请输入进程”); printf(“%d”,i); printf(“申请的资源数n”); printf(“类别: A B Cn”);printf(“ ”); for(j=0;j { scanf(“%d”,&Request[j]); if(Request[j]>NEED[i][j]) { printf(“%d”,i); printf(“号进程”); printf(“申请的资源数 > 进程”); printf(“%d”,i); printf(“还需要”); printf(“%d”,j);printf(“类资源的资源量!申请不合理，出错!请重新选择!n”); goto err; } else { if(Request[j]>AVAILABLE[j]) { printf(“进程 ”); printf(“%d”,i); printf(“申请的资源数大于系统可用”); printf(“%d”,j); printf(“类资源的资源量!申请不合理，出错!请重新选择!n”); goto err; } } } } changdata(i);if(chkerr(i)){ rstordata(i); showdata();} else showdata(); printf(“n”); printf(“按'y'或'Y'键继续,否则退出n”); flag=getch(); if(flag=='y'||flag=='Y'){ goto enter; } else { exit(0);} } /*显示数组*/ void showdata(){ int i,j;printf(“系统可用资源向量:n”);printf(“***Available***n”);printf(“资源类别: A B Cn”);printf(“资源数目:”);for(j=0;j printf(“%d ”,AVAILABLE[j]);} printf(“n”);printf(“n”);printf(“各进程还需要的资源量:n”);printf(“******Need******n”);printf(“资源类别: A B Cn”);for(i=0;i printf(“ ”); printf(“%d”,i); printf(“号进程:”); for(j=0;j { printf(“ %d ”,NEED[i][j]); } printf(“n”);} printf(“n”);printf(“各进程已经得到的资源量: n”);printf(“***Allocation***n”);printf(“资源类别: A B Cn”);for(i=0;i printf(“ ”); printf(“%d”,i); printf(“号进程:”); /*printf(“:n”);*/ for(j=0;j { printf(“ %d ”,ALLOCATION[i][j]); } printf(“n”); } printf(“n”);} /*系统对进程请求响应，资源向量改变*/ void changdata(int k){ int j; for(j=0;j AVAILABLE[j]=AVAILABLE[j]-Request[j]; ALLOCATION[k][j]=ALLOCATION[k][j]+Request[j]; NEED[k][j]=NEED[k][j]-Request[j];} } /*资源向量改变*/ void rstordata(int k) { int j; for(j=0;j AVAILABLE[j]=AVAILABLE[j]+Request [j]; ALLOCATION[k][j]=ALLOCATION[k][j]-Request[j]; NEED[k][j]=NEED[k][j]+Request[j]; } } /*安全性检查函数*/ int chkerr(int s){ int WORK,FINISH[M],temp[M];int i,j,k=0; for(i=0;i WORK=AVAILABLE[j]; i=s; printf(“n”); while(i { if(FINISH[i]==FALSE&&NEED[i][j]<=WORK) { printf(“系统不安全!本次资源申请不成功!n”); printf(“n”); return 1; } } } WORK=WORK+ALLOCATION[i][j]; FINISH[i]=TRUE; temp[k]=i;k++;i=0; printf(“n”); printf(“经安全性检查，系统安全，本printf(”n“); printf(” 本次安全序列：n“);printf(”进程依次为“);for(i=0;i printf(”%d“,temp[i]); 次分配成功。n”);} else { i++;} } for(i=0;i printf(“-> ”);} printf(“n”);return 0;四．程序运行截图 0号进程申请资源{1,2,3},各向量发生变化 0和进程继续申请资源{2,2,0}，各向量变化 2号进程申请资源，由于NEED[2]={9,0,2},前两次申请不合理，系统处于不安全状态太。第三次2号申请资源向量为{1,0,2}，系统回到安全状态，并得出新的安全序列3-0-1-2-4。 五．心得体会 从此次的课程设计中，我收获很多。首先也是最重要的一点是对处理机调度与死锁有了深入的理解；其次，再次巩固了C语言编程。 在用C语言设计和编写银行家算法和安全性检查算法时遇到了一些困难都克服了。在使程序界面美观、能够持续循环运行时用了很多方法，花了比较多的时间。最后选择用goto语句控制，我觉得在此实验中比较好，代码阅读起来更加方便。第二篇：计算机操作系统实验三页面置换算法模拟实验
第三篇：实验5 页面置换算法
第四篇：操作系统 七次实验报告 常用页面置换算法模拟实验
第五篇：计算机操作系统 课程设计报告 银行家算法
点击咨询 