存儲管理動態(tài)分區(qū)分配及回收算法

1、存儲管理動態(tài)分區(qū)分配及回收算法 (First Fit AlgorithmBest Fit Algor)一、目的和要求分區(qū)管理是應(yīng)用較廣泛的一種存儲管理技術(shù)。本實(shí)驗(yàn)要求用一種結(jié)構(gòu)化高級語言構(gòu)造分區(qū)描述器，編制動態(tài)分區(qū)分配算法和回收算法模擬程序，并討論不同分配算法的特點(diǎn)。二、實(shí)驗(yàn)內(nèi)容1 、編寫： First Fit Algorithm首次適應(yīng)算法( First Fit ) ：從空閑分區(qū)表的第一個(gè)表目起查找該表，把最先能夠滿足要求的空閑區(qū)分配給作業(yè)，這種方法目的在于減少查找時(shí)間。為適應(yīng)這種算法，空閑分區(qū)表(空閑區(qū)鏈)中的空閑分區(qū)要按地址由低到高進(jìn)行排序。該算法優(yōu)先使用低址部分空閑區(qū)，在低址空間造成許

2、多小的空閑區(qū)，在高地址空間保留大的空閑區(qū)。2 、編寫：Best Fit Algorithm最佳適應(yīng)算法( Best Fit ) ：它從全部空閑區(qū)中找出能滿足作業(yè)要求的、且大小最小的空閑分區(qū)，這種方法能使碎片盡量小。為適應(yīng)此算法，空閑分區(qū)表(空閑區(qū)鏈)中的空閑分區(qū)要按從小到大進(jìn)行排序，自表頭開始查找到第一個(gè)滿足要求的自由分區(qū)分配。該算法保留大的空閑區(qū)，但造成許多小的空閑區(qū)。#include<stdio.h>#include<stdlib.h>#include<string.h>#define MAX_SIZE 32767typedef struct node

3、/ 定義分區(qū)描述器的結(jié)構(gòu)int id;/編號int adr;/分區(qū)首地址int size;/分區(qū)大小struct node *next;/ 指向下一個(gè)分區(qū)的指針Node;Node *head1,*head2,*back1,*back2,*assign;/*head-空閑區(qū)隊(duì)列首指針back- 指向釋放區(qū)Node 結(jié)構(gòu)的指針assign-指向申請的內(nèi)存分區(qū) Node結(jié)構(gòu)的指針*/- 1 -int request; / 用戶申請存儲區(qū)的大小(由用戶輸入)int check(int add,int siz,char c)/ 用于檢查指定的釋放塊(由用戶鍵入)的合法性Node *p,*head;int

4、 check=1;if(add<0|siz<0)check=0;/* 地址和大小不能為負(fù) */if(c='f'|c='F')head=head1;elsehead=head2;p=head->next;while(p!=NULL)&&check)/* 地址不能和空閑區(qū)表中結(jié)點(diǎn)出現(xiàn)重疊*/if(add<p->adr)&&(add+siz>p->adr)|(add>=p->adr)&&(add<p->adr+p->size)check=0;else

