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

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

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

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

4、文件讀入空閑區(qū)表。在這里我們可以設(shè)計一個空閑區(qū)表文件的結(jié)構(gòu)為如表2所示：表2 空閑區(qū)表起始地址長度200k50k這樣也可以方便地將空閑表一次讀入程序中，而不必再一個個的輸入。主要變量及函數(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、 實驗代碼清單1、主函數(shù)（如圖1）void main()int ch;/算法選擇標(biāo)記cout請輸入所使用的內(nèi)存分配算法：n;coutch;while(ch3)coutch;Initblock(); /開創(chuàng)空間表int choice; /操作選擇標(biāo)記while(1)show();cout請輸入您的操作：;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輸入有誤，請重試！endl;continue;圖12、分配主存（如圖2）Status alloc(int ch)int request = 0;coutrequest;if(request0 |request=0) cout分配大小不合適，請重試！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)存不足，分配失?。ata.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