在之前系列的博客中介绍了页面调度算法的原理：
    https://www.cnblogs.com/wkfvawl/p/11700301.html#_label2_3
    这里编写代码模拟一些页面调度算法的实现。

    （1）最佳淘汰算法——OPT(Optimal)
    这是Belady贝莱迪于1966年提出的一种理论上的算法。该算法每次都淘汰以后
    永不使用的，或者过最长的时间后才会被访问的页面。显然，采用这种算法会保证最低的缺页率，但它是无法实现的，因为它必须知道页面“将来”的访问情况。不过，该算法仍有一定意义，可作为衡量其他算法优劣的一个标准。
    （2）先进先出淘汰算法——FIFO
    这是最早出现的淘汰算法。
    总是淘汰最先进入内存的页面。它实现简单，只需把进程中已调入内存的页面，按先后次序链成一个队列，并设置一个所谓的替换指针，使它总是指向内存中最老的页面。
    （3） 最近最久未使用算法——(LRU, Least Recently Used）
    根据页面调入内存后的使用情况，选择内存中最久未使用的页面被置换。这是局部性原理的合理近似，性能接近最佳算法。
    OPT算法使用页面将要被访问的时间，LRU算法使用页面最后一次被访问的时间。二者唯一的差别是：OPT是向前看的，而LRU是向后看的。

    1. #include<cstdio>
    2. #include<cstring>
    3. #include<algorithm>
    4. using namespace std;
    5. int N;//进程虚页数
    6. int M;//内存块个数
    7. int page[100];//进程虚页
    8. int block[100];//内存块
    9. int weight[100];//当前内存块在后面出现的次数
    10. int success;//命中次数
    11. int fail;//未命中次数
    12. void FIFO()
    13. {
    14.     int i,j;
    15.     int flag;
    16.     int pos=0;
    17.     int success=0;
    18.     int fail=0;
    19.     for(i=0; i<N; i++)
    20.     {
    21.         flag =0;
    22.         for(j=1; j<=M; j++)
    23.         {
    24.             if(page[i]==block[j])//命中
    25.             {
    26.                 flag=1;
    27.                 success++;
    28.                 pos--;
    29.                 break;
    30.             }
    31.         }
    32.         if(flag==0)
    33.         {
    34.             fail++;
    35.             block[pos%M+1]=page[i];
    36.         }
    37.         pos++;
    38.         for(j=1; j<=M; j++)
    39.         {
    40.             printf("%d ",block[j]);
    41.         }
    42.         printf("\n");
    43.     }
    44.     printf("命中次数为：%d\n",success);
    45.     printf("未命中次数为：%d\n",fail);
    47. }
    48. void OPT()
    49. {
    50.     int i,j,k;
    51.     int flag;
    52.     int success=0;
    53.     int fail=0;
    54.     int needReplace;
    55.     for(i=0; i<N; i++)
    56.     {
    57.         flag=0;
    58.         for(j=1; j<=M; j++)
    59.         {
    60.             if(page[i]==block[j])//命中
    61.             {
    62.                 flag=1;
    63.                 success++;
    64.             }
    65.         }
    66.         if(flag==0)//未命中
    67.         {
    68.             fail++;
    69.             for(j=1; j<=M; j++) //若内存块未满，先将内存块填满
    70.             {
    71.                 if(block[j]==0)
    72.                 {
    73.                     block[j]=page[i];
    74.                     break;
    75.                 }
    76.             }
    77.             int minCnt=100;
    78.             memset(weight,0,sizeof(weight));
    79.             if(j>M)//若内存块已满，需要进行调度
    80.             {
    81.                 for(k=i+1; k<N; k++) //向后
    82.                 {
    83.                     for(j=1; j<=M; j++)
    84.                     {
    85.                         if(block[j]==page[k])
    86.                         {
    87.                             weight[j]=N-k;//越靠近，权值越大
    88.                             break;
    89.                         }
    90.                     }
    91.                 }
    92.                 for(j=1; j<=M; j++) //找权值最小的那一个
    93.                 {
    94.                     if(weight[j]<=minCnt)
    95.                     {
    96.                         minCnt=weight[j];
    97.                         needReplace=j;
    98.                     }
    99.                 }
    100.                 block[needReplace]=page[i];//替换掉权值最小的
    101.             }
    102.         }
    103.         for(j=1; j<=M; j++)
    104.         {
    105.             printf("%d ",block[j]);
    106.         }
    107.         printf("\n");
    108.     }
    109.     printf("命中次数为：%d\n",success);
    110.     printf("未命中次数为：%d\n",fail);
    111. }
    112. void LRU()
    113. {
    114.     int i,j;
    115.     int flag;
    116.     int success=0;
    117.     int fail=0;
    118.     int needReplace;
    119.     for(i=0; i<N; i++)
    120.     {
    121.         flag=0;
    122.         for(j=1; j<=M; j++)
    123.         {
    124.             if(page[i]==block[j])//命中
    125.             {
    126.                 flag=1;
    127.                 success++;
    128.             }
    129.         }
    130.         if(flag==0)//未命中
    131.         {
    132.             fail++;
    133.             for(j=1; j<=M; j++) //现将内存块填满
    134.             {
    135.                 if(block[j]==0)
    136.                 {
    137.                     block[j]=page[i];
    138.                     break;
    139.                 }
    140.             }
    141.             if(j>M)//内存块已满，需要进行调度
    142.             {
    143.                 //向前找,需要替换的页面为i-M
    144.                 needReplace=page[i-M];
    145.                 for(j=1; j<=M; j++)
    146.                 {
    147.                     if(block[j]==needReplace)//找到后替换掉
    148.                     {
    149.                         block[j]=page[i];
    150.                         break;
    151.                     }
    152.                 }
    153.             }
    154.         }
    155.         for(j=1; j<=M; j++)
    156.         {
    157.             printf("%d ",block[j]);
    158.         }
    159.         printf("\n");
    160.     }
    161.     printf("命中次数为：%d\n",success);
    162.     printf("未命中次数为：%d\n",fail);
    163. }
    164. int main()
    165. {
    166.     printf("请输入进程执行时页面访问个数：\n");
    167.     scanf("%d",&N);
    168.     printf("请输入空闲内存块的个数：\n");
    169.     scanf("%d",&M);
    170.     printf("请输入进程执行时页面访问次序：\n");
    171.     memset(page,0,sizeof(page));
    172.     memset(block,0,sizeof(block));
    173.     int i;
    174.     int needReplace;
    175.     for(i=0; i<N; i++)
    176.     {
    177.         scanf("%d",&page[i]);
    178.     }
    179.     printf("采用最佳淘汰算法OPT:\n");
    180.     OPT();
    181.     memset(block,0,sizeof(block));
    182.     printf("采用先进先出淘汰算法FIFO:\n");
    183.     FIFO();
    184.     memset(block,0,sizeof(block));
    185.     printf("采用最近最久未使用淘汰算法LRU:\n");
    186.     LRU();
    187.     return 0;
    188. }
    189. /*
    190. 12
    191. 3
    192. 2
    193. 3
    194. 2
    195. 1
    196. 5
    197. 2
    198. 4
    199. 5
    200. 3
    201. 2
    202. 5
    203. 2
    204. */