程序员经验分享-hwhale

动态分区分配算法(First Fit，Next Fit，Best Fit，Worst Fit)

2023-10-27

一、动态分区分配算法的背景

为了能将用户程序装入内存，必须为它分配一定大小的内存空间。连续分配方式是最早出现的一种存储器分配方式， 曾被广泛应用于上世纪60~ -80 年代的OS中，该分配万式为个用户程序分配 一个连续的内存空间， 即程序中代码或数据的逻辑地址相邻，体现在内存空间分配时物理地址的相邻。连续分配方式可分为四类:单一连续分配、固定分区分配、动态分区分配以及动态可重定位分区分配算法四种方式，其中动态分区分配算法就是此实验的实验对象。
动态分区分配又称为可变分区分配，它是根据进程的实际需要，动态地为之分配内存空间。在实现动态分区分配时，将涉及到分区分配中所用的数据结构、分区分配算法和分区的分配与回收操作这样三方面的问题。
动态分区分配又称为可变分区分配，它是根据进程的实际需要，动态地为之分配内存空间。在实现动态分区分配时，将涉及到分区分配中所用的数据结构、分区分配算法和分区的分配与回收操作这样三方面的问题。

二、四种分配算法原理

1.首次适应算法（First Fit）

将空闲分区链以地址递增的顺序连接；在进行内存分配时，从链首开始顺序查找，直到找到一块分区的大小可以满足需求时，按照该作业的大小，从该分区中分配出内存，将剩下的空闲分区仍然链在空闲分区链中。
在这里插入图片描述

2.循环首次适应算法（Next Fit）

分配内存时不是从链首进行查找可以分配 内存的空闲分区，而是从上一次分配内存的空闲分区的下一个分区开始查找，直到找到可以为该进程分配内存的空闲分区；
在这里插入图片描述

3.最佳适应算法（Best Fit）

将空闲分区链中的空闲分区按照空闲分区由小到大的顺序排序，从而形成空闲分区链。每次从链首进行查找合适的空闲分区为作业分配内存，这样每次找到的空闲分区是和作业大小最接近的，所谓“最佳”。
在这里插入图片描述

4.最坏适应算法（Worst Fit）

与最佳适应算法刚好相反，将空闲分区链的分区按照从大到小的顺序排序形成空闲分区链，每次查找时只要看第一个空闲分区是否满足即可。
在这里插入图片描述

三、四种算法过程记录

动态内存信息：
分区个数：5
各分区首址：0 50 190 340 530
各分区大小：130 70 140 80 20

1.首次适应算法（First Fit）

在这里插入图片描述

2.循环首次适应算法（Next Fit）
在这里插入图片描述

3.最佳适应算法（Best Fit）
在这里插入图片描述

4.最坏适应算法（Worst Fit）
在这里插入图片描述

四、算法的优劣比较

1.首次适应算法（First Fit）

优点：高址部分的大的空闲分区得到保留，为大作业的内存分配创造了条件；
缺点：
（1）每次都是优先利用低址部分的空闲分区，造成低址部分产生大量的外碎片。
（2）每次都是从低址部分查找，使得查找空闲分区的开销增大；

2.循环首次适应算法（Next Fit）

优点：
（1）使得空闲分区分布更加均匀；
（2）空闲分区的查找开销小；
缺点：高址部分的大空闲分区被分小，使得大作业进入无法分配内存；

3.最佳适应算法（Best Fit）

优点：第一次找到的空闲分区是大小最接近待分配内存作业大小的；
缺点:产生大量难以利用的外部碎片。

4.最坏适应算法（Worst Fit）

优点：效率高，分区查找方便；
缺点：当小作业把大空闲分区分小了，那么，大作业就找不到合适的空闲区。

五、代码实现

Partition.h

#pragma once
#include <iostream>
#include <fstream>
#include<string>
#include<vector>
#include<functional>
#include<cstdlib>
#include<map>
#include<set>
using namespace std;
typedef struct//分区
{
	static int PartitionNum;//分区数量 
	int m_PartitionId;//分区首地容量址
	int m_PartitionSize;//分区
	int m_BlockId;//空白分区首地址
}Partition;

typedef struct//进程控制块
{
	static int PCBNum;//进程数量
	string m_PidName;//进程名称
	int m_PidSize;//进程大小
}PCB;

void ReadData();//读入数据
void Display1();
void Display_Partition();
void Display();//输出分区完后各个分区的状态
void Display_PCB();//显示进程的状态
void FirstFit();//首次适应算法
void NextFit();//循环首次适应算法
void BestFit();//最佳适应算法
void WorstFit();//最坏适应算法

