頁面置換演算法c實現

『壹』 操作系統課程設計，用C#實現內存頁面的置換。實現演算法間比較

頁面置換演算法

一．題目要求：

通過實現頁面置換演算法的FIFO和LRU兩種演算法，理解進程運行時系統是怎樣選擇換出頁面的，對於兩種不同的演算法各自的優缺點是哪些。

要求設計主界面以靈活選擇某演算法，且以下演算法都要實現 1) 最佳置換演算法(OPT)：將以後永不使用的或許是在最長(未來)時間內不再被訪問的頁面換出。

2) 先進先出演算法(FIFO)：淘汰最先進入內存的頁面，即選擇在內存中駐留時間最久的頁面予以淘汰。

3) 最近最久未使用演算法(LRU)：淘汰最近最久未被使用的頁面。 4) 最不經常使用演算法(LFU) 二．實驗目的：

1、用C語言編寫OPT、FIFO、LRU，LFU四種置換演算法。 2、熟悉內存分頁管理策略。 3、了解頁面置換的演算法。 4、掌握一般常用的調度演算法。 5、根據方案使演算法得以模擬實現。 6、鍛煉知識的運用能力和實踐能力。 三、設計要求

1、編寫演算法，實現頁面置換演算法FIFO、LRU；

2、針對內存地址引用串，運行頁面置換演算法進行頁面置換； 3、演算法所需的各種參數由輸入產生（手工輸入或者隨機數產生）； 4、輸出內存駐留的頁面集合，頁錯誤次數以及頁錯誤率；

四．相關知識：

1．虛擬存儲器的引入：

局部性原理：程序在執行時在一較短時間內僅限於某個部分；相應的，它所訪問的存儲空間也局限於某個區域，它主要表現在以下兩個方面：時間局限性和空間局限性。

2．虛擬存儲器的定義：

虛擬存儲器是只具有請求調入功能和置換功能，能從邏輯上對內存容量進行擴充的一種存儲器系統。

3．虛擬存儲器的實現方式：

分頁請求系統，它是在分頁系統的基礎上，增加了請求調頁功能、頁面置換功能所形成的頁面形式虛擬存儲系統。

請求分段系統，它是在分段系統的基礎上，增加了請求調段及分段置換功能後，所形成的段式虛擬存儲系統。

4．頁面分配：

平均分配演算法，是將系統中所有可供分配的物理塊，平均分配給各個進程。 按比例分配演算法，根據進程的大小按比例分配物理塊。

考慮優先的分配演算法，把內存中可供分配的所有物理塊分成兩部分：一部分按比例地分配給各進程；另一部分則根據個進程的優先權，適當的增加其相應份額後，分配給各進程。

5．頁面置換演算法：

常用的頁面置換演算法有OPT、FIFO、LRU、Clock、LFU、PBA等。 五、設計說明

1、採用數組頁面的頁號

2、FIFO演算法，選擇在內存中駐留時間最久的頁面予以淘汰；

分配n個物理塊給進程，運行時先把前n個不同頁面一起裝入內存，然後再從後面逐一比較，輸出頁面及頁錯誤數和頁錯誤率。

3、LRU演算法，根據頁面調入內存後的使用情況進行決策；

同樣分配n個物理塊給進程，前n個不同頁面一起裝入內存，後面步驟與前一演算法類似。

選擇置換演算法，先輸入所有頁面號，為系統分配物理塊，依次進行置換： 六．設計思想：

OPT基本思想：

是用一維數組page[pSIZE]存儲頁面號序列，memery[mSIZE]是存儲裝入物理塊中的頁面。數組next[mSIZE]記錄物理塊中對應頁面的最後訪問時間。每當發生缺頁時，就從物理塊中找出最後訪問時間最大的頁面，調出該頁，換入所缺的頁面。

FIFO基本思想：

是用隊列存儲內存中的頁面，隊列的特點是先進先出，與該演算法是一致的，所以每當發生缺頁時，就從隊頭刪除一頁，而從隊尾加入缺頁。或者藉助輔助數組time[mSIZE]記錄物理塊中對應頁面的進入時間，每次需要置換時換出進入時間最小的頁面。

LRU基本思想：

是用一維數組page[pSIZE]存儲頁面號序列，memery[mSIZE]是存儲裝入物理塊中的頁面。數組flag[10]標記頁面的訪問時間。每當使用頁面時，刷新訪問時間。發生缺頁時，就從物理塊中頁面標記最小的一頁，調出該頁，換入所缺的頁面。 七．流程圖：

