wordpress去掉链接中的m,seo关键词排名软件流量词,曲阳网站建设在哪,电商发展现状与趋势#x1f493;博主csdn个人主页#xff1a;小小unicorn ⏩专栏分类#xff1a;linux #x1f69a;代码仓库#xff1a;小小unicorn的代码仓库#x1f69a; #x1f339;#x1f339;#x1f339;关注我带你学习编程知识 目录 必做题代码分析#xff08;重点以时间统计… 博主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 chronousing 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_castchrono::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_castchrono::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_castchrono::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_castchrono::microseconds(end - start).count();在这一行中执行了以下操作
end - start 计算了两个时间点之间的时间差这个结果是一个持续时间对象duration。chrono::duration_castchrono::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 011 / 100 0104 / 100 1170 / 100 173 / 100 0309 / 100 3185 / 100 1245 / 100 2246 / 100 2434 / 100 4458 / 100 4364 / 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_mapusing namespace std;class PageReplacement
{
public:PageReplacement(int m, const vectorint pages): m(m), pages(pages), missed(0), n(pages.size()) {}virtual void run() 0;int getMissedCount() const { return missed; }protected:int m; // 可用页面数vectorint pages; // 页面访问序列int missed; // 缺页次数int n; // 页面序列长度
};class FIFO : public PageReplacement
{
public:FIFO(int m, const vectorint pages) : PageReplacement(m, pages) { run(); }void run() override {vectorint 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 vectorint pages) : PageReplacement(m, pages) { run(); }void run() override {vectorint frame(m, -1);unordered_mapint, 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 vectorint pages) : PageReplacement(m, pages) { run(); }void run() override {vectorint 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()
{// 页面访问序列vectorint accessSequence { 10, 11, 104, 170, 73, 309, 185, 245, 246, 434, 458, 364 };vectorint 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_castchrono::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_castchrono::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_castchrono::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 可能会有所不同具体取决于页面访问序列。
