2018-05-21

OS学习周报告-3

页面置换算法模拟-FIFO

页面置换算法是虚拟内存技术中重要的技术之一，该算法是在搜索页表发生缺页时决定哪块页面该被调出。FIFO先进先出算法是最简单的一种页面置换算法。之所以模拟这个算法是因为FIFO有一个很奇特的belady现象。

代码如下

#include <stdio.h>
typedef struct reco             //定义结构体，用来存储页面号，和缺页标记
{
  int no;
  int misspage;
}reco;
int main()
{
  int n,count,no;
  printf("请输入进程分区大小: \n");
  scanf("%d",&n);
  int que[n];                   //定义循环队列
  int size=0                    //用size记录队列中存放元素个数，用来判断循环队列，队满队空。
  int front=0,rear=0; 
  for(int i=0;i<n;i++) que[i]=0;
  printf("请输入页号序列长度：\n");
  scanf("%d",&count);
  reco page[count];                   //reco型的数组，记录每次输入页号时，当前物理块否缺页
  int block[n][count];                //用二维数组记录各物理块中存放过的页号
  for(int i=0;i<n;i++)               //初始化,i表示物理块编号，j表示页面输入时的顺序
  {   
     for(int j=0;j<count;j++)
     {
       block[i][j]=-1;
     }
  }       
  printf("请依次输入页号序列:\n");
  for(int i=0;i<count;i++)
  {
     scanf("%d",&no);
     page[i].no=no;
     for(int j=0;j<n;j++)                  //在物理块队列中查找当前输入页号，若没找到则标记缺页，反之，未缺页
     {                                     
       if(que[j]==no)  
       {
         page[i].misspage=0;
         break;
       }
       else page[i].misspage=1;
     }
     if(page[i].misspage==1)               //缺页，进行页面置换。若物理块队列不满，则将该页号插入队尾
     {                                     //未缺页，则只需记录未缺页标记即可
       if(size<n)
       {
         que[rear]=no;
         rear=(rear+1)%n;
         size++;
       }
       else                               //队列满，则将队头页号覆盖
       {
         que[rear]=no;
         rear=(rear+1)%n;
       }
       for(int k=0;k<n;k++)   block[k][i]=que[k];     //记录下缺页时页面置换后，各物理块中存储的页号
     }     
  }
  printf("访问页面");
  for(int i=0;i<count;i++) printf("%2d",page[i].no);
  printf("\n");
  for(int j=0;j<n;j++)
  {
    printf("物理块%d ",j);
    for(int k=0;k<count;k++) 
    { 
      if(block[j][k]==-1)  printf("  ");
      else printf("%2d",block[j][k]);
    }
    printf("\n");
  }
  printf("缺页否  ");
  float temp=0;
  for(int i=0;i<count;i++) 
  {
    if(page[i].misspage==1) printf(" *"),temp++;
    else printf("  ");
  }
  printf("\n缺页率:%.2f%\n",temp/count*100);
  return 1;
}

bleady现象：

物理块为3块时：

hawl29@hawl29-PC:~/Desktop/cprogram/OS_experiment$ ./fifo_execfile 
请输入进程分区大小: 
3
请输入页号序列长度：
12
请依次输入页号序列:
1
2
3
4
1
2
5
1
2
3
4
5
访问页面 1 2 3 4 1 2 5 1 2 3 4 5
物理块0  1 1 1 4 4 4 5     5 5  
物理块1  0 2 2 2 1 1 1     3 3  
物理块2  0 0 3 3 3 2 2     2 4  
缺页否   * * * * * * *     * *  
缺页率:75.00%

物理块为4块时：

hawl29@hawl29-PC:~/Desktop/cprogram/OS_experiment$ ./fifo_execfile 
请输入进程分区大小: 

4
请输入页号序列长度：
12
请依次输入页号序列:
1
2
3
4
1
2
5
1
2
3
4
5
访问页面 1 2 3 4 1 2 5 1 2 3 4 5
物理块0  1 1 1 1     5 5 5 5 4 4
物理块1  0 2 2 2     2 1 1 1 1 5
物理块2  0 0 3 3     3 3 2 2 2 2
物理块3  0 0 0 4     4 4 4 3 3 3
缺页否   * * * *     * * * * * *
缺页率:83.33%

物理块增多了，缺页率反而提高了，听起来相当反直觉，但它确实发生了，这是只有在FIFO算法中才会出现的一种现象，由Belady发现。原因据说与队列的性质有关，具体我还在查找资料。

2018-05-21

OS学习周报告-3

页面置换算法模拟-FIFO

推荐阅读更多精彩内容