如下頁所示

六．運行結果： 1. 按任意鍵進行初始化：

2. 載入數據：

3. 進入置換演算法選擇界面：

4.運算中延遲操作：

5.三種演算法演示結果：

『貳』 採用近期最少使用（LFU）演算法模擬請求分頁系統（C語言實現）

你這個問題拿到網路上是不可能有人回答你的，而且像這種操作系統的問題，步驟這么多是要收費的。去csdn求助試試。

『叄』 C++編程，clock置換演算法

#include<iostream>
#include<stdlib.h>
#include<time.h>
#define N 20 //虛擬內存尺寸
using namespace std;

int P;
int const blockCount=3 ;//內存中的物理塊數
int count = 0;
int block[blockCount];
int const PageCount=15;//總的頁面數
int Page[PageCount];
int state[blockCount];//clock置換演算法中，內存中的每個頁面號對應的狀態
int state2[blockCount][2];// 二維數組，第一行第一列為訪問位，第一行的第二列為修改位
double lost= 0.0;

void generate_list(int *list,int e,int m,int t)
{
int i,j=0,q=P,r;
srand((unsigned)time(NULL));
while(j<e)
{
for(i=j;i<j+m;i++)
{
if(i==e)
break;
list[i]=(q+rand()%e)%N; //保證在虛擬內存的頁號內
}
j=i;
r=rand()%100;
if(r<t)
q=rand()%N;
else
q=(q+1)%N;
}
}

//隨機生產是否被修改的情況，prop(0……100),prop/100的概率為被修改
void generate_modify(int *mo,int e,int prop)
{
int i,t;
for(i=0;i<e;i++)
{
t=rand()%100;
if(t>prop)
mo[i]=0;
else
mo[i]=1;
}
}

//檢測頁號是否在內存中
bool inblock(int num)
{
for(int i=0; i<blockCount;i++)
{
if(block[i] == Page[num])
{
state[i] = 1;
return true;
}
}
return false;
}

//判斷頁面是否已經被修改
bool change()
{
if((rand()%2+1) == 1 )
{
printf("該頁面被修改!\n");
return true;
}
else
return false;
}

//用於改進型clock置換演算法，檢測頁號是否在內存中並把訪問位和修改位置1
bool inblock2(int num)
{
for(int i=0;i<blockCount;i++){
if(block[i] == Page[num]){
if(change()){
state2[i][0] = 1;
state2[i][1] = 1;
}
else{
state2[i][0] = 1;
}
return true;
}
}
return false;
}

//用於改進型clock置換演算法，判斷內存中第幾個需要被置換
int whichpage(){

int j;

for(j=0;j<blockCount;j++)
{
if(state2[j][0] == 0&&state2[j][1] == 0)
{
return j;
}
}
for(j=0;j<blockCount;j++ )
{
if(state2[j][0] == 0&&state2[j][1] == 1)
{
return j;
}
state2[j][0] = 0 ;
}
for(j=0;j<blockCount;j++ )
{
state2[j][0] =0 ;
}
return whichpage();
}

//簡單Clock置換演算法
void CLOCK(int num)
{
int j;

if(inblock(num))
{
printf("命中!\n");
lost++;
for(int i=0;i<blockCount;i++)
printf("物理塊%d#中內容:%d\n",i,block [i]);
}
else
if(count == blockCount)
{
//lost++;
for(j=0;j<blockCount; )
{
if(state[j] == 0)
{
break;
}
else{
state[j] = 0;
}
j++;
j = j%3;
}
block[j] = Page[num];
state[j] = 1;
for(int i=0;i<blockCount;i++)
printf("物理塊%d#中內容:%d\n",i,block[i]);
}
else{
block[count] = Page[num];
count++;
for(int i=0;i<blockCount;i++)
printf("物理塊%d#中內容:%d\n",i,block[i]);
}
}

//改進型clock置換演算法
void LCLOCK(int num)
{
int j;

if(inblock2(num))
{
printf("命中!\n");
lost++;
for(int i=0;i<blockCount;i++)
printf("物理塊%d#中內容:%d\n",i,block[i]);
}
else
if(count == blockCount)
{
//lost++;
j = whichpage();
block[j] = Page[num];
state2[j][0] = 1;
for(int i=0;i<blockCount;i++)
printf("物理塊%d#中內容:%d\n",i,block[i]);
}
else{
block[count] = Page[num];
count++;
for(int i=0;i<blockCount;i++)
printf("物理塊%d#中內容:%d\n",i,block[i]);
}
}

