操作系统动态分区分配方式C/C++语言（首次适应算法（FF）循环首次适应算法（NF）最best适应算法（BF）最坏适应算法（WF））

算法介绍一、动态分区分配算法为把一个新作业装入内存，须按照一定的分配算法，从空闲分区表或空闲分区链中出一分区分配给该作业。由于内存分配算法对系统性能有很大的影响，故人们对它进行了较为广泛而深入的研究，于是产生了许多动态分区分配算法。传统的四种分配算法，它们都属于顺序式搜索算法。二、分区分配操作在动态分区存储管理方式中，主要的操作是分配内存和回收内存。1)分配内存系统应利用某种分配算法，从空闲分区

小小圆脸

18419人浏览 · 2021-12-06 18:03:28

小小圆脸 · 2021-12-06 18:03:28 发布

算法介绍

一、动态分区分配算法
为把一个新作业装入内存，须按照一定的分配算法，从空闲分区表或空闲分区链中出一分区分配给该作业。由于内存分配算法对系统性能有很大的影响，故人们对它进行了较为广泛而深入的研究，于是产生了许多动态分区分配算法。传统的四种分配算法，它们都属于顺序式搜索算法。
二、分区分配操作
在动态分区存储管理方式中，主要的操作是分配内存和回收内存。
1)分配内存
系统应利用某种分配算法，从空闲分区链(表)中找到所需大小的分区。设请求的分区大小为u.size,表中每个空闲分区的大小可表示为m.size. 若m.size-u.size≤size(size是事先规定的不再切割的剩余分区的大小)，说明多余部分太小，可不再切割，将整个分区分配给请求者。否则(即多余部分超过size),便从该分区中按请求的大小划分出一块内存空间分配出去，余下的部分仍留在空闲分区链(表)中。然后，将分配区的首址返回给调用者。图示出了分配流程。
在这里插入图片描述
2)回收内存
当进程运行完毕释放内存时，系统根据回收区的首址，从空闲区链(表)中找到相应的插入点，此时可能出现以下四种情况之一：
(1)回收区与插入点的前一个空闲分区F1 相邻接，此时应将回收区与插入点的前一分区合并，不必为回收分区分配新表项，而只需修改其前一分区F的大小。如图（a）。
(2)回收分区与插入点的后一空闲分区F2相邻接，此时也可将两分区合并，形成新的空闲分区，但用回收区的首址作为新空闲区的首址，大小为两者之和。如图（b）
(3)回收区同时与插入点的前、后两个分区邻接。此时将三个分区合并，使用F的表项和F的首址，取消F2的表项，大小为三者之和。如图（c）。
(4)回收区既不与F邻接，又不与F2邻接。这时应为回收区单独建立一个新表项，填写回收区的首址和大小，并根据其首址插入到空闲链中的适当位置。

在这里插入图片描述
内存回收时流程图：

三、基于顺序搜索的动态分区分配算法

为了实现动态分区分配，通常是将系统中的空闲分区链接成一个链。所谓顺序搜索，是指依次搜索空闲分区链上的空闲分区，去寻找一个其大小能满足要求的分区。基于顺序搜索的动态分区分配算法有如下四种:首次适应算法、循环首次适应算法、最佳适应算法和最坏适应算法，下面分别进行介绍。

1.首次适应(first fit, FF)算法

我们以空闲分区链为例来说明采用FF算法时的分配情况。FF算法要求空闲分区链以地址递增的次序链接。在分配内存时，从链首开始顺序查找，直至找到一个大小能满足要求的空闲分区为止。然后再按照作业的大小，从该分区中划出一块内存空间，分配给请求者，余下的空闲分区仍留在空闲链中。若从链首直至链尾都不能找到一个能满足要求的分区，则表明系统中已没有足够大的内存分配给该进程，内存分配失败，返回。该算法倾向于优先利用内存中低址部分的空闲分区,从而保留了高址部分的大空闲区。这为以后到达的大作业分配大的内存空间创造了条件。其缺点是低址部分不断被划分，会
留下许多难以利用的、很小的空闲分区，称为碎片。而每次查找又都是从低址部分开始的，这无疑又会增加查找可用空闲分区时的开销。

2.循环首次适应(next fit，NF)算法

为避免低址部分留下许多很小的空闲分区，以及减少查找可用空闲分区的开销，循环首次适应算法在为进程分配内存空间时，不再是每次都从链首开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找，直至找到一一个能满足要求的空闲分区，从中划出一块与请求大小相等的内存空间分配给作业。为实现该算法，应设置一起始查寻指针，用于指示下一次起始查寻的空闲分区，并采用循环查找方式，即如果最后一个(链尾)空闲分区的大小仍不能满足要求，则应返回到第一个空闲分区，比较其大小是否满足要求。找到后，应调整起始查寻指针。该算法能使内存中的空闲分区分布得更均匀，从而减少了查找空闲分区时的开销，但这样会缺乏大的空闲分区。

