頁面調度演算法

① 操作系統原理與應用之 頁面調度演算法問題

FIFO：即先進先出演算法，就是先進去的頁在位置不夠時先淘汰。所以具體如下：
主存開始為空
訪問1，1不在主存中，產生缺頁中斷，添加，主存里現在是：1
訪問2，2不在主存中，產生缺頁中斷，添加，主存里現在是：1,2
以此類推，
1,2,3（缺頁中斷）
1,2,3,6（缺頁中斷）
訪問4，4不在主存中，缺頁中斷，主存滿了，最早的1淘汰，主存里現在是：2,3,6,4
然後3,6,4,7（缺頁中斷，2淘汰）
然後3，3在主存中，不產生中斷
然後6,4,7,2（缺頁中斷，3淘汰）
4,7,2,1（缺頁中斷，6淘汰）
4在主存中，不中斷
7在主存中，不中斷
7,2,1,5（缺頁中斷，4淘汰）
2,1,5,6（缺頁中斷，7淘汰）
5在主存中，不中斷
2在主存中，不中斷
1在主存中，不中斷
整個FIFO過程就是這樣。

LRU是最近最久未使用的先淘汰，具體如下：
1（缺頁中斷）
1,2（缺頁中斷）
1,2,3（缺頁中斷）
1,2,3,6（缺頁中斷）
2,3,6,4（缺頁中斷，1最久沒用過，淘汰）
3,6,4,7（缺頁中斷，2最久沒用過，淘汰）
3在主存中，不中斷，3最近使用過，主存中順序調整為6,4,7,3
4,7,3,2（缺頁中斷，6最久沒用過，淘汰）
7,3,2,1（缺頁中斷，4最久沒用過，淘汰）
3,2,1,4（缺頁中斷，7最久沒用過，淘汰）
2,1,4,7（缺頁中斷，3最久沒用過，淘汰）
1,4,7,5（缺頁中斷，2最久沒用過，淘汰）
4,7,5,6（缺頁中斷，1最久沒用過，淘汰）
5在主存中，調整順序為4,7,6,5
7,6,5,2（缺頁中斷，4最久沒用過，淘汰）
6,5,2,1（缺頁中斷，7最久沒用過，淘汰）
整個LRU過程就是這樣。

全手打求採納謝謝~！如有問題請追問~

② 頁面調度演算法

- 後的答案，你知道
打字不易，如滿意，望採納。

③ 頁面調度先進先出演算法（FIFO） 用C語言描述 歡迎高手前來挑戰

c語言實現的頁面調度演算法,用三種演算法實現調度1.先進先出2.OPT3.LRU 2.頁面序列從指定的文本文件（TXT文件）中取出3.輸出：第一行：每次淘汰的頁面號 第二行：顯示缺頁的總次數(上機已經運行通過!!)-pages scheling algorithm, a three-Scheling Algorithm 1. FIFO 2.OPT3.LRU 2. Pages from the designated sequence of text files (TXT) out of three. Output : the first line : each of the pages out of the second line : show na the total number of pages (on the plane had run through! !)

④ 頁面調度演算法的實驗目的

頁式虛擬存儲器實現的一個難點是設計頁面調度（置換）演算法，即將新頁面調入內存時，如果內存中所有的物理頁都已經分配出去，就要按某種策略來廢棄某個頁面，將其所佔據的物理頁釋放出來，供新頁面使用。本實驗的目的是通過編程實現幾種常見的頁面調度（置換）演算法，加深讀者對頁面思想的理解。

⑤ 頁面調度演算法的實驗內容