Partition.cpp

#include" Partition.h"

int Partition::PartitionNum = 0;
int PCB::PCBNum = 0;
Partition* partition;
PCB* pcb;
int MIN;


void ReadData()//读入数据
{
	ifstream readData;
	readData.open("data.txt");

	readData >> Partition::PartitionNum;//读入分区数量
	partition = new Partition[Partition::PartitionNum];//开空间

	for (int i = 0; i < Partition::PartitionNum; i++)//读入分区起始地址
	{
		readData >> partition[i].m_PartitionId;
		partition[i].m_BlockId = partition[i].m_PartitionId;
	}
	for (int i = 0; i < Partition::PartitionNum; i++)//读入分区大小
	{
		readData >> partition[i].m_PartitionSize;
	}

	//readData >> PCB::PCBNum;//读入进程数量
	//pcb = new PCB[PCB::PCBNum];

	//for (int i = 0; i < PCB::PCBNum; i++)//读入进程名称
	//{
	//	readData >> pcb[i].m_PidName;
	//}

	//for (int i = 0; i < PCB::PCBNum; i++)//读入进程大小
	//{
	//	readData >> pcb[i].m_PidSize;
	//}
	//readData.close();
}

void FirstFit()//首次适应算法
{
	bool flag = false;
	int i, j;
	string choose;
	ReadData();
	//cout << "输入MIN:";
	//cin >> MIN;
	//Display_PCB();
	do
	{
		Display_Partition();
		pcb = (PCB*)realloc(pcb, sizeof(PCB)*(PCB::PCBNum + 1));
		cout << "输入进程名称：";
		cin >> pcb[PCB::PCBNum - 1].m_PidName;
		cout << "输入进程大小:";
		cin >> pcb[PCB::PCBNum - 1].m_PidSize;

		i = PCB::PCBNum - 1;

		for (j = 0; j < Partition::PartitionNum; j++)
		{
			if (pcb[i].m_PidSize <= partition[j].m_PartitionSize)
			{
				partition[j].m_PartitionSize -= pcb[i].m_PidSize;
				partition[j].m_BlockId += partition[j].m_PartitionSize;
				if (partition[j].m_PartitionSize <= MIN)
				{
					partition[j].m_PartitionSize = 0;
				}
				flag = true;
				break;
			}
		}
		if (flag)
		{
			flag = false;
			cout << "进程" << pcb[i].m_PidName << "分配到分区" << partition[j].m_PartitionId << endl;
		}
		else
		{
			cout << "进程" << pcb[i].m_PidName << "分配失败！" << endl;
		}
		Display1();
		cout << "继续分配按Y" << endl;
		cin >> choose;

	} while (choose == "Y");
}
void NextFit()//循环首次适应算法
{
	int pos = 0;
	bool flag = false;
	int i, j;
	string choose;
	ReadData();
	//Display_PCB();
	/*cout << "输入MIN:";
	cin >> MIN;*/
	do
	{

		Display_Partition();
		pcb = (PCB*)realloc(pcb, sizeof(PCB)*(PCB::PCBNum+1));
		cout << "输入进程名称：";
		cin >> pcb[PCB::PCBNum - 1].m_PidName;
		cout << "输入进程大小:";
		cin >> pcb[PCB::PCBNum - 1].m_PidSize;
		i = PCB::PCBNum - 1;

		for (j = pos;; j++)
		{
			if (pos >= PCB::PCBNum)
			{
				pos = 0;
			}
			if (pcb[i].m_PidSize <= partition[j].m_PartitionSize)
			{
				partition[j].m_PartitionSize -= pcb[i].m_PidSize;
				partition[j].m_BlockId += partition[j].m_PartitionSize;
				if (partition[j].m_PartitionSize <= MIN)
				{
					partition[j].m_PartitionSize = 0;
				}
				flag = true;
				pos = j + 1;
				if (pos == PCB::PCBNum)
				{
					pos = 0;
				}
				break;
			}
		}
		if (flag)
		{
			flag = false;
			cout << "进程" << pcb[i].m_PidName << "分配到分区" << partition[j].m_PartitionId << endl;
		}
		else
		{
			cout << "进程" << pcb[i].m_PidName << "分配失败！" << endl;
		}
		Display1();
		cout << "继续分配按Y" << endl;
		cin >> choose;

	} while (choose == "Y");

}
void BestFit()//最佳适应算法
{
	int pos = 0;
	bool flag = false;
	int i, j;
	multimap<int, Partition*> m;
	multimap<int, Partition*>::iterator ip;
	string choose;
	ReadData();
	//Display_PCB();
	/*cout << "输入MIN:";
	cin >> MIN;*/
	do
	{
		Display_Partition();
		pcb = (PCB*)realloc(pcb, sizeof(PCB)*(PCB::PCBNum + 1));
		cout << "输入进程名称：";
		cin >> pcb[PCB::PCBNum - 1].m_PidName;
		cout << "输入进程大小:";
		cin >> pcb[PCB::PCBNum - 1].m_PidSize;
		i = PCB::PCBNum - 1;

		m.clear();
		for (j = 0; j < Partition::PartitionNum; j++)//按从小带大排序
		{
			m.insert(make_pair(partition[j].m_PartitionSize, partition + j));
		}

		for (ip = m.begin(); ip != m.end();)
		{
			if (pcb[i].m_PidSize <= ip->first)
			{
				ip->second->m_PartitionSize -= pcb[i].m_PidSize;
				ip->second->m_BlockId += ip->second->m_PartitionSize;
				/*if (ip->second->m_PartitionSize <= MIN)
				{
				ip->second->m_PartitionSize = 0;
				}*/
				flag = true;
				break;
			}
			else
			{
				ip++;
			}
		}
		if (flag)
		{
			flag = false;
			cout << "进程" << pcb[i].m_PidName << "分配到分区" << ip->second->m_PartitionId << endl;
		}
		else
		{
			cout << "进程" << pcb[i].m_PidName << "分配失败！" << endl;
		}
		Display();
		cout << "继续分配按Y" << endl;
		cin >> choose;

	} while (choose == "Y");
}
void WorstFit()//最坏适应算法
{
	int pos = 0;
	bool flag = false;
	int i, j;
	multimap<int, Partition*, greater<int>> m;
	multimap<int, Partition*>::iterator ip = m.begin();
	string choose;
	ReadData();
	//Display_PCB();
	/*cout << "输入MIN:";
	cin >> MIN;*/
	do
	{
		Display_Partition();
		pcb = (PCB*)realloc(pcb, sizeof(PCB)*(PCB::PCBNum + 1));
		cout << "输入进程名称：";
		cin >> pcb[PCB::PCBNum - 1].m_PidName;
		cout << "输入进程大小:";
		cin >> pcb[PCB::PCBNum - 1].m_PidSize;
		i = PCB::PCBNum - 1;

		m.clear();
		for (j = 0; j < Partition::PartitionNum; j++)//按从大到小排序
		{
			m.insert(make_pair(partition[j].m_PartitionSize, partition + j));
		}

		for (ip = m.begin(); ip != m.end();)
		{
			if (pcb[i].m_PidSize <= ip->first)
			{
				ip->second->m_PartitionSize -= pcb[i].m_PidSize;
				ip->second->m_BlockId += ip->second->m_PartitionSize;
				/*if (ip->second->m_PartitionSize <= MIN)
				{
				ip->second->m_PartitionSize = 0;
				}*/
				flag = true;
				break;
			}
			else
			{
				ip++;
			}
		}
		if (flag)
		{
			flag = false;
			cout << "进程" << pcb[i].m_PidName << "分配到分区" << ip->second->m_PartitionId << endl;
		}
		else
		{
			cout << "进程" << pcb[i].m_PidName << "分配失败！" << endl;
		}
		Display();
		cout << "继续分配按Y" << endl;
		cin >> choose;

	} while (choose == "Y");
}
void Display()
{
	int i;
	set<int> s;
	for (i = 0; i < Partition::PartitionNum; i++)
	{
		s.insert(partition[i].m_PartitionSize);
	}

	cout << "空白分区链:";
	for (auto& e : s)
	{
		cout << e << "->";
	}
	cout << "NULL";
	cout << endl;
}

