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

组号 成绩

计算机操作系统
课程设计报告

题目 基于可重定位分区别配算法内存管理设计与实现

专业： 计算机科学与技术
班级：
学号+姓名：
指引教师：

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<u.size则查找下一种空闲分区表项，直到找到一种足够大空闲分区；如果没有找到一种足够大内存空闲分区，但所有小空闲分区容量总和不不大于顾客规定，就进行紧凑，将紧凑后得到大空闲分区按上述方式分派给顾客；但如果所有小空闲分区容量总和仍不能满足顾客需要，则分派失败。
（2） 内存回收模块
进行内存回收操作时，先随机产生一种要回收进程进程号，把该进程从进程表中中删除，它所释放空闲内存空间插入到空闲分区表；如果回收区与插入点前一种空闲分区相邻，应将回收区与插入点前一分区合并，修改前一种分区大小；如果回收区与插入点后一种空闲分区相邻，应将回收区与插入点后一分区合并，回收区首址作为新空闲分区首址，大小为两者之和；如果回收区同步与插入点前、后空闲分区相邻，应将三个分区合并，使用前一种分区首址，取消后一种分区，大小为三者之和。
（3） 紧凑模块
将内存中所有作业进行移动，使她们全都相邻接，把本来分散各种空闲小分区拼接成一种大分区。

2. 流程图

否
否

是 是

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 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-1;i++){
pList[i]=pList[i+1];
}
pLength--;
}//ListDelete

void 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(pList[j].pStartAddr>pList[j+1].pStartAddr){
temp=pList[j];
pList[j]=pList[j+1];
pList[j+1]=temp;
}
}
}
}
//AAA/紧凑 ,内存中进程移动，修改进程数据构造；空闲分区合并，修改空闲分区表数据构造
void compact(LinkList &L,struct PCB *pList){

printf("进行紧凑\n")；
//1、进程移动,修改进程数据构造
int i;
pList[0].pStartAddr=0；//第一种进程移到最上面
for(i=0;i<pLength-1;i++){
pList[i+1].pStartAddr=pList[i].pStartAddr+pList[i].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=pList[pLength-1].pStartAddr+pList[pLength-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；
}else{
p=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=pList[index].pNo;
delPSize=pList[index].pSize;
delPOccupy=pList[index].pOccupy;
delPStartAddr=pList[index].pStartAddr;
printf("________________________________________________________________________________");
printf("回收内存 进程 P%d： 始址：%d K 占用：%d KB\n",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/构造一种新有头节点空链表L
{
LinkList 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;
}//InitList

Status ClearList(LinkList &L) //2AAA/将链表L重置为空表
{
LinkList p,r;
p=L->next；r=p->next;
while(p!=NULL)
{
free(p);
if(r==NULL){
p=NULL;
}else{
p=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;
}else{
while(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;
}//ListInsert2

void 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);
}
else
p=p->next;
}
}//DeleteElem

////////////////////////////////////////////////
void PrintList(LinkList L)//AAA/*****输出各结点值
{
printf("\n空闲分区状况： 始址\t 大小\n");
LinkList p=L->next;
while(p!=NULL)
{
printf(" %d K\t%d KB\n",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%d\t %d K\t%d KB\n",
pList[i].pNo,pList[i].pStartAddr,pList[i].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；//进程实际占用内存 为改空闲分区大小

pList[pLength++]= *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；//进程实际占用内存 为该进程大小

pList[pLength++]= *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 KB\n",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("分派失败\n\n")；
}

}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状态。

五． 课程设计小结
这次课程设计让我受益匪浅。通过这次课程设计，我不但深刻理解了可重定位分区别配算法；更理解了存储器管理目：提高存储器运用率，提高系统性能。在作课程设计过程中我还体会到，持续分派存储管理弊端：持续分派方式会形成许多“碎片”，虽然可通过“紧凑”方式将许多碎片拼接成可用大块空间，但须为之付出很大开销。