FIFO和LRU算法实现操作系统中主存管理

FIFO，用数组实现

1和2都是使用nextReplace实现新页面位置的更新

1、不精确时间：用ctime输出运行时间都是0.00秒

#include <iostream>
#include <iomanip>
#include<ctime>//用于计算时间
using namespace std;// 页访问顺序
int pages[20] = { 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1 };// FIFO算法
void fifo(int n) {int memory[5] = { -1, -1, -1, -1, -1 };  // 用于存储主存块，初始化为 -1 表示空int table[5][20] = { -1 };               // 用于记录每次访问的内存状态，初始化为 -1 表示空bool status[20];                         // 记录是否缺页int pageFaults = 0;                      // 缺页次数int nextReplace = 0;                     // 记录下一个要替换的位置// 获取开始时间（时钟周期数）clock_t start = clock();// 遍历每个页面访问for (int j = 0; j < 20; j++) {int page = pages[j];bool found = false;// 检查页面是否已在内存中for (int i = 0; i < n; i++) {if (memory[i] == page) {found = true;break;}}if (!found) {  // 缺页情况memory[nextReplace] = page;       // 替换页面nextReplace = (nextReplace + 1) % n; // 更新替换位置status[j] = false;                // 标记缺页pageFaults++;}else {status[j] = true;                 // 标记命中}// 记录当前内存状态到表格for (int i = 0; i < n; i++) {table[i][j] = memory[i];}}// 获取结束时间（时钟周期数）clock_t end = clock();// 输出结果表格cout << "主存块号 ";for (int j = 0; j < 20; j++) {cout << pages[j] << " ";}cout << endl;for (int i = 0; i < n; i++) {cout << "   " << i << "     ";for (int j = 0; j < 20; j++) {if (table[i][j] == -1) {cout << "  ";  // 空块显示为空格}else {cout << table[i][j] << " ";}}cout << endl;}// 输出缺页标记cout << "是否缺页 ";for (int j = 0; j < 20; j++) {if (status[j]) {cout << "\u221A ";  // Unicode "√"}else {cout << "\u00D7 ";  // Unicode "×"}}cout << endl;cout << "FIFO 缺页率: " << fixed << setprecision(2) << (float)pageFaults / 20 * 100 << "%" << endl;cout << "运行时间: " << (double)(end - start) / CLOCKS_PER_SEC << " 秒" << endl; // 输出运行时间
}int main() {cout << "内存容量为 3 块:\n";fifo(3);cout << endl;cout << "内存容量为 4 块:\n";fifo(4);return 0;
}

2、精确时间：用chrono输出运行时间都是xx微秒，输出时间不定

#include <iostream>
#include <iomanip>
#include <chrono> // 引入chrono库using namespace std;
using namespace std::chrono; // 使用chrono命名空间// 页访问顺序
int pages[20] = { 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1 };// FIFO算法
void fifo(int n) {int memory[5] = { -1, -1, -1, -1, -1 };  // 用于存储主存块，初始化为 -1 表示空int table[5][20] = { -1 };               // 用于记录每次访问的内存状态，初始化为 -1 表示空bool status[20];                         // 记录是否缺页int pageFaults = 0;                      // 缺页次数int nextReplace = 0;                     // 记录下一个要替换的位置// 获取开始时间auto start = high_resolution_clock::now();// 遍历每个页面访问for (int j = 0; j < 20; j++) {int page = pages[j];bool found = false;// 检查页面是否已在内存中for (int i = 0; i < n; i++) {if (memory[i] == page) {found = true;break;}}if (!found) {  // 缺页情况memory[nextReplace] = page;       // 替换页面nextReplace = (nextReplace + 1) % n; // 更新替换位置status[j] = false;                // 标记缺页pageFaults++;}else {status[j] = true;                 // 标记命中}// 记录当前内存状态到表格for (int i = 0; i < n; i++) {table[i][j] = memory[i];}}// 获取结束时间auto stop = high_resolution_clock::now();auto duration = duration_cast<microseconds>(stop - start);// 输出结果表格cout << "主存块号 ";for (int j = 0; j < 20; j++) {cout << pages[j] << " ";}cout << endl;for (int i = 0; i < n; i++) {cout << "   " << i << "     ";for (int j = 0; j < 20; j++) {if (table[i][j] == -1) {cout << "  ";  // 空块显示为空格}else {cout << table[i][j] << " ";}}cout << endl;}// 输出缺页标记cout << "是否缺页 ";for (int j = 0; j < 20; j++) {if (status[j]) {cout << "\u221A ";  // Unicode "√"}else {cout << "\u00D7 ";  // Unicode "×"}}cout << endl;cout << "FIFO 缺页率: " << fixed << setprecision(2) << (float)pageFaults / 20 * 100 << "%" << endl;cout << "运行时间: " << duration.count() << " 微秒" << endl; // 输出运行时间
}int main() {cout << "内存容量为 3 块:\n";fifo(3);cout << endl;cout << "内存容量为 4 块:\n";fifo(4);return 0;
}

