《操作系統(tǒng)》課程設(shè)計(jì)動(dòng)態(tài)分區(qū)管理的主存分配模擬設(shè)計(jì)最優(yōu)適應(yīng)法、最差適應(yīng)法

1、武漢理工大學(xué)操作系統(tǒng)課程設(shè)計(jì)任務(wù)書附件1：學(xué) 號(hào)： 0120910340719課 程 設(shè) 計(jì)題 目動(dòng)態(tài)分區(qū)管理的主存分配模擬設(shè)計(jì)-最優(yōu)適應(yīng)法、最差適應(yīng)法學(xué) 院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 專 業(yè)計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)班 級(jí)0907姓 名xxxx指導(dǎo)教師羅 芳2012年1月11日課程設(shè)計(jì)任務(wù)書學(xué)生姓名： xxxx 專業(yè)班級(jí)： 計(jì)科0907 指導(dǎo)教師： 羅 芳 工作單位： 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 題 目: 動(dòng)態(tài)分區(qū)管理的主存分配模擬設(shè)計(jì)-最優(yōu)適應(yīng)法、最差適應(yīng)法初始條件：1預(yù)備內(nèi)容：閱讀操作系統(tǒng)的內(nèi)存管理章節(jié)內(nèi)容，理解動(dòng)態(tài)分區(qū)的思想，并體會(huì)各分配算法的具體實(shí)施方法。2實(shí)踐準(zhǔn)備：掌握一種計(jì)算機(jī)高級(jí)語言的使用。要求

2、完成的主要任務(wù): （包括課程設(shè)計(jì)工作量及其技術(shù)要求，以及說明書撰寫等具體要求）1采用指定算法模擬動(dòng)態(tài)分區(qū)管理方式的主存分配。能夠處理以下的情形： 隨機(jī)出現(xiàn)的進(jìn)程i申請(qǐng)jkb內(nèi)存，程序能判斷是否能分配，如果能分配，要求輸出分配的首地址faddress，并要求輸出內(nèi)存使用情況和空閑情況。內(nèi)存情況輸出的格式為：faddress該分區(qū)的首地址；eaddress該分區(qū)的尾地址len 分區(qū)長度；process 如果使用，使用的進(jìn)程號(hào)，否則為0 主存分配函數(shù)實(shí)現(xiàn)尋找空閑區(qū)、空閑區(qū)表的修改、已分配區(qū)表的修改功能；2設(shè)計(jì)報(bào)告內(nèi)容應(yīng)說明： 課程設(shè)計(jì)目的與功能； 需求分析，數(shù)據(jù)結(jié)構(gòu)或模塊說明(功能與框圖)； 源程序

3、的主要部分； 運(yùn)行結(jié)果與運(yùn)行情況分析； 自我評(píng)價(jià)與總結(jié)：i）你認(rèn)為你完成的設(shè)計(jì)哪些地方做得比較好或比較出色；ii）什么地方做得不太好，以后如何改正；iii）從本設(shè)計(jì)得到的收獲（在編寫，調(diào)試，執(zhí)行過程中的經(jīng)驗(yàn)和教訓(xùn)）；iv）完成本題是否有其他的其他方法（如果有，簡要說明該方法）；v）對(duì)實(shí)驗(yàn)題的評(píng)價(jià)和改進(jìn)意見，請(qǐng)你推薦設(shè)計(jì)題目。時(shí)間安排：設(shè)計(jì)安排一周：周1、周2：完成程序分析及設(shè)計(jì)。周2、周3：完成程序調(diào)試及測(cè)試。周4、周5：驗(yàn)收、撰寫課程設(shè)計(jì)報(bào)告。（注意事項(xiàng)：嚴(yán)禁抄襲，一旦發(fā)現(xiàn)，抄與被抄的一律按0分記）指導(dǎo)教師簽名： 年 月 日系主任（或責(zé)任教師）簽名： 年 月 日一、題目動(dòng)態(tài)分區(qū)管理的主存分配

