[操作系统作业]页面置换算法实现（C++）

devtools/2024/11/12 19:44:53/

💓博主csdn个人主页：小小unicorn
⏩专栏分类：linux
🚚代码仓库：小小unicorn的代码仓库🚚
🌹🌹🌹关注我带你学习编程知识

目录

  • 必做题
    • 代码分析（重点以时间统计）
      • 1. 引入 `<chrono>` 库
      • 2. 开始计时
      • 3. 执行被测代码
      • 4. 结束计时
      • 5. 计算执行时间
      • 6. 对每个算法重复以上步骤
      • 7. 输出结果
      • 总结1
    • 运行结果
    • 结果分析（我们以块数为3为例）
      • 缺页次数比较
      • 2. 执行时间比较
      • 3. 性能评估
      • 4. 总结
  • 选做题
      • 1. 计算页面走向
      • 页面走向
      • 2. 定义内存和算法
      • C++ 实现
      • 代码说明
      • 结果分析

必做题

在一个请求分页系统中，假如一个作业的页面走向为1,2,3,4,2,1,5,6,2,1,2,3,7,6,3,2,1,2,3,6，当分配给该作业的物理块数分别为3和5时，分别采用FIFO/OPT/LRU页面置换算法，计算中访问过程中发生的缺页次数和缺页率。（建议增加必要的算法执行时间统计）

实现算法如下：

