目录

一、实验介绍

         1.实验名称

2.实验目的

3.实验内容

二、分配与回收的概念介绍

 三、代码部分

1.算法简介

2.示例代码

四、结果展示

---

一、实验介绍

1.实验名称

         内存的分配与回收（首次适应FF、最佳适应BF、最坏适应WF）算法模拟实验。

2.实验目的

        通过内存的分配与回收算法的模拟，加深对内存分配三种算法的理解。

3.实验内容

        初始化一内存空间，对内存进行分配、回收及打印。

二、分配与回收的概念介绍

  分配:在操作系统中，我们的可分配内存与不可分配内存通常是交叉存在的，如下图所示

        由于这种分配内存块与未分配内存块交叉存在的现象，我们就涉及到了不同的内存分配算法，该实验中主要涉及到首次适应算法(FF)、最佳适应算法(BF)、最坏适应算法(WF).

FF:在空闲链表中从链首开始顺序查找，直到能找到一个符合要求的空闲块。

BF:就是从链表中找到既满足要求又是空闲内存最少的空闲块，避免"大材小用"。

WF:在空闲块中挑出符合要求的最大的空闲块分配给应用进程。

回收:

回收也可以分为下面4种情况:

 

 三、代码部分

1.算法简介

a.该算法中，由于内存的连续性故内存用顺序表M表示,空闲块用链表表示

内存顺序表:

空闲链表:

b.关于占用内存:首先初始化内存大小，随后插入进程，插入的进程首先搜索空闲链表，得到空闲链表后将空闲链表出队，并在内存M中进行内存占用(内存-1表示空闲，若为其他数则表示对应ID)

c.关于回收:回收先根据id在内存顺序表中找到该回收的目标进程，然后将其内存内容置为-1，随后根据内存信息修改链表。

2.示例代码

#include"stdio.h"
#include"iostream"
#include"cstdio"
#include"iomanip"
#include"malloc.h"
using namespace std;
typedef struct SNode{
	int id;//名称 
	int ad;//地址 
	int data;//大小 
	SNode *front;
	SNode *next;
}Snode;//双链表结构体 
void Insertlist(Snode *&l,int id,int ad,int data)//将进程插入链表 
{
	Snode *s;//指向新节点 
	s=(Snode *)malloc(sizeof(Snode));
	s->ad=ad;
	s->data=data;
	s->id=id;
	s->next=l->next;//新节点的插入 
	if(l->next!=NULL)
		l->next->front=s;
	s->front=l;
	l->next=s;
}
int Changelist(Snode *&l,int data1)//在空闲链表中匹配程序空闲块 并修改链表 
{
	Snode *s;//找到大小满足的空闲块；
	int ad=-1;
	s=l->next;
	while(s!=NULL)
	{
		if(s->data>=data1)
		{	
			ad=s->ad;//将空闲块的首地址记下来 
			if(s->data==data1)//空闲块等于进程大小的情况 
			{
				if(s->next!=NULL)
				{
				s->front->next=s->next;
				s->next->front=s->front;
				free(s); 
				}
				else
				{
					s->front->next=NULL;
					free(s);
				}
			}
			else//空闲块大于进程大小的情况 
			{
				s->data=s->data-data1;
				s->ad=s->ad+data1;
			}
		return ad;
		}
		s=s->next;
	 } 
	return -1;
}
void InsertM(int M[],int ad,int data,int id)//将程序插入到内存中 
{
	int p=0;
	for(int i=ad;i<ad+data;i++)//根据位置进行插入 
	{
		M[i]=id;
	}
}
int FindID(int M[],int record[],int id,int m)//m代表数组数量 找到并修改 ，将地址存在record[0],大小存在record[1] 
{
	int c=-1;//记录大小 
	m++;
	record[0]=-1;record[1]=-1; 
	for(int i=0;i<m;i++)
	{
		if(M[i]==id)
		{
			record[0]=i;//记录回收地址 
			for(int j=i;j<m;j++)
			{
				c++;
				if(M[j]!=id)
				{
					record[1]=c;//记录回收进程大小 
					return 1;
				}
				M[j]=-1;//回收后将内存置为空闲(-1为空闲) 
			}
		}
	}
	return 0;
 } 
 void Sortlist(Snode *&l,int j)//链表排序 
{
 	Snode *f1;
 	Snode *f2;
 	Snode *f3;
 	f1=l->next;
 	f2=f1;
 	f3=f1;
 	while(f1->next!=NULL)
 	{
 			if(j==0)
			 while(f3!=NULL)//j==0则FF算法排列 
 			{
 				
 				if(f3->ad<f2->ad)
 				f2=f3;
 				f3=f3->next;
			 }
			 if(j==1)
			 while(f3!=NULL)//j==1则将空闲块按照从大到小排列 
 			{				
 				if(f3->data<f2->data)
 				f2=f3;
 				f3=f3->next;
			 }
			 if(j==2)//j==2则将空闲块按照从小到大排列 
			 while(f3!=NULL)
 			{
		
 				if(f3->data>f2->data)
 				f2=f3;
 				f3=f3->next;
			 }
			 if(f1!=f2)//每次循环都f2所指空闲块移到f1所指指针前 
			 {
			 	if(f2->next!=NULL)
				 {	
				 	f2->front->next=f2->next;
				 	f2->next->front=f2->front;
				 	f2->next=f1;
				 	f1->front->next=f2;
				 	f2->front=f1->front;
				 	f1->front=f2;
				 	
				  } 
				  else
				  {
				  	f2->front->next=NULL;
				  	f2->next=f1;
				  	f1->front->next=f2;
				  	f2->front=f1->front;
				 	f1->front=f2;	  	
				  }			 
			 }
			 else
			 {
			 	f1=f1->next;
			 }
			 f2=f1;
			 f3=f2;
	 }
  } 
