操作系统：实验四 页面置换算法
程序员文章站
2022-07-14 21:35:46
...
一. 实验目的：
1、通过编写和调试存储管理的模拟程序以加深对存储管理方案的理解。熟悉虚存管理的各种页面淘汰算法
2、通过编写和调试地址转换过程的模拟程序以加强对地址转换过程的了解。
二 . 实验指导：
设计一个请求页式存储管理方案。并编写模拟程序实现之。流程图见下图。
产生一个需要访问的指令地址流。它是一系列需要访问的指令的地址。为不失一般性，你可以适当地（用人工指定地方法或用随机数产生器）生成这个序列。 页面淘汰算法分别采用 FIFO页面淘汰算法和LRU算法，并且在淘汰一页时，只将该页在页表中抹去。而不再判断它是否被改写过，也不将它写回到辅存。
具体的做法可以是：
产生一个需要访问的指令地址流（也可以依次输入地址）；
指定合适的页面尺寸（例如以 1K或2K为1页）；
制定为进程分配的物理块数
每访问一个地址时，首先要计算该地址所在的页的页号，然后查各物理块，判断该页是否在主存——如果该页已在主存，则打印物理快使用情况；如果该页不在主存且物理快未满，则调入一页并打印物理块使用情况；如果该页不在主存且物理块已满，则淘汰算法淘汰一页后调入所需的页，打印物理块使用情况；
逐个地址访问，直到所有地址访问完毕。
LRU算法：
思路：
LRU
利用一个链表来实现，
每次新插入数据的时候将新数据插到链表的尾部；
每次缓存命中（即数据被访问），
则将数据移到链表尾部；
那么当链表满的时候，
就将链表头部的数据丢弃。
void LRU()
{
// vector<int> page_number_set;//放置过去的和现在的页号
vector<table> ta(physics_cnt);
for(int i=0; i<ta.size(); i++) //初始化
{
ta[i].physical_block_number=i;
ta[i].page_number=-1;
}
while(1)
{
cout<<endl;
cout<<"输入要访问的逻辑地址(-1退出):";
cin>>logical_address;
if(logical_address==-1)
{
system("cls");
break;
}
else if(logical_address<job_logical_size*1024)
{
address_transformation(logical_address);
// page_number_set.push_back(page_num);
cout<<endl;
cout<<"\t页号："<<page_num;
int flag=0;
int index_page;
vector<table>::iterator it=ta.begin();
for(int i=0; i<ta.size(); i++,it++)
{
if(ta[i].page_number==page_num)
{
index_page=i;
flag=1;//命中
break;
}
}
if(flag==0)
{
cout<<" 该页不在内存中,调入!"<<endl;
int f=0;
for(int i=0; i<ta.size(); i++)
{
if(ta[i].page_number==-1)//直接调入
{
f=1;
ta[i].page_number=page_num;
break;
}
}
if(f==0)//已无空闲物理块,置换!
{
cout<<endl;
cout<<"\t已无空闲物理块,置换!"<<endl;
vector<table>::iterator k = ta.begin();
table node1;
node1.page_number=page_num;
node1.physical_block_number=(*k).physical_block_number;
ta.erase(k);
ta.push_back(node1);
}
}
else//命中
{
cout<<" 该页已在内存中!"<<endl;
table node;
node.page_number=ta[index_page].page_number;
node.physical_block_number=ta[index_page].physical_block_number;
ta.erase(it);
ta.push_back(node);
}
cout<<endl;
cout<<" 物理块号 页号"<<endl;
for(int i=0; i<ta.size(); i++)
{
cout<<"\t "<<ta[i].physical_block_number<<" ";
printf("%2d\n",ta[i].page_number);
}
cout<<endl;
cout<<" 块号是：";
int index;
for(int i=0; i<ta.size(); i++)
{
if(page_num==ta[i].page_number)
{
index=i;
break;
}
}
cout<<ta[index].physical_block_number<<" 物理地址是："<<physics_address+1024*ta[index].physical_block_number<<endl;
}
else
{
cout<<endl;
cout<<" 错误，地址越界！！"<<endl;
cout<<endl;
}
}
}
FIFO算法：
该算法思路特别简单，在此我不多做赘述，直接看代码
void FIFO()
{
vector<table> ta(physics_cnt);
for(int i=0; i<ta.size(); i++) //初始化
{
ta[i].physical_block_number=i;
ta[i].page_number=-1;
}
while(1)
{
cout<<endl;
cout<<"输入要访问的逻辑地址(-1退出):";
cin>>logical_address;
if(logical_address==-1)
{
system("cls");
break;
}
else if(logical_address<job_logical_size*1024)
{
address_transformation(logical_address);
cout<<endl;
cout<<"\t页号："<<page_num;
int flag=0;
for(int i=0; i<ta.size(); i++)
{
if(ta[i].page_number==page_num)
flag=1;
}
if(flag==0)
{
cout<<" 该页不在内存中,调入!"<<endl;
int f=0;
for(int i=0; i<ta.size(); i++)
{
if(ta[i].page_number==-1)//直接调入
{
f=1;
ta[i].page_number=page_num;
break;
}
}
if(f==0)//已无空闲物理块,置换!
{
cout<<endl;
cout<<"\t已无空闲物理块,置换!"<<endl;
vector<table>::iterator k = ta.begin();
table node;
node.physical_block_number=ta[0].physical_block_number;
node.page_number=page_num;
ta.erase(k);
ta.push_back(node);
}
}
else//命中
{
cout<<" 该页已在内存中!"<<endl;
}
cout<<endl;
cout<<" 物理块号 页号"<<endl;
for(int i=0; i<ta.size(); i++)
{
cout<<"\t "<<ta[i].physical_block_number<<" ";
printf("%2d\n",ta[i].page_number);
}
cout<<endl;
cout<<" 块号是：";
int index;
for(int i=0; i<ta.size(); i++)
{
if(page_num==ta[i].page_number)
{
index=i;
break;
}
}
cout<<ta[index].physical_block_number<<" 物理地址是："<<physics_address+1024*ta[index].physical_block_number<<endl;
}
else
{
cout<<endl;
cout<<" 错误，地址越界！！"<<endl;
cout<<endl;
}
}
}
源代码：
#include<bits/stdc++.h>
using namespace std;
int page_size=1;//页面大小
int job_logical_size=20;//作业逻辑地址空间大小
int physics_cnt=3;//物理块数
int logical_address;//逻辑地址
int page_num;//页号
int physics_address;//物理地址
struct table
{
int physical_block_number;//物理块号
int page_number;//页号
};
void menu()
{
cout<<"\n\n"<<endl;
cout<<"\t 页面置换算法模拟程序"<<endl;
cout<<endl;
cout<<"\t1. 初始化"<<endl;
cout<<endl;
cout<<"\t2. FIFO算法"<<endl;
cout<<endl;
cout<<"\t3. LRU算法"<<endl;
cout<<endl;
cout<<"\t0. 退出"<<endl;
cout<<endl;
cout<<" 注：已初始化页面大小为1kb，作业地址空间大小为20kb。"<<endl;
cout<<endl;
cout<<" 已为作业分配物理块数为3。页面分配策略采用固定分配局部置换。"<<endl;
cout<<endl;
cout<<endl;
cout<<"请输入选择:";
}
void init()
{
system("cls");
cout<<endl;
cout<<"输入页面大小(kb):";
cin>>page_size;
cout<<endl;
cout<<"请输入作业逻辑地址空间大小(kb):";
cin>>job_logical_size;
cout<<endl;
cout<<"输入物理块数:";
cin>>physics_cnt;
system("cls");
}
void address_transformation(int logical_address)
{
int L;
L=page_size*1024;
page_num=logical_address/L;
physics_address=logical_address%L;
}
void FIFO()
{
vector<table> ta(physics_cnt);
for(int i=0; i<ta.size(); i++) //初始化
{
ta[i].physical_block_number=i;
ta[i].page_number=-1;
}
while(1)
{
cout<<endl;
cout<<"输入要访问的逻辑地址(-1退出):";
cin>>logical_address;
if(logical_address==-1)
{
system("cls");
break;
}
else if(logical_address<job_logical_size*1024)
{
address_transformation(logical_address);
cout<<endl;
cout<<"\t页号："<<page_num;
int flag=0;
for(int i=0; i<ta.size(); i++)
{
if(ta[i].page_number==page_num)
flag=1;
}
if(flag==0)
{
cout<<" 该页不在内存中,调入!"<<endl;
int f=0;
for(int i=0; i<ta.size(); i++)
{
if(ta[i].page_number==-1)//直接调入
{
f=1;
ta[i].page_number=page_num;
break;
}
}
if(f==0)//已无空闲物理块,置换!
{
cout<<endl;
cout<<"\t已无空闲物理块,置换!"<<endl;
vector<table>::iterator k = ta.begin();
table node;
node.physical_block_number=ta[0].physical_block_number;
node.page_number=page_num;
ta.erase(k);
ta.push_back(node);
}
}
else//命中
{
cout<<" 该页已在内存中!"<<endl;
}
cout<<endl;
cout<<" 物理块号 页号"<<endl;
for(int i=0; i<ta.size(); i++)
{
cout<<"\t "<<ta[i].physical_block_number<<" ";
printf("%2d\n",ta[i].page_number);
}
cout<<endl;
cout<<" 块号是：";
int index;
for(int i=0; i<ta.size(); i++)
{
if(page_num==ta[i].page_number)
{
index=i;
break;
}
}
cout<<ta[index].physical_block_number<<" 物理地址是："<<physics_address+1024*ta[index].physical_block_number<<endl;
}
else
{
cout<<endl;
cout<<" 错误，地址越界！！"<<endl;
cout<<endl;
}
}
}
void LRU()
{
// vector<int> page_number_set;//放置过去的和现在的页号
vector<table> ta(physics_cnt);
for(int i=0; i<ta.size(); i++) //初始化
{
ta[i].physical_block_number=i;
ta[i].page_number=-1;
}
while(1)
{
cout<<endl;
cout<<"输入要访问的逻辑地址(-1退出):";
cin>>logical_address;
if(logical_address==-1)
{
system("cls");
break;
}
else if(logical_address<job_logical_size*1024)
{
address_transformation(logical_address);
// page_number_set.push_back(page_num);
cout<<endl;
cout<<"\t页号："<<page_num;
int flag=0;
int index_page;
vector<table>::iterator it=ta.begin();
for(int i=0; i<ta.size(); i++,it++)
{
if(ta[i].page_number==page_num)
{
index_page=i;
flag=1;//命中
break;
}
}
if(flag==0)
{
cout<<" 该页不在内存中,调入!"<<endl;
int f=0;
for(int i=0; i<ta.size(); i++)
{
if(ta[i].page_number==-1)//直接调入
{
f=1;
ta[i].page_number=page_num;
break;
}
}
if(f==0)//已无空闲物理块,置换!
{
cout<<endl;
cout<<"\t已无空闲物理块,置换!"<<endl;
vector<table>::iterator k = ta.begin();
table node1;
node1.page_number=page_num;
node1.physical_block_number=(*k).physical_block_number;
ta.erase(k);
ta.push_back(node1);
}
}
else//命中
{
cout<<" 该页已在内存中!"<<endl;
table node;
node.page_number=ta[index_page].page_number;
node.physical_block_number=ta[index_page].physical_block_number;
ta.erase(it);
ta.push_back(node);
}
cout<<endl;
cout<<" 物理块号 页号"<<endl;
for(int i=0; i<ta.size(); i++)
{
cout<<"\t "<<ta[i].physical_block_number<<" ";
printf("%2d\n",ta[i].page_number);
}
cout<<endl;
cout<<" 块号是：";
int index;
for(int i=0; i<ta.size(); i++)
{
if(page_num==ta[i].page_number)
{
index=i;
break;
}
}
cout<<ta[index].physical_block_number<<" 物理地址是："<<physics_address+1024*ta[index].physical_block_number<<endl;
}
else
{
cout<<endl;
cout<<" 错误，地址越界！！"<<endl;
cout<<endl;
}
}
}
int main()
{
int flag=1;
while(1)
{
menu();
int sel;
cin>>sel;
switch(sel)
{
case 1:
init();
break;
case 2:
FIFO();
break;
case 3:
LRU();
break;
case 0:
flag=0;
break;
}
if(flag==0)
break;
}
return 0;
}
运行效果：
FIFO:
LRU:
上一篇： Clickhouse环境安装
下一篇： JAVA简单工厂模式