實(shí)驗(yàn)二：存儲(chǔ)器的分配與回收算法實(shí)現(xiàn)

1、人和以吟實(shí)驗(yàn)報(bào)告學(xué)院（系）名稱(chēng)： 計(jì)算機(jī)與通信工程學(xué)院姓名劉俊杰學(xué)號(hào)20115542專(zhuān)業(yè)信息與計(jì)算科學(xué)班級(jí)2011級(jí)1班實(shí)驗(yàn)項(xiàng)目實(shí)驗(yàn)二：存儲(chǔ)器的分配與回收算法實(shí)現(xiàn)課程名稱(chēng)操作系統(tǒng)課程代碼0668036實(shí)驗(yàn)時(shí)間2013-11-27 3-4 節(jié) 2013-11-29 7-8 節(jié) 2013-12-4 3-4 節(jié) 2013-12-6 7-8 節(jié)實(shí)驗(yàn)地點(diǎn)主校區(qū)7-215批改意見(jiàn)成績(jī)教師簽字：實(shí)驗(yàn)內(nèi)容：1. 本實(shí)驗(yàn)是模擬操作系統(tǒng)的主存分配，運(yùn)用可變分區(qū)的存儲(chǔ)管理算法設(shè)計(jì)主存分配和回收程序，并不 實(shí)際啟動(dòng)裝入作業(yè)。2. 采用最先適應(yīng)法、最佳適應(yīng)法、最壞適應(yīng)法分配主存空間。3. 當(dāng)一個(gè)新作業(yè)要求裝入主存時(shí)，必

2、須查空閑區(qū)表，從中找出一個(gè)足夠大的空閑區(qū)。若找到的空閑區(qū) 大于作業(yè)需要量，這是應(yīng)把它分成二部分，一部分為占用區(qū)，加一部分又成為一個(gè)空閑區(qū)。4. 當(dāng)一個(gè)作業(yè)撤離時(shí)，歸還的區(qū)域如果與其他空閑區(qū)相鄰，則應(yīng)合并成一個(gè)較大的空閑區(qū)，登在空閑 區(qū)表中。5. 設(shè)計(jì)的模擬系統(tǒng)中，進(jìn)程數(shù)不小于5,進(jìn)程調(diào)度方式可以采用實(shí)驗(yàn)一中的任何一種。6. 運(yùn)行所設(shè)計(jì)的程序，輸出有關(guān)數(shù)據(jù)結(jié)構(gòu)表項(xiàng)的變化和內(nèi)存的當(dāng)前狀態(tài)。 實(shí)驗(yàn)要求：1. 詳細(xì)描述實(shí)驗(yàn)設(shè)計(jì)思想、程序結(jié)構(gòu)及各模塊設(shè)計(jì)思路；2. 詳細(xì)描述程序所用數(shù)據(jù)結(jié)構(gòu)及算法；3. 明確給出測(cè)試用例和實(shí)驗(yàn)結(jié)果；4. 為增加程序可讀性，在程序中進(jìn)行適當(dāng)注釋說(shuō)明；5. 認(rèn)真進(jìn)行實(shí)驗(yàn)總結(jié)，

3、包括：設(shè)計(jì)中遇到的問(wèn)題、解決方法與收獲等；6. 實(shí)驗(yàn)報(bào)告撰寫(xiě)要求結(jié)構(gòu)清晰、描述準(zhǔn)確邏輯性強(qiáng)；7. 實(shí)驗(yàn)過(guò)程中，同學(xué)之間可以進(jìn)行討論互相提高，但絕對(duì)禁止抄襲。 代碼實(shí)現(xiàn)：#in clude<stdio.h>#in clude<malloc.h>#defi ne NULL 0#define LEN1 sizeof(struct job)/ 作業(yè)大小#define LEN2 sizeof(struct idle)/ 空閑區(qū)單元大小#define LEN3 sizeof(struct allocate)/ 已分配區(qū)單元大小 int SPACE=100;定義內(nèi)存空間大小int 0

4、RIGI=1;定義內(nèi)存起始地址struct job/定義作業(yè)int n ame;int size;int address;struct idle/定義空閑區(qū)int size;int address;struct idle *n ext;struct allocate/定義已分配區(qū)int n ame;int size;int address;struct allocate *n ext;struct idle *creatidle(void) 建立空閑表struct idle *head;struct idle *p1;p1= (struct idle*)malloc(LEN2);p1->

5、size=SPACE; p1->address=ORIGI;p1-> next=NULL;head=p1; return(head);struct allocate *creatallocate(void)/ 建立已分配表struct allocate *head;head=NULL;return(head);struct job *creatjob(void) 建立作業(yè)struct job *p;p=(struct job*)malloc(LEN1);printf(”請(qǐng)輸入要運(yùn)行的作業(yè)的名稱(chēng)與大小:n”)；scan f("%d%d",&p-> n

6、ame,&p->size); return(p);struct idle *in it1(struct idle *head,struct job *p)首次適應(yīng)算法分配內(nèi)存struct idle *p0,*p1;struct job *a;a=p;p0=head;p仁 p0;while(pO-> next!=NULL&&p0->size<a->size)pO=pO _>n ext;if(p0->size>a->size)pO->size=pO->size-a->size;a->address