void Display1()
{
	int i;
	map<int, Partition*> m;
	for (i = 0; i < Partition::PartitionNum; i++)
	{
		m.insert(make_pair(partition[i].m_PartitionId, partition + i));
	}

	cout << "空白分区链:";
	for (auto& e : m)
	{
		if (e.second->m_PartitionSize != 0)
		{
			cout << e.second->m_PartitionSize << "->";
		}
	}
	cout << "NULL";
	cout << endl;
}
void Display_Partition()
{
	cout << endl << "分区起始地址 ";
	for (int i = 0; i < Partition::PartitionNum; i++)
	{
		printf("%-d  ", partition[i].m_PartitionId);
	}
	cout << endl << "分区大小:   ";
	for (int i = 0; i < Partition::PartitionNum; i++)
	{

		printf("%-d  ", partition[i].m_PartitionSize);

	}
	cout << endl << endl;
}

void Display_PCB()
{
	cout << endl << "进程id:  ";
	for (int i = 0; i < PCB::PCBNum; i++)
	{
		printf("%3s  ", pcb[i].m_PidName.c_str());
	}
	cout << endl << "进程大小:";
	for (int i = 0; i < PCB::PCBNum; i++)
	{
		printf("%3d  ", pcb[i].m_PidSize);
	}
	cout << endl << endl;
}

