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

1、分区存储管理模拟实验报告1实验目的了解动态分区存储管理方式中的数据结构和分配算法，加深对动态分区存储管理方式及其实现技术的理解。2. 实验内容§ 用C语言或Pascal语言分别实现采用首次适应算法和最佳适应算法的动态分区分配过程Allocate()和回收过程Free()。其中，空闲分区采用空闲分区链来组织，内存分配时，优先使用空闲区低地址部分的空间。§ 假设初始状态，可用内存空间为640KB，作业请求序列如下（也可以编程从键盘输入，R表示请求，F表示释放）：² 作业1请求130 KB。² 作业2请求60 KB。² 作业3请求100 KB。

2、78; 作业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实验分析和思考§ 采用首次适应算法和最佳适应算法，对内存的分配和回收速度有什么影响？§ 如何解决碎片片问题？详细设计首次适应算法：当要分配内存空间时，就查表，在各空

3、闲区中查找满足大小要求的可用块。只要找到第一个足以满足要球的空闲块就停止查找，并把它分配出去；如果该空闲空间与所需空间大小一样，则从空闲表中取消该项；如果还有剩余，则余下的部分仍留在空闲表中，但应修改分区大小和分区始址。最佳适应算法：当要分配内存空间时，就查找空闲表中满足要求的空闲块，并使得剩余块是最小的。然后把它分配出去，若大小恰好合适，则直按分配；若有剩余块，则仍保留该余下的空闲分区，并修改分区大小的起始地址。内存回收：将释放作业所在内存块的状态改为空闲状态，删除其作业名，设置为空。并判断该空闲块是否与其他空闲块相连，若释放的内存空间与空闲块相连时，则合并为同一个空闲块，同时修改分区大小及

4、起始地址。typedef struct freeareaElemType;定义一个空闲区说明表结构，每申请一个作业，改作业便具有此结构体typedef struct DuLNodeDuLNode,*DuLinkList;定义一个双向链表Status Initblock()开创带头结点的内存空间链表,通过双向链表把申请的作业链接起来，作业的插入和删除，和链表中节点的插入和删除类似。双向链表如图1所示Status First_fit(int ID,int request)传入作业名及申请量采用首次适应算法实现动态内存分区分配的模拟，初始态640KB，只是一个虚态，每申请成功一个作业，便相应的640

5、KB做相应的减少，同过双向链表模拟主存的分配情况。内存分配流程如图2所示Status free(int ID)传过来需要回收的分区号实现分区的回收，对不同情况采取不同的处理10void show()显示当前主存的分配情况源程序/-/- 动态分区分配方式的模拟 -/- #include<iostream.h>#include<stdlib.h> #define Free 0 /空闲状态#define Busy 1 /已用状态#define OK 1 /完成#define ERROR 0 /出错#define MAX_length 640 /最大内存空间为640KBtype

6、def int Status; typedef struct freearea/定义一个空闲区说明表结构int ID; /分区号long size; /分区大小long address; /分区地址int state; /状态ElemType; /- 线性表的双向链表存储结构 -typedef struct DuLNode /double linked listElemType data; struct DuLNode *prior; /前趋指针struct DuLNode *next; /后继指针DuLNode,*DuLinkList; DuLinkList block_first; /头结

7、点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()/开创带头结点的内存空间链表block_first=(DuLinkList)malloc(sizeof(DuLNode);block_last=(DuLinkList)malloc(sizeof(

8、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 alloc(int ch)int ID,re

9、quest;cout<<"请输入作业(分区号)：" cin>>ID;cout<<"请输入需要分配的主存大小(单位:KB)：" cin>>request;if(request<0 |request=0) cout<<"分配大小不合适，请重试！"<<endl;return ERROR; if(ch=2) /选择最佳适应算法if(Best_fit(ID,request)=OK) cout<<"分配成功！"<<endl;e

10、lse cout<<"内存不足，分配失败！"<<endl;return OK;else /默认首次适应算法if(First_fit(ID,request)=OK) cout<<"分配成功！"<<endl;else cout<<"内存不足，分配失败！"<<endl;return OK;/- 首次适应算法 -Status First_fit(int ID,int request)/传入作业名及申请量/为申请作业开辟新空间且初始化DuLinkList temp=(DuL

11、inkList)malloc(sizeof(DuLNode); temp->data.ID=ID; temp->data.size=request;temp->data.state=Busy; DuLNode *p=block_first->next;while(p)if(p->data.state=Free && p->data.size=request)/有大小恰好合适的空闲块p->data.state=Busy;p->data.ID=ID;return OK;break;if(p->data.state=Free &a

12、mp;& p->data.size>request)/有空闲块能满足需求且有剩余"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=p->next;r

13、eturn ERROR;/- 最佳适应算法 -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) /初始化最小空间和最佳位置if(p->data.state=

14、Free &&(p->data.size>request | p->data.size=request) )q=p;ch=p->data.size-request;break;p=p->next;while(p)if(p->data.state=Free && p->data.size=request)/空闲块大小恰好合适p->data.ID=ID;p->data.state=Busy;return OK;break;if(p->data.state=Free && p->data

15、.size>request)/空闲块大于分配需求if(p->data.size-request<ch)/剩余空间比初值还小ch=p->data.size-request;/更新剩余最小值q=p;/更新最佳位置指向p=p->next;if(q=NULL) return ERROR;/没有找到空闲块else/找到了最佳位置并实现分配temp->prior=q->prior;temp->next=q;temp->data.address=q->data.address;q->prior->next=temp;q->prio

16、r=temp;q->data.address+=request;q->data.size=ch;return OK; /- 主 存 回 收 -Status free(int ID)DuLNode *p=block_first;while(p)if(p->data.ID=ID)p->data.state=Free;p->data.ID=Free;if(p->prior->data.state=Free)/与前面的空闲块相连p->prior->data.size+=p->data.size;p->prior->next=p-&

17、gt;next;p->next->prior=p->prior;if(p->next->data.state=Free)/与后面的空闲块相连 p->data.size+=p->next->data.size;p->next->next->prior=p;p->next=p->next->next;break;p=p->next;return OK; /- 显示主存分配情况 -void show()cout<<"-n"cout<<"- 主 存 分 配 情

18、 况 -n"cout<<"-n"DuLNode *p=block_first->next;while(p)cout<<"分 区 号："if(p->data.ID=Free) cout<<"Free"<<endl;else cout<<p->data.ID<<endl;cout<<"起始地址："<<p->data.address<<endl;cout<<"

19、分区大小："<<p->data.size<<" KB"<<endl;cout<<"状 态："if(p->data.state=Free) cout<<"空 闲"<<endl;else cout<<"已分配"<<endl;cout<<"-"<<endl;p=p->next; /- 主 函 数-void main()int ch;/算法选择标记cout<<" 动态分区分配方式的模拟 n&qu