虛擬內存的調低演算法

⑴ 求高手教教我"虛擬內存頁面調度演算法"

其實我不懂你這個問題下面是我復制別人的 哈 不知道是不是
#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;
}
}