实验二 主存储器空间的分配和回收

实验二 主存储器空间的分配和回收

1、 实验内容

主存储器空间的分配和回收。

2、 实验目的

计算机系统不仅要有足够容量、存储速度高、稳定可靠的主存储器，而且要能合理的分配和使用者且存储空间。主存的分配和回收的实现是与主存储器的管理方式有关的。本实验有助于了解在不同的存储管理方式下，应怎样实现主存空间的分配和回收。

3、 实验题目

在可变分区管理方式下，采用最先适应算法实现主存空间的分配和回收。

4、 数据结构

struct Block //空闲链结构体

{

string name; //作业名

int address; //分区首地址

int size; //分区大小

int state; //分区转态

struct Block *next; //前向指针

struct Block *front; //后向指针

};

——构造一个空闲链

struct Used //已分配分区结构体

{

Block *usedArea;

Used *next;

};

——分配分区结构体

void Allocate(string reqName,int reqSize) //分配函数

{

Block *p=freeHead->front ;

Used *r1,*r2;

while(p!=NULL)

{

if(reqSizesize) //如果请求的分区的大小小于一个空闲分区的大小

{

Used *temp=new Used;

temp->usedArea =p;

Block *q=new Block;

*q=*p;

temp->usedArea ->name =reqName;

temp->usedArea ->size =reqSize;

temp->usedArea ->front =q;

temp->usedArea ->state =1;

q->size =q->size -reqSize;

q->address =q->address + reqSize;

q ->next->front=q;

if(q ->front!=NULL)

q ->front->next=q;

r1=usedHead;

r2=usedHead->next;

while(r2!=NULL&&r2->usedArea->addressusedArea->address)

{r1=r2;r2=r2->next;}

r1->next=temp;

temp->next=r2;

break;

}

else if(reqSize==p->size)//如果请求的分区的大小等于一个空闲分区的大小

{

Used *temp=new Used;

temp->usedArea =p;

temp->usedArea ->name =reqName;

temp->usedArea ->state =1;

p->next->front =p->front ;

if(p->front!=NULL)

p->front ->next =p->next ;

r1=usedHead;

r2=usedHead->next;

while(r2!=NULL&&r2->usedArea->addressusedArea->address)

{r1=r2;r2=r2->next;}

r1->next=temp;

temp->next=r2;

break;

}

p=p->front;

}

——构建一个链表，实现内存分配。

5、 源程序

#include

#include

using namespace std;

struct Block //空闲链结构体

{

string name; //作业名

int address; int size; int state; struct Block *next; struct Block *front; };

struct Used {

Block *usedArea; Used *next;

//分区首地址

//分区大小

//分区转态

//前向指针

//后向指针

//已分配分区结构体

};

Block *freeHead; // 带表头附加节点的空闲链头指针

Used *usedHead; //带表头附加结点的已分配分区头指针

bool InitValue() //初始化函数

{

cout<<\"本程序设立的操作功能：1-申请资源 2-释放资源 3-打印信息\"<freeHead=new Block;

freeHead->size=0;

freeHead->next=NULL;

freeHead->state=1;

usedHead=new Used;

Block *p=new Block;

p->address=0;

usedHead->usedArea=p;

usedHead->next=NULL;

Block *temp=new Block;

cout<<\"请先输入主存大小(k)：\"<cin>>temp->size;

temp->address=0;

temp->state =0;

temp->next=freeHead;

temp->front=NULL;

freeHead->front=temp;

return true;

}

void Display(Block *p,Used *q) //打印信息的函数

{

cout<<\"已分配分区信息(作业,始址,大小):\"<while(q!=NULL)

{

cout<usedArea->name<<','<usedArea->address<<','<usedArea->size<q=q->next;

}

cout<<\"空闲链分区信息(始址,大小)：\"<while(p!=NULL)

{

cout<address<<',';

cout<size<p=p->front;

}

}

void Allocate(string reqName,int reqSize) //分配函数

{

Block *p=freeHead->front ;

Used *r1,*r2;

while(p!=NULL)

{

if(reqSizesize) //如果请求的分区的大小小于一个空闲分区的大小

{

Used *temp=new Used;

temp->usedArea =p;

Block *q=new Block;

*q=*p;

temp->usedArea ->name =reqName;

temp->usedArea ->size =reqSize;

temp->usedArea ->front =q;

temp->usedArea ->state =1;

q->size =q->size -reqSize;

q->address =q->address + reqSize;

q ->next->front=q;

if(q ->front!=NULL)

q ->front->next=q;

r1=usedHead;

r2=usedHead->next;

while(r2!=NULL&&r2->usedArea->addressusedArea->address)

{r1=r2;r2=r2->next;}

r1->next=temp;

temp->next=r2;

break;

}

else if(reqSize==p->size)//如果请求的分区的大小等于一个空闲分区的大小

{

Used *temp=new Used;

temp->usedArea =p;

temp->usedArea ->name =reqName;

temp->usedArea ->state =1;

p->next->front =p->front ;

if(p->front!=NULL)

p->front ->next =p->next ;

r1=usedHead;

r2=usedHead->next;

while(r2!=NULL&&r2->usedArea->addressusedArea->address)

{r1=r2;r2=r2->next;}

r1->next=temp;

temp->next=r2;

break;

}

p=p->front;

}

if(p==NULL)

cout<<\"资源不足 请等待\"<}

void Recycle(string freeName) //回收分区的函数

{

Used *p=usedHead->next,*r=usedHead;

Block *q;

while(p!=NULL)

{

if(p->usedArea->name==freeName)//找到同名的作业后，再分四种情况讨论

{

q=p->usedArea;

int flag1=1,flag2=1;

Block *p1=freeHead->front;

Block *pfront,*pnext;

while(p1->addressaddress)

{

if(p1->address+p1->size==q->address){flag1=0;pnext=p1;}

p1=p1->front;

}

if(q->address+q->size==p1->address)

{flag2=0;pfront=p1;}

if(flag1==0)

{

if(flag2==0)

{

pnext->front =pfront->front;

pnext->size=pnext->size + q->size + pfront->size;

if(pfront->front!=NULL)

pfront ->front ->next=pnext;

r->next =p->next;

}

else {pnext ->size +=q->size;r->next =p->next ; }

}

else

{

if(flag2 ==0)

{

pfront ->address -=q->size;

pfront ->size +=q->size ;

r->next =p->next ;

}

else

{

Block *temp=freeHead;

while(temp->address <=q->address )temp=temp->front;

q->front =temp;

q->next =temp->next ;

q->next->front =q;

temp->next =q;

q->state =0;

r->next =p->next ;

}

}

break;

}

r=p;

p=p->next ;

}

}

int main()

{

InitValue();

int operate;//操作符1-申请资源 2-释放资源 3-打印信息

string name;

int size;

while(1)

{

cout<<\"请选择操作功能\"<cin>>operate;

if(operate==1)

{ cout<<\"请输入作业名(字符串) 空间大小(正整数)\"<cin>>name>>size;

Allocate(name,size);

}

else if(operate==2)

{

cout<<\"请输入作业名(字符串)\"<cin>>name;

Recycle(name);

}

else if(operate==3) Display(freeHead->front,usedHead->next );

}

return 0;

}

5、 运行结果