页面置换算法的实现

OS实验五(软件0967020050)2010.11.27OS实验五(软件)今日DATE\@"M/d/yyyy"1/18/2011页面置换算法的实现实验要求请用LRU和FIFO模拟教材P150页面序列，并打印出置换页面。作业序列能够动态输入内存物理块数可以动态的修改，且初始状态均为空总结收获体会及对该题解的改进意见和见解 (一)分析题意得模型(一)分析题意得模型利用数组相关知识LRU:（最近最久未使用置换算法）数组A[]数组A[],记录页面顺序70120304230321201701内存块7772

2

4440

1

1

1

000

0

0033

3

0

0

11

3

3222

2

2

7

缺页否√√√√

√

√√√√

√

√

√

M=3时:123423453数组C[],记录页面最近出现的位置数组C[],记录页面最近出现的位置701201201数组数组B[],记录内存块的页面每次找C[]值最小的页面置换FIFO(先进先出页面置换算法)与LRU相似,不过，不必设数组C来记录经历的时间,只需循环地置换第1个到第m个页面（二）写主要算法（二）写主要算法思路（三）调试运行（多种情况都要运行）（三）调试运行（多种情况都要运行）详见源程序及注释分类（四（四）体会及不足1.先找到问题思路，然后运用所学知识，用数组实现就1.先找到问题思路，然后运用所学知识，用数组实现就较为简单，问题不大。2.但同时也要注意如何使运行结果的界面更为美观。我也不知为什么，老是前两个”是否缺页”的Y与后面的Y对不齐（四）体会及不足LUR源代码：#include<stdio.h>voidmain(){ intm,i=0,j=0,j0,min,n=0,s,page,k=0,A[100],B[100],C[100],count=0; printf("请输入页框(物理块)数:"); scanf("%d",&m); printf("请输入页面顺序(以-999结束):\n"); scanf("%d",&page); while(page!=-999) { A[i]=page; i++;n++; scanf("%d",&page); } printf("\n最近最久未被使用(LRU)页面置换算法\n"); printf("\t页面顺序\t内存块\t\t是否缺页(Y/N)\n"); i=0; while(i<n) { printf("\t%d\t\t",A[i]); /*一.若内存块B[]未满,直接将页面A[]装入,C[]为所对应B[]的出现位置*/ if(i<m) { B[j]=A[i];i++; C[j]=i; j++; for(j0=0;j0<j;j0++) printf("%3d",B[j0]); printf("\t\tY\n"); count++; } /*二.若内存块B已满,分两种情况*/ else { for(j=0;j<m;j++) { if(A[i]!=B[j])k++; else break; } //1.原内存块B无此页面,找C值最小(即最近最久未使用),换出页面A// if(k==m) { min=C[0]; s=0; for(j0=0;j0<m;j0++) { if(C[j0]<min) { min=C[j0]; s=j0; } } B[s]=A[i];i++; C[s]=i; j++; for(j0=0;j0<m;j0++) printf("%3d",B[j0]); printf("\t\tY\n"); count++; } //2.原内存块B有此页面,改变B所对应的C所出现的位置,再读下一页面// else { i++;C[k]=i; printf("\n"); } k=0; } } printf("\n缺页中断数为%d总页数为%d缺页率为%.2f\n\n",count,i,(float)count/i);}FIFO源代码：#include<stdio.h>voidmain(){ intm,i=0,j=0,page,n=0,k=0,j0,j1=0,A[100],B[100],count=0; printf("请输入页框(物理块)数:"); scanf("%d",&m); printf("请输入页面顺序(以-999结束):\n"); scanf("%d",&page); while(page!=-999) { A[i]=page; i++;n++; scanf("%d",&page); } printf("\n先进先出(FIFO)页面置换算法\n"); printf("\t页面顺序\t内存块\t\t是否缺页(Y/N)\n"); i=0; while(i<n) { printf("\t%d\t\t",A[i]); /*一.若内存块B[]未满,直接将页面A[]装入*/ if(i<m) { B[j]=A[i];j++; for(j0=0;j0<j;j0++) printf("%3d",B[j0]); printf("\t\tY\n"); count++;i++; } /*二.若内存块B已满,分两种情况*/ else { for(j=0;j<m;j++) { if(A[i]!=B[j])k++; } //1.原内存块B无此页面,依次置换出页面A// if(k==m) { B[j1]=A[i];i++;j1++; for(j0=0;j0<m;j0++) printf("%3d",B[j0]); printf("\t\tY\n"); count++; if(j1==m)j1=0; }