1. Toy模板网首页
  2. > Toy博客

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

10月前 作者：小小圆脸 分类：Toy博客 阅读(41) 违法举报

这篇具有很好参考价值的文章主要介绍了操作系统动态分区分配方式C/C++语言（首次适应算法（FF）循环首次适应算法（NF）最best适应算法（BF）最坏适应算法（WF））。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

算法介绍

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

操作系统动态分区分配方式C/C++语言（首次适应算法（FF）循环首次适应算法（NF）最best适应算法（BF）最坏适应算法（WF））
内存回收时流程图：
操作系统动态分区分配方式C/C++语言（首次适应算法（FF）循环首次适应算法（NF）最best适应算法（BF）最坏适应算法（WF））
三、基于顺序搜索的动态分区分配算法

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

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对链表初始化
操作系统动态分区分配方式C/C++语言（首次适应算法（FF）循环首次适应算法（NF）最best适应算法（BF）最坏适应算法（WF））
（2）选用首次适应算法申请分区号为4大小为428的进程：

操作系统动态分区分配方式C/C++语言（首次适应算法（FF）循环首次适应算法（NF）最best适应算法（BF）最坏适应算法（WF））
（3）为了方便 进行回收算法 第二第四未被回收。注意：回收有四种状态
操作系统动态分区分配方式C/C++语言（首次适应算法（FF）循环首次适应算法（NF）最best适应算法（BF）最坏适应算法（WF））
（4）使用最佳适应算法 申请 12 大小26的分区：

操作系统动态分区分配方式C/C++语言（首次适应算法（FF）循环首次适应算法（NF）最best适应算法（BF）最坏适应算法（WF））
（5）使用最坏适应算法 申请 分区号15 大小为88按照最佳适应为申请在2号分区但是最坏适应在最大分区 如下：
操作系统动态分区分配方式C/C++语言（首次适应算法（FF）循环首次适应算法（NF）最best适应算法（BF）最坏适应算法（WF））
（6）循环首次自己试去…end
上课了 跑了。。。。。。。。。。。文章来源地址https://www.toymoban.com/news/detail-495265.html

到了这里，关于操作系统动态分区分配方式C/C++语言（首次适应算法（FF）循环首次适应算法（NF）最best适应算法（BF）最坏适应算法（WF））的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 操作系统中文件系统的实现和分配方式探析（下）

    操作系统中文件系统的实现和分配方式探析（下）

    我们已经对连续分配的方式有了一定的了解，并且也清楚了它存在的问题和局限性。为了解决这些问题，非连续存放的方式应运而生。非连续空间存储大致可以分为两种形式：链表形式和索引形式。 链式分配是一种离散分配的方式，用于为文件分配非连续的磁盘块。它有两种

    2024年02月10日
    浏览(41)
  • 操作系统中文件系统的实现和分配方式探析（上）

    操作系统中文件系统的实现和分配方式探析（上）

    在 Linux 文件系统中，用户空间、系统调用、虚拟机文件系统、缓存、文件系统以及存储之间存在着紧密的关系。 如下图： 在操作系统中，文件系统起到了重要的作用，它们负责管理操作系统中的文件和目录。然而，不同的文件系统有着不同的实现方式和存储位置。为了提供

    2024年02月10日
    浏览(35)
  • 实验名称：动态分区分配方式模拟

    实验名称：动态分区分配方式模拟

    实验名称：动态分区分配方式模拟 实验目的 进一步加深对动态分区分配管理方式的理解；掌握动态分区分配方式使用的数据结构、分配算法和回收算法 实验内容 编写C语言程序，模拟实现首次/最佳/最坏适应算法的内存块分配和回收，要求每次分配和回收后显示出空闲分区和

    2024年02月03日
    浏览(40)
  • 【操作系统】基于动态优先级的进程调度算法-C语言实现（有代码）

    【操作系统】基于动态优先级的进程调度算法-C语言实现（有代码）

    本文章将会介绍如何编写动态优先级的进程调度算法，并使用从语言实现。 一、什么是动态优先级的调度算法        进程运行一个时间片后，如果进程已占用 CPU时间已达到所需要的运行时间，则撤消该进程；如果运行一个时间片后进程的已占用CPU时间还未达所需要的运行

    2024年02月06日
    浏览(50)
  • 操作系统-内存分配算法

    操作系统-内存分配算法

    操作系统原理实验报告 实验题目   实 验 四内存分配算法     1.1 实验目的 一个好的计算机系统不仅要有一个足够容量的、存取速度高的、稳定可靠的主存储器，而且要能合理地分配和使用这些存储空间。当用户提出申请主存储器空间时，存储管理必须根据申请者的要求，

    2024年02月03日
    浏览(47)
  • GUID分区与MBR分区有什么区别？ 操作系统知识

    GUID分区与MBR分区有什么区别？ 操作系统知识

    GUID分区与MBR分区有什么区别？ 操作系统知识 1、MBR分区表类型的磁盘 主引导记录（Master Boot Record，缩写：MBR），又叫做主引导扇区，它仅仅包含一个64个字节的硬盘分区表。由于每个分区信息需要16个字节，所以对于采用MBR型分区结构的硬盘，最多只能识别4个主要分区（Pr

    2024年02月13日
    浏览(42)

  • 操作系统实验（一）——可变分区存储管理

    湖南师范大学信息科学与工程学院计算机科学与技术非师范班操作系统实验报告 一、实验目的： 加深对可变分区存储管理的理解； 提高用C语言编制大型系统程序的能力，特别是掌握C语言编程的难点：指针和指针作为函数参数； 掌握用指针实现链表和在链表上的基本操作。

    2024年02月06日
    浏览(43)
  • 银河麒麟桌面操作系统之磁盘分区与磁盘挂载

    银河麒麟桌面操作系统之磁盘分区与磁盘挂载

    今天跟大家分享一篇干货 - - 银河麒麟添加硬盘与挂载硬盘，也就是磁盘分区与磁盘挂载 本文使用fdisk命令进行操作 测试环境：虚拟机（因为使用的是虚拟机，因此小编添加的磁盘容量较小） 系统版本：Kylin-Desktop-V10-SP1-Release-hwe-2107 注：此为桌面系统教程 磁盘分区 1.我们打

    2024年01月19日
    浏览(208)
  • Ubuntu20.04操作系统安装及重中之重：系统分区

    Ubuntu20.04操作系统安装及重中之重：系统分区

    最近因为学习原因，需要将电脑设置为双系统，在windows10的系统下去安装Ubuntu操作系统。本来看网上相关的安装教程蛮多的，以为比较简单，结果一路过五关斩六将，坑的七零八落的，折腾了好久，才算安装完成了。 在此将Ubuntu20.04的系统安装过程总结记录，以供报考。 准备

    2024年02月07日
    浏览(53)

  • 操作系统与云计算：实现高效的资源分配和管理

    操作系统和云计算都是现代计算机科学的核心领域。操作系统负责管理计算机资源，为应用程序提供服务，而云计算则是利用大规模网络计算资源为用户提供服务。在这篇文章中，我们将探讨操作系统与云计算之间的密切关系，以及如何实现高效的资源分配和管理。 操作系统

    2024年04月11日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包