頁置換演算法例題

『壹』 頁面置換演算法模擬

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

參考資料：http://..com/question/41040745.html

希望採納

『貳』 頁面置換演算法的實驗

#include <stdio.h>
#define PROCESS_NAME_LEN 32 /*進程名稱的最大長度*/
#define MIN_SLICE 10 /*最小碎片的大小*/
#define DEFAULT_MEM_SIZE 1024 /*默認內存的大小*/
#define DEFAULT_MEM_START 0 /*默認內存的起始位置*/

/* 內存分配演算法 */
#define MA_FF 1
#define MA_BF 2
#define MA_WF 3

int mem_size=DEFAULT_MEM_SIZE; /*內存大小*/
int ma_algorithm = MA_FF; /*當前分配演算法*/
static int pid = 0; /*初始pid*/
int flag = 0; /*設置內存大小標志*/

struct free_block_type
{
int size;
int start_addr;
struct free_block_type *next;
};
struct free_block_type *free_block;

struct allocated_block
{
int pid;
int size;
int start_addr;
char process_name[PROCESS_NAME_LEN];
struct allocated_block *next;
};
struct allocated_block *allocated_block_head;

/*初始化空閑塊，默認為一塊，可以指定大小及起始地址*/
struct free_block_type* init_free_block(int mem_size)
{

struct free_block_type *fb;

fb=(struct free_block_type *)malloc(sizeof(struct free_block_type));
if(fb==NULL)
{
printf("No mem\n");
return NULL;
}
fb->size = mem_size;
fb->start_addr = DEFAULT_MEM_START;
fb->next = NULL;
return fb;
}

void display_menu()
{
printf("\n");
printf("1 - Set memory size (default=%d)\n", DEFAULT_MEM_SIZE);
printf("2 - Select memory allocation algorithm\n");
printf("3 - New process \n");
printf("4 - Terminate a process \n");
printf("5 - Display memory usage \n");
printf("0 - Exit\n");
}

/*設置內存的大小*/
int set_mem_size()
{
int size;
if(flag!=0)
{ /*防止重復設置*/
printf("Cannot set memory size again\n");
return 0;
}
printf("Total memory size =");
scanf("%d", &size);
if(size>0)
{
mem_size = size;
free_block->size = mem_size;
}
flag=1;
return 1;
}
/*Best-fit使用最小的能夠放下將要存放數據的塊，First-first使用第一個能夠放下將要存放數據的塊，Worst-fit使用最大的能夠放下將要存放數據的塊。*/
/* 設置當前的分配演算法 */
/*分區分配演算法(Partitioning Placement Algorithm)
*/
void set_algorithm()
{
int algorithm;
printf("\t1 - First Fit\n");/*首次適應演算法(FF)：。 */
printf("\t2 - Best Fit\n");/*最佳適應演算法(BF)： */

printf("\t3 - Worst Fit\n");
scanf("%d", &algorithm);
if(algorithm>=1 && algorithm <=3) ma_algorithm=algorithm;
/*按指定演算法重新排列空閑區鏈表*/
rearrange(ma_algorithm);
}

void swap(int* data_1,int* data_2)
{
int temp;
temp=*data_1;
*data_1=*data_2;
*data_2=temp;
}

void rearrange_FF()
{
struct free_block_type *tmp, *work;
printf("Rearrange free blocks for FF \n");
tmp = free_block;
while(tmp!=NULL)
{
work = tmp->next;
while(work!=NULL)
{
if( work->start_addr < tmp->start_addr)
{ /*地址遞增*/
swap(&work->start_addr, &tmp->start_addr);
swap(&work->size, &tmp->size);
}
else
{
work=work->next;
}
}
tmp=tmp->next;
}
}
/*按BF演算法重新整理內存空閑塊鏈表(未完成)
void rearrange_BF()
{
struct free_block_type *tmp,*work;
printf("Rearrange free blocks for BF\n");
tmp=free_block;
while(tmp!=NULL)
{
work=tmp->next;
while(work!=NULL)
{

}
}

}

*/
/*按WF演算法重新整理內存空閑塊鏈表(未完成)
void rearrange_WF()
{
struct free_block_type *tmp,*work;
printf("Rearrange free blocks for WF \n");
tmp=free_block;
while(tmp!=NULL)
{
work=tmp->next;
while(work!=NULL)
{

}
}
}
*/

/*按指定的演算法整理內存空閑塊鏈表*/
int rearrange(int algorithm)
{
switch(algorithm)
{
case MA_FF: rearrange_FF(); break;
/*case MA_BF: rearrange_BF(); break; */
/*case MA_WF: rearrange_WF(); break; */
}
}

