動(dòng)態(tài)分區(qū)分配存儲(chǔ)管理系統(tǒng)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)操作系統(tǒng)原理操作系統(tǒng)原理課程設(shè)計(jì)報(bào)告題目：題目：動(dòng)態(tài)分區(qū)分配存儲(chǔ)管理系統(tǒng)動(dòng)態(tài)分區(qū)分配存儲(chǔ)管理系統(tǒng)所在學(xué)院： 班 級(jí)： 學(xué) 號(hào)： 姓 名： 指導(dǎo)教師： 2014 年 3 月 18精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)目目 錄錄444556精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)1 1 引言引言操作系統(tǒng)是最重要的系統(tǒng)軟件，同時(shí)也是最活躍的學(xué)科之一。我們通過操作系統(tǒng)可以理解計(jì)算機(jī)系統(tǒng)的資源如何組織，操作系統(tǒng)如何有效地管理這些系統(tǒng)資源，用戶如何通過操作系統(tǒng)與計(jì)算機(jī)系統(tǒng)打交道。存儲(chǔ)器是計(jì)算機(jī)系統(tǒng)的重要組成部分，近年來，存儲(chǔ)器容量雖然一直在不斷擴(kuò)大，但仍不能

2、滿足現(xiàn)代軟件發(fā)展的需要，因此，存儲(chǔ)器仍然是一種寶貴而又緊俏的資源。如何對(duì)它加以有效的管理，不僅直接影響到存儲(chǔ)器的利用率，而且還對(duì)系統(tǒng)性能有重大影響。而動(dòng)態(tài)分區(qū)分配屬于連續(xù)分配的一種方式，它至今仍在內(nèi)存分配方式中占有一席之地。2 2 需求分析需求分析動(dòng)態(tài)分區(qū)分配是根據(jù)進(jìn)程的實(shí)際需要，動(dòng)態(tài)地為之分配內(nèi)存空間。在實(shí)現(xiàn)動(dòng)態(tài)分區(qū)分配時(shí)，將涉及到分區(qū)分配中所用的數(shù)據(jù)結(jié)構(gòu)、分區(qū)分配算法和分區(qū)的分配和回收操作這樣三個(gè)問題。常用的數(shù)據(jù)結(jié)構(gòu)有動(dòng)態(tài)分區(qū)表和動(dòng)態(tài)分區(qū)鏈。在對(duì)數(shù)據(jù)結(jié)構(gòu)有一定掌握程度的情況下設(shè)計(jì)合理的數(shù)據(jù)結(jié)構(gòu)來描述存儲(chǔ)空間，實(shí)現(xiàn)分區(qū)存儲(chǔ)管理的內(nèi)存分配功能，應(yīng)該選擇最合適的適應(yīng)算法（最佳適應(yīng)算法，最壞適應(yīng)算

3、法） ，在動(dòng)態(tài)分區(qū)存儲(chǔ)管理方式中主要實(shí)現(xiàn)內(nèi)存分配和內(nèi)存回收算法，在這些存儲(chǔ)管理中間必然會(huì)有碎片的產(chǎn)生，當(dāng)碎片產(chǎn)生時(shí)，進(jìn)行碎片的拼接等相關(guān)的內(nèi)容。3 3 概要設(shè)計(jì)概要設(shè)計(jì)本程序采用機(jī)構(gòu)化模塊化的設(shè)計(jì)方法，共分為兩大模塊。1最佳適應(yīng)算法實(shí)現(xiàn)它從全部空閑區(qū)中找出能滿足作業(yè)要求的、且大小最小的空閑分區(qū)，這種方法能使碎片盡量小。為適應(yīng)此算法，空閑分區(qū)表（空閑區(qū)鏈）中的空閑分區(qū)要按從小到大進(jìn)行排序，自表頭開始查找到第一個(gè)滿足要求的自由分區(qū)分配。2.最壞算法實(shí)現(xiàn)最壞適應(yīng)分配算法要掃描整個(gè)空閑分區(qū)或鏈表，總是挑選一個(gè)最大的空閑分區(qū)分割給作業(yè)使用。該算法要求將所有的空閑分區(qū)按其容量從大到小的順序形成一空閑分區(qū)鏈

