分区存储管理模拟实验报告

分区存储管理模拟实验报告

1．实验目的

了解动态分区存储管理方式中的数据结构和分配算法，加深对动态分区存储管理方式及其实现技术的理解。

2. 实验内容

用C 语言或Pascal 语言分别实现采用首次适应算法和最佳适应算法的动态分区分配过

程Allocate()和回收过程Free()。其中，空闲分区采用空闲分区链来组织，内存分配时，优先使用空闲区低地址部分的空间。

假设初始状态，可用内存空间为640KB ，作业请求序列如下（也可以编程从键盘输入，

R 表示请求，F 表示释放）：

✧ 作业1请求130 KB。 ✧ 作业2请求60 KB。 ✧ 作业3请求100 KB。 ✧ 作业2释放60 KB。 ✧ 作业4请求200 KB。 ✧ 作业3释放100 KB。 ✧ 作业1释放130 KB。 ✧ 作业5请求140 KB。 ✧ 作业6请求60 KB。 ✧ 作业7请求50 KB。 ✧ 作业6释放60 KB。

要求每次分配和回收后显示出空闲区链的情况。

如果不能为作业的请求进行内存分配，给出相应的提示信息。

3．实验分析和思考

采用首次适应算法和最佳适应算法，对内存的分配和回收速度有什么影响？ 如何解决碎片片问题？

详细设计

首次适应算法：当要分配内存空间时，就查表，在各空闲区中查找满足大小要求的可用块。只要找到第一个足以满足要球的空闲块就停止查找，并把它分配出去；如果该空闲空间与所需空间大小一样，则从空闲表中取消该项；如果还有剩余，则余下的部分仍留在空闲表中，但应修改分区大小和分区始址。

最佳适应算法：当要分配内存空间时，就查找空闲表中满足要求的空闲块，并使得剩余块是最小的。然后把它分配出去，若大小恰好合适，则直按分配；若有剩余块，则仍保留该余下的空闲分区，并修改分区大小的起始地址。

内存回收：将释放作业所在内存块的状态改为空闲状态，删除其作业名，设置为空。并判断该空闲块是否与其他空闲块相连，若释放的内存空间与空闲块相连时，则合并为同一个空闲块，同时修改分区大小及起始地址。

typedef struct freearea{}ElemType;

定义一个空闲区说明表结构，每申请一个作业，改作业便具有此结构体 typedef struct DuLNode{}DuLNode,*DuLinkList; 定义一个双向链表 Status Initblock(){}

开创带头结点的内存空间链表, 通过双向链表把申请的作业链接起来，作业的插入和删除，和链表中节点的插入和删除类似。

双向链表如图1所示

Status First_fit(int ID,int request){}

传入作业名及申请量采用首次适应算法实现动态内存分区分配的模拟，初始态640KB ，只是一个虚态，每申请成功一个作业，便相应的640KB 做相应的减少，同过双向链表模拟主存的分配情况。

内存分配流程如图2所示

Status free(int ID)

传过来需要回收的分区号实现分区的回收，对不同情况采取不同的处理

void show()显示当前主存的分配情况

源程序

//---------------------------------------------------------------- //--------- 动态分区分配方式的模拟 --------- //----------------------------------------------------------------

#include #include

#define Free 0 //空闲状态 #define Busy 1 //已用状态 #define OK 1 //完成 #define ERROR 0 //出错

#define MAX_length 640 //最大内存空间为640KB typedef int Status;

typedef struct freearea//定义一个空闲区说明表结构 {

//---------- 线性表的双向链表存储结构 ------------ typedef struct DuLNode //double linked list {

DuLinkList block_first; //头结点 DuLinkList block_last; //尾结点

Status alloc(int);//内存分配 Status free(int); //内存回收

Status First_fit(int,int);//首次适应算法 Status Best_fit(int,int); //最佳适应算法 void show();//查看分配

Status Initblock();//开创空间表

Status Initblock()//开创带头结点的内存空间链表

ElemType data;