7、=p0->address;pO->address=pO->address+a->size;elseprintf("無(wú)法分配 n”);return(head);struct idle *in it2(struct idle *head,struct job *p) 最優(yōu)struct idle *p0,*p1;struct job *a;a=p;p0=head;if(p0=NULL)printf("無(wú)法進(jìn)行分配!n");while(p0-> next!=NULL&&p0->size<a->size)p0=

8、p0 _>n ext;if(p0->size>a->size)p1=p0; pO=pO->n ext;elseprintf(” 無(wú)法分配!n"); while(pO!=NULL) if(pO->size>p1->size)p0=p0 _>n ext;else if(p0->size<p1->size )&&(pO->size>a->size) p仁 p0; pO=pO _>n ext; p1_>size=(p1_>size)_(a_>size); a-&g

9、t;address=p1->address;p1->address=(p1->address)+(a->size); return(head);最差struct idle *in it3(struct idle *head,struct job *p)struct idle *p0,*p1;struct job *a;a=p;p0=head;if(p0=NULL)printf("無(wú)法進(jìn)行分配!");while(p0-> next!=NULL&&p0->size<a->size) p0=p0 _>n ext

10、;if(p0->size>a->size)p仁 p0; p0=p0 _>n ext;elseprintf("無(wú)法分配!n");while(pO!=NULL)if(pO->size<p1->size)p0=p0 _>n ext;else if(p0->size>p1->size)p仁 p0;p0=p0 _>n ext;p1_>size=(p1_>size)_(a_>size);a->address=p1->address; p1->address=(p1->add

11、ress)+(a->size); return(head);重置已分配表struct allocate *reallocate(struct allocate *head,struct job *p) struct allocate *pO,*p1,*p2;*p3,*p4;struct job *a;/struct idle *b;a=p;pO=(struct allocate*)malloc(LEN3);p仁(struct allocate*)malloc(LEN3);if(head=NULL)pO->n ame=a->n ame;p0->size=a->siz

12、e; pO->address=ORIGI; p0-> next=NULL;head=p0;Elsep1- >n ame=a->n ame;p1->size=a->size; p1->address=a->address; p2=head;while(p2-> next!=NULL)p2=p2->n ext; p2->n ext=p1;p1- >n ext=NULL;retur n( head);struct allocate *del(struct allocate *head,struct job *p) 刪除指定的作業(yè)

13、 struct job *p1;struct allocate *p2,*p3;p2=head;p仁p；while(p1-> name!=p2-> name)&&(p2-> next!=NULL)p3=p2;p2=p2->n ext;if(p1- >n ame=p2->n ame)if(p2=head)head=p2->n ext;elsep3->n ext=p2->n ext;return(head);struct job *delejob(struct allocate *head)struct job *p1;stru

14、ct allocate *p2;int num;p1= (struct job*)malloc(LEN1);printf("請(qǐng)輸入要?jiǎng)h除的作業(yè)的名稱(chēng)n");scan f("%d", &n um);p2=head;while( nu m!=p2-> name )&&(p2-> next!=NULL)p2=p2->n ext;if(num=p2->n ame)p1- >n ame=p2->n ame;p1->size=p2->size;p1->address=p2->addr

15、ess;return(p1);struct idle *un ite(struct job *p,struct idle *head) 合并相鄰內(nèi)存空間struct idle *p1,*p2,*p3;struct job *m;m=p;p仁head;p3=(struct idle*)malloc(LEN2);while(p1->address<m->address)&&(p1-> next!=NULL) p2=p1;p1=p1- >n ext;if(m->address<p1->address)if(head=p1)p3->

16、size=m->size; p3->address=m->address; if(p1->address-p3->address)=(p3->size)p1->address=p3->address; p1->size=p3->size+p1->size;elsehead=p3;p3->n ext=p1;elsep3->size=m->size; p3->address=m->address; if(p1->address-p3->address)=(p3->size)p1->

17、;address=p3->address; p1->size=p3->size+p1->size; if(p3->address-p2->address)=(p2->size) p2->size=p1->size+p2->size;p2->n ext=p1- >n ext;elsep2->n ext=p1;elseif(p3->address-p2->address)=(p2->size) p2->size=p2->size+p3->size;elsep3->n ext=p1

18、;p2->n ext=p3;elsep3->size=m->size;p3->address=m->address;if(p3->address-p1->address)=(p1->size)p1->size=p1->size+p3->size;elsep1- >n ext=p3;p3-> next=NULL;return(head);void prin t(struct idle *h1,struct allocate *h2)struct idle *m1;struct allocate *n1;m仁 h1;n仁

19、 h2;if(m1=NULL)printf("空閑表為空!n");elsewhile(m1!=NULL) printf(” 空閑單元地址為 d,其大小為 dn",m1->address,m1->size); m1=m1- >n ext;if(n 1=NULL)printf("已分配表為空!n");elsewhile( n1!=NULL)printf("已分配單元地址為 %d,其大小為 %d,其名稱(chēng)為 %dn",n1->address,n1->size,n1->name); n仁n1->

20、;n ext;void FF(void)struct idle *p1;struct allocate *p2;struct job *p,*q;int y=1;int n=0;int a=1;int c;p1=creatidle();p2=creatallocate();printf("初始情況為:n”);prin t(p1,p2);while(a=y)printf("請(qǐng)輸入要進(jìn)行的操作:1.建立作業(yè)2刪除作業(yè)3結(jié)束操作n");sca nf("%d",&c);switch(c)case 1:p=creatjob();p1=i ni t

21、1(p1,p);p2=reallocate(p2,p);prin t(p1,p2);break;case 2:q=delejob(p2);p2=del(p2,q);p2=reallocate(p2,q);p1= un ite(q,p1);prin t(p1,p2);break;case 3:y=0;break;void BF(void)struct idle *p1;struct allocate *p2;struct job *p,*q;int y=1;int n=0;int a=1;int c;p1=creatidle();p2=creatallocate();printf("初始情況為:n”);prin t(p1,p2);while(a=y)printf("請(qǐng)輸入