[操作系统]请求分页系统中的置换算法

C++ 操作系统
操作系统
发布日期:   2021-04-28
文章字数:   3.9k
阅读时长:   16 分
阅读次数:  

题目描述

（1）通过如下方法产生一指令序列，共320条指令

A.在[1，32k-2]的指令地址之间随机选取一起点M,访问 M；

B.顺序访问M+1；

C.在[0，M-1]中随机选取M1，访问 M1；

D.顺序访问M1+1；

E.在[M1+2，32k-2]中随机选取M2，访问 M2；

F.顺序访问M2+1；

G.重复 A—F，直到执行 320 次指令。

（2）指令序列变换成页地址流

A. 页面大小为1K

B. 用户虚存容量为32K

（3）计算并输出下述各种算法在不同内存页块(页块个数范围:8-32)下的命中率。

A. 先进先出（FIFO）页面置换算法

B. 最近最久未使用（LRU）页面置换算法

C. 最佳（Optimal）页面置换算法

程序功能及设计思路

程序功能：

程序先按照题目的要求生成320条指令，再把指令转化为一系列的地址流，把地址流按照顺序访问在先进先出（FIFO）页面置换算法、最近最久未使用（LRU）页面置换算法和最佳（Optimal）页面置换算法的缺页数从而计算出命中率并输出。

设计思路：

产生320条指令可以采用在范围内取随机数的方法，一次循环通过产生3个要求的随机数从而获得6条指令，将每条指令的地址除以1K(1024)即可获得页块号，获得地址流。需要设计三个算法来处理地址流，先进先出算法只需要用一个队列，发生缺页时队首元素出队新元素入队；最近最久未使用算法需要设置一个时间戳，每读入一个新的地址，页面中所有页号的时间戳均增加1，如果页面中有新访问的页号，就把这个页号时间戳重置为0，否则移除时间错最大的那个页号并加入新的页号；最佳页面置换算法可以使用链表，当新页号在页面中没有时，先把页面的页号复制一遍，再看地址流后面的地址，每找到一个页面中有的地址就将这个页号删除，直到只剩下一个页号，这个剩下的页号就是被替换的页号，将其替换即可。然后根据缺页的数量计算命中率。

​

程序功能及设计思路

数据结构：

class JobScheduling
{
private:
    vector<int> address;            //地址流
    int page;                    //页块的数量
    void creatSequence();            //获取320条指令序列,暂存在地址流中    
    void creatAddress();            //将320条指令序列转化为地址流(这一操作包括creatSequence())
    int getLast(list<int> L, int n);//获取从n开始往后最后一个访问的数据

public:
    JobScheduling();                //构造函数
    void setPage(int n);            //设置页块的数量
    void outAdd();                //输出地址流
    void FIFO();                //执行先进先出算法并输出命中率
    void LRU();                    //最久未使用置换算法
    void OPT();                    //最佳页面置换算法
};

请求分页系统类里一共有2个成员，为地址流address和页块的数量page。

//LRU的节点
struct LRUNode
{
    int add;        //页块号
    int time;        //停留时间
    LRUNode() {};
    LRUNode(int a) :add(a), time(0) {};    //节点默认的停留时间为0
    friend bool operator==(LRUNode a, LRUNode b) { return a.add == b.add; }
};

最近最久未使用（LRU）页面置换算法节点有两个成员，为页块号和在页面的停留时间time。

算法设计：

//获取320条指令序列,暂存在地址流中    
void JobScheduling::creatSequence()
{
    srand((unsigned)time(NULL));    //设置随机数种子
    int m, m1, m2;
    //实际产生了324条，后面四条不用即可
    while (address.size() < number)
    {//不足320条是就继续产生
        m = rand() % 32766 + 1;        //获取一个【1，32k-2】的数
        address.push_back(m);        //访问m
        address.push_back(m + 1);    //访问m+1

        m1 = rand() % m;
        address.push_back(m1);        //访问m1
        address.push_back(m1 + 1);    //访问m1+1

        m2 = rand() % (32766 - m1 - 2 + 1) + (m1 + 2);    
        address.push_back(m2);        //访问m2
        address.push_back(m2 + 1);    //访问m2+1
    }
}