3.最佳适应(best fit，BF)算法

所谓“最佳”是指，每次为作业分配内存时，总是把能满足要求、又是最小的空闲分区分配给作业，避免“大材小用”。为了加速寻找，该算法要求将所有的空闲分区按其容量以从小到大的顺序形成——空闲分区链。这样，第一次找到的能满足要求的空闲区必然是最佳的。孤立地看，最佳适应算法似乎是最佳的，然而在宏观上却不一定。因为每次分配后所切割下来的剩余部分总是最小的，这样，在存储器中会留下许多难以利用的碎片。

4.最坏适应(worst fit, WF)算法

由于最坏适应分配算法选择空闲分区的策略正好与最佳适应算法相反:它在扫描整个空闲分区表或链表时，总是挑选-一个最大的空闲区，从中分割一部分存储空间给作业使用，以至于存储器中缺乏大的空闲分区，故把它称为是最坏适应算法。实际上，这样的算法未必是最坏的，它的优点是可使剩下的空闲区不至于太小，产生碎片的可能性最小，对中、小作业有利。同时，最坏适应分配算法查找效率很高，该算法要求，将所有的空闲分区，按其容量以从大到小的顺序形成——空闲分区链，查找时，只要看第一个分区能否满足作业要求即可。

直接代码（实验原因封装在一块）

.h文件（头文件）

#pragma once
#include<iostream>
using namespace std;

typedef struct Node
{
	int pid;//分区号
	long size;//分区大小
	long start_locat;//分区起始地址
	int status;//分区状态
	struct Node* next;
	struct Node* perior;
}Node, *PNode;
void Init_list(PNode list);//初始化头结点
void Creat_list(PNode list);//初始化链表
PNode Insert_Node();//新插入链表
long* _Sort_min(long* p);//小到大因为实验量小采用冒泡排序
long* _Sort_max(long* p);//大到小因为实验量小采用冒泡排序
void First_fit(PNode list);//FF首次适应算法
void Next_fit(PNode list);//循环首次适应
void Best_fit(PNode list);//BF 最佳适应算法
void Worst_fit(PNode list);//最欢适应算法
void Release_Mem(PNode list);//回收内存
void Show(PNode list);

.cpp文件

#include<assert.h>
#include"list.h"

