計算機(jī)操作系統(tǒng)內(nèi)存分配實驗報告

1、計算機(jī)操作系統(tǒng)內(nèi)存分配實驗報告 計算機(jī)操作系統(tǒng)內(nèi)存分配實驗報告 一、實驗?zāi)康?熟悉主存的分配與回收。理解在不同的存儲管理方式下，如何實現(xiàn)主存空間的分配與回收。掌握動態(tài)分區(qū)分配方式中的數(shù)據(jù)結(jié)構(gòu)和分配算法及動態(tài)分區(qū)存儲管理方式及其實現(xiàn)過程。 二、實驗內(nèi)容和要求 主存的分配和回收的實現(xiàn)是與主存儲器的管理方式有關(guān)的。所謂分配，就是解決多道作業(yè)或多進(jìn)程如何共享主存空間的問題。所謂回收，就是當(dāng)作業(yè)運行完成時將作業(yè)或進(jìn)程所占的主存空間歸還給系統(tǒng)。 可變分區(qū)管理是指在處理作業(yè)過程中建立分區(qū)，使分區(qū)大小正好合適作業(yè)的需求，并且分區(qū)個數(shù)是可以調(diào)整的。當(dāng)要裝入一個作業(yè)時，依據(jù)作業(yè)需要的主存量查看是否有足夠的空閑空間

2、，假設(shè)有，則按需要量分割一個分區(qū)分配給該作業(yè)； 假設(shè)無，則作業(yè)不能裝入，作業(yè)等待。隨著作業(yè)的裝入、完成，主存空間被分成許多大大小小的分區(qū)，有的分區(qū)被作業(yè)占用，而有的分區(qū)是空閑的。 實驗要求使用可變分區(qū)存儲管理方式，分區(qū)分配中所用的數(shù)據(jù)結(jié)構(gòu)采納空閑分區(qū)表和空閑分區(qū)鏈來進(jìn)行，分區(qū)分配中所用的算法采納首次適應(yīng)算法、最正確適應(yīng)算法、最差適應(yīng)算法三種算法來實現(xiàn)主存的分配與回收。同時，要求制定一個有用友好的用戶界面，并顯示分配與回收的過程。同時要求制定一個有用友好的用戶界面,并顯示分配與回收的過程。 三、實驗主要儀器設(shè)備和材料 實驗環(huán)境 硬件環(huán)境：pc或兼容機(jī) 軟件環(huán)境：vc+ 6.0 四、實驗原理及制定

3、分析 某系統(tǒng)采納可變分區(qū)存儲管理，在系統(tǒng)運行當(dāng)然開始，假設(shè)初始狀態(tài)下，可用的內(nèi)存空間為640kb，存儲器區(qū)被分為操作系統(tǒng)分區(qū)40kb和可給用戶的空間區(qū)600kb。 作業(yè)1 申請130kb、 作業(yè)2 申請60kb、 作業(yè)3 申請100kb 、 作業(yè)2 釋放 60kb 、 作業(yè)4 申請 200kb、 作業(yè)3釋放100kb、 作業(yè)1 釋放130kb 、 作業(yè)5申請140kb 、 作業(yè)6申請60kb 、作業(yè)7申請50kb 當(dāng)作業(yè)1進(jìn)入內(nèi)存后，分給作業(yè)1130kb，隨著作業(yè)1、2、3的進(jìn)入，分別分配60kb、100kb，經(jīng)過一段時間的運行后，作業(yè)2運行完畢，釋放所占內(nèi)存。此時，作業(yè)4進(jìn)入系統(tǒng)，要求分配2