/*創建新的進程，主要是獲取內存的申請數量*/
int new_process()
{
struct allocated_block *ab;
int size;
int ret;
ab=(struct allocated_block *)malloc(sizeof(struct allocated_block));
if(!ab)
exit(-5);
ab->next = NULL;
pid++;
sprintf(ab->process_name, "PROCESS-%02d", pid);
ab->pid = pid;

printf("Memory for %s:", ab->process_name);
scanf("%d", &size);
if(size>0) ab->size=size;
ret = allocate_mem(ab); /* 從空閑區分配內存，ret==1表示分配ok*/
/*如果此時allocated_block_head尚未賦值，則賦值*/
if((ret==1) &&(allocated_block_head == NULL))
{
allocated_block_head=ab;
return 1;
}
/*分配成功，將該已分配塊的描述插入已分配鏈表*/
else if (ret==1)
{
ab->next=allocated_block_head;
allocated_block_head=ab;
return 2;
}
else if(ret==-1)
{ /*分配不成功*/
printf("Allocation fail\n");
free(ab);
return -1;
}
return 3;
}

/*分配內存模塊*/
int allocate_mem(struct allocated_block *ab)
{
struct free_block_type *fbt,*pre,*r;
int request_size=ab->size;
fbt=pre=free_block;
while(fbt!=NULL)
{
if(fbt->size>=request_size)
{
if(fbt->size-request_size>=MIN_SLICE)
{
fbt->size=fbt->size-request_size;
}
/*分配後空閑空間足夠大，則分割*/

else
{
r=fbt;
pre->next=fbt->next;
free(r);
/*分割後空閑區成為小碎片，一起分配*/

return 1;
}
}
pre = fbt;
fbt = fbt->next;
}

return -1;
}

/*將ab所表示的已分配區歸還，並進行可能的合並*/
int free_mem(struct allocated_block *ab)
{
int algorithm = ma_algorithm;
struct free_block_type *fbt, *pre, *work;

fbt=(struct free_block_type*) malloc(sizeof(struct free_block_type));
if(!fbt)
return -1;
fbt->size = ab->size;
fbt->start_addr = ab->start_addr;
/*插入到空閑區鏈表的頭部並將空閑區按地址遞增的次序排列*/
fbt->next = free_block;
free_block=fbt;
rearrange(MA_FF);
fbt=free_block;
while(fbt!=NULL)
{
work = fbt->next;
if(work!=NULL)
{
/*如果當前空閑區與後面的空閑區相連，則合並*/
if(fbt->start_addr+fbt->size == work->start_addr)
{
fbt->size += work->size;
fbt->next = work->next;
free(work);
continue;
}
}
fbt = fbt->next;
}
rearrange(algorithm); /*重新按當前的演算法排列空閑區*/
return 1;
}

/*?釋放ab數據結構節點*/
int dispose(struct allocated_block *free_ab)
{
struct allocated_block *pre, *ab;

if(free_ab == allocated_block_head)
{ /*如果要釋放第一個節點*/
allocated_block_head = allocated_block_head->next;
free(free_ab);
return 1;
}
pre = allocated_block_head;
ab = allocated_block_head->next;

while(ab!=free_ab)
{
pre = ab;
ab = ab->next;
}
pre->next = ab->next;
free(ab);
return 2;
}
/*查找要刪除的進程*/
struct allocated_block* find_process(int pid)
{
struct allocated_block *temp;
temp=allocated_block_head;
while(temp!=NULL)
{
if(temp->pid==pid)
{
return temp;
}
temp=temp->next;
}
}

/*刪除進程，歸還分配的存儲空間，並刪除描述該進程內存分配的節點*/
void kill_process()
{
struct allocated_block *ab;
int pid;
printf("Kill Process, pid=");
scanf("%d", &pid);
ab=find_process(pid);
if(ab!=NULL)
{
free_mem(ab); /*釋放ab所表示的分配區*/
dispose(ab); /*釋放ab數據結構節點*/

}
}

/* 顯示當前內存的使用情況，包括空閑區的情況和已經分配的情況 */