Main.cpp

#include"Partition.h"

int main()
{
	int choose;
	while (1)
	{
		cout << "请选择实现的算法：" << endl;
		cout << "*****  1 - 首次适应算法     *****" << endl;
		cout << "*****  2 - 循环首次适应算法 *****" << endl;
		cout << "*****  3 - 最佳适应算法     *****" << endl;
		cout << "*****  4 - 最坏适应算法     *****" << endl;
		cout << "*****  0 - 结束             *****" << endl;
		cout << "输入你的选择 ： ";
		cin >> choose;
		switch (choose)
		{
			
			case 0:exit(0); break;
			case 1:FirstFit(); break;
			case 2:NextFit(); break;
			case 3:BestFit(); break;
			case 4:WorstFit(); break;
			default:cout << "请输入正确的序号：" << endl;
		}
	}
    system("pause");
    return 0;
}
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

算法

操作系统

动态分区分配算法(First Fit，Next Fit，Best Fit，Worst Fit) 的相关文章

  • Obsidian利用插件Remotely-save实现超低成本全平台云笔记

    Obsidian作为一个笔记软件 是目前最满足我需求的了 本地存储文件 Markdown格式作为基础 双链支持 以及好用的搜索等功能 基本实现了我对一款文字笔记软件的要求 但是Obsidian的收费价格确实不低 虽然软件本身的所有功能基本免

  • Visual Unit 简明教程

    载自 http www vckbase com index php wv 1270 VU1 0 简介 Visual Unit 简称VU 是新一代单元测试工具 功能强大 使用简单 完全可视化 不需编写测试代码 VU的测试结果使程序行为一目了然

  • UNIX系统被删文件的恢复策略

    与DOS Windows不同 UNIX文件被删除后很难恢复 这是由UNIX独特 的文件系统结构决定的 UNIX文件目录不像DOS Windows那样 文 件即使被删除之后仍保存有完整的文件名 文件长度 始簇号 即 文件占有的第一个磁盘块号

  • TTF、TOF、WOFF 和 WOFF2 的相关概念

    前言 在上一篇文章中 我引入了 TTF 格式的字体文件来解决各平台字体表现不统一的问题 但其实那不是最优解决方案 因为字体文件不止有 TTF 格式 常见的字体格式还有 OTF WOFF 和 WOFF2 等 今天 我来总结一下最常见字体格式的

  • Bootstarp学习教程（14） 其他相关组件（2）

    页面标题 简单的h1样式 可以适当地分出空间且分开页面中的章节 像其它组件一样 它可以使用h1的默认small元素 div class page header h1 Example page header h1 div