4、模擬設(shè)計(jì)-最優(yōu)適應(yīng)法、最差適應(yīng)法二、主要任務(wù)1采用指定算法模擬動(dòng)態(tài)分區(qū)管理方式的主存分配。能夠處理以下的情形： 隨機(jī)出現(xiàn)的進(jìn)程i申請(qǐng)jkb內(nèi)存，程序能判斷是否能分配，如果能分配，要求輸出分配的首地址faddress，并要求輸出內(nèi)存使用情況和空閑情況。內(nèi)存情況輸出的格式為：faddress該分區(qū)的首地址；eaddress該分區(qū)的尾地址len 分區(qū)長度；process 如果使用，使用的進(jìn)程號(hào)，否則為0 主存分配函數(shù)實(shí)現(xiàn)尋找空閑區(qū)、空閑區(qū)表的修改、已分配區(qū)表的修改功能；2設(shè)計(jì)報(bào)告內(nèi)容應(yīng)說明： 課程設(shè)計(jì)目的與功能； 需求分析，數(shù)據(jù)結(jié)構(gòu)或模塊說明(功能與框圖)； 源程序的主要部分； 運(yùn)行結(jié)果與運(yùn)行情況分

5、析； 自我評(píng)價(jià)與總結(jié)：i）你認(rèn)為你完成的設(shè)計(jì)哪些地方做得比較好或比較出色；ii）什么地方做得不太好，以后如何改正；iii）從本設(shè)計(jì)得到的收獲（在編寫，調(diào)試，執(zhí)行過程中的經(jīng)驗(yàn)和教訓(xùn)）；iv）完成本題是否有其他的其他方法（如果有，簡要說明該方法）；v）對(duì)實(shí)驗(yàn)題的評(píng)價(jià)和改進(jìn)意見，請(qǐng)你推薦設(shè)計(jì)題目。三、原理1.最佳適應(yīng)算法:最佳適應(yīng)算法要求從小到大的次序組成空閑區(qū)可用表或自由鏈。當(dāng)用戶作業(yè)或進(jìn)程申請(qǐng)一個(gè)空閑區(qū)時(shí)，存儲(chǔ)管理程序從表頭開始查找，當(dāng)找到第一個(gè)滿足要求的空閑區(qū)時(shí)，停止查找。如果該空閑區(qū)大于請(qǐng)求表中的請(qǐng)求長度，則與最先適應(yīng)法時(shí)相同，將減去請(qǐng)求長度后的剩余空閑區(qū)部分留在可用表中。2.最壞適應(yīng)算法：

6、最壞適應(yīng)算法要求空閑區(qū)按其大小遞減的順序組成空閑區(qū)可用表或自由鏈。當(dāng)用戶作業(yè)或進(jìn)程申請(qǐng)一個(gè)空閑區(qū)時(shí)，先檢查空閑區(qū)可用邊或自由鏈的第一個(gè)空閑可用區(qū)的大小是否大于或等于所要求的內(nèi)存長度，若可用表或自由鏈的第一個(gè)項(xiàng)長度小于所要求的，則分配失敗，否則從空閑區(qū)可用表或自由鏈中分配相應(yīng)的存儲(chǔ)空間給用戶，然后修改和調(diào)整空閑區(qū)可用表或自由鏈。四、實(shí)驗(yàn)需求分析存儲(chǔ)器是計(jì)算機(jī)系統(tǒng)的重要資源之一,存儲(chǔ)空間是操作系統(tǒng)管理的寶貴資源,雖然其容量在不斷擴(kuò)大,但仍然遠(yuǎn)遠(yuǎn)不能滿足軟件發(fā)展的需要。對(duì)存儲(chǔ)資源進(jìn)行有效的管理,不僅關(guān)系到存儲(chǔ)器的利用率,而且還對(duì)操作系統(tǒng)的性能和效率有很大的影響。分區(qū)管理是把內(nèi)存劃分為若干大小不等的區(qū)

