湖南师范大学树达学院

操作系统课程实验报告

题目   编程模拟页面置换算法  

理工系09级电子商务专业

姓名           学号       

指导教师       张楚才      

2011年 5 月 5 日

实验题目：编程模拟页面置换算法

实验要求：

利用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>

void Print(int bc[],int blockCount)  

{  

    for(int i=0;i<blockCount;i++)  

    {  

        printf("%d ",bc[i]);  

    }  

   printf("\n"); 

}  

 

bool Travel(int bc[],int blockCount,int x)  

{  

    bool is_found=false;  

    int i;  

    for(i=0;i<blockCount;i++)  

    {  

        if(bc[i]==x)  

        {  

            is_found=true;  

            break;  

        }  

    }  

    return is_found;  

}  

 

void FIFO(int pc[],int bc[],int pageCount,int blockCount)  

{  

    printf("0：FIFO置换算法\n");  

    int i;  

    if(pageCount<=blockCount)  

    {  

        printf("缺页次数为0\n");

        printf("缺页率为0\n");  

    }  

    else 

    {  

        int noPage=0;  

        int p=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);  

    }  

}  

 

int FoundMaxNum(int a[],int n)  

{  

    int k,j;  

    k=a[0];  

    j=0;  

    for (int i=0;i<n;i++)  

    {  

        if(a[i]>=k)  

        {  

            k=a[i];  

            j=i;  

        }  

    }  

    return j;  

}  

 

void LRU(int pc[],int bc[],int pageCount,int blockCount)  

{  

    printf("1：LRU置换算法\n");  

    if(pageCount<=blockCount)  

    {  

      printf("缺页次数为0\n");

       printf("缺页率为0\n");   

    }  

    else 

    {  

        int noPage=0;  

        int i,j,m;  

        int bc1[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(int p=0;p<=i;p++)  

                    {  

                        bc1[p]++;  

                    }  

                }  

                else 

                {  

                    for(j=0;j<blockCount;j++)  

                    {  

                        bc1[j]++;  

                    }  

                    int k=FoundMaxNum(bc1,blockCount);  

                    bc[k]=pc[i];  

                    bc1[k]=1;  

                       

                }  

                noPage++;  

                //printf("物理快情况：\n");  

                //Print(bc,blockCount);  

            }  

            else if(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);  

    }  

}  

 

void Optiomal(int pc[],int bc[],int pageCount,int blockCount)  

{  

    printf("2：最佳置换算法\n");  

    if(pageCount<=blockCount)  

    {  

       printf("缺页次数为0\n");

        printf("缺页率为0\n");  

    }  

    else 

    {  

        int noPage=0;  

        int i,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 

                {  

                    int max=0;  

                    int blockIndex;;  

                    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");

        }  

        printf("OPT缺页次数为:%d\n",noPage);  

        printf("OPT缺页率为:%.2f%%\n",(float)noPage/pageCount*100);  

    }  

}  

 

int main()  

{  

    int pageCount,blockCount,i,pc[100];  

    printf("输入页面数\n");  

    scanf("%d",&pageCount);    

    printf("输入页面走向\n");  

    for(i=0;i<pageCount;i++)  

    {  

      scanf("%d",&pc[i]);  

    }  

    blockCount=3;//物理块数  

            int bc1[100];  

   printf("\n");

            FIFO(pc,bc1,pageCount,blockCount);  

            int bc2[100];  

   printf("\n");

            LRU(pc,bc2,pageCount,blockCount);  

            int bc3[100]; 

   printf("\n");

            Optiomal(pc,bc3,pageCount,blockCount);     

    return 0;  

}

 

第二篇：《操作系统》实验五：页面置换算法模拟

                                  实验五. 请求页式存储管理的模拟

[实验内容]:

熟悉虚拟存储管理的各种页面置换算法，并编写模拟程序实现请求页式存储管理的页面置换算法----最近最久未使用算法（LRU），要求在每次产生置换时显示页面分配状态和缺页率。

[实验要求]：

1、运行给出的实验程序，查看执行情况，进而分析算法的执行过程，在理解FIFO页面置换算法和最近最久未使用算法（LRU）置换算法后，给出最佳置换算法的模拟程序实现，并集成到参考程序中。

2、执行2个页面置换模拟程序，分析缺页率的情况。最好页框数和访问序列长度可调节，在使用同一组访问序列数据的情况下，改变页框数并执行2个页面置换模拟程序，查看缺页率的变化。

