計算機(jī)操作系統(tǒng)實驗報告 動態(tài)分區(qū)分配方式的模擬

1、計算機(jī)操作系統(tǒng)實驗報告姓名：班級：學(xué)號:題目：動態(tài)分區(qū)分配方式的模擬實習(xí) 內(nèi)容 簡要 描述本次實驗要完成兩部分內(nèi)容：一是用C語言實現(xiàn)對采用首次適應(yīng)算法和最佳適應(yīng)算法的動態(tài)分區(qū)分配過程ALLOC（） 和回收過程FREE（），其中空閑分區(qū)由空閑分區(qū)鏈來管理，進(jìn)行分配時，系統(tǒng)優(yōu)先使用 空閑區(qū)底端空間。一是假設(shè)初始狀態(tài)下，可用內(nèi)存空間為640KB。按照題目要求的作業(yè)順序，以及各個作 業(yè)分配和回收的內(nèi)存空間。分別采用首次適應(yīng)法和最佳適應(yīng)法，對內(nèi)存進(jìn)行分配和回收， 要求每次分配和回收后顯示空閑內(nèi)存分區(qū)鏈的情況。實驗分析算法介紹本次實驗通過用C語言進(jìn)行編程并調(diào)試、運行，形象地表現(xiàn)出動態(tài)分區(qū)的分配方式，直 觀

2、地展現(xiàn)了首次適應(yīng)算法和最佳適應(yīng)算法對內(nèi)存的釋放和回收方式之間的區(qū)別。加深了 我們對兩種算法優(yōu)缺點的理解，幫助我們了解一些數(shù)據(jù)結(jié)構(gòu)和分配算法，進(jìn)一步加深我 們對動態(tài)分區(qū)存儲器管理方式及其實現(xiàn)過程的理解。主要的問題在于，如何解決兩種算 法對內(nèi)存的釋放和回收空間的表示。動態(tài)分區(qū)分配：又稱為可變分區(qū)分配，這種分配方式并不事先先將主存劃分成一塊塊的 分區(qū)，而是在作業(yè)進(jìn)入主存時，根據(jù)作業(yè)的大小動態(tài)地建立分區(qū)。并使分區(qū)的大小正好 適應(yīng)作業(yè)的需要。因此系統(tǒng)中分區(qū)的大小是可變的，分區(qū)的數(shù)目也是可變的。分區(qū)分配算法：（兩者的空閑塊鏈接方式不同）首次適應(yīng)法：為作業(yè)選擇分區(qū)時總是按地址從高到低搜索，只要找到可以容納該

3、作業(yè)的空白塊， 就把該空白塊分配給該作業(yè)。特點：優(yōu)先利用內(nèi)存中底地址部分的空閑分區(qū)（將所有空閑區(qū)，按其地址遞增的順序鏈 接）最佳適應(yīng)算法：接到內(nèi)存申請時，在空閑塊表中找到一個不小于請求的最小空塊進(jìn)行分配;為作業(yè) 選擇分區(qū)時總是尋找其大小最接近于作業(yè)所要求的存儲區(qū)域。特點：用最小空間滿足要求（將所有空閑區(qū)，按其大小遞增的順序聯(lián)接成空閑區(qū)鏈）結(jié)果 分析 （思 考題 解 答； 錯誤 原因 分 析）運行結(jié)果分析：1、參考程序方法1中，用兩個獨立的程序分別實現(xiàn)首次適應(yīng)算法和最佳適應(yīng)算法的分 配和回收過程。首次適應(yīng)算法，在進(jìn)行內(nèi)存分配時，從空閑分區(qū)鏈?zhǔn)组_始順序查找， 能滿足其大小要求的空閑分區(qū)為止。然后，

4、再按照作業(yè)大小，從該分區(qū)中劃出一塊 內(nèi)存空間分配給請求者，余下的空閑分區(qū)仍然留在空閑分區(qū)鏈中。最佳適應(yīng)算法， 在進(jìn)行內(nèi)存分配時，從空閑分區(qū)鏈?zhǔn)组_始順序查找，直至找到第一個能滿足其大小 要求的空閑分區(qū)為止。如果給空閑分區(qū)大于作業(yè)的大小，則從該分區(qū)中劃出一塊內(nèi) 存空間分配給請求者，將剩余空閑區(qū)仍然留在空閑區(qū)分鏈中。當(dāng)作業(yè)運行完成時， 對已使用完的分區(qū)進(jìn)行回收，系統(tǒng)根據(jù)回收分區(qū)的大小及首地址，在空閑分區(qū)鏈中 檢查是否有鄰接的空閑區(qū)，如有相鄰空閑區(qū)則合并成一個大的空閑區(qū)，然后修改有 關(guān)的分區(qū)狀態(tài)信息。2、參考程序方法2中，只用了一個程序來實現(xiàn)整個操作內(nèi)容：首先確定內(nèi)存空間分配 表；然后編寫主函數(shù)實現(xiàn)所

