循環(huán)首次適應(yīng)的動態(tài)分區(qū)分配算法模擬

1、課程設(shè)計報告課程設(shè)計題目：循環(huán)首次適應(yīng)的動態(tài)分區(qū)分配算法模擬專業(yè)：計算機(jī)科學(xué)與技術(shù)班級：10204102姓名：譜學(xué)號：10204102指導(dǎo)教師：高小輝2013年1月11日1 .循環(huán)首次適應(yīng)算法 31 .概述32 .需求分析32 .實(shí)驗(yàn)指導(dǎo)41 .基本思想-42 .數(shù)據(jù)結(jié)構(gòu)43 .運(yùn)行環(huán)境64 .流程圖。65 .循環(huán)首次適應(yīng)算法代碼56 .調(diào)試結(jié)果11七、總結(jié)14八.參考文獻(xiàn), 14循環(huán)首次適應(yīng)算法1 . 概述：該算法是由首次適應(yīng)算法演變而成的。 在為進(jìn)程分配內(nèi)存空間時，不再 是每次都從鏈?zhǔn)组_始查找，而是從上次找到的空閑分區(qū)的下一個空閑分區(qū)開 始查找，直至找到一個能滿足要求的空閑分區(qū)， 從中劃出

2、一塊的請求大小相 等的內(nèi)存空間分配給作業(yè)。為實(shí)現(xiàn)該算法，應(yīng)設(shè)置一起始查找指針，用于指 示下一次起始查詢的空閑分區(qū)，并采用循環(huán)查找方式，即如果最后一個(鏈 尾)空閑分區(qū)的大小仍不能滿足要求， 則返回到第一個空閑分區(qū)，比較大小 是否滿足，找到后，應(yīng)調(diào)整起始查詢指針。2 .需求分析了解動態(tài)分區(qū)分配中使用的數(shù)據(jù)結(jié)構(gòu)和分配算法，并進(jìn)一步加深對動態(tài) 分區(qū)存儲管理方式及其實(shí)現(xiàn)過程的理解。采用首次適應(yīng)算法的動態(tài)分區(qū)分配 過程alloc()和回收過程free()。空閑分區(qū)通過空閑分區(qū)鏈表來管理， 在進(jìn)行內(nèi)存分配時，系統(tǒng)優(yōu)先使用空閑區(qū)低端的空間，即每次分配內(nèi)存空間是總是從低址部分開始進(jìn)行循環(huán)，找到第一個合適的空間

3、，便按作業(yè)所需分配的大小分配給作業(yè)。作業(yè)完成時，需要釋放作業(yè)所占空間，此時要考慮到四種情況：(1)回收區(qū)與插入點(diǎn)的前一個空閑分區(qū)相鄰接。此時將二者合并，修改前一分區(qū)的大小。(2)回收區(qū)與插入點(diǎn)的后一空閑分區(qū)相鄰接，將二者合并，用回收區(qū)的首址作為新空閑區(qū)的首址。(3)回收區(qū)同時與插入點(diǎn)的前后兩個空閑分區(qū)相鄰接，三者合并，使用前一空閑分區(qū)的表項和首址。(4)回收區(qū)單獨(dú)存在。二、實(shí)驗(yàn)指導(dǎo)1 .基本思想動態(tài)分區(qū)是指系統(tǒng)不預(yù)先劃分固定分區(qū)，而是在裝入程序的時候劃分內(nèi)存區(qū)域，使得為程序分配的分區(qū)大小恰好等于該程序的需求量，且分區(qū)的個數(shù)是動態(tài)的。顯然動態(tài)分區(qū)有較大的靈活性，較之固定分區(qū)能獲得好的內(nèi)存利用率。

4、2 .數(shù)據(jù)結(jié)構(gòu)動態(tài)分區(qū)管理可以用兩種數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)，一種是已分配區(qū)表和空閑區(qū)表，也就是 用預(yù)先定義好的系統(tǒng)空間來存放空間分配信息。另一種也是最常用的就是空閑鏈表，由于對分區(qū)的操作是動態(tài)的，所以很難估計 數(shù)據(jù)結(jié)構(gòu)所占用的空間，而且空閑區(qū)表會占用寶貴的系統(tǒng)空間，所以提出了空閑 鏈表的概念。其特點(diǎn)是用于管理分區(qū)的信息動態(tài)生成并和該分區(qū)在物理地址上相鄰。這樣由于可以簡單用兩個空閑塊之間的距離定位已分配空間，不僅節(jié)約了系統(tǒng)空間，而且不必維持已分配空間的信息。本實(shí)驗(yàn)是要做一個模擬程序，來模擬動態(tài)分區(qū)算法的分配和回收過程， 并不是真 正的去分配和回收內(nèi)存。基本的模擬方法有兩種：1、先從內(nèi)存中申請一塊存儲區(qū)，對

