基于可重定位分区分配算法的内存管理的设计与实现
组号 成绩 计算机操作系统课程设计报告 题目 基于可重定位分区分配算法的内存管理的设计与实现 专业： 计算机科学与技术 班级： 学号+姓名: 指导教师: 2016年12月 23 日一 设计目的掌握内存的连续分配方式的各种分配算法二 设计内容基于可重定位分区分配算法的内存管理的设计与实现。本系统模拟操作系统内存分配算法的实现，实现可重定位分区分配算法,采用PCB定义结构体来表示一个进程，定义了进程的名称和大小，进程内存起始地址和进程状态。内存分区表采用空闲分区表的形式来模拟实现。要求定义与算法相关的数据结构,如PCB、空闲分区；在使用可重定位分区分配算法时必须实现紧凑。三 设计原理可重定位分区分配算法与动态分区分配算法基本上相同，差别仅在于：在这种分配算法中，增加了紧凑功能.通常,该算法不能找到一个足够大的空闲分区以满足用户需求时,如果所有的小的空闲分区的容量总和大于用户的要求，这是便须对内存进行“紧凑"，将经过“紧凑”后所得到的大空闲分区分配给用户.如果所有的小空闲分区的容量总和仍小于用户的要求，则返回分配失败信息四 详细设计及编码1. 模块分析（1） 分配模块这里采用首次适应(FF）算法.设用户请求的分区大小为u。size，内存中空闲分区大小为m。size,规定的不再切割的剩余空间大小为size.空闲分区按地址递增的顺序排列；在分配内存时,从空闲分区表第一个表目开始顺序查找，如果m。sizeu。size且m.sizeu。sizesize，说明多余部分太小，不再分割，将整个分区分配给请求者；如果m。sizeu.size且m。sizeu。size>size，就从该空闲分区中按请求的大小划分出一块内存空间分配给用户，剩余的部分仍留在空闲分区表中；如果m.sizeu。size则查找下一个空闲分区表项，直到找到一个足够大的空闲分区;如果没有找到一个足够大的内存空闲分区，但所有的小的空闲分区的容量总和大于用户的要求，就进行紧凑,将紧凑后得到的大的空闲分区按上述的方式分配给用户；但如果所有的小的空闲分区的容量总和仍不能满足用户需要，则分配失败。（2） 内存回收模块进行内存回收操作时，先随机产生一个要回收的进程的进程号,把该进程从进程表中中删除，它所释放的空闲内存空间插入到空闲分区表；如果回收区与插入点的前一个空闲分区相邻，应将回收区与插入点的前一分区合并，修改前一个分区的大小；如果回收区与插入点的后一个空闲分区相邻，应将回收区与插入点的后一分区合并，回收区的首址作为新空闲分区的首址，大小为二者之和；如果回收区同时与插入点的前、后空闲分区相邻，应将三个分区合并，使用前一个分区的首址，取消后一个分区,大小为三者之和。（3） 紧凑模块将内存中所有作业进行移动，使他们全都相邻接，把原来分散的多个空闲小分区拼接成一个大分区。2. 流程图开始请求分配u.size分区找到>u.size的空闲区？按动态分区方式分配空闲分区总和u.size?进行紧凑修改有关数据结构分配失败返回返回分区号及首址 否 否 是 是 3. 代码实现include<stdio。h#includestdlib。h>includetime。h>#includewindows。h#define TURE 1define FALSE 0#define OK 1#define ERROR 0define INFEASIBLE -1define OVERFLOW -2#define SIZE 15 /进程表/int ppNo=1; /用于递增生成进程号 int pLength=0;struct PCBint pNo； /进程号（名)int pSize； / 进程大小 int pOccupy； / 实际占用的内存 int pStartAddr; / 进程起始地址 int pState； /进程状态 ;struct PCB pList200;/空闲分区表部分/typedef int Status;typedef struct emptyNode /空闲分区结构体 int areaSize； /空闲分区大小 int aStartAddr； /空闲分区始址 struct emptyNode next；emptyNode,LinkList；int ListDelete（struct PCB *pList，int i);/AAA/删除下标为i的进程 void pSort(struct PCB *pList); /AAA/内存中的进程按始址递增排序 void compact（LinkList &L，struct PCB *pList)；/AAA/紧凑 ,内存中进程移动，修改进程数据结构；空闲分区合并，修改空闲分区表数据结构 void amalgamate（LinkList L）； /AAA/回收后进行合并空闲分区 void recycle(LinkList L，struct PCB pList); /AAA/回收 ，从进程表中删除进程 ，把释放出的空间插入到空闲分区链表中 Status InitList（LinkList L)； /1AAA/构造一个新的有头节点的空链表LStatus ClearList(LinkList &L）； /2AAA/将链表L重置为空表Status ListInsert(LinkList L,LinkList s1）； /AAA/*根据始址进行插入 void DeleteElem（LinkList L，int aStartAddr）；/*删除线性表中始址值为aStartAddr的结点void PrintList(LinkList L)； /AAA/*输出各结点的值void creatP（struct PCB p); /AAA/初始化进程int search(LinkList &L,int pSize）； /AAA/检索分区表 ,返回合适分区的首址 int add（LinkList &L); /AAA/返回空闲分区总和 void pListPrint(struct PCB pList）； /AAA/输出内存中空间占用情况 void distribute（LinkList L，struct PCB process）;int ListDelete（struct PCB pList，int i）/AAA/删除下标为i的进程 for（；ipLength-1;i+)pListi=pListi+1;pLength-;/ListDeletevoid pSort（struct PCB *pList） /AAA/内存中的进程按始址递增排序 int i,j;struct PCB temp；for（i=0;i<pLength-1;i+）for(j=0；jpLength-i1；j+)if(pListj。pStartAddrpListj+1。pStartAddr）temp=pListj;pListj=pListj+1；pListj+1=temp；/AAA/紧凑 ,内存中进程移动，修改进程数据结构；空闲分区合并，修改空闲分区表数据结构 void compact（LinkList L，struct PCB pList) printf("进行紧凑n"）; /1、进程移动，修改进程数据结构int i；pList0.pStartAddr=0； /第一个进程移到最上面 for（i=0;ipLength1;i+)pListi+1。pStartAddr=pListi.pStartAddr+pListi。pOccupy;/2、 空闲分区合并，修改空闲分区表数据结构 LinkList p=L-next，s;int sumEmpty=0;while（p!=NULL)/求空闲区总和 sumEmpty+=p->areaSize；p=pnext;ClearList(L)； /清空空闲分区表s=(LinkList）malloc(sizeof（emptyNode）；s-aStartAddr=pListpLength1。pStartAddr+pListpLength1。pOccupy； s>areaSize=sumEmpty；ListInsert（L，s); printf("n紧凑后的>n”）; pListPrint(pList）;PrintList（L);void amalgamate（LinkList &L）/AAA/回收后进行合并空闲分区 LinkList p=Lnext,q=p->next;while（q！=NULL）if(p-aStartAddr+p-areaSize=q-aStartAddr）pareaSize+=qareaSize；DeleteElem（L，qaStartAddr);/删除被合并的结点q=pnext； elsep=q;q=q>next；/AAA/回收 ，从进程表中删除进程 ,把释放出的空间插入到空闲分区链表中 void recycle（LinkList &L，struct PCB *pList） int index
