转载声明：文章来源https://blog.csdn.net/weixin_73963254/article/details/143881426
一、页面置换算法
通过编程模拟实现请求页式存储管理的几种常用页面置换算法，了解虚拟页式存储管理的特点，掌握请求页式存储管理中几种基本页面置换算法的基本思想和实现过程，并进行比较。
二、流程图及运行结果展示
三、数据结构设计
#define total 330
//变量定义
int a[total]; //指令流数组,a[i]表示第i条指令的地址
int appear[40]; // 出现次数,appear[i]表示在接下来的访问中第i页还需要访问的次数
int page[total]; //每条指令所属的页号,page[i]表示第i条指令所在的页号
int offset[total]; //每页装入10条指令后取模运算页号偏移值.
int total_pf; //用户进程的内存页面数.
int disaffect;//页面失效次数
int cnt; //驻留集个数
int stop[total]; //内存块stop[i]驻留集中第i个页号
int choice; //算法选择
int cho; //更改页面大小或驻留集大小选择
int n; //查询指令数
int _cnt; //驻留集剩余数量
double pro; //命中率
int store; //页面存放指令数
int visit[total]; //记录页面访问，visit[i]表示第i条指令已经访问过的次数四、算法选择
1.最佳淘汰算法（OPT）
//使用OPT算法.
void OPT() {
for (int i = 0; i < n; i++)
{
int f = find(page[i]);
if (f == -1) {
disaffect++;
if (_cnt < cnt) {
stop[_cnt] = page[i];
_cnt++;
}
else {
//找出stop中出现次数最少的下标
int t = min_appear();
stop[t] = page[i];
}
}
appear[page[i]]--;
out(i);
}
}2.先进先出算法（FIFO）
//使用FIFO算法.
void FIFO() {
for (int i = 0; i < n; i++) {
int f = find(page[i]);
if (f == -1) {
stop[_cnt] = page[i];
_cnt = (_cnt+1)%cnt;
disaffect++;
}
out(i);
}
}3.最近最久未使用算法(LRU)
//使用LRU算法
void LRU() {
_cnt = cnt - 1;
for (int i = 0; i < n; i++) {
int f = find(page[i]);
if (f == -1) {
disaffect++;
if (_cnt >= 0) {
stop[_cnt] = page[i];
_cnt--;
}
else {
update_stack(cnt);
stop[0] = page[i];
}
}
else {
update_stack(f);
}
out(i);
}
}4.最不经常使用算法(LFU)
//使用LFU算法.
void LFU() {
for (int i = 0; i < n; i++) {
int f = find(page[i]);
if (f == -1) {
disaffect++;
if (_cnt < cnt) {
stop[_cnt] = page[i];
_cnt++;
}
else {
int t = min_visit();
stop[t] = page[i];
visit[t] = 0;
}
}
else {
visit[f]++;
}
out(i);
}
}5.最近未使用算法(Clock)
//使用Clock算法
void CLOCK() {
int p = 0; //指向上一次的访问位(下标)
for (int i = 0; i < n; i++) {
int f = find(page[i]);
if (f == -1) {
disaffect++;
if (_cnt < cnt) {
stop[_cnt] = page[i];
visit[_cnt] = 1;
_cnt++;
}
else {
int t = l_find(p);
stop[t] = page[i];
visit[t] = 1;
p = (t + 1)%cnt;
}
}
else {
visit[f]=1;
}
out(i);
}
}五、完整代码展示
#include<iostream>
#include<stdlib.h>
#include<time.h>
#include<list>
using namespace std;
#define total 330
//变量定义
int a[total]; //指令流数组,a[i]表示第i条指令的地址
int appear[40]; // 出现次数,appear[i]表示在接下来的访问中第i页还需要访问的次数
int page[total]; //每条指令所属的页号,page[i]表示第i条指令所在的页号
int offset[total]; //每页装入10条指令后取模运算页号偏移值.
int total_pf; //用户进程的内存页面数.
int disaffect;//页面失效次数
int cnt; //驻留集个数
int stop[total]; //内存块stop[i]驻留集中第i个页号
int choice; //算法选择
int cho; //更改页面大小或驻留集大小选择
int n; //查询指令数
int _cnt; //驻留集剩余数量
double pro; //命中率
int store; //页面存放指令数
int visit[total]; //记录页面访问，visit[i]表示第i条指令已经访问过的次数
//确保输入合法
void check(int& x) {
while (cin >> x) {
if (x == 0) {
cout << "该值不能为零，请重新输入: ";
}
else {
break;
}
}
}
//得到指令序列
void get_list() {
srand(time(0));
int ins;
for (int i = 0; i < 320; i++)
{
ins = rand() % 320;
a[i] = ins;
}
}
// 初始化函数, 给每个相关的页面赋值
void init1() {
cnt = 0;
memset(page, -1, sizeof(page));
memset(offset, 0, sizeof(offset));
memset(appear, 0, sizeof(appear));
printf("请输入页面大小(单位是KB,要求为32的因数):");
check(store);
//页面数量
total_pf = 32 / store;
store = store * 10;
printf("请输入驻留集的个数cnt：");
check(cnt);
for (int i = 0; i < n; i++) {
page[i] = a[i] / store;
appear[page[i]]++;
offset[i] = a[i] % store;
}
}
//对不同的页面大小和驻留集大小循环的初始化
void _init1() {
printf("==============更改设置选项==============\n");
printf("1.更改页面大小\n");
printf("2.更改驻留集大小\n");
printf("3.更改页面和驻留集大小\n");
printf("========================================\n");
printf("请输入你要选择更改的序号(输入0退出更改)：");
scanf("%d", &cho);
printf("\n");
switch (cho) {
case 0:
printf("\n已退出更改选择\n");
break;
case 1:
memset(page, -1, sizeof(page));
memset(offset, 0, sizeof(offset));
memset(appear, 0, sizeof(appear));
printf("请输入页面大小(单位是KB,要求为32的因数):");
check(store);
//页面数量
total_pf = 32 / store;
store = store * 10;
for (int i = 0; i < n; i++) {
page[i] = a[i] / store;
appear[page[i]]++;
offset[i] = a[i] % store;
}
break;
case 2:
printf("请输入驻留集的个数cnt：");
check(cnt);
break;
case 3:
init1();
break;
default:
printf("选择不存在,更改失败，保持原设置！！\n");
break;
}
}
//对算法选择的循环
void init2() {
_cnt = 0;
disaffect = 0;
memset(stop, -1, sizeof(stop));
memset(visit, 0, sizeof(visit));
memset(appear, 0, sizeof(appear));
for (int i = 0; i < n; i++) {
appear[page[i]]++;
}
}
//输出每次访问结果
void out(int i) {
printf("指令%-3d: 访问虚存地址%-3d 所在页面%-2d: ", i+1, a[i], page[i]);
printf("内存块：");
for (int j = 0; j < cnt; j++)
printf(" %3d", stop[j]);
printf("\n");
}
//找到驻留集中最不经常使用的页
int min_visit() {
int t = 0;
for (int i = 1; i < cnt; i++) {
if (visit[i] < visit[t])
t = i;
}
return t;
}
//找到之后使用次数最少的页
int min_appear() {
int t = 0;
//找到驻留集中，出现次数最少的页
for (int i = 1; i < cnt; i++) {
if (appear[stop[t]] > appear[stop[i]])
t = i;
}
return t;
}
//判断驻留集中是否存在访问页面，存在返回下标，否则返回-1
int find(int x)
{
for (int i = 0; i < cnt; i++)
{
if (stop[i] == x)
return i;
}
return -1;
}
//循环找到最近未使用的页
int l_find(int p) {
for (int i = p; i < cnt; i = (i + 1) % cnt) {
if (visit[i] == 0)
return i;
else visit[i] = 0;
}
}
//用于最近最久未使用刷新栈
void update_stack(int f) {
int t = stop[f];
for (int i = f - 1; i >= _cnt; i--)
stop[i + 1] = stop[i];
stop[0] = t;
}
//使用OPT算法.
void OPT() {
for (int i = 0; i < n; i++)
{
int f = find(page[i]);
if (f == -1) {
disaffect++;
if (_cnt < cnt) {
stop[_cnt] = page[i];
_cnt++;
}
else {
//找出stop中出现次数最少的下标
int t = min_appear();
stop[t] = page[i];
}
}
appear[page[i]]--;
out(i);
}
}
//使用FIFO算法.
void FIFO() {
for (int i = 0; i < n; i++) {
int f = find(page[i]);
if (f == -1) {
stop[_cnt] = page[i];
_cnt = (_cnt+1)%cnt;
disaffect++;
}
out(i);
}
}
//使用LRU算法
void LRU() {
_cnt = cnt - 1;
for (int i = 0; i < n; i++) {
int f = find(page[i]);
if (f == -1) {
disaffect++;
if (_cnt >= 0) {
stop[_cnt] = page[i];
_cnt--;
}
else {
update_stack(cnt);
stop[0] = page[i];
}
}
else {
update_stack(f);
}
out(i);
}
}
//使用LFU算法.
void LFU() {
for (int i = 0; i < n; i++) {
int f = find(page[i]);
if (f == -1) {
disaffect++;
if (_cnt < cnt) {
stop[_cnt] = page[i];
_cnt++;
}
else {
int t = min_visit();
stop[t] = page[i];
visit[t] = 0;
}
}
else {
visit[f]++;
}
out(i);
}
}
//使用Clock算法
void CLOCK() {
int p = 0; //指向上一次的访问位(下标)
for (int i = 0; i < n; i++) {
int f = find(page[i]);
if (f == -1) {
disaffect++;
if (_cnt < cnt) {
stop[_cnt] = page[i];
visit[_cnt] = 1;
_cnt++;
}
else {
int t = l_find(p);
stop[t] = page[i];
visit[t] = 1;
p = (t + 1)%cnt;
}
}
else {
visit[f]=1;
}
out(i);
}
}
int main()
{
//确定页面大小和驻留集
get_list();
while (1) {
printf("输入访问的指令数量n (输入0退出访问)：");
scanf("%d", &n);
if (n == 0) break;
init1();
while (1) {
printf("访问序列：");
for (int i = 0; i < n; i++)
printf("%5d", a[i]);
cout << endl;
printf("所在页面：");
for (int i = 0; i < n; i++)
printf("%5d", page[i]);
cout << endl;
while (1) {
init2();
printf("==============算法选项==============\n");
printf("1.最佳淘汰算法(OPT)\n");
printf("2.先进先出算法(FIFO)\n");
printf("3.最近最久未使用算法(LRU)\n");
printf("4.最不经常使用算法(LFU)\n");
printf("5.最近未使用算法(Clock)\n\n");
printf("====================================\n");
printf("页面置换算法选择(输入0退出算法选择)： ");
scanf("%d", &choice);
if (choice == 0) {
printf("\n已退出算法选择！可重新更改参数\n\n");
break;
}
switch (choice) {
case 1:
OPT();
break;
case 2:
FIFO();
break;
case 3:
LRU();
break;
case 4:
LFU();
break;
case 5:
CLOCK();
break;
default:
printf("算法不存在，请重新输入!!\n");
break;
}
if (choice > 0 && choice < 6) {
printf("缺页次数：%d\n", disaffect);
printf("命中率：%.2lf%%\n\n", (1 - 1.0 * disaffect / n) * 100);
}
}
_init1();
if (cho == 0)break;
}
}
return 0;
}六、结果分析
1. 不同的访问指令数
增加访问指令数时，若页面冗余小，OPT 通常会表现最佳，但 FIFO 和 LRU 有接近的表现；小访问指令数可能导致 FIFO 显示出较高的缺页率，因为某些页面可能在短期内利用，而 FIFO 并不考虑页面的使用频率。
2. 不同的页面大
较小的页面大小意味着更多的页面可以被加载在内存中，自然可能会降低缺页率；较大的页面大小可能导致内存利用率低，即使使用最佳算法（如 OPT），也可能由于内存不够而导致较高的缺页率。
3. 不同的驻留集个数
增加驻留集个数通常会减少缺页率，特别是在有较高局部性访问的情况下。不同算法的表现会有所不同；对于 FIFO 和 LFU，增加驻留集个数在初期可能减少缺页率，但是可能后期在某些情境下反而导致更多的缺页，尤其是 FIFO。
帖子还没人回复快来抢沙发