4、，查找時(shí)只要看第一個(gè)分區(qū)能否滿足作業(yè)要求。4 4 詳細(xì)設(shè)計(jì)詳細(xì)設(shè)計(jì)4.1 問題描述和分析系統(tǒng)應(yīng)利用某種分配算法，從空閑分區(qū)鏈表中找到所需大小的分區(qū)，如果空閑分區(qū)大精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)小大于請(qǐng)求分區(qū)大小，則從該分區(qū)中按改請(qǐng)求的大小劃分出一塊內(nèi)存空間大小劃分出一塊內(nèi)存空間分配出去，余下的部分仍留在空閑鏈表中。然后，將分配區(qū)的首址返回給調(diào)用者。當(dāng)進(jìn)程運(yùn)行完畢師范內(nèi)存時(shí)，系統(tǒng)根據(jù)回收區(qū)的首址，從空閑區(qū)中找到相應(yīng)的插入點(diǎn)，此時(shí)可能出現(xiàn)以下四種情況之一：該空閑區(qū)的上下兩相鄰分區(qū)都是空閑區(qū)：將三個(gè)空閑區(qū)合并為一個(gè)空閑區(qū)。新空閑區(qū)的起始地址為上空閑區(qū)的起始地址，大小為三個(gè)空閑區(qū)之和?？臻e

5、區(qū)合并后，取消可用表或自由鏈中下空閑區(qū)的表目項(xiàng)或鏈指針，修改上空閑區(qū)的對(duì)應(yīng)項(xiàng)。 該空閑區(qū)的上相鄰區(qū)是空閑區(qū)：將釋放區(qū)與上空閑區(qū)合并為一個(gè)空閑區(qū)，其起始地址為上空閑區(qū)的起始地址，大小為上空閑區(qū)與釋放區(qū)之和。合并后，修改上空閑區(qū)對(duì)應(yīng)的可用表的表目項(xiàng)或自由鏈指針。 該空閑區(qū)的下相鄰區(qū)是空閑區(qū)：將釋放區(qū)與下空閑區(qū)合并，并將釋放區(qū)的起始地址作為合并區(qū)的起始地址。合并區(qū)的長(zhǎng)度為釋放區(qū)與下空閑區(qū)之和。同理，合并后修改可用表或自由鏈中相應(yīng)的表目項(xiàng)或鏈指針。兩相鄰區(qū)都不是空閑區(qū)：釋放區(qū)作為一個(gè)新空閑可用區(qū)插入可用表或自由鏈。4.2 程序流程圖內(nèi)存分配流程圖，如圖 4-1 所示。精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專

6、注-專業(yè)從頭開始查表檢索完否？分區(qū)大小所需大小分區(qū)大小-所需大小=不可再分割大小從該分區(qū)中劃出所需大小的新分區(qū)將該分區(qū)分配給請(qǐng)求者修改有關(guān)數(shù)據(jù)結(jié)構(gòu)返回繼續(xù)檢索下一個(gè)表項(xiàng)將該分區(qū)從鏈中移出返回YYYNNN內(nèi)存回收流程圖，如圖 4-2 所示。開始判斷空閑區(qū)上下內(nèi)存情況上為空下為空上下都為空上下都不為空將上面的空閑區(qū)合并，并回收將下面的空閑區(qū)合并，并回收將上下的空閑區(qū)合并，并回收直接將其回收結(jié)束4.3 數(shù)據(jù)結(jié)構(gòu)體分析進(jìn)程屬性結(jié)構(gòu)體精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)typedef struct readyque char name10; int size;readyque,*readyqueu

7、e;空閑鏈表結(jié)構(gòu)體typedef struct idlyspace int from; int size; idlyspace * next;idlyspace,*idly;已分配鏈表結(jié)構(gòu)體typedef struct busyspace int from; readyque r; busyspace * next;busyspace,*busy 4.4 主要程序代碼分析#include#include#includeusing namespace std;typedef struct readyque/進(jìn)程的屬性結(jié)構(gòu)體 char name10; int size;readyque,*read

