1、課程設(shè)計(jì)報(bào)告課程設(shè)計(jì)題目：循環(huán)首次適應(yīng)的動(dòng)態(tài)分區(qū)分配算法模擬 專 業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)班 級(jí)：10204102姓 名：譜學(xué) 號(hào): 10204102指導(dǎo)教師: 高小輝 2013年 1 月 11 日目 錄一循環(huán)首次適應(yīng)算法 ·······························

2、3;···················3 1. 概述 ·····························&#

3、183;·································· 3 2需求分析··············

4、·················································3 二實(shí)驗(yàn)指

5、導(dǎo)··················································

6、;··············4 1.基本思想··································

7、83;···················42數(shù)據(jù)結(jié)構(gòu)·····························

8、83;························4三運(yùn)行環(huán)境························

9、83;······························6四流程圖··················

10、3;················································6五循環(huán)首次適應(yīng)算法

11、代碼···········································5六調(diào)試結(jié)果·····

12、3;·················································11七、

13、總結(jié)·················································

14、3;········14八參考文獻(xiàn)········································

15、83;··············14一 循環(huán)首次適應(yīng)算法 1. 概述：該算法是由首次適應(yīng)算法演變而成的。在為進(jìn)程分配內(nèi)存空間時(shí)，不再是每次都從鏈?zhǔn)组_(kāi)始查找，而是從上次找到的空閑分區(qū)的下一個(gè)空閑分區(qū)開(kāi)始查找，直至找到一個(gè)能滿足要求的空閑分區(qū)，從中劃出一塊的請(qǐng)求大小相等的內(nèi)存空間分配給作業(yè)。為實(shí)現(xiàn)該算法，應(yīng)設(shè)置一起始查找指針，用于指示下一次起始查詢的空閑分區(qū)，并采用循環(huán)查找方式，即如果最后一個(gè)（鏈尾）空閑分區(qū)的大小仍不能滿足要求，則返回到第一個(gè)空閑分區(qū)，比較

16、大小是否滿足，找到后，應(yīng)調(diào)整起始查詢指針。2. 需求分析了解動(dòng)態(tài)分區(qū)分配中使用的數(shù)據(jù)結(jié)構(gòu)和分配算法，并進(jìn)一步加深對(duì)動(dòng)態(tài)分區(qū)存儲(chǔ)管理方式及其實(shí)現(xiàn)過(guò)程的理解。采用首次適應(yīng)算法的動(dòng)態(tài)分區(qū)分配過(guò)程alloc()和回收過(guò)程free()。空閑分區(qū)通過(guò)空閑分區(qū)鏈表來(lái)管理，在進(jìn)行內(nèi)存分配時(shí)，系統(tǒng)優(yōu)先使用空閑區(qū)低端的空間，即每次分配內(nèi)存空間是總是從低址部分開(kāi)始進(jìn)行循環(huán)，找到第一個(gè)合適的空間，便按作業(yè)所需分配的大小分配給作業(yè)。作業(yè)完成時(shí)，需要釋放作業(yè)所占空間，此時(shí)要考慮到四種情況：(1)回收區(qū)與插入點(diǎn)的前一個(gè)空閑分區(qū)相鄰接。此時(shí)將二者合并，修改前一分區(qū)的大小。(2)回收區(qū)與插入點(diǎn)的后一空閑分區(qū)相鄰接，將二者合并，

17、用回收區(qū)的首址作為新空閑區(qū)的首址。(3)回收區(qū)同時(shí)與插入點(diǎn)的前后兩個(gè)空閑分區(qū)相鄰接，三者合并，使用前一空閑分區(qū)的表項(xiàng)和首址。(4)回收區(qū)單獨(dú)存在。二、實(shí)驗(yàn)指導(dǎo)1基本思想動(dòng)態(tài)分區(qū)是指系統(tǒng)不預(yù)先劃分固定分區(qū)，而是在裝入程序的時(shí)候劃分內(nèi)存區(qū)域，使得為程序分配的分區(qū)大小恰好等于該程序的需求量，且分區(qū)的個(gè)數(shù)是動(dòng)態(tài)的。顯然動(dòng)態(tài)分區(qū)有較大的靈活性，較之固定分區(qū)能獲得好的內(nèi)存利用率。2數(shù)據(jù)結(jié)構(gòu)動(dòng)態(tài)分區(qū)管理可以用兩種數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)，一種是已分配區(qū)表和空閑區(qū)表，也就是用預(yù)先定義好的系統(tǒng)空間來(lái)存放空間分配信息。另一種也是最常用的就是空閑鏈表，由于對(duì)分區(qū)的操作是動(dòng)態(tài)的，所以很難估計(jì)數(shù)據(jù)結(jié)構(gòu)所占用的空間，而且空閑區(qū)表會(huì)占

