基于可重定位分区分配算法的内存管理的设计实现分析

1、-. z.组号成绩计算机操作系统课程设计报告题目基于可重定位分区分配算法的存管理的设计与实现专业：计算机科学与技术班级：*+：指导教师：2016年12月 23 日设计目的掌握存的连续分配方式的各种分配算法设计容基于可重定位分区分配算法的存管理的设计与实现。本系统模拟操作系统存分配算法的实现，实现可重定位分区分配算法，采用PCB定义构造体来表示一个进程，定义了进程的名称和大小，进程存起始地址和进程状态。存分区表采用空闲分区表的形式来模拟实现。要求定义与算法相关的数据构造，如PCB、空闲分区；在使用可重定位分区分配算法时必须实现紧凑。设计原理可重定位分区分配算法与动态分区分配算法根本上一样，差异仅

2、在于：在这种分配算法中，增加了紧凑功能。通常，该算法不能找到一个足够大的空闲分区以满足用户需求时，如果所有的小的空闲分区的容量总和大于用户的要求，这是便须对存进展紧凑，将经过紧凑后所得到的大空闲分区分配给用户。如果所有的小空闲分区的容量总和仍小于用户的要求，则返回分配失败信息详细设计及编码模块分析分配模块这里采用首次适应(FF)算法。设用户请求的分区大小为u.size,存中空闲分区大小为m.size,规定的不再切割的剩余空间大小为size。空闲分区按地址递增的顺序排列；在分配存时，从空闲分区表第一个表目开场顺序查找，如果m.sizeu.size且size，说明多余局部太小，不再分割，将整个分区

3、分配给请求者；如果m.sizeu.size且m.size-u.sizesize，就从该空闲分区中按请求的大小划分出一块存空间分配给用户，剩余的局部仍留在空闲分区表中；如果m.sizeu.size的空闲区？按动态分区方式分配空闲分区总和u.size进展紧凑修改有关数据构造分配失败返回返回分区号及首址否否是是代码实现#include#include#include#include#define TURE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2#define SIZE 15

4、 /进程表/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 *ne*t;empt

5、yNode,*LinkList;int ListDelete(struct PCB *pList,int i);/AAA/删除下标为i的进程void pSort(struct PCB *pList); /AAA/存中的进程按始址递增排序void pact(LinkList &L,struct PCB *pList);/AAA/紧凑 ,存中进程移动，修改良程数据构造；空闲分区合并，修改空闲分区表数据构造void amalgamate(LinkList &L); /AAA/回收后进展合并空闲分区void recycle(LinkList &L,struct PCB *pList); /AAA/回收

6、，从进程表中删除进程，把释放出的空间插入到空闲分区链表中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 cr