3、数组模拟队列、类似滑动窗口

#include <iostream>
#include <iomanip>
#include <chrono>
#include <cstring>using namespace std;
using namespace std::chrono;const int N = 1010;
int memory[N];//每次查找页面进行记录的滑动窗口
int table[5][20]; // 最终输出的表格状态
// 页访问顺序
int pages[20] = { 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1 };// FIFO算法
void fifo(int n) {memset(memory, 0x3f, sizeof memory);bool status[20];  // 记录是否缺页int pageFaults = 0;       // 缺页次数int hh = 0, tt = -1;      // 队首和队尾指针auto start = high_resolution_clock::now(); // 获取开始时间for (int j = 0; j < 20; j++) {int page = pages[j];bool found = false;// 检查页面是否已在内存中for (int i = hh; i <= tt; i++) {if (memory[i] == page) {found = true;break;}}if (!found) {  // 缺页情况memory[++tt] = page; // 新页面加入队尾// 控制滑动窗口大小为 nif (tt - hh + 1 > n) {hh++; // 超过容量，队首出队}status[j] = false;  // 标记缺页pageFaults++;}else {status[j] = true;   // 标记命中}// 记录当前内存状态到表格for (int i = 0; i < n; i++) {//如果只写memory[hh]的话不就移动队首指针了吗，不可以，现在是赋值阶段，只需要控制负责赋值的滑动指针首先不能超过队尾指针，确保在滑动窗口范围内，//因为有可能这个滑动窗口不足n长，你就会多余赋值本来不能存在的页面号赋值成0x3f，其次需要满足当前检查是否缺页的一次记录memory，该位置是否有值if (i + hh <= tt && memory[i + hh] != 0x3f) {table[i][j] = memory[i + hh];}else {table[i][j] = -1; // 空位显示为 -1}}}auto stop = high_resolution_clock::now(); // 获取结束时间auto duration = duration_cast<microseconds>(stop - start);// 输出结果表格cout << "主存块号 ";for (int j = 0; j < 20; j++) {cout << pages[j] << " ";}cout << endl;for (int i = 0; i < n; i++) {cout << "   " << i << "     ";for (int j = 0; j < 20; j++) {if (table[i][j] == -1) {cout << "  ";  // 空块显示为空格}else {cout << table[i][j] << " ";}}cout << endl;}// 输出缺页标记cout << "是否缺页 ";for (int j = 0; j < 20; j++) {cout << (status[j] ? "\u221A " : "\u00D7 ");//unicode编码，前者代表true则不缺页是√标识，后者代表false是缺页×表示}cout << endl;cout << "FIFO 缺页率: " << fixed << setprecision(2) << (float)pageFaults / 20 * 100 << "%" << endl;cout << "运行时间: " << duration.count() << " 微秒" << endl;
}int main() {cout << "内存容量为 3 块:\n";fifo(3);cout << endl;cout << "内存容量为 4 块:\n";fifo(4);return 0;
}

朴素版算缺页率

#include <iostream>
#include <ctime>
#include <cstring>using namespace std;const int N = 1010;
int memory[N];//每次查找页面进行记录的滑动窗口
int table[5][20]; // 最终输出的表格状态
// 页访问顺序
int pages[20] = { 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1 };// FIFO算法
void fifo(int n) {memset(memory, 0x3f, sizeof memory);bool status[20];  // 记录是否缺页int pageFaults = 0;       // 缺页次数int hh = 0, tt = -1;      // 队首和队尾指针clock_t start=clock(); // 获取开始时间for (int j = 0; j < 20; j++) {int page = pages[j];bool found = false;// 检查页面是否已在内存中for (int i = hh; i <= tt; i++) {if (memory[i] == page) {found = true;break;}}if (!found) {  // 缺页情况memory[++tt] = page; // 新页面加入队尾// 控制滑动窗口大小为 nif (tt - hh + 1 > n) {hh++; // 超过容量，队首出队}status[j] = false;  // 标记缺页pageFaults++;}else {status[j] = true;   // 标记命中}// 记录当前内存状态到表格for (int i = 0; i < n; i++) {//如果只写memory[hh]的话不就移动队首指针了吗，不可以，现在是赋值阶段，只需要控制负责赋值的滑动指针首先不能超过队尾指针，确保在滑动窗口范围内，//因为有可能这个滑动窗口不足n长，你就会多余赋值本来不能存在的页面号赋值成0x3f，其次需要满足当前检查是否缺页的一次记录memory，该位置是否有值if (i + hh <= tt && memory[i + hh] != 0x3f) {table[i][j] = memory[i + hh];}else {table[i][j] = -1; // 空位显示为 -1}}}clock_t end = clock(); // 获取结束时间// 输出结果表格cout << "主存块号 ";for (int j = 0; j < 20; j++) {cout << pages[j] << " ";}cout << endl;for (int i = 0; i < n; i++) {cout << "   " << i << "     ";for (int j = 0; j < 20; j++) {if (table[i][j] == -1) {cout << "  ";  // 空块显示为空格}else {cout << table[i][j] << " ";}}cout << endl;}// 输出缺页标记cout << "是否缺页 ";for (int j = 0; j < 20; j++) {cout << (status[j] ? "\u221A " : "\u00D7 ");//unicode编码，前者代表true则不缺页是√标识，后者代表false是缺页×表示}cout << endl;cout << "FIFO 缺页率: " << (float)pageFaults / 20 * 100 << "%" << endl;cout << "运行时间: " << (double)(end-start)/CLOCKS_PER_SEC << " 秒" << endl;}int main() {cout << "内存容量为 3 块:\n";fifo(3);cout << endl;cout << "内存容量为 4 块:\n";fifo(4);return 0;
}

