页面淘汰算法模拟实现与比较

1.实验目标

利用标准C 语言,编程设计与实现最佳淘汰算法、先进先出淘汰算法、最近最久未使用淘汰算法、简单 Clock 淘汰算法及改进型 Clock 淘汰算法,并随机发生页面访问序列开展有关算法的测试及性能比较。

2.算法描述

 1. 最佳淘汰算法(Optimal Replacement Algorithm):这种算法选择将来最久不会被访问的页面进行淘汰。实现这个算法需要预知未来的页面访问请求,因此在实际中无法实现,但是我们可以模拟访问序列来比较实现效果。

2. 先进先出淘汰算法(FIFO Replacement Algorithm):这种算法总是淘汰最早进入内存的页面。实现这个算法可以使用一个队列,新进入的页面放入队尾,需要淘汰页面时总是淘汰队头的页面。

3. 最近最久未使用淘汰算法(LRU Replacement Algorithm):这种算法淘汰最长时间未被访问的页面。实现这个算法可以使用一个链表,每次页面被访问时,将这个页面移动到链表头,需要淘汰页面时总是淘汰链表尾的页面。

4. 简单 Clock 淘汰算法(Clock Replacement Algorithm):这种算法将内存中的页面组织成一个环形链表,有一个指针指向最早进入的页面。每次需要淘汰页面时,检查指针指向的页面,如果这个页面最近被访问过,则将其标记清除,指针向前移动,否则淘汰这个页面。

5. 改进型 Clock 淘汰算法(Enhanced Clock Replacement Algorithm):这是 Clock 算法的改进版,增加了一个修改位用于记录页面是否被修改过。在选择淘汰的页面时,优先选择未被修改且最近未被访问的页面。

3.访问序列模拟 

1. 初始化进程逻辑地址空间页面总数 N、各逻辑页面的读写访问方式(是否支持写访问,即R、RW)、工作集起始页号s(s∈[0, N)) 、工作集中包含的页数 w,工作集移动速率 v(每处理 v 个页面访问,就将工作集起始页号递增即 s+1)以及一个取值区间为[0, 1]的值 t

2. 生成取值区间为[s, min(s+w, N-1)]的v 个随机数并添加保存到页面访问序列中,同时为每次页面访问分别生成一个取值区间为[0, 1]的随机数,若该随机数值大于 0.7 且对应所访问页面支持写访问则设定以写方式访问相应页面,否则以读方式访问对应页面

3. 生成取值区间为[0, 1]的一个随机数r,并比较 r 与t 的大小

4. 若r < t,则为s 生成一个新值(s∈[0, N)) ,否则s = (s + 1) mod N

5. 如果想继续加大页面访问序列的长度,返回第 2 步,否则结束

4.模拟测试思路 

基于相同的条件,系统均采用固定分配局部置换策略、相同的进程逻辑地址空间大小、分配给进程同样多的物理块、相同的页面访问序列、均预装入前三个页面,进行有关算法的测试,预计执行一百轮测试,以轮数为随机数种子,保证结果可以复现。

5.相关数据结构 

// 模拟页面
struct PAGE { 
    int  pages[MAXLEN];
    int  usenum; // 分配的最大页框数
    int  visitlen; // 访问序列长度
} pinfo;

// 模拟页表
struct MEM { 
    int time; // 访问记录
    int r; // 访问位
    int rw; // 修改位
    int pages; // 页号
} minfo;

MEM pagelist[MAXLEN]; // 分配页框
#include <iostream>
#include <thread>
#include <time.h>
using namespace std;

const int MAXLEN = 1024; // 最大页面数
const int epoch = 100; // 测试次数
int lossnum; // 缺页次数统计
int now; // 当前访问的页面
int replace; // 页面替换指针
int lossflag; // 是否缺页
int full; // 已使用的页框数
int rate[5][epoch];
int times[5][epoch];

struct PAGE {
    int  pages[MAXLEN];
    int  usenum; // 分配的最大页框数
    int  visitlen; // 访问序列长度
} pinfo;
struct MEM {
    int time; // 访问记录
    int r; // 访问位
    int rw; // 修改位
    int pages; // 页号
} minfo;
MEM pagelist[MAXLEN]; // 分配页框

void pageinit() { // 初始化页面数据
    pinfo.usenum = 3;
    pinfo.visitlen = 256;
    for (int i = 0; i < MAXLEN; i++)
        pinfo.pages[i] = -1;
}