7、eatP(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

8、=pListi+1;pLength-;/ListDeletevoid pSort(struct PCB *pList) /AAA/存中的进程按始址递增排序int i,j;struct PCB temp;for(i=0;ipLength-1;i+)for(j=0;jpListj+1.pStartAddr)temp=pListj;pListj=pListj+1;pListj+1=temp;/AAA/紧凑 ,存中进程移动，修改良程数据构造；空闲分区合并，修改空闲分区表数据构造void pact(LinkList &L,struct PCB *pList) printf(进展紧凑n); /1、进程移动

9、,修改良程数据构造int i;pList0.pStartAddr=0; /第一个进程移到最上面for(i=0;ine*t,s;int sumEmpty=0;while(p!=NULL)/求空闲区总和sumEmpty+=p-areaSize;p=p-ne*t;ClearList(L); /清空空闲分区表s=(LinkList)malloc(sizeof(emptyNode);s-aStartAddr=pListpLength-1.pStartAddr+pListpLength-1.pOccupy; s-areaSize=sumEmpty;ListInsert(L,s); printf(n紧凑后的

10、n); pListPrint(pList);PrintList(L);void amalgamate(LinkList &L)/AAA/回收后进展合并空闲分区LinkList p=L-ne*t,q=p-ne*t;while(q!=NULL)if(p-aStartAddr+p-areaSize=q-aStartAddr)p-areaSize+=q-areaSize;DeleteElem(L,q-aStartAddr);/删除被合并的结点q=p-ne*t; elsep=q;q=q-ne*t;/AAA/回收，从进程表中删除进程，把释放出的空间插入到空闲分区链表中void recycle(LinkLi

11、st &L,struct PCB *pList) int inde*,delPNo,delPSize,delPOccupy,delPStartAddr; LinkList s; srand(time(0); inde*=rand()%pLength; delPNo=pListinde*.pNo; delPSize=pListinde*.pSize; delPOccupy=pListinde*.pOccupy; delPStartAddr=pListinde*.pStartAddr; printf(_); printf(回收存进程 P%d: 始址：%d K 占用：%d KBn,delPNo,de

12、lPStartAddr,delPOccupy); printf(n回收后n); ListDelete(pList,inde*); /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/构造一个新的有头节点的空链表LL

13、inkList s;L=(LinkList)malloc(sizeof(emptyNode); /生成新节点(头结点)if(!L) return ERROR; /申请存失败s=(LinkList)malloc(sizeof(emptyNode);s-areaSize=900;s-aStartAddr=0;L-ne*t=s; /头节点的指针域指向第一个结点s-ne*t=NULL;return OK;/InitListStatus ClearList(LinkList &L) /2AAA/将链表L重置为空表LinkList p,r;p=L-ne*t; r=p-ne*t;while(p!=NULL)

14、free(p);if(r=NULL)p=NULL;elsep=r; r=p-ne*t;L-ne*t=NULL;return OK;/ClearList /AAA/*根据始址进展插入Status ListInsert(LinkList &L,LinkList s1)LinkList r=L,p=L-ne*t,s;/指针s=(LinkList)malloc(sizeof(emptyNode);s-areaSize=s1-areaSize;s-aStartAddr=s1-aStartAddr;if(p=NULL)L-ne*t=s;s-ne*t=NULL;elsewhile(p!=NULL) if(s

15、1-aStartAddr aStartAddr) s-ne*t=r-ne*t; r-ne*t=s; break; r=p; p=p-ne*t; /后移 if(p=NULL) r-ne*t=s; s-ne*t=NULL; return OK;/ListInsert2void DeleteElem(LinkList &L,int aStartAddr)/*删除线性表中始址值为aStartAddr的结点LinkList p=L,q;while(p-ne*t!=NULL)q=p-ne*t;if(q-aStartAddr=aStartAddr)p-ne*t=q-ne*t;free(q);elsep=p-

16、ne*t;/DeleteElem/void PrintList(LinkList L)/AAA/*输出各结点的值 printf(n空闲分区情况: 始址t 大小n);LinkList p=L-ne*t;while(p!=NULL) printf( %d Kt%d KBn,p-aStartAddr,p-areaSize);p=p-ne*t;printf(n);/PrintListvoid creatP(struct PCB *p) /AAA/初始化进程int size;srand(time(NULL); size=rand()%7+1; size*=10;p-pNo=ppNo+;p-pSize=s

17、ize;p-pOccupy=0;p-pStartAddr=0;p-pState=0;int search(LinkList &L,int pSize) /检索分区表 ,返回适宜分区的首址LinkList p=L-ne*t;while(p!=NULL)if(p-areaSize=pSize)return p-aStartAddr;p=p-ne*t;return -1;/没有足够大的int add(LinkList &L) /返回空闲分区总和LinkList p=L-ne*t;int sum=0; while(p!=NULL)sum+=p-areaSize;p=p-ne*t;return sum;

18、void pListPrint(struct PCB *pList)/AAA/输出存中空间占用情况printf(n进程分配情况: 进程t 始址t占用n);for(int i=0;ine*t;while(p!=NULL)if(p-areaSize=process-pSize) break; p=p-ne*t;printf(%d KB pSize,p-areaSize);if(p-areaSize-process-pSizepStartAddr=p-aStartAddr; /进程始址变化process-pState=1; /进程状态process-pOccupy=p-areaSize; /进程实际

19、占用存为改空闲分区的大小pListpLength+= *process; /把进程参加进程列表printf( 且 %d KB - %d KB = %d KB 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-pOc

20、cupy=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);/输出存中空间占用情况/pact(L,pList);p-aStartAddr+=process-pSize; /空闲分区始址变化p-areaSize-=p

21、rocess-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); /紧凑 pact(L,pList)