利用C語言實(shí)現(xiàn)頁面置換算法的詳細(xì)過程
操作系統(tǒng)實(shí)驗(yàn)
頁面置換算法(FIFO、LRU、OPT)
概念:
1.最佳置換算法(OPT)(理想置換算法):從主存中移出永遠(yuǎn)不再需要的頁面;如無這樣的頁面存在,則選擇最長(zhǎng)時(shí)間不需要訪問的頁面。于所選擇的被淘汰頁面將是以后永不使用的,或者是在最長(zhǎng)時(shí)間內(nèi)不再被訪問的頁面,這樣可以保證獲得最低的缺頁率。
2.先進(jìn)先出置換算法(FIFO):是最簡(jiǎn)單的頁面置換算法。這種算法的基本思想是:當(dāng)需要淘汰一個(gè)頁面時(shí),總是選擇駐留主存時(shí)間最長(zhǎng)的頁面進(jìn)行淘汰,即先進(jìn)入主存的頁面先淘汰。其理由是:最早調(diào)入主存的頁面不再被使用的可能性最大。
3.最近最久未使用(LRU)算法:這種算法的基本思想是:利用局部性原理,根據(jù)一個(gè)作業(yè)在執(zhí)行過程中過去的頁面訪問歷史來推測(cè)未來的行為。它認(rèn)為過去一段時(shí)間里不曾被訪問過的頁面,在最近的將來可能也不會(huì)再被訪問。所以,這種算法的實(shí)質(zhì)是:當(dāng)需要淘汰一個(gè)頁面時(shí),總是選擇在最近一段時(shí)間內(nèi)最久不用的頁面予以淘汰。
題目:
編寫一個(gè)程序,實(shí)現(xiàn)本章所述的FIFO、LRU和最優(yōu)頁面置換算法。首先,生成一個(gè)隨機(jī)的頁面引用串,其中頁碼范圍為0-9.將這個(gè)隨機(jī)頁面引用串應(yīng)用到每個(gè)算法,并記錄每個(gè)算法引起的缺頁錯(cuò)誤的數(shù)量。實(shí)現(xiàn)置換算法,一遍頁面幀的數(shù)量可以從1~7。
代碼
#include <stdio.h> #include <stdlib.h> #include <time.h> int numbers[20]={7,0,1,2, 0,3,0,4, 2,3,0,3, 2,1,2,0, 1,7,0,1};//本地?cái)?shù)據(jù),與課本一致,方便測(cè)試 int nums=0;//輸入棧的個(gè)數(shù),為了方便使用, int stack[20][7]={10}; void begin(); void randomnum();//用于產(chǎn)生隨機(jī)數(shù) void init();//初始化 void FIFO();//FIFO算法 void LRU();//LRU算法 void OPT();//最優(yōu)頁面置換算法(OPT) void print();//輸出 int main() { begin(); FIFO(); LRU(); OPT(); return 0; } void begin()//開始菜單界面 { int i,j,k; printf("請(qǐng)輸入頁面幀的數(shù)量(1-7):"); scanf("%d",&nums); for(k=0;;k++) { printf("是否使用隨機(jī)數(shù)產(chǎn)生輸入串(0:是,1:否)"); scanf("%d",&j); if(j==0) { randomnum(); break; } else if(j==1) { break; } else { printf("請(qǐng)輸入正確的選擇!\n"); } } printf("頁面引用串為:\n"); for(i=0;i<20;i++) { printf("%d ",numbers[i]); } printf("\n"); init(); } void randomnum()//如果需要使用隨機(jī)數(shù)生成輸入串,調(diào)用該函數(shù) { srand(time(0));//設(shè)置時(shí)間種子 for(int i = 0; i < 20; i++) { numbers[i] = rand() % 10;//生成區(qū)間0`9的隨機(jī)頁面引用串 } } void init()//用于每次初始化頁面棧中內(nèi)容,同時(shí)方便下面輸出的處理 { int i,j; for(i=0;i<20;i++) for(j=0;j<nums;j++) stack[i][j]=10; } void print()//輸出各個(gè)算法的棧的內(nèi)容 { int i,j; for(i=0;i<nums;i++) { for(j=0;j<20;j++) { if(stack[j][i]==10) printf("* "); else printf("%d ",stack[j][i]); } printf("\n"); } } void FIFO()//FIFO算法 { init(); int i,j=1,n=20,k,f,m; stack[0][0]=numbers[0]; for(i=1;i<20;i++) { f=0; for(m=0;m<nums;m++) { stack[i][m]=stack[i-1][m]; } for(k=0;k<nums;k++) { if(stack[i][k]==numbers[i]) { n--; f=1; break; } } if(f==0) { stack[i][j]=numbers[i]; j++; } if(j==nums) j=0; } printf("\n"); printf("FIFO算法:\n"); print(); printf("缺頁錯(cuò)誤數(shù)目為:%d\n",n); } void LRU()//LRU算法 { int i,j,m,k,sum=1,f; int sequence[7]={0};//記錄序列 init(); stack[0][0]=numbers[0]; sequence[0]=nums; for(i=1;i<nums;i++)//前半部分,頁面空置的情況 { for(j=0;j<nums;j++) { stack[i][j]=stack[i-1][j]; } for(j=0;j<nums;j++) //判斷要插入的是否在棧中已經(jīng)存在 { f=0; if(stack[i][j]==numbers[i]) { f=1; sum--; sequence[j]=nums; break; } } for(j=0;j<nums;j++) { if(sequence[j]==0&&f==0) { stack[i][j]=numbers[i]; sequence[i]=nums;//最近使用的優(yōu)先級(jí)列為最高 break; } } for(j=0;j<i;j++)//將之前的優(yōu)先級(jí)序列都減1 { if(sequence[j]!=0) sequence[j]--; } //sequence[i]=nums; sum++; } for(i=nums;i<20;i++)//頁面不空,需要替換的情況 { int f; f=0; for(j=0;j<nums;j++) { stack[i][j]=stack[i-1][j]; } for(j=0;j<nums;j++)//判斷輸入串中的數(shù)字,是否已經(jīng)在棧中 { if(stack[i][j]==numbers[i]) { f=1; k=j; break; } } if(f==0)//如果頁面棧中沒有,不相同 { for(j=0;j<nums;j++)//找優(yōu)先序列中為0的 { if(sequence[j]==0) { m=j; break; } } for(j=0;j<nums;j++) { sequence[j]--; } sequence[m]=nums-1; stack[i][m]=numbers[i]; sum++; } else//如果頁面棧中有,替換優(yōu)先級(jí) { if(sequence[k]==0)//優(yōu)先級(jí)為最小優(yōu)先序列的 { for(j=0;j<nums;j++) { sequence[j]--; } sequence[k]=nums-1; } else if(sequence[k]==nums-1)//優(yōu)先級(jí)為最大優(yōu)先序列的 { //無需操作 } else//優(yōu)先級(jí)為中間優(yōu)先序列的 { for(j=0;j<nums;j++) { if(sequence[k]<sequence[j]) { sequence[j]--; } } sequence[k]=nums-1; } } } printf("\n"); printf("LRU算法:\n"); print(); printf("缺頁錯(cuò)誤數(shù)目為:%d\n",sum); } void OPT()//OPT算法 { int i,j,k,sum=1,f,q,max; int seq[7]={0};//記錄序列 init(); stack[0][0]=numbers[0]; seq[0]=nums-1; for(i=1;i<nums;i++)//前半部分,頁面空置的情況 { for(j=0;j<nums;j++) { stack[i][j]=stack[i-1][j]; } for(j=0;j<nums;j++) //判斷要插入的是否在棧中已經(jīng)存在 { f=0; if(stack[i][j]==numbers[i]) { f=1; sum--; //b++; seq[j]=nums; break; } } for(j=0;j<nums;j++) { if(seq[j]==0&&f==0) { stack[i][j]=numbers[i]; seq[j]=nums;//最近使用的優(yōu)先級(jí)列為最高 break; } // else if(seq[j]==0&&f==1){ // b++; // sum--; // seq[j]=nums-1; // break; // } } for(j=0;j<nums;j++)//將之前的優(yōu)先級(jí)序列都減1 { if(seq[j]!=0) seq[j]--; } sum++; } for(i=nums;i<20;i++)//后半部分,頁面棧中沒有空的時(shí)候情況 { //k=nums-1;//最近的數(shù)字的優(yōu)先級(jí) for(j=0;j<nums;j++)//前面的頁面中內(nèi)容賦值到新的新的頁面中 { stack[i][j]=stack[i-1][j]; } for(j=0;j<nums;j++) { f=0; if(stack[i][j]==numbers[i]) { f=1; break; } } if(f==0)//頁面中沒有,需要替換的情況 { for(q=0;q<nums;q++)//優(yōu)先級(jí)序列中最大的就是最久不會(huì)用的,有可能出現(xiàn)后面沒有在用過的情況 { seq[q]=20; } for(j=0;j<nums;j++)//尋找新的優(yōu)先級(jí) { for(q=i+1;q<20;q++) { if(stack[i][j]==numbers[q]) { seq[j]=q-i; break; } } } max=seq[0]; k=0; for(q=0;q<nums;q++) { if(seq[q]>max) { max=seq[q]; k=q; } } stack[i][k]=numbers[i]; sum++; } else { //頁面棧中有需要插入的數(shù)字,無需變化,替換的優(yōu)先級(jí)也不需要變化 } } printf("\n"); printf("OPT算法:\n"); print(); printf("缺頁錯(cuò)誤數(shù)目為:%d\n",sum); }
運(yùn)行結(jié)果截圖:
總結(jié)
設(shè)置多個(gè)數(shù)組,一個(gè)用來模仿棧,一個(gè)用來存要存取的頁面,還有在OPT算法和LRU算法中,記錄棧中每個(gè)數(shù)據(jù)的替換優(yōu)先級(jí)。
之前的代碼寫的有點(diǎn)爛,重新看了一次才感覺之前的有多爛,哈哈哈哈哈,這個(gè)代碼能在linux上跑通的,在windows上肯定也沒得問題
相關(guān)文章
C語言中如何在結(jié)構(gòu)體內(nèi)定義函數(shù)
這篇文章主要介紹了C語言中如何在結(jié)構(gòu)體內(nèi)定義函數(shù)問題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2023-02-02C語言實(shí)現(xiàn)2048游戲(ege圖形庫版)
這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)2048游戲,ege圖形庫版,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2018-12-12C++實(shí)現(xiàn)正整數(shù)的四則運(yùn)算表達(dá)式
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)正整數(shù)的四則運(yùn)算表達(dá)式,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2020-06-06C++使用HTTP庫和框架輕松發(fā)送HTTP請(qǐng)求
使用C++編程發(fā)送HTTP請(qǐng)求通常需要使用第三方的HTTP庫或框架,本文主要介紹了C++使用HTTP庫和框架輕松發(fā)送HTTP請(qǐng)求,感興趣的可以了解一下2023-12-12c++和python實(shí)現(xiàn)順序查找實(shí)例
這篇文章主要介紹了c++和python實(shí)現(xiàn)順序查找實(shí)例,流程即將目標(biāo)數(shù)值和數(shù)據(jù)庫中的每個(gè)數(shù)值進(jìn)行比較,如果相同則搜索完成,如果不同則繼續(xù)比較下一處,下面來看看具體的實(shí)例操作吧,需要的朋友可以參考一下2022-03-03