Question

找高手求页面置换算法模拟

要求：
页面置换算法的模拟实现
分别实现最佳置换算法(optimal)、先进先出(FIFO)页面置换算法和最近最久未使用（LRU）置换算法，并给出各算法缺页次数和缺页率。

请发到我的邮箱：jojoyoyo2@163.com

如果调式可以通过的话，还悬赏30分

Answer 1

#include <iostream>
#include <deque>
#include <ctime>
using namespace std;

typedef struct
{
int id; //页面ID
int stayTime; //内存中驻留时间
int unUseTime; //已经多久未被使用
}CPage;
deque<int> RunQueue;
deque<CPage> interPage; //内存中的四个页面
deque<CPage> exterPage; //外存中的N个页面
int presentSeat; //目前运行到了队列的第几个？
int lackNum[3] ={0};
int getRandNum(int range) //返回[0,range)范围内的整数
{
return static_cast<int>(rand()%range);
}
int findPageIdByCmdId(int cmdId) //通过强制转换成整数的形式判断指令属于哪个页面
{
return static_cast<int>(cmdId/10);
}
void InitDevice() //初始化运行队列 按照25% 50% 25%的标准生成
{
srand(static_cast<int>(time(NULL)));
int t_cmdNum = getRandNum(320); //随机选择第一条指令
RunQueue.push_back(t_cmdNum); //将其插入队列
if(t_cmdNum < 319)
RunQueue.push_back(t_cmdNum+1); //顺序执行下一条指令

while(RunQueue.size() <= 320)
{
t_cmdNum = getRandNum(t_cmdNum); //跳转到m1属于[0,m-1]
RunQueue.push_back(t_cmdNum); //将m1插入队列
if(t_cmdNum < 319)
RunQueue.push_back(t_cmdNum+1); //将m1+1插入队列
int temp = 320 - (t_cmdNum + 2);
t_cmdNum = t_cmdNum+2+getRandNum(temp);//跳转到m2属于[m+2,319]
RunQueue.push_back(t_cmdNum); //插入队列
if(t_cmdNum < 319)
RunQueue.push_back(t_cmdNum+1); //将m2+1插入队列
}
while(RunQueue.size() > 320)
RunQueue.pop_back();
}
void InitMemoryQueue() //初始化运行标志、内存外存页面队列
{
presentSeat = 0;
exterPage.clear();
interPage.clear();
for(int i=0;i<32;i++)
{
CPage temp;
temp.id = i;
temp.stayTime = 0;
temp.unUseTime = 0;
exterPage.push_back(temp);
}
}
int searchStatusOfPage(int t_PageId,bool sign) //分别在内外存中查找页面 存在返回位置 不存在返回-1
{
if(sign)
for(unsigned i=0;i<interPage.size();i++)
{
if(t_PageId == interPage[i].id)
return i;
} //这里的括号不能删除，否则if else的匹配会出问题
else
for(unsigned j=0;j<exterPage.size();j++)
if(t_PageId == exterPage[j].id)
return j;
return -1;
}
int searchNextStatusOfInterPage(int start, int id) //OPT算法中查找内存页面中的页面下次需要用到它的时候的队列下标
{ //找到就返回下标 没找到就返回-1
for(int i=start;i < 320;i++)
if(static_cast<int>(RunQueue[i]/10) == id)
return i;
return -1;
}
int findLongestStayTimePage() //FIFO算法中查找在内存中呆了最久的页面
{
int max = 0;
for(unsigned i=1;i<interPage.size();i++)
if(interPage[i].stayTime>interPage[max].stayTime)
max = i;
return max;
}
int findLongestUnUseTimePage() //LRU算法中查找最久未使用的页面
{
int max = 0;
for(unsigned j=0;j<interPage.size();j++)
if(interPage[j].unUseTime>interPage[max].unUseTime)
max = j;
return max;
}
int findNeedLongestTimePage() //OPT算法中查找最长时间不会用到的页面
{
deque<int> temp;
for(unsigned i=0;i < interPage.size();i++)
{
int it = searchNextStatusOfInterPage(presentSeat,interPage[i].id);
if(it == -1)
return i;
temp.push_back(it);
}
int max = -1,status = 0;
for(unsigned j=1;j < temp.size();j++)
{
if(max < temp[j])
{
max = temp[j];
status = j;
}
}
return status; //返回需要最长时间才执行的页面在内存中的位置
}
void directFlod(int t_PageId) //当内存空间还有剩余时直接调入
{
int status = searchStatusOfPage(t_PageId,false);
if(status == -1) return;
interPage.push_back(exterPage[status]); //先插入节点到内存，再从外存中将其删除
exterPage.erase(exterPage.begin()+status);
}
bool Manage(int count,int t_PageId) //当内存已经满了需要按照三种算法调度时
{
int status = searchStatusOfPage(t_PageId,false); //获取执行页面在外存中的索引地址
if(status == -1)
return false;
int targetStatus = 0;
if(count == 0)
targetStatus = findNeedLongestTimePage();
else if(count == 1)
targetStatus = findLongestStayTimePage();
else if(count == 2)
targetStatus = findLongestUnUseTimePage();
interPage[targetStatus].stayTime = 0;
interPage[targetStatus].unUseTime = 0;
swap(exterPage[status],interPage[targetStatus]);
return true;
}
void Run(int count) //运行，通过count来决定使用什么算法
{
while(presentSeat < 320)
{
for(unsigned i=0;i<interPage.size();i++)
{
interPage[i].stayTime++;
interPage[i].unUseTime++;
}
int t_PageId = findPageIdByCmdId(RunQueue[presentSeat++]),status = -1; //找到当前将要执行的指令的页面号
if((status =searchStatusOfPage(t_PageId,true)) != -1)
{
interPage[status].unUseTime = 0;
continue;
}
lackNum[count]++;
if(interPage.size()<4)
directFlod(t_PageId);
else
Manage(count,t_PageId);
}
}
void main(void) //主函数
{
InitDevice();
int count = 0;
while(count<3)
{
InitMemoryQueue();
Run(count);
cout<<(double)lackNum[count++]/320*100<<"%"<<endl;
}
}