請求頁式存儲管理

1、軟軟 件件 學(xué)學(xué) 院院操作系統(tǒng)實驗報告操作系統(tǒng)實驗報告 專專 業(yè)：業(yè)： 軟件工程軟件工程 班班 級：級： RB 軟工互軟工互 152 學(xué)學(xué) 號：號： 201560160226 學(xué)生姓名：學(xué)生姓名： 王澤華王澤華 指導(dǎo)教師：指導(dǎo)教師： 韓新超韓新超 實驗四：實驗四：請求頁式存儲管理一實驗?zāi)康囊粚嶒災(zāi)康纳钊肜斫庹埱箜撌酱鎯芾淼脑?，重點(diǎn)認(rèn)識其中的地址變換、缺頁中斷、置換算法等實現(xiàn)思想。二實驗屬性二實驗屬性該實驗為綜合性、設(shè)計性實驗。三實驗儀器設(shè)備及器材三實驗儀器設(shè)備及器材普通 PC386 以上微機(jī)四實驗要求四實驗要求本實驗要求 4 學(xué)時完成。本實驗要求完成如下任務(wù)：（1） 建立相關(guān)的數(shù)據(jù)結(jié)構(gòu)：存

2、儲塊表、頁表等；（2） 實現(xiàn)基本分頁存儲管理，如分配、回收、地址變換；（3） 在基本分頁的基礎(chǔ)上實現(xiàn)請求分頁存儲管理；（4） 給定一批作業(yè)/進(jìn)程，選擇一個分配或回收模擬；（5） 將整個過程可視化顯示出來。實驗前應(yīng)復(fù)習(xí)實驗中所涉及的理論知識和算法，針對實驗要求完成基本代碼編寫并完成預(yù)習(xí)報告、實驗中認(rèn)真調(diào)試所編代碼并進(jìn)行必要的測試、記錄并分析實驗結(jié)果。實驗后認(rèn)真書寫符合規(guī)范格式的實驗報告（參見附錄 A） ，并要求用正規(guī)的實驗報告紙和封面裝訂整齊，按時上交。五、實驗提示五、實驗提示1、本實驗雖然不以前面實驗為基礎(chǔ)，但建議在其界面中繼續(xù)增加請求頁式存儲管理功能。2、數(shù)據(jù)結(jié)構(gòu)：內(nèi)存分配表、頁表空間（用數(shù)

3、組實現(xiàn)） ，修改 PCB 結(jié)構(gòu)增加頁表指針、頁表長度。3、存儲管理：編寫內(nèi)存分配、內(nèi)存回收算法、頁面置換算法。4、主界面設(shè)計：在界面上增加一個請求分頁內(nèi)存分配按鈕、請求分頁內(nèi)存回收按鈕、裝入指定進(jìn)程的指定頁按鈕。觸發(fā)請求分頁內(nèi)存分配按鈕，彈出作業(yè)大小輸入框，輸入后調(diào)用內(nèi)存分配函數(shù)，在內(nèi)存分配表和頁表中看到分配的存儲塊。觸發(fā)請求分頁內(nèi)存回收按鈕，彈出進(jìn)程 ID 輸入框，輸入后調(diào)用內(nèi)存回收函數(shù)，在內(nèi)存分配表中看到回收后的狀態(tài)改變。5、功能測試：從顯示出的內(nèi)存分配表和頁表，可查看操作的正確與否。六、實驗步驟六、實驗步驟（1）任務(wù)分析：1.最佳頁面置換算法（OPT）：其所選擇的被淘汰頁面，將是以后永不

4、使用的或許是在最長(未來)時間內(nèi)不再被訪問的頁面。采用最佳置換算法，通常可保證獲得最低的缺頁率。2.最近最久未使用（LRU）算法：當(dāng)需要置換一頁時，選擇在最近一段時間里最久沒有使用過的頁面予以置換。（2）程序設(shè)計：程序功能模塊圖如下： （1）在同一進(jìn)程中的各個線程，都可以共享該進(jìn)程所擁有的資源，這表現(xiàn)在：所有線程都具有相同的地址空間（進(jìn)程的地址空間） 。此外我們應(yīng)該還要用控制語句，控制線程的同步執(zhí)行。 2. 這個實驗是要求我們采用算法模擬分頁存儲管理技術(shù)的 FIFO 和 LRU 算法。所以我們 應(yīng)該先生成地址序列，有了地址序列，我們要找到它所在的虛頁，然后通過查找實頁，再判斷下一步動作。假如要

5、訪問的虛頁不在內(nèi)存中，不命中，我們要替換實頁內(nèi)容。根據(jù) FIFO 算法，直接替換最早進(jìn)入內(nèi)存中的那一頁就可以了。所以可以設(shè)立一個循環(huán)指針，記錄那個最早進(jìn)入內(nèi)存中的那頁。而對于 LRU 算法，我們要替換是到現(xiàn)在為止最長時間沒被訪問的頁，在這里我們可以用一個隊列來表示內(nèi)存。把最久沒使用的頁放在隊頭，然后替換進(jìn)去的頁放在隊尾就可以了。假如要訪問的虛頁在內(nèi)存中，明顯是命中。對于 FIFO 算法，不處理，而對于 LRU 算法，我們還要把他的權(quán)值置 0。（2）系統(tǒng)功能流程圖： N N Y Y請求分頁式儲存管理最近最久未使用算法先進(jìn)先出算法開始還有指令？開始還有指令？ Y Y N N（3）算法分析1.先進(jìn)先