4、00kb內(nèi)存。作業(yè)3、1運行完畢，釋放所占內(nèi)存。此時又有作業(yè)5申請140kb，作業(yè)6申請60kb，作業(yè)7申請50kb。為它們進(jìn)行主存分配和回收。 1、采納可變分區(qū)存儲管理，使用空閑分區(qū)鏈實現(xiàn)主存分配和回收。 空閑分區(qū)鏈：使用鏈指針把所有的空閑分區(qū)鏈成一條鏈，為了實現(xiàn)對空閑分區(qū)的分配和鏈接，在每個分區(qū)的起始部分設(shè)置狀態(tài)位、分區(qū)的大小和鏈接各個分區(qū)的前向指針，由狀態(tài)位指示該分區(qū)是否分配出去了； 同時，在分區(qū)尾部還設(shè)置有一后向指針，用來鏈接后面的分區(qū)；分區(qū)中間部分是用來存放作業(yè)的空閑內(nèi)存空間，當(dāng)該分區(qū)分配出去后，狀態(tài)位就由“0置為“1。 設(shè)置一個內(nèi)存空閑分區(qū)鏈，內(nèi)存空間分區(qū)通過空閑分區(qū)鏈來管理，在進(jìn)

5、行內(nèi)存分配時，系統(tǒng)優(yōu)先使用空閑低端的空間。 制定一個空閑分區(qū)說明鏈，制定一個某隨時主存空間占用狀況表，作為主存當(dāng)前使用基礎(chǔ)。初始化空間區(qū)和已分配區(qū)說明鏈的值，制定作業(yè)申請隊列以及作業(yè)完成后釋放順序，實現(xiàn)主存的分配和回收。要求每次分配和回收后顯示出空閑內(nèi)存分區(qū)鏈的狀況。把空閑區(qū)說明鏈的變化狀況以及各作業(yè)的申請、釋放狀況顯示打印出來。 2.采納可變分區(qū)存儲管理，分別采納首次適應(yīng)算法、最正確適應(yīng)算法和最壞適應(yīng)算法實現(xiàn)主存分配和回收。 3、主存空間分配 1首次適應(yīng)算法 在該算法中，把主存中所有空閑區(qū)按其起始地址遞增的次序排列。在為作業(yè)分配存儲空間時，從上次找到的空閑分區(qū)的下一個空閑分區(qū)開始查找，直到找

6、到第一個能滿足要求的空閑區(qū)，從中劃出與請求的大小相等的存儲空間分配給作業(yè)，余下的空閑區(qū)仍留在空閑區(qū)鏈中。 2最正確適應(yīng)算法 在該算法中，把主存中所有空閑區(qū)按其起始地址遞增的次序排列。在為作業(yè)分配存儲空間時，從上次找到的空閑分區(qū)的下一個空閑分區(qū)開始查找，直到找到一個能滿足要求的空閑區(qū)且該空閑區(qū)的大小比其他滿足要求的空閑區(qū)都小，從中劃出與請求的大小相等的存儲空間分配給作業(yè)，余下的空閑區(qū)仍留在空閑區(qū)鏈中 3最壞適應(yīng)算法 在該算法中，把主存中所有空閑區(qū)按其起始地址遞增的次序排列。在為作業(yè)分配存儲空間時，從上次找到的空閑分區(qū)的下一個空閑分區(qū)開始查找，直到找到一個能滿足要求的空閑區(qū)且該空閑區(qū)的大小比其他滿

7、足要求的空閑區(qū)都大，從中劃出與請求的大小相等的存儲空間分配給作業(yè)，余下的空閑區(qū)仍留在空閑區(qū)鏈中。 4、主存空間回收 當(dāng)一個作業(yè)執(zhí)行完成撤離時，作業(yè)所占的分區(qū)應(yīng)該歸還給系統(tǒng)。歸還的分區(qū)如果與其它空閑區(qū)相鄰，則應(yīng)合成一個較大的空閑區(qū)，登記在空閑區(qū)說明鏈中，此時，相鄰空閑區(qū)的合并問題，要求合計四種狀況： 1 釋放區(qū)下鄰空閑區(qū)低地址鄰接 2 釋放區(qū)上鄰空閑區(qū)高地址鄰接 3 釋放區(qū)上下都與空閑區(qū)鄰接 4 釋放區(qū)上下鄰都與空閑區(qū)不鄰接 五、程序流程圖 main函數(shù)里的流程圖 初始化first和end 整理分區(qū)序號 顯示空閑分區(qū)鏈 選擇算法a a=1，首次適應(yīng)算法 a=2，最正確適應(yīng)算法 a=3，最壞適應(yīng)算

