基于c语言实现动态分区分配算法【100011543】

# 动态分区分配算法实现 # 一、需求分析 用C语言实现采用循环首次适应算法的动态分区分配过程alloc()和回收过程 free()。其中，空闲分区通过空闲分区链表来管理，在进行内存分配时，系统优先使用空闲区低端的空间。采用循环首次适应算法进行内存块的分配和回收，同时显示内存块分配和回收后空闲内存分区链的情况。 假设初始状态如下，可用的内存空间为640KB，并按照下列的请求序列进行内存的分配与回收： 作业1申请130KB；作业2申请60KB；作业3申请100KB；作业2释放60KB；作业4申请200 KB；作业3释放100 KB；作业1释放130 KB；作业5申请140 KB；作业6申请60 KB；作业7申请50KB；作业6释放60 KB 基本功能：设计与实现动态分区分配的数据结构与算法。根据作业大小，对空闲分区按照循环首次适应算法进行分配，回收分区时，按照回收算法进行合并回收。分配、回收后显示空闲分区状态。 扩展功能：同时实现首次适应算法、最佳适应算法、最坏适应算法。通过绘制分区状态图更直观地显示分配和回收过程，对比各种算法的差异和优劣。 # 二、概要设计 总体结构： 在C语言面向过程编程方法中，常用分层方法进行编程，降低各模块之间的耦合度。在操作系统中，也用到了分层思想进行设计，每一步设计都建立在可靠的基础上，这样易于扩充和维护系统。 在此次的课程设计中，同样也使用分层的方法，可以将各种算法很简单方便的一起实现。最底层是基本的数据结构，用来存储分区的信息。上一层是分配分区的函数alloc()和回收分区的函数free()。通过调用alloc()和free()函数可以实现四种算法。通过图形展示算法可以直观地显示分配和回收过程。最上一层 是程序的界面，允许用户可以自由的对内存进行分配和回收，程序展示动态结果。 总体结构如图1。  图1 程序总体结构 数据结构： 在实际的操作系统中，分配出去的内存记录在进程控制块中，为了加快内存的分配过程，动态分区最常采用的数据结构是空闲表或空闲链表，数据结构只记录未分配的内存分区。为了降低模拟程序的复杂度，本模拟将分配出去的和未分配出去的内存分区记录在同一个数据结构中，用一个标志表示是否已被分配。各分区按地址递增次序排列。内存的分配和回收只要是对数据结构做插入和删除操作，采用双向链表结构。 为使程序具有扩展性灵活性，分区大小采用宏定义方式（#define MEMORY_SIZE 640），可修改分区的大小，展示在不同分区大小下的分配情况。 ```c++ typedef struct SubAreaNode *SubAreaList; struct SubAreaNode { int addr; //分区起始地址 int size; //分区大小 int stat; //分区状态 宏定义 ALLOCED 1 FREE 0 int pid; //已分配分区的进程 id SubAreaList pre; SubAreaList next; } ; SubAreaList head; //全局变量 分区链表首指针 SubAreaList nowList; //当前位置分区指针 用于循环首次适应算法分区分配算法： ``` 接口：int alloc(int pid, int psize, SubAreaList p); 在链表位置p处为编号为pid，大小为psize的作业分配空间，链表p通过各种查找空闲分区算法（首次适应、循环首次适应、最佳适应、最坏适应）提供。 返回本次分配成功与否。 算法流程图见图2。  图2 分区分配算法流程图 回收分区算法： 接口：int freeAlloc(int pid)； 释放pid进程的分区空间，重新插入到空闲分区链表。返回值为本次回收是否成功。 回收时先遍历链表，找到进程pid所在的位置p，如果存在，可能出现下面四种情况之一： 回收区与前一空闲分区相邻，此时应将回收区与前一分区合并。 2） 回收区与后一空闲分区相邻，此时应将回收区与后一分区合并。 3） 回收区同时与前后两个空闲分区相邻，此时将三个分区合并。 回收区不相邻前后空闲分区，直接改为空闲分区。 算法流程图见图3。  图3 回收分区算法流程图 首次适应算法寻找分区位置： 接口：SubAreaList ffFindFreeSubArea(int psize); 按照首次适应算法从分区链表中找到第一个不小于psize的空闲分区，返回此分区地址。如果找不到可用的空闲分区返回NULL。 算法流程图见图4。 循环首次适应算法寻找分区位置： 接口：SubAreaList nfFindFreeSubArea(int psize); 按照循环首次适应算法从分区链表的当前位置开始寻找第一个不小于 psize的空闲分区，返回此分区地址。寻找结束后更新当前位置。当链表循环一圈后仍没有找到合适的空闲分区则返回NULL。 算法流程图见图5。   图4 首次适应算法寻找分区位置 图5 循环首次适应算法寻找分区位置 最佳适应算法寻找分区位置： 接口：SubAreaList bfFindFreeSubArea(int psize); 可以将所有空闲分区按照大小升序排列，从头寻找第一个符合要求的空间分区进行分配。在这里为简单起见，对链表线性搜索一轮，找到符合空间大小要求的最小的空闲分区。 算法流程图如图6。 最坏适应算法寻找分区位置： 接口：SubAreaList wfFindFreeSubArea(int psize); 可以将所有空闲分区按照大小降序排列，从头寻找第一个符合要求的空间分区进行分配。在这里为简单起见，对链表线性搜索一轮，找到符合空间大小要求的最大的空闲分区。 算法流程图如图7。   图6 最佳适应算法寻找分区位置 图7 最坏适应算法寻找分区位置 绘制状态图算法： 接口：void disAllocGraph(int prec); 用于绘制精度为prec的内存状态图。也即每MEMORY_SIZE/prec绘制一格。 程序界面： 接口：void selectAlogrithm(); 可选择进入不同算法进行内存分配和回收的演示，每个算法既支持手动输入分配回收序列，也支持从文件中输入分配回收序列。每进行一步即展示当前这一步的分配结果。展示时内存分配表和分配图并排展示，可以更直观清晰的看到内 存分配回收情况，加深对算法的理解程度。 # 三、运行环境 - 硬件环境： - cpu： Intel(R) Core(TM) i7-6500U CPU @ 2.50GHz × 4 内存：8G - 软件环境： - OS：Deepin Linux 15.6 64位 - Linux内核：Linux 4.15.0-21deepin-generic # 四、开发工具和编程语言 编辑软件： ```c++ Sublime Text 3 ``` 编译软件： ```c++ gcc version 7.2.0 ``` 编程语言： C语言 # 五、详细设计 链表初始化： ```c++ SubAreaList getASubArea() { return (SubAreaList)malloc(sizeof(struct SubAreaNode)); } //对空闲分区链表进行初始化，一整块空间为空 SubAreaList initSubArea() {