分區(qū)式存儲(chǔ)管理

1、操作系統(tǒng)設(shè)計(jì)性實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)題目： 分區(qū)式存儲(chǔ)管理 學(xué) 號(hào)： 姓 名： 完成時(shí)間： 一、實(shí)驗(yàn)概述1.1 實(shí)驗(yàn)?zāi)康?.通過(guò)本次實(shí)驗(yàn)，加深對(duì)內(nèi)存管理的認(rèn)識(shí)，進(jìn)一步掌握內(nèi)存的分配、回收算法的思想。2.通過(guò)本次實(shí)驗(yàn)，加深掌握對(duì)數(shù)據(jù)結(jié)構(gòu)的理解和進(jìn)一步提高自己的編程能力。1.2 任務(wù)描述設(shè)計(jì)程序模擬內(nèi)存的動(dòng)態(tài)分區(qū)法存儲(chǔ)管理。內(nèi)存空閑區(qū)使用自由鏈管理，采用最壞適應(yīng)算法從自由鏈中尋找空閑區(qū)進(jìn)行分配，內(nèi)存回收時(shí)假定不做與相鄰空閑區(qū)的合并。假定系統(tǒng)的內(nèi)存共640K，初始狀態(tài)為操作系統(tǒng)本身占用64K。在t1時(shí)間之后，有作業(yè)A、B、C、D分別請(qǐng)求8K、16K、64K、124K的內(nèi)存空間；在t2時(shí)間之后，作業(yè)C完成；在t

