首次适应算法和循环首次适应算法

1、首次适应算法和循环首次适应算法一、实验目的1、加深操作系统内存管理过程的理解2、掌握内存分配算法的基本应用二、实验要求1. 在分配时，须按照一定的分配算法，从空闲分区表或空闲分区链中选取一分区分配给该作业2. 上机时独立完成编辑，调试程序。三、实验任务请同学们用C/C+实现一个完整的（可变）动态分区管理器，包括分配，回收，分区碎片整理等。希望同学们实现如下功能：n初始化功能：内存状态设置为初始状态。n分配功能：要求至少使用两种算法，用户可以 选择使用。n回收功能：n空闲块的合并：即紧凑功能，用以消除碎片。当做碎片整理时，需要跟踪分配的空间，修改其 引用以保证引用的正确性。n显示当前内存的使用状

2、态，可以使用表格或图 形。四、实验指导1. 基本思想动态分区是指系统不预先划分固定分区，而是在装入程序的时候划分内存区域， 使得为程序分配 的分区大小恰好等于该程序的需求虽，且分区的个数是动态的。显然动态分区有较大的灵活性， 较之固定分区能获得好的内存利用率。2. 数据结构动态分区管理可以用两种数据结构实现，一种是已分配区表和空闲区表， 也就是用预先定义好的 系统空间来存放空间分配信息。另一种也是最常用的就是空闲链表，由于对分区的操作是动态的，所以很难估计数据结构所占用 的空间，而且空闲区表会占用宝贵的系统空间，所以提出了空闲链表的概念。 其特点是用于管理分区的信息动态生成并和该分区在物理地址

3、上相邻。这样由于可以简单用两个空闲块之间的距 离定位已分配空间，不仅节约了系统空间，而且 不必维持已分配空间的信息。本实验是要做一个模拟程序，来模拟动态分区算法的分配和回收过程，并不是真正的去分配和回 收内存。基本的模拟方法有两种：(1) 、先从内存中申请一块存储区，对这块存储 区进行模拟的分配和回收活动。(2) 、不申请存储区，自己定义一块虚拟的存储 区，对这块存储区进行模拟的分配和回收活动， 分配和回收仅仅是对数据结构的修改而已。程序代码：#include<iostream>using namespace std;intFreePartition100;/空闲分区块数组intF

4、irstPartition100;/首次适应算法数组intCycleFirstPartition100;/循环首次适应算法数组intProcessNeed100;/每个作业的大小intPartitionNum,ProcessNum;/分区块数，作业数/首次适应算法void First()inti,j;charstr;for(i=0;i<PartitionNum;i+)(FirstPartitioni=FreePartitioni;for(i=0;i<ProcessNum;i+)/ 找出第一块满足作业的分区for(j=0;j<PartitionNum;j+)(if(Proces

5、sNeedi>FirstPartitionj)continue;else(FirstPartitionj-=ProcessNeedi;/找到后把分区大小减去作业的大小? ? ? ? ? ? ? ?str='A'+i;cout<<"作业"<<str<<"在第"<<j+1<<"块分区中”<<endl;break;cout<<endl;cout<<"分配之后剩余情况："<<endl;? ?for(i=0

6、;i<PartitionNum;i+) cout<<FirstPartitioni<<""cout<<endl<<endl;/循环首次适应算法voidCycleFirst()inti,j=1;charstr;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(Proc

7、essNeedi>CycleFirstPartitionj)/continue;j+；else(CycleFirstPartitionj-=ProcessNeedi;str='A'+i;cout<<"作业"<<str<<”在第”<<j+1<<"块分区中"<<endl;break;/j+;/cout<<j<<" "if(j=PartitionNum&&i!=ProcessNum)(i=-1;cout<

8、;<endl;cout<<"分配之后剩余情况："<<endl;for(i=0;i<PartitionNum;i+)cout<<CycleFirstPartitioni<<""cout<<endl<<endl;void main()(inti;cout<<"输入分区块数："<<endl;cin>>PartitionNum;cout<<"输入每个分区的大小："<<endl;fo

9、r(i=0;i<PartitionNum;i+)cin>>FreePartitioni;cout<<"输入作业数："<<endl;cin>>ProcessNum;cout<<"输入每个作业的大小："<<endl;for(i=0;i<ProcessNum;i+)cin>>ProcessNeedi;cout<<"首 次 适 应 算 法"<<endl;First();cout<<" 循环首次适应算法"<<endl;? ?CycleFirst();六、实验总结 在一开始老师布置这次的实验题目时， 自己根本不知道要干什么，因为在上课时对动态分区分配 这节内容不是太了解， 所以在上机时不知道如何下手，后来，将本章内容反复的看了几遍之后，终于有了自己的思路。在程序的编写过程中，我并没有按照书上所说的定 义了双向链表来实现各种算法的执行，我只简单的运用了结构体数组，通过这种方法比较容易理解与编写，在这几个算法中，只有循环首次适应算法编写起来有点困难，因为涉及到了循环，而其他的算法只运行一遍就能够得出所 要的效果，因此在程序中，我使用了一个全局变虽来掌控 循环以及记录上次运