OS實(shí)驗(yàn)指導(dǎo)三——存儲(chǔ)器管理

1、OS實(shí)驗(yàn)指導(dǎo)三 操作系統(tǒng)實(shí)驗(yàn)指導(dǎo)三 實(shí)驗(yàn)項(xiàng)目（三）基本存儲(chǔ)器管理實(shí)驗(yàn)實(shí)驗(yàn)類型設(shè)計(jì)實(shí)驗(yàn)學(xué)時(shí)4一、實(shí)驗(yàn)?zāi)康睦斫夥謪^(qū)式存儲(chǔ)管理的基本原理，熟悉分區(qū)分配和回收算法。即理解在不同的存儲(chǔ)管理方式下，如何實(shí)現(xiàn)主存空間的分配與回收；并掌握動(dòng)態(tài)分區(qū)分配方式中的數(shù)據(jù)結(jié)構(gòu)和分配算法及動(dòng)態(tài)分區(qū)存儲(chǔ)管理方式及其實(shí)現(xiàn)過程。二、設(shè)備與環(huán)境 1. 硬件設(shè)備：PC機(jī)一臺(tái)2. 軟件環(huán)境：安裝Windows操作系統(tǒng)或者Linux操作系統(tǒng)，并安裝相關(guān)的程序開發(fā)環(huán)境，如VC VC+Java 等編程語言環(huán)境。三、實(shí)驗(yàn)原理實(shí)驗(yàn)要求使用可變分區(qū)存儲(chǔ)管理方式，分區(qū)分配中所用的數(shù)據(jù)結(jié)構(gòu)采用空閑分區(qū)表和空閑分區(qū)鏈來進(jìn)行，分區(qū)分配中所用的算法采用首

2、次適應(yīng)算法、最佳適應(yīng)算法、最差適應(yīng)算法三種算法來實(shí)現(xiàn)主存的分配與回收。同時(shí)，要求設(shè)計(jì)一個(gè)實(shí)用友好的用戶界面，并顯示分配與回收的過程。同時(shí)要求設(shè)計(jì)一個(gè)實(shí)用友好的用戶界面,并顯示分配與回收的過程。A、主存空間分配 （1）首次適應(yīng)算法算法要求空閑分區(qū)表以地址遞增的次序排列。在分配內(nèi)存時(shí)，從表首開始順序查找，直至找到一個(gè)大小能滿足要求的空閑分區(qū)為止；然后按照作業(yè)的大小，從該分區(qū)中劃出一塊內(nèi)存空間分配給請(qǐng)求者，余下的空閑分區(qū)仍留在空閑分區(qū)表中。若從頭到尾不存在滿足要求的分區(qū)，則分配失敗。（2）最佳適應(yīng)算法所謂“最佳”是指每次為作業(yè)分配內(nèi)存時(shí)，總是把能滿足要求、又是最小的空閑分區(qū)分配給作業(yè)，避免“大材小用

3、”。要求將所有的空閑分區(qū)按其容量以從小到大的順序形成一空閑分區(qū)鏈。（3）最壞適應(yīng)算法最壞適應(yīng)分配算法要掃描整個(gè)空閑分區(qū)表或鏈表，總是挑選一個(gè)最大的空閑區(qū)分割給作業(yè)使用。該算法要求將所有的空閑分區(qū)按其容量以從大到小的順序形成一空閑分區(qū)鏈，查找時(shí)只要看第一個(gè)分區(qū)能否滿足作業(yè)要求。 B、主存空間回收當(dāng)一個(gè)作業(yè)執(zhí)行完成撤離時(shí)，作業(yè)所占的分區(qū)應(yīng)該歸還給系統(tǒng)。歸還的分區(qū)如果與其它空閑區(qū)相鄰，則應(yīng)合成一個(gè)較大的空閑區(qū)，登記在空閑區(qū)說明鏈中，此時(shí)，相鄰空閑區(qū)的合并問題，要求考慮四種情況：a) 釋放區(qū)下鄰空閑區(qū)（低地址鄰接）b) 釋放區(qū)上鄰空閑區(qū)（高地址鄰接）c) 釋放區(qū)上下都與空閑區(qū)鄰接d) 釋放區(qū)上下鄰都與

