動(dòng)態(tài)內(nèi)存分配(C語(yǔ)言)

1、實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)課程名稱：動(dòng)態(tài)內(nèi)存分配算法專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)班級(jí)：姓名：學(xué)號(hào)：實(shí)驗(yàn)學(xué)時(shí)：指導(dǎo)教師：成績(jī):實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)報(bào)告專業(yè)計(jì)算機(jī)科學(xué) 與技術(shù)班級(jí)姓名學(xué)號(hào)實(shí)驗(yàn)課 稈操作系統(tǒng)指導(dǎo)教 師實(shí)驗(yàn)日 期同實(shí)驗(yàn) 者實(shí)驗(yàn)項(xiàng)目動(dòng)態(tài)內(nèi)存分配算法實(shí)驗(yàn)設(shè) 備及器 材PC 機(jī)一臺(tái)，VC+6.0一、實(shí)驗(yàn)內(nèi)容與要求動(dòng)態(tài)分區(qū)分配又稱為可變分區(qū)分配，它是根據(jù)進(jìn)程的實(shí)際需要，動(dòng)態(tài)地為之分配內(nèi)存空間。在實(shí)驗(yàn)中運(yùn)用了三種基于順序搜索的動(dòng)態(tài)分區(qū)分配算法，分別是1首次適應(yīng)算法2. 循環(huán)首次適應(yīng)算法3.最佳適應(yīng)法3最壞適應(yīng)法分配主存空間。二、需求分析本次實(shí)驗(yàn)通過(guò)C語(yǔ)言進(jìn)行編程并調(diào)試、運(yùn)行，顯示出動(dòng)態(tài)分區(qū)的分配方式，直觀的展 示了首次適應(yīng)

2、算法循環(huán)首次適應(yīng)算法、最佳適應(yīng)算法和最壞適應(yīng)算法對(duì)內(nèi)存的釋放和回收方式之間 的區(qū)別。首次適應(yīng)算法 要求空閑分區(qū)鏈以地址遞增的次序鏈接，在分配內(nèi)存時(shí)，從鏈?zhǔn)组_始順序查找，直至找到一個(gè)大小能滿足要求的空閑分區(qū)為止，然后在按照作業(yè)的大小，從該分區(qū)中劃出一塊內(nèi)存空間，分配給請(qǐng)求者，余下的空余分區(qū)仍留在空鏈中。優(yōu)點(diǎn)：優(yōu)先利用內(nèi)存中彳氐址部分的空閑分區(qū)，從 而保留了高址部分的大空閑區(qū)，為以后到達(dá)的大作業(yè)分配大的內(nèi)存空間創(chuàng)造了條件。缺點(diǎn)：低址部分不斷被劃分，會(huì)留下許多難以利用的、很小的空閑分區(qū)即碎片。而每次查找又都是從低址部分開始的，這無(wú)疑又會(huì)增加查找可用空閑分區(qū)時(shí)的開銷。循環(huán)首次適應(yīng)算法在為進(jìn)程分配內(nèi)存空

3、間時(shí)，不是每次都從鏈?zhǔn)组_始查找，而是從上次找到的空閑分區(qū)的下一個(gè)空閑 分區(qū)開始查找，直到找到一個(gè)能滿足要求的空閑分區(qū)。優(yōu)點(diǎn)：該算法能使內(nèi)存中的空閑分區(qū)分布得更 均勻，從而減少了查找空閑分區(qū)時(shí)的開銷。最佳適應(yīng)算法該算法總是把能滿足要求、又是最小的空閑分區(qū)分配給作業(yè)，避免大材小用，該算法要求將所有 的空閑分區(qū)按其容量以從小到大的順序形成一空閑分區(qū)鏈。缺點(diǎn)：每次分配后所切割下來(lái)的剩余部分 總是最小的，這樣，在存儲(chǔ)器中會(huì)留下許多難以利用的碎片。最壞適應(yīng)算法最壞適應(yīng)算法選擇空閑分區(qū)的策略正好與最佳適應(yīng)算法相反：它在掃描整個(gè)空閑分區(qū)或鏈表時(shí)，總 會(huì)挑選一個(gè)最大的空閑區(qū)，從中切割一部分存儲(chǔ)空間給作業(yè)使用。該

4、算法要求，將所有的空閑分 區(qū)，按其容量以大到小的順序形成一空閑分區(qū)鏈。查找時(shí)，只要看第一個(gè)分區(qū)能否滿足作業(yè)要求即 可優(yōu)點(diǎn)：可使剩下的空閑區(qū)不至于太小，產(chǎn)生碎片的可能性最小，對(duì)中小作業(yè)有利，同時(shí)，最壞適應(yīng) 算法查找效率很高。缺點(diǎn)：導(dǎo)致存儲(chǔ)器中缺乏大的空閑分區(qū)三、數(shù)據(jù)結(jié)構(gòu)為了實(shí)現(xiàn)動(dòng)態(tài)分區(qū)分配算法，系統(tǒng)中配置了相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，用以描述空閑分區(qū)和已分配分區(qū)的情 況，常用的數(shù)據(jù)結(jié)構(gòu)有空閑分區(qū)表和空閑分區(qū)鏈流程圖(Wfe)讀入文件115首次適應(yīng)載住總應(yīng)餉M甘次適 應(yīng)垃壞適應(yīng)當(dāng)一個(gè)新作業(yè)要求裝入主存時(shí)，必須查空閑分區(qū)表，從中找出一個(gè)足夠大的空閑區(qū)。若找到的空閑 區(qū)大于作業(yè)需要量，這時(shí)應(yīng)把它分成兩部分，一部分