3、在每次产生置换时要求显示分配状态和缺页率。程序的地址访问序列通过随机数产生，要求具有足够的长度。最好页框数和访问序列长度可调节。

实验的执行结果如下图所示（左下图为FIFO执行结果，右下图为LRU执行结果）：

       

程序源代码：

#include <libio.h>

#include "windows.h"

#include <conio.h>

#include <stdlib.h>

#include <fstream.h>

#include <io.h>

#include <string.h>

#include <stdio.h>

void initialize();    //初始化相关数据结构

void createps();      //随机生成访问序列

void displayinfo();   //显示当前状态及缺页情况

void fifo();          //先进先出算法

int  findpage();      //查找页面是否在内存

void lru();           //最近最久未使用算法

int   invalidcount = 0;   // 缺页次数

int   vpoint;             //页面访问指针

int   pageframe[10];      // 分配的页框

int   pagehistory[10];    //记录页框中数据的访问历史

int   rpoint;             //页面替换指针

int   inpflag;            //缺页标志，0为不缺页，1为缺页

struct PageInfo       //页面信息结构

{

   int  serial[100];  // 模拟的最大访问页面数，实际控制在20以上

   int  flag;         // 标志位，0表示无页面访问数据

   int  diseffect;    // 缺页次数

   int  total_pf;     // 分配的页框数

   int  total_pn;     // 访问页面序列长度

} pf_info;

////////////////////////////////////////////////////////////////////////

//初始化相关数据结构

void initialize()                       

{

    int i,pf;

    inpflag=0;              //缺页标志，0为不缺页，1为缺页

    pf_info.diseffect =0;   // 缺页次数

    pf_info.flag =0;        // 标志位，0表示无页面访问数据

    printf("\n请输入要分配的页框数：");   // 自定义分配的页框数

    scanf("%d",&pf);

    pf_info.total_pf =pf;   

    for(i=0;i<100;i++)   // 清空页面序列

    {

       pf_info.serial[i]=-1;

    }

}

///////////////////////////////////////////////////////////////////

// 随机生成访问序列

void createps(void )

{

    int s,i,pn;

    initialize();     //初始化相关数据结构

    printf("\n请输入要随机生成访问序列的长度：");   //自定义随机生成访问序列的长度

    scanf("%d",&pn);

    srand(rand());    //初始化随机数队列的"种子"

    s=((float) rand() / 32767) * 50 + pn;   // 随机产生页面序列长度

    pf_info.total_pn = s;

    for(i=0;i<s;i++)    //产生随机访问序列

    { 

        pf_info.serial[i]=((float) rand() / 32767) * 16 ;   //随机数的大小在0-15之间       

    }  

}

////////////////////////////////////////////////////////////////////////

//  显示当前状态及缺页情况

void displayinfo(void)

{ 

   int i,n;

   if(vpoint==0)

   {  

       printf("\n=============页面访问序列=============\n");

       for(i=0; i<pf_info.total_pn; i++)

       {  

           printf("%4d",pf_info.serial[i]);

           if ((i+1) % 10 ==0) printf("\n");   //每行显示10个                 

       }

       printf("\n======================================\n");

   }

   printf("访问%3d : 内存<",pf_info.serial[vpoint]);

   for(n=0;n<pf_info.total_pf;n++)     // 页框信息

   {

      if (pageframe[n] >=0)

         printf("%3d",pageframe[n]);

      else

         printf("   ");

   }

   printf(" >");

   if(inpflag==1)     //缺页标志，0为不缺页，1为缺页

   {

       printf(" ==>缺页 ");

       printf("缺页率%3.1f",(float)(pf_info.diseffect)*100.00/vpoint);

   }

   printf("\n");

}

////////////////////////////////////////////////////////////////////////

// 查找页面是否在内存，1为在内存，0为不在即缺页

int findpage(int page)

{

    int n;

    for(n=0;n<pf_info.total_pf;n++)

    {

        pagehistory[n] ++;   // 访问历史加1

    }

    for(n=0;n<pf_info.total_pf;n++)

    {

      if (pageframe[n]==page )

      { 

          inpflag=0 ;    //inpflag缺页标志，0为不缺页，1为缺页   

          pagehistory[n]=0;   //置访问历史为0

          return 1;

      }

    }

    inpflag=1;      //页面不存在，缺页

    return 0;     

}

////////////////////////////////////////////////////////////////////////