8、法 選擇操作i i=1，分配空間函數(shù)a i=0，退出程序 i=2，回收空間函數(shù) 結(jié)束 分配空間里的流程圖 p-data.length=request 分配不成功 分配空間函數(shù) a=1 a=2 a=3 輸入申請內(nèi)存大小 按順序找空閑塊 初始化q，使它指向空閑塊中長度小的一塊 輸入申請內(nèi)存大小 初始化q，使它指向空閑塊中長度大的一塊 p-data.lengthrequest p的狀態(tài)為已分配 剩下 p-data.length-=request 輸入申請內(nèi)存大小 y y n n 返回到整理分區(qū)序號 回收空間里的流程圖 p的狀態(tài)改為空閑 回收p，p的前一個為first p的后一個是end p的后一個狀

9、態(tài)空 與后面空閑塊相連 將p 的狀態(tài)改為空閑 將p 的狀態(tài)改為空閑 回收空間函數(shù) p的后一個是end y n y n y n p的前一個狀態(tài)空 p的前一個狀態(tài)空 p的后一個狀態(tài)空 p的后一個狀態(tài)空 p的后一個狀態(tài)空 p的后一個狀態(tài)空 y y y n n n 與前面空閑塊相連 p的狀態(tài)改為空閑 與前面空閑塊相連 與后面空閑塊相連 y n 返回到整理分區(qū)序號 六、相關(guān)數(shù)據(jù)結(jié)構(gòu)及關(guān)鍵函數(shù)說明 本程序采納了一個struct free_table數(shù)據(jù)結(jié)構(gòu)，里面包含分區(qū)序號num、起始地址address、分區(qū)長度length和分區(qū)狀態(tài)state。還用了線性表的雙性鏈表存儲結(jié)構(gòu)struct node，里面包

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

11、算法中滿足或者不滿足分配請求，都會又返回值給allocation；recovery是用來回收內(nèi)存的，里面包含了四種狀況相連結(jié)果，即釋放區(qū)上與空閑區(qū)鄰接、釋放區(qū)下與空閑區(qū)鄰接、釋放區(qū)上下都與空閑區(qū)鄰接、釋放區(qū)上下都與空閑區(qū)不鄰接這四種狀況的結(jié)果。 七、源代碼 #includestdio.h #includestdlib.h #define ok 1 /完成 #define error 0 /出錯 typedef int status; typedef struct free_table/定義一個空閑區(qū)說明表結(jié)構(gòu) int num; /分區(qū)序號 long address; /起始地址 long le

12、ngth; /分區(qū)大小 int state; /分區(qū)狀態(tài) elemtype; typedef struct node/ 線性表的雙向鏈表存儲結(jié)構(gòu) elemtype data; struct node *prior; /前趨指針 struct node *next; /后繼指針 node,*linklist; linklist first; /頭結(jié)點 linklist end; /尾結(jié)點 int flag;/記錄要刪除的分區(qū)序號 status initblock()/開創(chuàng)帶頭結(jié)點的內(nèi)存空間鏈表 first=(linklist)malloc(sizeof(node); end=(linklist)

13、malloc(sizeof(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ū)序號重新排序 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

14、) q-data.num+=1; /顯示主存分配狀況 void show() int flag=0;/用來記錄分區(qū)序號 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ū)序號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-dat

