操作系统课设页面置换算法

操作系统课程设计

模拟 (1) LRU、(2)OPT算法

#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; }

}