int main()
{
int a[N];
int mo[N];
int A=10;
int e,m,prop,t,j;
printf("頁面走向為：");
generate_list(a, e,m,t);
generate_modify(mo,e,prop);

for(int i = 0;i<PageCount;i++)
{

Page[i] =rand()%9 + 1;
printf("%d ",Page[i]);
}
char ch ;
printf("\n");
printf("\t\t1 Clock置換演算法\n");
printf("\t\t2 改進型Clock置換演算法\n");
printf("\t\t3 退出!\n\n");
printf("請輸入演算法序號:\t\n");
while(1){
scanf("%c",&ch);
switch(ch){
case '1':{
lost=0;
count=0;
for(int m=0;m<blockCount;m++)
{
state[m] = 0;
}
for(int j=0;j<blockCount;j++)
{
block[j]=0;
}
for(int i=0;i<PageCount;i++)
{
printf("讀入Page[%d]\n",i);
CLOCK(i);
}
printf("頁面訪問次數: %d\n缺頁次數: %0.lf\n",PageCount,PageCount-lost);
printf("缺頁率為:%0.001f\n",(PageCount-lost)/PageCount);
printf("\n請輸入演算法序號:\t");
}break;
case '2':{
lost = 0;
count = 0;
for(int m = 0; m < blockCount; m++)
{
for(int n = 0; n < 2;n++)
state2[m][n] = 0;
}
for(int j = 0; j < blockCount; j++)
{
block[j] = 0;
}
for(int i = 0; i < PageCount; i++)
{
printf("讀入Page[%d]\n",i);
LCLOCK(i);
}
printf("頁面訪問次數: %d\n缺頁次數: %0.lf\n",PageCount,PageCount-lost);
printf("缺頁率為:%0.001f\n",(PageCount-lost)/PageCount);
printf("\n請輸入演算法序號:\t");
}break;
case '3':{
exit(0);
}
}
}
return 0;
}

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

#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~

『伍』 編程描述頁面置換演算法：最近最久未使用演算法

可以先寫一個結構體，包括編號和使用次數2個內容。
然後動態生成一個數組，數組元素就是結構體。

然後另外寫2個函數。一個計算中斷次數 一個進行頁面置換 。

在檢測是否中斷的時候，可以循環遍歷上面動態生成的數組。如果數組滿了且有頁面中斷的時候，才調用頁面置換的函數，否則只要把數據放入數組就可以，不用進行頁面置換。

『陸』 高分求~頁面置換演算法OPT演算法

opt演算法是1966年由Belady在理論上提出的一種演算法，其演算法實質是：系統預測作業今後要訪問的頁面，置換頁是將來不被訪問的頁面或者在最長時間後才被訪問的頁面，置換該頁不會造成剛置換出去又立即要把它調入的現象。
這是一種理想化的置換演算法，其優點是缺頁中斷率最低。它要求操作系統能知道進程「將來」頁面的使用情況，但這是不可能實現的，因為程序的執行是不可預測的。不過通過該演算法可用來模擬實驗分析或理論分析其他演算法的優劣性。

