天天看點
傳回

作業系統：實驗四 頁面置換算法

一. 實驗目的：

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:

作業系統：實驗四 頁面置換算法
作業系統 C/C++ 頁面置換算法
上一篇: 頁面置換算法實驗報告C語言,作業系統頁面置換算法實驗報告.doc
下一篇: 記憶體管理之頁面置換算法

繼續閱讀