欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

操作系统页面置换算法之FIFO,LRU

程序员文章站 2022-07-05 08:05:48
...
#include<iostream>
#include<unistd.h>
#include<vector>
#include<wait.h>
#include<iterator>
#include<ctime>
#include<cmath>
#include<algorithm>

using namespace std;

const int total_i = 10;
const int mf1 = 3;
const int mf2 = 4;

vector<int> access_series(total_i);

int firstEmpty(vector<int>& v,int n)
{
	for(int i = 0;i < n;++i)
		if(v[i] == -1)
			return i;
	return -1;
}

int getLen()
{
	int index = 0;
	vector<int> v = access_series;
	sort(v.begin(),v.end());
	for(int i = 0;i < total_i;++i)
	{
		if (v[index] != v[i])
			v[++index] = v[i];
	}
	return index + 1;
}
			
int getLeast(vector<int>& v,int n)
{
	int min = v[0];
	int position = 0;
	for(int i = 0;i < n;++i)
	{
		if(v[i] != 0 && v[i] < min)
		{
			min = v[i];
			position = i;
		}
	}
	return position;
}
	
void change(vector<int>& state,int size)
{
	for(int k = 0;k < size;++k)
		if(state[k] != -1)
			state[k] >>= 1;
}

void FIFO(int n)
{
	int miss = 0;
	vector<int> v(n,-1);
	for(int i = 0;i < total_i;++i)
	{
		bool flag = false;
		for(int j = 0;j < n;++j)
		{
			if(v[j] == access_series[i])
			{
				flag = true;
				break;
			}
		}
		if(!flag)
		{
			++miss;
			for(int k = 0;k < n - 1;++k)
				v[k] = v[k + 1];
			v[n - 1] = access_series[i];
		}
		copy(v.begin(),v.end(),ostream_iterator<int>(cout," "));
		cout<<endl;
	}
	cout<<"\npage miss:"<<miss * 1.0 / total_i<<"\n";
}

void LRU(int n)
{
	int miss = 0;
	vector<int> v(n,-1);
	int size = getLen();
	vector<int> state(size,0);
	for(int i = 0;i < total_i;++i)
	{
		int pos = -1;
		for(int j = 0;j < n;++j)
		{
			if(v[j] == access_series[i])
			{
				pos = j;
				break;
			}
		}
		if(pos == -1)//not found
		{
			++miss;
			int p = firstEmpty(v,n);
			if(p != -1)//has empty position
			{
				change(state,size);
				v[p] = access_series[i];
				state[p] = pow(2,size - 1);	
			}
			else
			{
				change(state,size);
				int p1 = getLeast(state,size);
				v[p1] = access_series[i];
				state[p1] = pow(2,size - 1);
			}
		}
		else 
		{
			change(state,size);
			//state[pos] >>= 1; 
			state[pos] += pow(2,size - 1); 
		}
		copy(v.begin(),v.end(),ostream_iterator<int>(cout," "));
		cout<<endl;
	}
	cout<<"\npage miss:"<<miss * 1.0 / total_i<<"\n";
}

int main()
{
	int p1,p2,p3;
	srand((unsigned)time(0));
	for(int i = 0;i < total_i;++i)
		access_series[i] = rand() % 6;
		//cin>>access_series[i];
	copy(access_series.begin(),access_series.end(),ostream_iterator<int>(cout," "));
	cout<<endl;
	while((p1 = fork()) == -1);
	if(p1 == 0)
	{
		cout<<"\nFIFO:\n";
		FIFO(mf1);
	}
	else
	{
		wait(0);
		while((p2 = fork()) == -1);
		if(p2 == 0)
		{
			cout<<"\nFIFO:\n";
			FIFO(mf2);
		}
		else
		{
			wait(0);
			while((p3 = fork()) == -1);
			if(p3 == 0)
			{
				cout<<"\nLRU:\n";
				LRU(mf1);
			}
		}
	}
	return 0;
}