操作系统 采用FIFO页面置换算法,当页面的顺序为 0 1 2 3 0 1 4 0 1 2 3 4 时,m=3和m=4时,缺页中断的次数各为多少?

采用FIFO页面置换算法,当页面的顺序为 0 1 2 3 0 1 4 0 1 2 3 4 时,m=3和m=4时,缺页中断的次数各为多少?

典型的Belady
一个9次，一个10次

• 以下回答由chatgpt基于相关博客总结生成:

  当m值为3时，缺页中断的次数为4；当m值为4时，缺页中断的次数为5。

  解决方案：

  FIFO页面置换算法就是按照被调入内存的页面的先后次序来调置物理块，将最早进入内存的页面先置换出去，由新调入的页面占用这个物理块。

  首先需要先定义结构体MemSchedule，用于存储内存访问序列和内存块大小等信息：

  typedef struct {
      int seq; // 内存块号
      int priority; // 优先级
  }MemBlock;
  
  typedef struct {
      int *VisitSeq; // 内存访问序列
      int length; // 序列长度
      MemBlock *WorkSpace; // 内存块大小
      int work_len; // 内存块数
      int e; // 内存块大小
      int change; // 是否发生了换页
  }MemSchedule;
  

  使用FIFO算法来统计缺页中断的次数，可以定义Fifo()函数，具体实现如下：

  int Fifo(MemSchedule s1)
  {
      clock_t start, finish;
      start = clock();
      int miss = 0;
      printf("***************先入先出算法*****************\n");
      printf("seq\t");
      for (int i = 0; i<s1.e; i++)
      {
          printf("%d\t", i + 1);
      }
      printf("\n");
      for (int i = 0; i<s1.length; i++)
      {
          int pointer = s1.VisitSeq[i];
          printf("%d:\t", pointer);
          if (s1.work_len<s1.e)
          {
              int flag = 0;
              for (int m = 0; m<s1.work_len; m++)
              {
                  s1.WorkSpace[m].priority--;
                  if (s1.WorkSpace[m].seq == pointer)
                  {
                      flag = 1;
                      s1.WorkSpace[m].priority = s1.e;
                  }
              }
              if (flag == 1)
              {
                  s1.change = -1;
              }
              if (flag == 0)
              {
                  s1.WorkSpace[s1.work_len].seq = pointer;
                  s1.WorkSpace[s1.work_len].priority = s1.e;
                  s1.change = s1.work_len;
                  s1.work_len++;
              }
              for (int k = 0; k<s1.work_len; k++)
              {
                  if (k == s1.change)
                  {
                      printf("%d@\t", s1.WorkSpace[k].seq);
                      miss++;
                  }
                  else
                      printf("%d\t", s1.WorkSpace[k].seq);
              }
              for (int j = 0; j<s1.e - s1.work_len; j++)
              {
                  printf("*\t");
              }
  
  
          }
          else
          {
              int flag = 0;
              for (int m = 0; m<s1.work_len; m++)
              {
                  s1.WorkSpace[m].priority--;
                  if (s1.WorkSpace[m].seq == pointer)
                  {
                      flag = 1;
                      s1.WorkSpace[m].priority = s1.e;
  
                  }
              }
              if (flag == 1)
              {
                  s1.change = -1;
              }
              if (flag == 0)
              {
                  int min_pri = 0xffffff;
                  for (int m = 0; m<s1.work_len; m++)
                  {
                      int n = s1.WorkSpace[m].priority;
                      if (n < min_pri)
                      {
                          s1.change = m;
                          min_pri = n;
                      }
                  }
                  s1.WorkSpace[s1.change].seq = pointer;
                  s1.WorkSpace[s1.change].priority = s1.e;
              }
              for (int m = 0; m<s1.e; m++)
              {
                  if (m == s1.change)
                  {
                      printf("%d@\t", s1.WorkSpace[m].seq);
                      miss++;
                  }
                  else
                      printf("%d\t", s1.WorkSpace[m].seq);
              }
  
  
          }
          printf("\n");
      }
      finish = clock();
      printf("******************算法评估**************\n");
      printf("缺页率:\t%.2f %%\n", (miss*1.0) / s1.length * 100);
      printf("时间开销:\t%.2f ms\n", (double)(finish - start));
      free(s1.WorkSpace);
      free(s1.VisitSeq);
      return  0;
  }
  

  最后调用Fifo()函数计算缺页中断的次数即可：

      int VisitSeq[] = { 0, 1, 2, 3, 0, 1, 4, 0, 1, 2, 3, 4 };
      int size = sizeof(VisitSeq) / sizeof(VisitSeq[0]);
      MemBlock *WorkSpace;
      WorkSpace = (MemBlock*)malloc(m * sizeof(MemBlock));
      for (int i = 0; i < m; i++) {
          WorkSpace[i].seq = -1;
          WorkSpace[i].priority = 0;
      }
      MemSchedule s1 = { VisitSeq, size, WorkSpace, 0, m, -1 };
      Fifo(s1);
  

  完整代码如下：