动态内存分配

1、实验报告实验课程名称：动态内存分配算法指导教师：成 绩:年12月1日实验报告专业计算机科学 与技术班级姓名学号实验课 程操作系统指导教 师实验日 期同实验 者实验项 目动态内存分配算法实验设 备及器 材PC机一台，VC+6.0一、实验内容与要求动态分区分配又称为可变分区分配， 它是根据进程的实际需要，动态地为之分配 内存空间。在实验中运用了三种基于顺序搜索的动态分区分配算法，分别是1.首次适应算法2.循环首次适应算法3最佳适应法3最坏适应法分配主存空间。二、需求分析本次实验通过C语言进行编程并调试、运行，显示出动态分区的分配方式，直观的展示了首次适应算法循环首次适应算法、最佳适应算法和最坏适应

2、算法对内 存的释放和回收方式之间的区别。首次适应算法要求空闲分区链以地址递增的次序链接，在分配内存时，从链首开始顺序查找，直至找到一个大小能满足要求的空闲分区为止， 然后在按照作业的大小，从该分 区中划出一块内存空间，分配给请求者，余下的空余分区仍留在空链中。优点：优先利用内存中低址部分的空闲分区，从而保留了高址部分的大空闲区，为以后到达的大作业分配大的内存空间创造了条件。缺点：低址部分不断被划分，会留下许多难以利用的、很小的空闲分区即碎片。而每次查找又都是从低址部分开始的，这无疑又会增加查找可用空闲分区时的开循环首次适应算法 在为进程分配内存空间时，不是每次都从链首开始查找，而是从上次找到的

3、空闲 分区的下一个空闲分区开始查找，直到找到一个能满足要求的空闲分区。优点：该算法能使内存中的空闲分区分布得更均匀， 从而减少了查找空闲分区时 的开销。最佳适应算法该算法总是把能满足要求、又是最小的空闲分区分配给作业，避免大材小用，该算法要求将所有的空闲分区按其容量以从小到大的顺序形成一空闲分区链。缺点：每次分配后所切割下来的剩余部分总是最小的， 这样，在存储器中会留下 许多难以利用的碎片。最坏适应算法最坏适应算法选择空闲分区的策略正好与最佳适应算法相反：它在扫描整个空闲分区或链表时，总会挑选一个最大的空闲区，从中切割一部分存储空间给作业使 用。该算法要求，将所有的空闲分区，按其容量以大到小的

4、顺序形成一空闲分区 链。查找时，只要看第一个分区能否满足作业要求即可。优点：可使剩下的空闲区不至于太小，产生碎片的可能性最小，对中小作业有利， 同时，最坏适应算法查找效率很高。缺点：导致存储器中缺乏大的空闲分区三、数据结构为了实现动态分区分配算法，系统中配置了相应的数据结构，用以描述空闲分区 和已分配分区的情况，常用的数据结构有空闲分区表和空闲分区链 流程图当一个新作业要求装入主存时，必须查空闲分区表，从中找出一个足够大的空闲 区。若找到的空闲区大于作业需要量，这时应把它分成两部分，一部分为占用区, 另一部分为空闲区。当一个作业撤离时，归还的区域如果与其他空闲区相邻，则合并成一个较大的空 闲区

5、，登录在空闲区表中四、功能实现E:wangqDebugwangg.exe前人每个分区的大小=0 20 30蔚入作业数；525i适口 口口 次区区区_1412 3 第第第 一暮在 A B G分配之后剩余情况:is;分配之后剩余情況:"E:wanggDebugwa ngg.exen法算适口 口 口 &区区区一块豊 -12 3-第第第 一在苗在 一 = H G 一业业业-J LBII适口 口 口 坏区区区 -444 -第第第 一在在在 -ABC 一业业业分配之肓剩余情况;0 -E 10五、心得体会通过本次实验，对动态内存分配的相关知识有了更深的认识， 中途也遇到了许多困难，但幸运的

6、是最终的顺利的解决并完成了此次试验，也更加熟练地掌握了关 于内存分配的使用六、源代码#include<iostream>using namespace std;int FreePartition100;/int FirstPartition100;/int CycleFirstPartition100;/int BestPartition100;/int WorstPartition100;/int ProcessNeed100;/空闲分区块数组首次适应算法数组循环首次适应算法数组 最佳适应算法数组 最坏适应算法数组int PartitionNum,ProcessNum;/ 分区块

7、数，作业数 / 首次适应算法void First()int i,j;char str; for(i=0;i<PartitionNum;i+)FirstPartitioni=FreePartitioni;for(i=0;i<ProcessNum;i+)/ 找出第一块满足作业的分区 for(j=0;j<PartitionNum;j+)if(ProcessNeedi>FirstPartitionj) continue;elseFirstPartitionj-=ProcessNeedi;/ 找到后把分区大小减去作业的大小 str='A'+i;coutvv&quo

8、t;作业"vvstrvv"在第"<<j+1<<"块分区中"<<endl;break;cout<<endl;cout<<" 分配之后剩余情况： "<<endl;for(i=0;i<PartitionNum;i+)cout<<FirstPartitioni<<" "cout<<endl<<endl;/ 循环首次适应算法void CycleFirst()int i,j=1;char st

9、r;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+; else CycleFirstPartitionj-=ProcessNeedi; str='A'+i;coutvv"作业"vvstrvv

10、"在第"<<j+1<<"块分区中"<<endl; break;/j+;/cout<<j<<" "if(j=PartitionNum && i!=ProcessNum)i=-1;cout<<endl;cout<<" 分配之后剩余情况： "<<endl; for(i=0;i<PartitionNum;i+) cout<<CycleFirstPartitioni<<" &

11、quot;cout<<endl<<endl;/ 最佳适应算法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<<BestPartitionj<<" "<<ProcessNeedi<<endl; if(BestPartitionj>=P

12、rocessNeedi)k=j;break;for(int n=0;n<PartitionNum;n+)&& if(BestPartitionn<BestPartitionkBestPartitionn>=ProcessNeedi)/ 找最佳的 k=n;BestPartitionk-=ProcessNeedi; str='A'+i;coutvv"作业"vvstrvv"在第"<<j+1<<"块分区中"<<endl;cout<<endl;co

13、ut<<" 分配之后剩余情况： "<<endl; for(i=0;i<PartitionNum;i+) cout<<BestPartitioni<<" "cout<<endl<<endl;/ 最坏适应算法void Worst()int i,j,k;char str; for(i=0;i<PartitionNum;i+)WorstPartitioni=FreePartitioni;for(i=0;i<ProcessNum;i+)k=0; for(j=0;j<Pa

14、rtitionNum;j+)if(WorstPartitionj>WorstPartitionk)/找到最大的分区k=j;WorstPartitionk-=ProcessNeedi;str='A'+i;coutvv"作业"vvstrvv"在第"<<j+1<<"块分区中"<<endl;cout<<endl;cout<<" 分配之后剩余情况： "<<endl; for(i=0;i<PartitionNum;i+) cou

15、t<<WorstPartitioni<<" "cout<<endl<<endl;void main()int i;cout<<" 输入分区块数： "<<endl;cin>>PartitionNum;cout<<" 输入每个分区的大小： "<<endl;for(i=0;i<PartitionNum;i+) cin>>FreePartitioni;cout<<" 输入作业数： "<<endl; cin>>ProcessNum;cout<<" 输入每个作业的大小： "<<endl; for(i=0;i<ProcessNum;i+)