動(dòng)態(tài)分區(qū)分配方式首次適應(yīng)算法

1、動(dòng)態(tài)分區(qū)分配方式首次適應(yīng)算法 算法思路使用動(dòng)態(tài)分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu)和分配算法，編輯動(dòng)態(tài)分區(qū)存儲(chǔ)管理方式并實(shí)現(xiàn)。本程序主要采用首次適應(yīng)算法的動(dòng)態(tài)分區(qū)分配過程alloc()和回收過程free()。 空閑分區(qū)通過空閑分區(qū)鏈表來管理，在進(jìn)行內(nèi)存分配時(shí)，系統(tǒng)優(yōu)先使用空閑區(qū)低端的空間，即每次分配內(nèi)存空間是總是從低址部分開始進(jìn)行循環(huán)，找到第一個(gè)合適的空間，便按作業(yè)所需分配的大小分配給作業(yè)。二、算法流程圖檢查完否？從頭開始查表YesNo與要求內(nèi)存是否一致？繼續(xù)查找下一個(gè)表NoYes 三、函數(shù)代碼#include<iostream.h>#include<stdlib.h>#de

2、fine Free 0 /空閑狀態(tài)#define Busy 1 /已用狀態(tài)#define OK 1 /完成#define ERROR 0 /出錯(cuò)#define MAX_length 640 /最大內(nèi)存空間為640KBtypedef int Status;typedef struct freearea/定義一個(gè)空閑區(qū)說明表結(jié)構(gòu)int ID;long size;long address;int state;ElemType;typedef struct DuLNode /double linked list ElemType data; struct DuLNode *prior; /前趨指針 s

3、truct DuLNode *next; /后繼指針DuLNode,*DuLinkList;DuLinkList block_first; /頭結(jié)點(diǎn)DuLinkList block_last; /尾結(jié)點(diǎn)Status alloc();/內(nèi)存分配Status free(int); /內(nèi)存回收Status First_fit(int,int);/首次適應(yīng)算法void show();/查看分配Status Initblock();/開創(chuàng)空間表Status Initblock()/開創(chuàng)帶頭結(jié)點(diǎn)的內(nèi)存空間鏈表block_first=(DuLinkList)malloc(sizeof(DuLNode);bl

4、ock_last=(DuLinkList)malloc(sizeof(DuLNode); block_first->prior=NULL; block_first->next=block_last; block_last->prior=block_first; 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 O

5、K;/- 分 配 主 存 -Status alloc()int ID,request;cout<<"請(qǐng)輸入作業(yè)(分區(qū)號(hào))："cin>>ID; cout<<"請(qǐng)輸入需要分配的主存大小(單位:KB)：" cin>>request; if(request<0 |request=0)cout<<"分配大小不合適，請(qǐng)重試！"<<endl;return ERROR;if(First_fit(ID,request)=OK)cout<<"分配成功！&q

6、uot;<<endl;elsecout<<"內(nèi)存不足，分配失?。?quot;<<endl;/- 首次適應(yīng)算法 -Status First_fit(int ID,int request)/傳入作業(yè)名及申請(qǐng)量/為申請(qǐng)作業(yè)開辟新空間且初始化DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode); temp->data.ID=ID; temp->data.size=request; temp->data.state=Busy; DuLNode *p=block_first->next;w

7、hile(p)if(p->data.state=Free && p->data.size=request)/有大小恰好合適的空閑塊p->data.state=Busy;p->data.ID=ID;return OK;break;if(p->data.state=Free && p->data.size>request)/有空閑塊能滿足需求且有剩余temp->prior=p->prior;temp->next=p;temp->data.address=p->data.address;p->

8、;prior->next=temp; p->prior=temp;p->data.address=temp->data.address+temp->data.size;p->data.size-=request;return OK;break;p=p->next;return ERROR;/- 主 存 回 收 -Status free(int ID)DuLNode *p=block_first;while(p)if(p->data.ID=ID)p->data.state=Free;p->data.ID=Free;if(p->pr

9、ior->data.state=Free)/與前面的空閑塊相連p->prior->data.size+=p->data.size; p->prior->next=p->next; p->next->prior=p->prior;if(p->next->data.state=Free)/與后面的空閑塊相連p->data.size+=p->next->data.size;if(p->next->next=NULL)p->next=NULL;elsep->next->next-&g

10、t;prior=p;p->next=p->next->next;break;p=p->next;cout<<"分區(qū)："<<ID<<"回收成功"<<endl;return OK;/- 顯示主存分配情況 -void show()cout<<"+n"cout<<"+ 主 存 分 配 情 況 +n"cout<<"+n"DuLNode *p=block_first->next;while(p)

11、cout<<"分 區(qū) 號(hào)："if(p->data.ID=Free)cout<<"Free"<<endl;elsecout<<p->data.ID<<endl;cout<<"起始地址："<<p->data.address;cout<<" 分區(qū)大?。?quot;<<p->data.size<<" KB"cout<<" 狀 態(tài)："if(p

12、->data.state=Free)cout<<"空 閑"<<endl;elsecout<<"已分配"<<endl;p=p->next;/- 主 函 數(shù)-void main()Initblock();int choice;int i;for(i=0;i+) cout<<"+n"cout<<"+動(dòng)態(tài)分區(qū)分配方式的模擬一+n"cout<<"+首次適應(yīng)算法+n"cout<<" +n&q

13、uot;cout<<" + 1: 分配內(nèi)存 2: 回收內(nèi)存 +n"cout<<" + 3: 查看分配 0: 退 出 +n"cout<<" +n"cout<<"請(qǐng)輸入您的操作 ："cin>>choice;if(choice=1)/ 分配內(nèi)存alloc();else if(choice=2)/ 內(nèi)存回收 int ID; cout<<"請(qǐng)輸入您要釋放的分區(qū)號(hào)：" cin>>ID;free(ID);else if(choice=3)/顯示主存show();else if(choice=0)/退出break;else /輸入操作