程序员经验分享-hwhale

C++实现基于顺序搜索的动态分区分配算法

2023-05-16

目录

1.需求分析

2.代码实现

3.测试用例

4.总结与收获

1.需求分析

动态分区分配又称为可变分区分配，他是根据进程的实际需要，动态地为之分配内存空间。在实现动态分区分配时，将涉及到分区分配中所有的数据结构、分区算法和分区的分配与回收操作这三方面的问题。 在本实验中运用了四种分配算法，分别是首次适应算法，循环首次适应算法，最坏适应算法，最佳适应算法。

  1. 首次适应算法

FF算法要求空闲分区链以地址递增的次序链接。在分配内存时，从链首开始顺序查找，直到找到一个大小能满足要求的空闲分区为止。然后再按照作业的大小，从该分区划分出一块内存空间，分配给请求者，余下的空闲分区仍留在空闲链中。如果从链首直至链尾都不能找到一个能满足要求的分区，则表明系统中已经没有足够大的内存分配给该进程，内存分配失败，返回。

    2.循环首次适应算法

NF（next fit）算法在为进程分配内存空间时，不再是每次都从链首开始查找，而是从上次找到的空闲分区的下一个K线分区开始查找，直至找到一个能满足要求的空闲分区，从中划出一块与请求大小相等的内存框架分配给该作业。

3.最佳适应算法

BF（best fit）算法要求将所有的空闲分区按照其容量以从小到大的顺序形成一空闲分区链。这样第一次找到的能满足要求的空闲区是最佳的。所谓“最佳”是指每次为作业分配内存时，只是把能满足要求又是最小的空闲分区分配给作业。

4.最坏适应算法

WF（worst fit）算法在扫描整个空闲分区表或链表时，只是挑选一个最大的空闲区，从中分割一部分存储空间给作业使用以至于存储器中缺乏大的空闲分区。

2.代码实现

C++代码：

#include<iostream>
#include<vector>
#include <iomanip>
#include <algorithm>
using namespace std;

