2022年首次适应算法和循环首次适应算法 .pdf

首次适应算法和循环首次适应算法一、实验目的1、加深操作系统内存管理过程的理解2、掌握内存分配算法的基本应用二、实验要求1. 在分配时，须按照一定的分配算法，从空闲分区表或空闲分区链中选取一分区分配给该作业2. 上机时独立完成编辑，调试程序。三、实验任务请同学们用C/C+实现一个完整的（可变）动态分区管理器， 包括分配，回收，分区碎片整理等。希望同学们实现如下功能：n 初始化功能：内存状态设置为初始状态。n 分配功能：要求至少使用两种算法，用户可以选择使用。n 回收功能：n 空闲块的合并：即紧凑功能，用以消除碎片。当做碎片整理时，需要跟踪分配的空间，修改其引用以保证引用的正确性。n 显示当前内存的使用状态，可以使用表格或图名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 8 页 - - - - - - - - - 形。四、实验指导1基本思想动态分区是指系统不预先划分固定分区，而是在装入程序的时候划分内存区域，使得为程序分配的分区大小恰好等于该程序的需求量，且分区的个数是动态的。显然动态分区有较大的灵活性，较之固定分区能获得好的内存利用率。2数据结构动态分区管理可以用两种数据结构实现，一种是已分配区表和空闲区表，也就是用预先定义好的系统空间来存放空间分配信息。另一种也是最常用的就是空闲链表，由于对分区的操作是动态的， 所以很难估计数据结构所占用的空间，而且空闲区表会占用宝贵的系统空间，所以提出了空闲链表的概念。其特点是用于管理分区的信息动态生成并和该分区在物理地址上相邻。这样由于可以简单用两个空闲块之间的距离定位已分配空间，不仅节约了系统空间，而且不必维持已分配空间的信息。本实验是要做一个模拟程序，来模拟动态分区算法的分配和回收过程，并不是真正的去分配和回名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 8 页 - - - - - - - - - 收内存。基本的模拟方法有两种：（1） 、先从内存中申请一块存储区，对这块存储区进行模拟的分配和回收活动。（2） 、不申请存储区，自己定义一块虚拟的存储区，对这块存储区进行模拟的分配和回收活动，分配和回收仅仅是对数据结构的修改而已。程序代码：#include using namespace std; intFreePartition100;/空闲分区块数组intFirstPartition100;/首次适应算法数组intCycleFirstPartition100;/循环首次适应算法数组intProcessNeed100;/每个作业的大小intPartitionNum,ProcessNum;/分区块数，作业数/ 首次适应算法void First() 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 8 页 - - - - - - - - - inti,j; charstr; for(i=0;iPartitionNum;i+) FirstPartitioni=FreePartitioni; for(i=0;iProcessNum;i+)/找出第一块满足作业的分区for(j=0;jFirstPartitionj) continue; else FirstPartitionj-=ProcessNeedi;/找到后把分区大小减去作业的大小? ? ? ? ? ? ? ?str=A+i; cout 作业 str在第 j+1 块分区中 endl; break; coutendl; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 8 页 - - - - - - - - - cout 分配之后剩余情况：endl; ? ?for(i=0;iPartitionNum;i+) coutFirstPartitioni ; coutendlendl; / 循环首次适应算法voidCycleFirst() inti,j=1; charstr; for(i=0;iPartitionNum;i+) CycleFirstPartitioni=FreePartitioni; for(i=0;iProcessNum;i+) /for(j=0;jPartitionNum;j+) j=j-1; while(jCycleFirstPartitionj) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 8 页 - - - - - - - - - /continue; j+; else CycleFirstPartitionj-=ProcessNeedi; str=A+i; cout 作业 str在第 j+1 块分区中 endl; break; /j+; /coutj ; if(j=PartitionNum&i!=ProcessNum) i=-1; coutendl; cout 分配之后剩余情况：endl; for(i=0;iPartitionNum;i+) coutCycleFirstPartitioni ; coutendlendl; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 8 页 - - - - - - - - - void main() inti; cout 输入分区块数： PartitionNum; cout 输入每个分区的大小：endl; for(i=0;iFreePartitioni; cout 输入作业数： ProcessNum; cout 输入每个作业的大小：endl; for(i=0;iProcessNeedi; cout-首次适应算法-endl; First(); cout-循环首次适应算法-endl; ? ?CycleFirst(); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 8 页 - - - - - - - - - 六、 实验总结在一开始老师布置这次的实验题目时，自己根本不知道要干什么，因为在上课时对动态分区分配这节内容不是太了解，所以在上机时不知道如何下手，后来，将本章内容反复的看了几遍之后，终于有了自己的思路。在程序的编写过程中，我并没有按照书上所说的定义了双向链表来实现各种算法的执行，我只简单的运用了结构体数组， 通过这种方法比较容易理解与编写，在这几个算法中， 只有循环首次适应算法编写起来有点困难，因为涉及到了循环， 而其他的算法只运行一遍就能够得出所要的效果， 因此在程序中， 我使用了一个全局变量来掌控循环以及记录上次运行到的地方，只要理解了算法的主要思想， 编写程序就比较容易了。另外，还有一点是在本实验中还有一个算法没有编写，即快速适应算法， 这个算法必须要求使用链表，因为要根据其容量大小进行分类，将其单独设立一个空闲的分区链表。这是程序需要改进的地方， 由于这次临近考试，暂时没有编写， 在以后的时间中，一定会将此算法编写出来。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 8 页 - - - - - - - - -