操作系統(tǒng)實(shí)驗(yàn)二存儲管理動態(tài)分區(qū)分配及回收算法

1、實(shí)驗(yàn)二 存儲管理動態(tài)分區(qū)分配及回收算法一、 實(shí)驗(yàn)?zāi)康耐ㄟ^分區(qū)管理實(shí)驗(yàn)，了解操作系統(tǒng)的基本概念，理解計(jì)算機(jī)系統(tǒng)的資源如何組織，操作系統(tǒng)如何有效地管理這些系統(tǒng)資源，用戶如何通過操作系統(tǒng)與計(jì)算機(jī)系統(tǒng)打交道。通過課程設(shè)計(jì)，我們可以進(jìn)一步理解在計(jì)算機(jī)系統(tǒng)上運(yùn)行的其它各類操作系統(tǒng)，并懂得在操作系統(tǒng)的支持下建立自己的應(yīng)用系統(tǒng)。二、 實(shí)驗(yàn)要求本實(shí)驗(yàn)要求用一種結(jié)構(gòu)化高級語言構(gòu)造分區(qū)描述器，編制動態(tài)分區(qū)分配算法和回收算法模擬程序，并掌握分配算法的特點(diǎn)，提高編程技巧和對算法的理解和掌握。三、 實(shí)驗(yàn)過程1 準(zhǔn)備 （一）主程序 1、定義分區(qū)描述器node，包括 3個元素： （1）adr分區(qū)首地址 （2）size分區(qū)大小

2、 （3）next指向下一個分區(qū)的指針 2、定義 3個指向node結(jié)構(gòu)的指針變量： （1）head1空閑區(qū)隊(duì)列首指針 （2）back1指向釋放區(qū)node結(jié)構(gòu)的指針 （3）assign指向申請的內(nèi)存分區(qū)node結(jié)構(gòu)的指針 3、定義 1個整形變量： free用戶申請存儲區(qū)的大?。ㄓ捎脩翩I入） （二）過程 1、定義check過程，用于檢查指定的釋放塊（由用戶鍵入）的合法性 2、定義assignment1過程，實(shí)現(xiàn)First Fit Algorithm 3、定義assignment2過程，實(shí)現(xiàn)Best Fit Algorithm 4、定義acceptment1過程，實(shí)現(xiàn)First Fit Algorit

3、hm的回收算法 5、定義acceptment2過程，實(shí)現(xiàn)Best Fit Algorithm的回收算法 6、定義print過程，打印空閑區(qū)隊(duì)列 （三）執(zhí)行 程序首先申請一整塊空閑區(qū)，其首址為0，大小為32767；然后，提示用戶使用哪種分配算法，再提示是分配還是回收；分配時要求輸入申請區(qū)的大小，回收時要求輸入釋放區(qū)的首址和大小。 （四）輸出 要求每執(zhí)行一次，輸出一次空閑區(qū)隊(duì)列情況，內(nèi)容包括： 編號 首址 終址 大小 2.主要流程和源代碼實(shí)驗(yàn)二源代碼#include<stdio.h>#include<stdlib.h>#include<string.h>#def

4、ine MAX_SIZE 32767typedef struct node int id; int adr; int size; struct node *next; Node;Node *head1,*head2,*back1,*back2,*assign;int request; int check(int add,int siz,char c) Node *p,*head;int check=1;if(add<0|siz<0)check=0;/*地址和大小不能為負(fù)*/if(c='f'|c='F')head=head1;elsehead=head

5、2;p=head->next;while(p!=NULL)&&check) if(add<p->adr)&&(add+siz>p->adr)|(add>=p->adr)&&(add<p->adr+p->size) check=0; else p=p->next;if(check=0) printf("t輸入釋放區(qū)地址或大小有錯誤！n"); return check; void init() Node *p;head1=(Node*)malloc(sizeof(N

6、ode);head2=(Node*)malloc(sizeof(Node);p=(Node*)malloc(sizeof(Node);head1->next=p;head2->next=p;p->size=MAX_SIZE;p->adr=0;p->next=NULL;p->id=0;Node* assignment1(int num,int req) 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) before->next=after->next;ass->adr=after->adr;else after->size-=req;ass->adr=after->adr;after->adr+=req;return ass;void acceptment1

8、(int address,int siz,int rd) 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ū)（按首址大小從小到大插入）if(after=NULL)|(back1->adr<=afte

9、r->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;before->next=back1->next;free(back1);else

10、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)存失??！n");Node* assignment2(int num,int req) Node *bef

11、ore,*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;if(after=NULL)ass->adr=-1; elseif(after->size=req) before->next=after->

12、next;ass->adr=after->adr;else q=after;before->next=after->next;ass->adr=q->adr;q->size-=req;q->adr+=req;before=head2;after=head2->next;if(after=NULL)before->next=q;q->next=NULL;elsewhile(after->size)<(q->size)before=before->next;after=after->next;befor

13、e->next=q;q->next=after;return (ass);void acceptment2(int address,int siz,int rd) Node *before,*after;int insert=0; back2=(Node*)malloc(sizeof(Node);before=head2;after=head2->next;back2->adr=address;back2->size=siz;back2->id=rd;back2->next=NULL;if(head2->next=NULL)/空閑隊(duì)列為空head

14、2->next=back2;head2->size=back2->size;else/空閑隊(duì)列不為空while(after)if(back2->adr=after->adr+after->size)/和前邊空閑分區(qū)合并before->next=after->next;after->size+=back2->size;back2=after;elsebefore=before->next;after=after->next;before=head2;after=head2->next;while(after)if(af

15、ter->adr=back2->adr+back2->size)/和后邊空閑區(qū)合并before->next=after->next;back2->size+=after->size;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-

16、>size<back2->size) before->next=back2; back2->next=after; insert=1;break; else before=before->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='

17、;F')p=head1->next;elsep=head2->next;if(p)printf("n空閑區(qū)隊(duì)列的情況為：n");printf("t編號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("c

18、ls");printf("選擇最先適應(yīng)算法請輸入F，選擇最佳適應(yīng)算法請輸入B，退出程序請輸入Enn");printf("請輸入你的選擇:");scanf("%c",&chose);if(chose='e'|chose='E')exit(0);elsesystem("cls");while(1)if(chose='f'|chose='F')printf("最先適應(yīng)算法(First-Fit)模擬:n");if(chos

19、e='b'|chose='B')printf("最佳適應(yīng)算法(Best-Fit)模擬:n");printf("1.分配內(nèi)存,2.回收內(nèi)存,3.查看內(nèi)存,4.返回nn");printf("請輸入你的選擇:");scanf("%d",&ch);fflush(stdin);switch(ch)case 1:printf("輸入申請的分區(qū)大?。?quot;);scanf("%d",&r);if(chose='f'|chose='F')assign=assignment1(num,r);elseassign=assignment2(num,r);if(assign->adr=-1)printf("分配內(nèi)存失??！n");else printf("分配成功！分配的內(nèi)存的首址為:%dn",assig