int display_mem_usage()
{
struct free_block_type *fbt=free_block;
struct allocated_block *ab=allocated_block_head;
if(fbt==NULL) return(-1);
printf("----------------------------------------------------------\n");

/* 顯示空閑區 */
printf("Free Memory:\n");
printf("%20s %20s\n", " start_addr", " size");
while(fbt!=NULL)
{
printf("%20d %20d\n", fbt->start_addr, fbt->size);
fbt=fbt->next;
}
/* 顯示已分配區 */
printf("\nUsed Memory:\n");
printf("%10s %20s %10s %10s\n", "PID", "ProcessName", "start_addr", " size");
while(ab!=NULL)
{
printf("%10d %20s %10d %10d\n", ab->pid, ab->process_name, ab->start_addr, ab->size);
ab=ab->next;
}
printf("----------------------------------------------------------\n");
return 0;
}

**********************************************************************
樓主啊，小女子給你的是殘缺版滴，要是你給我分，我就把剩下滴給你,上次在北京大學貼吧都被人騙了，世道炎涼啊O(∩_∩)O~

『叄』 最佳頁面置換演算法的舉例

假定系統為耨進程分配的物理塊數為3，訪問以下頁面：4,2,96,2,6,9,4,9,2.採用最佳置換演算法時的置換圖。

『肆』 頁面置換演算法

  上文說到，請求分頁管理方式中，當需要調入頁面到內存中，但此時內存已滿，就需要從內存中按照一定的置換演算法決定將哪個頁面取出將內存給調入的頁面。本文將介紹幾種頁面置換算方法。
   本文內容

  演算法思想：每次選擇 淘汰的頁面 將是 以後永不使用 ，或者 在最長時間內不再被訪問的頁面 ，這樣可以保證最低的缺頁率。
  舉例說明，假設系統為進程分配了三個內存塊，並考慮到有以下頁面號引用串（會依次訪問這些頁面）：7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1

  ....按照此演算法依次執行，最後的結果如下

  結果圖

  註：缺頁時未必發生頁面置換，若還有可用的空閑內存空間就不用進行頁面置換。
  最佳置換演算法可以保證最低的缺頁率，但是實際上，只有進程執行的過程中才能知道接下來會訪問到的是哪個頁面。操作系統無法提前預判頁面的訪問序列。因此， 最佳置換演算法是無法實現的 。

  演算法思想：每次選擇 淘汰的頁面是最早進入內存的頁面。
  該演算法很簡單，每次淘汰最在內存中待時間最久的各個，下面分別給出系統為進程分為配三個內存塊和四個內存塊的執行情況圖。訪問序列為3,2,1,0,3,2,4,3,2,1,0,4
  分配三個內存塊的情況：

  分配四個內存塊的情況：

  當為進程分配的物理塊數增大時，缺頁次數不減反增的異常現象稱為 貝萊迪（Belay）異常 。
   只有FIFO演算法會產生Belay異常。 另外，FIFO演算法雖然實現簡單，但是該演算法與進程實際運行時的規律不適應。因為先進入的頁面也有可能最經常被訪問。因此， 演算法性能差。

  演算法思想： 每次淘汰的頁面是最近最久未使用的頁面。
  實現方法：賦予每個頁面對應的頁表項中，用 訪問欄位記錄該頁面純虧自上次被訪問以來所經歷的時間t。 當需要淘汰一個頁面時，選擇現有頁面中t最大的頁面，即最近最久未使用。

  舉例說明，加入某系統為某進程分配了四個內存塊，並考慮到有以下頁面號引用串：1,8,1,7,8,2,7,2,1,8,3,8,2,1,3,1,7,1,3,7
  這里先直接給出答案

  結果圖

  最佳置換演算法那性能最好，但無法實現。先進先出置換演算法實現簡單，但是演算法性能差。最近最久未使用置換演算法性能好，是最接近OPT演算法性能的，但是實現起來需要專門的硬體支持，演算法開銷大。 時鍾置換演算法 是一種 性能和開銷均春褲配平衡 的演算法。又稱 CLOCK演算法 ，或 最近未用演算法 （ NRU ，Not Recently Used）
   簡單CLOCK演算法 演算法思想：為每個頁面設置一個 訪問位 ，再將內存中的頁面都通過 鏈接指針鏈接成一個循環隊列 。當某個頁被訪問時，其訪問位置1.當需要淘汰一個頁面時，只需檢查頁的訪問位。如果是0，就選擇該頁換出；如果是1，暫不換出，將訪問位改為0，繼續檢查下一個頁面，若第一輪掃描中所有的頁面都是1，則將這些頁面的訪問位一次置為0後，再進行第二輪掃描（第二輪掃描中一定會有訪問位為0的頁面，因此簡單的CLOCK演算法選擇一個扒指淘汰頁面最多會經過 兩輪掃描 ）。

  這個演算法指針在掃描的過程就像時鍾一樣轉圈，才被稱為時鍾置換演算法。

  簡單的時鍾置換演算法僅考慮到了一個頁面最近是否被訪問過。事實上，如果淘汰的頁面沒有被修改過，就不需要執行I/O操作寫回外存。 只有淘汰的頁面被修改過時，才需要寫回外存。
  因此，除了考慮一個頁面最近有沒有被訪問過之外，操作系統還需要考慮頁面有沒有被修改過。
  改進型時鍾置換演算法的 演算法思想 ： 在其他在條件相同時，應該優先淘汰沒有被修改過的頁面， 從而來避免I/O操作。
  為了方便討論，用（訪問位，修改位）的形式表示各頁面的狀態。如（1,1）表示一個頁面近期被訪問過，且被修改過。
   演算法規則 ：將所有可能被置換的頁面排成一個循環隊列

  由於第二輪已將所有的頁的訪問位都設為0，因此第三輪、第四輪掃描一定會選中一個頁，因此 改進型CLOCK置換演算法最多會進行四輪掃描。

  假設系統為進程分配了5個內存塊，某時刻，各個頁的狀態如下圖

  如果此時有新的頁要進入內存，開始第一輪掃描就找到了要替換的頁，即最下面的狀態為（0,0）的頁。

  某一時刻頁面狀態如下

  如果此時有新的頁要進入內存，開始第一輪掃描就發現沒有狀態為（0，0）的頁，第一輪掃描後不修改任何標志位。所以各個頁狀態和上圖一樣。
  然後開始第二輪掃描，嘗試找到狀態為（0,1）的頁，並將掃描過後的頁的訪問位設為0，第二輪掃描找到了要替換的頁。

  某一時刻頁面狀態如下

  第一輪掃描沒有找到狀態為（0,0）的頁，且第一輪掃描不修改任何標志位，所以第一輪掃描後狀態和上圖一致。
  然後開始第二輪掃描，嘗試找狀態為（0,1）的頁，也沒有找到，第二輪掃描需要將訪問位設為1，第二輪掃描後，狀態為下圖

  某一時刻頁面狀態如下

  具體的掃描過程和上面相同，這里只給出最後的結果，如下圖

  所以，改進型的CLOCK置換演算法最多需要四輪掃描確定要置換的頁。從上面的分析可以看出，改進型的CLOCK置換演算法
  (1) 第一優先順序淘汰的是 最近沒有訪問且沒有修改 的頁面。
  (2) 第二優先順序淘汰的是 最近沒有訪問但修改 的頁面。
  (3) 第三優先順序淘汰的是 最近訪問但沒有修改 的頁面。
  (4) 第四優先順序淘汰的是 最近訪問且修改 的頁面。