（1）設計程序實現以上三種頁面調度演算法，要求：
①.可以選擇頁面調度演算法類型；
②.可以為進程設置分到物理頁的數目，設置進程的頁面引用情況，可以從鍵盤輸入頁面序列，也可從文件中讀取；
③.隨時計算當前的頁面調度次數的缺頁中斷率；
④.使用敲鍵盤或響應WM-TIMER的形式模仿時間的流逝；
⑤.以直觀的的形式將程序的執行情況顯示在計算機屏幕上；
⑥.存檔及讀盤功能，可以隨時將數據存入磁碟文件，供以後重復實驗時使用。
（2）假定進程分配到3個物理塊，對於下面的頁面引用序列：
7-0-1-2-0-3-0-4-2-3-0-3-2-1-2-0-1-7-0-1
請分別用先進和先出調度演算法，最近最少用調度演算法，最近最不常用調度演算法計算缺頁中斷次數，缺頁中斷率和缺頁調度次數、缺頁置換率。
再假定進程分配到4、5個物理塊，重復本實驗。
（3）假定進程分配到3個物理塊，對於下面的頁面引用序列：
4-3-2-1-4-3-5-4-3-2-1-5-0-7-3-8-9-0-2-1-4-7-3-9
請分別用先進先出調度演算法、最近最少用調度演算法，最近最不常用調度演算法計算缺頁中斷次數，缺頁中斷率和缺頁調度次數、缺頁置換率。
再假定進程分配到4、5個物理塊，重復本實驗。
（4）假定進程分配到3個物理塊，使用程序的動態頁面序列生成演算法，生成一個頁面序列，將此序列存入磁碟文件。再從磁碟文件讀入該序列，用程序分別計算三種演算法下的缺頁中斷次數、缺頁中斷率和缺頁調度次數、缺頁置換率。

⑥ 如何利用FIFO頁面調度演算法計算！

4 2 3 0 0 0 1 2 2 2
4 2 3 3 3 0 1 1 1
4 2 2 2 3 0 0 0
FT T F F T T
F：中斷 前面三個已裝入了不算中斷。希望對你有幫助。

⑦ 頁面調度演算法的實驗步驟

#include stdafx.h
#include conio.h
#include iostream.h
#include fstream.h
//-------------------------------Menu----------------------#define KEY_EXIT '-'
typedef struct{
char ch;
char *label;
void (*pfunc)();
}MenuItemDef;
Void clearscr() {cout<< ;}
int waitakey(){return getch();}
class MenuDef
{public:
int nCount;
MenuItemDef menu[24];
public:
MenuDef(){nCount=0;}
public:
void display()
{ for(int i=0; i<nCount;i++)
cout<< <<menu.ch<<.<<menu.label<<endl;
cout<< <<KEY_EXIT<<.<<EXIT<<endl; }
void run()
{int ch;
do{clearscr();
display();
ch=waitakey();
for(int i=0;i<nCount;i++)
if(menu.ch==ch)
menu.pfunc();
}while(ch!=KEY_EXIT); }
void add (char ch0,char *plabel,void(*func)())
{ menu[nCount].ch=ch0;
menu[nCount].label=plabel;
menu[nCount].pfunc=func;
nCount++;}};
//--------------------------------------page-----------------------
class Page{
public:
Page(){SetNull();}
public:
enum{kLFU=0,kFCFS,kLRU};
int nCurPage;
int nAlgID;
int nCountPage;
int pages[128];
int nCountFrame;
int nEmpty;
int frames[32];
int counters[32];
int nCount1;
int nCount2;
public:
void Input();
void Run();
int IsFinish(){return nCurPage>=nCountPage;}
void SetAlgorithm(int kAlgId){nAlgID=kAlgId;}
void SetNull()
{nCurPage=nCountPage=nCountFrame=nCount1=nCount2=nEmpty=0 ; nAlgID=kLRU;}
double IPercent(){return nCount1*1.0/nCurPage;}//缺頁中斷率
double EPercent(){return nCount2*1.0/nCurPage;}//缺頁轉換率
//functions should be implemented......
void FCFS() {} //先來先服務調度演算法
void LRU() {} //LRU調度演算法
void LFU() {} //LFU調度演算法
void Display() {} //系統狀態
void DisplayAlg() {} //演算法執行狀態
public:
friend istream& operator>>(istream&stream,Page&p)
{return stream;}
friend ostream& operator>>(ostream&stream,Page&p)
{return stream;} };
void Page::Input()
{ cout<<Count of page-frames:;
cin>>nCountFrame;
nEmpty=nCountFrame;
cout<<Count of page:;
cin>>nCountPage;
for (int i=0;i<nCountPage;i++)
cin>>pages;
nCurPage=0;
}
void Page::Run()
{ while(!IsFinish()){
waitakey(); //wait for a key pressed
if(nAlgID==kLFU)
LFU();
else if(nAlgID==kFCFS)
FCFS();
else
LRU();
DisplayAlg();
nCurPage++;}}
//------------global variables-----------------
MenuDef menu;
Page page;
//------------call-back functions for menu-------
void input()
{ clearscr();
page.SetNull();
page.Display();}
void display()
{ clearscr();
page.Display();}
void setalg1()
{ page.SetAlgorithm(Page::kLFU); }
void setalg2()
{ page.SetAlgorithm(Page::kFCFS); }
void setalg3()
{ page.SetAlgorithm(Page::kLRU); }
void run()
{ clearscr();
page.Run();}
void load()
{ char fname[128];
cout<< Load From file:;
cin>>fname;
ifstream inFile;
inFile.open(fname);
page.SetNull();
inFile>>page; }
void save()
{ char fname[128];
cout<< Save to file:;
cin>>fname;
ofstream outFile;
outFile.open(fname);
outFile>>page; }
void main(int args,char *argv[])
{ menu.add('1',Input from keyboard, input);
menu.add('3',Set Algorithm1:LFU,setalg1);
menu.add('4',Set Algorithm2:FCFS, setalg2);
menu.add('5',Set Algorithm3:LRU, setalg3);
menu.add('6',Display, display);
menu.add('7',Run, run);
menu.add('8',Load from file, load);
menu.add('9',Save to file, save);
menu.run();}

