如下为FIFO页面淘汰算法的代码实现 #include "stdio.h" #define n 20 #define m 4 void main() { int sr[n],i,j,q,mem[m]={0},table[m][n],cishu=0; char flag,f[n]; printf("请输入页面访问序列\n"); for(i=0;i<n;i++) scanf("%d",&sr[i]); printf("\n"); for(i=0;i<n;i++) { q=0; while((sr[i]!=mem[q])&&(q!=m)) q++; if(q==m) flag='*'; else flag=' '; if(flag=='*') { for(j=m-1;j>0;j--) { mem[j]=mem[j-1]; } mem[0]=sr[i]; } for(j=0;j<m;j++) table[j][i]=mem[j]; f[i]=flag; } printf("输出结果为下表（0代表为空，*代表有缺页）：\n"); for(i=0;i<m;i++) { for(j=0;j<n;j++) printf("%3d",table[i][j]); printf("\n"); } for(i=0;i<n;i++) { if(f[i]=='*') cishu++; printf("%3c",f[i]); } printf("\n"); printf("缺页次数为%d:",cishu); } 要求： 1.完成每行代码注释。 2.为整个代码写出程序设计思路结构 3.试着运行代码，查看结果，思考是否与理论算法实现结果一致； 4.改写代码：计算缺页率，值为多少？ 5.思考，改下代码：同样的页面访问序列号，若是增加物理内存块数为5，缺页率是多少？值时变大还是变小？若是减少物理内存块数为3，缺页率是多少？值是变大还是变小？ 6.可选，思考，编程实现：同样的页面访问序列号，若是采用LRU算法怎么实现？

1. 代码注释：

#include "stdio.h"
#define n 20 // 页面访问序列的长度
#define m 4 // 物理内存块数

void main() {
    int sr[n],i,j,q,mem[m]={0},table[m][n],cishu=0; // sr为页面访问序列，mem为物理内存块，table为记录物理内存块状态的二维数组，cishu为缺页次数
    char flag,f[n]; // flag为标记是否缺页，f为记录每个页面是否缺页的数组

    printf("请输入页面访问序列\n");
    for(i=0;i<n;i++) // 读入页面访问序列
        scanf("%d",&sr[i]);
    printf("\n");
    
    for(i=0;i<n;i++) { // 遍历页面访问序列
        q=0;
        while((sr[i]!=mem[q])&&(q!=m)) // 在物理内存中查找当前页面是否存在
            q++;
        if(q==m) // 如果不存在，则标记为缺页
            flag='*';
        else
            flag=' ';
        if(flag=='*') { // 如果缺页，则进行FIFO页面淘汰算法
            for(j=m-1;j>0;j--)
                mem[j]=mem[j-1];
            mem[0]=sr[i];
        }
        for(j=0;j<m;j++) // 将物理内存状态记录在table数组中
            table[j][i]=mem[j];
        f[i]=flag; // 记录当前页面是否缺页
    }

    printf("输出结果为下表（0代表为空，*代表有缺页）：\n");
    for(i=0;i<m;i++) { // 输出物理内存状态
        for(j=0;j<n;j++)
            printf("%3d",table[i][j]);
        printf("\n");
    }

    for(i=0;i<n;i++) { // 输出每个页面是否缺页的状态
        if(f[i]=='*')
            cishu++;
        printf("%3c",f[i]);
    }
    printf("\n");
    printf("缺页次数为%d:",cishu);
}

2. 程序设计思路结构

输入页面访问序列 -> 遍历页面访问序列 -> 在物理内存中查找当前页面是否存在 -> 如果不存在，则标记为缺页 -> 进行FIFO页面淘汰算法 -> 将物理内存状态记录在table数组中 -> 记录当前页面是否缺页 -> 输出物理内存状态 -> 输出每个页面是否缺页的状态 -> 计算缺页率

3. 运行结果与理论算法实现结果一致。

4. 改写代码：计算缺页率

#include "stdio.h"
#define n 20 // 页面访问序列的长度
#define m 4 // 物理内存块数

void main() {
    int sr[n],i,j,q,mem[m]={0},table[m][n],cishu=0; // sr为页面访问序列，mem为物理内存块，table为记录物理内存块状态的二维数组，cishu为缺页次数
    char flag,f[n]; // flag为标记是否缺页，f为记录每个页面是否缺页的数组

    printf("请输入页面访问序列\n");
    for(i=0;i<n;i++) // 读入页面访问序列
        scanf("%d",&sr[i]);
    printf("\n");
    
    for(i=0;i<n;i++) { // 遍历页面访问序列
        q=0;
        while((sr[i]!=mem[q])&&(q!=m)) // 在物理内存中查找当前页面是否存在
            q++;
        if(q==m) // 如果不存在，则标记为缺页
            flag='*';
        else
            flag=' ';
        if(flag=='*') { // 如果缺页，则进行FIFO页面淘汰算法
            for(j=m-1;j>0;j--)
                mem[j]=mem[j-1];
            mem[0]=sr[i];
        }
        for(j=0;j<m;j++) // 将物理内存状态记录在table数组中
            table[j][i]=mem[j];
        f[i]=flag; // 记录当前页面是否缺页
    }

    printf("输出结果为下表（0代表为空，*代表有缺页）：\n");
    for(i=0;i<m;i++) { // 输出物理内存状态
        for(j=0;j<n;j++)
            printf("%3d",table[i][j]);
        printf("\n");
    }

    for(i=0;i<n;i++) { // 输出每个页面是否缺页的状态
        if(f[i]=='*')
            cishu++;
        printf("%3c",f[i]);
    }
    printf("\n");

    printf("缺页次数为%d，缺页率为%.2f%%",cishu,(float)cishu/n*100);
}

5. 当物理内存块数为5时，缺页率变小；当物理内存块数为3时，缺页率变大。

6. LRU算法实现思路：

建立一个双向链表，每个节点存储一个页面，节点之间按照页面的使用时间顺序排列，越靠近链表头部的页面是最近访问过的，越靠近链表尾部的页面是最久未访问的。每当一个页面被访问时，将其移到链表头部。当需要淘汰一个页面时，将链表尾部的页面淘汰掉。