操作系统 设计和实现最佳页面置换算法，并统计缺页中断率。

//偶尔看到同学的笔记以文章的形式记录，觉得很是不错，被论为是盲目跟风，或是急功近利、抄来抄去亦可    反正是做给自己的，那就不妨大胆一些。

好了，这次有废话多了，以后就不会了

实验内容

为进程分配物理块，其次输入页面引用串

设计和实现最佳置换算法，并统计缺页率。

设系统为某一进程分配了3个物理块，引用串为：

7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1

设计和实现最佳置换算法，并统计缺页率。

最佳置换算法：一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，那么如果发生缺页中断时，就将该页面换出，以便存放后面调入内存中的页面

由于要预知剩余序列的页面 这种算法目前为理想状态化 并没有具体实现

#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define MAX 20   // 作业序列的最大长度
#define num_alloacte 3       //内存分配给进程的物理块数  ， 也就是同一时刻最多有几个页面可以在内存中

int work_list[MAX];        //存储作业序列
int num;        //存储要输入的序列的长度
int sum=0;      //用来记录缺页数
int memory_alloacte[num_alloacte];   // 现在在进程中的页面序列

int current; // 记录已经分配的作业的下标

void input() {       //初始化作业序列  , 以及内存分配给进程的物理块数
    printf("请输入作业的个数:");
    cin>>num;
    if (num > MAX) {
        printf("序列过长");
        return;
    }
    printf("请输入作业序列：n");
    for (int i = 0; i < num; i++) {
        cin>>work_list[i];
    }
    for (int i = 0; i < MAX; i++) {
        memory_alloacte[i] = -1;
    }
    for (int i = 0; i < num_alloacte; i++) {
        memory_alloacte[i] = work_list[i];
        current = i;
    }
}

void print(int* work_list, int* memory_alloacte) {
    printf("t现在进程中的页面序列：");
    for (int i = 0; i < num_alloacte; i++) {
        printf("%3dt", *(memory_alloacte + i));
    }
    printf("tt当前剩余的作业序列:");
    for (int i = current + 1; i < num; i++) {
        printf("%3d", *(work_list + i));
    }
    printf("n");
}

int judge() {
    int temp[num_alloacte];            //赋值一个临时变量 记录此时物理框中的作业号
    int count = num_alloacte;           //记录临时变量物理框中还剩下的个数
    for (int i = 0; i < num_alloacte; i++) {
        temp[i] = memory_alloacte[i];
    }
    int cur = current + 1;
    while (cur < num)
    {
        for (int i = 0; i < num_alloacte; i++)
        {
            if (work_list[cur] == temp[i]) {       //如果剩下的工作序列中 现有内存中的作业还会调用的话， 就将其的值置为  -1    
                if (count == 1) {              //此时内存中剩下的那个作业号肯定是最长时间没有调用过的，后者是以后再也不会调用
                    return i;
                }
                temp[i] = -1;
                count--;
                break;
            }
        }
        cur++;
    }
    //此时再来遍历这个 临时的物理块中作业号的  数组  ，  如果他的值不是  -1，就说明后面需要调用的作业中再也没有这个作业了，所以 就可以直接返回。  
    for (int i = 0; i < num_alloacte; i++) {
        if (temp[i] != -1) {
            return i;
        }
        else
        {
            continue;
        }

    }
    return 0;
}

void change() {//缺页中断处理
    int index;
    int flag = 0;
    for (int i = current + 1; i < num; i++)
    {

        for (int j = 0; j < num_alloacte; j++)          //来判断下一个作业是否已经在内存中
        {
            if (work_list[i] == memory_alloacte[j]) {
                flag = 1;                       //是的话让标志位置为1
                break;
            }
        }
        if (flag == 0) {
            sum++;                        //说明不在内存中，会出现页面中断。需要进行换页。
            index = judge();
            if (memory_alloacte[index] != work_list[i]) {
                memory_alloacte[index] = work_list[i];
            }
            current++;
            print(work_list, memory_alloacte);

        }
        else
        {
            flag = 0;
            current++;
            print(work_list, memory_alloacte);
            continue;
        }

    }
    sum+= 3;//加上初始时的分配断页
    cout << "缺页率为";
    cout << fixed << setprecision(2) << float(sum)/float(num)*100 <<"%" << endl;
}
int main() {

    input();

    change();


}

注意：缺页率=中断次数/总页数

 fixed << setprecision(2)//保留两位小数

 

对应解析头文件#include

运行结果如下：