void visitlist(int epoch) { // 随机生成访问序列
    int v = 16, w = 64, s = 128; // v为每个页面访问次数,w为每个页面访问的范围,s为页面访问的起始位置
    pageinit();
    srand(epoch); // 随机种子
    int t= rand() % 11; // 生成t
    for(int i = 0, j =0; i < 10; i++) {
        for(j = i * v; j < (i + 1) * v; j++) { // 生成v个[s, s+w]的随机数
            if(j > pinfo.visitlen) // 生成数量不能超序列长度
                break;
            pinfo.pages[j]= (s + (rand() % w)) % MAXLEN; // 随机数存储到访问序列中
        }
        if(rand() % 11 < t) // 如果r < t,则为p生成一个新值
            s = rand() % MAXLEN;
        else
            s = (s + 1) % MAXLEN;
    }
}

bool randBool() { // 读写随机数生成函数
    if(rand() % 11 > 7) return true;
    else return false;
}

bool inram(int page) { // 查找是否在内存
    for(int i = 0; i < pinfo.usenum; i++) {
        pagelist[i].time++;  // 访问记录++
    }
    for(int i = 0; i < pinfo.usenum; i++) {
        if(pagelist[i].pages == page) {
            lossflag = 0; // 不缺页置为0
            pagelist[i].time = 0; // 访问记录置0
            if(randBool()) {
                pagelist[i].r = 1;
                pagelist[i].rw = 1;
            }
            else
                pagelist[i].r = 1;
            return true;
        }
    }
    lossflag = 1; // 缺页置为1
    return false;
}

void OPT() {// 最佳淘汰算法
    replace = 0, lossnum = 0, full = 0, lossflag = 0;
    for(int i = 0; i < pinfo.usenum; i++) // 刷新页框
        pagelist[i].pages = -1;
    for(now = 0; now < pinfo.visitlen; now++) {
        if(full < pinfo.usenum) {
            if(!inram(pinfo.pages[now])) { // 不在内存则装入页面
                pagelist[replace].pages = pinfo.pages[now];
                replace = (replace + 1) % pinfo.usenum;
                full++, lossnum++; 
            }
        }
        else {
            if(!inram(pinfo.pages[now])) { // 不在内存则需置换
                int min, max = 0 ; // min为最近访问,max为最远访问
                for(int m = 0; m < pinfo.usenum ; m++) {
                    min = MAXLEN;
                    for(int n = now; n < pinfo.visitlen; n++) {
                        if (pinfo.pages[n] == pagelist[m].pages) {
                            min = n;
                            break;
                        }
                    }
                    if(max < min) {
                        max = min;
                        replace = m;
                    }
                }
                pagelist[replace].pages = pinfo.pages[now];
                replace = (replace + 1) % pinfo.usenum;
                lossnum++;
            }
        }
        std::this_thread::sleep_for(10ms);
    }
}

void FIFO(void) { // 先进先出淘汰算法
    replace = 0, lossnum = 0, full = 0, lossflag = 0;
    for(int i = 0; i < pinfo.usenum; i++)
        pagelist[i].pages = -1;
    for(now = 0; now < pinfo.visitlen; now++) {
        if(full < pinfo.usenum) { 
            if(!inram(pinfo.pages[now])) {
                pagelist[replace].pages = pinfo.pages[now];
                replace = (replace + 1) % pinfo.usenum;
                full++, lossnum++;
            }
        }
        else {
            if(!inram(pinfo.pages[now])) {
                pagelist[replace].pages = pinfo.pages[now];
                replace = (replace + 1) % pinfo.usenum;
                lossnum++;
            }
        }
        std::this_thread::sleep_for(10ms);
    }
}

void LRU(void) { // 最近最久未使用淘汰算法
    replace = 0, lossnum = 0, full = 0, lossflag = 0;
    for(int i = 0; i < pinfo.usenum; i++) {
        pagelist[i].pages = -1;
        pagelist[i].time = 0;
    } // 刷新页框
    for(now = 0; now < pinfo.visitlen; now++) {
        if(full < pinfo.usenum) {
            if(!inram(pinfo.pages[now])) {
                pagelist[replace].pages = pinfo.pages[now];
                replace = (replace + 1) % pinfo.usenum;
                full++, lossnum++;
            }
        }
        else {
            if(!inram(pinfo.pages[now])) {
                int max = 0; // 最久的访问记录
                for(int i = 1; i < pinfo.usenum; i++) {
                    if(pagelist[i].time > pagelist[max].time) {
                        max = i;
                    }
                }
                replace = max;
                pagelist[replace].pages = pinfo.pages[now];
                pagelist[replace].time = 0;
                lossnum++;
            }
        }
        std::this_thread::sleep_for(10ms);
    }
}

