操作系统 FIFO算法 LRU算法 OPT算法

题目

实验三 请求调页存储管理方式的模拟
1．实验目的
通过对页面、页表、地址转换和页面置换过程的模拟，加深对请求调页系统的原理和实现过程的理解。
2．实验内容
（1）假设每个页面中可存放10条指令，分配给作业的内存块数为4。
（2）用c语言模拟一个作业的执行过程，该作业共有320条指令，即它的地址空间为32页，目前它的所有页都还未调入内存。在模拟过程中，如果所访问的指令已在内存，则显示其物理地址，并转下一条指令。如果所访问的指令还未装入内存，则发生缺页，此时需记录缺页的次数，并将相应页调入内存。如果4个内存块均已装入该作业，则需进行页面置换，最后显示其物理地址，并转下一条指令。在所有320指令执行完毕后，请计算并显示作业运行过程中发生的缺页率。
（3）置换算法：采用先进先出（FIFO）、最近最久未使用（LRU）和最佳置换（OPT）算法置换算法。
（4）通过随机数产生一个指令序列，共320条指令。
1）指令的地址按下述原则生成：
① 50%的指令是顺序执行的；
② 25%的指令是均匀分布在前地址部分；
③ 25%的指令是均匀分布在后地址部分；
具体的实施方法是：
① 在[0，319]的指令地址之间随机选取一起点m；
② 顺序执行一条指令，即执行序号为m+1的指令；
③ 在前地址[0，m-1]中随机选取一条指令并执行，该指令的序号为m1；
④ 顺序执行一条指令，其序号为m1+1的指令；
⑤ 在后地址[m1+2，319]中随机选取一条指令并执行,该指令的序号为m2；
⑥ 顺序执行一条指令，其序号为m2+1的指令；
重复上述步骤①～⑥，直到执行320次指令。
2）将指令序列变换为页地址流
设页面大小为1K， 用户虚存容量为32K。在用户虚存中，按每K存放10条指令排列虚存地址，即320条指令在虚存中的存放方式为：
第0条～第9条指令为第0页（对应虚存地址为[0，9]）；
第10条～第19条指令为第1页（对应虚存地址为[10，19]）；
……
……
第310条～第319条指令为第31页（对应虚存地址为[310，319]）。
按以上方式，用户指令可组成32页。
3.思考
（1）如果增加分配给作业的内存块数，将会对作业运行过程中的缺页产生什么影响？
（2）为什么一般情况下，LRU具有比FIFO更好的性能？

首先要注意的是，实验文档那个获取随机指令的方法非常糟糕，很多种情况会导致程序奔溃或者获得的指令不在范围内，需要特判。

FIFO算法

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <string>
#include <string.h>
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <time.h>
using namespace std;
int cnt;                ///发生缺页的次数
const int maxn = 4;     ///内存块数的数目
const int maxn_n = 320;

typedef struct Node{
    int a[10];
    bool is_empty = true;
}Node;
Node block[maxn];///结构体数组模拟队列，4个内存块维护页面

int head = 0;
int tail = 0;
int instruction[maxn_n];    ///指令

int search(int id){
    for(int i = 0; i < maxn; i++){
        if(!block[i].is_empty){
            for(int j = 0; j < 10; j++){
                if(block[i].a[j] == id){
                    return 0 * printf("已存在，物理地址为：%d\n", i * 10 + j);
                }
            }
        }
    }
    return -1;
}

void adjust(int id){
    if(tail < maxn){
        block[tail].is_empty = false;
        for(int i = 0; i < 10; i++){
            block[tail].a[i] = id / 10 * 10 + i;

        }
        printf("调入内存后物理地址为：%d\n", tail * 10 + id % 10);
        tail++;
    }else{
        for(int i = 0; i < 10; i++){
            block[head].a[i] = id / 10 * 10 + i;
        }
        printf("调入内存后物理地址为：%d\n", head * 10 + id % 10);
        head = (head + 1) % maxn;
    }
}

void solve(int id){
    if(search(id) == -1){
        cnt++;
        adjust(id);
    }
}

int main(){
    srand(int(time(0)));
    int n = 320;
    int cnt_n = 0;
    while(cnt_n < 320){
        int m = rand() % n;
        instruction[cnt_n++] = m + 1;

        if(m == 0)
            continue;
        int m1 = rand() % m;
        instruction[cnt_n++] = m1;
        instruction[cnt_n++] = m1 + 1;

        if(n - m1 - 2 <= 0)
            continue;
        int m2 = rand() % (n - m1 - 2) + m1 + 2;
        instruction[cnt_n++] = m2;
        instruction[cnt_n++] = m2 + 1;
    }
    for(int i = 0; i < 320; i++){
        solve(instruction[i]);
    }
    printf("缺页次数为：%d\n", cnt);
    printf("缺页率为：%f\n", 1.0 * cnt / 320);
    return 0;
}

LRU算法

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <string>
#include <string.h>
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <time.h>
using namespace std;

int cnt;                ///发生缺页的次数
int now_time;           ///当前时间
const int maxn = 4;     ///内存块数的数目
const int maxn_n = 320 + 20;

typedef struct Node{
    int id;                 ///块序号
    int a[10];
    int passage = -1;       ///页
    int recent_time = -1;   ///上次使用的时间，越大说明越接近现在我们所处的时间
}Node;
Node block[maxn];///结构体数组模拟队列，4个内存块维护页面