void Recyclelist(Snode *&l,int ad)//回收函数 
{
	Snode *s;
	Snode *s1;//辅助frees 
	Snode *ad1;
	int j=0;//直接走2 
	ad1=l->next;
	while(ad1->ad!=ad)//先在内存(顺序表)中由地址(ad)找到目标程序 
	{
		ad1=ad1->next;
	}
	s=ad1;
		if(s->front!=l&&s->front->ad+s->front->data==s->ad)//回收区上方有空闲 
		{
			if(s->next==NULL)
			{
				s->front->data=s->front->data+s->data;
				s->front->next=NULL;
				free(s);
				s=NULL;
				
			}
			else{
			s->front->data=s->front->data+s->data;
			s->front->next=s->next;
			s->next->front=s->front;
			s1=s->front; 
			free(s);
			s=s1;
		
			}
		}
		if(s!=NULL&&s->next!=NULL&&s->ad+s->data==s->next->ad)//回收区下方有空闲 
		{
			if(s->next->next==NULL)
			{
				s->data=s->data+s->next->data;
				free(s->next);
				s->next=NULL;
			}
			else{
			s=s->next;
			s->front->data=s->front->data+s->data;
			s->front->next=s->next;
			s->next->front=s->front;
			free(s);
			}
		}
 } 
int main()
{	
	Snode *l;//zhixxiangneicun;
	int record[2];//record[0]记录ID，record[1]记录目标块大小  
	int m;
	cout<<"请输入内存初始大小:"; 
	cin>>m;//存储内存 
	int M[m+1];
	M[m]=-2;
	cout<<"初始内存状态如下(-1表示该单位空闲):\n";
	for(int i=0;i<m;i++)
	{
		M[i]=-1; 
		cout<<M[i]<<" "; 
	}
	l=(Snode *)malloc(sizeof(Snode));
	l->next=NULL;
	l->front=NULL;
	Insertlist(l,-1,0,m);
	int getselect=-1;
	int getid=-1;
	int getdata=-1;
	int b; 
	int j;
	while(1)
	{
		getid=getdata=-1;
		getselect=-1;
		j=-1;
		cout<<"\n请输入进行的步骤：（0代表插入进程，1代表回收进程）: "; 
		cin>>getselect;//用于记录操作步骤 
		if(getselect==0)
		{
			cout<<"请输入进程ID及大小:\n";
			cin>>getid;
			cin>>getdata;
			cout<<"请输入选择的插入方法，0-FF，1-BF,2-WF: "; 
			cin>>j;
			Sortlist(l,j); 
			b=Changelist(l,getdata);//插链表，查到并修改 
			if(b!=-1)
			{
				InsertM(M,b,getdata,getid);//将进程插入内存中 
			}
			else
			cout<<"程序过大，插入失败";		
		}
		if(getselect==1)
		{
			cout<<"请输入查找ID: ";
			cin>>getid; 
			if (FindID(M,record,getid,m))
			{
				Insertlist(l,-1,record[0],record[1]);
				Sortlist(l,0);
				Recyclelist(l,record[0]);
			}
			else
			cout<<"查无进程，回收失败"; 
		}
		cout<<"\n内存情况(-1表示空闲,数字表示相应ID占用空间)：\n";
		for(int i=0;i<m;i++)
	 	{
		cout<<" "<<M[i]; 
	 	}
	    cout<<"\n空闲链表情况(表头地址-空闲大小):\n";
		Snode *s5;
		s5=l->next;
		while(s5 !=NULL)
		{
			cout<<"->"<<s5->ad<<"-"<<s5->data;
			s5=s5->next; 
		}
	 } 	
	return 0;
 }

四、结果展示

      代码的插入与回收步骤展示的并不完整(整个流程太长了)，大家可自行尝试，有什么问题的话欢迎大家交流~