算法分析：设置一个随机种子后，然后循环产生地址，先在[1，32k-2]找到一个随机地址，访问这个地址与下一个地址；再在[0，M-1] 找到一个随机地址，访问这个地址与下一个地址，最后在[M1+2，32k-2] 到一个随机地址，访问这个地址与下一个地址，直到获取了320个地址。

//将320条指令序列转化为地址流
void JobScheduling::creatAddress()
{
    creatSequence();
    for (int i = 0;i < number;i++)
    {//直接更改原地址获取分页
        address[i] /= 1024;
    }
}

算法思想：把之前获取的地址都除以1024得到对应的页号。

//执行先进先出算法并返回命中率
void JobScheduling::FIFO()
{
    int count = 0;    //记录页面失效的次数
    int i = 0;        //地址流的当前指向
    set<int> flag;                //用于判断页面是否在页块中
    queue<int> pageQueue;        //页面中含有的页块
    int out;
    //对地址逐个进行处理
    for (i=0;i < number;i++)
    {
        //如果在页块中，不需要置换，剩余继续访问
        if (flag.find(address[i]) != flag.end())
        {
            continue;
        }
        //否则发生缺页可能需要置换
        else
        {
            if (pageQueue.size() < page)
            {//页块没有满，直接加入
                pageQueue.push(address[i]);
                flag.insert(address[i]);
            }
            else
            {
                //移除队列的第一个元素(标志集合也做相应处理)
                out = pageQueue.front();
                pageQueue.pop();
                flag.erase(out);

                //新元素加入队列尾部(标志集合也做相应处理)
                pageQueue.push(address[i]);
                flag.insert(address[i]);
                count++;        //发生一次缺页
            }
        }
    }
    //计算命中率
    double hitRate;
    hitRate = 1 - (double)count / (double)number;
    std::cout << "先进先出算法(FIFO)的命中率为:" << hitRate * 100 << "%" << endl;
}

算法思想:初始将缺页次数设置为0，并用一个集合flag判断页号是否在页面中，用一个队列存储存储页号，最后对地址流进行逐个处理，如果在页块中，不需要置换。否则发生缺页可能需要置换，判断队列是否已满，如果没满直接加入，如果队列满了移除队列的第一个元素(标志集合也做相应处理)，并将新元素加入队列尾部(标志集合也做相应处理)，并且缺页次数增加一次。最后计算命中率。

//数组中所有的LRUNode成员时间均增加1
void timeAdd(vector<LRUNode>& v)
{
    for (int i = 0;i < v.size();i++)
    {
        v[i].time++;
    }
}

算法思想：对数组中的所有元素的时间成员增加1。

//获取数组中时间最长的下标
int getMost(vector<LRUNode>& v)
{
    if (v.empty()) return -1;
    //不空就先默认是第一个
    int result = 0;

    for (int i = 0;i < v.size();i++)
    {//发现有更大的就替换
        if (v[result].time < v[i].time)
        {
            result = i;
        }
    }
    return result;
}

算法思想：遍历数组中的所有成员，找到时间戳最大的那个成员并返回在数组中的下标。