class Partion
{
private:
	int size;
	int startaddress;
	int endaddress;
	bool flag;//是否空闲(1表示空闲)
	int sort = 1;
public:
	Partion(int psize, int paddress = 0) :size(psize)
	{
		flag = 1;
	}
	operator int() const
	{
		if (sort == 1)
		{
			return size;
		}
		else
		{
			return startaddress;
		}
		
	}
	int& Size()
	{
		return size;
	}
	const int& Size()const
	{
		return size;
	}
	int& Startaddress()
	{
		return  startaddress;
	}
	const int& Startaddress()const
	{
		return  startaddress;
	}
	int& Endaddress()
	{
		return  endaddress;
	}
	const int& Endaddress()const
	{
		return  endaddress;
	}
	bool& Flag()
	{
		return  flag;
	}
	const bool& Flag()const
	{
		return  flag;
	}
		int& Tag()
		{
			return  sort;
		}
		const int& Tag()const
		{
			return  sort;
		}
};
class Manage
{
private:
	vector<Partion> PartionList;
public:
	void Init(Partion& val)
	{
		//列表中第一个元素存放地址空间的总大小，以后不做处理
		val.Startaddress() = 0;
		val.Endaddress() = val.Size() + val.Startaddress();
		PartionList.push_back(val);
		PartionList.push_back(val);
	}
	void RecySpace(int space)//回收空间
	{
		int length = PartionList.size();
		bool success = 0;
		for (int i = 1; i < length; i++)
		{
			if (PartionList[i].Size() == space)
			{
				PartionList[i].Flag() = 1;
				cout << "释放空间成功！" << endl;
				break;
			}
			if (i == length + 1)
			{
				cout << "释放空间失败！" << endl;
			}
		}
	}
	void Base_FFNF(Partion process,int i)
	{
		cout << "成功分配空间！" << endl;

		int size = PartionList[i].Endaddress() - process.Size() - PartionList[i].Startaddress();
		int end = PartionList[i].Endaddress();

		PartionList[i].Flag() = 0;
		PartionList[i].Size() = process.Size();
		PartionList[i].Endaddress() = PartionList[i].Size() + PartionList[i].Startaddress();

		Partion Changeprocess(size);
		PartionList.insert(PartionList.begin() + i + 1, Changeprocess);
		PartionList[i + 1].Startaddress() = PartionList[i].Endaddress();
		PartionList[i + 1].Endaddress() = end;

	}
	int NF(Partion process, int& next)
	{
		//当有进程要分配空间时，先看是否有足够的空闲分区
		int i = next;
		int length = PartionList.size();
		bool success = 0;//
		for (; i < length; )//跳过0 
		{
			if (i == 0)//对列中存放的是空间的初始大小，不做处理，所以要跳过
			{
				i++;
			}
			//有足够大的空闲分区
			if (process.Size() <= PartionList[i].Size() && PartionList[i].Flag())
			{
				success = 1;
				//要分配给进程分区
				cout << "成功分配空间！" << endl;
				Base_FFNF(process,i);
				break;
			}
			i = (i + 1) % length;
			if (i == next)
			{
				cout << "分配空间失败！" << endl;
				break;
			}
		}
		next = next + 1;//下次查找的空闲分区
		return next;
	}
	void FF(Partion process)
	{
		//当有进程要分配空间时，先看是否有足够的空闲分区
		int length = PartionList.size();
		bool success = 0;//
		for (int i = 1; i < length; i++)
		{
			//有足够大的空闲分区
			if (process.Size() <= PartionList[i].Size() && PartionList[i].Flag())
			{
				success = 1;
				//要分配给进程分区
				Base_FFNF(process, i);
				break;
			}
			if (i == length + 1)
			{
				cout << "分配空间失败！" << endl;
				break;
			}
		}
	}
	void BF(Partion process)
	{
		//按照空闲区大小从小到大排序
		sort(PartionList.begin() + 1, PartionList.end());
		FF(process);
	}
	void WF(Partion process)
	{
		//按照空闲区大小从大到小排序
		sort(PartionList.begin() + 1, PartionList.end(),greater<Partion>()); 
		FF(process);
	}
	void Print()
	{
		int length = PartionList.size();
		for (int i = 0; i < length; i++)
		{
			PartionList[i].Tag() = 2;
		}
		sort(PartionList.begin() + 1, PartionList.end());
		cout << "空间地址" << PartionList[0].Startaddress() << "----->" << PartionList[0].Endaddress() << endl;
		cout << setw(18) << "开始地址" << setw(9) << "大小" << setw(13) << "结束地址" << setw(13) << "分配状态" << endl;
		
		for (int i = 1; i < length; i++)
		{
			if (PartionList[i].Size() != 0)
			{
				cout << "第" << i << "个" << "分区：";
				cout << setw(2) << PartionList[i].Startaddress() << setw(12) << PartionList[i].Size()
					<< setw(13) << PartionList[i].Endaddress() << setw(13);
				if (PartionList[i].Flag())
				{
					cout << "空闲" << endl;
				}
				else
				{
					cout << "已分配" << endl;
				}
			}
		}

	}
	void Clear()
	{
		PartionList.clear();
	}
	void Menu()
	{
		cout << "1------首次适应算法------" << endl;
		cout << "2------循环首次适应-------" << endl;
		cout << "3------最佳适应算法--------" << endl;
		cout << "4------最坏适应算法--------" << endl;
		cout << "5------回收分区------" << endl;
	}
};
int main()
{
	Manage process;
	int next = 1;//记录循坏首次适应算法的空闲标记
	int size;
	int space;
	cout << "请输入分区块的总大小：";
	cin >> size;
	Partion init(size);
	process.Init(init);
	process.Menu();
	int choose = 0;
	char end = 'y';
	while ('y' == end || 'Y' == end)
	{
		fflush(stdin);
		
		cout << "请输入你的选择：";
		cin >> choose;
		if (choose < 1 || choose>5)
		{
			cout << "请重新输入！！！" << endl;
		}
		else if (choose == 5)
		{
			cout << "请输入释放空间的大小：";
			cin >> space;
			process.RecySpace(space);
			process.Print();
		}
		else
		{
			cout << "请输入分配分区的大小：";
			cin >> size;
			Partion obj1(size);
			switch (choose)
			{
			case 1:				
				process.FF(obj1);
				process.Print();
				break;
			case 2:
				process.NF(obj1, next);
				process.Print();
				break;
			case 3:
				process.BF(obj1);
				process.Print();
				break;
			case 4:
				process.WF(obj1);
				process.Print();
				break;
			default:
				cout << "请输入正确选项！！！" << endl;
				break;
			}
						cout << "是否继续选择算法(Y/y)：";
			fflush(stdin);
			cin >> end;
		}
	}
}