4、空閑區(qū)不鄰接四、實(shí)驗(yàn)要求1. 模擬操作系統(tǒng)的主存分配，運(yùn)用可變分區(qū)的存儲(chǔ)管理算法設(shè)計(jì)主存分配和回收程序，并不實(shí)際啟動(dòng)裝入作業(yè)。2. 采用首次適應(yīng)法、最佳適應(yīng)法、最壞適應(yīng)法分配主存空間。3. 當(dāng)一個(gè)新作業(yè)要求裝入主存時(shí)，必須查空閑區(qū)表，從中找出一個(gè)足夠大的空閑區(qū)。若找到的空閑區(qū)大于作業(yè)需要量，這是應(yīng)把它分成二部分，一部分為占用區(qū)，加一部分又成為一個(gè)空閑區(qū)。4. 當(dāng)一個(gè)作業(yè)撤離時(shí)，歸還的區(qū)域如果與其他空閑區(qū)相鄰，則應(yīng)合并成一個(gè)較大的空閑區(qū)，登在空閑區(qū)表中。5. 運(yùn)行所設(shè)計(jì)的程序，輸出有關(guān)數(shù)據(jù)結(jié)構(gòu)表項(xiàng)的變化和內(nèi)存的當(dāng)前狀態(tài)。五、實(shí)驗(yàn)設(shè)計(jì)參考1.算法流圖l main函數(shù)的流程圖初始化first和end

5、整理分區(qū)序號(hào)顯示空閑分區(qū)鏈選擇算法aa=1，首次適應(yīng)算法a=2，最佳適應(yīng)算法a=3，最壞適應(yīng)算法選擇操作ii=1，分配空間函數(shù)ai=0，退出程序i=2，回收空間函數(shù)結(jié)束l 分配空間的流程圖分配空間函數(shù)a=1a=2a=3輸入申請(qǐng)內(nèi)存大小按順序找空閑塊初始化q，使它指向空閑塊中長(zhǎng)度小的一塊輸入申請(qǐng)內(nèi)存大小初始化q，使它指向空閑塊中長(zhǎng)度大的一塊p-data.length=requestp的狀態(tài)為已分配剩下p-data.length-=request輸入申請(qǐng)內(nèi)存大小YYNN返回到整理分區(qū)序號(hào)p-data.lengthrequest分配不成功l 回收空間的流程圖p的狀態(tài)改為空閑回收p，p的前一個(gè)為fir

6、stp的后一個(gè)是endp的后一個(gè)狀態(tài)空與后面空閑塊相連將p 的狀態(tài)改為空閑將p 的狀態(tài)改為空閑回收空間函數(shù)p的后一個(gè)是endYNYNYNp的前一個(gè)狀態(tài)空p的前一個(gè)狀態(tài)空p的后一個(gè)狀態(tài)空p的后一個(gè)狀態(tài)空p的后一個(gè)狀態(tài)空p的后一個(gè)狀態(tài)空YYYNNN與前面空閑塊相連p的狀態(tài)改為空閑與前面空閑塊相連與后面空閑塊相連YN返回到整理分區(qū)序號(hào)2. 相關(guān)數(shù)據(jù)結(jié)構(gòu)及關(guān)鍵函數(shù)說明 使用了struct free_table數(shù)據(jù)結(jié)構(gòu)用來說明分區(qū)。包含：分區(qū)序號(hào)（num）、起始地址（address）、分區(qū)長(zhǎng)度（length）和分區(qū)狀態(tài)（state）。 使用了線性表的雙向鏈表存儲(chǔ)結(jié)構(gòu)（struct Node），里面包含前

7、驅(qū)指針（prior）和后繼指針（next）。一開始定義一條（含有first和end）的鏈，用開始指針和尾指針開創(chuàng)空間鏈表。然后分別按三種算法進(jìn)行分配和回收。 在該程序中關(guān)鍵函數(shù)有，sort（）、allocation（）、recovery（）、和First_fit（）、Best_fit（）、Worst_fit（）。其中： sort（）函數(shù)用來整理分區(qū)序號(hào)。如在刪序號(hào)3時(shí)，它與前面序號(hào)2相連在一起了，然后序號(hào)2中的長(zhǎng)度若滿足申請(qǐng)的內(nèi)存大小，就會(huì)在序號(hào)2中分配，然后序號(hào)在2的基礎(chǔ)上加1，一直加，加到與原本序號(hào)3的下一個(gè)序號(hào)也就是4相等，這時(shí)sort（）就開始有明顯的工作了； allocation（）