7、域，除操作系統(tǒng)占用一個(gè)區(qū)域外，其余由多道環(huán)境下的各并發(fā)進(jìn)程共享。動(dòng)態(tài)分區(qū)法在作業(yè)執(zhí)行前并不建立分區(qū)，分區(qū)的建立是在作業(yè)的處理過程中進(jìn)行的，且大小可隨作業(yè)或進(jìn)程對(duì)內(nèi)存的要求而改變。采用動(dòng)態(tài)分區(qū)法，在系統(tǒng)初啟時(shí)，除了操作系統(tǒng)中常駐的內(nèi)存部分外，只有一個(gè)空閑區(qū)。隨后，分配的程序?qū)⒃搮^(qū)依次劃給調(diào)度選中的作業(yè)或進(jìn)程。下圖給出了fifo調(diào)度方式時(shí)內(nèi)存的初始分配情況：進(jìn)程a 8k進(jìn)程b16k進(jìn)程c64k進(jìn)程d124k. os進(jìn)程a進(jìn)程b進(jìn)程c進(jìn)程d os進(jìn)程a進(jìn)程b進(jìn)程 os進(jìn)程a進(jìn)程b os進(jìn)程a五、實(shí)驗(yàn)功能設(shè)計(jì)1.數(shù)據(jù)結(jié)構(gòu)說明本實(shí)驗(yàn)用到了結(jié)構(gòu)體和類兩種數(shù)據(jù)結(jié)構(gòu)：結(jié)構(gòu)體定義如下：struct tableu

8、nionint head;int cnt;int end;table* next; ;其中定義了四個(gè)數(shù)據(jù)成員，分別為：head（分區(qū)的首地址）、cnt（結(jié)構(gòu)體指針的計(jì)數(shù)）、end（分區(qū)的尾地址）、table*next（指向下一節(jié)點(diǎn)的指針）。由此可以計(jì)算出分區(qū)的長度為：end-head。內(nèi)存分配如下： 首地址尾地址分區(qū)大小 0 50 50 150 200 50 300 400 100 410 480 70類定義如下：class areaalloc public:int initmemblock();areaalloc(); areaalloc(); public:table* findleast

9、(int flag,int i);void change(int i,table*p);void sort(int flag);int fit(int flag, int memsize);table* m_head;2.函數(shù)模塊說明本程序主要由類areaalloc的成員函數(shù)實(shí)現(xiàn)，其成員函數(shù)的說明如下：構(gòu)造函數(shù)areaalloc:areaalloc() 析構(gòu)函數(shù)areaalloc:areaalloc() 成員函數(shù)initmemblock（）將給定的結(jié)構(gòu)體數(shù)組鏈入鏈表，其基本定義如下：int areaalloc:initmemblock()table mt = 數(shù)組定義部分 ;m_head =

10、new table;memset(m_head,0,sizeof(table);table*head = m_head;for(int i = 0 ; i head = mti.head;p-end = mti.end;head-next = p;head = p;m_head-cnt +; head-next = null; return 1;成員函數(shù)fit(int flag,int memsize) ，功能：根據(jù)flag的值決定是采用最優(yōu)還是最差分區(qū)的分配方法給所要求的進(jìn)程分配內(nèi)存，當(dāng)flag=0時(shí)采用最優(yōu)分配，當(dāng)flag=1時(shí)采用最差分配。其函數(shù)的定義如下：int areaalloc:f

11、it(int flag,int memsize) /flag=0 最優(yōu)分配 if(flag = 0)/最優(yōu) sort(0); else /最差 sort(1); int len = m_head-cnt;table* p = m_head-next; for(int i = 0 ; i end - p-head) = memsize) if(p-end - p-head) = memsize) /將該內(nèi)存塊從可用內(nèi)存塊中移除table* beforp = m_head;while(beforp) if(beforp-next = p) table* delp = p;int ret = p-h

12、ead;beforp-next = p-next;delete delp;m_head-cnt -;return ret; beforp = beforp-next; else /截取所需大小 調(diào)整可用表 int ret = p-head;p-head = p-head+memsize;return ret; p = p-next; return -1; 成員函數(shù)findleast(int flag, int i)，根據(jù)標(biāo)志位flag的值來決定是找出第i位之后的最大值還是最小值，當(dāng)flag=0時(shí)，找出最大值，當(dāng)flag=1時(shí)，找出最小值。其定義如下：table* areaalloc:findl

