動態(tài)分區(qū)分配方式的模擬C語言代碼和C++代碼

1、實驗三 使用動態(tài)分區(qū)分配方式的模擬1、實驗目的了解動態(tài)分區(qū)分配方式中使用的數(shù)據(jù)結(jié)構(gòu)和分配算法，并進一步加深對動態(tài)分區(qū)存儲管理方式及其實現(xiàn)過程的理解。2、實驗內(nèi)容(1) 用C語言分別實現(xiàn)采用首次適應算法和最佳適應算法的動態(tài)分區(qū)分配過程alloc( )和回收過程free( )。其中，空閑分區(qū)通過空閑分區(qū)鏈來管理：在進行內(nèi)存分配時，系統(tǒng)優(yōu)先使用空閑區(qū)低端的空間。(2) 假設(shè)初始狀態(tài)下，可用的內(nèi)存空間為640KB，并有下列的請求序列：作業(yè)1申請130KB。作業(yè)2申請60KB。作業(yè)3申請100KB。作業(yè)2釋放60KB。作業(yè)4申請200KB。作業(yè)3釋放100KB。作業(yè)1釋放130KB。作業(yè)5申請140KB

2、。作業(yè)6申請60KB。作業(yè)7申請50KB。作業(yè)6釋放60KB。請分別采用首次適應算法和最佳適應算法，對內(nèi)存塊進行分配和回收，要求每次分配和回收后顯示出空閑分區(qū)鏈的情況。程序代碼C語言實現(xiàn)#include<stdio.h>#include<stdlib.h>struct node /空閑分區(qū)鏈結(jié)點的定義node *before;node *after;int size;int address;int state;node L;struct usenodeusenode *next;int num;int add;int size;U,*n;void Init() /空閑分