int replace0(int num) { // 简单Clock置换
    for(int i = 0; i < pinfo.usenum; i++) {
        if(pagelist[(i + num) % pinfo.usenum].r == 0 ) // 找到第一个访问位为0的页面
            return (i + num) % pinfo.usenum;
        pagelist[(i + num) % pinfo.usenum].r = 0; // 未找到则将所有访问位置0
    }
    for(int i = 0; i < pinfo.usenum; i++) {
        if(pagelist[(i + num) % pinfo.usenum].r == 0 )
            return (i + num) % pinfo.usenum;
    }
    return 0;
}

int replace1(int num) { // 改进的clock置换
    for(int i = 0; i < pinfo.usenum; i++) {
        if (pagelist[(i + num) % pinfo.usenum].r == 0 && pagelist[(i + num) % pinfo.usenum].rw == 0) // 先找访问位和修改位都为0的页面
            return (i + num) % pinfo.usenum;
    }
    for(int i = 0; i < pinfo.usenum; i++) {
        if (pagelist[(i + num) % pinfo.usenum].r == 0 && pagelist[(i + num) % pinfo.usenum].rw == 1) // 再找访问位为0,修改位为1的页面
            return (i + num) % pinfo.usenum;
        pagelist[(i + num) % pinfo.usenum].r = 0; // 未找到则将所有访问位置0
    }
    for(int i = 0; i < pinfo.usenum; i++) {
        if (pagelist[(i + num) % pinfo.usenum].r == 0 && pagelist[(i + num) % pinfo.usenum].rw == 0) // 再找访问位和修改位都为0的页面
            return (i + num) % pinfo.usenum;
    }
    for(int i = 0; i < pinfo.usenum; i++) {
        if (pagelist[(i + num) % pinfo.usenum].r == 0 && pagelist[(i + num) % pinfo.usenum].rw == 1) // 最后找访问位为0,修改位为1的页面
            return (i + num) % pinfo.usenum;
    }
    return 0;
}

void CLOCK(int choose) {
    int num = 0;
    replace = 0, lossnum = 0, full = 0, lossflag = 0;
    for(int i = 0; i < pinfo.usenum; i++) {
        pagelist[i].pages = -1;
        pagelist[i].rw = 0;
        pagelist[i].r = 0;
        pagelist[i].time = 0;
    }
    for(now = 0; now < pinfo.visitlen; now++) {
        if(full < pinfo.usenum) {
            if(!inram(pinfo.pages[now])) {
                pagelist[replace].pages = pinfo.pages[now];
                replace = (replace + 1) % pinfo.usenum;
                pagelist[replace].r = 1;
                full++, lossnum++;
            }
        }
        else {
            if(!inram(pinfo.pages[now])) {
                    if(choose == 1)
                        replace = replace1(num++); // choose=1,改进clock算法
                    else if(choose == 0) // choose=0,简单clock算法
                        replace = replace0(num++); 
                    pagelist[replace].pages = pinfo.pages[now];
                    pagelist[replace].r = 1;
                    lossnum++;
                }
        }
        std::this_thread::sleep_for(10ms);
    }
}

void calculate(int i, int j, clock_t start) { // 计算缺页率和运行时间
    rate[i][j] = (double)(lossnum) * 100 / now;
    times[i][j] = (double)(clock() - start) / 1000;
}

int main() {
    clock_t start;
    for(int i = 0; i < epoch; i++) {
        visitlist(i);
        start = clock();
        OPT();
        calculate(0, i, start);
        start = clock();
        FIFO();
        calculate(1, i, start);
        start = clock();
        LRU();
        calculate(2, i, start);
        start = clock();
        CLOCK(0);
        calculate(3, i, start);
        start = clock();
        CLOCK(1);
        calculate(4, i, start);
    }
    for(int i = 0; i < 5; i++) {
        if(i == 0) printf("OPT:    ");
        if(i == 1) printf("FIFO:   ");
        if(i == 2) printf("LRU:    ");
        if(i == 3) printf("CLOCK:  ");
        if(i == 4) printf("CLOCK+: ");
        int avrate = 0, avtime = 0;
        for(int j = 0; j < epoch; j++) {
            avrate += rate[i][j];
            avtime += times[i][j];
        }
        printf("Average replace rate = %.3lf%%  ", (double)(avrate) / epoch);
        printf("Average spend time: %.3lfs\n", (double)(avtime) / epoch);
    }
    return 0;
}