18、用寶貴的系統(tǒng)空間，所以提出了空閑鏈表的概念。其特點(diǎn)是用于管理分區(qū)的信息動(dòng)態(tài)生成并和該分區(qū)在物理地址上相鄰。這樣由于可以簡(jiǎn)單用兩個(gè)空閑塊之間的距離定位已分配空間，不僅節(jié)約了系統(tǒng)空間，而且不必維持已分配空間的信息。本實(shí)驗(yàn)是要做一個(gè)模擬程序，來(lái)模擬動(dòng)態(tài)分區(qū)算法的分配和回收過(guò)程，并不是真正的去分配和回收內(nèi)存。基本的模擬方法有兩種：1、先從內(nèi)存中申請(qǐng)一塊存儲(chǔ)區(qū)，對(duì)這塊存儲(chǔ)區(qū)進(jìn)行模擬的分配和回收活動(dòng)。2、不申請(qǐng)存儲(chǔ)區(qū)，自己定義一塊虛擬的存儲(chǔ)區(qū)，對(duì)這塊存儲(chǔ)區(qū)進(jìn)行模擬的分配和回收活動(dòng)，分配和回收僅僅是對(duì)數(shù)據(jù)結(jié)構(gòu)的修改而已。三運(yùn)行環(huán)境： 1.操作系統(tǒng) WINDOWS XP 2.編譯軟件 Microsoft Vi

19、sual C+ 3.電腦配置：主頻3.0GHz 內(nèi)存512MB 四流程圖1程序結(jié)構(gòu)如圖： 主菜單創(chuàng)建新作業(yè)alloc（）；內(nèi)存分配查看空閑分區(qū)鏈free（）；內(nèi)存回收程序結(jié)束退出回收內(nèi)存空間2.首次適應(yīng)算法的結(jié)構(gòu)如圖：從鏈?zhǔn)组_(kāi)始順序查找空閑分區(qū)鏈完否？返 回分區(qū)大小>所需大小？分區(qū)大小-所需大小<=不可再分割大小？從該分區(qū)中劃出所需大小的新分區(qū)將該整個(gè)分區(qū)從空閑分區(qū)鏈中移出將該分區(qū)分配給相應(yīng)的作業(yè)，修改有關(guān)數(shù)據(jù)返 回Y繼續(xù)檢索下一個(gè)表項(xiàng)YNNNY五循環(huán)首次適應(yīng)算法代碼#include <iostream> #include <stdlib.h> #inclu

20、de <stdio.h>using namespace std; struct memory struct memory *former; /前向指針 int address;/地址 int num;/作業(yè)號(hào) int size;/分配內(nèi)存大小 int state;/狀態(tài)0表示空閑1表示已分配 struct memory *next; /后向指針; typedef struct memory MEMORY; MEMORY *mem; const int size_min=10;/內(nèi)存允許的最小空閑塊的大小 void init(); /初始化內(nèi)存塊void exec();/執(zhí)行相應(yīng)算法

21、void F_F(int); /依次初始化每個(gè)作業(yè),并根據(jù)相應(yīng)算法對(duì)作業(yè)分配內(nèi)存void alloc(MEMORY *,MEMORY *);/分配內(nèi)存算法（包括兩種不同算法）void free(MEMORY *,int);/首次適應(yīng)算法回收內(nèi)存void sort(MEMORY *);/對(duì)內(nèi)存鏈進(jìn)行排序 void insert(MEMORY *,MEMORY *); /按空間大小將作業(yè)順序插入到內(nèi)存鏈void print(MEMORY *);/打印內(nèi)存鏈 void main() /主函數(shù) int i=0; while(1) /選擇算法 cout<<("n歡迎進(jìn)入！"

22、;); cout<<("nPlease select a number(1,0)"); cout<<("n 循環(huán)首次適應(yīng)算法"); cout<<" 0-中止程序"<<endl; cin>>i; if(i=1) /首次適應(yīng)算法 cout<<("n以下為首次適應(yīng)算法:n"); init();exec(); else exit(1); void init() /初始化內(nèi)存容量 mem=new MEMORY; mem->size=640; mem

23、->former=0; mem->next=0; void exec()/執(zhí)行算法 while(1) /選擇申請(qǐng)或釋放內(nèi)存操作 cout<<"*"<<endl; cout<<"申請(qǐng)內(nèi)存請(qǐng)輸入作業(yè)號(hào)（1-6）"<<endl; cout<<"釋放內(nèi)存請(qǐng)輸入數(shù)字8"<<endl; cout<<"中止程序請(qǐng)輸入數(shù)字0"<<endl; cout<<"*"<<endl; int