『柒』 頁面置換演算法的操作系統頁面置換演算法代碼

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h> #define TRUE 1
#define FALSE 0
#define INVALID -1
#define NUL 0
#define total_instruction 320 /*指令流長*/
#define total_vp 32 /*虛頁長*/
#define clear_period 50 /*清零周期*/
typedef struct{ /*頁面結構*/
int pn,pfn,counter,time;
}pl_type;
pl_type pl[total_vp]; /*頁面結構數組*/
struct pfc_struct{ /*頁面控制結構*/
int pn,pfn;
struct pfc_struct *next;
};
typedef struct pfc_struct pfc_type;
pfc_type pfc[total_vp],*freepf_head,*busypf_head,*busypf_tail;
int diseffect,a[total_instruction];
int page[total_instruction], offset[total_instruction];
void initialize(int);
void FIFO(int);
void LRU(int);
void NUR(int);
int main()
{
int S,i;
srand((int)getpid());
S=(int)rand()%390;
for(i=0;i<total_instruction;i+=1) /*產生指令隊列*/
{
a[i]=S; /*任選一指令訪問點*/
a[i+1]=a[i]+1; /*順序執行一條指令*/
a[i+2]=(int)rand()%390; /*執行前地址指令m』*/
a[i+3]=a[i+2]+1; /*執行後地址指令*/
S=(int)rand()%390;
}
for(i=0;i<total_instruction;i++) /*將指令序列變換成頁地址流*/
{
page[i]=a[i]/10;
offset[i]=a[i]%10;
}
for(i=4;i<=32;i++) /*用戶內存工作區從4個頁面到32個頁面*/
{
printf(%2d page frames,i);
FIFO(i);
LRU(i);
NUR(i);
printf( );
}
return 0;
}
void FIFO(int total_pf) /*FIFO(First in First out)ALGORITHM*/
/*用戶進程的內存頁面數*/
{
int i;
pfc_type *p, *t;
initialize(total_pf); /*初始化相關頁面控制用數據結構*/
busypf_head=busypf_tail=NUL; /*忙頁面隊列頭，對列尾鏈接*/
for(i=0;i<total_instruction;i++)
{
if(pl[page[i]].pfn==INVALID) /*頁面失效*/
{
diseffect+=1; /*失效次數*/
if(freepf_head==NUL) /*無空33閑頁面*/
{
p=busypf_head->next;
pl[busypf_head->pn].pfn=INVALID; /*釋放忙頁面隊列中的第一個頁面*/
freepf_head=busypf_head;
freepf_head->next=NUL;
busypf_head=p;
}
p=freepf_head->next; /*按方式調新頁面入內存頁面*/
freepf_head->next=NUL;
freepf_head->pn=page[i];
pl[page[i]].pfn=freepf_head->pfn;
if(busypf_tail==NUL)
busypf_head=busypf_tail=freepf_head;
else
{
busypf_tail->next=freepf_head;
busypf_tail=freepf_head;
}
freepf_head=p;
}
}
printf(FIFO:%6.4F,1-(float)diseffect/320);
}
void LRU(int total_pf)
{
int min,minj,i,j,present_time;
initialize(total_pf);present_time=0;
for(i=0;i<total_instruction;i++)
{
if(pl[page[i]].pfn==INVALID) /*頁面失效*/
{
diseffect++;
if(freepf_head==NUL) /*無空閑2頁面*/
{
min=32767;
for(j=0;j<total_vp;j++)
if(min>pl[j].time&&pl[j].pfn!=INVALID)
{
min=pl[j].time;
minj=j;
}
freepf_head=&pfc[pl[minj].pfn];
pl[minj].pfn=INVALID;
pl[minj].time=-1;
freepf_head->next=NUL;
}
pl[page[i]].pfn=freepf_head->pfn;
pl[page[i]].time=present_time;
freepf_head=freepf_head->next;
}
else
pl[page[i]].time=present_time;
present_time++;
}
printf(LRU:%6.4f,1-(float)diseffect/320);
}
void NUR(int total_pf)
{
int i,j,dp,cont_flag,old_dp;
pfc_type *t;
initialize(total_pf);
dp=0;
for(i=0;i<total_instruction;i++)
{
if(pl[page[i]].pfn==INVALID) /*頁面失效*/
{
diseffect++;
if(freepf_head==NUL) /*無空閑1頁面*/
{
cont_flag=TRUE;old_dp=dp;
while(cont_flag)
if(pl[dp].counter==0&&pl[dp].pfn!=INVALID)
cont_flag=FALSE;
else
{
dp++;
if(dp==total_vp)
dp=0;
if(dp==old_dp)
for(j=0;j<total_vp;j++)
pl[j].counter=0;
}
freepf_head=&pfc[pl[dp].pfn];
pl[dp].pfn=INVALID;
freepf_head->next=NUL;
}
pl[page[i]].pfn=freepf_head->pfn;
freepf_head=freepf_head->next;
}
else
pl[page[i]].counter=1;
if(i%clear_period==0)
for(j=0;j<total_vp;j++)
pl[j].counter=0;
}
printf(NUR:%6.4f,1-(float)diseffect/320);
}
void initialize(int total_pf) /*初始化相關數據結構*/
/*用戶進程的內存頁面數*/
{
int i;
diseffect=0;
for(i=0;i<total_vp;i++)
{
pl[i].pn=i;pl[i].pfn=INVALID; /*置頁面控制結構中的頁號，頁面為空*/
pl[i].counter=0;pl[i].time=-1; /*頁面控制結構中的訪問次數為0，時間為-1*/
}
for(i=1;i<total_pf;i++)
{
pfc[i-1].next=&pfc[i];pfc[i-1].pfn=i-1;/*建立pfc[i-1]和pfc[i]之間的連接*/
}
pfc[total_pf-1].next=NUL;pfc[total_pf-1].pfn=total_pf-1;
freepf_head=&pfc[0]; /*頁面隊列的頭指針為pfc[0]*/
}
/*說明：本程序在Linux的gcc下和c-free下編譯運行通過*/