⑧ 頁面調度演算法的實現和分析源碼

dev c++

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
typedef struct mem
{
int num;
int v;
}meme;
static int process[1024],L,M;
void LRU();
void FIFO();
void get();
int menu();

int main()
{
menu();
system("pause");
}

int menu()
{
int x;
while(1)
{
printf("************************************************\n\n");
printf("*************1.輸入頁面地址流長度***************\n");
printf("*************2.輸入存儲塊數目 ***************\n");
printf("*************3.獲得頁面地址流 ***************\n");
printf("*************4.FIFO演算法 ***************\n");
printf("*************5.LRU演算法 ***************\n");
printf("*************6.退出 ***************\n\n");
printf("************************************************\n\n");
printf("請選擇：");
scanf("%d",&x);
switch(x)
{
case 1:printf("\n請輸入頁面地址流長度L(10<L<100)：");scanf("%d",&L);break;
case 2:printf("\n請輸入輸入存儲塊數目M(3<=M<=5)：");scanf("%d",&M);break;
case 3:printf("\n獲得頁面地址流為：");get();break;
case 4:printf("\n演算法：FIFO L=%d M=%d",L,M);FIFO();break;
case 5:printf("\n演算法：LRU L=%d M=%d",L,M);LRU();break;
case 6:exit(0);break;
default:printf("\n輸入錯誤！");break;
}
printf("\n\n");
}
}

void get()
{
srand((unsigned)time(NULL));
for(int i=0;i<L;i++)
{
process[i]=rand()%10;
printf("%d ",process[i]);
}
}

void FIFO()
{
int i = 0, j = 0,k=0,x,y;
int replace,count=0;
meme memery[M];
printf("\n頁號");
for(k=0;k<M;k++){printf("\t塊%d",k+1);memery[k].num=-1;}
printf("\t淘汰\t缺頁統計");

for(i = 0; i<L; i++) //對輸入序列進行循環
{
x=0;y=0; //置x，y初值為0
for(j = 0; j <M; j++) //對三個內存塊進行循環，先查找有沒有與即將訪問頁號相同的
if(memery[j].num == process[i])
{ x=1;//有相同的則置x為1
replace=-2;
break;//跳出此次內存塊循環
}

if(x==0)//沒有與即將訪問頁號相同的內存塊
{
for(j = 0; j <M; j++)//對內存塊循環，查找有沒有空內存塊
if(memery[j].num==-1)
{
y=1;//有則置y為1
replace=-1;count++;
memery[j].num=process[i];// 置此內存塊為訪問頁號
if(j!=0) memery[j-1].v=0;//置上一個訪問塊v為0
memery[j].v=1;//置此塊v為1
break;//跳出此次內存塊循環
}
}

if(x==0&&y==0)//既沒有與即將訪問頁號相同的內存塊也沒有空內存塊
{
for(j=0;j<M;j++)//對內存塊循環，查找出v=1的內存塊
{
if(memery[j].v==1)
{
memery[j].v=0;//置此塊v為0
count++;
if(j!=M-1)
{
replace=memery[j+1].num;
memery[j+1].num=process[i]; //置下個內存塊為訪問頁號塊
memery[j+1].v=1;//置下個內存塊v為1
}
else
{
replace=memery[0].num;
memery[0].num=process[i]; //置下個內存塊為訪問頁號塊
memery[0].v=1;//置下個內存塊v為1
}
break;
}
}
}

printf("\n%d",process[i]);
for(j = 0 ;j <M; j++) //列印每次訪問後的情況
printf("\t%d",memery[j].num);
if(replace!=-2)
printf("\t%d",replace);
else printf("\t");
printf("\t%d",count);
}
}

