操作系统试验报告(3)

实验（二）

（页面置换）

一、问题描述：

主要包括三种典型的置换算法：最佳适用（OPT）算法，先进先出（FIFO）算法，最久未使用（URL）算法。 二、程序分析与设计： 1、基本思想

A.最佳适用算法：所选择的淘汰页是以后永不使用或者以后最长时间不需要访问的页，是一种理想化的算法，具有最好的性能，通常可以保证最低的缺页率。实现方法：利用一个与内存块相同大小的数组记录以后的重复出现的页面位置，如未出现则为最大，然后对这个数组进行比较，选出位置最大的页予以淘汰。

B．先进先出算法：总是淘汰最先进入内存的页，也就是将内存中中驻留时间最久的页面。实现方法：在内存块数组中，按顺序存入数组，依次淘汰，即最先进来的先淘汰。

C．最久未使用算法：根据页面调入内存后的使用情况进行决策，选择最近最久未使用的页面予以淘汰。实现方法：每次将页面存入内存数组栈顶，然后下面的一次向下移，在栈底位置的页面为下一次要淘汰的页。 2、结构定义

#define N 10 //页面数

int a[N],b[32]; // a[]为要调入内存的页面，b[]为内存块数组

while(f) //对内存块数组进行初始化 { for(j=0;j

b[j]=-1; } 3、算法描述 #include #include #define N 10 using namespace std;

int a[N],b[32]; //a[]为要调入内存的页面，b[]为内存块数组

void Optimal(int m) {

cout<<\ OPT\\n\

int i=0,j=0,count=0,k; while(i

算法置换

{

for(k=0;k

if(b[k]==a[i]) {

cout<<\内存中有这个页面,直接访问.\ break; }

} // 判断内存中是否有该页面.

if(k==m)

if(b[m-1]<0) //内存未满的情况// {

b[j]=a[i];

cout<

cout<<\产生\次缺页\ j++; j=j%m; }

else

{int temp[4]; //存储内存块中的页号在下一次使用的位置

int h=j;

while(a[h]!=b[0]&&h

temp[0]=h; h=j;

while(a[h]!=b[1]&&h

temp[1]=h; h=j;

while(a[h]!=b[2]&&h

temp[2]=h; h=j;

while(a[h]!=b[3]&&h

int max_x=0;//最后定位要换出的页号所在的内存号 int max=temp[0];

for(int c=0;c<4;++c) //找出要置换的页号// if(temp[c]>max) {max=temp[c];max_x=c; } count++;

cout<

cout<<\共缺页\次 缺页率为：\}

////-------------FIFO算法置---------------//// void FIFO( int m ) {

cout<<\ FIFO\\n\

算法置换