页面置换算法实验报告_16281100_雷兵

页面置换算法实验报告

1实验题目

设计和实现最佳置换算法、先进先出置换算法、最近最久未使用置换算法、页面缓冲置换算法；通过页面访问序列随机发生器实现对上述算法的测试及性能比较。

2实验要求

假设前提

模拟的虚拟内存的地址为16位，页面大小为1K，模拟的物理内存有32K；
页表用整数数组或结构数组来表示；
页面访问序列串是一个整数序列，整数的取值范围为0到N - 1。页面访问序列串中的每个元素p表示对页面p的一次访问。

性能测评及问题说明

测试不同的页面访问序列及不同的虚拟内存尺寸，并从缺页率、算法开销等方面对各个算法进行比较。（同时请给出在给定页面访问序列的情况下，发生页面置换次数的平均值）

3概要设计

3.1模块设计

总模块图

3.2功能

随机访问序列生成

确定虚拟内存的尺寸N，工作集的起始位置p，工作集中包含的页数e，工作集移动率m（每处理m个页面访问则将起始位置p +1），以及一个范围在0和1之间的值t；
生成m个取值范围在p和p + e间的随机数，并记录到页面访问序列串中；
生成一个随机数r，0 ≤ r ≤ 1；
如果r < t，则为p生成一个新值，否则p = (p + 1) mod N；
如果想继续加大页面访问序列串的长度，请返回第2步，否则结束。

最佳置换算法OPT

选择永不使用或是在最长时间内不再被访问（即距现在最长时间才会被访问）的页面淘汰出内。

先进先出置换算法FIFO

选择最先进入内存即在内存驻留时间最久的页面换出到外存。

进程已调入内存的页面按进入先后次序链接成一个队列，并设置替换指针以指向最老页面。

最近最久未使用置换算法LRU

以“最近的过去”作为“最近的将来”的近似，选择最近一段时间最长时间未被访问的页面淘汰出内存。

改进型Clock置换算法CLO

① 从查寻指针当前位置起扫描内存分页循环队列，选择A=0且M=0的第一个页面淘汰；若未找到，转②

② 开始第二轮扫描，选择A=0且M=1的第一个页面淘汰，同时将经过的所有页面访问位置0；若不能找到，转①

4详细设计

4.1程序流程

程序总流程图

先进先出页面置换算法流程图

最近久未使用置换算法流程图

最佳置换算法流程图

改进型Clock置换算法流程图

4.3程序代码

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<stdlib.h>
#include<time.h>
#define N 64   //虚拟内存大小
#define MAX 2000    //引用串的长度
#define P 32  //物理内存大小

using namespace std;
int result;  //置换次数
int RS[100] = {};  //RS串
int M[P] = {0};   // 物理内存大小

void PRS()
{
 int p = 1;//工作集的起始位置p
 int e = 40;//工作集中包含的页数e
 int m = 64;//工作集移动率m
 double t = 0.5;
 int judge = 1;
 int count = 0;
 double r;
 while(judge == 1)
 {
  srand((unsigned)time(NULL));
  for(int i = 0;i < m;i++)
  {
   RS[count] = rand()%e+p;
   count++;
  }
  r = (rand()%9+1)/10;
  if(r < t)
  {
   p = rand()%N+1;
  }
  else
  {
   p = (p+1)%N;
  }
  if(count >= MAX){
            printf("以下是生成的引用串:\n");
            for(int i = 0;i < count;i++)
            {
                printf("%d ",RS[i]);
            }
            printf("\n");
            break;
  }
 }
}

void print(int c)
{
 printf("以下为物理内存情况：\n");
 for(int i = 0;i < c;i++)
 {
  printf("%d ",M[i]);
 }
 printf("\nend**********************\n");
}

//判断物理内存是否已满
int full(int c,int j)
{
 int judge = 0;
 for(int i = 0;i < c;i++)
 {
  if(RS[j] == M[i])
  {
   judge = 1;
   break;
  }
 }
 if(!judge)
 {
  M[c] = RS[j];
  c++;
 }
 return c;
}

//判断是否为缺页
int lack(int c, int j)
{
 int judge = 0;
 for(int i = 0;i < c;i++)
 {
  if(RS[j] == M[i])
  {
   judge = 1;
   break;
  }
 }
 return judge;
}