24、 k;cin>>k; /根據(jù)k值選擇相應(yīng)的操作if(k>=1&&k<=7) F_F(k); if(k=8)int m; cout<<"請(qǐng)輸入要釋放的作業(yè)號(hào)：" cin>>m; /選擇相應(yīng)的回收算法 free(mem,m); else if(k=0) /回滾到選擇算法的步驟break;void F_F(int i) /依次初始化每個(gè)作業(yè),并根據(jù)相應(yīng)算法對(duì)作業(yè)分配內(nèi)存 int work=130,60,100,200,160,60,50;/作業(yè)序列，i從1開(kāi)始（與作業(yè)號(hào)對(duì)應(yīng)），因此從第一個(gè)開(kāi)始存放作業(yè)值，第0個(gè)值為0

25、，不是作業(yè) cout<<"請(qǐng)輸入要作業(yè)所需的內(nèi)存大小：" MEMORY *running; running=(MEMORY *)malloc(sizeof(MEMORY); if(running!=NULL) running->former=NULL; running->address=0; running->num=i; /i從1開(kāi)始循環(huán) running->size=worki; /指定作業(yè)大小 running->state=0; /作業(yè)未分配 running->next=NULL; /根據(jù)相應(yīng)算法為作業(yè)分配內(nèi)存，詳見(jiàn)all

26、oc函數(shù) alloc(mem,running); print(mem); cout<<endl; else cout<<"沒(méi)有足夠的內(nèi)存空間"<<endl; void print(MEMORY *ptr) /打印顯示內(nèi)存情況 MEMORY *temp; temp=ptr->next; cout<<"n內(nèi)存鏈的狀態(tài)為："<<endl; while(temp!=NULL) if(temp->state=0) cout<<"內(nèi)存 空閑 "<<&q

27、uot;起始地址為:"<<temp->address <<" 空閑空間大小為:"<<temp->size<<"k" else cout<<"內(nèi)存已分配 "<<"起始地址為:"<<temp->address<<" 分配空間大小為:" <<temp->size<<"k" <<" 運(yùn)行的作業(yè)號(hào):"&

28、lt;<temp->num; cout<<endl; temp=temp->next; void free(MEMORY *ptr,int i) /首次適應(yīng)算法 作業(yè)處理完后釋放內(nèi)存空間 MEMORY *previous,*current; previous=ptr; current=previous->next; while(current!=NULL) /循環(huán)直到找到需要釋放的作業(yè)位置 if(current->state=1&&current->num=i) break; previous=current; current=c

29、urrent->next; if(current=NULL) cout<<"內(nèi)存中沒(méi)有任何作業(yè)！"<<endl; return; else if(current->next=NULL) /當(dāng)前作業(yè)為內(nèi)存中最后一個(gè)作業(yè) if(previous->state=0) /與前一個(gè)相鄰空閑區(qū)合并 previous->size=previous->size+current->size; previous->next=NULL; cout<<"作業(yè) "<<(current->

30、;num)<<"釋放 "<<(current->size)<<"k 的空間"<<endl; print(mem); else /將狀態(tài)改為0，即為空閑區(qū) current->state=0; cout<<"作業(yè) "<<(current->num)<<"釋放 "<<(current->size)<<"k 的空間"<<endl; print(mem); els

31、e if(current->next)->next=NULL)/p6 /當(dāng)前作業(yè)為倒數(shù)第二個(gè)作業(yè)(此種情況還是要單列出來(lái)討論的否則會(huì)出現(xiàn)錯(cuò)誤) if(previous->state=0&&(current->next)->state=0) /p7 /釋放的地址空間前后均為空閑區(qū) previous->size=previous->size+current->size+(current->next)->size; previous->next=NULL; /與下邊else（其他情況的不同之處） cout<<

32、;"作業(yè) "<<(current->num)<<"釋放 "<<(current->size)<<"k 的空間"<<endl; print(mem); else if(previous->state=0) /p5 /釋放的地址空間前面有空閑塊則把它和前面的合并 previous->size=previous->size+current->size; (current->next)->former=previous; previou

33、s->next=current->next; cout<<"作業(yè) "<<(current->num)<<"釋放 "<<(current->size)<<"k 的空間"<<endl; print(mem); else if(current->next)->state=0) /p8 /釋放的地址空間后面有空閑塊則把它和后面的空閑塊合并 current->size=current->size+(current->ne

34、xt)->size; current->state=0; current->next=NULL; /與下邊else（其他情況的不同之處） cout<<"作業(yè) "<<(current->num)<<"釋放 "<<(current->size)<<"k 的空間"<<endl; print(mem); else /釋放的地址空間前后都沒(méi)有空閑塊時(shí)直接把它的狀態(tài)改為0 current->state=0; cout<<&quo

