首次適應(yīng)算法和循環(huán)首次適應(yīng)算法

1、精選優(yōu)質(zhì)文檔-傾情為你奉上首次適應(yīng)算法和循環(huán)首次適應(yīng)算法一、 實(shí)驗(yàn)?zāi)康?、加深操作系統(tǒng)內(nèi)存管理過(guò)程的理解2、掌握內(nèi)存分配算法的基本應(yīng)用二、 實(shí)驗(yàn)要求1. 在分配時(shí)，須按照一定的分配算法，從空閑分區(qū)表或空閑分區(qū)鏈中選取一分區(qū)分配給該作業(yè)2. 上機(jī)時(shí)獨(dú)立完成編輯，調(diào)試程序。三、 實(shí)驗(yàn)任務(wù)請(qǐng)同學(xué)們用C/C+實(shí)現(xiàn)一個(gè)完整的（可變）動(dòng)態(tài)分區(qū)管理器，包括分配，回收，分區(qū)碎片整理等。希望同學(xué)們實(shí)現(xiàn)如下功能：n 初始化功能：內(nèi)存狀態(tài)設(shè)置為初始狀態(tài)。n 分配功能：要求至少使用兩種算法，用戶可以選擇使用。n 回收功能：n 空閑塊的合并：即緊湊功能，用以消除碎片。當(dāng)做碎片整理時(shí)，需要跟蹤分配的空間，修改其引用以保證

2、引用的正確性。n 顯示當(dāng)前內(nèi)存的使用狀態(tài)，可以使用表格或圖形。四、 實(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ì)占用寶貴的系統(tǒng)空間，所以提出了空閑鏈表的概念。其特點(diǎn)是用于管理分區(qū)的信息動(dòng)態(tài)生成并和

3、該分區(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)的修改而已。程序代碼：#include<iostream>using namespace std;int FreePartition100;/空閑分區(qū)塊數(shù)組int

4、 FirstPartition100;/首次適應(yīng)算法數(shù)組int CycleFirstPartition100;/循環(huán)首次適應(yīng)算法數(shù)組int ProcessNeed100;/每個(gè)作業(yè)的大小int PartitionNum,ProcessNum;/分區(qū)塊數(shù)，作業(yè)數(shù)/首次適應(yīng)算法void First()int i,j;char str;for(i=0;i<PartitionNum;i+)FirstPartitioni=FreePartitioni;for(i=0;i<ProcessNum;i+)/找出第一塊滿足作業(yè)的分區(qū)for(j=0;j<PartitionNum;j+)if(Pr

5、ocessNeedi>FirstPartitionj)continue;elseFirstPartitionj-=ProcessNeedi;/找到后把分區(qū)大小減去作業(yè)的大小? ? ? ? ? ? ? ?str='A'+i;cout<<"作業(yè)"<<str<<"在第"<<j+1<<"塊分區(qū)中"<<endl;break;cout<<endl;cout<<"分配之后剩余情況："<<endl;?

6、?for(i=0;i<PartitionNum;i+)cout<<FirstPartitioni<<" "cout<<endl<<endl;/循環(huán)首次適應(yīng)算法void CycleFirst()int i,j=1;char str;for(i=0;i<PartitionNum;i+)CycleFirstPartitioni=FreePartitioni;for(i=0;i<ProcessNum;i+)/for(j=0;j<PartitionNum;j+)j=j-1;while(j<Partition

7、Num)if(ProcessNeedi>CycleFirstPartitionj)/continue;j+;elseCycleFirstPartitionj-=ProcessNeedi;str='A'+i;cout<<"作業(yè)"<<str<<"在第"<<j+1<<"塊分區(qū)中"<<endl;break;/j+;/cout<<j<<" "if(j=PartitionNum && i!=Pr

8、ocessNum)i=-1;cout<<endl;cout<<"分配之后剩余情況："<<endl;for(i=0;i<PartitionNum;i+)cout<<CycleFirstPartitioni<<" "cout<<endl<<endl;void main()int i;cout<<"輸入分區(qū)塊數(shù)："<<endl;cin>>PartitionNum;cout<<"輸入每個(gè)分區(qū)的大小

9、："<<endl;for(i=0;i<PartitionNum;i+)cin>>FreePartitioni;cout<<"輸入作業(yè)數(shù)："<<endl;cin>>ProcessNum;cout<<"輸入每個(gè)作業(yè)的大?。?quot;<<endl;for(i=0;i<ProcessNum;i+)cin>>ProcessNeedi;cout<<"-首次適應(yīng)算法-"<<endl;First();cout<&

10、lt;"-循環(huán)首次適應(yīng)算法-"<<endl;? ?CycleFirst();六、 實(shí)驗(yàn)總結(jié) 在一開(kāi)始老師布置這次的實(shí)驗(yàn)題目時(shí)，自己根本不知道要干什么，因?yàn)樵谏险n時(shí)對(duì)動(dòng)態(tài)分區(qū)分配這節(jié)內(nèi)容不是太了解，所以在上機(jī)時(shí)不知道如何下手，后來(lái)，將本章內(nèi)容反復(fù)的看了幾遍之后，終于有了自己的思路。 在程序的編寫(xiě)過(guò)程中，我并沒(méi)有按照書(shū)上所說(shuō)的定義了雙向鏈表來(lái)實(shí)現(xiàn)各種算法的執(zhí)行，我只簡(jiǎn)單的運(yùn)用了結(jié)構(gòu)體數(shù)組，通過(guò)這種方法比較容易理解與編寫(xiě)，在這幾個(gè)算法中，只有循環(huán)首次適應(yīng)算法編寫(xiě)起來(lái)有點(diǎn)困難，因?yàn)樯婕暗搅搜h(huán)，而其他的算法只運(yùn)行一遍就能夠得出所要的效果，因此在程序中，我使用了一個(gè)全局變量來(lái)掌控循環(huán)以及記錄上次運(yùn)行到的地方，