5、這塊存儲區(qū)進(jìn)行模擬的分配和回收活動。2、不申請存儲區(qū)，自己定義一塊虛擬的存儲區(qū)，對這塊存儲區(qū)進(jìn)行模擬的分配 和回收活動，分配和回收僅僅是對數(shù)據(jù)結(jié)構(gòu)的修改而已。三.運(yùn)行環(huán)境：1 .操作系統(tǒng) WINDOWS XP2 .編譯軟件 Microsoft Visual C+3 .電腦配置：主頻 3.0GHz 內(nèi)存512MB四.流程圖1.程序結(jié)構(gòu)如圖:word范文2.首次適應(yīng)算法的結(jié)構(gòu)如圖:五.循環(huán)首次適應(yīng)算法代碼#include <iostream>#include <stdlib.h>#include <stdio.h>using namespace std;stru

6、ct memorystruct memory *former; / 前向指針int address;/ 地址int num;/ 作業(yè)號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)算法void F_F(int); /依次初始化每個作業(yè)，并根據(jù)相應(yīng)算法對作業(yè)分配內(nèi)存void a

7、lloc(MEMORY *,MEMORY *);/分配內(nèi)存算法(包括兩種不同算法)void free(MEMORY *,int);/首次適應(yīng)算法回收內(nèi)存void sort(MEMORY *);/ 對內(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)入！");cout<<("nPlease select a number(1,

8、0)”);cout<<("n循環(huán)首次適應(yīng)算法");cout<<" 0-中止程序"<<endl;cin>>i;if(i=1) /首次適應(yīng)算法cout<<("n以下為首次適應(yīng)算法：n");init();exec();elseexit；void init()/初始化內(nèi)存容量mem=new MEMORY;mem->size=640;mem->former=0;mem->next=0;void exec()/執(zhí)行算法while(1)/選擇申請或釋放內(nèi)存操作cout&l

9、t;<"*"<<endl;cout<<"申請內(nèi)存請輸入作業(yè)號(1-6) "<<endl;cout<<"釋放內(nèi)存請輸入數(shù)字8"<<endl;cout<<"中止程序請輸入數(shù)字0"<<endl;cout<<"*"<<endl;int k;cin>>k;/根據(jù)k值選擇相應(yīng)的操作if(k>=1&&k<=7) F_F(k);if(k=8)int m;cou

10、t<<"請輸入要釋放的作業(yè)號："cin>>m; /選擇相應(yīng)的回收算法free(mem,m);else if(k=0)/回滾到選擇算法的步驟break;void F_F(int i) /依次初始化每個作業(yè)，并根據(jù)相應(yīng)算法對作業(yè)分配內(nèi)存intwork=130,60,100,200,160,60,50;/作業(yè)序列，i 從 1 開始(與作業(yè)號對應(yīng))，因此從第一個開始存放作業(yè)值，第 0個值為0,不是作業(yè)cout<<”請輸入要作業(yè)所需的內(nèi)存大小："MEMORY *running;running=(MEMORY *)malloc(sizeof

11、(MEMORY);if(running!=NULL) running->former=NULL;running->address=0;running->num=i; /i從1開始循環(huán)running->size=worki; /指定作業(yè)大/、running->state=0; /作業(yè)未分配running->next=NULL;/根據(jù)相應(yīng)算法為作業(yè)分配內(nèi)存，詳見 alloc函數(shù)alloc(mem,running); print(mem); cout<<endl;elsecout<<”沒有足夠的內(nèi)存空間"<<endl;

12、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)存 空閑"<<”起始地址為："<<temp->address<<"空閑空間大小為："<<temp->size<<"k"elsecout

13、<<" 內(nèi)存已分配"<<”起始地址為："<<temp->address<<”分配空間大小為:“<<temp->size<<"k" <<"運(yùn)行的作業(yè)號："<<temp->num;cout<<endl;temp=temp->next;void free(MEMORY *ptr,int i)/首次適應(yīng)算法 作業(yè)處理完后釋放內(nèi)存空間MEMORY *previous,*current;previous=p

14、tr; current=previous->next;while(current!=NULL) /循環(huán)直到找到需要釋放的作業(yè)位置if(current->state=1&&current->num=i) break;previous=current;current=current->next;if(current=NULL) cout<<”內(nèi)存中沒有任何作業(yè)！ ！ ！ "<<endl; return;else if(current->next=NULL) /當(dāng)前作業(yè)為內(nèi)存中最后一個作業(yè)if(previous->

15、state=0) /與前一個相鄰空閑區(qū)合并previous->size=previous->size+current->size;previous->next=NULL;cout<<" 作業(yè)"<<(current->num)<<" 釋放"<<(current->size)<<"k 的 空間"<<endl;print(mem);else /將狀態(tài)改為0,即為空閑區(qū)current->state=0;cout<<&q

16、uot; 作業(yè)"<<(current->num)<<" 釋放"<<(current->size)<<"k 的 空間"<<endl;print(mem);else if(current->next)->next=NULL)p6 /當(dāng)前作業(yè)為倒數(shù)第二個作業(yè)(此種情況還是要單列出來討論的否則會出現(xiàn)錯誤)if(previous->state=0&&(current->next)->state=0) /p7 /釋放的地址空間前后均為空閑區(qū)