#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <chrono>using namespace std;class Base
{
public:Base(int m, int n, int* p) :m(m), n(n), p(p), missed(0),field(new int[m] {}),blocks(new int[m]) {for (int j = 0; j < m; ++j)blocks[j] = -1;}int getMissedCount() const { return missed; } // 获取缺页次数protected:int m;int n;int* p; // 页面调用序列int i{}; // 页面调用序列的指针int missed; // 缺页次数int* field; // 访问字段int* blocks; // 物理块void run(); // 运行函数
private:float rateOfMissingPage{}; // 缺页率bool isHit(); // 检查是否命中virtual int blockSelect() = 0; // 换出页面选择函数virtual void printAlgorithmName() const = 0;void pageExchange(int blockInd, int page); // 页面换出函数void updateField(); // 更新访问字段void printBlocks();void printRateOfMissingPage() const;
};void Base::pageExchange(int blockInd, int page)
{blocks[blockInd] = page;
}void Base::printBlocks()
{int t;for (int j = 0; j < m; ++j){t = blocks[j];if (t >= 0) printf("%d ", t);else printf("- ");}
}bool Base::isHit()
{int page = p[i];for (int j = 0; j < m; ++j)if (page == blocks[j]){// 命中则修改访问字段field[j] = 0;return true;}return false;
}void Base::run()
{int blockInd;printAlgorithmName();for (i = 0; i < n; ++i){updateField();// 尚有空闲物理块if (i < m){blocks[i] = p[i];blockInd = i;}else{// 命中if (isHit()){printf("\033[32m%d: ", p[i]);printBlocks();printf("(hit)\033[0m\n");continue;}else{ // 未命中blockInd = blockSelect();pageExchange(blockInd, p[i]);}}printf("\033[31m%d: ", p[i]);printBlocks();printf("(miss)\033[0m\n");++missed;field[blockInd] = 0;}rateOfMissingPage = (float)missed / (float)n;printRateOfMissingPage();
}void Base::printRateOfMissingPage() const
{printf("缺页率为： %.3f\n", rateOfMissingPage);
}void Base::updateField()
{for (int j = 0; j < m; ++j)++field[j];
}class OPT : public Base
{
public:OPT(int m, int n, int* p) : Base(m, n, p) { run(); }private:int blockSelect() override{int j, k;int obj_page;int look_back = 0;for (j = 0; j < m; ++j){for (k = i + 1; k < n; ++k){if (blocks[j] == p[k]){if (k > look_back){obj_page = j;look_back = k;}break;}}if (k == n) {obj_page = j;break;}}return obj_page;}void printAlgorithmName() const override{cout << "OPT: " << endl;}
};class FIFO : public Base
{
public:FIFO(int m, int n, int* p) : Base(m, n, p) { run(); }private:int blockSelect() override{return (missed) % m;}void printAlgorithmName() const override{cout << "FIFO: " << endl;}
};class LRU : public Base
{
public:LRU(int m, int n, int* p) : Base(m, n, p) { run(); }private:int blockSelect() override{int tag = 0;int obj_page;for (int j = 0; j < m; ++j){if (tag < field[j]){tag = field[j];obj_page = j;}}return obj_page;}void printAlgorithmName() const override{cout << "LRU: " << endl;}
};int main()
{int m = 0; // 块数// 分配给该作业的物理块数cout << "请输入分配给该作业的物理块数:" << endl;cin >> m;int n = 0; // 页面访问次数cout << "请输入页面访问次数: ";cin >> n;// 动态分配数组int* P = new int[n];cout << "请输入页面访问序列: ";for (int i = 0; i < n; i++){cin >> P[i];}// 时间统计auto start = chrono::high_resolution_clock::now();OPT opt(m, n, P);auto end = chrono::high_resolution_clock::now();auto durationOpt = chrono::duration_cast<chrono::microseconds>(end - start).count();start = chrono::high_resolution_clock::now();FIFO fifo(m, n, P);end = chrono::high_resolution_clock::now();auto durationFifo = chrono::duration_cast<chrono::microseconds>(end - start).count();start = chrono::high_resolution_clock::now();LRU lru(m, n, P);end = chrono::high_resolution_clock::now();auto durationLru = chrono::duration_cast<chrono::microseconds>(end - start).count();// 打印缺页次数和执行时间cout << "OPT 缺页次数: " << opt.getMissedCount() << ", 执行时间: " << durationOpt << " 微秒" << endl;cout << "FIFO 缺页次数: " << fifo.getMissedCount() << ", 执行时间: " << durationFifo << " 微秒" << endl;cout << "LRU 缺页次数: " << lru.getMissedCount() << ", 执行时间: " << durationLru << " 微秒" << endl;// 释放动态分配的内存delete[] P;return 0;
}

代码分析（重点以时间统计）

我们时间统计的部分主要使用了 C++ 的 <chrono> 库来测量代码块的执行时间。以下是对这部分代码的详细解释：

1. 引入 <chrono> 库

#include <chrono>

这一行代码引入了 <chrono> 库，它提供了时间处理的功能，包括高精度计时器。

2. 开始计时

auto start = chrono::high_resolution_clock::now();

这行代码使用 chrono::high_resolution_clock::now() 来获取当前时间点，并将其存储在 start 变量中。这个时间点代表了计时的开始。

  • high_resolution_clock 是 C++ 中提供的一个高精度时钟，适合用于测量较短时间的运行。
  • auto 关键字自动推导变量类型，这里 start 将是一个时间点类型。

3. 执行被测代码

OPT opt(m, n, P);

在这行代码中，调用了 OPT 算法的构造函数。这段代码会执行页面置换算法的主要逻辑，并记录缺页次数。

4. 结束计时

auto end = chrono::high_resolution_clock::now();

这行代码获取了当前时间点，存储在 end 变量中，表示计时的结束。

5. 计算执行时间

auto durationOpt = chrono::duration_cast<chrono::microseconds>(end - start).count();

在这一行中，执行了以下操作：

  • end - start 计算了两个时间点之间的时间差，这个结果是一个持续时间对象（duration）。
  • chrono::duration_cast<chrono::microseconds> 将这个持续时间对象转换为微秒（microseconds）单位。你可以选择不同的单位，比如秒（seconds）、毫秒（milliseconds）等，根据需求而定。
  • .count() 方法返回这个时间差的数值，即以微秒为单位的执行时间。

6. 对每个算法重复以上步骤

对 FIFO 和 LRU 算法同样进行开始计时、执行算法和结束计时的操作，确保每个算法的执行时间都能被准确记录。

7. 输出结果

最后，输出每个算法的缺页次数和执行时间：

cout << "OPT 缺页次数: " << opt.getMissedCount() << ", 执行时间: " << durationOpt << " 微秒" << endl;

这样,我们就能够清晰地看到每个页面置换算法的缺页次数以及它们的执行时间，便于对比和分析不同算法的性能。

总结1

使用 <chrono> 库来进行时间统计能够提供高精度的性能测量，适用于分析程序性能或调试。通过这种方式，你可以识别出性能瓶颈，并作出相应的优化。

运行结果

运行结果如下：

块数为3时：
在这里插入图片描述

块数为5时：
在这里插入图片描述

结果分析（我们以块数为3为例）

缺页次数比较

  • OPT 算法: 缺页次数为 11，是所有算法中最少的。这是因为 OPT 算法使用了未来知识，能够根据未来的页面请求来选择最合适的页面替换，确保在执行过程中尽量减少缺页。
  • FIFO 算法: 缺页次数为 16，表现中等。FIFO 算法简单地按照页面进入的顺序替换页面，虽然实现简单，但在某些情况下可能导致较多的缺页（例如，“Belady’s Anomaly”）。
  • LRU 算法: 缺页次数为 15，略优于 FIFO，但仍明显高于 OPT。LRU 算法通过替换最近最少使用的页面来降低缺页率，通常能有效地减少缺页，但没有利用未来的信息，因此在某些情况下性能不如 OPT。

2. 执行时间比较

  • OPT 算法: 执行时间为 5735 微秒，是最快的。这与缺页次数的结果相符，因为更少的缺页通常意味着更高的执行效率。
  • FIFO 算法: 执行时间为 8051 微秒，相对较慢。虽然 FIFO 算法简单，但由于其简单的替换策略，可能导致更多的缺页，从而增加执行时间。
  • LRU 算法: 执行时间为 19705 微秒，是所有算法中最慢的。LRU 的实现相对复杂，因为需要跟踪每个页面的使用情况，这增加了时间开销，尤其是在页面访问次数较多时。

3. 性能评估

  • OPT 是最优的选择，虽然其实现可能不适合实际应用（因为不能提前知道未来的页面请求）。
  • FIFO 和 LRU 是两种常见的替换算法，FIFO 实现简单，但可能在某些情况下表现不佳，而 LRU 更加复杂，可能在资源利用上更优，但开销更大。

4. 总结

综合缺页次数和执行时间，OPT 算法是最有效的选择，尤其是在缺页次数和执行时间上都表现最佳。FIFO 和 LRU 在执行时间和缺页次数上有差距，具体选择哪种算法还需考虑实际应用场景的需求，比如内存资源的限制、算法的实现复杂度等。

选做题

考虑下面存储访问序列，该程序大小为460字：10,11,104,170,73,309,185,245,246,434,458,364，假设页面大小是100字，请给出该访问序列的页面走向。又假设该程序基本可用内存是200字，采用FIFO置换算法，求出其缺页率。如果采用LRU页面算法，缺页率是多少？如果采用最优淘汰算法，其缺页率又是多少？（建议增加必要的算法执行时间统计）

为了分析这个存储访问序列并计算缺页率，我们可以首先计算出访问序列对应的页面，然后使用 FIFO、LRU 和 OPT 算法来进行页面置换。下面是详细的步骤和 C++ 实现：

1. 计算页面走向

给定的页面大小是 100 字，因此我们可以通过将每个字节地址除以 100 来计算页面编号。

  • 存储访问序列: 10, 11, 104, 170, 73, 309, 185, 245, 246, 434, 458, 364
  • 对应页面编号:
    • 10 / 100 = 0
    • 11 / 100 = 0
    • 104 / 100 = 1
    • 170 / 100 = 1
    • 73 / 100 = 0
    • 309 / 100 = 3
    • 185 / 100 = 1
    • 245 / 100 = 2
    • 246 / 100 = 2
    • 434 / 100 = 4
    • 458 / 100 = 4
    • 364 / 100 = 3

页面走向

根据上述计算，访问的页面序列为：0, 0, 1, 1, 0, 3, 1, 2, 2, 4, 4, 3

2. 定义内存和算法

假设可用内存为 200 字，即可以容纳 2 个页面。我们将实现 FIFO、LRU 和 OPT 三种页面置换算法，计算缺页率，并进行时间统计。

C++ 实现

#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <chrono>
#include <vector>
#include <unordered_map>using namespace std;class PageReplacement 
{
public:PageReplacement(int m, const vector<int>& pages): m(m), pages(pages), missed(0), n(pages.size()) {}virtual void run() = 0;int getMissedCount() const { return missed; }protected:int m; // 可用页面数vector<int> pages; // 页面访问序列int missed; // 缺页次数int n; // 页面序列长度
};class FIFO : public PageReplacement 
{
public:FIFO(int m, const vector<int>& pages) : PageReplacement(m, pages) { run(); }void run() override {vector<int> frame(m, -1);int index = 0;for (int page : pages) {bool hit = false;for (int f : frame) {if (f == page) {hit = true;break;}}if (!hit) {frame[index] = page;index = (index + 1) % m;missed++;}}}
};class LRU : public PageReplacement 
{
public:LRU(int m, const vector<int>& pages) : PageReplacement(m, pages) { run(); }void run() override {vector<int> frame(m, -1);unordered_map<int, int> pageIndex; // 页面到索引的映射int index = 0;for (int page : pages) {bool hit = pageIndex.find(page) != pageIndex.end();if (!hit) {if (index < m) {frame[index] = page;pageIndex[page] = index;index++;}else {// 找到最近最少使用的页面int lruIndex = 0;for (int j = 1; j < m; j++) {if (pageIndex[frame[j]] < pageIndex[frame[lruIndex]]) {lruIndex = j;}}pageIndex.erase(frame[lruIndex]);frame[lruIndex] = page;pageIndex[page] = lruIndex;}missed++;}else {// 更新页面使用时间pageIndex[page] = index++;}}}
};class OPT : public PageReplacement 
{
public:OPT(int m, const vector<int>& pages) : PageReplacement(m, pages) { run(); }void run() override {vector<int> frame(m, -1);int index = 0;for (int page : pages) {bool hit = false;for (int f : frame) {if (f == page) {hit = true;break;}}if (!hit) {if (index < m) {frame[index] = page;index++;}else {// 找到将来最久未使用的页面int farthest = -1;int replaceIndex = -1;for (int j = 0; j < m; j++) {int nextUse = findNextUse(frame[j], index);if (nextUse > farthest) {farthest = nextUse;replaceIndex = j;}}frame[replaceIndex] = page;}missed++;}}}private:int findNextUse(int page, int start) {for (int j = start; j < n; j++) {if (pages[j] == page) return j;}return n; // 表示不再使用}
};int main() 
{// 页面访问序列vector<int> accessSequence = { 10, 11, 104, 170, 73, 309, 185, 245, 246, 434, 458, 364 };vector<int> pages;// 计算页面走向for (int address : accessSequence) {pages.push_back(address / 100); // 根据页面大小计算页面编号}int m = 2; // 可用页面数// FIFO算法auto start = chrono::high_resolution_clock::now();FIFO fifo(m, pages);auto end = chrono::high_resolution_clock::now();auto durationFifo = chrono::duration_cast<chrono::microseconds>(end - start).count();// LRU算法start = chrono::high_resolution_clock::now();LRU lru(m, pages);end = chrono::high_resolution_clock::now();auto durationLru = chrono::duration_cast<chrono::microseconds>(end - start).count();// OPT算法start = chrono::high_resolution_clock::now();OPT opt(m, pages);end = chrono::high_resolution_clock::now();auto durationOpt = chrono::duration_cast<chrono::microseconds>(end - start).count();// 打印结果cout << "FIFO 缺页次数: " << fifo.getMissedCount() << ", 执行时间: " << durationFifo << " 微秒" << endl;cout << "LRU 缺页次数: " << lru.getMissedCount() << ", 执行时间: " << durationLru << " 微秒" << endl;cout << "OPT 缺页次数: " << opt.getMissedCount() << ", 执行时间: " << durationOpt << " 微秒" << endl;return 0;
}

代码说明

  • 页面走向计算: 通过将每个字节地址除以 100 得到页面编号。
  • 页面置换算法: 实现了 FIFO、LRU 和 OPT 三种算法，每个算法在 run 方法中执行页面替换逻辑。
  • 时间统计: 使用 chrono 库来测量每种算法的执行时间。

结果分析

在这里插入图片描述

运行该程序后，会输出每种算法的缺页次数和执行时间。你可以根据缺页次数判断每种算法的性能，通常来说，OPT 算法的缺页次数最少，而 FIFO 和 LRU 可能会有所不同，具体取决于页面访问序列。


http://www.ppmy.cn/devtools/132479.html

相关文章

Docker 的基本概念和优势，以及在应用程序开发中的实际应用

Docker 的基本概念和优势，以及在应用程序开发中的实际应用

Docker是一种容器化平台&#xff0c;它允许开发者将应用程序及其依赖项打包为一个独立的、可移植的容器&#xff0c;然后在任何环境中运行。它的基本概念包括以下几点&#xff1a; 镜像&#xff08;Image&#xff09;&#xff1a;一个镜像是一个可执行包&#xff0c;它包含了运…
阅读更多...
yelp数据集上识别潜在的热门商家

yelp数据集上识别潜在的热门商家

yelp数据集是研究B2C业态的一个很好的数据集&#xff0c;要识别潜在的热门商家是一个多维度的分析过程&#xff0c;涉及用户行为、商家特征和社区结构等多个因素。从yelp数据集里我们可以挖掘到下面信息有助于识别热门商家 用户评分和评论分析 评分均值: 商家的平均评分是反映其…
阅读更多...
香港航空 阿里滑块 acw_sc__v3 分析

香港航空 阿里滑块 acw_sc__v3 分析

声明: 本文章中所有内容仅供学习交流使用&#xff0c;不用于其他任何目的&#xff0c;抓包内容、敏感网址、数据接口等均已做脱敏处理&#xff0c;严禁用于商业用途和非法用途&#xff0c;否则由此产生的一切后果均与作者无关&#xff01; 有相关问题请第一时间头像私信联系我删…
阅读更多...
【开源项目】经典开源项目数字孪生智慧小镇——开源工程及源码

【开源项目】经典开源项目数字孪生智慧小镇——开源工程及源码

飞渡科技数字孪生小镇管理平台&#xff0c;依托自研数字孪生引擎平台&#xff0c;将5G、物联网、大数据、人工智能等数字化技术融合应用&#xff0c;采集、整合、应用小镇的规划、运营、管理等数据&#xff0c;实现特色小镇全域管理系统化以及精细化。 基于地理信息系统&#x…
阅读更多...
什么是 ASP.NET Core？与 ASP.NET MVC 有什么区别？

什么是 ASP.NET Core？与 ASP.NET MVC 有什么区别？

ASP.NET Core 是一个现代的开源框架&#xff0c;用于构建跨平台的Web应用程序。它由微软开发&#xff0c;支持运行在 Windows、macOS 和 Linux 上&#xff0c;与传统的 ASP.NET 框架相比&#xff0c;ASP.NET Core 提供了更高的性能、更小的内存占用、以及更灵活的部署模式。ASP…
阅读更多...
day04 vue学习

day04 vue学习

将登录系统和 To-Do List 系统结合在一起&#xff0c;我们可以创建一个简单的 Vue 应用&#xff0c;该应用具备用户登录功能&#xff0c;并在用户登录后展示其个人 To-Do List。用户可以添加、删除、标记任务完成状态等。我们可以使用 Pinia 来管理用户登录状态和 To-Do 列表数…
阅读更多...
你是我的映射，我是你的值：C++ map 中的心灵共鸣

你是我的映射，我是你的值：C++ map 中的心灵共鸣

文章目录 map的概念一、map的使用1. 插入删除相关1&#xff09;插入(1) 插入语法(1) 插入语法 2&#xff09;删除 二. map的遍历三、map重载operator[]四、小试&#x1f402;&#x1f52a;1. 前K个高频单词2. 单词识别 总结 map的概念 map是key_value的模型&#xff1a; 一棵树…
阅读更多...
STM32实现串口接收不定长数据

STM32实现串口接收不定长数据

原理 STM32实现串口接收不定长数据&#xff0c;主要靠的就是串口空闲&#xff08;idle&#xff09;中断,此中断的触发条件与接收的字节数无关&#xff0c;只有当Rx引脚无后续数据进入时&#xff08;串口空闲时&#xff09;&#xff0c;认为这时候代表一个数据包接收完成了&…
阅读更多...
最新文章

Copyright @ 2022~2023