操作系统之内存分配与回收

1、操作系统实验内存的分配与回收 实验报告1、 实验题目：内存的分配与回收2、 实验内容：利用可变分区的首次适应算法，模拟内存的分配与回收。3、 实验目的：掌握可变分区首次适应算法的原理以及其编程实现。4、 实验过程：1、基本思想：可变分区分配是根据进程的实际需求，动态地为之分配内存空间。首次适应算法要求空闲空间链以地址递增的次序链接。进行内存分配时，从链表头部开始依次检索，找到第一个不小于请求空间大小的空闲空间进行分配。分配时需考虑碎片问题，若分配会导致碎片产生则将整块分区分配。内存的回收需要考虑四种情况：回收分区前后两个分区都空闲，则需要和前后两个分区合并；（2）回收分区只有前一分区空闲，则与

2、前一分区合并；（3）回收分区只有后一分区空闲，则和后一分区合并；（4）回收分区独立，不考虑合并。2、主要数据结构：struct FreeArea 链结点包含的数据：分区号、大小、起址、标记 int ID;int size;long address;int sign;struct Node 双链表结点结构体：数据区、前向指针、后继指针FreeArea data;struct Node *prior; struct Node *next; *DLinkList;3、输入、输出： 输入： I.内存分配时由键盘输入分区ID和大小； II.内存回收时由键盘输入需要回收的分区ID；输出： 输出内存的分配情

3、况（按照地址从低到高）4、 程序流程图：结束合并后回收合并后回收该分区后一个分区空闲该分区前一个分区空闲合并后回收该分区前后都空闲回收分区独立输入分区号显示分区情况结束开始退出Choice=0Choice=3Choice=2将分区从空闲链移出，并修改相应数据结构整块分配判断是否会有碎片内存不足判断剩余空间是否足够输入分区大小输入分区号输入有误验证该分区是否已经被占用Choice=1Choice>3或choice<0选择操作choice输出可选操作5、 实验结果截屏：6、 源程序代码：#include<iostream>using namespace std;#defin

4、e Free 0 /空闲状态#define Busy 1 /已用状态#define PBusy 2 /碎片已用状态#define FINISH 1 /完成#define FINISH2 1 /完成#define ERROR 0 /出错#define memory 512 /最大内存空间为(单位：KB）#define min 10 /碎片最小值(单位：KB)typedef struct FreeArea/空闲链数据int ID;int size;long address;int sign;typedef struct Node /空闲连结构 FreeArea data;struct Node *

5、prior; struct Node *next; *DLinkList;DLinkList head; /头结点DLinkList tail; /尾结点int Create()/初始化head=(DLinkList)malloc(sizeof(Node);/分配内存tail=(DLinkList)malloc(sizeof(Node);head->prior=NULL;head->next=tail;tail->prior=head;tail->next=NULL;tail->data.address=0;tail->data.size=memory;ta

6、il->data.ID=0;tail->data.sign=Free;return FINISH;int FirstFit(int ID,int request)/首次适应算法DLinkList temp=(DLinkList)malloc(sizeof(Node);/新建作业的结点temp->data.ID=ID;temp->data.size=request;temp->data.sign=Busy;Node *p=head;/插入指针P while(p)if(p->data.sign=Free && p->data.size=re

7、quest)/剩余大小恰好满足p->data.sign=Busy;p->data.ID=ID;return FINISH;break;else if(p->data.sign=Free && p->data.size>request && (p->data.size-request>min)/满足需求且有剩余且不产生碎片temp->prior=p->prior;temp->next=p;temp->data.address=p->data.address;p->prior->ne

8、xt=temp;p->prior=temp;p->data.address=temp->data.address+temp->data.size;p->data.size=p->data.size-request;return FINISH;break;else if(p->data.sign=Free && p->data.size>request && p->data.size-request<=min)/产生碎片时p->data.sign=PBusy;p->data.ID=ID;

9、return FINISH;break;p=p->next;/若前面的分区都已分配，P指针后移return ERROR;int Allocate()/主存分配int ID,request;cout<<"请输入作业所在分区号："cin>>ID;cout<<"请输入分配的主存(单位:KB)："cin>>request;if(request<0 |request=0)cout<<"分配的主存必须是正整数！"<<endl;return ERROR;if(Fir

10、stFit(ID,request)=FINISH)cout<<"分配成功！"<<endl;elsecout<<"内存不足，分配失败！"<<endl;int Recycle(int ID)/回收Node *p=head;while(p)if(p->data.ID=ID)p->data.sign=Free;/p->data.ID=Free;if(p->prior->data.sign=Free)&&(p->next->data.sign=Free)/与前

11、后的空闲块相连p->prior->data.size=p->prior->data.size+p->data.size+p->next->data.size;p->prior->next=p->next->next;if(p->next->next=NULL)/若p->next是最后一个结点p->prior->data.ID=Free;p->next=NULL;elsep->next->next->prior=p->prior;break; if(p->prior

12、->data.sign=Free)/与前面的空闲块相连p->prior->data.size+=p->data.size;p->prior->next=p->next;p->next->prior=p->prior;break;if(p->next->data.sign=Free)/与后面的空闲块相连p->data.size+=p->next->data.size;if(p->next->next=NULL)/若p->next是最后一个结点p->next=NULL;elsep-&g

13、t;next->next->prior=p;p->next=p->next->next;break;break;p=p->next;cout<<"分区："<<ID<<"回收成功"<<endl;return FINISH;void show()/显示cout<<" 主存分配情况 n"Node *p=head->next;while(p)cout<<"分区号："if(p->data.ID=Free)c

14、out<<"Free"<<endl;elsecout<<p->data.ID<<endl;cout<<"起始地址："<<p->data.address;cout<<" 分区大小："<<p->data.size<<" KB"cout<<" 状 态："if(p->data.sign=Free)cout<<"空 闲"<&l

15、t;endl;else if(p->data.sign=PBusy)cout<<"碎片已分配"<<endl;elsecout<<"已分配"<<endl;p=p->next;cout<<endl;void main()Create();int choice;int i;for(i=0;i+) cout<<"请输入操作："cout<<"1.分配内存 2.回收内存 3.显示主存 0.退出"cout<<endl;cin>>choice;