FIFO，用链表实现

LRU，用计数器实现

#include <iostream>
#include <ctime>
#include <cstring>
#include <unordered_map>using namespace std;const int N = 1010;
int table[5][20]; // 最终输出的表格状态
unordered_map<int, int> m; // 键为page号，值为count值
int pages[20] = { 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1 };void lru(int n) {memset(table, -1, sizeof table);m.clear();bool status[20]; // 记录是否缺页int pageFaults = 0; // 缺页次数clock_t start = clock(); // 获取开始时间for (int j = 0; j < 20; j++) {int page = pages[j];if (!m.count(page)) { // 没命中就要加入或者替换页面if (m.size() >= n) {// 找到count最大的页面进行替换int maxpage = -1, maxcounts = -1;for (auto p : m) {if (p.second > maxcounts) {maxpage = p.first;maxcounts = p.second;}}m.erase(maxpage);}m[page] = 0;//没命中且主存没满则直接加入页面pageFaults++;status[j] = false; // 标记缺页}else {status[j] = true; // 标记命中m[page] = 0;}// 更新所有页面的count值：命中则置0，没命中加入新页面——满足条件则不加1即可，不管加不加入新页面，其他没中的页面都是要count+1的for (auto& p : m) {if (p.first != page) {p.second += 1;}}// 更新当前主存块内存在的页面int i = 0;for (auto p : m) {if (i < n) {//用一个i去便利贮存块，而不用fortable[i][j] = p.first;i++;}}//一开始写错了：/*for (int i = 0; i < n; i++) {for (auto p : m) {table[i][j] = p.first;}}*/}clock_t end = clock(); // 获取结束时间// 输出结果表格cout << "主存块号 ";for (int j = 0; j < 20; j++) {cout << pages[j] << " ";}cout << endl;for (int i = 0; i < n; i++) {cout << "   " << i << "     ";for (int j = 0; j < 20; j++) {if (table[i][j] == -1) {cout << "  "; // 空块显示为空格}else {cout << table[i][j] << " ";}}cout << endl;}// 输出缺页标记cout << "是否缺页 ";for (int j = 0; j < 20; j++) {cout << (status[j] ? "\u221A " : "\u00D7 ");}cout << endl;cout << "LRU 缺页率: " << (float)(pageFaults) / 20 * 100 << "%" << endl;cout << "运行时间: " << (double)(end - start) / CLOCKS_PER_SEC << " 秒" << endl;
}int main() {cout << "内存容量为 3 块:\n";lru(3);cout << endl;cout << "内存容量为 4 块:\n";lru(4);return 0;
}

LRU，用堆栈实现

两个算法综合在一起看运行速率