5、需功能；最后分別采用首次和最佳適應(yīng)算法完成內(nèi)存空間的分配和回收。結(jié)果 分析 (思 考題 解 答； 錯誤 原因 分 析)思考題解答：1、首次適應(yīng)算法分配時從表頭指針開始查找可利用空間表，將找到的第一個大小不小 于“請求”的空閑塊的一部分分配給用戶?？衫每臻g表本身既不按節(jié)點的初始地址有 序，也不按節(jié)點的大小有序。用戶釋放內(nèi)存，回收時只是將空閑塊插入在鏈表的表頭即 可。最佳適應(yīng)算法將可利用空間表中一個大小不小于“請求”且最接近“請求”的 空閑塊的一部分分配給用戶。分配與回收都需要對可利用空間表從頭至尾查詢一遍。為 了避免每次分配都要查詢整個鏈表，通常要求節(jié)點從大到小排序，由此只需找到第一個 足夠大

6、的空閑塊即可予以分配。但回收時，必須把回收的空閑塊放置在符合大小順序關(guān) 系的鏈表位置。因此，首次適應(yīng)算法分配和回收的速度更快，用時更少。2、經(jīng)過一段時間的分配回收后，內(nèi)存中存在很多很小的空閑塊。它們每一個都很小， 不足以滿足分配要求；但其總和滿足分配要求。這些空閑塊被稱為碎片。造成存儲資源 的浪費，我們可以通過緊湊技術(shù)來解決，即通過在內(nèi)存移動程序，將所有小的空閑區(qū)域 合并為大的空閑區(qū)域(緊縮技術(shù)，緊致技術(shù)，浮動技術(shù)，搬家技術(shù))。錯誤原因：方法1：直接運行便可得到正確的結(jié)果。方法2：參考程序直接運行會出現(xiàn)llerrors，需改正才能正常運行，其涉及錯誤有：用getch();缺少頭函數(shù):#incl

7、ude ；在程序一開始處缺少函數(shù)定義int wum(long return_pointer,long size,char name)”定義類型出錯，應(yīng)將 long (*test_alloc)();改為 long (*test_alloc)(long alloc_size,char name);。/*首次適應(yīng)算法*/#include stdlib.h”主要代碼結(jié)構(gòu)#include stdio.h”/*定義空閑分區(qū)鏈結(jié)構(gòu)*/ struct Node(附注釋)int num;/*sequence number of work 序列號的工作*/int space;/*space taken up 占用