『伍』 c語言編寫頁面置換演算法

//熬夜弄出來的，記得加分哦
#include<stdio.h>
void Print(int bc[],int blockCount)
{
for(int i=0;i<blockCount;i++)
{
printf("%d ",bc[i]);
}
printf("\n");
}

bool Travel(int bc[],int blockCount,int x)
{
bool is_found=false;
int i;
for(i=0;i<blockCount;i++)
{
if(bc[i]==x)
{
is_found=true;
break;
}
}
return is_found;
}

void FIFO(int pc[],int bc[],int pageCount,int blockCount)
{
printf("0：FIFO置換演算法\n");
int i;
if(pageCount<=blockCount)
{
printf("缺頁次數為0\n");
printf("缺頁率為0\n");
}
else
{
int noPage=0;
int p=0;
for(i=0;i<pageCount;i++)
{

//printf("引用頁：%d\n",pc[i]);
if(!Travel(bc,blockCount,pc[i]))
{
if(i<blockCount)
{
bc[i]=pc[i];
}
else
{
if(p==blockCount)
{
p=0;
}
bc[p]=pc[i];
p++;

}
noPage++;
//printf("物理塊情況：\n");
//Print(bc,blockCount);
}
//printf("\n");
}
printf("FIFO缺頁次數為:%d\n",noPage);
printf("FIFO缺頁率為:%.2f%%\n",(float)noPage/pageCount*100);
}
}

int FoundMaxNum(int a[],int n)
{
int k,j;
k=a[0];
j=0;
for (int i=0;i<n;i++)
{
if(a[i]>=k)
{
k=a[i];
j=i;
}
}
return j;
}

