請求頁式存儲管理

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

2、（5） 將整個(gè)過程可視化顯示出來。實(shí)驗(yàn)前應(yīng)復(fù)習(xí)實(shí)驗(yàn)中所涉及的理論知識和算法，針對實(shí)驗(yàn)要求完成基本代碼編寫并完成預(yù)習(xí)報(bào)告、 實(shí)驗(yàn)中認(rèn)真調(diào)試所編代碼并進(jìn)行必要的測試、記錄并分析實(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)提示1、本實(shí)驗(yàn)雖然不以前面實(shí)驗(yàn)為基礎(chǔ)，但建議在其界面中繼續(xù)增加請求頁式存儲管理功能。2、數(shù)據(jù)結(jié)構(gòu)：內(nèi)存分配表、頁表空間（用數(shù)組實(shí)現(xiàn)） ，修改 PCB 結(jié)構(gòu)增加頁表指針、頁表長度。3、存儲管理：編寫內(nèi)存分配、內(nèi)存回收算法、頁面置換算法。4、主界面設(shè)計(jì)：在界面上增加一個(gè)請求分頁內(nèi)存分配按鈕、請求分頁內(nèi)存回收按

3、鈕、裝入指定進(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)存分配表和頁表，可查看操作的正確與否。六、實(shí)驗(yàn)步驟（ 1） 任務(wù)分析 ：;.1.最佳頁面置換算法（ OPT）：其所選擇的被淘汰頁面，將是以后永不使用的或許是在最長 (未來 )時(shí)間內(nèi)不再被訪問的頁面。采用最佳置換算法，通?？杀ＷC獲得最低的缺頁率。2.最近最久未使用（ LRU ）算法：當(dāng)需要置換一頁時(shí)，選擇在最近一段時(shí)間里最

4、久沒有使用過的頁面予以置換。（ 2） 程序設(shè)計(jì)：程序功能模塊圖如下：請求分頁式儲存管理最 近先最 久進(jìn)未 使先用 算出法算法（1）在同一進(jìn)程中的各個(gè)線程，都可以共享該進(jìn)程所擁有的資源，這表現(xiàn)在：所有線程都具有相同的地址空間（進(jìn)程的地址空間） 。此外我們應(yīng)該還要用控制語句，控制線程的同步執(zhí)行。 2. 這個(gè)實(shí)驗(yàn)是要求我們采用算法模擬分頁存儲管理技術(shù)的 FIFO 和 LRU 算法。所以我們 應(yīng)該先生成地址序列，有了地址序列，我們要找到它所在的虛頁，然后通過查找實(shí)頁，再判斷下一步動(dòng)作。假如要訪問的虛頁不在內(nèi)存中，不命中，我們要替換實(shí)頁內(nèi)容。根據(jù) FIFO 算法，直接替換最早進(jìn)入內(nèi)存中的那一頁就可以了。

5、 所以可以設(shè)立一個(gè)循環(huán)指針， 記錄那個(gè)最早進(jìn)入內(nèi)存中的那頁。而對于 LRU 算法，我們要替換是到現(xiàn)在為止最長時(shí)間沒被訪問的頁， 在這里我們可以用一個(gè)隊(duì)列來表示內(nèi)存。 把最久沒使用的頁放在隊(duì)頭，然后替換進(jìn)去的頁放在隊(duì)尾就可以了。 假如要訪問的虛頁在內(nèi)存中， 明顯是命中。對于 FIFO 算法，不處理，而對于 LRU 算法，我們還要把他的權(quán)值置 0。（2）系統(tǒng)功能流程圖：開始開始NN還有指令？還有指令？YY計(jì)算頁號計(jì)算頁號;.找到Y(jié)了嗎？YNN新頁進(jìn)入計(jì)算過程數(shù)組第一 位，其余為一次下移計(jì)算命中率找到了嗎？比較現(xiàn)有頁面計(jì)數(shù)項(xiàng)的大小，新頁面替換最大項(xiàng)頁面計(jì)算命中率結(jié)束結(jié)束（3）算法分析1.先進(jìn)先出 定

6、義一個(gè)隊(duì)列存放頁面，頭指針記錄最先進(jìn)入隊(duì)列的頁面的位置，每次替換頭指針指向的頁面。2.最近最少使用 定義一個(gè)二維數(shù)組，一維用來記錄頁面號，一維用來記錄該頁面被使用的次數(shù)，每次替換最近最少使用的頁面（3）程序結(jié)果： 在運(yùn)行界面選擇某個(gè)算法，運(yùn)行結(jié)果，如圖1，圖 2 所示：圖 1;.圖 2（ 3） 調(diào)試與測試：1.第一道涉及線程的題編譯時(shí)總是發(fā)生錯(cuò)誤，原來編譯這類程序在原有的編譯語言后要加上 -pthread.2.第二個(gè)分頁算法我們在系統(tǒng)結(jié)構(gòu)課已經(jīng)做過這個(gè)實(shí)驗(yàn)，所以有了一定的了解，加上一點(diǎn)修改就能夠使用了。所以沒太花功夫。七、實(shí)驗(yàn)總結(jié)通過實(shí)現(xiàn)請求頁式存儲管理的幾種基本頁面置換算法， 了解了虛擬存儲

7、技術(shù)的特點(diǎn)。通過對頁面、頁表、地址轉(zhuǎn)換和頁面置換過程的模擬，加深對請求調(diào)頁系統(tǒng)的原理和實(shí)現(xiàn)過程的理解， 也知道了幾種算法的效率， 也驗(yàn)證了 LRU算法的命中率平均的比 FIFO 算法要高。通過本次實(shí)驗(yàn)， 我收獲了很多。 我了解到編寫程序不是首要任務(wù)， 而是一種實(shí)現(xiàn)手段。我們最重要的是如何做好需求分析和理清思路， 做出正確、簡介的流程設(shè)計(jì)，這樣可以達(dá)到事半功倍的效果。八、附錄/# include <windows.h>/# include <iostream>#include"stdio.h"#include<conio.h>#includ

8、e <malloc.h>#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 pageint 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=1;i&l

9、t;=num;i+) q=(page *)malloc(sizeof(page);p->next=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 pos

10、ition)int i;int total=0;int flag=1;int distancenum;.int MAX;int order=0;page *p,*q;p=head->next;q=head->next;for(i=0;i<num;i+)distancei=100;i=0;while(p)if(p->address=0)flag=0;break;p=p->next;i+;if(!flag)p->address=n;printf("Change the page %dn",i+1);elsewhile(q)for(i=posi

11、tion;i<N;i+)if(q->address=Ai)distancetotal=i-position;total+;q=q->next;MAX=distance0;for(i=0;i<num;i+);.if(distancei>MAX)MAX=distancei;order=i;printf("Change 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

12、;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->next;printf("Delect from the head, and add new to the end.n");delect->address=n;re

13、ar->next=delect;rear=delect;rear->next=NULL;float OPT()int i;int lose=0;float losef;float percent;for(i=0;i<N;i+)if(search(Ai)=0)lose+;changeOPT(Ai,i);losef=lose;percent=1-(losef/N);return percent;float LRU()int i;int lose=0;float losef;.float percent;page *p;for(i=0;i<N;i+)if(search(Ai)

14、=0)lose+;changeLRU(Ai);elsep=run->next;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();/* 計(jì)算 OPT 時(shí)的缺頁率 */prin