2、3時(shí)間之后，作業(yè)E請(qǐng)求50K的內(nèi)存空間；在t4時(shí)間之后，作業(yè)D完成。要求編程序分別輸出t1、t2、t3、t4時(shí)刻內(nèi)存的空閑區(qū)的狀態(tài)。二、主要數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)1. 程序中自由鏈隊(duì)列的結(jié)點(diǎn)類(lèi)型可描述如下： struct freelinkint len, address; /* len為分區(qū)長(zhǎng)度；address為分區(qū)起始地址struct freelink /* next;2. 內(nèi)存占用區(qū)用鏈表描述，其結(jié)點(diǎn)類(lèi)型描述如下： struct busylinkchar name; /* 作業(yè)或進(jìn)程名 name=S 表示OS占用int len , address;struct busylink *next; 3.設(shè)

3、全程量：struct freelink *free_head=NULL; / 自由鏈隊(duì)列（帶頭結(jié)點(diǎn)）隊(duì)首指針 struct busylink *busy_head=NULL, / 占用區(qū)隊(duì)列隊(duì)（帶頭結(jié)點(diǎn)）首指針 struct busylink *busy_tail=NULL； / 占用區(qū)隊(duì)列隊(duì)尾指針三、主要函數(shù)設(shè)計(jì)1函數(shù)名稱(chēng): requireMemo(char name, int require)功能描述：在空閑區(qū)域鏈中找到第一個(gè)滿足條件的結(jié)點(diǎn)，將其分配掉，如果結(jié)點(diǎn)的長(zhǎng)度大于require，則剩下的又將作為一個(gè)空閑結(jié)點(diǎn)插入到空閑區(qū)域鏈中 輸入?yún)?shù)：char name, int require輸

4、出參數(shù)：無(wú)程序流程圖： 2函數(shù)名稱(chēng)：void freeMemo(char name) 功能描述：找到要回收的結(jié)點(diǎn)，將其釋放，并將這個(gè)結(jié)點(diǎn)重新插入到空閑區(qū)域鏈中去 輸入?yún)?shù)：char name 輸出參數(shù)：無(wú) 程序流程圖：將w插入到空閑區(qū)域鏈中時(shí)前的歸并算法的流程圖如下：四、測(cè)試數(shù)據(jù)及運(yùn)行結(jié)果41 測(cè)試數(shù)據(jù)準(zhǔn)備假定系統(tǒng)的內(nèi)存共640K，初始狀態(tài)為操作系統(tǒng)本身占用64K。在t1時(shí)間之后，有作業(yè)A、B、C、D分別請(qǐng)求8K、16K、64K、124K的內(nèi)存空間；在t2時(shí)間之后，作業(yè)C完成；在t3時(shí)間之后，作業(yè)E請(qǐng)求50K的內(nèi)存空間；在t4時(shí)間之后，作業(yè)D完成。要求編程序分別輸出t1、t2、t3、t4時(shí)刻內(nèi)

5、存的空閑區(qū)的狀態(tài)。42 運(yùn)行結(jié)果及說(shuō)明1.測(cè)試目標(biāo):運(yùn)用按最佳適應(yīng)算法1（空閑區(qū)未歸并時(shí)的）運(yùn)行結(jié)果:2.測(cè)試目標(biāo):運(yùn)用按最佳適應(yīng)算法（空閑區(qū)歸并時(shí)的）運(yùn)行結(jié)果: 五、實(shí)驗(yàn)總結(jié) 首先，對(duì)鏈表又有進(jìn)一步的理解，還有就是加深理解內(nèi)存的分配與回收，分配與回收的策略，并掌握動(dòng)態(tài)分區(qū)這種內(nèi)存管理的具體實(shí)施方法。 再者，就是在編程中遇到的困難，在編寫(xiě)歸并程序首先是自己考慮問(wèn)題不全面，寫(xiě)的程序就只顧及到一個(gè)結(jié)點(diǎn)，而沒(méi)有實(shí)現(xiàn)有兩個(gè)結(jié)點(diǎn)的情況，于是后來(lái)再加了一條else語(yǔ)句，就沒(méi)有出現(xiàn)問(wèn)題。還有一個(gè)問(wèn)題就是將多余的結(jié)點(diǎn)free時(shí)也出現(xiàn)問(wèn)題，加了一條if(s=NULL）,成立就釋放掉。一開(kāi)始把free語(yǔ)句寫(xiě)在wh

6、ile循環(huán)內(nèi)，一旦把找到的結(jié)點(diǎn)釋放掉，則找不到下一個(gè)結(jié)點(diǎn)，也會(huì)出錯(cuò)，所以應(yīng)該把free放到while循環(huán)外。六、參考文獻(xiàn) 1 附：程序源代碼按最先適應(yīng)算法#include <unistd.h>#include<stdio.h>#include<stdlib.h>struct freelinkint len, address; / len為分區(qū)長(zhǎng)度；address為分區(qū)起始地址struct freelink * next; /內(nèi)存占用區(qū)用鏈表描述，其結(jié)點(diǎn)類(lèi)型描述如下：struct busylinkchar name; / 作業(yè)或進(jìn)程名 name='S&

7、#39; 表示OS占用int len , address;struct busylink *next; ;/并設(shè)全程量：struct freelink *free_head=NULL; / 自由鏈隊(duì)列帶頭結(jié)點(diǎn)）隊(duì)首指針? struct busylink *busy_head=NULL, *busy_tail=NULL; / 占用區(qū)隊(duì)列隊(duì)（帶頭結(jié)點(diǎn)）首指針 / 占用區(qū)隊(duì)列隊(duì)尾指針/ 設(shè)計(jì)子函數(shù)：void start(void) /* 設(shè)置系統(tǒng)初始狀態(tài)*/ struct freelink * p; struct busylink *q; free_head=(struct freelink*)ma

