#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;
}
操作系统页面置换算法之FIFO,LRU
程序员文章站
2022-07-05 08:05:48
...