7.运行结果

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/115526.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

编写shell脚本,利用mysqldump实现mysql数据库分库分表备份

摘要&#xff1a;本文介绍了如何使用 Shell 脚本和 mysqldump 工具实现 MySQL 数据库的分库分表备份。通过编写脚本&#xff0c;我们可以自动化备份多个数据库以及每个数据库中的所有表&#xff0c;并将备份文件按照数据库和表的层次结构进行存储。 一、准备工作 在开始编写 Sh…

HMDD 4.0:miRNA-疾病关系数据库

拥有多项自主专利技 术和软件著作权&#xff0c;具 有丰富的数据库平台 搭建经验。 凌恩-盈飞团队 MicroRNA&#xff08;miRNA&#xff09;是一类重要的小非编码RNA&#xff0c;在疾病诊断和治疗中发挥着重要作用。人类 MicroRNA 疾病数据库 (HMDD) 为 miRNA 相关医学提供了…

【云原生基础】了解云原生,什么是云原生?

&#x1f4d1;前言 本文主要讲了云原生的基本概念和原则的文章&#xff0c;如果有什么需要改进的地方还请大佬指出⛺️ &#x1f3ac;作者简介&#xff1a;大家好&#xff0c;我是青衿&#x1f947; ☁️博客首页&#xff1a;CSDN主页放风讲故事 &#x1f304;每日一句&#x…

人工智能师求职面试笔试题及答案汇总

人工智能师求职面试笔试题及答案汇总 1.如何在Python中实现一个生成器&#xff1f; 答&#xff1a;在Python中&#xff0c;生成器是一种特殊类型的迭代器。生成器允许你在需要时才生成值&#xff0c;从而节省内存。生成器函数在Python中是通过关键字yield来实现的。例如&…

leetCode 137. 只出现一次的数字 II(拓展篇) + 模5加法器 + 真值表(数字电路)

leetCode 137. 只出现一次的数字 II 有其他的题解可看我的往期文章&#xff1a; leetCode 137. 只出现一次的数字 II 位运算 模3加法器 真值表&#xff08;数字电路&#xff09; 有限状态机-CSDN博客https://blog.csdn.net/weixin_41987016/article/details/134138112?sp…

生成带分表和水印的excel压缩文件

功能描述 将查询结果生成带分表和水印的excel压缩文件 功能点 1、将查询结果导出为excel文件 2、每个表格存放50万条数据&#xff0c;超过50万条数据&#xff0c;生成新的分表 3、生成的表格需要添加水印 4、将生成的全部分表&#xff0c;打包成zip压缩文件 引入依赖 <…

【LeetCode】每日一题 2023_11_2 环和杆(题目质量不错)

文章目录 刷题前唠嗑题目&#xff1a;环和杆题目描述代码与解题思路看看别人的题解 结语 刷题前唠嗑 今天是简单&#xff0c;我快乐了 题目&#xff1a;环和杆 题目链接&#xff1a;2103. 环和杆 题目描述 代码与解题思路 func countPoints(rings string) (ans int) {num…

强化学习的动态规划二

一、典型示例 考虑如下所示的44网格。 图1 非终端状态为S {1, 2, . . . , 14}。在每个状态下有四种可能的行为&#xff0c;A {up, down, right, left}&#xff0c;这些行为除了会将代理从网格上移走外&#xff0c;其他都会确定性地引起相应的状态转换。因此&#xff0c;例如&…

java入门,程序=数据结构+算法

一、前言 在学习java的时候&#xff0c;我印象最深的一句话是&#xff1a;程序数据结构算法&#xff0c;对于写java程序来说&#xff0c;这就是java的入门。 二、java基本数据结构与算法 1、数据类型 java中的数据类型8种基本数据类型&#xff1a; 整型 byte 、short 、int…

32 mysql in 的实现