8、用來分配空間。也是過渡到三個(gè)算法中的，當(dāng)三個(gè)算法中滿足或者不滿足分配請(qǐng)求，都會(huì)又返回值給allocation（）； recovery（）用來回收內(nèi)存。包含四種情況的處理，即釋放區(qū)上與空閑區(qū)鄰接、釋放區(qū)下與空閑區(qū)鄰接、釋放區(qū)上下都與空閑區(qū)鄰接、釋放區(qū)上下都與空閑區(qū)不鄰接。3.源碼參考： #include#include#define OK 1 /完成#define ERROR 0 /出錯(cuò)typedef int Status;typedef struct free_table/定義一個(gè)空閑區(qū)說明表結(jié)構(gòu) int num; /分區(qū)序號(hào) long address; /起始地址 long length;

9、/分區(qū)大小 int state; /分區(qū)狀態(tài)ElemType;typedef struct Node/ 線性表的雙向鏈表存儲(chǔ)結(jié)構(gòu) ElemType data; struct Node *prior; /前趨指針 struct Node *next; /后繼指針Node,*LinkList; LinkList first; /頭結(jié)點(diǎn)LinkList end; /尾結(jié)點(diǎn)int flag;/記錄要?jiǎng)h除的分區(qū)序號(hào)Status Initblock()/開創(chuàng)帶頭結(jié)點(diǎn)的內(nèi)存空間鏈表 first=(LinkList)malloc(sizeof(Node); end=(LinkList)malloc(sizeo

10、f(Node); first-prior=NULL; first-next=end; end-prior=first; end-next=NULL; end-data.num=1; end-data.address=40; end-data.length=600; end-data.state=0; return OK;void sort()/分區(qū)序號(hào)重新排序 Node *p=first-next,*q; q=p-next; for(;p!=NULL;p=p-next) for(q=p-next;q;q=q-next) if(p-data.num=q-data.num) q-data.num+

11、=1; /顯示主存分配情況void show() int flag=0;/用來記錄分區(qū)序號(hào) Node *p=first; p-data.num=0; p-data.address=0; p-data.length=40; p-data.state=1; sort(); printf(ntt主存空間分配情況n); printf(*nn); printf(分區(qū)序號(hào)t起始地址t分區(qū)大小t分區(qū)狀態(tài)nn); while(p) printf(%dtt%dtt%d,p-data.num,p-data.address,p-data.length); if(p-data.state=0) printf(tt空閑

12、nn); else printf(tt已分配nn); p=p-next; printf(*nn);/首次適應(yīng)算法Status First_fit(int request) /為申請(qǐng)作業(yè)開辟新空間且初始化 Node *p=first-next; LinkList temp=(LinkList)malloc(sizeof(Node); temp-data.length=request; temp-data.state=1; p-data.num=1; while(p) if(p-data.state=0)&(p-data.length=request) /有大小恰好合適的空閑塊 p-data.st

13、ate=1; return OK; break; else if(p-data.state=0) & (p-data.lengthrequest) /有空閑塊能滿足需求且有剩余 temp-prior=p-prior; temp-next=p; temp-data.address=p-data.address; temp-data.num=p-data.num; p-prior-next=temp; p-prior=temp; p-data.address=temp-data.address+temp-data.length; p-data.length-=request; p-data.num

14、+=1; return OK; break; p=p-next; return ERROR;/最佳適應(yīng)算法Status Best_fit(int request) int ch; /記錄最小剩余空間 Node *p=first; Node *q=NULL; /記錄最佳插入位置 LinkList temp=(LinkList)malloc(sizeof(Node); temp-data.length=request; temp-data.state=1; p-data.num=1; while(p) /初始化最小空間和最佳位置 if(p-data.state=0) & (p-data.lengt

15、h=request) ) if(q=NULL) q=p; ch=p-data.length-request; else if(q-data.length p-data.length) q=p; ch=p-data.length-request; p=p-next; if(q=NULL) return ERROR;/沒有找到空閑塊 else if(q-data.length=request) q-data.state=1; return OK; else temp-prior=q-prior; temp-next=q; temp-data.address=q-data.address; temp

16、-data.num=q-data.num; q-prior-next=temp; q-prior=temp; q-data.address+=request; q-data.length=ch; q-data.num+=1; return OK; return OK;/最差適應(yīng)算法Status Worst_fit(int request) int ch; /記錄最大剩余空間 Node *p=first-next; Node *q=NULL; /記錄最佳插入位置 LinkList temp=(LinkList)malloc(sizeof(Node); temp-data.length=reque

17、st; temp-data.state=1; p-data.num=1; while(p) /初始化最大空間和最佳位置 if(p-data.state=0 & (p-data.length=request) ) if(q=NULL) q=p; ch=p-data.length-request; else if(q-data.length data.length) q=p; ch=p-data.length-request; p=p-next; if(q=NULL) return ERROR;/沒有找到空閑塊 else if(q-data.length=request) q-data.lengt

18、h=1; return OK; else temp-prior=q-prior; temp-next=q; temp-data.address=q-data.address; temp-data.num=q-data.num; q-prior-next=temp; q-prior=temp; q-data.address+=request; q-data.length=ch; q-data.num+=1; return OK; return OK;/分配主存Status allocation(int a) int request;/申請(qǐng)內(nèi)存大小 printf(請(qǐng)輸入申請(qǐng)分配的主存大小(單位:K

19、B):); scanf(%d,&request); if(requestnext) if(q=p) if(q-prior-data.state=0&q-next-data.state!=0) q-prior-data.length+=q-data.length; q-prior-next=q-next; q-next-prior=q-prior; q=q-prior; q-data.state=0; q-data.num=flag-1; if(q-prior-data.state!=0&q-next-data.state=0) q-data.length+=q-next-data.length

20、; q-next=q-next-next; q-next-next-prior=q; q-data.state=0; q-data.num=flag; if(q-prior-data.state=0&q-next-data.state=0) q-prior-data.length+=q-data.length; q-prior-next=q-next; q-next-prior=q-prior; q=q-prior; q-data.state=0; q-data.num=flag-1; if(q-prior-data.state!=0&q-next-data.state!=0) q-data.

21、state=0; return OK;Status deal2(Node *p)/處理回收空間 Node *q=first; for(;q!=NULL;q=q-next) if(q=p) if(q-prior-data.state=0&q-next-data.state!=0) q-prior-data.length+=q-data.length; q-prior-next=q-next; q-next-prior=q-prior; q=p-prior; q-data.state=0; q-data.num=flag-1; if(q-prior-data.state!=0&q-next-dat

22、a.state=0) q-data.state=0; if(q-prior-data.state=0&q-next-data.state=0) q-prior-data.length+=q-data.length; q-prior-next=q-next; q-next-prior=q-prior; q=q-prior; q-data.state=0; q-data.num=flag-1; if(q-prior-data.state!=0&q-next-data.state!=0) q-data.state=0; return OK;/主存回收Status recovery(int flag)

23、 Node *p=first; for(;p!=NULL;p=p-next) if(p-data.num=flag) if(p-prior=first) if(p-next!=end)/當(dāng)前P指向的下一個(gè)不是最后一個(gè)時(shí) if(p-next-data.state=0) /與后面的空閑塊相連 p-data.length+=p-next-data.length; p-next-next-prior=p; p-next=p-next-next; p-data.state=0; p-data.num=flag; else p-data.state=0; if(p-next=end)/當(dāng)前P指向的下一個(gè)是

24、最后一個(gè)時(shí) p-data.state=0; /結(jié)束if(p-prior=block_first)的情況 else if(p-prior!=first) if(p-next!=end) deal1(p); else deal2(p); /結(jié)束if(p-prior!=block_first)的情況 /結(jié)束if(p-data.num=flag)的情況 printf(t*回收成功*); return OK; /主函數(shù)void main() int i; /操作選擇標(biāo)記 int a;/算法選擇標(biāo)記 printf(*n); printf(tt用以下三種方法實(shí)現(xiàn)主存空間的分配n); printf(t(1)首次適應(yīng)算法t(2)最佳適應(yīng)算法t(3)最差適應(yīng)算法n);printf(*n); printf(n); printf(請(qǐng)輸入所使用的內(nèi)存分配算法:); scanf(%d,&a); while(a3) printf(輸入錯(cuò)誤，請(qǐng)重新輸入所使用的內(nèi)存分配算法:n); scanf(%d,&a); switch(a) case 1:printf(nt*使用首次適應(yīng)算法：*n);break; case 2:print