8、空間*/struct Node *next; /指向下一個節(jié)點的指針域，后向指針 ;typedef struct Node Node;Node *head=NULL; /頭指針，賦空Node *newNode() return (Node*)malloc(sizeof(Node); void init() head=newNode();head-next=NULL;/判斷頭指針的下個節(jié)點是否為空/*內(nèi)存分配*/void ALLOC(int num, int space)Node *p=newNode();/為p分配一個Node類型所占的空間，p指向所分配的內(nèi)存的首 地址Node *q=head

9、-next;Node *s=newNode();Node *n=newNode();if(head-next=NULL)/如果指針指向的下個位置為空則分配p-space=640;p-num=0;主要 代碼 結(jié)構(gòu)（附 注釋）p-next=NULL; /插入尾最后一個結(jié)點head-next=p;if(p-space=space)s=newNode();s-space=space; /賦值數(shù)據(jù)s-num=num;p-space-=space;s-next=p; /把p鏈接到最后一個結(jié)點的nexthead-next=s;return;printf(Out of Memory!n);return;if(

10、q-num=0&q-space=space)s=newNode();s-space=space;s-num=num;q-space-=space;s-next=q; /把q鏈接到最后一個結(jié)點的next head-next=s;return;p=q-next;while(p!=NULL)if(p-num=0)if(p-space=space)n=newNode();n-space=space;n-num=num;p-space-=space;n-next=p; /把p鏈接到最后一個結(jié)點的nextq-next=n; /把n鏈接到最后一個結(jié)點的nextreturn;主要代碼結(jié)構(gòu)p=p-next; /

11、下移（附printf(Out of Memory!n);printf(Outq=q-next; /下移q-num=0;/*表示此段空間已經(jīng)回收*/注 釋)/*內(nèi)存回收*/void FREE(int num)Node *q=head; int i=1;Node *p=head;Node *t=newNode();while(q-num!=num)q=q-next;i+;/*查找有無連續(xù)空閑存儲空間，如果有則回收*/while(p-next!=NULL)if(p-num=0&p-next-num=0)t=p-next;p-next=t-next;p-space+=t-space;free(t);p

12、=p-next;/*查看分配*/void show()int account_space=0;Node *p=newNode();printf(Distribution of memory:n);for(p=head-next;p!=NULL;p=p-next)if(p-num=0)printf(free :%dn,p-space);主要 代碼 結(jié)構(gòu)（附 注釋）elseprintf(work%d:%dn”,p-num,p-space);account_space+=p-space;printf();/*主函數(shù)*/int main()init();/*初始化，建立一個頭指針指向內(nèi)存區(qū)*/ALLO

13、C(1,130); /作業(yè) 1 申請 130KB show();getchar();/*控制顯示,運行時用戶每從鍵盤上輸入一次回車，內(nèi)存分配變化一次*/ALLOC(2,60);show();getchar();ALLOC(3,100);show();getchar();FREE(2);/釋放空間：FREE(p) show();getchar();ALLOC(4,200);show();getchar();FREE(3);show();getchar();主要 代碼 結(jié)構(gòu)（附 注釋）FREE(1);show();getchar();ALLOC(5,140);show();getchar();AL

14、LOC(6,60);show();getchar();ALLOC(7,50);show();getchar();FREE(6);show();printf(nThe end!n);getchar();return 0;/*最佳適應(yīng)算法*/#include stdlib.h#include stdio.h#include /*定義空閑分區(qū)鏈結(jié)構(gòu)*/struct Nodeint num;/*sequence number of work 序列號的工作*/int space;/*space taken up 占用空間*/struct Node *next;/后向指針 ;typedef struct

15、Node Node;Node *head=NULL; /頭指針，賦空Node * array10;/*數(shù)組，用來存放num 0點的指針*/Node * before_array10;/*存放 arrayi對應(yīng)的前一指針*/Node *newNode()return (Node*)malloc(sizeof(Node); /返回帶頭結(jié)點的鏈表void init()head=newNode();head-next=NULL;/*內(nèi)存分配*/void ALLOC(int num, int space)int i=0,j;Node *temp=newNode();Node *p=newNode();N

16、ode *q=head-next;Node *s=newNode();Node *r=newNode();主要 代碼 結(jié)構(gòu)（附 注釋）if(head-next=NULL)p-space=640;p-num=0;p-next=NULL;head-next=p;if(p-space=space)s-space=space;s-num=num;p-space-=space;s-next=p;head-next=s;return;printf(Out of Memory!n);return;p=head;q=p-next;while(q!=NULL)if(q-num=0&q-space=space)a

17、rrayi=q;before_arrayi=p;i+;q=q-next;p=p-next;if(i1)for(j=0;jspacespace)temp=before_arrayj;elsetemp=before_arrayj+1;else主要 代碼 結(jié)構(gòu)（附 注釋）temp=before_array0;r-space=space;r-num=num;temp-next-space-=space;r-next=temp-next;temp-next=r;return;/*內(nèi)存回收*/void FREE(int num)Node *q=head;int i=1;Node *p=head;Node

18、*t=newNode();while(q-num!=num)q=q-next;i+;q-num=0;/*表示此段空間已經(jīng)回收*/*查找有無連續(xù)空閑存儲空間，如果有則回收*/while(p-next!=NULL)if(p-num=0&p-next-num=0)t=p-next;p-next=t-next;p-space+=t-space;free(t);p=p-next;/*查看分配*/void show()主要代碼結(jié)構(gòu)（附注釋）int account_space=0;Node *p=newNode();printf(Distribution of memory:n);for(p=head-ne

19、xt;p!=NULL;p=p-next)if(p-num=0)printf(free :%dn,p-space);elseprintf(work%d:%dn”,p-num,p-space);account_space+=p-space;printf(/*主函數(shù)*/int main()/*初始化，建立一個頭指針指向內(nèi)存區(qū)*/*控制顯示,運行時用戶每從鍵盤上輸入一次回車，內(nèi)存分配變init();ALLOC(1,130); show(); getchar();化一次*/ALLOC(2,60);show(); getchar();ALLOC(3,100);show(); getchar();FREE(

20、2); show();getchar();ALLOC(4,200); show();getchar();FREE(3);show();getchar();FREE(1); show();getchar();ALLOC(5,140);show(); getchar();ALLOC(6,60);show(); getchar();ALLOC(7,50);主要代碼結(jié)構(gòu)show(); getchar();FREE(6);show();（附注釋）printf(nThe end!n); getchar();return 0;運行結(jié)果：Distribution of memory: work1:130 free :510Distribution of memory: work1:13