3、區(qū)鏈的初始化node *p;p=(node *)malloc(sizeof(node);p->before=&L;p->after=NULL;p->size=640;p->address=0;p->state=0;L.after=p;L.before=NULL;L.size=0;U.next=NULL;n=&U;node *search(int a)node *p=L.after;if(p=NULL)printf("沒有空閑的區(qū)域!");p=NULL;return p;elsewhile(p!=NULL && a

4、>p->size)p=p->after;if(p=NULL)printf("沒有找到合適的空閑空間!");p=NULL;return p;else return p;void recovery(int a,int b) /內(nèi)存回收算法node *c,*s,*r=L.after;node *d=L.after,*e;usenode *k=U.next,*h=&U; while(k!=NULL && a!=k->num)h=k;k=k->next;if(k=NULL)printf("沒有找到這樣的作業(yè)!"

5、);elseh->next=k->next;if(h->next=NULL)n=h;while(r!=NULL) /若回收得到的空閑塊的前方有空閑塊合并此空閑塊if(k->add=r->address+r->size)r->size=r->size+k->size;break;elser=r->after; if(r=NULL) /若回收得到的空閑塊的后面有空閑塊合并此空閑塊 r=L.after; while(r!=NULL) if(k->add+k->size=r->address)r->address=k-

6、>add;r->size=r->size+k->size;break;else r=r->after; while(d!=NULL) /保證空閑鏈表中沒有相鄰的空閑空間if(d->after!=NULL)e=d->after;elsebreak;if(d->address+d->size=e->address)d->after=e->after;while(e->after!=NULL)e->after->before=d;d->size=d->size+e->size;free(e);

7、break;elsed=d->after; if(r=NULL) r=L.after; c=(node *)malloc(sizeof(node); c->size=b; c->address=k->add; if(L.after=NULL)c->after=L.after;c->before=&L;L.after=c; else r=L.after; while(r!=NULL) if(r->address>c->address) c->after=r; c->before=r->before; r->be

8、fore->after=c; r->before=c; free(k); return; else r=r->after;free(k);void alloc(int a ,int b) /分配內(nèi)存算法node *p,*q=L.after;usenode *m;p=search(b); if(p=NULL)return;m=(usenode *)malloc(sizeof(usenode);/生成一個被占用鏈表的結(jié)點,并插入到該鏈表的尾部m->add=p->address;m->size=b;m->num=a;m->next=n->next

9、;n->next=m;n=m; /保證n始終指向被占用鏈表的尾部，方便以后新生成結(jié)點的插入 if(p->size>b) /如果申請空間的大小小于找到空閑空間的大小的處理p->size=p->size-b;p->address=p->address+b;else /如果申請空間的大小等于找到空閑空間的大小的處理 p->before->after=p->after;if(p->after!=NULL) p->after->before=p->before;free(p);void sort() /對空閑鏈表進行排序

10、int max; node *p,*q,*r,*s;node a;p=L.after;while(p!=NULL) /讓指針q指向鏈表的最后一個結(jié)點q=p;p=p->after;if(L.after->after=NULL) return;else while(p!=q) s=r=p=L.after; max=r->size; while(s!=q->after) if(s->size>max) max=s->size; r=s; s=s->after; else s=s->after; a.size=q->size; a.addre

11、ss=q->address; q->size=r->size; q->address=r->address; r->size=a.size; r->address=a.address;if(q->before->before=&L)return;else q=q->before; void Print()node *p=L.after;usenode *q=U.next;int i=1;printf("n空閑區(qū)域列表:n");printf("FREEID address sizen");

12、while(p!=NULL)printf("%-10d",i);printf("%-10d",p->address);printf("%dn",p->size);p=p->after;i+;if(q=NULL)return;elseprintf("n已分配區(qū)域列表:n");printf("WORKID address sizen");while(q!=NULL)printf("%-10d",q->num);printf("%-10d"

13、;,q->add);printf("%dn",q->size);q=q->next;void firstfit() /首次適應算法int a,b,i;Init();Print();while(1)printf("n1、申請空間n"); printf("2、釋放空間n"); printf("3、退出首次適應算法n"); printf("請輸入你的選擇:"); scanf("%d",&i); switch(i) case 1: printf("

14、請輸入申請空間的作業(yè)號:"); scanf("%d",&a); printf("請輸入申請空間的大小:"); scanf("%d",&b); alloc(a,b); Print(); break; case 2: printf("請輸入釋放空間的作業(yè)號:"); scanf("%d",&a); printf("請輸入釋放空間的大小:"); scanf("%d",&b); recovery(a,b); Print();

15、 break; case 3:printf("n");return; void bestfit()int a,b,i;Init();Print();while(1)printf("n1、申請空間n"); printf("2、釋放空間n"); printf("3、退出最佳適應算法n"); printf("請輸入你的選擇:"); scanf("%d",&i); switch(i) case 1: printf("請輸入申請空間的作業(yè)號:"); scan

16、f("%d",&a); printf("請輸入申請空間的大小:"); scanf("%d",&b); alloc(a,b); sort(); Print(); break; case 2: printf("請輸入釋放空間的作業(yè)號:"); scanf("%d",&a); printf("請輸入釋放空間的大小:"); scanf("%d",&b); recovery(a,b); sort(); Print(); break; c

17、ase 3:printf("n");return; void main() int i; while(1) printf("1、首次適應算法n"); printf("2、最佳適應算法n"); printf("3、退出n"); printf("請輸入你的選擇:"); scanf("%d",&i); switch(i) case 1:firstfit();break; case 2:bestfit();break; case 3:return; 運行結(jié)果 開始界面 首次適

18、應算法 最佳適應算法程序代碼C+語言實現(xiàn)/*/*             動態(tài)分區(qū)分配方式的模擬          */* #include<iostream.h>#include<stdlib.h> #define Free 0 /空閑狀態(tài)#define Busy 1 /已用狀態(tài)#define OK 1 

19、0;  /完成#define ERROR 0 /出錯#define MAX_length 640 /最大內(nèi)存空間為640KBtypedef int Status; typedef struct freearea/定義一個空閑區(qū)說明表結(jié)構(gòu)    int ID;   /分區(qū)號    long size;   /分區(qū)大小    long address; /分區(qū)地址  &#

20、160; int state;   /狀態(tài)ElemType; /-  線性表的雙向鏈表存儲結(jié)構(gòu)  -typedef struct DuLNode /double linked list    ElemType data;    struct DuLNode *prior; /前趨指針    struct DuLNode *next;  /后繼指針DuLNode,*Du

21、LinkList; DuLinkList block_first; /頭結(jié)點DuLinkList block_last;  /尾結(jié)點 Status alloc(int);/內(nèi)存分配Status free(int); /內(nèi)存回收Status First_fit(int,int);/首次適應算法Status Best_fit(int,int); /最佳適應算法void show();/查看分配Status Initblock();/開創(chuàng)空間表 Status Initblock()/開創(chuàng)帶頭結(jié)點的內(nèi)存空間鏈表   

22、60;block_first=(DuLinkList)malloc(sizeof(DuLNode);    block_last=(DuLinkList)malloc(sizeof(DuLNode);    block_first->prior=NULL;    block_first->next=block_last;    block_last->prior=block_first;  

23、0; block_last->next=NULL;    block_last->data.address=0;    block_last->data.size=MAX_length;    block_last->data.ID=0;    block_last->data.state=Free;    return OK; /- 分

24、 配 主 存 -Status alloc(int ch)    int ID,request;    cout<<"請輸入作業(yè)(分區(qū)號)："    cin>>ID;    cout<<"請輸入需要分配的主存大小(單位:KB)："    cin>>request;   &#

25、160;if(request<0 |request=0)            cout<<"分配大小不合適，請重試！"<<endl;        return ERROR;         if(ch=2) /選擇最佳適應算法  

26、60;         if(Best_fit(ID,request)=OK) cout<<"分配成功！"<<endl;        else cout<<"內(nèi)存不足，分配失?。?quot;<<endl;        return OK;  

27、60;     else /默認首次適應算法            if(First_fit(ID,request)=OK) cout<<"分配成功！"<<endl;        else cout<<"內(nèi)存不足，分配失??！"<<endl; 

28、0;      return OK;    /- 首次適應算法 -Status First_fit(int ID,int request)/傳入作業(yè)名及申請量    /為申請作業(yè)開辟新空間且初始化    DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode);    temp->data.ID=ID;

29、60;   temp->data.size=request;    temp->data.state=Busy;     DuLNode *p=block_first->next;    while(p)            if(p->data.state=Free && p

30、->data.size=request)        /有大小恰好合適的空閑塊            p->data.state=Busy;            p->data.ID=ID;     

31、0;      return OK;            break;                if(p->data.state=Free && p->data.size>request)  

32、60;     /有空閑塊能滿足需求且有剩余"            temp->prior=p->prior;            temp->next=p;          

33、       temp->data.address=p->data.address;            p->prior->next=temp;            p->prior=temp;     

34、       p->data.address=temp->data.address+temp->data.size;            p->data.size-=request;            return OK;   &

35、#160;        break;                p=p->next;        return ERROR;/-  最佳適應算法  -Status Best_fit(int ID,int request)

36、60;   int ch; /記錄最小剩余空間    DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode);    temp->data.ID=ID;    temp->data.size=request;    temp->data.state=Busy;    DuLNode *p=block_fi

37、rst->next;    DuLNode *q=NULL; /記錄最佳插入位置    while(p) /初始化最小空間和最佳位置            if(p->data.state=Free &&            (p->data.

38、size>request | p->data.size=request) )                    q=p;            ch=p->data.size-request;     

39、60;      break;                p=p->next;        while(p)            if(p->data.stat

40、e=Free && p->data.size=request)        /空閑塊大小恰好合適            p->data.ID=ID;            p->data.state=Busy;   

41、;         return OK;            break;                if(p->data.state=Free && p->data.size>reques

42、t)        /空閑塊大于分配需求            if(p->data.size-request<ch)/剩余空間比初值還小                     

43、;       ch=p->data.size-request;/更新剩余最小值                q=p;/更新最佳位置指向                   

44、;         p=p->next;        if(q=NULL) return ERROR;/沒有找到空閑塊    else    /找到了最佳位置并實現(xiàn)分配        temp->prior=q->prior;  

45、      temp->next=q;        temp->data.address=q->data.address;        q->prior->next=temp;        q->prior=temp;   &#

46、160;    q->data.address+=request;        q->data.size=ch;        return OK;     /-   主 存 回 收   -Status free(int ID)    

47、DuLNode *p=block_first;    while(p)            if(p->data.ID=ID)                    p->data.state=Free;  

48、;          p->data.ID=Free;            if(p->prior->data.state=Free)/與前面的空閑塊相連                 &

49、#160;          p->prior->data.size+=p->data.size;                p->prior->next=p->next;          

50、0;     p->next->prior=p->prior;                        if(p->next->data.state=Free)/與后面的空閑塊相連        

51、;                    p->data.size+=p->next->data.size;                p->next->next->prior=p; 

52、60;              p->next=p->next->next;                              &#

53、160;          break;                 p=p->next;        return OK; /-  顯示主存分配情況 -void show()  

54、;  cout<<"+n"    cout<<"+        主 存 分 配 情 況        +n"    cout<<"+n"    DuLNode *p=block_first->ne

55、xt;    while(p)            cout<<"分 區(qū) 號："        if(p->data.ID=Free) cout<<"Free"<<endl;        els

56、e cout<<p->data.ID<<endl;        cout<<"起始地址："<<p->data.address<<endl;        cout<<"分區(qū)大小："<<p->data.size<<" KB"<<endl; &#

57、160;      cout<<"狀    態(tài)："        if(p->data.state=Free) cout<<"空  閑"<<endl;        else cout<<"已分配"<

58、<endl;        cout<<""<<endl;        p=p->next;     /- 主  函  數(shù)-void main()    int ch;/算法選擇標記    cout&l

59、t;<"       動態(tài)分區(qū)分配方式的模擬       n"    cout<<"*n"    cout<<"* 1)首次適應算法  2)最佳適應算法 *n"    cout<<"*n"    cout<<"請選擇分配算法："    cin>>ch;    Initblock(); /開創(chuàng)空間表    int choice;  /操作