#define MAX_ALLOC_SIZE 600000
long start_add, end_add, memory_size;// 起始地址，终止地址，内存大小 
int free_num = 0;
Node* Flag_Node = NULL;
void Init_list(PNode list)
{
	assert(NULL != list);
	list->next =list;
	list->perior = list;
	list->start_locat = start_add;
	list->size = 0;
	list->status = 1;
}
void Creat_list(PNode list)
{
	assert(NULL != list);
	int _id = -1, _num = 0;
	long _size = -1;
	long _locat = list->start_locat;
	cout << "请输入申请资源的进程个数：" << endl;
	cin >> _num;
	for (int i = 0; i <= _num; i++)
	{
		Node* newnode = (Node*)malloc(sizeof(Node));
		assert(NULL != newnode);
		if (i < _num)
		{
           cout << "请输入第" << i + 1 << "个进程调入的分区号及其大小:" << endl;
		   cin >> _id >> _size;
		   newnode->pid = _id;
		   newnode->size = _size;
		   newnode->start_locat = _locat;
		   newnode->status = 1;
		   _locat += _size;
		}
		else
		{
			newnode->pid = -1;
			newnode->size = memory_size - _locat;
			newnode->start_locat = _locat;
			newnode->status = 0;
			free_num++;
		}
		PNode ptr = list;
		for (ptr; ptr->next != list; ptr = ptr->next);
		newnode->next = list;
		newnode->perior = ptr;
		ptr->next = newnode;
		list->perior = newnode;
	}
}
PNode Insert_Node()
{
	Node* newnode = (Node*)malloc(sizeof(Node));
	assert(NULL != newnode);
	int _id = 0;
	long _size = 0;
	cout << "请输入进程调入的分区号及其大小:" << endl;
	cin >> _id >> _size;
	newnode->next = NULL;
	newnode->perior = NULL;
	newnode->pid = _id;
	newnode->size = _size;
	newnode->start_locat = 0;
	newnode->status = 0;
	return newnode;

}
void First_fit(PNode list)
{
	assert(NULL != list);
	PNode _head = Insert_Node();
	PNode ptr = list;
	while (ptr->next != list)
	{
		PNode cur = ptr->next;
		if (cur->status==0&&cur->size > _head->size)
		{ 
			_head->next = cur;
			_head->perior = ptr;
             cur->perior = _head;
			 ptr->next = _head;
			_head->status = 1;
			_head->start_locat = ptr->start_locat + ptr->size;
			cur->start_locat = _head->start_locat + _head->size;
			cur->size = cur->size - _head->size;
			break;
		}
		else if (cur->status == 0&&cur->size == _head->size)
		{
			cur->pid = _head->pid;
			cur->status = 1;
			free_num--;
			break;
		}
		ptr = ptr->next;
	}
	if (ptr->next->status == 0)
	{
		cout << "没有适合的申请位置" << endl;
	}
}
void Next_fit(PNode list)
{
	assert(NULL != list);
	PNode _head = Insert_Node();
	PNode p = list;
	if (Flag_Node != NULL)
	{
		p = Flag_Node;
	}
	PNode ptr = p;
	while (ptr->next != p)
	{
		PNode cur = ptr->next;
		if (cur->status == 0 && cur->size > _head->size)
		{
			_head->next = cur;
			_head->perior = ptr;
			cur->perior = _head;
			ptr->next = _head;
			_head->status = 1;
			_head->start_locat = ptr->start_locat + ptr->size;
			cur->start_locat = _head->start_locat + _head->size;
			cur->size = cur->size - _head->size;
			Flag_Node = _head;
			break;
		}
		else if (cur->status == 0 && cur->size == _head->size)
		{
			cur->pid = _head->pid;
			cur->status = 1;
			Flag_Node = cur;
			free_num--;
			break;
		}
		ptr = ptr->next;
	}
	if (ptr->next->status == 0)
	{
		cout << "没有适合的申请位置" << endl;
	}
}
long* _Sort_min(long* p)
{
	assert(NULL != p);
	for (int i = 0; i < free_num-1; i++)
	{
		for (int j = 0; j < free_num - 1 - i; j++)
		{
			if (p[j] > p[j + 1])
			{
				long tmp = p[j];
				p[j] = p[j + 1];
				p[j + 1] = tmp;
			}
		}
	 }
	return p;
}
void Best_fit(PNode list)
{
	assert(NULL != list);
	PNode _head = Insert_Node();
	long* p = (long*)malloc(sizeof(long)*(free_num));
	assert(NULL!=p);
	PNode ptr = list->next;
	long i = 0, j = 0;
	while (ptr!= list)
	{
		if (ptr->status == 0)
		{
			*(p+i) = ptr->size;
			i++;
		}
		ptr = ptr->next;
	}
	long* q = _Sort_min(p);
	while (j < free_num)
	{
		if (_head->size < q[j])
		{
			break;
		}
		j++;
	}
	PNode cur = list;
	while (cur->next != list)
	{
		PNode tr = cur->next;
		if (tr->status==0&&tr->size == q[j])
		{
			if (_head->size < tr->size)
			{
				_head->next = tr;
				_head->perior = cur;
				tr->perior = _head;
				cur->next = _head;
				_head->status = 1;
				_head->start_locat = cur->start_locat + cur->size;
				tr->start_locat = _head->start_locat + _head->size;
				tr->size = tr->size - _head->size;
				break;
			}
			else if(_head->size==tr->size)
			{
				tr->pid = _head->pid;
				tr->status = 1;
				break;
			}
		}
		cur = cur->next;
	}
}
long* _Sort_max(long* p)
{
	assert(NULL != p);
	for (int i = 0; i < free_num - 1; i++)
	{
		for (int j = 0; j < free_num - 1 - i; j++)
		{
			if (p[j] <= p[j + 1])
			{
				long tmp = p[j];
				p[j] = p[j + 1];
				p[j + 1] = tmp;
			}
		}
	}
	return p;
}
void Worst_fit(PNode list)
{
	assert(NULL != list);
	PNode _head = Insert_Node();
	long* p = (long*)malloc(sizeof(long) * (free_num));
	assert(NULL != p);
	PNode ptr = list->next;
	long i = 0, j = 0;
	while (ptr != list)
	{
		if (ptr->status == 0)
		{
			*(p + i) = ptr->size;
			i++;
		}
		ptr = ptr->next;
	}
	long* q = _Sort_max(p);
	PNode cur = list;
	while (cur->next != list)
	{
		PNode tr = cur->next;
		if (tr->status == 0 && tr->size == q[j])
		{
			if (_head->size < tr->size)
			{
				_head->next = tr;
				_head->perior = cur;
				tr->perior = _head;
				cur->next = _head;
				_head->status = 1;
				_head->start_locat = cur->start_locat + cur->size;
				tr->start_locat = _head->start_locat + _head->size;
				tr->size = tr->size - _head->size;
				break;
			}
			else if (_head->size == tr->size)
			{
				tr->pid = _head->pid;
				tr->status = 1;
				break;
			}
		}
		cur = cur->next;
	}
}
void Release_Mem(PNode list)
{
	assert(NULL != list);
	int delet_id = 0;
	cout << "请输入需要回收的进程号：" << endl;
	cin >> delet_id;
	PNode ptr = list;
	while (ptr->next != list)
	{
		PNode cur = ptr->next;
		if (cur->pid == delet_id)
		{
			if (cur->status == 0)
			{
				cout << "回收错误请输入正确进程号" << endl;
				break;
			}
			else
			{
				if (ptr->status == 0&&cur->next->status==1)//1
				{
					ptr->size = ptr->size + cur->size;
					cur->next->perior = ptr;
					ptr->next = cur->next;
					free(cur);
					cur = NULL;
					break;
				}
				else if (ptr->status == 1 && cur->next->status == 0)//2
				{
					PNode p = cur->next;
					cur->size = cur->size + p->size;
					p->next->perior = cur;
					cur->next = p->next;
					cur->status = 0;
					free(p);
					p = NULL;
					break;
				}
				else if (ptr->status == 0 && cur->next->status == 0)//3
				{
					PNode p = cur->next;
					ptr->size = cur->size + ptr->size + p->size;
					p->perior = ptr;
					ptr->next = p;
					free(cur);
					cur = NULL;
					p->next->perior = ptr;
					ptr->next = p->next;
					free(p);
					p = NULL;
					free_num--;
					break;
				}
				else//4
				{
					cur->status = 0;
					free_num++;
					break;
				}
				
			}
			
		}
		ptr = ptr->next;
	}
}
void Show(PNode list)
{
	assert(NULL != list);
	printf("分区号码  分区大小  分区始址  分区状态\n"); 
	PNode ptr = list;
	while (ptr->next!=list)
	{    
		ptr = ptr->next;
		if (ptr->status == 0)
		{
			printf("%6d    %6dk    %6dk      空闲\n",ptr->pid, ptr->size,ptr->start_locat);
		}
		else
		{
			printf("%6d    %6dk    %6dk      占用\n",ptr->pid, ptr->size, ptr->start_locat);
		}
		
	}
}