//  FIFO页面置换算法

void fifo(void)

{

  int n,count,pstate; 

  rpoint=0;          // 页面替换指针初始化为0

  invalidcount = 0;  // 缺页数初始化为0

  createps();        // 随机生成访问序列

  count=0;           // 是否装满是所有的页框

  for(n=0;n<pf_info.total_pf;n++) // 清除页框信息

  {

    pageframe[n]=-1;

  }

  inpflag=0;   //缺页标志，0为不缺页，1为缺页

  for(vpoint=0;vpoint<pf_info.total_pn;vpoint++)  // 执行算法

  {    

      pstate=findpage(pf_info.serial[vpoint]);  //查找页面是否在内存

      if(count<pf_info.total_pf)    // 开始时不计算缺页

      {

        if(pstate==0)    // 页不存在则装入页面

        {

            pageframe[rpoint]=pf_info.serial[vpoint];              

            rpoint=(rpoint+1) % pf_info.total_pf;              

            count++;

        }          

      }

      else      // 正常缺页置换

      {

          if(pstate==0)    // 页不存在则置换页面

          {

                pageframe[rpoint]=pf_info.serial[vpoint];              

                rpoint=(rpoint+1) % pf_info.total_pf;                  

                pf_info.diseffect++;     // 缺页次数加1                        

           }

      }

      Sleep(10); 

      displayinfo();       // 显示当前状态

  } // 置换算法循环结束

  getch();

  return;

}

///////////////////////////////////////////////////////////////////

//  LRU页面置换算法

void lru(void)                                                                    

{

  int n,count,pstate,max; 

  rpoint=0;          // 页面替换指针

  invalidcount = 0;  // 缺页次数初始化为0

  createps();        // 随机生成访问序列

  count=0;           // 是否装满所有的页框

  for(n=0;n<pf_info.total_pf;n++)

  {

      pageframe[n]=-1;    // 清除页框信息

      pagehistory[n]=0;   // 清除页框历史

  }

  inpflag=0;    //缺页标志，0为不缺页，1为缺页

  for(vpoint=0;vpoint<pf_info.total_pn;vpoint++)  // 执行算法

  {  

      pstate=findpage(pf_info.serial[vpoint]);  //查找页面是否在内存

      if(count<pf_info.total_pf)   // 开始时不计算缺页

      {  

         if(pstate==0)   // 页不存在则装入页面

         {

            pageframe[rpoint]=pf_info.serial[vpoint]; //把要调入的页面放入一个空的页框里

            rpoint=(rpoint+1) % pf_info.total_pf;  

            count++;

         }  

      }

      else // 正常缺页置换

      {

          if(pstate==0)// 页不存在则置换页面

          {

            max=0;

             for(n=1;n<pf_info.total_pf;n++)

             {

                if(pagehistory[n]>pagehistory[max])

                {

                   max=n;

                }

             }

             rpoint=max;

             pageframe[rpoint]=pf_info.serial[vpoint]; 

             pagehistory[rpoint]=0;

             pf_info.diseffect++;  // 缺页次数加1              

          }

        }

       Sleep(10);

       displayinfo();    // 显示当前状态

  }     // 置换算法循环结束

   _getch();

   return;

}

  

///////////////////

//最佳置换算法

   自己完成

///////////////////////////////////////////////////////////////////

//  主函数

int main()

{

  char ch;

  system("cls") ;

  while ( true )                           

  {

    printf("*******************************************\n");

    printf("     若要执行FIFO页面置算法请按1\n");

    printf("     若要执行LRU 页面置算法请按2\n");

    printf("     若要退出请按3\n") ;

    printf("*******************************************\n");

    printf( "Enter your choice (1 or 2 or 3): "); 

    do

    {   //如果输入信息不正确，继续输入

        ch = (char)getch() ;

    }while(ch != '1' && ch != '2'&& ch != '3');

    printf("\n\n你按的是：%c ,现在为你执行对应操作。",ch);

    if(ch == '3') //选择3，退出

    {

       return 0;

    }

    else

    {

        if(ch == '1')  //选择1，FIFO

        {

           printf("\n\n----------*****执行FIFO算法*****-----------\n");

           fifo();

        }

        else

        {

           printf("\n\n----------*****执行LRU算法*****----------\n");

           //lru();

        }

    }

    system("cls") ;

  }

  printf("\n\nPress Any Key To Continue:");

  getch() ;

  return 0;

}