算法介紹

一、動(dòng)態(tài)分區(qū)分配算法
為把一個(gè)新作業(yè)裝入內(nèi)存，須按照一定的分配算法， 從空閑分區(qū)表或空閑分區(qū)鏈中出一分區(qū)分配給該作業(yè)。由于內(nèi)存分配算法對(duì)系統(tǒng)性能有很大的影響，故人們對(duì)它進(jìn)行了較為廣泛而深入的研究，于是產(chǎn)生了許多動(dòng)態(tài)分區(qū)分配算法。傳統(tǒng)的四種分配算法，它們都屬于順序式搜索算法。
二、分區(qū)分配操作
在動(dòng)態(tài)分區(qū)存儲(chǔ)管理方式中，主要的操作是分配內(nèi)存和回收內(nèi)存。
1)分配內(nèi)存
系統(tǒng)應(yīng)利用某種分配算法，從空閑分區(qū)鏈(表)中找到所需大小的分區(qū)。設(shè)請(qǐng)求的分區(qū)大小為u.size,表中每個(gè)空閑分區(qū)的大小可表示為m.size. 若m.size-u.size≤size(size是事先規(guī)定的不再切割的剩余分區(qū)的大小)，說明多余部分太小，可不再切割，將整個(gè)分區(qū)分配給請(qǐng)求者。否則(即多余部分超過size),便從該分區(qū)中按請(qǐng)求的大小劃分出一塊內(nèi) 存空間分配出去，余下的部分仍留在空閑分區(qū)鏈(表)中。然后，將分配區(qū)的首址返回給調(diào)用者。圖示出了分配流程。

2)回收內(nèi)存
當(dāng)進(jìn)程運(yùn)行完畢釋放內(nèi)存時(shí)，系統(tǒng)根據(jù)回收區(qū)的首址，從空閑區(qū)鏈(表)中找到相應(yīng)的插入點(diǎn)，此時(shí)可能出現(xiàn)以下四種情況之一：
(1)回收區(qū)與插入點(diǎn)的前一個(gè)空閑分區(qū)F1 相鄰接， 此時(shí)應(yīng)將回收區(qū)與插入點(diǎn)的前一分區(qū)合并，不必為回收分區(qū)分配新表項(xiàng)，而只需修改其前一分區(qū)F的大小。如圖（a）。
(2)回收分區(qū)與插入點(diǎn)的后一空閑分區(qū)F2相鄰接，此時(shí)也可將兩分區(qū)合并，形成新的空閑分區(qū)，但用回收區(qū)的首址作為新空閑區(qū)的首址，大小為兩者之和。如圖（b）
(3)回收區(qū)同時(shí)與插入點(diǎn)的前、后兩個(gè)分區(qū)鄰接。此時(shí)將三個(gè)分區(qū)合并，使用F的表項(xiàng)和F的首址，取消F2的表項(xiàng)，大小為三者之和。如圖（c）。
(4)回收區(qū)既不與F鄰接，又不與F2鄰接。這時(shí)應(yīng)為回收區(qū)單獨(dú)建立一個(gè)新表項(xiàng)，填寫回收區(qū)的首址和大小，并根據(jù)其首址插入到空閑鏈中的適當(dāng)位置。

內(nèi)存回收時(shí)流程圖：

三、基于順序搜索的動(dòng)態(tài)分區(qū)分配算法

為了實(shí)現(xiàn)動(dòng)態(tài)分區(qū)分配，通常是將系統(tǒng)中的空閑分區(qū)鏈接成一個(gè)鏈。所謂順序搜索，是指依次搜索空閑分區(qū)鏈上的空閑分區(qū)，去尋找一個(gè)其大小能滿足要求的分區(qū)?；陧樞蛩阉鞯膭?dòng)態(tài)分區(qū)分配算法有如下四種:首次適應(yīng)算法、循環(huán)首次適應(yīng)算法、最佳適應(yīng)算法和最壞適應(yīng)算法，下面分別進(jìn)行介紹。

1.首次適應(yīng)(first fit, FF)算法