8、yqueue;typedef struct idlyspace/空閑表結(jié)構(gòu)體精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)int from; int size; idlyspace * next;idlyspace,*idly,*idly1;typedef struct busyspace/已分配鏈表結(jié)構(gòu)體int from; readyque r; busyspace * next;busyspace,*busy;static idly Is;static idly Is2;static busy Bs;int bestfit();int worstfit();int recover();void

9、 Isprint();void Bsprint();idly Sort1(idly l);idly Sort(idly l);int main()Is=(idly)malloc(sizeof(idlyspace); Is-from=0; Is-size=100; Is-next=NULL; Is2=Is; Bs=(busy)malloc(sizeof(busyspace); Bs-next=NULL;精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè) int t,t1;l1: printf(|*歡迎來到動(dòng)態(tài)分區(qū)存儲(chǔ)管理系統(tǒng)*|n); printf(|請(qǐng)選擇要執(zhí)行的算法: |n); printf(| 1

10、.最佳適應(yīng)算法 |n); printf(| 2.最差適應(yīng)算法 |n); printf(|*|n); printf(請(qǐng)輸入您的選擇:); scanf(%d,&t);system(cls);/ int i; while(i!=0)printf(|*|n); printf(| 操作菜單如下： |n); printf(| 1.分配空間 2.回收空間 |n); printf(| 3.返回上級(jí) 4.退出 |n); printf(|*|n); scanf(%d,&i);switch(i)case 1:switch(t)case 1:t1=bestfit(); break; case 2: t

11、1=worstfit(); break; default:精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè) printf(選擇算法錯(cuò)誤n); return 1;if(t1)printf(分配空間成功n);else printf(分配空間失敗n);Bsprint();Isprint();break;case 2:t1=recover();if(t1)printf(回收成功n);else printf(回收失敗n);Bsprint();Isprint();break;case 3:goto l1;case 4:exit(0);default: printf(輸入錯(cuò)誤，重新輸入n); return 0;i