13、east(int flag, int i)table*pleast = m_head;for(int j = 0; j next;table *p = pleast-next;while(p)if(flag = 0)/從小到大if(p-end - p-head end - pleast-head)pleast = p;else /從大到小if(p-end - p-head pleast-end - pleast-head)pleast = p;p = p-next;return pleast;成員函數(shù)change(int i, table *p)，交換函數(shù)，交換第i個(gè)數(shù)和第p個(gè)，其定義如下：v

14、oid areaalloc:change(int i, table *p)/交換第i個(gè)數(shù)和第p個(gè)table*pi = m_head-next;for(int j = 0; j next;if(pi = p)return;table tmp;tmp.head = p-head;tmp.end = p-end;p-head = pi-head;p-end = pi-end;pi-head = tmp.head;pi-end = tmp.end;成員函數(shù)sort(int flag)根據(jù)標(biāo)志位flag決定是采用哪種方法排序，當(dāng)flag=0時(shí)采用從大到小的順序排序，當(dāng)flag=1時(shí)采用從小到大的順序排序

15、，其定義如下：void areaalloc:sort(int flag)/flag = 0根據(jù)關(guān)鍵字 從小到大排序 1 從大到小 int len = m_head-cnt;for(int i = 1; i cnt;table *p = ma.m_head-next;coutsetw(8)起始地址setw(8) 結(jié)束地址setw(12)分區(qū)大 小endl;for(int i = 0 ; i cnt; i+)coutsetw(8)head setw(8)endsetw(12)end - p-headnext;3.程序的流程圖最優(yōu)適應(yīng)法和最差適應(yīng)法的流程圖一樣，如下： 請(qǐng)求size大小的分區(qū)從空閑區(qū)

16、表第一表目順序查找表目查完？ 是無法分配 否該空閑區(qū)的長度size？取下一表項(xiàng) 否 是該空閑區(qū)的長度=size？從該空閑表中截取所需大小，修改調(diào)整可用表 否 是從可用表中移去該表目，調(diào)整可用表 返回分配起始地址六、開發(fā)平臺(tái)本程序開發(fā)平臺(tái)為microsoft visual c+ 6.0七、源代碼#include #include using namespace std; #includestdlib.htypedef struct area int start; int length; int state; struct area *next;area,*parea;area *head;con

17、st int max=255;void printmemorystate(area *);void bestfit(area *);void worstfit(area *);void init();void main() int choice; /開始循環(huán) while(1) system(cls);init();printmemorystate(head); printf(1.最優(yōu)適應(yīng)法;2.最差適應(yīng)法;0.退出程序n); scanf(%d,&choice);/輸入你所要的選項(xiàng)。為choice 的值 switch(choice) case 0: printf(the system is sh

18、utdown. n); exit(0);case 1: bestfit(head); printmemorystate(head);/最優(yōu)適應(yīng)法break;case 2: worstfit(head);printmemorystate(head);/最差適應(yīng)法 break; default: printf(please input a right number!n); break; system(pause); void init() area *work; area *p;area *p1;area *p2;area *p3;area *p4;area *p5; /int start;del

19、ete head; head=(area *)malloc(sizeof(area);/分配頭指針/extern void *malloc(unsigned int num_bytes)功能：分配長度為num_bytes字節(jié)的內(nèi)存塊 work=(area *)malloc(sizeof(area); head-start=0; head-length=0; head-state=0; head-next=null; /裝入系統(tǒng) printf(.正在載入系統(tǒng)中.n); work-start=0;work-length=1;work-next=null;work-state=0; head-nex

20、t=work; p=(area *)malloc(sizeof(area); p-start=1;p-length=32;/p-next=null;p-state=0; work-next=p;p1=(area *)malloc(sizeof(area); p1-start=33;p1-length=16;/p1-next=null;p1-state=0; p-next=p1;p2=(area *)malloc(sizeof(area); p2-start=49;p2-length=8;/p2-next=null;p2-state=0; p1-next=p2;p3=(area *)malloc

21、(sizeof(area); p3-start=57;p3-length=4;/p3-next=null;p3-state=0; p2-next=p3; p4=(area *)malloc(sizeof(area); p4-start=61;p4-length=64;/p4-next=null;p4-state=0; p3-next=p4; p5=(area *)malloc(sizeof(area); p5-start=125;p5-length=max-125;p5-next=null;p5-state=0; p4-next=p5;void printmemorystate(area *h

22、ead) int state=-1; area *temp=(area *)malloc(sizeof(area); temp=head-next; printf(t起始地址t內(nèi)存長度t內(nèi)存狀態(tài)n);do printf(t%8dt%8dt%8dn,temp-start,temp-length,temp-state); temp=temp-next; while(temp!=null); return ;void worstfit(area *head)/裝入作業(yè),最差適應(yīng)法 int lengthtemp;int a3; area *last=null; area *newfree=null;i

23、nt i;int name=0;cout請(qǐng)分別輸入需要分配內(nèi)存的3個(gè)作業(yè)內(nèi)存長度:endl;for(i=1;i=3;i+)cout進(jìn)程iai-1;for(i=0;inext;task=null;while(last!=null)if(last-state0)last=last-next;elseif(task=null)task=last;if(last-lengthtask-length)task=last;last=last-next;/task指向length最大的那塊if(aitask-length)coutai 作業(yè)過長，無法裝入 length=ai)task-state=i+1;/

24、等于的話直接裝入if(task-lengthai)lengthtemp=task-length;task-length=ai;task-state=i+1;newfree=(area *)malloc(sizeof(area);newfree-next=task-next;newfree-start=task-start+task-length;newfree-length=lengthtemp-task-length;newfree-state=0;task-next=newfree;/成功插入newfree節(jié)點(diǎn)void bestfit(area *head)/裝入作業(yè),最優(yōu)適應(yīng)法 int

25、flag=0; int lengthtemp;int a3; area *last=null; area *newfree=null;area *h=null;int i;cout請(qǐng)分別輸入需要分配內(nèi)存的3個(gè)作業(yè)內(nèi)存長度:endl;for( i=1;i=3;i+)cout進(jìn)程iai-1;for(i=0;inext;p=head-next;h=head-next;while(h!=null)if(h-state0)h=h-next;elsebn=h-length;h=h-next;n+;sum=b0;for(int j=1;jn;j+)if(sumsum)coutai 作業(yè)過長，無法裝入 sta

26、te0)last=last-next;elseif(ailast-length)last=last-next;else if(ai=last-length)task=last;task-state=i;break;else if(ailength)if(task=null)task=last;else if(task-lengthlast-length)task=last;last=last-next;if(task-lengthai)lengthtemp=task-length; task-length=ai;task-state=i+1;newfree=(area *)malloc(siz

27、eof(area);newfree-next=task-next;newfree-start=task-start+task-length;newfree-length=lengthtemp-task-length;newfree-state=0;task-next=newfree;/成功插入newfree節(jié)點(diǎn)八、運(yùn)行結(jié)果與運(yùn)行情況分析編寫源程序，編譯無誤之后運(yùn)行得到如下界面： 首先采用最優(yōu)適應(yīng)方法，輸入1之后，要求分別輸入需要分配內(nèi)存的3個(gè)作業(yè)的內(nèi)存長度得到如下界面：回車后得到的結(jié)果如下：由于多次隨機(jī)分配之后所剩的空閑區(qū)的長度越來越小，經(jīng)過幾次最優(yōu)適應(yīng)法之后分配之后，空閑區(qū)的長度可能不滿足分配的要求，得到如下界面： 之后采用最差適應(yīng)法進(jìn)行分配，得到如下界面：同理，由于所剩的空閑區(qū)的長度越來越小，可能出現(xiàn)空閑區(qū)的長度滿足所要求的長度，得到如下界面：九、自我評(píng)價(jià)與總結(jié)1.你認(rèn)為你完成的設(shè)計(jì)哪些地方做得比較好或比較出色. 實(shí)驗(yàn)?zāi)軌蚝芎玫暮筒僮飨到y(tǒng)的理論結(jié)合起來，驗(yàn)證最優(yōu)適應(yīng)法、最壞適應(yīng)法的流程和優(yōu)缺點(diǎn)，程序中用鏈表分別將空閑區(qū)和進(jìn)程連接起來，這樣更加方便分配內(nèi)存后把所剩的內(nèi)存碎片連接起來，同時(shí)用指針很方便的進(jìn)行對(duì)進(jìn)程分配內(nèi)存塊。另外所有進(jìn)程都是隨機(jī)產(chǎn)生的，