我們以空閑分區(qū)鏈為例來說明采用FF算法時(shí)的分配情況。FF算法要求空閑分區(qū)鏈以地址遞增的次序鏈接。在分配內(nèi)存時(shí)，從鏈?zhǔn)组_始順序查找，直至找到一個(gè)大小能滿足要求的空閑分區(qū)為止。然后再按照作業(yè)的大小，從該分區(qū)中劃出一塊內(nèi)存空間，分配給請(qǐng)求者，余下的空閑分區(qū)仍留在空閑鏈中。若從鏈?zhǔn)字敝伶溛捕疾荒苷业揭粋€(gè)能滿足要求的分區(qū)，則表明系統(tǒng)中已沒有足夠大的內(nèi)存分配給該進(jìn)程，內(nèi)存分配失敗，返回。該算法傾向于優(yōu)先利用內(nèi)存中低址部分的空閑分區(qū),從而保留了高址部分的大空閑區(qū)。這為以后到達(dá)的大作業(yè)分配大的內(nèi)存空間創(chuàng)造了條件。其缺點(diǎn)是低址部分不斷被劃分，會(huì)
留下許多難以利用的、很小的空閑分區(qū)，稱為碎片。而每次查找又都是從低址部分開始的，這無疑又會(huì)增加查找可用空閑分區(qū)時(shí)的開銷。

2.循環(huán)首次適應(yīng)(next fit，NF)算法

為避免低址部分留下許多很小的空閑分區(qū)，以及減少查找可用空閑分區(qū)的開銷，循環(huán)首次適應(yīng)算法在為進(jìn)程分配內(nèi)存空間時(shí)，不再是每次都從鏈?zhǔn)组_始查找，而是從上次找到的空閑分區(qū)的下一個(gè)空閑分區(qū)開始查找，直至找到一一個(gè)能滿足要求的空閑分區(qū)，從中劃出一塊 與請(qǐng)求大小相等的內(nèi)存空間分配給作業(yè)。為實(shí)現(xiàn)該算法，應(yīng)設(shè)置一起始查尋指針，用于指示下一次起始查尋的空閑分區(qū)，并采用循環(huán)查找方式，即如果最后一個(gè)(鏈尾)空閑分區(qū)的大小仍不能滿足要求，則應(yīng)返回到第一個(gè)空閑分區(qū)，比較其大小是否滿足要求。找到后，應(yīng)調(diào)整起始查尋指針。該算法能使內(nèi)存中的空閑分區(qū)分布得更均勻，從而減少了查找空閑分區(qū)時(shí)的開銷，但這樣會(huì)缺乏大的空閑分區(qū)。

3.最佳適應(yīng)(best fit，BF)算法

所謂“最佳”是指，每次為作業(yè)分配內(nèi)存時(shí)，總是把能滿足要求、又是最小的空閑分區(qū)分配給作業(yè)，避免“大材小用”。為了加速尋找，該算法要求將所有的空閑分區(qū)按其容量以從小到大的順序形成——空閑分區(qū)鏈。這樣，第一次找到的能滿足要求的空閑區(qū)必然是最佳的。孤立地看，最佳適應(yīng)算法似乎是最佳的，然而在宏觀上卻不一定。 因?yàn)槊看畏峙浜笏懈钕聛淼氖Ｓ嗖糠挚偸亲钚〉?，這樣，在存儲(chǔ)器中會(huì)留下許多難以利用的碎片。

4.最壞適應(yīng)(worst fit, WF)算法

由于最壞適應(yīng)分配算法選擇空閑分區(qū)的策略正好與最佳適應(yīng)算法相反:它在掃描整個(gè)空閑分區(qū)表或鏈表時(shí)，總是挑選-一個(gè)最大的空閑區(qū)，從中分割一部分存儲(chǔ)空間給作業(yè)使用，以至于存儲(chǔ)器中缺乏大的空閑分區(qū)，故把它稱為是最壞適應(yīng)算法。實(shí)際上，這樣的算法未必是最壞的，它的優(yōu)點(diǎn)是可使剩下的空閑區(qū)不至于太小，產(chǎn)生碎片的可能性最小，對(duì)中、小作業(yè)有利。同時(shí)，最壞適應(yīng)分配算法查找效率很高，該算法要求，將所有的空閑分區(qū)，按其容量以從大到小的順序形成——空閑分區(qū)鏈，查找時(shí)，只要看第一個(gè)分區(qū)能否滿足作業(yè)要求即可。

直接代碼（實(shí)驗(yàn)原因封裝在一塊）

.h文件（頭文件）

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