前言 这里我们主要是来探讨一下 mysql 中 in 的使用, find_in_set 的使用 这两者 在我们实际应用中应该也是 非常常用的了 测试数据表如下 CREATE TABLE tz_test (id int(11) unsigned NOT NULL AUTO_INCREMENT,field1 varchar(16) DEFAULT NULL,field2 varchar(16) DEFAU…

macOS 下 starUML 软件激活方案

starUML每次打开都弹出提示其实挺烦的&#xff0c;于是研究了一下如何 po 解(激活)它。记录一下方法以便以后使用。 我觉得这个软件很好用&#xff0c;大型项目的所有图我都是用这个软件画的。 直接上步骤&#xff01;先关掉starUML 1、安装 asar&#xff0c;以便可以打开 asa…

4+1视图的理解和使用

软件架构 原文&#xff1a; Architectural Blueprints—The “41” View Model of Software Architecture 老外的原文还是很值得一看的&#xff0c;互联网上的很多文章理解得都比较粗浅 什么是软件架构&#xff1f;面试的时候很多面试官可能会问你最近在做的项目的架构。其实这…

通讯录(C语言文件版本)(超详细过程)

❇️❇️❇️❇️❇️❇️❇️❇️❇️❇️❇️❇️❇️ ❇️❇️❇️❇️ 不同的信念 ❇️❇️❇️❇️ ❇️❇️❇️ 决定不同的命运 ❇️❇️❇️ ❇️❇️❇️❇️❇️❇️❇️❇️❇️❇️❇️❇️ &#x1f4d6;通讯录 ✅具备的功能 ℹ️需要的头文件名 #include<…

警惕Mallox勒索病毒的最新变种mallox,您需要知道的预防和恢复方法。

尊敬的读者&#xff1a; 在这个数字时代&#xff0c;恶意软件不再是仅限于技术领域的威胁&#xff0c;而是每个人都可能面临的潜在风险。其中&#xff0c;.mallox勒索病毒崭露头角&#xff0c;它不仅能够以不可思议的方式加密您的数据&#xff0c;还能要求您支付赎金以获取解密…

基于饥饿游戏算法的无人机航迹规划-附代码

基于饥饿游戏算法的无人机航迹规划 文章目录 基于饥饿游戏算法的无人机航迹规划1.饥饿游戏搜索算法2.无人机飞行环境建模3.无人机航迹规划建模4.实验结果4.1地图创建4.2 航迹规划 5.参考文献6.Matlab代码 摘要&#xff1a;本文主要介绍利用饥饿游戏算法来优化无人机航迹规划。 …

运维基础-Docker容器命令部署

Docker基础知识 安装问题-有podmanCentos8使用yum install docker -y时&#xff0c;默认安装的是podman-docker软件安装docker yum list installed | grep dockeryum -y remove xxxxDocker安装配置下载安装docker启动docker&#xff0c;并设置开机启动下载所需镜像 centos镜像进…

红海云签约澳森集团,为钢铁行业人力资源数字化转型注入新动能

辛集市澳森特钢集团有限公司&#xff08;以下简称“澳森集团”&#xff09;是集钢铁冶炼、轧钢及钢材深加工、新型建材、国际贸易、房地产开发、酒店餐饮、热力供应于一体的大型钢铁联合企业&#xff0c;是华北地区最具品牌影响力和核心竞争力的综合性大型企业集团。 近日&…

批量剪辑:高效处理视频文件的图文解析,AI智剪方法

随着视频文件的数量和种类不断增加&#xff0c;传统的视频剪辑方法往往效率低下且费时费力。为了解决这个问题&#xff0c;批量剪辑和AI智剪技术应运而生。在剪辑过程中&#xff0c;AI智剪可自动调整画面质量、音效、色彩等参数&#xff0c;以保证视频质量。它们可以帮助我们高…

C++定义一个 Student 类,在该类定义中包括:一个数据成员 score(分数)及两个静态数据 成员 total(总分)和学生人数 count

完整代码&#xff1a; /*声明一个Student类&#xff0c;在该类中包括一个数据成员score&#xff08;分数&#xff09;、两个静态数据成员total_score&#xff08;总分&#xff09;和count&#xff08;学生人数&#xff09;&#xff1b;还包括一个成员函数account&#xff08;&…

Sqoop的安装和使用

目录 一.安装 二.导入 1.全量导入 一.MySQL导入HDFS 二.MySQL导入Hive 2.增量导入 一.过滤导入hdfs/hive 二.导出 一.安装 1.下载地址&#xff1a;sqoop下载地址 2.解压 tar -zxvf ./sqoop-1.4.7.bin__hadoop-2.6.0.tar.gz -C ../module/ 3.改名和配置归属权限 #改名…