组号 成绩
计算机操作系统
课程设计报告
题目 基于可重定位分区分配算法的内存管理的设计与实现
专业： 计算机科学与技术 班级： 学号+姓名：
指导教师：
2016年12月 23 日
一． 设计目的
掌握内存的连续分配方式的各种分配算法
二． 设计内容
基于可重定位分区分配算法的内存管理的设计与实现。本系统模拟操作系统内存分配算法的实现，实现可重定位分区分配算法，采用PCB定义结构体来表示一个进程，定义了进程的名称和大小，进程内存起始地址和进程状态。内存分区表采用空闲分区表的形式来模拟实现。要求定义与算法相关的数据结构，如PCB、空闲分区；在使用可重定位分区分配算法时必须实现紧凑。
三． 设计原理
可重定位分区分配算法与动态分区分配算法基本上相同，差别仅在于：在这种分配算法中，增加了紧凑功能。通常，该算法不能找到一个足够大的空闲分区以满足用户需求时，如果所有的小的空闲分区的容量总和大于用户的要求，这是便须对内存进行“紧凑”，将经过“紧凑”后所得到的大空闲分区分配给用户。如果所有的小空闲分区的容量总和仍小于用户的要求，则返回分配失败信息
四． 详细设计及编码
1. 模块分析
（1）分配模块
这里采用首次适应(FF)算法。设用户请求的分区大小为u.size,内存中空闲分区大小为m.size,规定的不再切割的剩余空间大小为size。空闲分区按地址递增的顺序排列；在分配内存时，从空闲分区表第一个表目开始顺序查找，如果m.size≥u.size且m.size-u.size≤size，说明多余部分太小，不再分割，将整个分区分配给请求者；如果m.size≥u.size且m.size-u.size>size，就从该空闲分区中按请求的大小划分出一块内存空间分配给用户，剩余的部分仍留在空闲分区表中；如果m.size （2）内存回收模块 进行内存回收操作时，先随机产生一个要回收的进程的进程号，把该进程从进程表中中删除，它所释放的空闲内存空间插入到空闲分区表；如果回收区与插入点的前一个空闲分区 相邻，应将回收区与插入点的前一分区合并，修改前一个分区的大小；如果回收区与插入点的后一个空闲分区相邻，应将回收区与插入点的后一分区合并，回收区的首址作为新空闲分区的首址，大小为二者之和；如果回收区同时与插入点的前、后空闲分区相邻，应将三个分区合并，使用前一个分区的首址，取消后一个分区，大小为三者之和。 （3）紧凑模块 将内存中所有作业进行移动，使他们全都相邻接，把原来分散的多个空闲小分区拼接成一个大分区。 2. 流程图 分配失败返回 开始 请求分配u.size分区 否 否 空闲分区总和≥u.size? 找到>u.size的空闲区？ 是 是 3. 代码实现 #include 修改有关数据结构 返回分区号及首址 进行紧凑 按动态分区方式分配 #define TURE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 #define SIZE 15 ////////////////////////////进程表////////////// int ppNo=1; //用于递增生成进程号 int pLength=0; struct PCB { int pNo; //进程号(名) int pSize; // 进程大小 int pOccupy; // 实际占用的内存 int pStartAddr; // 进程起始地址 int pState; //进程状态 }; struct PCB pList[200]; //////////////////空闲分区表部分/////////////// 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/构造一个新的有头节点的空链表L Status 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(;i pLength--; }//ListDelete void pSort(struct PCB *pList){ //AAA/内存中的进程按始址递增排序 int i,j; struct PCB temp; for(i=0;i for(j=0;j if(pList[j].pStartAddr>pList[j+1].pStartAddr){ } temp=pList[j]; pList[j]=pList[j+1]; pList[j+1]=temp; pList[i]=pList[i+1];