15、a.state=0) printf(“tt空閑nn“); else printf(“tt已分配nn“); p=p-next; printf(“*nn“); /首次適應(yīng)算法 status first_fit(int request) /為申請作業(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=re

16、quest) /有大小恰好合適的空閑塊 p-data.state=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.

17、length-=request; p-data.num+=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

18、(p-data.state=0) (p-data.length=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-dat

19、a.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; /最差適應(yīng)算法 status worst_fit(int request) int ch; /記錄最大剩余空間 node *p=first-next; node *q=null; /記錄最正確插入位置 linklist temp=(linklist)malloc(siz

20、eof(node); temp-data.length=request; 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 p-data.length) q=p; ch=p-data.length-request; p=p-next; if(q=null) return error;/沒有找到空閑塊 else if(q

21、-data.length=request) q-data.length=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 requ

22、est;/申請內(nèi)存大小 printf(“請輸入申請分配的主存大小(單位:kb):“); scanf(“%d“,request); if(request0 |request=0) printf(“分配大小不合適，請重試！“); return error; switch(a) case 1: /默認(rèn)首次適應(yīng)算法 if(first_fit(request)=ok) printf(“t*分配成功！*“); else printf(“t*內(nèi)存不夠，分配失?。?“); return ok; break; case 2: /選擇最正確適應(yīng)算法 if(best_fit(request)=ok) printf(

23、“t*分配成功！*“); else printf(“t*內(nèi)存不夠，分配失??！*“); return ok; break; case 3: /選擇最差適應(yīng)算法 if(worst_fit(request)=ok) printf(“t*分配成功！*“); else printf(“t*內(nèi)存不夠，分配失?。?“); return ok; break; status deal1(node *p)/處理回收空間 node *q=first; for(;q!=null;q=q-next) if(q=p) if(q-prior-data.state=0q-next-data.state!=0) q-prior

24、-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!=0q-next-data.state=0) q-data.length+=q-next-data.length; q-next=q-next-next; q-next-next-prior=q; q-data.state=0; q-data.num=flag; if(q-prior-data.state=0q-nex

25、t-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!=0q-next-data.state!=0) q-data.state=0; return ok; status deal2(node *p)/處理回收空間 node *q=first; for(;q!=null;q=q-next) if(q=p) if(q-prior-

26、data.state=0q-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!=0q-next-data.state=0) q-data.state=0; if(q-prior-data.state=0q-next-data.state=0) q-prior-data.length+=q-data.length;

27、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!=0q-next-data.state!=0) q-data.state=0; return ok; /主存回收 status recovery(int flag) 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指向的下一個不是最后一

28、個時 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指向的下一個是最后一個時 p-data.state=0; /結(jié)束if(p-prior=block_first)的狀況 else if(p-prior!=first) if(p-next!=end) deal1(p); else

29、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用以下三種方法實現(xiàn)主存空間的分配n“); printf(“t(1)首次適應(yīng)算法t(2)最正確適應(yīng)算法t(3)最差適應(yīng)算法n“); printf(“*n“); printf(“n“); printf(“請輸入所使用的內(nèi)存分配算法:“); scanf(“%d“,a);

30、while(a1|a3) printf(“輸入錯誤，請重新輸入所使用的內(nèi)存分配算法:n“); scanf(“%d“,a); switch(a) case 1:printf(“nt*使用首次適應(yīng)算法：*n“);break; case 2:printf(“nt*使用最正確適應(yīng)算法：*n“);break; case 3:printf(“nt*使用最壞適應(yīng)算法：*n“);break; initblock(); /開創(chuàng)空間表 while(1) show(); printf(“t1: 分配內(nèi)存t2: 回收內(nèi)存t0: 退出n“); printf(“請輸入您的操作：“); scanf(“%d“,i); if(i=1) allocation(a); / 分配內(nèi)存 else if(i=2) / 內(nèi)存回收 printf(“請輸入您要釋放的分區(qū)號：“); scanf(“%d“,flag); recovery(flag); else if(i=0) p