可變分區(qū)存儲(chǔ)管理

1、精選優(yōu)質(zhì)文檔-傾情為你奉上沈 陽(yáng) 工 程 學(xué) 院學(xué) 生 實(shí) 驗(yàn) 報(bào) 告（課程名稱： 操作系統(tǒng) ）實(shí)驗(yàn)題目： 可變分區(qū)存儲(chǔ)管理 班 級(jí) 計(jì)算機(jī)131 學(xué) 號(hào) 姓 名 楊光成 地 點(diǎn) 實(shí)訓(xùn)F608 指導(dǎo)教師 呂海華 王黎明 實(shí) 驗(yàn) 日 期 : 2015 年 5 月 19 日專心-專注-專業(yè)一、 實(shí)驗(yàn)題目主存儲(chǔ)器空間分配實(shí)驗(yàn)。二、實(shí)驗(yàn)要求編寫一段程序來模擬可變分區(qū)管理方法。要求能通過文件形式定義空閑區(qū)表；能隨意輸入作業(yè)及需要分配的空間；能分別使用首次適應(yīng)算法、最佳適應(yīng)算法和最壞適應(yīng)算法對(duì)輸入的作業(yè)進(jìn)行空間分配；能顯示系統(tǒng)空閑表和已分配空間表。三、實(shí)驗(yàn)?zāi)康耐ㄟ^首次適應(yīng)算法、最佳適應(yīng)算法和最壞適應(yīng)算法實(shí)

2、現(xiàn)主存空間的分配，可以使讀者可好地理解存儲(chǔ)分配算法。四、實(shí)驗(yàn)原理分析可變分區(qū)方式是按作業(yè)需要的主存空間大小來分區(qū)。當(dāng)裝入一個(gè)作業(yè)時(shí)，首先要查看是否有足夠的空閑空間來分配，若有則按指定的分配方式進(jìn)行分配；否則作業(yè)不能裝入。隨著作業(yè)的裝入和撤離主存空間被分為若干個(gè)大大小小的不連續(xù)的區(qū)間，為了表明各區(qū)間的狀態(tài)可以用一個(gè)內(nèi)存分區(qū)表如表1所示來表示。表1 內(nèi)存分區(qū)表起始地址長(zhǎng)度標(biāo)志120k20k作業(yè)1200k50k空閑這樣我們可以定義一個(gè)如下的結(jié)構(gòu)表示內(nèi)存分區(qū)信息。typedef struct nodeint start;/起始地址int length; /長(zhǎng)度char tag20;/標(biāo)志job;可變分

3、區(qū)的三種算法就是為作業(yè)分配主存空間的方法。 首次適應(yīng)算法：在空閑區(qū)間中查詢滿足作業(yè)需要的空間，并將作業(yè)裝入第一個(gè)滿足條件的空間中去。 最佳適應(yīng)算法：在空閑區(qū)間中查詢滿足作業(yè)需要的空間，并將作業(yè)裝入滿足條件的空閑空間中最小的一個(gè)空間中去。 最壞適應(yīng)算法：在空閑區(qū)間中查詢滿足作業(yè)需要的空間，并將作業(yè)裝入滿足條件的空閑空間中最大的一個(gè)空間中去。從三種算法的說明可以看出，分配空間的過程主要可以分兩步： 查詢所有滿足作業(yè)需求的空間塊。 按照指定的算法將作業(yè)裝入空間塊中。在操作的最初主存空間實(shí)際就是一個(gè)大的空閑區(qū)，不涉及到如何分配的問題。為直接模擬運(yùn)行一段時(shí)間后主存中出現(xiàn)了多個(gè)空閑塊的狀態(tài)，題目要求從一個(gè)

4、文件讀入空閑區(qū)表。在這里我們可以設(shè)計(jì)一個(gè)空閑區(qū)表文件的結(jié)構(gòu)為如表2所示：表2 空閑區(qū)表起始地址長(zhǎng)度200k50k這樣也可以方便地將空閑表一次讀入程序中，而不必再一個(gè)個(gè)的輸入。主要變量及函數(shù)說明如表3所示。表3 變量與函數(shù)說明表typedef struct node內(nèi)存塊結(jié)構(gòu)job frees空閑區(qū)表job occupys已分配區(qū)表free_quantity空閑區(qū)數(shù)量occupy_quantity已分配區(qū)數(shù)量void initial()初始化函數(shù)int readData()從文件讀入空閑表函數(shù)void sort()排序空閑表void view()顯示分區(qū)信息void earliest()最先適應(yīng)

