IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 操作系统(4)页面替换策略算法模拟实现 -> 正文阅读

[数据结构与算法]操作系统(4)页面替换策略算法模拟实现

1. 效果展示

2. 程序流程图

(1) 程序总流程

(2) FIFO策略

(3) LRU策略

??

(4) OPT策略

3. 数据结构设计

//页面数据结构
    struct PageInfo {
        int id;
        int visit;
    };

    PageInfo* Block;  // 物理块
    PageInfo* Page;  // 页面

4. 功能函数设计

序号

函数

功能说明

1

void init();

从data.txt文件中读取数据进行初始化

2

int findSpace();

查找是否有空闲物理块

3

int findExist(int curren);

查找物理块中是否存在该页面

4

int findReplace();

查找应予以置换的页面

5

int showSingle(int curren);

打印每一个序列号的结果

6

void FIFO();

替换最早进入的页面

7

void LRU();

淘汰上次使用距当前最远的页面

8

void OPT();

淘汰下一次访问距当前最远的页面中序号最小的一页

9

int main();

主函数,控制程序的整个流程

5. 代码实现

/// 页面替换策略 FIFO、OPT、LRU
#include <bits/stdc++.h>
using namespace std;

class Pager {
public:
    //页面数据结构
    struct PageInfo {
        int id;
        int visit;
    };

    PageInfo* Block;  // 物理块
    PageInfo* Page;  // 页面

    int BlockNum;
    int PageNum;

    int LockPageCnt;  //缺页次数
    int ChangePageCnt;  //置换次数

public:
    /// 从data.txt文件中读取数据,并初始化
    void init() {
        cout<<"正在进行数据读取..."<<endl;
        ifstream readData;
        readData.open("data.txt");

        readData>>BlockNum;
        Block = new PageInfo[BlockNum];
        for (int i = 0; i < BlockNum; ++i) {
            Block[i].id = -1;
            Block[i].visit = 0;
        }
        readData>>PageNum;
        Page = new PageInfo[PageNum];
        for (int i = 0; i < PageNum; ++i) {
            readData>>Page[i].id;
            Page[i].visit = 0;
        }
        readData.close();

        cout<<"数据读取结果如下:"<<endl;
        printf("物理块数为:%d\n", BlockNum);
        printf("页面个数为:%d\n", PageNum);
        cout<<"页面序列如下:"<<endl;
        for (int i = 0; i < PageNum; ++i) {
            printf("%d  ", Page[i].id);
        }
        cout<<endl;
        cout<<"数据读取完毕!"<<endl;
    }

    /// 查找是否有空闲块
    int findSpace() {
        for (int i = 0; i < BlockNum; ++i) {
            if (Block[i].id == -1) {
                return i;
            }
        }
        return -1;
    }

    /// 查找内存中是否存在该页面
    int findExist(int curren) {
        for (int i = 0; i < BlockNum; ++i) {
            if(Block[i].id != -1 && Block[i].id == curren) {
                return i;
            }
        }
        return -1;
    }

    /// 查找应予以置换的页面
    int findReplace() {
        int pos = 0;
        for (int i = 1; i < BlockNum; i++) {
            if(Block[i].id != -1 && Block[i].visit > Block[pos].visit) {
                pos = i;
            }
        }
        return pos;
    }

    /// 显示置换一次后的Block
    void showSingle(int curren) {
        printf("%d : ", curren);
        for (int i = 0; i < BlockNum; ++i) {
            if(Block[i].id != -1) {
                printf(" %d ", Block[i].id);
            }
        }
        cout<<endl;
    }

    /// FIFO
    void FIFO() {
        int exist, space, position;
        double fifo_missRate;
        LockPageCnt = 0;
        ChangePageCnt = 0;
        printf("\n----FIFO策略-start----\n");
        for (int i = 0; i < PageNum; ++i) {
            exist = findExist(Page[i].id);
            // 当前页面号不在内存中
            if (exist == -1) {
                LockPageCnt++;
                space = findSpace();
                // 当前内存已满,需置换
                if(space == -1) {
                    ChangePageCnt++;
                    position = findReplace();
                    Block[position] = Page[i];
                }
                // 当前内存未满,直接加入
                else {
                    Block[space] = Page[i];
                }

            }

            showSingle(Page[i].id);

            for (int j = 0; j < BlockNum; ++j) {
                if (Block[j].id != -1) {
                    Block[j].visit++;  // Block中的页面停留时间+1
                }
            }
        }
        fifo_missRate = (double) LockPageCnt / PageNum;
        printf("缺页次数:%d\n", LockPageCnt);
        printf("置换次数:%d\n", ChangePageCnt);
        printf("FIFO缺页率:%lf%%\n", fifo_missRate*100);
        printf("----FIFO策略-end----\n");
    }