8、lloc(sizeof(struct freelink); free_head->next=NULL; / 創(chuàng)建自由鏈頭結(jié)點(diǎn)busy_head=busy_tail=(struct busylink*)malloc(sizeof(struct busylink); busy_head->next=NULL; / 創(chuàng)建占用鏈頭結(jié)點(diǎn) p=( struct freelink *)malloc(sizeof(struct freelink);p->address=64;p->len=640-64; /（OS占用了64K）p->next=NULL; free_head->

9、;next=p;q=( struct busylink *)malloc(sizeof(struct busylink);q->name='S' /* S表示操作系統(tǒng)占用 */q->len=64; q->address=0; q->next=NULL;busy_head->next=q; busy_tail=q;void requireMemo(char name, int require) /*模擬內(nèi)存分配*/struct freelink *w,*u,*v,*x,*y;struct busylink *p;x=free_head;y=free_

10、head->next;while(y!=NULL) &&(y->len<require) /找到第一個(gè)滿足條件的空閑區(qū)x=y;y=y->next;if(y!=NULL)p=(struct busylink*)malloc(sizeof(busylink);p->name=name;p->address=y->address;p->len=require; p->next=NULL;busy_tail->next=p; /把p插入到busy_head的尾部busy_tail=p;w=x->next;x->ne

11、xt=w->next;if(w->len=require)free(w);elsew->address=w->address+require;w->len=w->len-require;u=free_head;v=free_head->next;while(v!=NULL) && (v->len<w->len)/如果此結(jié)點(diǎn)還有多余，就此又重新插入到空閑區(qū)域鏈中（按照長(zhǎng)度由小到大的次序排列）u=v;v=v->next;u->next=w;w->next=v;else printf("can&#

12、39;t allocate!n");void freeMemo(char name) /* 模擬內(nèi)存回收*/ struct busylink *p,*q;struct freelink *w,*u,*v,*s1=NULL,*s2=NULL;int len,address;int flag1=1,flag2=1;p=busy_head->next;while(p!=NULL)&&(p->name!=name) /找到要回收的結(jié)點(diǎn)q=p;p=p->next;if(p=NULL)printf("%c is not existn",nam

13、e);elseif (p=busy_tail) busy_tail=q;q->next=p->next;len=p->len;address=p->address;free(p);w=(struct freelink*) malloc(sizeof(freelink);w->len=len;w->address=address;u=free_head;v=free_head->next;while(v!=NULL) && (flag1=1 | flag2=1) /歸并算法if(w->address=(v->address+v

14、->len) &&flag1) s1=v;u->next=s1->next;w->address=v->address;w->len+=v->len; v=v->next;flag1=0; else if(w->address+w->len)=v->address) &&flag2)s2=v;u->next=s2->next;w->len+=v->len;v=v->next;flag2=0;elseu=v;v=v->next;if(s1!=NULL)free(s

15、1);if(s2!=NULL)free(s2);u=free_head;v=free_head->next;if(v!=NULL)while(v!=NULL) && (v->len<w->len)u=v;v=v->next;u->next=w;w->next=v;void past(int time) /* 模擬系統(tǒng)過(guò)了時(shí)間time，用sleep(),或者用個(gè)空循環(huán)*/sleep(5);printf("時(shí)間%d后：n",time);void printlink() /* 輸出內(nèi)存空閑情況（自由鏈的結(jié)點(diǎn)） */ str

16、uct freelink *p;p=free_head->next;if(p=NULL) printf("無(wú)空閑區(qū)！n");else while(p!=NULL) printf("首地址:%dt長(zhǎng)度:%dn",p->address,p->len);p=p->next; printf("-n");void printlink1() /* 輸出內(nèi)存占用的情況 */ struct busylink *p;p=busy_head->next;if(p=NULL) printf("無(wú)內(nèi)存占有區(qū)！n&quo

17、t;);else while(p!=NULL) printf("名字:%ct首地址:%dt長(zhǎng)度:%dn",p->name,p->address,p->len);p=p->next; /設(shè)計(jì)主函數(shù)：int main() start();past(5);requireMemo('A',8); requireMemo('B',16); requireMemo('C',64); requireMemo('D',124);printf("內(nèi)存占用區(qū)為：n");printlink1();printf("內(nèi)存空閑區(qū)為:n");printlink();past(10);freeMemo('C');printf("內(nèi)存占用區(qū)為：n");printlink1();printf(&qu