随机推荐

  • 【Web前端】彼岸の花——网上花店(网页制作)

    本篇博客我们来做一个好看又简单的前端案例 彼岸的花网页界面 这里是代码和网页素材 需要的自取 提取码 7777 https pan baidu com s 1PH0TCuLpapPlJnczDcGkig pwd 7777 at 166988

  • 面经获取

    分享下面文字和图片到朋友圈或者QQ空间 所有人可见 不能是小号 时间保留一天 或者发一个大于100人的群聊保留2分钟以上也行 但你如果发群里可能会被踢 提醒你一下 时间到了截图即可 面经整理不易 大家不要作弊啊 如果有父母啥的不能看 那么你

  • linux ssh出现Unable to negotiate with 192.168.1.1 port 22: no matching cipher found. Their offer......

    问题描述 linux ssh出现Unable to negotiate with 192 168 1 1 port 22 no matching cipher found Their offer aes128 cbc des cbc 解决办

  • VS2019安装配置QT插件（qt-vsaddin）

    1 介绍 Windows的Qt开发 一般采用Visual Studio安装Qt插件的方法开发Qt程序 毕竟VS开发工具还是比QtCreator开发工具强大 好用的多 本教程采用VS2019安装配置Qt插件 qt vsaddin msvc20

  • SpringMVC 从入门到精通系列 03 —— 常用注解

    文章目录 1 RequestParam 注解 2 RequestBody 注解 3 PathVariable 注解 4 RequestHeader 注解 了解 5 CookieValue 注解 了解 6 ModelAttribute 注解

  • Vuex常见面试题

    1 vuex是什么 怎么使用 哪种功能场景使用它 Vuex 是一个专为 Vue js 应用程序开发的状态管理插件 公共数据库 当项目遇到以下两种场景时 1 多个组件依赖于同一状态时 2 来自不同组件的行为需要变更同一状态 解决的问题 多个视

  • Python北理工_turtle绘画

    模块1 turtle库的使用 海龟绘图法 turtle setup 调整绘图窗体在电脑屏幕中的布局 空间坐标系 角度坐标系 代码示例 import turtle turtle left 45 turtle fd 150 turtle rig

  • C++11中std::condition_variable的使用

  • Java中如何创建一个枚举Enum类

    从jdk5出现了枚举类后 定义一些字典值可以使用枚举类型 枚举常用的方法是 values 对枚举中的常量值进行遍历 valueof String name 根据名称获取枚举类中定义的常量值 要求字符串跟枚举的常量名必须一致 获取枚举类中的常

  • Node创建应用

    github地址 https github com lily1010 Node learn tree master test 一 使用node的意义 使用 Node js 时 我们不仅仅 在实现一个JS应用 同时还实现了整个 HTTP 服务

  • 国际版阿里云/腾讯云免费：阿里云产品-弹性核算简介(依据官网转载)

    阿里云产品 弹性核算简介 依据官网转载 云服务器ECS Elastic Compute Service 是阿里云供给的功能杰出 安稳牢靠 弹性扩展的IaaS Infrastructure as a Service 等级云核算服务 实例 等同

  • Java复习-16-多态性

    多态性 在Java中对于多态性有两种实现的模式 方法的多态性 方法的重载 同一个方法名称可以根据传入的参数类型和个数的不同 进行不同的处理 方法的覆写 同一个方法可能根据使用子类的不同 由不同的实现 对象的多态性 父子实例之间的转换处理 有

  • 机器学习类比赛中经常用到的一些函数和知识点

    文章目录 豆瓣 清华源命令 pip升级命令 画图plot汉字显示不出 python控制台打印结果省略的问题 enumerate pandas描述数据基本分布情况 isin 判断值是否存在 某两个特征之间的关联性 np corrcoef fo

  • GLib学习

    Gstreamer 基础 学习博客 一 glib glib介绍 1 1 类型介绍 glib的类型定义在gtypes h文件中 关键定义如下 1 1 1 不规则类型 gboolean gpointer gconstpointer gchar

  • 品味树莓派：GPIO Zero库进阶使用

    文章目录 目的 进阶功能 Source Values模式 Device Source Tools 高级设备类库 异常 Internal Devices Pin Factory 总结 目的 GPIO Zero库在传统的GPIO使用基础上还提供

  • 性能测试简介

    性能测试是通过自动化的测试工具模拟多种正常 峰值以及异常负载条件来对系统的各项性能指标进行测试 负载测试和压力测试都属于性能测试 两者可以结合进行 通过负载测试 确定在各种工作负载下系统的性能 第三方测试目标是测试当负载逐渐增加时 系统各项

  • Dubbo笔记 ⑳ ：消费者的异步调用

    文章目录 一 前言 1 流程概述 二 关键类 1 DefaultFuture 1 1 DefaultFuture 的构造 1 2 DefaultFuture newFuture 1 3 DefaultFuture received 1 4

  • Windows上利用Zerotier配置moon无法连接

    问题描述 按照相关教程 1 2 配置好moon之后 需要在各客户端zerotier上配置 并连接此服务器 在Windows电脑中 用两种方法将机器连接上 moon 节点 方法一 在打开服务程序services msc 找到服务 ZeroTi

  • 内嵌Python import时undefined symbol错误及解决

    内嵌Python import时undefined symbol错误及解决 以下代码 include lt Python h gt include lt stdio h gt include lt stdlib h gt int main

  • 动态分区分配算法(First Fit，Next Fit，Best Fit，Worst Fit)

    一 动态分区分配算法的背景 为了能将用户程序装入内存 必须为它分配一定大小的内存空间 连续分配方式是最早出现的一种存储器分配方式 曾被广泛应用于上世纪60 80 年代的OS中 该分配万式为个用户程序分配 一个连续的内存空间 即程序中代码或数

热门标签