12、nt bestfit()/最佳適應(yīng)算法精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)int t=0;readyque D;printf(請(qǐng)輸入進(jìn)程名:n);scanf(%s,D.name);printf(輸入進(jìn)程申請(qǐng)空間大小:n);scanf(%d,&D.size);idly l=Is;idly min=NULL;int mt=100;busy b=Bs;Sort(l);while(l)/在空閑鏈中尋找第一個(gè)大于所輸入的進(jìn)程大小的空閑塊if(D.sizesize)if(D.sizesize;min=l;t=1;mt=mt-D.size;l=l-next;if(mt!=100)/找到第一個(gè)滿

13、足要求的空閑塊busy j;j=(busy)malloc(sizeof(busyspace);/申請(qǐng)分配用于存放進(jìn)程的內(nèi)存空間j-from=min-from;/將第一個(gè)滿足要求的空閑塊（min）的首地址賦給 jfor(int i=0;i=D.namei;j-r.size=D.size;/將所申請(qǐng)的內(nèi)存大小賦給 jwhile(b-next)/按從小到大的順序查找新進(jìn)程在已分配區(qū)中的位置if(b-next-fromfrom)b=b-next;elsebreak;j-next=b-next;b-next=j;/將所輸入的進(jìn)程插入進(jìn)程鏈min-from=min-from+D.size;/

14、改變?cè)摽臻e塊的起始地址min-size=min-size-D.size;/改變?cè)摽臻e塊的剩余大小return t;int worstfit()/最壞適應(yīng)算法int t=0;readyque D; printf(請(qǐng)輸入進(jìn)程名:n); scanf(%s,D.name); printf(輸入進(jìn)程申請(qǐng)空間大小:n); scanf(%d,&D.size);/輸入進(jìn)程申請(qǐng)的空間大小 idly l=Is;/l 指向空閑鏈表 ls 頭 idly min=NULL; int mt=0; busy b=Bs;/b 指向已分配鏈表 Bs 頭 /找到空閑分區(qū)中大小滿足進(jìn)程的請(qǐng)求且尺寸最大的結(jié)點(diǎn)精選優(yōu)質(zhì)文檔-傾

15、情為你奉上專心-專注-專業(yè)while(l)if(D.sizesize)/判斷進(jìn)程所申請(qǐng)的大小是否小于空閑區(qū)的各結(jié)點(diǎn)大小if(l-sizemt)mt=l-size;min=l;/min 指向空閑區(qū)中尺寸最大的結(jié)點(diǎn)t=1;l=l-next;/l 指向空閑鏈表下一個(gè)結(jié)點(diǎn)if(mt!=0)/判斷是否找到了空閑區(qū)的滿足結(jié)點(diǎn)busy j; j=(busy)malloc(sizeof(busyspace); j-from=min-from;for(int i=0;i=D.namei;j-r.size=D.size;while(b-next)/尋找插入到已分配鏈表中的位置if(b-next-fr

16、omfrom)b=b-next; else break; /把此進(jìn)程結(jié)點(diǎn) j 插入到已分配鏈表中精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)j-next=b-next; b-next=j; /修改空閑鏈表的相應(yīng)結(jié)點(diǎn)的參數(shù) min-from=min-from+D.size; min-size=min-size-D.size;return t;int recover()readyque D; printf(請(qǐng)輸入想要回收的進(jìn)程名n); scanf(%s,D.name); busy b=Bs; idly l=Is;while(b-next) /查找輸入的進(jìn)程名是否在已分配鏈表中int yo=1;for

17、(int i=0;i=D.namei)yo=yo*1; else yo=0; /如果在已分配鏈表中則釋放該結(jié)點(diǎn)所占空間if(yo)int t=b-next-from;int ts=b-next-r.size;精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)while(l)if(l-fromt+ts)/所回收進(jìn)程與空閑結(jié)點(diǎn)上下都不鄰接idly tl; tl=(idly)malloc(sizeof(idlyspace); tl-from=t; tl-size=ts; tl-next=l; Is=tl;break;if(l-from=t+ts)/所回收進(jìn)程與空閑結(jié)點(diǎn)下鄰接l-fro

18、m=t; l-size=l-size+ts;busy tb=b-next;b-next=b-next-next;free(tb);return 1;if(l-from+l-sizefrom=t; tl-size=ts; tl-next=l-next; l-next=tl;break;精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)else if(l-from+l-size=t)/所回收進(jìn)程與空閑結(jié)點(diǎn)上鄰接l-size=l-size+ts;if(l-from+l-size=l-next-from)/所回收進(jìn)程與空閑結(jié)點(diǎn)上下都鄰接l-size=l-size+l-next-size; idly tm=l-

19、next; l-next=l-next-next;free(tm);break;l=l-next; /從已分配鏈表中釋放所回收進(jìn)程busy tb=b-next; b-next=b-next-next; free(tb); return 1;b=b-next; printf(沒找到這個(gè)進(jìn)程n);Sort1(l);return 0;idly Sort(idly l)/*遞增排序函數(shù)：入口參數(shù)：鏈表的頭指針，此為鏈表中的排序函數(shù)*/精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)idly p,q;int temp;for(p=l;p!=NULL;p=p-next)for(q=p-next;q!=NULL;

20、q=q-next)if(p-sizeq-size)temp=q-size;q-size=p-size;p-size=temp;return l;idly Sort1(idly l)/*遞增排序函數(shù)：入口參數(shù)：鏈表的頭指針，此為鏈表中的排序函數(shù)*/idly p,q;int temp;for(p=l;p!=NULL;p=p-next)for(q=p-next;q!=NULL;q=q-next)if(p-sizesize)temp=q-size;q-size=p-size;p-size=temp;return l;void Isprint()/輸出空閑表中進(jìn)程的屬性值idly t=Is;printf(-*空閑分區(qū)表*-n); printf(進(jìn)程名tt 起始地址t 大小n);精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè) while(t)printf(%stt%4dtt