.cpp文件（主函数）

int main()
{
	struct Node head;
	int select = 1;
	cout << "请输入请初始化内存块的首地址及内存大小：" << endl;
	cin >> start_add >> memory_size;
	if (memory_size > MAX_ALLOC_SIZE) {
		cout << "申请内存超过内存大小阈值！" << endl;
		return -1;
	}
	Init_list(&head);
	Creat_list(&head);
	Show(&head);
	while (1)
	{
		cout << "******************************************\n";
		cout << "*****1.******* 首次适应算法 ************\n";
		cout << "*****2.******循环首次适应算法 ************\n";
		cout << "*****3.******  最佳适应算法   ************\n";
		cout << "*****4.******  最坏适应算法   ************\n";
		cout << "*****5.*******   回收内存    *********\n";
		cout << "*****0.**********退出*********************\n";
		cout << "请选择:> ";
		cin >> select;
		switch (select)
		{
		case 1:
			First_fit(&head);
			Show(&head);
			break;
		case 2:
			Next_fit(&head);
			Show(&head);
			break;
		case 3:
			Best_fit(&head);
			Show(&head);
			break;
		case 4:
			Worst_fit(&head);
			Show(&head);
			break;
		case 5:
			Release_Mem(&head);
			Show(&head);
			break;
		default:
			break;
		}
	}
	return 0;
}

第一次写不太好见谅

（1）以首地址为0内存大小1024对链表初始化
在这里插入图片描述
（2）选用首次适应算法申请分区号为4大小为428的进程：

在这里插入图片描述
（3）为了方便进行回收算法第二第四未被回收。注意：回收有四种状态

（4）使用最佳适应算法申请 12 大小26的分区：

在这里插入图片描述
（5）使用最坏适应算法申请分区号15 大小为88按照最佳适应为申请在2号分区但是最坏适应在最大分区如下：

（6）循环首次自己试去…end
上课了跑了。。。。。。。。。。。

开放原子开发者工作坊

开放原子开发者工作坊旨在鼓励更多人参与开源活动，与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动，如meetup、训练营等，主打技术交流，干货满满，真诚地邀请各位开发者共同参与！

更多推荐

【入坑ORB-SLAM3系列2】未标定的realsense D435i试运行ORB-SLAM3（手把手教学，含realsense d435i一些错误的解决）

文章目录前言一、前奏1. Error 12. Error 2二、正文1. 查看自己相机的可用的分辨率与频率2. 配置rs_camera.launch（realsense-ros文件夹中）3. 修改.yaml配置文件4. 修改源文件（只修改订阅的相机话题即可）三、尾声总结Reference前言我之前刚编译成功ORB-SLAM3的时候试跑了一下demo（数据集），但是效果其实很一般，甚至想说拉垮，在R