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

1、實(shí)驗(yàn)報(bào)告實(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ī)： 年12月1日實(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)通過C語言進(jìn)行編程并調(diào)試、運(yùn)行，顯示出動(dòng)態(tài)分區(qū)的分配方式

2、，直觀的展示了首次適應(yīng)算法循環(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ū)即碎片。而每次查找又都是從低址部分開始的，這無疑又會(huì)增加查找可用空閑分區(qū)時(shí)的開銷。循環(huán)首次適應(yīng)算法在為

3、進(jìn)程分配內(nèi)存空間時(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)：每次分配后所切割下來的剩余部分總是最小的，這樣，在存儲(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ū)鏈流程圖當(dāng)一個(gè)新作業(yè)要求裝入主存時(shí)，必須查空閑分區(qū)表，從中找出一個(gè)足夠大的空閑區(qū)。若找到的空閑區(qū)大于作業(yè)需要量，這時(shí)應(yīng)把它分成兩部分，一部分為占用區(qū)，另一部分為空閑區(qū)。當(dāng)一個(gè)作業(yè)撤離時(shí)，歸還的區(qū)域如果與其他

5、空閑區(qū)相鄰，則合并成一個(gè)較大的空閑區(qū)，登錄在空閑區(qū)表中。四、功能實(shí)現(xiàn)五、心得體會(huì)通過本次實(shí)驗(yàn)，對(duì)動(dòng)態(tài)內(nèi)存分配的相關(guān)知識(shí)有了更深的認(rèn)識(shí)，中途也遇到了許多困難，但幸運(yùn)的是最終的順利的解決并完成了此次試驗(yàn)，也更加熟練地掌握了關(guān)于內(nèi)存分配的使用。六、源代碼#include<iostream>using namespace std;int FreePartition100;/空閑分區(qū)塊數(shù)組int FirstPartition100;/首次適應(yīng)算法數(shù)組int CycleFirstPartition100;/循環(huán)首次適應(yīng)算法數(shù)組int BestPartition100;/最佳適應(yīng)算法數(shù)組int

6、WorstPartition100;/最壞適應(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(ProcessNeedi>FirstPartitionj)continue;

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

8、ni<<" "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<PartitionNum)if(ProcessNeedi>CycleFirstPartitionj)/continue;j

9、+;elseCycleFirstPartitionj-=ProcessNeedi;str='A'+i;cout<<"作業(yè)"<<str<<"在第"<<j+1<<"塊分區(qū)中"<<endl;break;/j+;/cout<<j<<" "if(j=PartitionNum && i!=ProcessNum)i=-1;cout<<endl;cout<<"分配之后剩余

10、情況："<<endl;for(i=0;i<PartitionNum;i+)cout<<CycleFirstPartitioni<<" "cout<<endl<<endl;/最佳適應(yīng)算法void Best()int i,j,k;char str; for(i=0;i<PartitionNum;i+)BestPartitioni=FreePartitioni;for(i=0;i<ProcessNum;i+)k=0;for(j=0;j<PartitionNum;j+)/cout<&

11、lt;BestPartitionj<<" "<<ProcessNeedi<<endl;if(BestPartitionj>=ProcessNeedi)k=j;break; for(int n=0;n<PartitionNum;n+) if(BestPartitionn<BestPartitionk && BestPartitionn>=ProcessNeedi)/找最佳的 k=n; BestPartitionk-=ProcessNeedi;str='A'+i;cout<<

12、"作業(yè)"<<str<<"在第"<<j+1<<"塊分區(qū)中"<<endl;cout<<endl;cout<<"分配之后剩余情況："<<endl;for(i=0;i<PartitionNum;i+)cout<<BestPartitioni<<" "cout<<endl<<endl;/最壞適應(yīng)算法void Worst()int i,j,k;char str

13、;for(i=0;i<PartitionNum;i+)WorstPartitioni=FreePartitioni;for(i=0;i<ProcessNum;i+)k=0;for(j=0;j<PartitionNum;j+)if(WorstPartitionj>WorstPartitionk)/找到最大的分區(qū) k=j;WorstPartitionk-=ProcessNeedi;str='A'+i;cout<<"作業(yè)"<<str<<"在第"<<j+1<<&q

14、uot;塊分區(qū)中"<<endl;cout<<endl;cout<<"分配之后剩余情況："<<endl;for(i=0;i<PartitionNum;i+)cout<<WorstPartitioni<<" "cout<<endl<<endl;void main()int i;cout<<"輸入分區(qū)塊數(shù)："<<endl;cin>>PartitionNum;cout<<"輸入每個(gè)分區(qū)的大?。?quot;<<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>>