5、分配算法void excellent()最優(yōu)適應(yīng)分配算法void worst()最壞適應(yīng)算法mem.txt空閑表文件5、 實(shí)驗(yàn)代碼清單1、主函數(shù)（如圖1）void main()int ch;/算法選擇標(biāo)記cout請(qǐng)輸入所使用的內(nèi)存分配算法：n;coutch;while(ch3)coutch;Initblock(); /開創(chuàng)空間表int choice; /操作選擇標(biāo)記while(1)show();cout請(qǐng)輸入您的操作：;coutchoice;if(choice=1) alloc(ch); / 分配內(nèi)存else if(choice=2) / 內(nèi)存回收int flag;coutflag;free(

6、flag);else if(choice=0) break; /退出else /輸入操作有誤cout輸入有誤，請(qǐng)重試！endl;continue;圖12、分配主存（如圖2）Status alloc(int ch)int request = 0;coutrequest;if(request0 |request=0) cout分配大小不合適，請(qǐng)重試！endl;return ERROR;if(ch=2) /選擇最佳適應(yīng)算法if(Best_fit(request)=OK) cout分配成功！endl;else cout內(nèi)存不足，分配失敗！endl;return OK;if(ch=3) /選擇最差適應(yīng)算

7、法if(Worst_fit(request)=OK) cout分配成功！endl;else cout內(nèi)存不足，分配失敗！endl;return OK;else /默認(rèn)首次適應(yīng)算法if(First_fit(request)=OK) cout分配成功！endl;else cout內(nèi)存不足，分配失??！data.size=request;temp-data.state=Busy;DuLNode *p=block_first-next;while(p)if(p-data.state=Free & p-data.size=request)/有大小恰好合適的空閑塊p-data.state=Busy;retu

8、rn OK;break;if(p-data.state=Free & p-data.sizerequest)/有空閑塊能滿足需求且有剩余temp-prior=p-prior;temp-next=p;temp-data.address=p-data.address;p-prior-next=temp;p-prior=temp;p-data.address=temp-data.address+temp-data.size;p-data.size-=request;return OK;break;p=p-next;return ERROR;圖34、最佳適應(yīng)（如圖4和圖5）Status Best_fi

9、t(int request)int ch; /記錄最小剩余空間DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode); temp-data.size=request;temp-data.state=Busy;DuLNode *p=block_first-next;DuLNode *q=NULL; /記錄最佳插入位置while(p) /初始化最小空間和最佳位置if(p-data.state=Free & (p-data.size=request) )if(q=NULL)q=p;ch=p-data.size-request;else if(q-data

10、.size p-data.size)q=p;ch=p-data.size-request;p=p-next;if(q=NULL) return ERROR;/沒有找到空閑塊else if(q-data.size=request)q-data.state=Busy;return OK;elsetemp-prior=q-prior;temp-next=q;temp-data.address=q-data.address;q-prior-next=temp;q-prior=temp;q-data.address+=request;q-data.size=ch;return OK;return OK;

11、圖4圖55、最差適應(yīng)（如圖6）Status Worst_fit(int request)int ch; /記錄最大剩余空間DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode); temp-data.size=request;temp-data.state=Busy;DuLNode *p=block_first-next;DuLNode *q=NULL; /記錄最佳插入位置while(p) /初始化最大空間和最佳位置if(p-data.state=Free & (p-data.size=request) )if(q=NULL)q=p;ch=p-da

12、ta.size-request;else if(q-data.size data.size)q=p;ch=p-data.size-request;p=p-next;if(q=NULL) return ERROR;/沒有找到空閑塊else if(q-data.size=request)q-data.state=Busy;return OK;elsetemp-prior=q-prior;temp-next=q;temp-data.address=q-data.address;q-prior-next=temp;q-prior=temp;q-data.address+=request;q-data.

13、size=ch;return OK;return OK;圖6圖76、主存回收和顯示主存分配情況（如圖8）Status free(int flag)DuLNode *p=block_first;for(int i= 0; i next;elsereturn ERROR;p-data.state=Free;if(p-prior!=block_first & p-prior-data.state=Free)/與前面的空閑塊相連p-prior-data.size+=p-data.size;p-prior-next=p-next;p-next-prior=p-prior;p=p-prior;if(p-next!=block_last & p-next-data.state=Free)/與后面的空閑塊相連p-data.size+=p-next-data.size;p-next-next-prior=p;p-next=p-next-next; if(p-next=block_last & p-next-data.state=Free)/與最后的空閑塊相連p-data.size+=p-next-data.size;p-next=NULL; return