//最久未使用置换算法
void JobScheduling::LRU()
{
    vector<LRUNode> pageVector;    
    int count = 0;    //记录页面失效的次数
    int i = 0;        //地址流的当前指向
    //对地址逐个进行处理
    for (i = 0;i < number;i++)
    {
        //先在页面中查找
        LRUNode node(address[i]);
        vector<LRUNode>::iterator it = find(pageVector.begin(), pageVector.end(), node);
        timeAdd(pageVector);            //时间均增加1
        //如果在页块中，不需要置换，但是时间设置为0，剩余继续访问
        if (it!=pageVector.end())
        {
            it->time = 0;
            continue;
        }
        //否则发生缺页可能需要置换
        else
        {
            if (pageVector.size() < page)
            {//页块没有满，直接加入
                pageVector.push_back(node);
            }
            else
            {
                //获取时间最长的元素的下标
                int replace = getMost(pageVector);
                //新元素替换时间最久的元素
                pageVector[replace] = node;
                count++;        //发生一次缺页
            }
        }
    }
    //计算命中率
    double hitRate;
    hitRate = 1 - (double)count / (double)number;
    std::cout << "最久未使用置换算法(LRU)的命中率为:" << hitRate * 100 << "%" << endl;
}

算法思想: 初始将缺页次数设置为0，用一个数组存储存储页号，最后对地址流进行逐个处理，时间戳均增加1，如果在页块中，不需要置换。否则发生缺页可能需要置换，判断数组是否已满，如果没满直接加入，如果数组满了，就找到时间戳最大的那个页号，用新元素替换时间戳最大的页号，并且缺页次数增加一次。最后计算命中率。

//获取从n开始往后最后一个访问的数据
int JobScheduling::getLast(list<int> L, int n)
{
    list<int> c(L);        //建一个L的copy链表
    int result;
    while (true)
    {
        if (c.size() == 1||n>=number) break;
        c.remove(address[n++]);    //移除元素
    }
    result = c.front();
    return result;
}

算法思想：先把页面的页号复制一遍，再看地址流后面的地址，每找到一个页面中有的地址就将这个页号删除，直到只剩下一个页号，返回这个页号。

//最佳页面置换算法
void JobScheduling::OPT()
{
    list<int> pageList;
    int count = 0;    //记录页面失效的次数
    int i = 0;        //地址流的当前指向

    //对地址逐个进行处理
    for (i = 0;i < number;i++)
    {
        //先在页面中查找
        int node = address[i];
        list<int>::iterator it = find(pageList.begin(), pageList.end(), node);

        //如果在页块中,不需要置换,剩余继续访问
        if (it != pageList.end())
        {
            continue;
        }

        //否则发生缺页可能需要置换
        else
        {
            if (pageList.size() < page)
            {//页块没有满，直接加入
                pageList.insert(pageList.end(), address[i]);
            }
            else
            {
                //获取最后一个访问的数据
                int replace = getLast(pageList, i + 1);
                //删除逐个数据
                pageList.remove(replace);
                pageList.insert(pageList.end(), address[i]);
                count++;        //发生一次缺页
            }
        }
    }
    //计算命中率
    double hitRate;
    hitRate = 1 - (double)count / (double)number;
    std::cout << "最佳页面置换算法(OPT)的命中率为:" << hitRate * 100 << "%" << endl;
}

算法思想:初始将缺页次数设置为0，用一个队列存储存储页号，最后对地址流进行逐个处理，如果在页块中，不需要置换。否则发生缺页可能需要置换，判断队列是否已满，如果没满直接加入，如果队列满了就找到最久未使用的那个页号，用新页号替换最久未使用的页号，并且缺页次数增加一次。最后计算命中率。

源代码

stdfax.h

#ifndef STDAFX_H_INCLUDE
#define STDAFX_H_INCLUDE
#include <iostream>
#include <queue>
#include <list>
#include <algorithm>
#include <set>
using namespace std;

#define number 320
#endif // !STDAFX_H_INCLUDE

jobScheduling.h

#ifndef JOBSCHEDULING_H_INCLUDE
#define JOBSCHEDULING_H_INCLUDE
#include "stdafx.h"

class JobScheduling
{
private:
    vector<int> address;            //地址流
    int page;                        //页块的数量
    void creatSequence();            //获取320条指令序列,暂存在地址流中    
    void creatAddress();            //将320条指令序列转化为地址流(这一操作包括creatSequence())
    int getLast(list<int> L, int n);//获取从n开始往后最后一个访问的数据

public:
    JobScheduling();                //构造函数
    void setPage(int n);            //设置页块的数量
    void outAdd();                    //输出地址流
    void FIFO();                    //执行先进先出算法并输出命中率
    void LRU();                        //最久未使用置换算法
    void OPT();                        //最佳页面置换算法
};