typedef struct Node
{
	int pid;//分區(qū)號(hào)
	long size;//分區(qū)大小
	long start_locat;//分區(qū)起始地址
	int status;//分區(qū)狀態(tài)
	struct Node* next;
	struct Node* perior;
}Node, *PNode;
void Init_list(PNode list);//初始化頭結(jié)點(diǎn)
void Creat_list(PNode list);//初始化鏈表
PNode Insert_Node();//新插入鏈表
long* _Sort_min(long* p);//小到大因?yàn)閷?shí)驗(yàn)量小采用冒泡排序
long* _Sort_max(long* p);//大到小因?yàn)閷?shí)驗(yàn)量小采用冒泡排序
void First_fit(PNode list);//FF首次適應(yīng)算法
void Next_fit(PNode list);//循環(huán)首次適應(yīng)
void Best_fit(PNode list);//BF 最佳適應(yīng)算法
void Worst_fit(PNode list);//最歡適應(yīng)算法
void Release_Mem(PNode list);//回收內(nèi)存
void Show(PNode list);

.cpp文件

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

#define MAX_ALLOC_SIZE 600000
long start_add, end_add, memory_size;// 起始地址，終止地址，內(nèi)存大小 
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 << "請(qǐng)輸入申請(qǐng)資源的進(jìn)程個(gè)數(shù)：" << endl;
	cin >> _num;
	for (int i = 0; i <= _num; i++)
	{
		Node* newnode = (Node*)malloc(sizeof(Node));
		assert(NULL != newnode);
		if (i < _num)
		{
           cout << "請(qǐng)輸入第" << i + 1 << "個(gè)進(jìn)程調(diào)入的分區(qū)號(hào)及其大小:" << 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 << "請(qǐng)輸入進(jìn)程調(diào)入的分區(qū)號(hào)及其大小:" << 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 << "沒有適合的申請(qǐng)位置" << 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 << "沒有適合的申請(qǐng)位置" << 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 << "請(qǐng)輸入需要回收的進(jìn)程號(hào)：" << 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 << "回收錯(cuò)誤請(qǐng)輸入正確進(jìn)程號(hào)" << 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("分區(qū)號(hào)碼  分區(qū)大小  分區(qū)始址  分區(qū)狀態(tài)\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文件（主函數(shù)）

int main()
{
	struct Node head;
	int select = 1;
	cout << "請(qǐng)輸入請(qǐng)初始化內(nèi)存塊的首地址及內(nèi)存大小：" << endl;
	cin >> start_add >> memory_size;
	if (memory_size > MAX_ALLOC_SIZE) {
		cout << "申請(qǐng)內(nèi)存超過內(nèi)存大小閾值！" << endl;
		return -1;
	}
	Init_list(&head);
	Creat_list(&head);
	Show(&head);
	while (1)
	{
		cout << "******************************************\n";
		cout << "*****1.******* 首次適應(yīng)算法 ************\n";
		cout << "*****2.******循環(huán)首次適應(yīng)算法 ************\n";
		cout << "*****3.******  最佳適應(yīng)算法   ************\n";
		cout << "*****4.******  最壞適應(yīng)算法   ************\n";
		cout << "*****5.*******   回收內(nèi)存    *********\n";
		cout << "*****0.**********退出*********************\n";
		cout << "請(qǐng)選擇:> ";
		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內(nèi)存大小1024對(duì)鏈表初始化

（2）選用首次適應(yīng)算法申請(qǐng)分區(qū)號(hào)為4大小為428的進(jìn)程：

（3）為了方便 進(jìn)行回收算法 第二第四未被回收。注意：回收有四種狀態(tài)

（4）使用最佳適應(yīng)算法 申請(qǐng) 12 大小26的分區(qū)：

（5）使用最壞適應(yīng)算法 申請(qǐng) 分區(qū)號(hào)15 大小為88按照最佳適應(yīng)為申請(qǐng)?jiān)?號(hào)分區(qū)但是最壞適應(yīng)在最大分區(qū) 如下：

（6）循環(huán)首次自己試去…end
上課了 跑了。。。。。。。。。。。文章來源地址http://www.zghlxwxcb.cn/news/detail-495265.html

到了這里，關(guān)于操作系統(tǒng)動(dòng)態(tài)分區(qū)分配方式C/C++語言（首次適應(yīng)算法（FF）循環(huán)首次適應(yīng)算法（NF）最best適應(yīng)算法（BF）最壞適應(yīng)算法（WF））的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！