17、previous->size=previous->size+current->size+(current->next)->size;previous->next=NULL; 與下邊else (其他情況的不同之處)cout<<" 作業(yè)"<<(current->num)<<" 釋放"<<(current->size)<<"k 的 空間"<<endl;print(mem);else if(previous->stat

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

19、if(current->next)->state=0) /p8 /釋放的地址空間后面有空閑塊則把它和后面的空閑塊合并current->size=current->size+(current->next)->size;current->state=0;current->next=NULL; / 與下邊else (其他情況的不同之處)cout<<" 作業(yè)"<<(current->num)<<" 釋放"<<(current->size)<<&

20、quot;k 的空間"<<endl;print(mem);else /釋放的地址空間前后都沒有空閑塊時直接把它的狀態(tài)改為0current->state=0;cout<<" 作業(yè)"<<(current->num)<<" 釋放"<<(current->size)<<"k 的空間"<<endl;print(mem);else /其他情況下(當(dāng)前作業(yè)在鏈表中問)if(previous->state=0&&(cu

21、rrent->next)->state=0) /p7 /所釋放空間前后均為空閑區(qū)previous->size=previous->size+current->size+(current->next)->size;(current->next)->next)->former=previous;previous->next=(current->next)->next;cout<<" 作業(yè)"<<(current->num)<<" 釋放"<

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

23、gt;num)<<" 釋放"<<(current->size)<<“k 的 空間"<<endl;print(mem);else if(current->next)->state=0) p8 /釋放的地址空間后面有空閑塊則把它和后面的空閑塊合并current->size=current->size+(current->next)->size;current->state=0;(current->next)->next)->former=current;c

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

25、t;<" 釋放"<<(current->size)<<"k 的 空間"<<endl;print(mem);void alloc(MEMORY *ptr,MEMORY *assign)/根據(jù)算法分配內(nèi)存(is_optimist 狀態(tài))if(ptr->next=NULL) /內(nèi)存沒有作業(yè)運(yùn)行if(ptr->size>=assign->size)/內(nèi)存空間大于作業(yè)所需空間，為內(nèi)存分配空間ptr->size=ptr->size-assign->size;assign->

26、;state=1;ptr->next=assign;assign->former=ptr;cout<<" 作業(yè)"<<(assign->num)<<"申請"<<(assign->size)<<""<<"k 的內(nèi)存空間"<<endl;elsecout<<”沒有足夠的內(nèi)存空間為作業(yè)"<<(assign->num)<<"分配"<<en

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

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

29、n->state=1;assign->former=previous;previous->next=assign;cout<<" 作業(yè)"<<(assign->num)<<"申請“<<(assign->size)<<" "<<"k 的 內(nèi)存空間"<<endl;)elsecout<<"沒有足夠的內(nèi)存空間為作業(yè)"<<(assign->num)<<"

30、分配"<<endl;) else釋放的空閑鏈中有可為此作業(yè)分配的空間if(current->size-assign->size)<=size_min) /空閑鏈所具備的空間與作業(yè)所需空間大小差不多時/直接把整個空閑塊的空間分配給作業(yè)否則從空閑塊中current->num=assign->num; /戈U出與作業(yè)等同的空間current->state=1;delete assign;cout<<" 作業(yè)"<<(current->num)<<" 申請“<<(

31、current->size)<<" "<<"k的內(nèi)存間"<<endl;)else 從空閑塊中劃分一塊與作業(yè)大小等同的空間current->size=current->size-assign->size;assign->state=1;assign->address=current->address+current->size;if(current->next=NULL) /此要分配的空間是空閑鏈的最后一個元素assign->former=current;cur

32、rent->next=assign;elseassign->next=current->next;(current->next)->former=assign;assign->former=current;current->next=assign;"<<"k 的cout<<" 作業(yè)"<<(assign->num)<<"申請"<<(assign->size)<< 內(nèi)存空間"<<endl;六.

33、調(diào)試結(jié)果1輸入條件作業(yè)1申請130KB 作業(yè)2申請60KB作業(yè)3申請100KB;作業(yè)2釋放60KB;作業(yè)4申請200 KB; 作業(yè)3釋放100 KB;作業(yè)1釋放130 KB; 作業(yè)5申請140 KB;作業(yè)6中請60 KB;作業(yè)7中請50KB;作業(yè)6釋放60 KB2 運(yùn)行結(jié)果：'C: KDoctmenrs and 551111£$&(1M111匕七工01口工熹面41，皿&，12也£/KiESAllkleci-ac 宮匕 1匚心匕 a miFibui'Wl.甲 0-循環(huán)首次適應(yīng)算怯。一中止程序1以下為首次固應(yīng)算法;JOtXJtMJHJC J（幀 MX鵬M KU JCJIiHJIJCMJCJlM：由業(yè)號1”G電,55® 家版時奉請, 中止隹序請&?II.70HiKHM K KK- 1K N- MM MM MM XM K MMM+C M-KM H請輸入要作業(yè)所需的內(nèi)存大小：作業(yè)S申請。k的內(nèi)存空司 內(nèi)存鏈的狀態(tài)為：內(nèi)存已分配起始地址為河分配空