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

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

必做题

在一个请求分页系统中，假如一个作业的页面走向为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 可能会有所不同，具体取决于页面访问序列。