3.测试用例

 

    1. FF算法

分别给内存分配300K，100K，释放300K，分配150K的状态变化

      • 分配300K

分区号

起始地址

大小

状态

1

0

300

已分配

2

300

212

未分配

      • 分配100K

分区号

起始地址

大小

状态

1

0

300

已分配

2

300

100

已分配

3

400

121

未分配

      • 释放300K

分区号

起始地址

大小

状态

1

0

300

未分配

2

300

100

已分配

3

400

121

未分配

      • 分配150K

分区号

起始地址

大小

状态

1

0

150

已分配

2

150

150

空闲

3

300

100

已分配

4

400

121

未分配

  1. NF算法

分别给内存分配300K，100K，释放300K，分配150K的状态变化.

    • 分配300K

分区号

起始地址

大小

状态

1

0

300

已分配

2

300

212

空闲

 

 

 

 

    • 分配100K

分区号

起始地址

大小

状态

1

0

300

已分配

2

300

100

已分配

3

400

111

空闲

    • 释放300K

分区号

起始地址

大小

状态

1

0

300

空闲

2

300

100

已分配

3

400

111

空闲

    • 分配150K

分区号

起始地址

大小

状态

1

0

150

已分配

2

150

150

空闲

3

300

100

已分配

4

400

111

空闲

  1. BF算法

当系统中空闲分区如下表时，分别分配100K，30K大小的内存空间。

①未分配前状态：

区号

分区首地址

大小

状态

1

0

20

已分配

2

20

32

空闲

3

52

8

空闲

4

60

120

空闲

5

180

331

空闲

 

 

 

 

 

 

 

 

      1.  
      2.  
      3.  
    2. 分配100K的分区状态表

区号

起始地址

大小

状态

1

0

20

已分配

2

20

32

空闲

3

52

8

空闲

4

60

100

已分配

5

160

20

空闲

6

180

331

空闲

    • 分配30K的分区状态表

区号

起始地址

大小

状态

1

0

20

已分配

2

20

30

已分配

3

50

2

空闲

4

52

8

空闲

5

60

100

已分配

6

160

20

空闲

7

180

331

空闲

 

4.总结与收获

 FF算法保留了高地址的大空闲块，但是也会增加查找分区时的开销，NF算法中设置起始查询指针是十分关键的，他减少了查找空闲分区的开销，但是也会造成大的空闲分区缺乏的情况，BF算法是按照存储区空闲区从小到大进行排序的，在存储器中留下了许多难以利用的碎片，而WF算法正好相反，是按照存储器空闲区从大到小的顺序来排列的，效率很高。

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