//最佳置换算法
int OPT()
{
 result = 0;
 int count = 0;
 for(int j = 0;j < MAX;j++)
 {
  int judge = 0;
  if(count < P)
  {
   count = full(count,j);
  }
  else
  {
   int number;
   judge = lack(count,j);
   if(!judge)   //没有找到，需进行置换
   {
    result++;
    int s;  //用于存放没有找到的页面的数组下标
    for(int k = 0;k < count;k++)
    {
     number = -1;
     for(int i = j+1;i < MAX;i++)
     {
      if(M[k] == RS[i])
      {
       if(number < i)
       {
        number = i;
        s = k;
       }
       break;
      }
     }
     //没有找到，说明此页面不会再被使用，所以直接进行替换
     if(number == -1)
     {
      s = k;
      break;
     }
    }
    M[s] = RS[j];
   }
  }
 }
 return result;
}

//先进先出置换算法
int FIFO()
{
 result = 0;
 int p = 0;
 int count = 0;
 for(int j = 0;j < MAX;j++)
 {
  int judge = 0;
  if(count < P)
  {
   count = full(count,j);
  }
  else
  {
   //判断是否是缺页
   judge = lack(count,j);
   //是缺页，进行置换
   if(!judge)
   {
    result++;
    M[p] = RS[j];
    p = (p+1)%P;
   }
  }
 }
 return result;
}

//最近最久未使用置换算法
int LRU()
{
 result = 0;
 int a[P];  //辅组数组,队尾为最近访问页面
 int count = 0;
 for(int j = 0;j < MAX;j++)
 {
  int judge = 0;
  if(count < P)
  {
   for(int i = 0;i < count;i++)
   {
    if(RS[j] == M[i])
    {
     judge = 1;
     //将页面提到队尾
     int change = M[i];
     for(int k = i;k < count-1;k++)
     {
      a[k] = a[k+1];
     }
     a[count-1] = change;

     break;
    }
   }
   if(!judge)
   {
    a[count] = RS[j];
    M[count] = RS[j];
    count++;
   }
  }
  else
  {
   //判断是否是缺页
   for(int i = 0;i < count;i++)
   {
    if(RS[j] == M[i])
    {
     judge = 1;
     //将页面提到队首
     int change = M[i];
     for(int k = i;k < P-1;k++)
     {
      a[k] = a[k+1];
     }
     a[P-1] = change;

     break;
    }
   }
   //是缺页，进行置换
   if(!judge)
   {
    result++;
    for(int i = 0;i < P;i++)
    {
     if(a[0] == M[i])
     {
      M[i] = RS[j];
      for(int k = 0;k < P-1;k++)
      {
       a[k] = a[k+1];
      }
      a[P-1] = RS[j];

      break;
     }
    }
   }
  }
 }
 return result;
}

//Clock置换算法
int CLO()
{
 result = 0;
 int p = 0;
 int a[MAX];   //辅助数组
 int count = 0;
 for(int j = 0;j < MAX;j++)
 {
  int judge = 0;
  if(count < P)
  {
   for(int i = 0;i < count;i++)
   {
    if(M[i] == RS[j])
    {
     a[i] == 1;
     judge = 1;
     break;
    }
   }
   if(!judge)
   {
    a[count] = 1;
    M[count] = RS[j];
    count ++;
   }
  }
  else
  {
   for(int i = 0;i < count;i++)
   {
    if(M[i] == RS[j])
    {
     judge = 1;
     a[i] = 1;
     break;
    }
   }
   //是缺页，进行置换
   if(!judge)
   {
    result++;
    while(1)
    {
     if(a[p] == 1)
     {
      a[p] = 0;
      p = (p+1)%P;
     }
     else
     {
      a[p] = 1;
      M[p] = RS[j];
      p = (p+1)%P;
      break;
     }
    }
   }
  }
 }
 return result;
}

int main()
{
 int condition = 1;
 while(condition)
 {
  //先调用函数生成引用串
  PRS();

  //对于生成的引用串用各个算法进行效率的测试
  char a[4][30] = {"最佳置换算法","先进先出置换算法",\
          "最近最久未使用置换算法","Clock置换算法"};
  int r[5];
  r[0] = OPT();
  r[1] = FIFO();
  r[2] = LRU();
  r[3] = CLO();
  printf("\n****************************\n");
  printf("最终结果:\n");
  for(int i = 0;i < 4;i++)
  {
      double q=(float)r[i]/MAX;
   printf("%s置换次数:%d,缺页率：%.3f\n",a[i],r[i],q);
  }
  printf("1.继续;\n");
  printf("0.退出;\n");
  scanf("%d",&condition);
 }
 return 0;
}