請(qǐng)求頁(yè)式存儲(chǔ)管理

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

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

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

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

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

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

7、經(jīng)做過(guò)這個(gè)實(shí)驗(yàn)，所以有了一定的了解，加上一點(diǎn)修改就能夠使用了。所以沒(méi)太花功夫。七、實(shí)驗(yàn)總結(jié)七、實(shí)驗(yàn)總結(jié)通過(guò)實(shí)現(xiàn)請(qǐng)求頁(yè)式存儲(chǔ)管理的幾種基本頁(yè)面置換算法，了解了虛擬存儲(chǔ)技術(shù)的特點(diǎn)。通過(guò)對(duì)頁(yè)面、頁(yè)表、地址轉(zhuǎn)換和頁(yè)面置換過(guò)程的模擬，加深對(duì)請(qǐng)求調(diào)頁(yè)系統(tǒng)的原理和實(shí)現(xiàn)過(guò)程的理解，也知道了幾種算法的效率，也驗(yàn)證了 LRU算法的命中率平均的比 FIFO 算法要高。通過(guò)本次實(shí)驗(yàn)，我收獲了很多。我了解到編寫程序不是首要任務(wù)，而是一種實(shí)現(xiàn)手段。我們最重要的是如何做好需求分析和理清思路，做出正確、簡(jiǎn)介的流程設(shè)計(jì)，這樣可以達(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; /*頁(yè)表映像*/typedef struct page int address; /*頁(yè)面地址*/ 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);/*選擇頁(yè)面置換算法*/ jccreat(); /*創(chuàng)建進(jìn)程*/ if(choice=1) /*采用 OPT 算法置換*/ percent=OPT(); /*計(jì)