C++实现基于顺序搜索的动态分区分配算法 的相关文章

  • jeston nano安装Ubuntu镜像时启动遇到问题

    A start job is running for End user configuration after initial OEM installation 开始我跑了一下午 43 一晚上 xff0c 都没成功 xff0c 第二天 xf

  • cmake 常用变量、常用环境变量、常用语法总结

    一 cmake 变量引用的方式 前面我们已经提到了 使用 进行变量的引用 在 IF 等语句中 是直接使用变量名而不通过 取值 二 cmake 自定义变量的方式 主要有隐式定义和显式定义两种 隐式定义的例子 xff1a PROJECT 指令

  • Java基础篇：Iterator迭代器

    一 什么是Iterator xff1a 迭代器 Iterator 是一个对象 xff0c 它的工作是遍历并目标序列中的对象 xff0c 它提供了一种访问一个容器 container 对象中的各个元素的方法 xff0c 把访问逻辑从不同类型的

  • 2022-2-19 ros环境变量

    学习时间及标题 xff1a 2022 2 19 ros环境变量 学习内容 xff1a 1 添加环境变量 xff1a source span class token operator span span class token operato

  • EGO-Planner: An ESDF-free Gradient-based Local Planner for Quadrotors（论文学习）

    EGO规划器 xff1a 一种基于ESDF自由梯度的四转子局部规划器 摘要 ESDF地图被广泛运用在局部地图的梯度方向和大小估计之中 xff0c 但是由于我们在进行轨迹优化的过程中 xff0c 只用到了ESDF地图中很小的一部分 xff0c

  • cmake ＂undefined reference to＂

    main函数在调用其他 c或 cpp文件的函数时 xff0c 有以下几种情况 函数名写错 没有将其他 c或 cpp文件链接到main o xff0c 导致main函数在执行时找不到需要调用的函数 的解决方法 修改CMakeLists txt

  • STM32串口详解

    实验一 xff1a 简单的利用串口接收中断回调函数实现数据的返回 关于串口调试助手 xff0c 还应知道 xff1a 发送英文字符需要用一个字符即8位 xff0c 发送汉字需要两个字符即16位 xff0c 如上图 xff0c 发送汉字 姜

  • RLException: [xx.launch] is neither a launch file in package [x] nor is [x] a launch file name的解决方法

    ROS学习过程中 xff0c 遇到问题 xff1a RLException xx launch is neither a launch file in package x nor is x a launch file name 出现的问题

  • numpy 中 shape 与 size 属性

    因为需要生成一个和现有矩阵大小相等的矩阵 xff0c 故查找了相关资料 span class token operator gt gt span span class token operator gt span span class to

  • Ubtuntu+C语言实现网络通信附源代码

    下面这个案例是我用C在ubtuntu上面写的网络编程案例 2 网络编程 xff08 1 xff09 OSI七层模型理想化 应用层 xff1a app xff0c 应用程序 表示层 xff1a 对数据进行加工 会话层 xff1a 建立会话 x

  • Jetson Nano的GPIO口学习

    1 配置GPIO库 https github com NVIDIA jetson gpio 1 安装pip工具 sudo apt get update sudo apt get install python3 pip sudo apt ge

  • 22.11.22 TCP与UDP 客户端与服务器 协议搭建

    ubuntu 64 ubuntu yuyu yu 11 cat Tcp Cli c 客户端 include lt stdio h gt include lt sys types h gt include lt sys socket h gt

  • cmake交叉编译配置

    cmake交叉编译配置 很多时候 xff0c 我们在开发的时候是面对嵌入式平台 xff0c 因此由于资源的限制需要用到相关的交叉编译 即在你host宿主机上要生成target目标机的程序 里面牵扯到相关头文件的切换和编译器的选择以及环境变量

  • OS——gcc、g++、gdb、vim、vs code的基本使用

    文章目录 g 43 43 的使用gdb的使用vim的使用vscode的使用vs code的安装vs code中C 43 43 的编译运行配置 如果想要学习如何在CentOS 7中安装配置gcc g 43 43 gdb zhs和oh my z

  • make和cmake

    编程人员已经使用CMake和Make很长一段时间了 当你加入一家大公司或者开始在一个具有大量代码的工程上开展工作时 xff0c 你需要注意所有的构建 你需要看到处跳转的 CMakeLists txt 文件 你应该会在终端使用 cmake 和

  • ubuntu自带python与anaconda python环境的切换

    ubuntu的python可分为三大类 xff1a 1 ubuntu自带的python环境 一般安装在 usr bin 中python2和python3可以共存 2 anaconda自带的base环境 3 在anaconda中创建的虚拟py

  • 详细介绍如何在ubuntu20.04中安装ROS系统，以及安装过程中出现的常见错误的解决方法，填坑！！！

    本篇文章写于2020 10 xff0c 经过很多小伙伴的验证 xff0c 文章所介绍的步骤是可以正常完成安装的 xff0c 现在是2021 10 xff0c 经过近期的探索 xff0c 我将安装步骤进行了进一步的优化 xff0c 使安装变得

  • VScode进行python开发出现 No module named “XXX“的解决方法

    VScode进行python开发出现 No module named 34 XXX 34 的解决方法 最近从pycharm转向vscode的时候 xff0c 遇到了如下问题 span class token keyword import s

  • CM3寄存器简介

    Cortex M3基础 寄存器组 通用目的寄存器组R0 R7 也被称为低组寄存器 xff0c 所有指令都能访问字长32位 通用目的寄存器组R8 R12 高组寄存器 32位寄存器 复位后的初始值不可预料 堆栈指针R13 CM3中共有两个堆栈指

  • 基于亚博K210开发板的学习之旅（一）

    本文参考亚博智能官方K210开源课程 五月份购买了亚博的K210开发板 xff0c 但由于课程压力就搁置了 xff0c 最近暑假得空又恰逢电赛清单里有这个 芯片 xff0c 就抽空学习一下 xff0c 特写下这些 xff0c 以作记录 按照

