操作系统之页面置换算法（最佳置换OPT，先进先出FIFO，最近最久未使用LRU）

  1 #include <iostream>
  2 #include <stdio.h>
  3 #include <stdlib.h>
  4 #define N 12
  5 #define B 3
  6 using namespace std;
  7 
  8 int pageArr[N]={1,2,3,4,1,2,5,1,2,3,4,5};//页面走向
  9 int block[B]={0};//物理块3个，其数值是页号
 10 typedef struct FLAG {
 11     int flags[B];
 12     int counts;
 13 } FLAG;
 14 
 15 void opt(int pageArr[],int block[]);
 16 int inBlock(int which);
 17 int findFar(int next);
 18 void Replace(int index,int value);
 19 void disPlay();
 20 
 21 int main(void){
 22     cout << "begin:" <<endl;
 23     opt(pageArr,block);
 24     cout << "end!" <<endl;
 25 return 0;
 26 }
 27 
 28 void opt(int pageArr[],int block[]){
 29     int getIndex;
 30     for(int i=0;i<N;i++){
 31         if(i<3){//前3页号#短缺#进队列
 32             block[i]=pageArr[i];
 33             printf("缺页：(null)-->%d\n",pageArr[i]);
 34         }
 35         else {
 36             if(i==3){
 37                 disPlay();
 38 
 39             }
 40             if(inBlock(pageArr[i])!=-1){//下一个页面if在物理块中返回index并跳过,反-1
 41                 disPlay();
 42 
 43                 continue;
 44             }
 45             getIndex=findFar(i+1);//从下一个页号，找到最远出现的页面,替换的下标
 46             if(getIndex==-1){
 47                 cout<<"error,not replace obj!"<<‘\t‘;
 48             }
 49             else{
 50                 Replace(getIndex,pageArr[i]);//由下标找到上一组替换目标，用第二参数替换
 51                 disPlay();
 52 
 53             }
 54         }
 55     }
 56 return;
 57 }
 58 
 59 //替换block中的物理块
 60 void Replace(int index,int value){
 61     printf("缺页：%d--被替换为-->%d\n",block[index],value);
 62     block[index]=value;
 63 return;
 64 }
 65 
 66 
 67 //找到最远出现的页面
 68 int findFar(int next){
 69     int index=-1;//error，默认返回不存在的索引
 70     FLAG myflag;
 71     myflag.flags[0]=0;
 72     myflag.flags[1]=0;
 73     myflag.flags[2]=0;
 74     myflag.counts=0;
 75     int stop = N-next;
 76     while(stop--){
 77         index=inBlock(pageArr[next++]);
 78         if(index!=-1){
 79             myflag.flags[index]=1;
 80             myflag.counts++;
 81         }
 82         else if(myflag.counts==B-1){//有2个不缺值时
 83             break;
 84         }
 85     }
 86     for(index=0;index<B;index++){
 87         if(myflag.flags[index]==0)
 88             break;
 89     }
 90 return index;
 91 }
 92 
 93 
 94 //下一个页面if在物理块中返回index,反-1
 95 int inBlock(int which){
 96     //int i=0;
 97     //while(i<B)
 98     //    if(block[i++]==which)
 99     //    return i-1;
100     for(int i=0;i<B;i++){
101         if(block[i]==which)
102             return i;
103     }
104 return -1;
105 }
106 
107 //打印一元组
108 void disPlay(){
109     int i=0;
110     while(i<B){
111         printf("%d\t",block[i++]);
112     }
113     printf("\n");
114 return;
115 }