基于可重定位分区分配算法的内存管理的设计与实现-课程设计报告.docx

组号 成绩 计算机操作系统课程设计报告 题目 基于可重定位分区分配算法的内存管理的设计与实现 专业： 计算机科学与技术 班级： 学号+姓名： 指导教师： 2016年12月 23 日一 设计目的掌握内存的连续分配方式的各种分配算法二 设计内容基于可重定位分区分配算法的内存管理的设计与实现。本系统模拟操作系统内存分配算法的实现，实现可重定位分区分配算法，采用PCB定义结构体来表示一个进程，定义了进程的名称和大小，进程内存起始地址和进程状态。内存分区表采用空闲分区表的形式来模拟实现。要求定义与算法相关的数据结构，如PCB、空闲分区；在使用可重定位分区分配算法时必须实现紧凑。三 设计原理可重定位分区分配算法与动态分区分配算法基本上相同，差别仅在于：在这种分配算法中，增加了紧凑功能。通常，该算法不能找到一个足够大的空闲分区以满足用户需求时，如果所有的小的空闲分区的容量总和大于用户的要求，这是便须对内存进行“紧凑”，将经过“紧凑”后所得到的大空闲分区分配给用户。如果所有的小空闲分区的容量总和仍小于用户的要求，则返回分配失败信息四 详细设计及编码1. 模块分析（1） 分配模块这里采用首次适应(FF)算法。设用户请求的分区大小为u.size,内存中空闲分区大小为m.size,规定的不再切割的剩余空间大小为size。空闲分区按地址递增的顺序排列；在分配内存时，从空闲分区表第一个表目开始顺序查找，如果m.sizeu.size且m.size-u.sizesize，说明多余部分太小，不再分割，将整个分区分配给请求者；如果m.sizeu.size且m.size-u.size>size，就从该空闲分区中按请求的大小划分出一块内存空间分配给用户，剩余的部分仍留在空闲分区表中；如果m.size<u.size则查找下一个空闲分区表项，直到找到一个足够大的空闲分区；如果没有找到一个足够大的内存空闲分区，但所有的小的空闲分区的容量总和大于用户的要求，就进行紧凑，将紧凑后得到的大的空闲分区按上述的方式分配给用户；但如果所有的小的空闲分区的容量总和仍不能满足用户需要，则分配失败。（2） 内存回收模块进行内存回收操作时，先随机产生一个要回收的进程的进程号，把该进程从进程表中中删除，它所释放的空闲内存空间插入到空闲分区表；如果回收区与插入点的前一个空闲分区相邻，应将回收区与插入点的前一分区合并，修改前一个分区的大小；如果回收区与插入点的后一个空闲分区相邻，应将回收区与插入点的后一分区合并，回收区的首址作为新空闲分区的首址，大小为二者之和；如果回收区同时与插入点的前、后空闲分区相邻，应将三个分区合并，使用前一个分区的首址，取消后一个分区，大小为三者之和。（3） 紧凑模块将内存中所有作业进行移动，使他们全都相邻接，把原来分散的多个空闲小分区拼接成一个大分区。2. 流程图开始请求分配u.size分区找到>u.size的空闲区？按动态分区方式分配空闲分区总和u.size?进行紧凑修改有关数据结构分配失败返回返回分区号及首址 否 否 是 是 3. 代码实现#include<stdio.h>#include<stdlib.h>#include<time.h>#include<windows.h>#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 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(;i<pLength-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;j<pLength-i-1;j+)if(pListj.pStartAddr>pListj+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;i<pLength-1;i+)pListi+1.pStartAddr=pListi.pStartAddr+pListi.pOccupy;/2、 空闲分区合并，修改空闲分区表数据结构 LinkList p=L->next,s;int sumEmpty=0;while(p!=NULL)/求空闲区总和 sumEmpty+=p->areaSize;p=p->next;ClearList(L); /清空空闲分区表s=(LinkList)malloc(sizeof(emptyNode);s->aStartAddr=pListpLength-1.pStartAddr+pListpLength-1.pOccupy; s->areaSize=sumEmpty;ListInsert(L,s); printf("n紧凑后的>>>>n"); pListPrint(pList);PrintList(L);void amalgamate(LinkList &L)/AAA/回收后进行合并空闲分区 LinkList p=L->next,q=p->next;while(q!=NULL)if(p->aStartAddr+p->areaSize=q->aStartAddr)p->areaSize+=q->areaSize;DeleteElem(L,q->aStartAddr);/删除被合并的结点q=p->next; elsep=q;q=q->next;/AAA/回收 ，从进程表中删除进程 ，把释放出的空间插入到空闲分区链表中 void recycle(LinkList &L,struct PCB *pList) int index,delPNo,delPSize,delPOccupy,delPStartAddr; LinkList s; srand(time(0); index=rand()%pLength; delPNo=pListindex.pNo; delPSize=pListindex.pSize; delPOccupy=pListindex.pOccupy; delPStartAddr=pListindex.pStartAddr; printf("_"); printf("回收内存 进程 P%d: 始址：%d K 占用：%d KBn",delPNo,delPStartAddr,delPOccupy); printf("n回收后>>>>n"); ListDelete(pList,index); /pListPrint(pList); s=(LinkList)malloc(sizeof(emptyNode);s->areaSize=delPOccupy; s->aStartAddr=delPStartAddr; ListInsert(L,s); amalgamate(L); pListPrint(pList);/输出内存中空间占用情况 PrintList(L); /Status InitList(LinkList &L) /1AAA/构造一个新的有头节点的空链表LLinkList s;L=(LinkList)malloc(sizeof(emptyNode); /生成新节点(头结点)if(!L) return ERROR; /申请内存失败 s=(LinkList)malloc(sizeof(emptyNode);s->areaSize=900;s->aStartAddr=0;L->next=s; /头节点的指针域指向第一个结点 s->next=NULL;return OK;/InitListStatus ClearList(LinkList &L) /2AAA/将链表L重置为空表LinkList p,r;p=L->next; r=p->next;while(p!=NULL)free(p);if(r=NULL)p=NULL;elsep=r; r=p->next;L->next=NULL;return OK;/ClearList /AAA/*根据始址进行插入 Status ListInsert(LinkList &L,LinkList s1)LinkList r=L,p=L->next,s;/指针 s=(LinkList)malloc(sizeof(emptyNode);s->areaSize=s1->areaSize;s->aStartAddr=s1->aStartAddr;if(p=NULL)L->next=s;s->next=NULL;elsewhile(p!=NULL) if(s1->aStartAddr < p->aStartAddr) s->next=r->next; r->next=s; break; r=p; p=p->next; /后移 if(p=NULL) r->next=s; s->next=NULL; return OK;/ListInsert2void DeleteElem(LinkList &L,int aStartAddr)/*删除线性表中始址值为aStartAddr的结点LinkList p=L,q;while(p->next!=NULL)q=p->next;if(q->aStartAddr=aStartAddr)p->next=q->next;free(q);elsep=p->next;/DeleteElem/void PrintList(LinkList L)/AAA/*输出各结点的值 printf("n空闲分区情况: 始址t 大小n");LinkList p=L->next;while(p!=NULL) printf(" %d Kt%d KBn",p->aStartAddr,p->areaSize);p=p->next;printf("n");/PrintList void creatP(struct PCB *p) /AAA/初始化进程int size;srand(time(NULL); size=rand()%7+1; size*=10;p->pNo=ppNo+;p->pSize=size;p->pOccupy=0;p->pStartAddr=0;p->pState=0;int search(LinkList &L,int pSize) /检索分区表 ,返回合适分区的首址 LinkList p=L->next;while(p!=NULL)if(p->areaSize>=pSize)return p->aStartAddr;p=p->next;return -1;/没有足够大的 int add(LinkList &L) /返回空闲分区总和 LinkList p=L->next;int sum=0; while(p!=NULL)sum+=p->areaSize;p=p->next;return sum;void pListPrint(struct PCB *pList)/AAA/输出内存中空间占用情况 printf("n进程分配情况: 进程t 始址t占用n");for(int i=0;i<pLength;i+) printf(" P%dt %d Kt%d KBn", pListi.pNo,pListi.pStartAddr,pListi.pOccupy);void distribute(LinkList &L,struct PCB *process)LinkList p=L->next;while(p!=NULL)if(p->areaSize>=process->pSize) break; p=p->next;printf("%d KB < %d KB",process->pSize,p->areaSize);if(p->areaSize-process->pSize<=SIZE)/不用分割全部分配 （直接删除此空闲分区结点）process->pStartAddr=p->aStartAddr; /进程始址变化 process->pState=1; /进程状态 process->pOccupy=p->areaSize; /进程实际占用内存 为改空闲分区的大小 pListpLength+= *process; /把进程加入进程列表 printf(" 且 %d KB - %d KB = %d KB < %d KB 则 整区分配n", p->areaSize,process->pSize,p->areaSize-process->pSize,SIZE);pSort(pList); printf("n分配后>>>>n");pListPrint(pList);/输出内存中空间占用情况 DeleteElem(L,p->aStartAddr);else/分割分配 process->pStartAddr=p->aStartAddr; /进程始址变化 process->pState=1; /进程状态 process->pOccupy=process->pSize; /进程实际占用内存 为该进程的大小 pListpLength+= *process; /把进程加入进程列表 printf(" 且 %d KB - %d KB = %d KB > %d KB 则 划分分配n", p->areaSize,process->pSize,p->areaSize-process->pSize,SIZE);pSort(pList); /进程排序 printf("n分配后>>>>n");pListPrint(pList);/输出内存中空间占用情况 /compact(L,pList);p->aStartAddr+=process->pSize; /空闲分区始址变化 p->areaSize-=process->pOccupy; /空闲分区大小 变化 int main()/0、创建一个进程，参数随机数方式产生 struct PCB p; int i,num,dele,k,stAddr,flag; LinkList s,L; printf("*可重定位分区分配*"); if(!InitList(L) /初始化空闲分区表 printf("创建表失败n"); while(1) srand(time(0); flag=rand()%100+1; if(flag%2=0) creatP(&p);/初始化进程 printf("_"); printf("待装入作业:%d Size = %d KBn",p.pNo,p.pSize); /1、请求分配 size /2、检索空闲分区表(首次适应FF) PrintList(L); stAddr=search(L,p.pSize);/得到足够大的分区的始址 ，没有则返回-1 if(stAddr=-1)/没有足够大的分区 if(add(L)>=p.pSize)/空闲区总和足够大 printf("没有足够大的空闲分区但空闲总和足够大n"); /紧凑 compact(L,pList); /按动态分区方式分配 distribute(L,&p); /compact(L,pList); /紧凑 else /空闲区总和不足 printf("分配失败nn"); else/有足够大的 distribute(L,&p); PrintList(L); /compact(L,pList); /紧凑 else/回收 if(pLength>0) recycle(L,pList); /compact(L,pList); /紧凑 else printf("无可回收内存！ "); system("pause"); /while return 0;4. 结果及其相关分析图4.1分析：作业1大小为20KB。找到足够大空闲分区，进行划分分配。图4.2分析：作业2大小为70KB。找到足够大空闲分区，进行划分分配。图4.3分析：先回收进程1大小为20KB，删除进程，并把释放的空闲分区插入空闲分区表；再回收进程2大小为70KB，删除进程，并把释放的空闲分区插入空闲分区表；图4.4分析：程序运行一段时间后的进程分配情况和空闲分区情况。图4.5分析：程序运行一段时间后的进程分配情况和空闲分区情况。图4.6分析：内存中已没有进程，所以不能进行回收。图4.7分析：没有足够大的空闲分区且所有分区之和也不满足要求，分配失败。图4.8图4.9分析：进行紧凑，图4.8状态装换为图4.9状态。五 课程设计小结这次课程设计让我受益匪浅。通过这次课程设计，我不但深刻理解了可重定位分区分配算法；更理解了存储器管理的目的：提高存储器的利用率，提高系统性能。在作课程设计过程中我还体会到，连续分配存储管理的弊端：连续分配方式会形成许多“碎片”，虽然可通过“紧凑”方式将许多碎片拼接成可用的大块空间，但须为之付出很大开销。