模擬實(shí)現(xiàn)一個(gè)簡單的可變分區(qū)存儲(chǔ)管理系統(tǒng)

1、11合肥學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系合肥學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系實(shí)驗(yàn)報(bào)告2013 2014 學(xué)年第 一 學(xué)期課程操作系統(tǒng)原理實(shí)驗(yàn)名稱 模擬實(shí)現(xiàn)一個(gè)簡單的可變分區(qū)存儲(chǔ)管理系統(tǒng)學(xué)生姓名專業(yè)班級(jí)指導(dǎo)教師謝雪勝2013 年 12 月1實(shí)驗(yàn)?zāi)康哪M實(shí)現(xiàn)一個(gè)簡單的固定（或可變）分區(qū)存儲(chǔ)管理系統(tǒng)2實(shí)驗(yàn)內(nèi)容本實(shí)驗(yàn)要求完成如下任務(wù)：（1） 建立相關(guān)的數(shù)據(jù)結(jié)構(gòu)，作業(yè)控制塊、已分配分區(qū)及未分配分區(qū)（2） 實(shí)現(xiàn)一個(gè)分區(qū)分配算法，如最先適應(yīng)分配算法、最優(yōu)或最壞適應(yīng)分配算法（3） 實(shí)現(xiàn)一個(gè)分區(qū)回收算法（4） 給定一批作業(yè)/進(jìn)程，選擇一個(gè)分配或回收算法，實(shí)現(xiàn)分區(qū)存儲(chǔ)的模擬管理。3實(shí)驗(yàn)步驟（1）任務(wù)分析本實(shí)驗(yàn)要實(shí)現(xiàn)的功能是模擬分區(qū)管

2、理系統(tǒng)，即輸入一個(gè)批作業(yè)，由程序根據(jù)各個(gè)作業(yè)的大小為批作業(yè)分配分區(qū)。如果能找到滿足條件的分區(qū)，則分配成功，否則分配失敗。對于程序的輸入，輸入用戶程序所要請求的分區(qū)大小，-1表示輸入完成。程序輸入分配分區(qū)后各個(gè)分區(qū)的使用情況，然后回收分區(qū)，程序輸出回收分區(qū)后各個(gè)分區(qū)的使用情況。（2）概要設(shè)計(jì)對于分區(qū)的定義，定義的數(shù)據(jù)結(jié)構(gòu)如下所示typedef structint no;/定義分區(qū)編號(hào)int size;/定義大小int start;/定義分區(qū)起始位置int state;/定義分區(qū)狀態(tài)，已分配或未分配fenqubiao;fenqubiao arr50;其中，no表示分區(qū)的編號(hào)，size表示當(dāng)前分區(qū)塊

3、的大小，start表示當(dāng)前分區(qū)的起始位置，state表示當(dāng)前分區(qū)的狀態(tài)，已分配或空閑。Arr50表示當(dāng)前系統(tǒng)所有分區(qū)情況。主程序的流程圖如下：NN輸入回收分區(qū)編號(hào)結(jié)束是否輸入完輸出分區(qū)表狀態(tài)開始初始化分區(qū)表輸入分區(qū)請求是否輸入完輸出分區(qū)表狀態(tài)YY（3）詳細(xì)設(shè)計(jì)一、初始化分區(qū)Fenqubiao arr50=1,10,0,0,2,20,10,1,3,10,30,0,4,12,40,0,5,30,52,1,6,25,82,0,7,20,107,0,8,5,127,1,9,64,132,0,10,32,196,0;10201012302520564320103040528210712713219622

4、8二、分區(qū)分配函數(shù)采用的分區(qū)分配函數(shù)是最先適應(yīng)法，每次從地址部分開始遍歷。本程序用的是編號(hào)作為遍歷的關(guān)鍵字，方便處理。如果當(dāng)前分區(qū)的大小大于所請求的大小，并且分區(qū)處于空閑狀態(tài)，則進(jìn)行分區(qū)，劃出滿足請求大小的分區(qū)，并修改狀態(tài)為已分配。如果所劃分分區(qū)所剩空間不為0，則修改其首址，設(shè)定其大小，添加到分區(qū)表中。如果當(dāng)前分區(qū)不滿足請求，則繼續(xù)查找，直至所有分區(qū)遍歷完成。然后返回分配失敗給請求者。具體代碼如下：int fun_allocate(int x,int *num,fenqubiao *arr)int i=0,p;fenqubiao t=0,0,0,0;for(i=0;i<*num;i+)i