『捌』 用C++語言編寫FIFO頁面置換演算法代碼

分別使用FIFO、OPT、LRU三種置換演算法來模擬頁面置換的過程。（Linux、Windows下皆可）
輸入：3//頁幀數
70120304230321201701//待處理的頁
輸出：頁面置換過程中各幀的變化過程和出現頁錯誤的次數
[cpp]
#include<iostream>
usingnamespacestd;
intinput[20]={7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1};
classpage
{
public:
intnum;
intmark;
page()
{
num=0;
mark=21;
}
};
voidFIFO()
{
cout<<"------FIFO-----------"<<endl;
interror=0;
pageframe[3];//頁幀
for(inti=0;i<3;i++)//處理前三個引用
{
frame[i].num=input[i];
error++;
cout<<frame[i].num<<"|";
for(intj=0;j<=i;j++)
cout<<frame[j].num<<'';
cout<<endl;
}
for(inti=3;i<20;i++)
{
intj;
for(j=0;j<3;j++)
if(input[i]==frame[j].num)
{
cout<<input[i]<<endl;
break;
}
if(j==3)
{
error++;
frame[((error-1)%3)].num=input[i];//換掉最舊的頁
cout<<input[i]<<"|";
for(intk=0;k<3;k++)
cout<<frame[k].num<<'';
cout<<endl;
}
}
cout<<"FrameError:"<<error<<endl<<endl;
}
voidOPT()
{
cout<<"------OPT------------"<<endl;
interror=0;
pageframe[3];
for(inti=0;i<3;i++)//處理前三個引用
{
frame[i].num=input[i];
error++;
cout<<frame[i].num<<"|";
for(intj=0;j<=i;j++)
cout<<frame[j].num<<'';
cout<<endl;
}
for(inti=3;i<20;i++)
{
intj;
for(j=0;j<3;j++)
if(input[i]==frame[j].num)
{
cout<<input[i]<<endl;
break;
}
if(j==3)
{
error++;
for(j=0;j<3;j++)
{
frame[j].mark=21;
for(intk=20;k>=i;k--)//向後遍歷，找到最長時間不用的頁
{
if(frame[j].num==input[k])
frame[j].mark=k;
}
}
if(frame[0].mark>frame[1].mark&&frame[0].mark>frame[2].mark)
frame[0].num=input[i];
elseif(frame[1].mark>frame[0].mark&&frame[1].mark>frame[2].mark)
frame[1].num=input[i];
else
frame[2].num=input[i];
cout<<input[i]<<"|";
for(intk=0;k<3;k++)
cout<<frame[k].num<<'';
cout<<endl;
}
}
cout<<"FrameError:"<<error<<endl<<endl;
}
voidLRU()
{
cout<<"------LRU------------"<<endl;
interror=0;
pageframe[3];
for(inti=0;i<3;i++)//處理前三個引用
{
frame[i].num=input[i];
error++;
cout<<frame[i].num<<"|";
for(intj=0;j<=i;j++)
cout<<frame[j].num<<'';
cout<<endl;
}
for(inti=3;i<20;i++)
{
intj;
for(j=0;j<3;j++)
if(input[i]==frame[j].num)
{
cout<<input[i]<<endl;
break;
}
if(j==3)
{
error++;
for(j=0;j<3;j++)
{
frame[j].mark=0;
for(intk=0;k<=i;k++)//向前遍歷，找到最近最少使用的
{
if(frame[j].num==input[k])
frame[j].mark=k;
}
}
if(frame[0].mark<frame[1].mark&&frame[0].mark<frame[2].mark)
frame[0].num=input[i];
elseif(frame[1].mark<frame[0].mark&&frame[1].mark<frame[2].mark)
frame[1].num=input[i];
else
frame[2].num=input[i];
cout<<input[i]<<"|";
for(intk=0;k<3;k++)
cout<<frame[k].num<<'';
cout<<endl;
}
}
cout<<"FrameError:"<<error<<endl<<endl;
}
intmain()
{
FIFO();
OPT();
LRU();
}