5、為占用區(qū)，另一部分為空閑區(qū)。當(dāng)一個(gè)作業(yè)撤離時(shí)，歸還的區(qū)域如果與其他空閑區(qū)相鄰，則合并成一個(gè)較大的空閑區(qū)，登錄在空閑 區(qū)表中 四、功能實(shí)現(xiàn)五、心得體會(huì)中途也遇到了許多通過(guò)本次實(shí)驗(yàn)，對(duì)動(dòng)態(tài)內(nèi)存分配的相尖知識(shí)有了更深的認(rèn)識(shí)， 困難，但幸運(yùn)的是最終的順利的解決并完成了此次試驗(yàn)，也更加熟練地掌握了尖于內(nèi) 存分配的使用六、源代碼#in clude using namespace std; int FreePartition100;/ int FirstPartition100;/ int CycleFirstPartition100;/ int BestPartition100;/ int WorstPa

6、rtition100;/ int ProcessNeed100;/空閑分區(qū)塊數(shù)組首次適應(yīng)算法數(shù)組循環(huán)首次適應(yīng)算法數(shù)組 最佳適應(yīng)算法數(shù)組最壞適應(yīng)算 法數(shù)組int PartitionNum,ProcessNum;/分區(qū)塊數(shù)，作業(yè)數(shù)/首次適應(yīng)算法 void First() int i,j;char str;for(i=0;iPartitionNum;i+)FirstPartiti on i=FreePartiti oni;)for(i=0;iProcessNum;i+)/找出第一塊滿足作業(yè)的分區(qū) for(j=0;jPartitionNum;j+)FirstPartitionj) continue;e

7、lseFirstPartitionj-=ProcessNeedi;/找到后把分區(qū)大小減去作業(yè)的大小str=7V+i; coutM 作業(yè)HstrH 在第Hj+1n 塊分區(qū)中 nendl;break;)coutendl;coutvv”分配之后剩余情況：”vvendl;for(i=0;iPartitionNum;i+) coutFirstPartitioniHcoutendlendl;)/循環(huán)首次適應(yīng)算法void CycleFirstOint i,j=1;char str;for(i=0;iPartitionNum;i+)CycleFirstPartitio ni=FreePartitioni;)f

8、or(i=0;iProcessNum;i+) /for(j=0;jPartitionNum;j+)j=j-1; while(jCycleFirstPartitionj) /continue;j+；elseCycleFirstPartitionj-=ProcessNeedi; str=A*+i;coutn 作業(yè)nstrn 在第Hj+1n 塊分區(qū)中 nendl; break;)j+;/coutjif(j=PartitionNum & i!=ProcessNum)i=-1;)coute ndl;coutvv” 分配之后剩余情況:nendl; for(i=0;iPartitionNum;i+)cout

9、CycleFirstPartitionicoute ndlvvendl;)/最佳適應(yīng)算法void Best()int i,j,k;char str; for(i=0;iPartitionNum;i+)BestPartitioni=FreePartitioni;)for(i=0;iProcessNum;i+)k=0; for(j=0;j=ProcessNeedi)break;)for(int n=O;nvPartitionNum;n+)if(BestPartitionn=ProcessNeedi)/ 找最 & 佳的k=n;BestPartitionk-=ProcessNeedi;str=,A,+

10、i;coutn 作業(yè)“vvstrvv” 在第Hj+1M 塊分區(qū)中 Hendl;)coute ndl;coutn 分配之后剩余情況:Hendl; for(i=0;iPartitionNum;i+)coutBestPartitionicoute ndlvvendl;/最壞適應(yīng)算法void Worst()int i,j,k;char str; for(i=0;iPartitionNum;i+)(WorstPartitioni=FreePartitioni;)for(i=0;iProcessNum;i+)k=0; for(j=0;jWorstPartitionk)/ 找到最大的分區(qū) k=j;)WorstPartitionk-=ProcessNeedi;str=,A,+i;cout作業(yè)”vvstrvv” 在第nj+1塊分區(qū)中 nendl;)coutendl;coutvv” 分配之后剩余情況:nendl; for(i=0;iPartitionNum;i+)coutWorstPartitionin ”；coute ndlvvendl;void main()int i;cout輸入分區(qū)塊數(shù)：”vvendl; cinPartitionNum;cout輸入每個(gè)分區(qū)的大小:Hendl; for(i=0;i FreePartitioni;cout輸入作業(yè)數(shù)：vvendl; cinProc