void LRU()
{
int i = 0, j = 0,k=0,x,y;
int replace,count=0;
meme memery[M];
printf("\n頁號");
for(k=0;k<M;k++){printf("\t塊%d",k+1);memery[k].num=-1;}
printf("\t淘汰\t缺頁統計");

for(i = 0; i<L; i++) //對輸入序列進行循環
{
x=0;y=0; //置x，y初值為0
for(j = 0; j<M; j++) //對三個內存塊進行循環，先查找有沒有與即將訪問頁號相同的
if(memery[j].num == process[i])
{ x=1;//有相同的則置x為1
replace=-2;
memery[j].v=0;//置此塊v為0
for(k=0;k<M;k++)
if(k!=j&&memery[k].num!=-1)memery[k].v++;//其他不為-1頁v++
break;//跳出此次內存塊循環
}

if(x==0)//沒有與即將訪問頁號相同的內存塊
{
for(j = 0; j <M; j++)//對內存塊循環，查找有沒有空內存塊
if(memery[j].num==-1)
{
y=1;//有則置y為1
replace=-1; count++;
memery[j].num=process[i];// 置此內存塊為訪問頁號
memery[j].v=0;//置此塊v為0
for(k=0;k<M;k++)
if(k!=j&&memery[k].num!=-1)memery[k].v++;//其他不為-1頁v++
break;//跳出此次內存塊循環
}
}

if(x==0&&y==0)//既沒有與即將訪問頁號相同的內存塊也沒有空內存塊
{
int m=memery[0].v;
for(j = 0; j < M; j++)
{
if(memery[j].v>m)
m=memery[j].v;
}//查找出v最大的內存塊m
for(j=0;j<M;j++)//對內存塊循環，v=m的內存塊
{
if(memery[j].v==m)
{
replace=memery[j].num;
count++;
memery[j].num=process[i]; //置此內存塊為訪問頁號塊
memery[j].v=0;//置此塊v為0
}
else memery[j].v++;//其他塊v++
}
}

printf("\n%d",process[i]);
for(j = 0 ;j <M; j++) //列印每次訪問後的情況
printf("\t%d",memery[j].num);
if(replace!=-2)
printf("\t%d",replace);
else printf("\t");
printf("\t%d",count);
}
}

⑨ k：=（k+1）mod n頁面調度FIFO演算法公式怎麼解釋

條件：
a^k = n (mod k+1)
b^k = m (mod k+1)
m*n = 1 (mod k+1)
所以(ab)^k = 1 (mod k+1) (1)

記k+1的歐拉函數為ψ(k+1)，那麼在(1,ψ(k+1))內，有且僅有
a^ψ(k+1) = 1 (mod k+1)
b^ψ(k+1) = 1 (mod k+1)
相乘得(ab)^ψ(k+1) = 1 (mod k+1) (2)
由於k >=ψ(k+1)
由(1)(2)可以得到k = p * ψ(k+1)
所以m = a^k = (a^ψ(k+1))^p = 1 (mod k+1)
n = b^k = (b^ψ(k+1))^p = 1 (mod k+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;
}
}