void LRU(int pc[],int bc[],int pageCount,int blockCount)
{
printf("1：LRU置換演算法\n");
if(pageCount<=blockCount)
{
printf("缺頁次數為0\n");
printf("缺頁率為0\n");
}
else
{
int noPage=0;
int i,j,m;
int bc1[100];
for(i=0;i<blockCount;i++)
{
bc1[i]=0;
}
for(i=0;i<pageCount;i++)
{
// printf("引用頁：%d\n",pc[i]);
if(!Travel(bc,blockCount,pc[i]))
{
if(i<blockCount)
{
bc[i]=pc[i];
for(int p=0;p<=i;p++)
{
bc1[p]++;
}
}
else
{
for(j=0;j<blockCount;j++)
{
bc1[j]++;
}
int k=FoundMaxNum(bc1,blockCount);
bc[k]=pc[i];
bc1[k]=1;

}
noPage++;
//printf("物理快情況：\n");
//Print(bc,blockCount);
}
else if(Travel(bc,blockCount,pc[i]))
{
if(i<blockCount)
{
for(j=0;j<=i;j++)
{
bc1[j]++;
}
for(m=0;m<=i;m++)
{
if(bc[m]==pc[i])
{
break;
}
}
bc1[m]=1;
bc[m]=pc[i];

}
else
{
for(j=0;j<blockCount;j++)
{
bc1[j]++;
}
for(m=0;m<blockCount;m++)
{
if(bc[m]==pc[i])
{
break;
}
}
bc1[m]=1;
bc[m]=pc[i];
}
}
//printf("\n");
}
printf("LRU缺頁次數為:%d\n",noPage);
printf("LRU缺頁率為:%.2f%%\n",(float)noPage/pageCount*100);
}
}

void Optiomal(int pc[],int bc[],int pageCount,int blockCount)
{
printf("2：最佳置換演算法\n");
if(pageCount<=blockCount)
{
printf("缺頁次數為0\n");
printf("缺頁率為0\n");
}
else
{
int noPage=0;
int i,j,k;
for(i=0;i<pageCount;i++)
{
// printf("引用頁：%d\n",pc[i]);
if(!Travel(bc,blockCount,pc[i]))
{
if(i<blockCount)
{
bc[i]=pc[i];
}
else
{
int max=0;
int blockIndex;;
for(j=0;j<blockCount;j++)
{
for(k=i;k<pageCount;k++)
{
if(bc[j]==pc[k])
{
break;
}
}
if(k>=max)
{
max=k;
blockIndex=j;
}
}
bc[blockIndex]=pc[i];

}
noPage++;
//printf("物理快情況：\n");
//Print(bc,blockCount);
}
//printf("\n");
}
printf("OPT缺頁次數為:%d\n",noPage);
printf("OPT缺頁率為:%.2f%%\n",(float)noPage/pageCount*100);
}
}

int main()
{
int pageCount,blockCount,i,pc[100];
printf("輸入頁面數\n");
scanf("%d",&pageCount);
printf("輸入頁面走向\n");
for(i=0;i<pageCount;i++)
{
scanf("%d",&pc[i]);
}
blockCount=3;//物理塊數
int bc1[100];
printf("\n");
FIFO(pc,bc1,pageCount,blockCount);
int bc2[100];
printf("\n");
LRU(pc,bc2,pageCount,blockCount);
int bc3[100];
printf("\n");
Optiomal(pc,bc3,pageCount,blockCount);
return 0;
}

『陸』 LRU替換演算法怎麼理解，過程好難，這個題麻煩大神幫我看看

• LRU是LeastRecently Used 近期最少使用演算法，也就是說，近期最少使用的那個頁面，將被置換出去（可以理解為這個頁面將被廢棄）

• 對於本題。內存容量為4個頁面，這是要清楚的。具體看下面的表格：

• 缺頁率 = 6 / 20 =3/ 10 = 30%

• 我具體解釋下上面的表格吧。

  從上到下是4個頁面。

• 最開始，1需要被調用，將1放入內存中，由於1一開始沒有，所以一次缺頁

• 然後，8要被調用，，將1放入內存中，由於8一開始沒有，所以又產生一次缺頁

• 以此往後，直到4塊內存都滿了，最新使用過的放在最下面（頁4），則置換出最上面（頁1）。

• 通俗地說，就是總共空間只有4塊。只能放4個頁面。那麼當頁面滿的時候，就把你很久很久沒有使用過的那個頁面（也就是近期最少使用的頁面）置換出去，然後補充新的頁面進來。

• 這個算是頁面置換裡面比較經典的一個演算法了，希望能幫到你！