5、f(arri.size>=x && arri.state=0)break;if(i=*num)return 0;p=i;t.no=arri.no+1;t.size=arri.size-x;t.start=arri.start+x;t.state=0;arri.size=x;arri.state=1;if(t.size!=0)for(i=*num;i>p;i-)arri=arri-1;arri.no=arri.no+1;arrp+1=t;*num=*num+1;return *num;三、輸出分區(qū)使用情況對分區(qū)表進(jìn)行遍歷，輸出各個(gè)分區(qū)的信息（編號(hào)，大小，起始，狀態(tài)）。

6、其中為了簡單易懂，若狀態(tài)為0則輸出空閑，否則輸出已分配。void fun_print(fenqubiao *arr,int num)int i=0;printf("編號(hào) 大小 起始 狀態(tài)n");for(i=0;i<num;i+)printf("%2d%7d%7d",arri.no,arri.size,arri.start);if(arri.state=1)printf(" 已分配n");elseprintf(" 空閑n");四、回收分區(qū)對所要回收的分區(qū)，則有四種情況。1、 上臨空閑，下臨空閑：修改上一個(gè)分區(qū)大

7、小為三個(gè)分區(qū)大小之和，下臨區(qū)之后的分區(qū)改變其分區(qū)編號(hào)，往前移兩個(gè)。2、 上臨空閑：修改上一個(gè)分區(qū)大小為兩個(gè)分區(qū)大小之和，下臨區(qū)之后的分區(qū)上移一個(gè)單位。3、 下臨空閑：修改當(dāng)前分區(qū)大小為兩個(gè)分區(qū)大小之和，修改狀態(tài)為未分配。然后下臨區(qū)之后的分區(qū)上移一個(gè)單位。4、 上下均無空閑：直接修改狀態(tài)為未分配。如果具體代碼如下:void fun_huishou(int no,int *num,fenqubiao *arr)int i=0;int p=0;for(i=1;i<=*num;i+)if(arri.no=no)p=i;break;if(arrp-1.state=0 && arrp

8、+1.state=0)/上下臨區(qū)arrp-1.size=arrp-1.size+arrp.size+arrp+1.size;for(i=p;i<*num-1;i+)arri=arri+2;arri.no=arri.no-2;*num=*num-2;else if(arrp+1.state=0)/下臨區(qū)arrp.size=arrp.size+arrp+1.size;arrp.state=0;for(i=p+1;i<*num;i+)arri=arri+1;arri.no=arri.no-1;*num=*num-1;else if(arrp-1.state=0) /上臨區(qū)arrp-1.s

9、ize=arrp-1.size+arrp.size;for(i=p;i<*num;i+)arri=arri+1;arri.no=arri.no-1;*num=*num-1;else /無相鄰分區(qū)arrp.state=0;(4)調(diào)試分析實(shí)驗(yàn)結(jié)果截圖如下：114實(shí)驗(yàn)總結(jié)首次適應(yīng)算法，分配時(shí)，當(dāng)進(jìn)程申請大小為SIZE的內(nèi)存時(shí)，系統(tǒng)從空閑區(qū)表的第一個(gè)表目開始查詢，直到首次找到等于或大于SIZE的空閑區(qū)。從該區(qū)中劃出大小為SIZE的分區(qū)分配給進(jìn)程，余下的部分仍作為一個(gè)空閑區(qū)留在空閑區(qū)表中，但要修改其首址和大小?；厥諘r(shí)，按釋放區(qū)的首址，查詢空閑區(qū)表，若有與釋放區(qū)相鄰的空閑區(qū)，則合并到相鄰的空閑區(qū)中，