//构造函数
JobScheduling::JobScheduling() 
{
    creatAddress();
}

//设置页块的数量
void JobScheduling::setPage(int n)
{
    page = n;
}

//输出地址流
void JobScheduling::outAdd()
{
    for (int i = 0;i < number;i++)
    {
        cout << address[i] << endl;
    }
}

//获取320条指令序列,暂存在地址流中    
void JobScheduling::creatSequence()
{
    srand((unsigned)time(NULL));    //设置随机数种子
    int m, m1, m2;
    //实际产生了324条，后面四条不用即可
    while (address.size() < number)
    {//不足320条是就继续产生
        m = rand() % 32766 + 1;        //获取一个【1，32k-2】的数
        address.push_back(m);        //访问m
        address.push_back(m + 1);    //访问m+1

        m1 = rand() % m;
        address.push_back(m1);        //访问m1
        address.push_back(m1 + 1);    //访问m1+1

        m2 = rand() % (32766 - m1 - 2 + 1) + (m1 + 2);    
        address.push_back(m2);        //访问m2
        address.push_back(m2 + 1);    //访问m2+1

    }
}

//将320条指令序列转化为地址流
void JobScheduling::creatAddress()
{
    creatSequence();
    for (int i = 0;i < number;i++)
    {//直接更改原地址获取分页
        address[i] /= 1024;
    }
}

//执行先进先出算法并返回命中率
void JobScheduling::FIFO()
{
    int count = 0;    //记录页面失效的次数
    int i = 0;        //地址流的当前指向
    set<int> flag;                //用于判断页面是否在页块中
    queue<int> pageQueue;        //页面中含有的页块
    int out;
    //对地址逐个进行处理
    for (i=0;i < number;i++)
    {
        //如果在页块中，不需要置换，剩余继续访问
        if (flag.find(address[i]) != flag.end())
        {
            continue;
        }
        //否则发生缺页可能需要置换
        else
        {
            if (pageQueue.size() < page)
            {//页块没有满，直接加入
                pageQueue.push(address[i]);
                flag.insert(address[i]);
            }
            else
            {
                //移除队列的第一个元素(标志集合也做相应处理)
                out = pageQueue.front();
                pageQueue.pop();
                flag.erase(out);

                //新元素加入队列尾部(标志集合也做相应处理)
                pageQueue.push(address[i]);
                flag.insert(address[i]);
                count++;        //发生一次缺页
            }
        }
    }
    //计算命中率
    double hitRate;
    hitRate = 1 - (double)count / (double)number;
    std::cout << "先进先出算法(FIFO)的命中率为:" << hitRate * 100 << "%" << endl;
}

//LRU的节点
struct LRUNode
{
    int add;        //页块号
    int time;        //停留时间
    LRUNode() {};
    LRUNode(int a) :add(a), time(0) {};    //节点默认的停留时间为0
    friend bool operator==(LRUNode a, LRUNode b) { return a.add == b.add; }
};

//数组中所有的LRUNode成员时间均增加1
void timeAdd(vector<LRUNode>& v)
{
    for (int i = 0;i < v.size();i++)
    {
        v[i].time++;
    }
}

//获取数组中时间最长的下标
int getMost(vector<LRUNode>& v)
{
    if (v.empty()) return -1;
    //不空就先默认是第一个
    int result = 0;

    for (int i = 0;i < v.size();i++)
    {//发现有更大的就替换
        if (v[result].time < v[i].time)
        {
            result = i;
        }
    }
    return result;
}