5、p=p->next;if(check=0)printf("t 輸入釋放區(qū)地址或大小有錯(cuò)誤！ ！ ！ n");return check; /* 返回檢查結(jié)果*/void init()/ 初始化，生成兩個(gè)帶頭節(jié)點(diǎn)的空閑隊(duì)列指針， /head1 指向 first-fit 的空閑隊(duì)列頭， head2 指向 best-fit 的空閑隊(duì)列頭Node *p,*q;head1=(Node*)malloc(sizeof(Node);head2=(Node*)malloc(sizeof(Node);p=(Node*)malloc(sizeof(Node);q=(Node*)malloc(

6、sizeof(Node);head1->next=p;head2->next=q;p->size=q->size=MAX_SIZE;p->adr=q->adr=0;p->next=q->next=NULL;p->id=q->id=0;Node* assignment1(int num,int req)/ 實(shí)現(xiàn)首次適應(yīng)算法的分配 Node *before,*after,*ass;ass=(Node*)malloc(sizeof(Node);before=head1;after=head1->next;ass->id=num;

7、ass->size=req;while(after->size<req)before=before->next;after=after->next;if(after=NULL)ass->adr=-1;/ 分配失敗elseif(after->size=req)/空閑分區(qū)恰好等于所申請的內(nèi)存大小before->next=after->next;ass->adr=after->adr;else/空閑分區(qū)大于所申請的內(nèi)存大小after->size-=req;ass->adr=after->adr;after->a

8、dr+=req;return ass;void acceptment1(int address,int siz,int rd)/ 實(shí)現(xiàn)首次適應(yīng)算法的回收Node *before,*after;int insert=0;back1=(Node*)malloc(sizeof(Node);before=head1;after=head1->next;back1->adr=address;back1->size=siz;back1->id=rd;back1->next=NULL;while(!insert&&after)/將要被回收的分區(qū)插入空閑區(qū)(按首址

9、大小從小到大插入)if(after=NULL)|(back1->adr<=after->adr)&&(back1->adr>=before->adr)before->next=back1;back1->next=after;insert=1;elsebefore=before->next;after=after->next;if(insert)if(back1->adr=before->adr+before->size)/和前邊分區(qū)合并before->size+=back1->size;b

10、efore->next=back1->next;free(back1);else if(after&&back1->adr+back1->size=after->adr)/和后邊分區(qū)合并back1->size+=after->size;back1->next=after->next;back1->id=after->id;free(after);after=back1;printf("t 首先分配算法回收內(nèi)存成功！ ！ ！ n"); elseprintf("t 首先分配算法回收內(nèi)存失

11、??！ ！ ！ n");Node* assignment2(int num,int req)/ 實(shí)現(xiàn)最佳適應(yīng)算法的分配 Node *before,*after,*ass,*q;ass=(Node*)malloc(sizeof(Node);q=(Node*)malloc(sizeof(Node);before=head2;after=head2->next;ass->id=num;ass->size=req;while(after->size<req) before=before->next;after=after->next;/printf(&

12、quot;nzphzph1n");if(after=NULL)ass->adr=-1;/ 分配失敗/printf("nzphzph2n");elseif(after->size=req)/空閑分區(qū)恰好等于所申請的內(nèi)存大小before->next=after->next; ass->adr=after->adr;/printf("nzphzph3n");else/空閑分區(qū)大于所申請的內(nèi)存大小q=after;before->next=after->next; ass->adr=q->adr

13、;q->size-=req; q->adr+=req;/printf("nzphzph4n");before=head2;after=head2->next;/printf("nzphzph4n"); if(after=NULL) /printf("nzphzph5n"); before->next=q;q->next=NULL;after=q;else/printf("nzphzph6n");while(after&&(after->size)<(q-&g

14、t;size) printf("nzphzph7n");before=before->next; after=after->next;/printf("nzphzph8n");before->next=q;q->next=after;after=q;return (ass); void acceptment2(int address,int siz,int rd)/ 實(shí)現(xiàn)最佳適應(yīng)算法的回收 Node *before,*after;int insert=0;/ 是否被回收的標(biāo)志back2=(Node*)malloc(sizeof(N

15、ode);before=head2;after=head2->next;back2->adr=address;back2->size=siz;back2->id=rd;back2->next=NULL;if(head2->next=NULL)/空閑隊(duì)列為空head2->next=back2;/head2->size=back2->size;else/空閑隊(duì)列不為空while(after)if(back2->adr=after->adr+after->size)/和前邊空閑分區(qū)合并before->next=after-

16、>next;after->size+=back2->size;back2=after;after=before->next;elsebefore=before->next;after=after->next;before=head2;after=head2->next;while(after)if(after->adr=back2->adr+back2->size)/和后邊空閑區(qū)合并before->next=after->next;back2->size+=after->size;after=before-&g

17、t;next;elsebefore=before->next;after=after->next;before=head2;after=head2->next;while(!insert)/將被回收的塊插入到恰當(dāng)?shù)奈恢?按分區(qū)大小從小到大)if(after=NULL|(after->size>back2->size)&&(before->size<back2->size)before->next=back2;back2->next=after;insert=1;break;elsebefore=before-&g

18、t;next;after=after->next;if(insert)printf("t 最佳適應(yīng)算法回收內(nèi)存成功！ ！ n");elseprintf("t 最佳適應(yīng)算法回收內(nèi)存失??！ ！ n"); void print(char choice)/ 輸出空閑區(qū)隊(duì)列信息Node *p;if(choice='f'|choice='F')p=head1->next;elsep=head2->next;if(p)printf("n 空閑區(qū)隊(duì)列的情況為： n");printf("t編號

19、t首址t終址t大小n");while(p)printf("t%dt%dt%dt%dn",p->id,p->adr,p->adr+p->size-1,p- >size);p=p->next;void menu()/ 菜單及主要過程char chose;int ch,num,r,add,rd;while(1)system("cls");printf("tt 存儲管理動態(tài)分區(qū)分配及回收算法模擬 nn");printf("tF. 最先適應(yīng)算法(First-Fit)nn");pr

20、intf("tB. 最佳適應(yīng)算法(Best-Fit)nn");printf("tE. 退出程序 nn");printf("t 你選擇( f/b ) :");- 11 -scanf("%c",&chose);if(chose='e'|chose='E')exit(0);elsesystem("cls");while(1)if(chose='f'|chose='F')printf("tt 最先適應(yīng)算法(First-Fi

21、t) 模擬 nn");if(chose='b'|chose='B')printf("tt 最佳適應(yīng)算法(Best-Fit) 模擬nn");printf("t1. 分配內(nèi)存 tt2. 回收內(nèi)存 nn");printf("t3. 查看內(nèi)存 tt4. 返回 nn");printf("t 你選擇( 1/2/3/4 ) :");scanf("%d",&ch);fflush(stdin);switch(ch)case 1:printf(" 輸入分區(qū)號： ");scanf("%d",&num);printf(" 輸入申請的分區(qū)大?。?");scanf("%d",&r);if(chose='f'|chose='F')assign=assignment1(nu