可重定向动态分区分配算法.docx

组号 成绩 计算机操作系统课程设计报告 题目 内存的连续分配算法 基于动态分区分配的内存管理的模拟设计与实现专业：班级：学号+姓名： 指导教师： 2016年12月 22 日一.设计目的掌握内存的连续分配方式的各种分配算法。二.设计内容 本系统模拟操作系统内存分配算法的实现，实现动态分区分配，算法，采用PCB定义结构体来表示一个进程，定义了进程的名称和大小，进程内存起始地址和进程状态。内存分区表采用单链表来模拟实现。定义与算法相关的数据结构，如PCB，空闲分区；在使用动态分区分配算法时必须实现紧凑功能。三．设计原理 1.首次适应算法分配内存：空闲分区链以地址递增的次序链接。进行内存分配时，从链首开始顺序查找，直到找到一个大小能满足要求的空闲分区为止。然后再按照作业的大小，从该分区中划出一块内存空间，分配给请求者，余下的空闲分区仍留在空闲链中。若从链首直至链尾都不能找到一个能满足要求的分区，则表明系统中已没有足够大的内存分配给该进程，内存分配结束，返回。2.回收内存：当进程运行完毕释放内存时，系统根据回收区的首址，从空闲区链中找到相应的插入点：（1）回收区与插入点的前一个空闲分区F1相邻接，此时应将回收区与插入点的前一分区合并，不必为回收分区分配新表项，而只需要修改前一分区F1的大小。（2）回收区与插入点的后一个空闲分区F2相邻接，此时将两分区合并形成新的空闲分区，但用回收区的首址作为新空闲区的首址，大小为两者之和。 （3）回收区与插入点的前后两个空闲分区相邻接，此时将三个分区合并，使用F1的表项和F1的首址，取消F2的表项，大小为三者之和。（4）回收区与插入点的前后两个空闲分区均不相邻接，此时应为回收区单独建立一个新表项，填写回收区的首址和大小，并根据其首址插入到空闲链中的适当位置。 3.紧凑：将内存中的所有作业移动，使他们全都相邻接。可以把原来分散的多个空闲小分区拼接成一个大分区，可将一个作业装入该区。这种技术称为“紧凑”。四．详细设计及编码1.模块分析①paixu()：排序算法。按分区的起始位置以递增的次序排序。②compact()：紧凑算法。记录每个忙碌分区的首址及大小，改变其首址。计算所有空闲分区的大小为新空闲分区的大小，首址为所有忙碌分区的大小总和。③show(FENQU *p)：输出函数。输出分区信息（首址，大小，状态，进程号）。④input()：输入函数。输入分区信息（分区个数，各分区首址，大小，状态，进程号）。调用show(FENQU *p)函数。⑤FENQU *scsf()：（递归算法）首次适应算法。进行内存分配时，从链首开始顺序查找，直到找到一个大小能满足要求的空闲分区为止。调用compact()函数。⑥FENQU * huishou()：回收算法。当进程运行完毕释放内存时，系统根据回收区的首址，从空闲区链中找到相应的插入点，判断相应情况进行后续动作。⑦void function()：逻辑函数。从键盘输入选择，实现相应操作。调用scsf()，huishou()，show(p)函数。⑧int main()：主函数。调用input()，function()函数。流程图进行紧凑形成连续空闲区空闲分区总和≥u.size?NYN找到＞u.size的分区?无法分配，返回请求分配u.size分区修改有关的数据结构进行紧凑形成连续空闲区按动态分区方式进行分配Y返回分区号及首址代码实现#includestdio.h#includestdlib.h#includestring.htypedef struct memory{ int startaddress;//首址 int size;//大小 char state[10];//状态 int number;//进程号 struct memory *next;}FENQU;FENQU *ready=NULL, *p;void paixu();int len();void compact();void show(FENQU *p){ printf(%d\t,p-startaddress); printf(%d\t,p-size); printf(%s\t,p-state); printf(%d\t\n\n,p-number);}//输入分区信息 void input(){ int i,address,size1,n,number1; printf(请输入分区个数：); scanf(%d,n); for(i=1;i=n;i++){ p=(FENQU*)malloc(sizeof(FENQU)); printf(请输入第%d个分区的起始地址：,i); scanf(%d,address); p-startaddress=address; printf(请输入第%d个分区