35、t;作業(yè) "<<(current->num)<<"釋放 "<<(current->size)<<"k 的空間"<<endl; print(mem); else /其他情況下（當(dāng)前作業(yè)在鏈表中間） if(previous->state=0&&(current->next)->state=0) /p7 /所釋放空間前后均為空閑區(qū) previous->size=previous->size+current->size+(curr

36、ent->next)->size; (current->next)->next)->former=previous; previous->next=(current->next)->next; cout<<"作業(yè) "<<(current->num)<<"釋放 "<<(current->size)<<"k 的空間"<<endl; print(mem); else if(previous->state=

37、0) /p5 /釋放的地址空間前面有空閑塊則把它和前面的合并 previous->size=previous->size+current->size; (current->next)->former=previous; previous->next=current->next; cout<<"作業(yè) "<<(current->num)<<"釋放 "<<(current->size)<<"k 的空間"<<endl;

38、 print(mem); else if(current->next)->state=0) /p8 /釋放的地址空間后面有空閑塊則把它和后面的空閑塊合并 current->size=current->size+(current->next)->size; current->state=0; (current->next)->next)->former=current; current->next=(current->next)->next; cout<<"作業(yè) "<<(cu

39、rrent->num)<<"釋放 "<<(current->size)<<"k 的空間"<<endl; print(mem); else /處理完的作業(yè)前后都沒(méi)有空閑塊時(shí)直接把它的狀態(tài)改為0 current->state=0; cout<<"作業(yè) "<<(current->num)<<"釋放 "<<(current->size)<<"k 的空間"<<

40、;endl; print(mem); void alloc(MEMORY *ptr,MEMORY *assign) /根據(jù)算法分配內(nèi)存（is_optimist狀態(tài)） if(ptr->next=NULL) /內(nèi)存沒(méi)有作業(yè)運(yùn)行 if(ptr->size>=assign->size) /內(nèi)存空間大于作業(yè)所需空間，為內(nèi)存分配空間 ptr->size=ptr->size-assign->size; assign->state=1; ptr->next=assign; assign->former=ptr; cout<<"作

41、業(yè) "<<(assign->num)<<"申請(qǐng)"<<(assign->size)<<" "<<"k的內(nèi)存空間"<<endl; else cout<<"沒(méi)有足夠的內(nèi)存空間為作業(yè)"<<(assign->num)<<"分配"<<endl; delete assign; else /內(nèi)存中如果已經(jīng)分配了空間 MEMORY *previous,*current

42、; previous=ptr;/previous為鏈表中的第一個(gè)元素 current=previous->next; while(current!=NULL) /當(dāng)前區(qū)間不為空（最后一個(gè)區(qū)間的next為空），即沒(méi)有循環(huán)到最后 /如果當(dāng)前內(nèi)存空間大于作業(yè)所需空間并且內(nèi)存沒(méi)有被分配/則結(jié)束循環(huán)，當(dāng)前current位置即為要插入的位置 if(current->size>=assign->size&&current->state=0) break; previous=current; /previous后移 current=current->next

43、; if(current=NULL) /空閑鏈中沒(méi)有為作業(yè)分配所需的空間，即釋放的空閑區(qū)間小于要分配的作業(yè)空間 /不夠用，則在所有作業(yè)后邊另外再申請(qǐng)空閑區(qū)，如作業(yè)4 if(ptr->size>=assign->size) /內(nèi)存中還有足夠沒(méi)分配的空閑空間為此作業(yè)分配 /此時(shí)ptr指向內(nèi)存上未分配空閑空間的起始地址 assign->address =640-(ptr->size); ptr->size=ptr->size-assign->size; assign->state=1; assign->former=previous; pr

44、evious->next=assign; cout<<"作業(yè) "<<(assign->num)<<"申請(qǐng)"<<(assign->size)<<" "<<"k的內(nèi)存空間"<<endl; else cout<<"沒(méi)有足夠的內(nèi)存空間為作業(yè)"<<(assign->num)<<"分配"<<endl; else /釋放的空閑鏈中有可為

45、此作業(yè)分配的空間 if(current->size-assign->size)<=size_min) /空閑鏈所具備的空間與作業(yè)所需空間大小差不多時(shí) /直接把整個(gè)空閑塊的空間分配給作業(yè)否則從空閑塊中 current->num=assign->num; /劃出與作業(yè)等同的空間 current->state=1; delete assign; cout<<"作業(yè) "<<(current->num)<<"申請(qǐng)"<<(current->size)<<" "<<"k的內(nèi)存間"<<e