![页面置换算法——C/C++实现 [ OTP, FIFO, LRU, LFU + 开源代码 + 详细解析]](http://www.mshxw.com/aiimages/31/675599.png "页面置换算法——C/C++实现 [ OTP, FIFO, LRU, LFU + 开源代码 + 详细解析]")
⌛️
文章目录
- 零、运行结果图
- 一、最佳置换算法（OPT）
- 二、先进先出算法（FIFO）
- 三、最近最久未使用算法（LRU）
- 四、最不经常使用算法（LFU）
- 五、完整代码 —— C语言版本
- 六、完整代码 —— C++版本
- 七、参考附录
Page Replacement Algorithm ⌨️
零、运行结果图
◆ 对上图说明：后面分别用四种算法，对该样例都进行了检验，结果一致。
● 后文代码的常见变量：
[1] n：物理页框数。
[2] len：地址走向的长度。
[3] save_frame：含有n个格子的物理页框（即一个长度为n的动态数组，指针申请的）。
[4] interview_Array：长度为len的地址数组（即一个长度为len的动态数组，指针申请的）。
一、最佳置换算法（OPT）
● 替换规则：将以后永不使用的或在最长时间内不再被访问的页面进行替换。
● 这是一种理想化的算法，有点 “先知” 算法的味道，故在实际上是难以实现的。但它可作为衡量各种实用的页面置换算法的标准。
● 样例：假设采用固定分配策略，为进程分配 3 个存储页框，进程运行时形成的访问地址走向为 2，3，2，1，5，2，4，5，3，2，5 和 2。则 OPT 算法运行结果如下。
◆ 说明：
① 第一个红箭头：因为后面需访问地址里面没有 “1”，所以用 “5” 置换 “1”。
② 第二个红箭头：因为后面需访问的地址里面，“2” 是最长时间内不被访问的，所以置换它。
③ 当进程运行完毕时，系统进行了 3 次置换，缺页中断次数为 6 次，即蓝色箭头加上红色箭头的个数。缺页率为 6/12 = 50% 。
● 算法设计：
[1] 依次读取每一个页面地址addr，然后看当前页框是否装满。如果未装满则执行[2]，否则执行[3]。
[2] 执行Find_Exist()函数，看页框中是否已存在当前地址。如果存在则 “命中”，然后返回执行步骤[1]，否则执行[4](即未命中的情况)。
[3] 执行Find_Exist()函数，看页框中是否已存在当前地址。如果存在则 “命中”，然后返回执行步骤[1]，否则执行[5](即未命中的情况)。
[4] 把当前地址addr装入空闲的物理页框，然后返回执行步骤[1]。
[5] 执行Find_LeastInteviewTime()函数，找出需要替换的页面地址(在物理页框中的)，并进行替换，然后返回执行步骤[1]。
● 核心代码：【注：Init()函数、Find_Exist()等函数在后文的完整代码中】
int Find_LeastInteviewTime(int sta, int addr, int* interview_Array, int len)
{
for (int i = sta; i < len; i++)
{
if (interview_Array[i] == addr)
return i - sta;
}
return 99999;
}
void OPT_Agorithm()
{
printf("欢迎使用 OPT n");
int n = 0, len = 0, * save_frame = NULL, * interview_Array = NULL;
Init(&n, &len);
save_frame = (int*)malloc(n * sizeof(int));
for (int i = 0; i < n; i++)
save_frame[i] = -999;
printf("请输入地址走向:");
interview_Array = (int*)malloc(len * sizeof(int));
for (int i = 0; i < len; i++)
scanf_s("%d", &interview_Array[i]);
int addr; // 地址
int cnt = 0; // 物理页框已装满的份数(大于 n 时无效)
int score = 0; // 成功的访问次数
int fail_time = 0; // 不成功的访问次数
int iter = 0; // 迭代次数
while (iter < len)
{
printf("n第%d轮：", iter);
addr = interview_Array[iter]; // 读取地址
iter++;
...
if (cnt < n)
{
if (Find_Exist(save_frame, cnt, addr) != -1)
{
score++;
...
}
else // 未命中，但有空间
{
fail_time++;
...
save_frame[cnt] = addr;
...
cnt++;
}
}
else
{
if (Find_Exist(save_frame, n, addr) != -1)
{
score++;
...
}
else // 未命中，但没了空间
{
fail_time++;
int* least_Time = (int*)malloc(n * sizeof(int));
int max_Time = 0;
int index;
for (int i = 0; i < n; i++)
{
least_Time[i] = Find_LeastInteviewTime(iter, save_frame[i], interview_Array, len);
if (least_Time[i] > max_Time)
{
max_Time = least_Time[i];
index = i;
}
}
...
save_frame[index] = addr;
...
}
}
}
...
}
● 运行结果：
二、先进先出算法（FIFO）
● 替换规则：淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以替换。
● 依旧沿用上面的样例来图形化说明：假设采用固定分配策略，为进程分配 3 个存储页框，进程运行时形成的访问地址走向为 2，3，2，1，5，2，4，5，3，2，5 和 2。则 OPT 算法运行结果如下。
◆ 说明：
① 第一个红箭头：因为 “2” 最先进来，所以用 “5” 置换 “2”。
② 当进程运行完毕时，系统进行了 6 次置换，缺页中断次数为 9 次，即蓝色箭头加上红色箭头的个数。缺页率为 9 /12 = 75% 。
● 算法设计：【in_HereTime[]：记录每个页面驻留的时间】
[1] 依次读取每一个页面地址addr，然后看当前页框是否装满。如果未装满则执行[2]，否则执行[3]。
[2] 执行Find_Exist()函数，看页框中是否已存在当前地址。如果存在则 “命中”，然后执行Update_InHereTime()函数来更新in_HereTime[]数组，然后返回执行步骤[1]，否则执行[4](即未命中的情况)。
[3] 执行Find_Exist()函数，看页框中是否已存在当前地址。如果存在则 “命中”，然后执行Update_InHereTime()函数来更新in_HereTime[]数组，然后返回执行步骤[1]，否则执行[5](即未命中的情况)。
[4] 把当前地址addr装入空闲的物理页框，然后执行Update_InHereTime()函数来更新in_HereTime数组，然后返回执行步骤[1]。
[5] 从in_HereTime[]找出最大值对应的那个页面地址(在物理页框中的)，并进行替换，然后返回执行步骤[1]。
● 核心代码：【注：Init()函数、Find_Exist()函数等函数在后文的完整代码中】
void Update_InHereTime(int* in_HereTime, int n, int ind)
{
for (int i = 0; i < n; i++)
in_HereTime[i]++;
if (ind != -1)
in_HereTime[ind] = 0;
}
void FIFO_Agorithm()
{
int n, len, * save_frame = NULL, * interview_Array = NULL;
Init(&n, &len);
save_frame = (int*)malloc(n * sizeof(int));
for (int i = 0; i < n; i++)
save_frame[i] = -999;
printf("请输入地址走向:");
interview_Array = (int*)malloc(len * sizeof(int));
for (int i = 0; i < len; i++)
scanf_s("%d", &interview_Array[i]);
int* in_HereTime = (int*)malloc(n * sizeof(int));
for (int i = 0; i < n; i++)
in_HereTime[i] = 0; // 初始化都为零
int addr;
int cnt = 0;
int score = 0;
int fail_time = 0;
int iter = 0;
while (iter < len)
{
printf("n第%d轮：", iter);
addr = interview_Array[iter];
iter++;
if (cnt < n)
{
if (Find_Exist(save_frame, cnt, addr) != -1)
{
score++;
...
Update_InHereTime(in_HereTime, cnt, -1);
}
else // 未命中，但有空间
{
fail_time++;
...
save_frame[cnt] = addr;
...
Update_InHereTime(in_HereTime, cnt, cnt);
cnt++;
}
}
else
{
if (Find_Exist(save_frame, n, addr) != -1)
{
score++;
...
Update_InHereTime(in_HereTime, n, -1);
}
else // 未命中，但没了空间
{
fail_time++;
int max_Time = 0;
int index;
for (int i = 0; i < n; i++)
{
if (in_HereTime[i] > max_Time)
{
max_Time = in_HereTime[i];
index = i;
}
}
...
save_frame[index] = addr;
...
int ind = Find_Exist(save_frame, n, addr);
Update_InHereTime(in_HereTime, n, ind);
}
}
}
...
}
● 测试结果：
三、最近最久未使用算法（LRU）
● 替换规则：替换最近一段时间内最久未被使用的页面。
● 依旧沿用上面的样例来图形化说明：假设采用固定分配策略，为进程分配 3 个存储页框，进程运行时形成的访问地址走向为 2，3，2，1，5，2，4，5，3，2，5 和 2。则 OPT 算法运行结果如下。
◆ 说明：
① 第一个红箭头：因为 “2” 最近被访问过，“1”刚刚才被调入，只有 “3” 最近最久未被访问，所以置换它。
② 当进程运行完毕时，系统进行了 4 次置换，缺页中断次数为 7 次，即蓝色箭头加上红色箭头的个数。缺页率为 7 /12 = 58.33% 。
● 算法设计：
[1] 依次读取每一个页面地址addr，然后看当前页框是否装满。如果未装满则执行[2]，否则执行[3]。
[2] 执行Find_Exist()函数，看页框中是否已存在当前地址。如果存在则 “命中”，然后返回执行步骤[1]，否则(即未命中)执行[4]。
[3] 执行Find_Exist()函数，看页框中是否已存在当前地址。如果存在则 “命中”，然后返回执行步骤[1]，否则(即未命中)执行[5]。
[4] 把当前地址addr装入空闲的物理页框，然后返回执行步骤[1]。
[5] 执行Find_LeastNotUseTime()函数，找出需要替换的页面地址(在物理页框中的)，并进行替换，然后返回执行步骤[1]。
● 核心代码：【注：Init()函数、Find_Exist()函数等函数在后文的完整代码中】
int Find_LeastNotUseTime(int end, int addr, int* interview_Array)
{
for (int i = end - 1; i >= 0; i--)
{
if (interview_Array[i] == addr)
return end - i;
}
return 99999;
}
void LRU_Agorithm()
{
int n, len, * save_frame = NULL, * interview_Array = NULL;
Init(&n, &len);
save_frame = (int*)malloc(n * sizeof(int));
for (int i = 0; i < n; i++)
save_frame[i] = -999;
printf("请输入地址走向:");
interview_Array = (int*)malloc(len * sizeof(int));
for (int i = 0; i < len; i++)
scanf_s("%d", &interview_Array[i]);
int addr;
int cnt = 0;
int score = 0;
int fail_time = 0;
int iter = 0;
while (iter < len)
{
addr = interview_Array[iter];
iter++;
...
if (cnt < n)
{
if (Find_Exist(save_frame, cnt, addr) != -1)
{
score++;
...
}
else // 未命中，但有空间
{
fail_time++;
...
save_frame[cnt] = addr;
...
cnt++;
}
}
else
{
if (Find_Exist(save_frame, n, addr) != -1)
{
score++;
...
}
else // 未命中，但没了空间
{
fail_time++;
int* Not_UseTime = (int*)malloc(n * sizeof(int));
int max_Time = 0;
int index;
for (int i = 0; i < n; i++)
{
Not_UseTime[i] = Find_LeastNotUseTime(iter, save_frame[i], interview_Array);
if (Not_UseTime[i] > max_Time)
{
max_Time = Not_UseTime[i];
index = i;
}
}
...
save_frame[index] = addr;
...
}
}
}
...
}
● 测试结果：
四、最不经常使用算法（LFU）
● 替换规则：把当前为止，访问次数最少的页面予以替换。
● 和上面的样例有一点不同(地址走向不同)：假设采用固定分配策略，为进程分配 3 个存储页框，进程运行时形成的访问地址走向为 2，3，2，1，2，1，5，4，2，4，4 和 6。则 LFU 算法运行结果如下。
◆ 说明：
① 第一个红箭头：因为 “3” 被访问（即被命中）的次数为 0，而其他两个页面( “2” 和 “1” 都分别有 2、1 次命中)，所以“3” 的访问次数最少，所以置换它。
② 当进程运行完毕时，系统进行了 3 次置换，缺页中断次数为 6 次（即蓝色箭头加上红色箭头的个数）。缺页率为 6 /12 = 50% 。
● 算法设计：【interview_Time[]：记录每个页面被访问的次数】
[1] 依次读取每一个页面地址addr，然后看当前页框是否装满。如果未装满则执行[2]，否则执行[3]。
[2] 执行Find_Exist()函数，看页框中是否已存在当前地址。如果存在则 “命中”，并且使对应的interview_Time加1，然后返回执行步骤[1]，否则(即未命中)执行[4]。
[3] 执行Find_Exist()函数，看页框中是否已存在当前地址。如果存在则 “命中”，并且使对应的interview_Time加1，然后返回执行步骤[1]，否则(即未命中)执行[5]。
[4] 把当前地址addr装入空闲的物理页框，然后返回执行步骤[1]。
[5] 执行Find_LeastNotInterviewTime()函数，找出需要替换的页面地址(在物理页框中的)进行替换，并使对应的的interview_Time重新赋值为0，然后返回执行步骤[1]。
● 核心代码：【注：Init()函数、Find_Exist()函数等函数在后文的完整代码中】
int Find_LeastNotInterviewTime(int n, int* interview_Time)
{
int min_Time = 99999;
int ind;
for (int i = 0; i < n; i++)
{
if (interview_Time[i] < min_Time)
{
min_Time = interview_Time[i];
ind = i;
}
}
return ind;
}
void LFU_Agorithm()
{
int n, len, * save_frame = NULL, * interview_Array = NULL;
Init(&n, &len);
save_frame = (int*)malloc(n * sizeof(int));
for (int i = 0; i < n; i++)
save_frame[i] = -999;
printf("请输入地址走向:");
interview_Array = (int*)malloc(len * sizeof(int));
for (int i = 0; i < len; i++)
scanf_s("%d", &interview_Array[i]);
int* interview_Time = (int*)malloc(n * sizeof(int));
for (int i = 0; i < n; i++)
interview_Time[i] = 0;
int addr;
int cnt = 0;
int score = 0;
int fail_time = 0;
int iter = 0;
while (iter < len)
{
printf("n第%d轮：", iter);
addr = interview_Array[iter];
iter++;
if (cnt < n)
{
if (Find_Exist(save_frame, cnt, addr) != -1)
{
score++;
...
int ind = Find_Exist(save_frame, cnt, addr);
interview_Time[ind]++;
}
else // 未命中，但有空间
{
fail_time++;
...
save_frame[cnt] = addr;
...
cnt++;
}
}
else
{
if (Find_Exist(save_frame, n, addr) != -1)
{
score++;
...
int ind = Find_Exist(save_frame, n, addr);
interview_Time[ind]++;
}
else // 未命中，但没了空间
{
fail_time++;
int index = Find_LeastNotInterviewTime(n, interview_Time);
...
save_frame[index] = addr;
...
}
}
}
...
}
● 测试结果：
五、完整代码 —— C语言版本
● 补充说明：完整代码中，还包含 “输出内存驻留的页面集合”【Print_frame()函数】 、“缺页次数” 和 “缺页率” 等功能【Page_Loss_Rate()函数】。
#include#include void OPT_Agorithm(); void FIFO_Agorithm(); void LRU_Agorithm(); void LFU_Agorithm(); double Page_Loss_Rate(int, int); int Find_Exist(int*, int, int); int Find_LeastInteviewTime(int, int, int*, int); void Update_InHereTime(int*, int, int); int Find_LeastNotUseTime(int, int, int*); int Find_LeastNotInterviewTime(int, int*); void Print_frame(int*, int); void Print_Menu(); void Init(int*, int*); int main() { int choice; do { Print_Menu(); printf("请选择要实现的算法："); scanf_s("%d", &choice); switch (choice) { case 1: OPT_Agorithm(); break; case 2: FIFO_Agorithm(); break; case 3: LRU_Agorithm(); break; case 4: LFU_Agorithm(); break; case 0: break; } system("pause"); system("cls"); } while (choice); return 0; } int Find_Exist(int* save_frame, int n, int addr) { for (int i = 0; i < n; i++) { if (save_frame[i] == addr) { return i; } } return -1; } void Print_Menu() { printf("+---------------------------------------+n"); printf("|t***算法清单***ttt|n"); printf("|t1.最佳置换算法(OPT)tt|n|t2.先进先出算法(FIFO)tt|n"); printf("|t3.最近最久未使用算法(LRU)t|n|t4.最不经常使用算法(LFU)tt|n"); printf("|t0.退出tttt|n"); printf("+---------------------------------------+n"); } void Print_frame(int* save_frame, int n) { printf("t"); for (int i = 0; i < n; i++) { if (i == 0) { if (save_frame[i] == -999) printf("/ /"); else printf("/%d/", save_frame[i]); } else { if (save_frame[i] == -999) printf(" /"); else printf("%d/", save_frame[i]); } } printf("n"); } void Init(int* n, int* len) { printf("请输入 n :"); scanf_s("%d", n); printf("请输入地址走向的长度："); scanf_s("%d", len); } double Page_Loss_Rate(int S, int F) { double ans = 1.0 * F / (1.0 * S + 1.0 * F) * 100; return ans; } int Find_LeastInteviewTime(int sta, int addr, int* interview_Array, int len) { for (int i = sta; i < len; i++) { if (interview_Array[i] == addr) { return i - sta; } } return 99999; } void OPT_Agorithm() { printf("欢迎使用 OPT n"); int n = 0, len = 0, * save_frame = NULL, * interview_Array = NULL; Init(&n, &len); save_frame = (int*)malloc(n * sizeof(int)); for (int i = 0; i < n; i++) save_frame[i] = -999; printf("请输入地址走向:"); interview_Array = (int*)malloc(len * sizeof(int)); for (int i = 0; i < len; i++) scanf_s("%d", &interview_Array[i]); printf("n"); //测试样例： 1 3 12 2 3 2 1 5 2 4 5 3 2 5 2 int addr; int cnt = 0; int score = 0; int fail_time = 0; int iter = 0; while (iter < len) { addr = interview_Array[iter]; iter++; printf("n第%d轮：", iter); if (cnt < n) { if (Find_Exist(save_frame, cnt, addr) != -1) { score++; printf(""%d" 被命中了tt------->", addr); Print_frame(save_frame, n); } else // 未命中，但有空间 { fail_time++; printf("未命中，"%d" 被装入 t------->", addr); save_frame[cnt] = addr; Print_frame(save_frame, n); cnt++; } } else { if (Find_Exist(save_frame, n, addr) != -1) { score++; printf(""%d" 被命中了tt------->", addr); Print_frame(save_frame, n); } else // 未命中，但没了空间 { fail_time++; int* least_Time = (int*)malloc(n * sizeof(int)); int max_Time = 0; int index; for (int i = 0; i < n; i++) { least_Time[i] = Find_LeastInteviewTime(iter, save_frame[i], interview_Array, len); if (least_Time[i] > max_Time) { max_Time = least_Time[i]; index = i; } } printf(""%d" 替换了 "%d"tt------->", addr, save_frame[index]); save_frame[index] = addr; Print_frame(save_frame, n); free(least_Time); } } // printf("n"); } printf("n"); printf("缺页次数为：%dn", fail_time); printf("缺页中断率 R = %.2f%%n", Page_Loss_Rate(score, fail_time)); free(save_frame); free(interview_Array); } void Update_InHereTime(int* in_HereTime, int n, int ind) { for (int i = 0; i < n; i++) in_HereTime[i]++; if (ind != -1) in_HereTime[ind] = 0; } void FIFO_Agorithm() { int n, len, * save_frame = NULL, * interview_Array = NULL; Init(&n, &len); save_frame = (int*)malloc(n * sizeof(int)); for (int i = 0; i < n; i++) save_frame[i] = -999; printf("请输入地址走向:"); interview_Array = (int*)malloc(len * sizeof(int)); for (int i = 0; i < len; i++) scanf_s("%d", &interview_Array[i]); printf("n"); int* in_HereTime = (int*)malloc(n * sizeof(int)); for (int i = 0; i < n; i++) in_HereTime[i] = 0; // 初始化都为零 //测试样例： 2 3 12 2 3 2 1 5 2 4 5 3 2 5 2 int addr; int cnt = 0; int score = 0; int fail_time = 0; int iter = 0; while (iter < len) { printf("n第%d轮：", iter); addr = interview_Array[iter]; iter++; if (cnt < n) { if (Find_Exist(save_frame, cnt, addr) != -1) { score++; printf(""%d" 被命中了tt------->", addr); Print_frame(save_frame, n); Update_InHereTime(in_HereTime, cnt, -1); } else // 未命中，但有空间 { fail_time++; printf("未命中，"%d" 被装入 t------->", addr); save_frame[cnt] = addr; Print_frame(save_frame, n); Update_InHereTime(in_HereTime, cnt, cnt); cnt++; } } else { if (Find_Exist(save_frame, n, addr) != -1) { score++; printf(""%d" 被命中了tt------->", addr); Print_frame(save_frame, n); Update_InHereTime(in_HereTime, n, -1); } else // 未命中，但没了空间 { fail_time++; int max_Time = 0; int index; for (int i = 0; i < n; i++) { if (in_HereTime[i] > max_Time) { max_Time = in_HereTime[i]; index = i; } } printf(""%d" 替换了 "%d"tt------->", addr, save_frame[index]); save_frame[index] = addr; Print_frame(save_frame, n); int ind = Find_Exist(save_frame, n, addr); Update_InHereTime(in_HereTime, n, ind); } } } printf("n"); printf("缺页次数为：%dn", fail_time); printf("缺页中断率 R = %.2f%%n", Page_Loss_Rate(score, fail_time)); free(save_frame); free(interview_Array); free(in_HereTime); return; } int Find_LeastNotUseTime(int end, int addr, int* interview_Array) { for (int i = end - 1; i >= 0; i--) { if (interview_Array[i] == addr) { return end - i; } } return 99999; } void LRU_Agorithm() { int n, len, * save_frame = NULL, * interview_Array = NULL; Init(&n, &len); save_frame = (int*)malloc(n * sizeof(int)); for (int i = 0; i < n; i++) save_frame[i] = -999; printf("请输入地址走向:"); interview_Array = (int*)malloc(len * sizeof(int)); for (int i = 0; i < len; i++) scanf_s("%d", &interview_Array[i]); printf("n"); //测试样例： 3 3 12 2 3 2 1 5 2 4 5 3 2 5 2 int addr; int cnt = 0; int score = 0; int fail_time = 0; int iter = 0; while (iter < len) { addr = interview_Array[iter]; iter++; printf("n第%d轮：", iter); if (cnt < n) { if (Find_Exist(save_frame, cnt, addr) != -1) { score++; printf(""%d" 被命中了tt------->", addr); Print_frame(save_frame, n); } else // 未命中，但有空间 { fail_time++; printf("未命中，"%d " 被装入 t------->", addr); save_frame[cnt] = addr; Print_frame(save_frame, n); cnt++; } } else { if (Find_Exist(save_frame, n, addr) != -1) { score++; printf(""%d" 被命中了tt------->", addr); Print_frame(save_frame, n); } else // 未命中，但没了空间 { fail_time++; int* Not_UseTime = (int*)malloc(n * sizeof(int)); int max_Time = 0; int index; for (int i = 0; i < n; i++) { Not_UseTime[i] = Find_LeastNotUseTime(iter, save_frame[i], interview_Array); if (Not_UseTime[i] > max_Time) { max_Time = Not_UseTime[i]; index = i; } } printf(""%d" 替换了 "%d"tt------->", addr, save_frame[index]); save_frame[index] = addr; Print_frame(save_frame, n); free(Not_UseTime); } } } printf("n"); printf("缺页次数为：%dn", fail_time); printf("缺页中断率 R = %.2f%%n", Page_Loss_Rate(score, fail_time)); free(save_frame); free(interview_Array); } int Find_LeastNotInterviewTime(int n, int* interview_Time) { int min_Time = 99999; int ind; for (int i = 0; i < n; i++) { if (interview_Time[i] < min_Time) { min_Time = interview_Time[i]; ind = i; } } return ind; } void LFU_Agorithm() { int n, len, * save_frame = NULL, * interview_Array = NULL; Init(&n, &len); save_frame = (int*)malloc(n * sizeof(int)); for (int i = 0; i < n; i++) save_frame[i] = -999; printf("请输入地址走向:"); interview_Array = (int*)malloc(len * sizeof(int)); for (int i = 0; i < len; i++) scanf_s("%d", &interview_Array[i]); printf("n"); int* interview_Time = (int*)malloc(n * sizeof(int)); for (int i = 0; i < n; i++) interview_Time[i] = 0; // 测试样例一：4 3 12 2 3 2 1 5 2 4 5 3 2 5 2 // 测试样例二：4 3 12 2 3 2 1 2 1 5 4 2 4 4 6 int addr; int cnt = 0; int score = 0; int fail_time = 0; int iter = 0; while (iter < len) { printf("n第%d轮：", iter); addr = interview_Array[iter]; iter++; if (cnt < n) { if (Find_Exist(save_frame, cnt, addr) != -1) { score++; printf(""%d" 被命中了tt------->", addr); Print_frame(save_frame, n); int ind = Find_Exist(save_frame, cnt, addr); interview_Time[ind]++; } else // 未命中，但有空间 { fail_time++; printf("未命中，"%d" 被装入 t------->", addr); save_frame[cnt] = addr; Print_frame(save_frame, n); cnt++; } } else { if (Find_Exist(save_frame, n, addr) != -1) { score++; printf(""%d" 被命中了tt------->", addr); Print_frame(save_frame, n); int ind = Find_Exist(save_frame, n, addr); interview_Time[ind]++; } else // 未命中，但没了空间 { fail_time++; int index = Find_LeastNotInterviewTime(n, interview_Time); printf(""%d" 替换了 "%d"tt------->", addr, save_frame[index]); save_frame[index] = addr; interview_Time[index] = 0; Print_frame(save_frame, n); } } } printf("n"); printf("缺页次数为：%dn", fail_time); printf("缺页中断率 R = %.2f%%n", Page_Loss_Rate(score, fail_time)); free(save_frame); free(interview_Array); free(interview_Time); }
六、完整代码 —— C++版本
● 补充说明：完整代码中，还包含 “输出内存驻留的页面集合”【Print_frame()函数】 、“缺页次数” 和 “缺页率” 等功能【Page_Loss_Rate()函数】。
#include#include using namespace std; void OPT_Agorithm(); void FIFO_Agorithm(); void LRU_Agorithm(); void LFU_Agorithm(); double Page_Loss_Rate(int, int); int Find_Exist(int*, int, int); int Find_LeastInteviewTime(int, int, int*, int); void Update_InHereTime(int*, int, int); int Find_LeastNotUseTime(int, int, int*); int Find_LeastNotInterviewTime(int, int*); void Print_frame(int*, int); void Print_Menu(); int main() { int choice; do { Print_Menu(); cout << "请选择要实现的算法："; cin >> choice; switch (choice) { case 1: OPT_Agorithm(); break; case 2: FIFO_Agorithm(); break; case 3: LRU_Agorithm(); break; case 4: LFU_Agorithm(); break; case 0: break; } system("pause"); system("cls"); } while (choice); return 0; } int Find_Exist(int* save_frame, int n, int addr) { for (int i = 0; i < n; i++) { if (save_frame[i] == addr) { return i; } } return -1; } void Print_Menu() { cout << "+---------------------------------------+" << endl; cout << "|t***算法清单***ttt|" << endl; cout << "|t1.最佳置换算法(OPT)tt|" << endl << "|t2.先进先出算法(FIFO)tt|" << endl; cout << "|t3.最近最久未使用算法(LRU)t|" << endl << "|t4.最不经常使用算法(LFU)tt|" << endl; cout << "|t0.退出tttt|" << endl; cout << "+---------------------------------------+" << endl; } void Print_frame(int* save_frame, int n) { cout << "t"; for (int i = 0; i < n; i++) { if (i == 0) { if (save_frame[i] == -999) cout << "/ /"; else cout << "/" << save_frame[i] << "/"; } else { if (save_frame[i] == -999) cout << " /"; else cout << save_frame[i] << "/"; } } cout << endl; } void Init(int* n, int* len, int*& save_frame, int*& interview_Array) { cout << "请输入 n :"; cin >> *n; save_frame = new int[*n]; for (int i = 0; i < *n; i++) save_frame[i] = -999; cout << "请输入地址走向的长度："; cin >> *len; cout << "请输入地址走向:"; interview_Array = new int[*len]; for (int i = 0; i < *len; i++) cin >> interview_Array[i]; } double Page_Loss_Rate(int S, int F) { double ans = 1.0 * F / (1.0 * S + 1.0 * F) * 100; return ans; } int Find_LeastInteviewTime(int sta, int addr, int* interview_Array, int len) { for (int i = sta; i < len; i++) { if (interview_Array[i] == addr) { return i - sta; } } return 99999; } void OPT_Agorithm() { cout << "欢迎使用 OPT " << endl; int n, len, * save_frame = NULL, * interview_Array = NULL; Init(&n, &len, save_frame, interview_Array); //测试样例： 1 3 12 2 3 2 1 5 2 4 5 3 2 5 2 int addr; int cnt = 0; int score = 0; int fail_time = 0; int iter = 0; while (iter < len) { addr = interview_Array[iter]; iter++; cout << endl << "第" << iter << "轮："; if (cnt < n) { if (Find_Exist(save_frame, cnt, addr) != -1) { score++; cout << """ << addr << "" 被命中了tt------->"; Print_frame(save_frame, n); } else // 未命中，但有空间，" << "" << addr << "" 被装入 { fail_time++; cout << "未命中，" << """ << addr << "" 被装入 t------->"; save_frame[cnt] = addr; Print_frame(save_frame, n); cnt++; } } else { if (Find_Exist(save_frame, n, addr) != -1) { score++; cout << """ << addr << "" 被命中了tt------->"; Print_frame(save_frame, n); } else // 未命中，但没了空间 { fail_time++; int* least_Time = new int[n]; int max_Time = 0; int index; for (int i = 0; i < n; i++) { least_Time[i] = Find_LeastInteviewTime(iter, save_frame[i], interview_Array, len); if (least_Time[i] > max_Time) { max_Time = least_Time[i]; index = i; } } cout << """ << addr << "" 替换了 "" << save_frame[index] << ""tt------->"; save_frame[index] = addr; Print_frame(save_frame, n); delete[] least_Time; } } } cout << endl; cout << "缺页次数为：" << fail_time << endl; cout << "缺页中断率 R = " << Page_Loss_Rate(score, fail_time) << "%" << endl; delete[] save_frame; delete[] interview_Array; } void Update_InHereTime(int* in_HereTime, int n, int ind) { for (int i = 0; i < n; i++) { in_HereTime[i]++; } if (ind != -1) in_HereTime[ind] = 0; } void FIFO_Agorithm() { int n, len, * save_frame = NULL, * interview_Array = NULL; Init(&n, &len, save_frame, interview_Array); int* in_HereTime = new int[n]; for (int i = 0; i < n; i++) in_HereTime[i] = 0; // 初始化都为零 //测试样例： 2 3 12 2 3 2 1 5 2 4 5 3 2 5 2 int addr; int cnt = 0; int score = 0; int fail_time = 0; int iter = 0; while (iter < len) { cout << endl << "第" << iter << "轮："; addr = interview_Array[iter]; iter++; if (cnt < n) { if (Find_Exist(save_frame, cnt, addr) != -1) { score++; cout << """ << addr << "" 被命中了tt------->"; Print_frame(save_frame, n); Update_InHereTime(in_HereTime, cnt, -1); } else // 未命中，但有空间 { fail_time++; cout << "未命中，" << """ << addr << "" 被装入 t------->"; save_frame[cnt] = addr; Print_frame(save_frame, n); Update_InHereTime(in_HereTime, cnt, cnt); cnt++; } } else { if (Find_Exist(save_frame, n, addr) != -1) { score++; cout << """ << addr << "" 被命中了tt------->"; Print_frame(save_frame, n); Update_InHereTime(in_HereTime, n, -1); } else // 未命中，但没了空间 { fail_time++; int max_Time = 0; int index; for (int i = 0; i < n; i++) { if (in_HereTime[i] > max_Time) { max_Time = in_HereTime[i]; index = i; } } cout << """ << addr << "" 替换了 "" << save_frame[index] << ""tt------->"; save_frame[index] = addr; Print_frame(save_frame, n); int ind = Find_Exist(save_frame, n, addr); Update_InHereTime(in_HereTime, n, ind); } } } cout << endl; cout << "缺页次数为：" << fail_time << endl; cout << "缺页中断率 R = " << Page_Loss_Rate(score, fail_time) << "%" << endl; delete[] save_frame; delete[] interview_Array; delete[] in_HereTime; return; } int Find_LeastNotUseTime(int end, int addr, int* interview_Array) { for (int i = end - 1; i >= 0; i--) { if (interview_Array[i] == addr) { // cout << " i = " << i << endl; return end - i; } } return 99999; } void LRU_Agorithm() { int n, len, * save_frame = NULL, * interview_Array = NULL; Init(&n, &len, save_frame, interview_Array); //测试样例： 3 3 12 2 3 2 1 5 2 4 5 3 2 5 2 int addr; int cnt = 0; int score = 0; int fail_time = 0; int iter = 0; while (iter < len) { addr = interview_Array[iter]; iter++; cout << endl << "第" << iter << "轮："; if (cnt < n) { if (Find_Exist(save_frame, cnt, addr) != -1) { score++; cout << """ << addr << "" 被命中了tt------->"; Print_frame(save_frame, n); } else // 未命中，但有空间 { fail_time++; cout << "未命中，" << """ << addr << "" 被装入 t------->"; save_frame[cnt] = addr; Print_frame(save_frame, n); cnt++; } } else { if (Find_Exist(save_frame, n, addr) != -1) { score++; cout << """ << addr << "" 被命中了tt------->"; Print_frame(save_frame, n); } else // 未命中，但没了空间 { fail_time++; int* Not_UseTime = new int[n]; int max_Time = 0; int index; for (int i = 0; i < n; i++) { Not_UseTime[i] = Find_LeastNotUseTime(iter, save_frame[i], interview_Array); if (Not_UseTime[i] > max_Time) { max_Time = Not_UseTime[i]; index = i; } } cout << """ << addr << "" 替换了 "" << save_frame[index] << ""tt------->"; save_frame[index] = addr; Print_frame(save_frame, n); delete[] Not_UseTime; } } } cout << endl; cout << "缺页次数为：" << fail_time << endl; cout << "缺页中断率 R = " << Page_Loss_Rate(score, fail_time) << "%" << endl; delete[] save_frame; delete[] interview_Array; } int Find_LeastNotInterviewTime(int n, int* interview_Time) { int min_Time = 99999; int ind; for (int i = 0; i < n; i++) { if (interview_Time[i] < min_Time) { min_Time = interview_Time[i]; ind = i; } } return ind; } void LFU_Agorithm() { int n, len, * save_frame = NULL, * interview_Array = NULL; Init(&n, &len, save_frame, interview_Array); int* interview_Time = new int[n]; for (int i = 0; i < n; i++) interview_Time[i] = 0; // 测试样例一：4 3 12 2 3 2 1 5 2 4 5 3 2 5 2 // 测试样例二：4 3 12 2 3 2 1 2 1 5 4 2 4 4 6 int addr; int cnt = 0; int score = 0; int fail_time = 0; int iter = 0; while (iter < len) { cout << endl << "第" << iter << "轮："; addr = interview_Array[iter]; iter++; if (cnt < n) { if (Find_Exist(save_frame, cnt, addr) != -1) { score++; cout << """ << addr << "" 被命中了tt------->"; Print_frame(save_frame, n); int ind = Find_Exist(save_frame, cnt, addr); interview_Time[ind]++; } else // 未命中，但有空间 { fail_time++; cout << "未命中，" << """ << addr << "" 被装入 t------->"; save_frame[cnt] = addr; Print_frame(save_frame, n); cnt++; } } else { if (Find_Exist(save_frame, n, addr) != -1) { score++; cout << """ << addr << "" 被命中了tt------->"; Print_frame(save_frame, n); int ind = Find_Exist(save_frame, n, addr); interview_Time[ind]++; } else // 未命中，但没了空间 { fail_time++; int index = Find_LeastNotInterviewTime(n, interview_Time); cout << """ << addr << "" 替换了 "" << save_frame[index] << ""tt------->"; save_frame[index] = addr; interview_Time[index] = 0; Print_frame(save_frame, n); } } } cout << endl; cout << "缺页次数为：" << fail_time << endl; cout << "缺页中断率 R = " << Page_Loss_Rate(score, fail_time) << "%" << endl; delete[] save_frame; delete[] interview_Array; delete[] interview_Time; }
七、参考附录
无。
(纯手敲，原创，可能存在未知 Bug，烦请指正…)
⭐️ ⭐️