    /// OPT
    void OPT() {
        int exist, space, position;
        double opt_missRate;
        LockPageCnt = 0;
        ChangePageCnt = 0;
        printf("\n----OPT策略-start----\n");
        for (int i = 0; i < PageNum; ++i) {
            exist = findExist(Page[i].id);
            // 当前页面号不在内存中
            if (exist == -1) {
                LockPageCnt++;
                space = findSpace();
                // 当前内存已满,需置换
                if(space == -1) {
                    ChangePageCnt++;
                    for (int k = 0; k < BlockNum; k++) {
                        for (int j = i+1; j < PageNum; j++) {
                            if (Block[k].id != Page[j].id) {
                                Block[k].visit = 1000;
                            } else {
                                Block[k].visit = j-i;
                                break;
                            }
                        }
                    }
                    position = findReplace();
                    Block[position] = Page[i];
                }
                // 当前内存未满,直接加入
                else {
                    Block[space] = Page[i];
                }
            }
            showSingle(Page[i].id);
        }
        opt_missRate = (double) LockPageCnt / PageNum;
        printf("缺页次数:%d\n", LockPageCnt);
        printf("置换次数:%d\n", ChangePageCnt);
        printf("OPT缺页率:%lf%%\n", opt_missRate*100);
        printf("----OPT策略-end----\n");
    }

    /// LRU
    void LRU() {
        int exist, space, position;
        double lru_missRate;
        LockPageCnt = 0;
        ChangePageCnt = 0;
        printf("\n----LRU策略-start----\n");
        for (int i = 0; i < PageNum; ++i) {
            exist = findExist(Page[i].id);
            // 当前页面号不在内存中
            if (exist == -1) {
                LockPageCnt++;
                space = findSpace();
                // 当前内存已满,需置换
                if(space == -1) {
                    ChangePageCnt++;
                    position = findReplace();
                    Block[position] = Page[i];
                }
                    // 当前内存未满,直接加入
                else {
                    Block[space] = Page[i];
                }
            }
            // 当前页面在内存中
            else {
                Block[exist].visit = 0;
            }
            showSingle(Page[i].id);

            for (int j = 0; j < BlockNum; ++j) {
                if (Block[j].id != -1) {
                    Block[j].visit++;  // Block中的页面停留时间+1
                }
            }
        }
        lru_missRate = (double) LockPageCnt / PageNum;
        printf("缺页次数:%d\n", LockPageCnt);
        printf("置换次数:%d\n", ChangePageCnt);
        printf("LRU缺页率:%lf%%\n", lru_missRate*100);
        printf("----LRU策略-end----\n");
    }
};

int main() {
    Pager page;
    int chooseAlgorithm;
    while(true)
    {
        printf("\t-------------------------------------\n");
        printf("\t||                                  ||\n");
        printf("\t||       页面替换策略模拟程序           ||\n");
        printf("\t||           1. FIFO                ||\n");
        printf("\t||           2. LRU                 ||\n");
        printf("\t||           3. OPT                 ||\n");
        printf("\t||           0. 退出程序             ||\n");
        printf("\t||                                  ||\n");
        printf("\t-------------------------------------\n");

        printf("请输入序号进行选择:");
        cin>>chooseAlgorithm;
        switch(chooseAlgorithm)
        {
            case 1:
                page.init();
                page.FIFO();
                break;
            case 2:
                page.init();
                page.LRU();
                break;
            case 3:
                page.init();
                page.OPT();
                break;
            case 0:
                cout<<"正在退出程序..."<<endl;
                system("pause");
                return 0;
            default:
                cout<<"请输入正确的序号进行选择!"<<endl;
        }
    }
}

  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2022-12-25 11:33:24  更:2022-12-25 11:38:27 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年6日历 -2024/6/18 13:13:47-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码