随机推荐

  • STM32标准库通用软件模拟IIC

    STM32标准库通用软件模拟IIC 继上次通用可移植的矩阵键盘之后 xff0c 便继续寻找着下一个能够拿来只需改改引脚就可以使用的通用方案 恰好最近在研究PCA9685 xff0c 这是一片能够产生最多十六路PWM信号的芯片 xff0c 通

  • STM32F103控制PCA9685产生16路PWM波控制SG90舵机

    STM32控制PCA9685产生16路PWM波控制SG90舵机 如果你能点开这篇文章 xff0c 说明你已经知道PCA9685是多么强大 xff0c NXP公司原本做这片芯片是为了提供给LED使用 xff0c 在其官方文档里也能看到所有PW

  • 从源代码来看HAL库函数（一） HAL基础函数

    从源代码来看HAL库函数 xff08 一 xff09 HAL基础函数 全局变量 IO uint32 t uwtick 这个变量充当了一个运行时长计数的作用 xff0c 每发生一次SysTick中断就会加一 xff0c 直至溢出 xff0c

  • 使用TCP+串口与板子进行网络通信

    最近做了一个嵌入式的project xff0c 大概要求就是做一个client端 xff0c 一个sensor端 xff0c 两者通过TCP UDP进行通信 xff0c 然后在client端输入不同的命令sensor需做出不同的处理 xff

  • 毕业论文格式（图片题注引用，表格，公式格式）

    本科毕业论文差不多写完了 xff0c 记录一下一些格式 xff0c 以后写作可能会用到 xff0c 就可以翻起来看看 首先 xff0c 如果可以找到一篇格式符合要求的word文档的话 xff0c 最简单的方法就是在这个文档的基础上进行内容的

  • 图像处理——相位恢复（GS,TIE,改进型角谱迭代法）（已更新代码）

    利用GS xff0c TIE xff0c 改进型角谱迭代算法进行相位恢复 角谱传播理论 角谱传播理论可以翻阅傅里叶光学的书 xff0c 就能找到定量分析的计算公式 xff0c 可以分析某个平面的角谱垂直传播到另外一个平面的角谱 xff0c

  • 串口应用：遵循uart协议，发送多个字节的数据（状态机）

    上一节中 xff0c 我们遵循uart协议 xff0c 它发送一次只能发送6 7 8位数据 xff0c 我们不能随意更改位数 xff08 虽然在代码上可行 xff09 xff0c 不然就不遵循uart协议了 xff0c 会造成接收端无法接收

  • 数码管动态显示Verilog实现（参考小梅哥教程）(视觉暂留)

    一个数码管有八个引脚 xff0c 控制八段二极管的亮灭 xff0c 用以显示需要的数字 当有N个数码管时 xff0c 一个一个控制的话需要N x 8 个引脚 xff0c 消耗资源较多 因此可以利用动态显示的方案通过人眼的视觉暂留特性达到静态

  • 彻底理解DDS（信号发生器）的fpga实现（verilog设计代码）

    DDS xff08 Direct Digital Synthesis xff09 是一种把一系列数字信号通过D A转换器转换成模拟信号的数字合成技术 它有查表法和计算法两种基本合成方法 在这里主要记录DDS查表法的fpga实现 查表法 xf

  • HDMI/DVI

    一 基础知识 1 历史 早期在FPGA芯片上实现HDMI控制显示是使用HDMI发送芯片 xff0c eg xff1a ADV7513 sil9022 xff0c CH7301等 用之前VGA控制中输出的RGB信号 行场同步信号和使能信号输入

  • HDMI/DVI____TMDS编码

    一 编码步骤 xff1a 基本方法 xff1a 取第一位数据为初值 xff0c 接下来输入的每一位与前一导出的位 xff08 根据判断条件 xff09 进行异或XOR或者同或XNOR xff08 最小化传输 xff0c 减少0 1翻转 xf

  • HDMI/DVI____串行发送器

    一 功能 xff1a 把10bit数据转化为串行数据在一个时钟周期全部输出 xff08 先输出高位 xff0c 再输出低位 xff09 二 框图 二 思路 对于TMDS编码器 xff0c 在每一个输入时钟周期 xff0c 输入一次数据到TM

  • keil添加新文件.c.h

    文章目录 添加文件到组中1 双击组名称2 点击快捷键 添加头文件路径 h1 点击魔术棒快捷键2 头文件加 添加文件到组中 1 双击组名称 双击组名称 xff0c 打开弹窗 xff0c 然后选择相应的组中的新文件 xff0c 在点击ADD 2

  • QT常用控件（二）——自定义控件封装

    引言 Qt已经提供了很多的基础控件供开发使用 xff0c 而Qt原生的控件有时候并不能满足我们的需求 xff0c 特别是在工业的运用上 xff0c 比如我们需要一个日期时间的选择器 xff0c Qt虽然已经提供了原生的QDateTime控件

  • STM32之串口通信USART模块学习(1)

    一 通信接口 通信的目的 xff1a 将一个设备的数据传送到另一个设备 xff0c 扩展硬件系统通信协议 xff1a 制定通信的规则 xff0c 通信双方按照协议规则进行数据收发 单端信号通信的双方必须要共地 xff0c 因为都是对GND的

  • 2019电赛总结（一）

    2019电赛总结 xff08 一 xff09 文章目录 2019电赛总结 xff08 一 xff09 4 那之前5 电赛初期6 电赛中期7 电赛强化练习8 电赛预热阶段8月初9 那以后 4 那之前 2019电赛总结 序 xff09 5 电赛

  • 统计从键盘输入的一行字符中小写字母，大写字母，数字字符和其它字符的个数。

    统计从键盘输入的一行字符中小写字母 xff0c 大写字母 xff0c 数字字符和其它字符的个数 C语言实现 vs 2019 span class token macro property span class token directive

  • c语言求1~10的阶乘和

    求1 43 2 43 3 43 43 10 的和 span class token macro property span class token directive keyword include span span class toke

  • C和Cpp区别

    1 输入 xff0c 输出不同 xff08 out xff0c put xff09 c语言 xff1a include lt stdio h gt scanf 34 d 34 amp a printf 34 a 61 d n 34 a cp

  • C++实现基于顺序搜索的动态分区分配算法

    目录 1 需求分析 2 代码实现 3 测试用例 4 总结与收获 1 需求分析 动态分区分配又称为可变分区分配 xff0c 他是根据进程的实际需要 xff0c 动态地为之分配内存空间 在实现动态分区分配时 xff0c 将涉及到分区分配中所有的

热门标签