struct DuLNode *prior; //前趋指针 struct DuLNode *next; //后继指针 int ID; //分区号 long size; //分区大小 long address; //分区地址 int state; //状态

}ElemType;

}DuLNode,*DuLinkList;

}

//----------------------- 分 配 主 存 ------------------------- Status alloc(int ch) { }

//------------------ 首次适应算法 ----------------------- Status First_fit(int ID,int request)//传入作业名及申请量 {

if(ch==2) //选择最佳适应算法 { }

else //默认首次适应算法 { }

if(First_fit(ID,request)==OK) cout

if(Best_fit(ID,request)==OK) cout

cout>ID;

cout>request;

if(request

cout

block_first=(DuLinkList)malloc(sizeof(DuLNode)); block_last=(DuLinkList)malloc(sizeof(DuLNode)); block_first->prior=NULL; block_first->next=block_last; block_last->prior=block_first; block_last->next=NULL; block_last->data.address=0; block_last->data.size=MAX_length; block_last->data.ID=0; block_last->data.state=Free; return OK;

}

//-------------------- 最佳适应算法 ------------------------ Status Best_fit(int ID,int request) {

int ch; //记录最小剩余空间

DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode)); temp->data.ID=ID; temp->data.size=request; temp->data.state=Busy; DuLNode *p=block_first->next; DuLNode *q=NULL; //记录最佳插入位置 while(p) //初始化最小空间和最佳位置 {

DuLNode *p=block_first->next; while(p) { }

return ERROR;

if(p->data.state==Free && p->data.size==request) {//有大小恰好合适的空闲块 }

if(p->data.state==Free && p->data.size>request) {//有空闲块能满足需求且有剩余" }

p=p->next;

temp->prior=p->prior; temp->next=p;

temp->data.address=p->data.address; p->prior->next=temp; p->prior=temp;

p->data.address=temp->data.address+temp->data.size; p->data.size-=request; return OK; break;

p->data.state=Busy; p->data.ID=ID; return OK; break;

DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode)); temp->data.ID=ID; temp->data.size=request; temp->data.state=Busy;

}

//----------------------- 主 存 回 收 -------------------- Status free(int ID)

} while(p) { }

if(q==NULL) return ERROR;//没有找到空闲块 else

{//找到了最佳位置并实现分配 }

temp->prior=q->prior; temp->next=q;

temp->data.address=q->data.address; q->prior->next=temp; q->prior=temp;

q->data.address+=request; q->data.size=ch; return OK;

if(p->data.state==Free && p->data.size==request) {//空闲块大小恰好合适 }

if(p->data.state==Free && p->data.size>request) {//空闲块大于分配需求 }

p=p->next;

if(p->data.size-request

ch=p->data.size-request;//更新剩余最小值 q=p;//更新最佳位置指向 p->data.ID=ID; p->data.state=Busy; return OK; break;

{ }

p=p->next;

q=p;

ch=p->data.size-request; break;

(p->data.size>request || p->data.size==request) )

}

//--------------- 显示主存分配情况 ------------------ void show() {

coutnext; while(p) {

cout

if(p->data.ID==Free) coutdata.ID

coutdata.addressdata.size

if(p->data.state==Free) cout

return OK;

if(p->data.ID==ID) { }

p=p->next;

p->data.state=Free; p->data.ID=Free;

if(p->prior->data.state==Free)//与前面的空闲块相连 { }

if(p->next->data.state==Free)//与后面的空闲块相连 { }

break;

p->data.size+=p->next->data.size; p->next->next->prior=p; p->next=p->next->next;

p->prior->data.size+=p->data.size; p->prior->next=p->next; p->next->prior=p->prior;

}

//----------------------- 主 函 数--------------------------- void main() {

int ch;//算法选择标记

cout>ch;

Initblock(); //开创空间表 int choice; //操作选择标记 while(1) { }

p=p->next;

cout>choice; }

}

if(choice==1) alloc(ch); // 分配内存 else if(choice==2) // 内存回收 { }

else if(choice==3) show();//显示主存 else if(choice==0) break; //退出 else //输入操作有误 { }

cout

cout>ID; free(ID);

截图

10