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

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

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

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

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

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

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

8、yqueue;typedef struct idlyspace/空閑表結構體精選優質文檔-傾情為你奉上專心-專注-專業int from; int size; idlyspace * next;idlyspace,*idly,*idly1;typedef struct busyspace/已分配鏈表結構體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;精選優質文檔-傾情為你奉上專心-專注-專業 int t,t1;l1: printf(|*歡迎來到動態分區存儲管理系統*|n); printf(|請選擇要執行的算法: |n); printf(| 1

10、.最佳適應算法 |n); printf(| 2.最差適應算法 |n); printf(|*|n); printf(請輸入您的選擇:); scanf(%d,&t);system(cls);/ int i; while(i!=0)printf(|*|n); printf(| 操作菜單如下： |n); printf(| 1.分配空間 2.回收空間 |n); printf(| 3.返回上級 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:精選優質文檔-傾情為你奉上專心-專注-專業 printf(選擇算法錯誤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(輸入錯誤，重新輸入n); return 0;i

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

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

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

15、情為你奉上專心-專注-專業while(l)if(D.sizesize)/判斷進程所申請的大小是否小于空閑區的各結點大小if(l-sizemt)mt=l-size;min=l;/min 指向空閑區中尺寸最大的結點t=1;l=l-next;/l 指向空閑鏈表下一個結點if(mt!=0)/判斷是否找到了空閑區的滿足結點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 插入到已分配鏈表中精選優質文檔-傾情為你奉上專心-專注-專業j-next=b-next; b-next=j; /修改空閑鏈表的相應結點的參數 min-from=min-from+D.size; min-size=min-size-D.size;return t;int recover()readyque D; printf(請輸入想要回收的進程名n); scanf(%s,D.name); busy b=Bs; idly l=Is;while(b-next) /查找輸入的進程名是否在已分配鏈表中int yo=1;for

17、(int i=0;i=D.namei)yo=yo*1; else yo=0; /如果在已分配鏈表中則釋放該結點所占空間if(yo)int t=b-next-from;int ts=b-next-r.size;精選優質文檔-傾情為你奉上專心-專注-專業while(l)if(l-fromt+ts)/所回收進程與空閑結點上下都不鄰接idly tl; tl=(idly)malloc(sizeof(idlyspace); tl-from=t; tl-size=ts; tl-next=l; Is=tl;break;if(l-from=t+ts)/所回收進程與空閑結點下鄰接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;精選優質文檔-傾情為你奉上專心-專注-專業else if(l-from+l-size=t)/所回收進程與空閑結點上鄰接l-size=l-size+ts;if(l-from+l-size=l-next-from)/所回收進程與空閑結點上下都鄰接l-size=l-size+l-next-size; idly tm=l-

19、next; l-next=l-next-next;free(tm);break;l=l-next; /從已分配鏈表中釋放所回收進程busy tb=b-next; b-next=b-next-next; free(tb); return 1;b=b-next; printf(沒找到這個進程n);Sort1(l);return 0;idly Sort(idly l)/*遞增排序函數：入口參數：鏈表的頭指針，此為鏈表中的排序函數*/精選優質文檔-傾情為你奉上專心-專注-專業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)/*遞增排序函數：入口參數：鏈表的頭指針，此為鏈表中的排序函數*/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()/輸出空閑表中進程的屬性值idly t=Is;printf(-*空閑分區表*-n); printf(進程名tt 起始地址t 大小n);精選優質文檔-傾情為你奉上專心-專注-專業 while(t)printf(%stt%4dtt