6、出 定義一個隊列存放頁面，頭指針記錄最先進(jìn)入隊列的頁面的位置，每次替換頭指針指向的頁面。2.最近最少使用 定義一個二維數(shù)組，一維用來記錄頁面號，一維用來記錄該頁面被使用的次數(shù)，每次替換最近最少使用的頁面（3）程序結(jié)果：在運(yùn)行界面選擇某個算法，運(yùn)行結(jié)果，如圖 1，圖 2 所示：圖 1新頁進(jìn)入計算過程數(shù)組第一 位，其余為一次下移找到了嗎？計算頁號計算命中率結(jié)束計算頁號找到了嗎？比較現(xiàn)有頁面計數(shù)項的大小，新頁面替換最大項頁面計算命中率結(jié)束 圖 2（3） 調(diào)試與測試：1.第一道涉及線程的題編譯時總是發(fā)生錯誤，原來編譯這類程序在原有的編譯語言后要加上-pthread.2.第二個分頁算法我們在系統(tǒng)結(jié)構(gòu)課已

7、經(jīng)做過這個實驗，所以有了一定的了解，加上一點(diǎn)修改就能夠使用了。所以沒太花功夫。七、實驗總結(jié)七、實驗總結(jié)通過實現(xiàn)請求頁式存儲管理的幾種基本頁面置換算法，了解了虛擬存儲技術(shù)的特點(diǎn)。通過對頁面、頁表、地址轉(zhuǎn)換和頁面置換過程的模擬，加深對請求調(diào)頁系統(tǒng)的原理和實現(xiàn)過程的理解，也知道了幾種算法的效率，也驗證了 LRU算法的命中率平均的比 FIFO 算法要高。通過本次實驗，我收獲了很多。我了解到編寫程序不是首要任務(wù)，而是一種實現(xiàn)手段。我們最重要的是如何做好需求分析和理清思路，做出正確、簡介的流程設(shè)計，這樣可以達(dá)到事半功倍的效果。八、附錄八、附錄/# include /# include #includest

8、dio.h#include#include #define N 16#define num 5 /*進(jìn)程分配物理塊數(shù)目*/int AN=1,2,3,4,5,6,7,8,5,2,3,2,7,8,1,4; /*頁表映像*/typedef struct page int address; /*頁面地址*/ struct page *next; page;struct page *head,*run,*rear;void jccreat() /*進(jìn)程分配物理塊*/ int i=1; page *p,*q; head=(page *)malloc(sizeof(page); p=head; for(i=

9、1;inext=q; q-address=0; q-next=NULL; p=q; rear=p;int search(int n) page *p; int i=0; p=head; while(p-next) if(p-next-address=n) printf(Get it at the page %dn,i+1); run=p; return 1; p=p-next; i+; return 0;void changeOPT(int n,int position) int i; int total=0; int flag=1; int distancenum; int MAX; int

10、 order=0; page *p,*q; p=head-next; q=head-next; for(i=0;iaddress=0) flag=0; break; p=p-next; i+; if(!flag) p-address=n; printf(Change the page %dn,i+1); else while(q) for(i=position;iaddress=Ai) distancetotal=i-position; total+; q=q-next; MAX=distance0; for(i=0;iMAX) MAX=distancei; order=i; printf(C

11、hange the page %dn,order+1); i=0; while(p) if(i=order) p-address=n; i+; p=p-next; void changeLRU(int n) int i=0; int flag=1; page *p,*delect; p=head-next; while(p) if(p-address=0) flag=0; p-address=n; printf(Change the page %dn,i+1); break; p=p-next; i+; if(flag) delect=head-next; head-next=delect-n

12、ext; printf(Delect from the head, and add new to the end.n); delect-address=n; rear-next=delect; rear=delect; rear-next=NULL; float OPT() int i; int lose=0; float losef; float percent; for(i=0;iN;i+) if(search(Ai)=0) lose+; changeOPT(Ai,i); losef=lose; percent=1-(losef/N); return percent;float LRU()

13、 int i; int lose=0; float losef; float percent; page *p; for(i=0;inext; run-next=p-next; rear-next=p; rear=p; rear-next=NULL; printf(Move it to end of queue.n); losef=lose; percent=1-(losef/N); return percent; main() /*主函數(shù)部分*/float percent; int choice; printf(Select the arithmetic:n(1)OPTn(2)LRUnyour choice is:); scanf(%d,&choice);/*選擇頁面置換算法*/ jccreat(); /*創(chuàng)建進(jìn)程*/ if(choice=1) /*采用 OPT 算法置換*/ percent=OPT(); /*計