操作系統的頁面調度演算法

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

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

❷ 操作系統概論的LRU調度演算法

LUR是最近最少使用調度演算法。
剛開始三個內存單元都是空的，7,0,1直接裝入內存；
當2要裝入內存時，由於3個內存單元都已被暫用，必須先有一個頁讓出內存，根據最近最少使用調度演算法的原則，最少使用的頁號為7（最長時間未使用），所以7出去，2進來，形成0,1,2的布局（2取代了7的位置，所以實際的順序是2,0,1，但是將其按照最長時間未使用的順序排列便於理解和後面的運算）
0頁面要裝入內存，但是其實它本來已經就在內存中，所以無需調度，內存中頁面不變，將其按照最長時間未使用的順序排列為1,2,0（實際順序還是2,0,1）；
3要進入內存，將最長時間未用到的1替換出去，所以又變成了2,0,3（3替換原來1的位置，所以實際順序為2,0,3）
依次類推可得結果。

❸ 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)

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

（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個物理塊，使用程序的動態頁面序列生成演算法，生成一個頁面序列，將此序列存入磁碟文件。再從磁碟文件讀入該序列，用程序分別計算三種演算法下的缺頁中斷次數、缺頁中斷率和缺頁調度次數、缺頁置換率。

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

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

❻ 最佳頁面淘汰演算法是怎樣計算的

<1> 先進先出調度演算法
先進先出調度演算法根據頁面進入內存的時間先後選擇淘汰頁面，先進入內存的頁面先淘汰，後進入內存的後淘汰。本演算法實現時需要將頁面按進入內存的時間先後組成一個隊列，每次調度隊首頁面予以淘汰。
<2>最近最少調度演算法
先進先出調度演算法沒有考慮頁面的使用情況，大多數情況下性能不佳。根據程序執行的局部性特點，程序一旦訪問了某些代碼和數據，則在一段時間內會經常訪問他們，因此最近最少用調度在選擇淘汰頁面時會考慮頁面最近的使用，總是選擇在最近一段時間以來最少使用的頁面予以淘汰。演算法實現時需要為每個頁面設置數據結構記錄頁面自上次訪問以來所經歷的時間。
<3>最近最不常用調度演算法
由於程序設計中經常使用循環結構，根據程序執行的局部性特點，可以設想在一段時間內經常被訪問的代碼和數據在將來也會經常被訪問，顯然這樣的頁面不應該被淘汰。最近最不常用調度演算法總是根據一段時間內頁面的訪問次數來選擇淘汰頁面，每次淘汰訪問次數最少的頁面。演算法實現時需要為每個頁面設置計數器，記錄訪問次數。計數器由硬體或操作系統自動定時清零。
（2）缺頁調度次數和缺頁中斷率、缺頁置換率計算
缺頁中斷次數是缺頁時發出缺頁中斷的次數。
缺頁中斷率=缺頁中斷次數/總的頁面引用次數*100%
缺頁調度次數是調入新頁時需要進行頁面調度的次數
缺頁置換率=缺頁調度次數/總的頁面引用次數*100%

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

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過程就是這樣。

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

❽ 操作系統的主要演算法都有哪些

一、進程(作業)調度演算法
l 先來先服務調度演算法（FCFS）：每次調度是從就緒隊列中，選擇一個最先進入就緒隊列的進程，把處理器分配給該進程，使之得到執行。該進程一旦佔有了處理器，它就一直運行下去，直到該進程完成或因發生事件而阻塞，才退出處理器。特點：利於長進程，而不利於短進程。

l 短進程（作業）優先調度演算法(SPF)：它是從就緒隊列中選擇一個估計運行時間最短的進程，將處理器分配給該進程，使之佔有處理器並執行，直到該進程完成或因發生事件而阻塞，然後退出處理器，再重新調度。

l 時間片輪轉調度演算法 ：系統將所有的就緒進程按進入就緒隊列的先後次序排列。每次調度時把CPU分配給隊首進程，讓其執行一個時間片，當時間片用完，由計時器發出時鍾中斷，調度程序則暫停該進程的執行，使其退出處理器，並將它送到就緒隊列的末尾，等待下一輪調度執行。

l 優先數調度演算法 ：它是從就緒隊列中選擇一個優先權最高的進程，讓其獲得處理器並執行。

l 響應比高者優先調度演算法：它是從就緒隊列中選擇一個響應比最高的進程，讓其獲得處理器執行，直到該進程完成或因等待事件而退出處理器為止。特點：既照顧了短進程，又考慮了進程到達的先後次序，也不會使長進程長期得不到服務，因此是一個比較全面考慮的演算法，但每次進行調度時，都需要對各個進程計算響應比。所以系統開銷很大，比較復雜。

l 多級隊列調度演算法

基本概念：

作業周轉時間（Ti）＝完成時間(Tei)－提交時間(Tsi)

作業平均周轉時間(T)＝周轉時間/作業個數

作業帶權周轉時間（Wi）＝周轉時間/運行時間

響應比＝（等待時間＋運行時間）/運行時間

二、存儲器連續分配方式中分區分配演算法
n 首次適應分配演算法（FF）：對空閑分區表記錄的要求是按地址遞增的順序排列的，每次分配時，總是從第1條記錄開始順序查找空閑分區表，找到第一個能滿足作業長度要求的空閑區，分割這個空閑區，一部分分配給作業，另一部分仍為空閑區。

n 循環首次適應演算法：每次分配均從上次分配的位置之後開始查找。

n 最佳適應分配演算法(BF)：是按作業要求從所有的空閑分區中挑選一個能滿足作業要求的最小空閑區，這樣可保證不去分割一個更大的區域，使裝入大作業時比較容易得到滿足。為實現這種演算法，把空閑區按長度遞增次序登記在空閑區表中，分配時，順序查找。

三、頁面置換演算法
l 最佳置換演算法（OPT) ：選擇以後永不使用或在最長時間內不再被訪問的內存頁面予以淘汰。

l 先進先出置換演算法（FIFO）：選擇最先進入內存的頁面予以淘汰。

l 最近最久未使用演算法（LRU）：選擇在最近一段時間內最久沒有使用過的頁，把它淘汰。

l 最少使用演算法（LFU）：選擇到當前時間為止被訪問次數最少的頁轉換。

四、磁碟調度
n 先來先服務（FCFS）：是按請求訪問者的先後次序啟動磁碟驅動器，而不考慮它們要訪問的物理位置

n 最短尋道時間優先（SSTF）：讓離當前磁軌最近的請求訪問者啟動磁碟驅動器，即是讓查找時間最短的那個作業先執行，而不考慮請求訪問者到來的先後次序，這樣就克服了先來先服務調度演算法中磁臂移動過大的問題

n 掃描演算法（SCAN）或電梯調度演算法：總是從磁臂當前位置開始，沿磁臂的移動方向去選擇離當前磁臂最近的那個柱面的訪問者。如果沿磁臂的方向無請求訪問時，就改變磁臂的移動方向。在這種調度方法下磁臂的移動類似於電梯的調度，所以它也稱為電梯調度演算法。

n 循環掃描演算法（CSCAN）：循環掃描調度演算法是在掃描演算法的基礎上改進的。磁臂改為單項移動，由外向里。當前位置開始沿磁臂的移動方向去選擇離當前磁臂最近的哪個柱面的訪問者。如果沿磁臂的方向無請求訪問時，再回到最外，訪問柱面號最小的作業請求。