10、并修改該區(qū)的大小和首址，否則，把釋放區(qū)作為一個(gè)空閑區(qū)，將其大小和首址按照首地址大小遞增的順序插入到空閑區(qū)表的適當(dāng)位置。這里，采用數(shù)組的方式，模擬內(nèi)存分配首次適應(yīng)算法，動(dòng)態(tài)的為作業(yè)分配內(nèi)存塊。可以根據(jù)作業(yè)名稱回收已分配的內(nèi)存塊，當(dāng)空閑內(nèi)存塊相鄰時(shí)，則合并，不相鄰是，直接插入。通過此次的實(shí)驗(yàn)，讓我對內(nèi)存分配中首次適應(yīng)算法更加熟悉，還通過這次實(shí)驗(yàn)了解了分配空間的另外兩種方法：最佳和最壞算法。通過編程模擬實(shí)現(xiàn)操作系統(tǒng)的可變分區(qū)存儲(chǔ)管理的功能，一方面加深對原理的理解，另一方面提高根據(jù)已有原理通過編程解決實(shí)際問題的能力，為進(jìn)行系統(tǒng)軟件開發(fā)和針對實(shí)際問題提出高效的軟件解決方案打下基礎(chǔ)。5附錄程序源代碼#in

11、clude <stdio.h>typedef structint no;/定義分區(qū)編號(hào)int size;/定義大小int start;/定義分區(qū)起始位置int state;/定義分區(qū)狀態(tài)，已分配或未分配fenqubiao;int fun_allocate(int x,int *num,fenqubiao *arr);/分區(qū)算法,分配成功返回分區(qū)數(shù)，否則返回0void fun_print(fenqubiao *arr,int num); /輸出當(dāng)前分區(qū)表狀態(tài)void fun_huishou(int no,int *num,fenqubiao *arr);int main()fenqu

12、biao arr50=1,10,0,0,2,20,10,1,3,10,30,0,4,12,40,0,5,30,52,1,6,25,82,0,7,20,107,0,8,5,127,1,9,64,132,0,10,32,196,0;int num=10;/用于統(tǒng)計(jì)分區(qū)個(gè)數(shù)int i=0,x,t;puts("|=操作系統(tǒng)大實(shí)驗(yàn)=|");puts("| |");puts("| 題目：模擬實(shí)現(xiàn)一個(gè)可變分區(qū)存儲(chǔ)管理系統(tǒng) |");puts("| |");puts("| |");puts("| 制作者

13、信息： |");puts("| |");puts("| 姓 名 學(xué) 號(hào) |");puts("| 萬定國 1104032034 |");puts("| 劉國慶 1104032035 |");puts("| 許成謙 1104032036 |");puts("| 祁益祥 1104032037 |");puts("| 朱 旭 1104032038 |");puts("| |");puts("|=|");system

14、("pause");system("cls");printf("初始分區(qū)情況:n");printf("編號(hào) 大小 起始 狀態(tài)n");for(i=0;i<10;i+)printf("%2d%7d%7d",arri.no,arri.size,arri.start);if(arri.state=1)printf(" 已分配n");elseprintf(" 空閑n");printf("=請求資源=n");printf("輸入請求

15、大小(-1結(jié)束):n");while(scanf("%d",&x) && x!=-1)t=fun_allocate(x,&num,arr);if(t=0)printf("分配失敗!n");elsenum=t;fun_print(arr,num);printf("=回收資源=n");printf("請輸入回收分區(qū)的編號(hào)(-1結(jié)束):n");while(scanf("%d",&x) && x!=-1)fun_huishou(x,&am

16、p;num,arr);fun_print(arr,num);int fun_allocate(int x,int *num,fenqubiao *arr)int i=0,p;fenqubiao t=0,0,0,0;for(i=0;i<*num;i+)if(arri.size>=x && arri.state=0)break;if(i=*num)return 0;p=i;t.no=arri.no+1;t.size=arri.size-x;t.start=arri.start+x;t.state=0;arri.size=x;arri.state=1;if(t.size!

17、=0)for(i=*num;i>p;i-)arri=arri-1;arri.no=arri.no+1;arrp+1=t;*num=*num+1;return *num;void fun_print(fenqubiao *arr,int num)int i=0;printf("編號(hào) 大小 起始 狀態(tài)n");for(i=0;i<num;i+)printf("%2d%7d%7d",arri.no,arri.size,arri.start);if(arri.state=1)printf(" 已分配n");elseprintf(" 空閑n");void fun_huishou(int no,int *num,fenqubiao *arr)int i=0;int p=0;for(i=1;i<=*num;i+)if(arri.no=no)p=i;break;if(arrp-1.state=0 && arrp+1.state=0)/上下臨區(qū)arrp-1.size=arrp-1.size+arrp.size+arrp+1.size;for(i=p;i<*num-1;i+)arri=arri+2;arri.no=arri.no-2;*num=*num-2;els