#include <iostream>
#include <ctime>
#include <cstring>
#include <unordered_map>
#include <chrono> // 引入chrono库using namespace std;
using namespace std::chrono; // 使用chrono命名空间const int N = 1010;
int table[5][20]; // 最终输出的表格状态
unordered_map<int, int> m; // 键为page号，值为count值
int pages[20] = { 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1 };
int memory[N];//每次查找页面进行记录的滑动窗口// FIFO算法
void fifo(int n) {memset(memory, 0x3f, sizeof memory);memset(table, -1, sizeof table);bool status[20];  // 记录是否缺页int pageFaults = 0;       // 缺页次数int hh = 0, tt = -1;      // 队首和队尾指针//clock_t start = clock(); // 获取开始时间// 获取开始时间auto start = high_resolution_clock::now();for (int j = 0; j < 20; j++) {int page = pages[j];bool found = false;// 检查页面是否已在内存中for (int i = hh; i <= tt; i++) {if (memory[i] == page) {found = true;break;}}if (!found) {  // 缺页情况memory[++tt] = page; // 新页面加入队尾// 控制滑动窗口大小为 nif (tt - hh + 1 > n) {hh++; // 超过容量，队首出队}status[j] = false;  // 标记缺页pageFaults++;}else {status[j] = true;   // 标记命中}// 记录当前内存状态到表格for (int i = 0; i < n; i++) {//如果只写memory[hh]的话不就移动队首指针了吗，不可以，现在是赋值阶段，只需要控制负责赋值的滑动指针首先不能超过队尾指针，确保在滑动窗口范围内，//因为有可能这个滑动窗口不足n长，你就会多余赋值本来不能存在的页面号赋值成0x3f，其次需要满足当前检查是否缺页的一次记录memory，该位置是否有值if (i + hh <= tt && memory[i + hh] != 0x3f) {table[i][j] = memory[i + hh];}else {table[i][j] = -1; // 空位显示为 -1}}}//clock_t end = clock(); // 获取结束时间// 获取结束时间auto stop = high_resolution_clock::now();auto duration = duration_cast<microseconds>(stop - start);// 输出结果表格cout << "主存块号 ";for (int j = 0; j < 20; j++) {cout << pages[j] << " ";}cout << endl;for (int i = 0; i < n; i++) {cout << "   " << i << "     ";for (int j = 0; j < 20; j++) {if (table[i][j] == -1) {cout << "  ";  // 空块显示为空格}else {cout << table[i][j] << " ";}}cout << endl;}// 输出缺页标记cout << "是否缺页 ";for (int j = 0; j < 20; j++) {cout << (status[j] ? "\u221A " : "\u00D7 ");//unicode编码，前者代表true则不缺页是√标识，后者代表false是缺页×表示}cout << endl;cout << "FIFO 缺页率: " << (float)pageFaults / 20 * 100 << "%" << endl;//cout << "运行时间: " << (double)(end - start) / CLOCKS_PER_SEC << " 秒" << endl;cout << "运行时间: " << duration.count() << " 微秒" << endl; // 输出运行时间}
void lru(int n) {memset(table, -1, sizeof table);m.clear();bool status[20]; // 记录是否缺页int pageFaults = 0; // 缺页次数//clock_t start = clock(); // 获取开始时间// 获取开始时间auto start = high_resolution_clock::now();for (int j = 0; j < 20; j++) {int page = pages[j];if (!m.count(page)) { // 没命中就要加入或者替换页面if (m.size() >= n) {// 找到count最大的页面进行替换int maxpage = -1, maxcounts = -1;for (auto p : m) {if (p.second > maxcounts) {maxpage = p.first;maxcounts = p.second;}}m.erase(maxpage);}m[page] = 0;//没命中且主存没满则直接加入页面pageFaults++;status[j] = false; // 标记缺页}else {status[j] = true; // 标记命中m[page] = 0;}// 更新所有页面的count值：命中则置0，没命中加入新页面——满足条件则不加1即可，不管加不加入新页面，其他没中的页面都是要count+1的for (auto& p : m) {if (p.first != page) {p.second += 1;}}// 更新当前主存块内存在的页面int i = 0;for (auto p : m) {if (i < n) {//用一个i去便利贮存块，而不用fortable[i][j] = p.first;i++;}}//一开始写错了：/*for (int i = 0; i < n; i++) {for (auto p : m) {table[i][j] = p.first;}}*/}//clock_t end = clock(); // 获取结束时间// 获取结束时间auto stop = high_resolution_clock::now();auto duration = duration_cast<microseconds>(stop - start);// 输出结果表格cout << "主存块号 ";for (int j = 0; j < 20; j++) {cout << pages[j] << " ";}cout << endl;for (int i = 0; i < n; i++) {cout << "   " << i << "     ";for (int j = 0; j < 20; j++) {if (table[i][j] == -1) {cout << "  "; // 空块显示为空格}else {cout << table[i][j] << " ";}}cout << endl;}// 输出缺页标记cout << "是否缺页 ";for (int j = 0; j < 20; j++) {cout << (status[j] ? "\u221A " : "\u00D7 ");}cout << endl;cout << "LRU 缺页率: " << (float)(pageFaults) / 20 * 100 << "%" << endl;//cout << "运行时间: " << (double)(end - start) / CLOCKS_PER_SEC << " 秒" << endl;cout << "运行时间: " << duration.count() << " 微秒" << endl; // 输出运行时间
}int main() {cout << "内存容量为 3 块:\n";fifo(3);cout << endl;lru(3);cout << endl;cout << "内存容量为 4 块:\n";fifo(4);cout << endl;lru(4);return 0;
}

1）主存块数越多的，不论哪个算法，运行时间都更长一些，用的时chrono精确时间微妙

但是同样的，运行每次的时间不定

2）主存块数越多的，不论哪个算法，缺页率都更低一些