「OS」页面置换算法

  OPT FIFO LRU LFU NRU

Posted by StandHR on July 5, 2018
View times

要求

  1. 假设分给一作业的内存块数为4,每个页面中可存放10条指令。
  2. 设计一个程序,模拟一作业的执行过程。设该作业共有320条指令,即它的地址空间为32页,目前它的所有页面都还未调入内存。在模拟过程中,如果所访问的指令已经在内存,则显示其物理地址,并转下一条指令。如果所访问的指令尚未装入内存,则发生缺页,此时需记录缺页的次数,并将相应页调入内存。如果4个内存块中均已装入该作业的虚页面,则需进行页面置换。最后显示其物理地址,并转下一条指令。在所有320条指令执行完毕后,请计算并显示作业运行过程中发生的缺页率。
  3. 置换算法:请分别考虑OPT、FIFO、LRU、LFU和NRU算法。
  4. 作业中指令的访问次序要求按下述原则生成:
    • 50%的指令是顺序执行的。
    • 25%的指令是均匀分布在前地址(即低地址)部分。
    • 25%的指令是均匀分布在后地址(即高地址)部分。
      具体的实施办法是:
      ① 在[0,319]之间随机选取一条起始执行指令,其序号为m;
      ② 顺序执行下一条指令,即序号为m+1的指令;
      ③ 通过随机数,跳转到前地址部分[0,m-1]中的某条指令处,其序号为m1;
      ④ 顺序执行下一条指令,即序号为m1+1的指令;
      ⑤ 通过随机数,跳转到后地址部分[m1+2,319]中的某条指令处,其序号为m2;
      ⑥ 顺序执行下一条指令,即序号为m2+1的指令;
      ⑦ 重复“跳转到前地址部分、顺序执行、跳转到后地址部分、顺序执行”的过程,直至执行完全部320条指令。
  5. 指令序列转换成页访问序列。
    第0条 - 第9条指令为第0页(对应虚存地址为[0,9])
    第10条 - 第19条指令为第1页(对应虚存地址为[10,19])
    ………………………………
    第310条-第319条指令为第31页(对应虚存地址为[310,319])
#include <iostream>
#include <map>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <vector>
using namespace std;

int commandSize;
const int blockSize = 4;

#define INF 1e6
#define MOD 320

vector<int> command;
map<int, bool> F;

int missPageNum;

typedef struct BLOCK {
    int pageNum;
    int OPT;
    int LRU;
} BLOCK;

BLOCK block[blockSize];


void GetRandom() {
    srand((unsigned)time(NULL));
    int flag = 0;
    int randomNum = rand() % MOD;
    int fnum = 0;
    for (int i = 0;; i++) {
        if(!F[randomNum]) {
            F[randomNum] = 1;
            fnum++;
        }
        command.push_back(randomNum);
        if(fnum == MOD)
            break;
        if (flag % 2 == 0)
            randomNum = ++randomNum % MOD;
        else if (flag == 1)
            randomNum = rand() % (randomNum - 1);
        else
            randomNum = randomNum + 1 + (rand() % (MOD - (randomNum + 1)));
        flag = ++flag % 4;
        printf(" %03d", command[i]);
    }
    cout << endl;
    commandSize = (int)command.size();
}

void InitBlocks() {
    for (int i = 0; i < blockSize; i++) {
        block[i].pageNum = -1;
        block[i].OPT = INF;
        block[i].LRU = -1;
    }
    missPageNum = 0;
}

int FindPage(int pageNum) {
    for(int i = 0; i < blockSize; i++) {
        if(block[i].pageNum == pageNum)
            return i;
    }
    return -1;
}

OPT

最佳(Optimal, OPT)置换算法所选择的被淘汰页面将是以后永不使用的,或者是在最长时间内不再被访问的页面,这样可以保证获得最低的缺页率。但由于人们目前无法预知进程在内存下的若千页面中哪个是未来最长时间内不再被访问的,因而该算法无法实现。

FindPage()寻找页面,每当在内存块中找不到页面时,OPTFindReplace()查找最长时间不被访问的页面,因此初始化物理块时把OPT值设为极大数INF,当页面被淘汰后为新页面OPTSetPriority()设置下次访问时间,不会再被访问时设INF

//************************        OPT       ***********************//

int OPTFindReplace() {
    int x = 0;
    for (int i = 0; i < blockSize; i++) {
        if(block[i].OPT > block[x].OPT)
            x = i;
    }
    return x;
}

void OPTSetPriority(int blockNum, int i) {
    for (int j = i + 1; j < commandSize; j++) {
        if (block[blockNum].pageNum == command[j] / 10) {
            block[blockNum].OPT = j;
            return;
        }
    }
    block[blockNum].OPT = INF;
}

void OPT() {
    InitBlocks();
    for (int i = 0; i < commandSize; i++) {
        int pageNum = command[i] / 10;
        if(FindPage(pageNum) == -1) {
            missPageNum++;
            int blockNum = OPTFindReplace();
            block[blockNum].pageNum = pageNum;
            OPTSetPriority(blockNum, i);
        }
        else {
            int blockNum = FindPage(pageNum);
            OPTSetPriority(blockNum, i);
        }
    }
    cout << "OPT:" << endl;
    cout << missPageNum << endl;
    printf("%.2lf%%\n\n", 100.0 * missPageNum / commandSize);
}