int instruction[maxn_n];    ///指令

bool search(int id, int passage){
    for(int i = 0; i < maxn; i++){
        if(block[i].passage == passage){
            block[i].recent_time = now_time;
            printf("已存在，物理地址为：%d\n", block[i].id * 10 + id % 10);
            return true;
        }
    }
    return false;
}

bool cmp(Node a, Node b){
    return a.recent_time < b.recent_time;///从小到大排序，小的离现在最久远
}

void adjust(int id, int passage){
    sort(block, block + maxn, cmp);
    for(int i = 0; i < 10; i++){
        block[0].a[i] = id / 10 * 10 + i;
    }
    block[0].passage = passage;
    block[0].recent_time = now_time;
    printf("调入内存后，物理地址为：%d\n", block[0].id * 10 + id % 10);
}

void solve(int id){
    if(!search(id, id / 10)){///找不到该页
        cnt++;
        adjust(id, id / 10);
    }
    now_time++;
}

int main(){
    srand(int(time(0)));
    int n = 320, cnt_n = 0;
    while(cnt_n < 320){
        int m = rand() % n;
        instruction[cnt_n++] = m + 1;

        if(m == 0)
            continue;
        int m1 = rand() % m;
        instruction[cnt_n++] = m1;
        instruction[cnt_n++] = m1 + 1;

        if(n - m1 - 2 <= 0)
            continue;
        int m2 = rand() % (n - m1 - 2) + m1 + 2;
        instruction[cnt_n++] = m2;
        instruction[cnt_n++] = m2 + 1;
    }
    for(int i = 0; i < maxn; i++){
        block[i].id = i;
    }
    for(int i = 0; i < n; i++){
        solve(instruction[i]);
    }
    printf("缺页次数为：%d\n", cnt);
    printf("缺页率为：%f\n", 1.0 * cnt / n);
    return 0;
}

OPT算法

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <string>
#include <string.h>
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <time.h>
using namespace std;
int now;
int cnt;                ///发生缺页的次数
const int maxn = 4;     ///内存块数的数目
const int maxn_n = 320 + 20;
const int INF = 0x3f3f3f3f;

typedef struct Node{
    int id;                 ///块序号
    int a[10];
    int passage = -1;       ///页
    int next_use = INF;     ///这个页面下次要用到的位置
}Node;
Node block[maxn];///结构体数组模拟队列，4个内存块维护页面

int next_use[maxn];         ///第i条指令所处的页面下次要使用到的位置
int instruction[maxn_n];    ///指令

bool search(int pos, int id, int passage){
    for(int i = 0; i < maxn; i++){
        if(block[i].passage == passage){
            block[i].next_use = next_use[pos];
            printf("已存在，物理地址为：%d\n", block[i].id * 10 + id % 10);
            return true;
        }
    }
    return false;
}

bool cmp(Node a, Node b){
    return a.next_use - now > b.next_use - now;///大到小排序，最晚用到的替代掉
}

void adjust(int pos,int id, int passage){
    sort(block, block + maxn, cmp);
    if(block[3].next_use - pos <= 0){
        for(int i = 0; i < 10; i++){
        block[3].a[i] = id / 10 * 10 + i;
        }
        block[3].passage = passage;
        block[3].next_use = next_use[pos];
        printf("调入内存后，物理地址为：%d\n", block[3].id * 10 + id % 10);
    }
    else
    {
        for(int i = 0; i < 10; i++){
            block[0].a[i] = id / 10 * 10 + i;
        }
        block[0].passage = passage;
        block[0].next_use = next_use[pos];
        printf("调入内存后，物理地址为：%d\n", block[0].id * 10 + id % 10);
    }
}

void solve(int pos, int id){
    if(!search(pos, id, id / 10)){///找不到该页
        cnt++;
        adjust(pos, id, id / 10);
    }
}

int main(){
    srand(int(time(0)));
    int n = 320, cnt_n = 0;
    while(cnt_n < 320){
        int m = rand() % n;
        instruction[cnt_n++] = m + 1;

        if(m == 0)
            continue;
        int m1 = rand() % m;
        if(m1 + 1 >= n)
            continue;
        instruction[cnt_n++] = m1;
        instruction[cnt_n++] = m1 + 1;

        if(n - m1 - 2 <= 0)
            continue;
        int m2 = rand() % (n - m1 - 2) + m1 + 2;
        instruction[cnt_n++] = m2;
        instruction[cnt_n++] = m2 + 1;
    }
    //预处理出多久后会再使用
    for(int i = 0; i < n; i++){
        for(int j = i + 1; j <= n; j++){
            if(j == n){
                next_use[i] = INF;
                break;
            }
            if(instruction[i] >= instruction[j] / 10 * 10 && instruction[i] < (instruction[j] / 10 + 1) * 10){
                next_use[i] = j;
                break;
            }
        }
    }
    for(int i = 0; i < maxn; i++){
        block[i].id = i;
    }
    for(int i = 0; i < n; i++){
        now = i;
        solve(i, instruction[i]);
    }
    printf("缺页次数为：%d\n", cnt);
    printf("缺页率为：%f\n", 1.0 * cnt / n);
    return 0;
}