//最久未使用置换算法
void JobScheduling::LRU()
{
    vector<LRUNode> pageVector;    
    int count = 0;    //记录页面失效的次数
    int i = 0;        //地址流的当前指向
    //对地址逐个进行处理
    for (i = 0;i < number;i++)
    {
        //先在页面中查找
        LRUNode node(address[i]);
        vector<LRUNode>::iterator it = find(pageVector.begin(), pageVector.end(), node);
        timeAdd(pageVector);            //时间均增加1
        //如果在页块中，不需要置换，但是时间设置为0，剩余继续访问
        if (it!=pageVector.end())
        {
            it->time = 0;
            continue;
        }
        //否则发生缺页可能需要置换
        else
        {
            if (pageVector.size() < page)
            {//页块没有满，直接加入
                pageVector.push_back(node);
            }
            else
            {
                //获取时间最长的元素的下标
                int replace = getMost(pageVector);
                //新元素替换时间最久的元素
                pageVector[replace] = node;
                count++;        //发生一次缺页
            }
        }
    }
    //计算命中率
    double hitRate;
    hitRate = 1 - (double)count / (double)number;
    std::cout << "最久未使用置换算法(LRU)的命中率为:" << hitRate * 100 << "%" << endl;
}

//获取从n开始往后最后一个访问的数据
int JobScheduling::getLast(list<int> L, int n)
{
    list<int> c(L);        //建一个L的copy链表
    int result;
    while (true)
    {
        if (c.size() == 1||n>=number) break;
        c.remove(address[n++]);    //移除元素
    }
    result = c.front();
    return result;
}

//最佳页面置换算法
void JobScheduling::OPT()
{
    list<int> pageList;
    int count = 0;    //记录页面失效的次数
    int i = 0;        //地址流的当前指向

    //对地址逐个进行处理
    for (i = 0;i < number;i++)
    {
        //先在页面中查找
        int node = address[i];
        list<int>::iterator it = find(pageList.begin(), pageList.end(), node);

        //如果在页块中,不需要置换,剩余继续访问
        if (it != pageList.end())
        {
            continue;
        }

        //否则发生缺页可能需要置换
        else
        {
            if (pageList.size() < page)
            {//页块没有满，直接加入
                pageList.insert(pageList.end(), address[i]);
            }
            else
            {
                //获取最后一个访问的数据
                int replace = getLast(pageList, i + 1);
                //删除逐个数据
                pageList.remove(replace);
                pageList.insert(pageList.end(), address[i]);
                count++;        //发生一次缺页
            }
        }
    }
    //计算命中率
    double hitRate;
    hitRate = 1 - (double)count / (double)number;
    std::cout << "最佳页面置换算法(OPT)的命中率为:" << hitRate * 100 << "%" << endl;
}
#endif // !JOBSCHEDULING_H_INCLUDE

main.cpp

#include "jobScheduling.h"

int main()
{
    int n;
    cout << "请输入页块的个数:";
    cin >> n;
    JobScheduling obj;
    obj.setPage(n);
    obj.FIFO();
    obj.LRU();
    obj.OPT();
    return 0;
}
文章作者: 陈细利
文章链接: https://firewolf321.github.io/2021/04/28/cao-zuo-xi-tong-qing-qiu-fen-ye-xi-tong-zhong-de-zhi-huan-suan-fa/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 陈细利 !
C++ 操作系统
赏
评论
 上一篇
[操作系统]作业调度 [操作系统]作业调度
题目描述1、假设系统中可同时运行两道作业，给出每道作业的到达时间和运行时间，如下表所示： 作业名 A B C D E F G H I J 到达时间 0 2 5 7 12 15 4 6 8 10 运行时间 7 10 20 30
2021-05-02 操作系统
C++ 操作系统
下一篇 
[操作系统]动态分区式存贮区管理 [操作系统]动态分区式存贮区管理
题目描述设计一个动态分区式存贮区管理程序，要求支持不同的放置策略。包括首次、最佳、最坏。 说明： (1) 分区描述器rd如下: flag size next 要求空闲区队列按链表组织。 主存大小假设为maxsize（单位为节=
2021-04-25 操作系统
C++ 操作系统
  目录