FIFO

先进先出(FIFO)页面置换算法,优先淘汰最早进入内存的页面,亦即在内存中驻留时间最久的页面。

很明显是队列结构,但由于需要遍历队列查找页面,于是动态数组模拟队列,FIFOFoundPage()查找页面,当没有页面时,数组尾部加入页面,判断数组空间是否大于4,大于就删除数组头元素。

//**********************         FIFO       ***********************//

int FIFOFoundPage(vector<BLOCK>& Q, int pageNum) {
    for (auto &i : Q) {
        if (i.pageNum == pageNum)
            return 1;
    }
    return 0;
}

void FIFO() {
    vector<BLOCK> Q;
    InitBlocks();
    for (int i = 0; i < commandSize; i++) {
        int pageNum = command[i] / 10;
        if (!FIFOFoundPage(Q, pageNum)) {
            missPageNum++;
            BLOCK x;
            x.pageNum = pageNum;
            Q.push_back(x);
            if ((int)Q.size() > 4)
                Q.erase(Q.begin());
        }
    }
    cout << "FIFO:" << endl;
    cout << missPageNum << endl;
    printf("%.2lf%%\n\n", 100.0 * missPageNum / commandSize);
}

LRU

最近最久未使用(LRU)置换算法,选择最近最长时间未访问过的页面予以淘汰,它认为过去一段时间内未访问过的页面,在最近的将来可能也不会被访问。

要淘汰最长时间未访问的页面只需记录下什么时候访问页面,当缺页时淘汰最早访问的页面即可。LRUFindReplace()查找最早访问。

//***********************         LRU         *********************//

int LRUFindReplace() {
    int x = 0;
    for (int i = 0; i < blockSize; i++) {
        if(block[i].LRU < block[x].LRU)
            x = i;
    }
    return x;
}

void LRU() {
    InitBlocks();
    for (int i = 0; i < commandSize; i++) {
        int pageNum = command[i] / 10;
        if(FindPage(pageNum) == -1) {
            missPageNum++;
            int blockNum = LRUFindReplace();
            block[blockNum].pageNum = pageNum;
            block[blockNum].LRU = i;
        }
        else
            block[FindPage(pageNum)].LRU = i;
    }
    cout << "LRU:" << endl;
    cout << missPageNum << endl;
    printf("%.2lf%%\n\n", 100.0 * missPageNum / commandSize);
}

LFU

LFU(Least Frequently Used)算法根据数据的历史访问频率来淘汰数据,其核心思想是“如果数据过去被访问多次,那么将来被访问的频率也更高”。

只需map记录下每个页面历史访问次数,LFUFindReplace()找到次数最少的淘汰。

//***********************         LFU         *********************//

int LFUFindReplace(map<int,int>& M) {
    int x = 0;
    for (int i = 0; i < blockSize; i++) {
        if(M[block[i].pageNum] < M[block[x].pageNum])
            x = i;
    }
    return x;
}

void LFU() {
    InitBlocks();
    map<int,int> M;
    for (int i = 0; i < commandSize; i++) {
        int pageNum = command[i] / 10;
        M[pageNum]++;
        if(FindPage(pageNum) == -1) {
            missPageNum++;
            int blockNum = LFUFindReplace(M);
            block[blockNum].pageNum = pageNum;
        }
    }
    cout << "LFU:" << endl;
    cout << missPageNum << endl;
    printf("%.2lf%%\n\n", 100.0 * missPageNum / commandSize);
}

NRU

简单的CLOCK算法是给每一帧关联一个附加位,称为使用位。当某一页首次装入主存时,该帧的使用位设置为1;当该页随后再被访问到时,它的使用位也被置为1。对于页替换算法,用于替换的候选帧集合看做一个循环缓冲区,并且有一个指针与之相关联。当某一页被替换时,该指针被设置成指向缓冲区中的下一帧。当需要替换一页时,操作系统扫描缓冲区,以查找使用位被置为0的一帧。每当遇到一个使用位为1的帧时,操作系统就将该位重新置为0;如果在这个过程开始时,缓冲区中所有帧的使用位均为0,则选择遇到的第一个帧替换;如果所有帧的使用位均为1,则指针在缓冲区中完整地循环一周,把所有使用位都置为0,并且停留在最初的位置上,替换该帧中的页。由于该算法循环地检查各页面的情况,故称为CLOCK算法,又称为最近未用(Not Recently Used, NRU)算法。

//***********************         NRU         *********************//

void NRU() {
    InitBlocks();
    bool arr[blockSize] = {0};
    int id = 0;
    for(int i = 0; i < commandSize; i++) {
        int pageNum = command[i] / 10;
        if(FindPage(pageNum) == -1) {
            missPageNum++;
            bool flag = 1;
            while(flag){
                if(arr[id] == 0) {
                    block[id].pageNum = pageNum;
                    arr[id] = 1;
                    flag = 0;
                    id = (id + 1) % blockSize;
                }
                else {
                    arr[id] = 0;
                    id = (id + 1) % blockSize;
                }
            }
            flag = 1;
        }
        else
            id = (FindPage(pageNum) + 1) % blockSize;
    }
    cout << "NRU:" << endl;
    cout << missPageNum << endl;
    printf("%.2lf%%\n\n", 100.0 * missPageNum / commandSize);
}