操作系统课程实验报告编程模拟页面置换算法

湖南师范大学树达学院操作系统课程实验报告题目编程模拟页面置换算法理工系09级电子商务专业姓名学号指导教师张楚才2011年

实验题目：编程模拟页面置换算法实验要求：利用C语言分别实现先进先出置换算法FIFO、最佳置换算法OPT、最近最久未使用置换算法LRU。要求在任意给定的页面访问序列和内存的物理块数下，输出每种算法下的缺页率。例如，假定系统为某进程分配了3个物理块，进程运行时的页面走向为7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1，开始时3个物理块均为空，分别求出每种算法下的缺页率。#include<stdio.h>voidPrint(intbc[],intblockCount){for(inti=0;i<blockCount;i++){printf("%d",bc[i]);}printf("\n");}boolTravel(intbc[],intblockCount,intx){boolis_found=false;inti;for(i=0;i<blockCount;i++){if(bc[i]==x){is_found=true;break;}}returnis_found;}voidFIFO(intpc[],intbc[],intpageCount,intblockCount){printf("0：FIFO置换算法\n");inti;if(pageCount<=blockCount){printf("缺页次数为0\n");printf("缺页率为0\n");}else{intnoPage=0;intp=0;for(i=0;i<pageCount;i++){//printf("引用页：%d\n",pc[i]);if(!Travel(bc,blockCount,pc[i])){if(i<blockCount){bc[i]=pc[i];}else{if(p==blockCount){p=0;}bc[p]=pc[i];p++;}noPage++;//printf("物理块情况：\n");//Print(bc,blockCount);}//printf("\n");}printf("FIFO缺页次数为:%d\n",noPage);printf("FIFO缺页率为:%.2f%%\n",(float)noPage/pageCount*100);}}intFoundMaxNum(inta[],intn){intk,j;k=a[0];j=0;for(inti=0;i<n;i++){if(a[i]>=k){k=a[i];j=i;}}returnj;}voidLRU(intpc[],intbc[],intpageCount,intblockCount){printf("1：LRU置换算法\n");if(pageCount<=blockCount){printf("缺页次数为0\n");printf("缺页率为0\n");}else{intnoPage=0;inti,j,m;intbc1[100];for(i=0;i<blockCount;i++){bc1[i]=0;}for(i=0;i<pageCount;i++){//printf("引用页：%d\n",pc[i]);if(!Travel(bc,blockCount,pc[i])){if(i<blockCount){bc[i]=pc[i];for(intp=0;p<=i;p++){bc1[p]++;}}else{for(j=0;j<blockCount;j++){bc1[j]++;}intk=FoundMaxNum(bc1,blockCount);bc[k]=pc[i];bc1[k]=1;}noPage++;//printf("物理快情况：\n");//Print(bc,blockCount);}elseif(Travel(bc,blockCount,pc[i])){if(i<blockCount){for(j=0;j<=i;j++){bc1[j]++;}for(m=0;m<=i;m++){if(bc[m]==pc[i]){break;}}bc1[m]=1;bc[m]=pc[i];}else{for(j=0;j<blockCount;j++){bc1[j]++;}for(m=0;m<blockCount;m++){if(bc[m]==pc[i]){break;}}bc1[m]=1;bc[m]=pc[i];}}//printf("\n");}printf("LRU缺页次数为:%d\n",noPage);printf("LRU缺页率为:%.2f%%\n",(float)noPage/pageCount*100);}}voidOptiomal(intpc[],intbc[],intpageCount,intblockCount){printf("2：最佳置换算法\n");if(pageCount<=blockCount){printf("缺页次数为0\n");printf("缺页率为0\n");}else{intnoPage=0;inti,j,k;for(i=0;i<pageCount;i++){//printf("引用页：%d\n",pc[i]);if(!Travel(bc,blockCount,pc[i])){if(i<blockCount){bc[i]=pc[i];}else{intmax=0;intblockIndex;;for(j=0;j<blockCount;j++){for(k=i;k<pageCount;k++){if(bc[j]==pc[k]){break;}}if(k>=max){max=k;blockIndex=j;}}bc[blockIndex]=pc[i];}noPage++;//printf("物理快情况：\n");//Print(bc,blockCount);}//printf("\n");}