嵌入式操作系统的内存管理算法

ittbank 2024-05-17 17:41


本文主要介绍内存的基本概念以及操作系统的内存管理算法。

1 内存的基本概念
内存是计算机系统中除了处理器以外最重要的资源,用于存储当前正在执行的程序和数据。内存是相对于CPU来说的,CPU可以直接寻址的存储空间叫做内存,CPU需要通过驱动才能访问的叫做外存。
2 ROM&RAM&Flash
内存一般采用半导体存储单元,分为只读存储器(ROM,Read Only Memory)、随机存储器(RAM,Random Access Memory)ROM一般只能读取不能写入,掉电后其中的数据也不会丢失。RAM既可以从中读取也可以写入,但是掉电后其中的数据会丢失。内存一般指的就是RAM。
ROM在嵌入式系统中一般用于存储BootLoader以及操作系统或者程序代码或者直接当硬盘使用。近年来闪存(Flash)已经全面代替了ROM在嵌入式系统中的地位,它结合了ROM和RAM的长处,不仅具备电子可擦除可编程的特性,而且断电也不会丢失数据,同时可以快速读取数据。
3 两类内存管理方式
内存管理模块管理系统的内存资源,它是操作系统的核心模块之一。主要包括内存的初始化、分配以及释放。
从分配内存是否连续,可以分为两大类。


  • 连续内存管理


为进程分配的内存空间是连续的,但这种分配方式容易形成内存碎片(碎片是难以利用的空闲内存,通常是小内存),降低内存利用率。连续内存管理主要分为单一连续内存管理和分区式内存管理两种。


  • 非连续内存管理


将进程分散到多个不连续的内存空间中,可以减少内存碎片,内存使用率更高。如果分配的基本单位是页,则称为分页内存管理;如果基本单位是段,则称为分段内存管理。
当前的操作系统,普遍采用非连续内存管理方式。不过因为分配粒度较大,对于内存较小的嵌入式系统,一般采用连续内存管理。本文主要对嵌入式系统中常用的连续内存管理的分区式内存管理进行介绍。
4 分区式内存管理
分区式内存管理分为固定分区和动态分区。


  • 固定分区
    事先就把内存划分为若干个固定大小的区域。分区大小既可以相等也可以不等。固定分区易于实现,但是会造成分区内碎片浪费,而且分区总数固定,限制了可以并发执行的进程数量。
  • 动态分区


根据进程的实际需要,动态地给进程分配所需内存。
5 动态分区内存管理
运作机制
动态分区管理一般采用空闲链表法,即基于一个双向链表来保存空闲分区。对于初始状态,整个内存块都会被作为一个大的空闲分区加入到空闲链表中。当进程申请内存时,将会从这个空闲链表中找到一个大小满足要求的空闲分区。如果分区大于所需内存,则从该分区中拆分出需求大小的内存交给进程,并将此拆分出的内存从空闲链表中移除,剩下的内存仍然是一个挂在空闲链表中的空闲分区。
数据结构
空闲链表法有多种数据结构实现,这里介绍一种较为简单的数据结构。每个空闲分区的数据结构中包含分区的大小,以及指向前一个分区和后一个分区的指针,这样就能将各个空闲分区链接成一个双向链表。
内存分配算法


  • First Fit(首次适应算法)


First Fit要求空闲分区链表以地址从小到大的顺序链接。分配内存时,从链表的第一个空闲分区开始查找,将最先能够满足要求的空闲分区分配给进程。


  • Next Fit(循环首次适应算法)


Next Fit由First Fit算法演变而来。分配内存时,从上一次刚分配过的空闲分区的下一个开始查找,直至找到能满足要求的空闲分区。查找时会采用循环查找的方式,即如果直到链表最后一个空闲分区都不能满足要求,则返回到第一个空闲分区开始查找。


  • Best Fit(最佳适应算法)


从所有空闲分区中找出能满足要求的、且大小最小的空闲分区。为了加快查找速度,Best Fit算法会把所有空闲分区按其容量从小到大的顺序链接起来,这样第一次找到的满足大小要求的内存必然是最小的空闲分区。


  • Worst Fit(最坏适应算法)


从所有空闲分区中找出能满足要求的、且大小最大的空闲分区。Worst Fit算法按其容量从大到小的顺序链接所有空闲分区。


  • Two LevelSegregated Fit(TLSF)


使用两层链表来管理空闲内存,将空闲分区大小进行分类,每一类用一个空闲链表表示,其中的空闲内存大小都在某个特定值或者某个范围内。这样存在多个空闲链表,所以又用一个索引链表来管理这些空闲链表,该表的每一项都对应一种空闲链表,并记录该类空闲链表的表头指针。
图中,第一层链表将空闲内存块的大小根据2的幂进行分类。第二层链表是具体的每一类空闲内存块按照一定的范围进行线性分段。比如25这一类,以23即8分为4个内存区间【25,25+8),【25+8,25+16),【25+16,25+24),【25+24,25+32);216这一类,以214分为4个小区间【216,216+214),【216+214,216+2*214),【216+2*214,216+3*214),【216+3*214,216+4*214)。同时为了快速检索到空闲块,每一层链表都有一个bitmap用于标记对应的链表中是否有空闲块,比如第一层bitmap后3位010,表示25这一类内存区间有空闲块。对应的第二层bitmap为0100表示【25+16,25+24)这个区间有空闲块,即下面的52Byte。


  • Buddysystems(伙伴算法)


Segregated Fit算法的变种,具有更好的内存拆分和回收合并效率。伙伴算法有很多种类,比如BinaryBuddies,Fibonacci Buddies等。Binary Buddies是最简单也是最流行的一种,将所有空闲分区根据分区的大小进行分类,每一类都是具有相同大小的空闲分区的集合,使用一个空闲双向链表表示。BinaryBuddies中所有的内存分区都是2的幂次方。
因为无论是已分配的或是空闲的分区,其大小均为 2 的幂次方,即使进程申请的内存小于分配给它的内存块,多余的内存也不会再拆分出来给其他进程使用,这样就容易造成内部碎片。
当进程申请一块大小为n的内存时的分配步骤为:
1、计算一个i值,使得2i-1
2、在空闲分区大小为2i的空闲链表中查找
3、如果找到空闲块,则分配给进程
4、如果2i的空闲分区已经耗尽,则在分区大小为2i+1的空闲链表中查找
5、如果存在2i+1的空闲分区,则将此空闲块分为相等的两个分区,这两分区就是一对伙伴,其中一块分配给进程,另一块挂到分区大小为2i的空闲链表中
6、如果2i+1的空闲分区还是不存在,则继续查找大小为2i+2的空闲分区。如果找到,需要进行两次拆分。第一次拆分为两块大小为2i+1的分区,一块分区挂到大小为2i+1的空闲链表中,另一块分区继续拆分为两块大小为2i的空闲分区,一块分配给进程,另一块挂到大小为2i的空闲链表中
7、如果2i+2的空闲分区也找不到,则继续查找2i+3,以此类推
在内存回收时,如果待回收的内存块与空闲链表中的一块内存互为伙伴,则将它们合并为一块更大的内存块,如果合并后的内存块在空闲链表中还有伙伴,则继续合并到不能合并为止,并将合并后的内存块挂到对应的空闲链表中。
下面的表格对上面6种算法的优缺点进行了比较:

ittbank 让电子库存因技术而改变的ITT模式电商平台。引领和适应市场,以共享经济理念的创客及工程师为核心、以免费开放用户生成的数据为基础,为其提供高性价比的应用解决方案和及时精准的供求信息,快速提高产品开发周期和生产直通率、提升电子器件的应用附加值。
评论
  •  光伏及击穿,都可视之为 复合的逆过程,但是,复合、光伏与击穿,不单是进程的方向相反,偏置状态也不一样,复合的工况,是正偏,光伏是零偏,击穿与漂移则是反偏,光伏的能源是外来的,而击穿消耗的是结区自身和电源的能量,漂移的载流子是 客席载流子,须借外延层才能引入,客席载流子 不受反偏PN结的空乏区阻碍,能漂不能漂,只取决于反偏PN结是否处于外延层的「射程」范围,而穿通的成因,则是因耗尽层的过度扩张,致使跟 端子、外延层或其他空乏区 碰触,当耗尽层融通,耐压 (反向阻断能力) 即告彻底丧失,
    MrCU204 2025-01-17 11:30 182浏览
  • 数字隔离芯片是一种实现电气隔离功能的集成电路,在工业自动化、汽车电子、光伏储能与电力通信等领域的电气系统中发挥着至关重要的作用。其不仅可令高、低压系统之间相互独立,提高低压系统的抗干扰能力,同时还可确保高、低压系统之间的安全交互,使系统稳定工作,并避免操作者遭受来自高压系统的电击伤害。典型数字隔离芯片的简化原理图值得一提的是,数字隔离芯片历经多年发展,其应用范围已十分广泛,凡涉及到在高、低压系统之间进行信号传输的场景中基本都需要应用到此种芯片。那么,电气工程师在进行电路设计时到底该如何评估选择一
    华普微HOPERF 2025-01-20 16:50 73浏览
  • 随着消费者对汽车驾乘体验的要求不断攀升,汽车照明系统作为确保道路安全、提升驾驶体验以及实现车辆与环境交互的重要组成,日益受到业界的高度重视。近日,2024 DVN(上海)国际汽车照明研讨会圆满落幕。作为照明与传感创新的全球领导者,艾迈斯欧司朗受邀参与主题演讲,并现场展示了其多项前沿技术。本届研讨会汇聚来自全球各地400余名汽车、照明、光源及Tier 2供应商的专业人士及专家共聚一堂。在研讨会第一环节中,艾迈斯欧司朗系统解决方案工程副总裁 Joachim Reill以深厚的专业素养,主持该环节多位
    艾迈斯欧司朗 2025-01-16 20:51 195浏览
  • 临近春节,各方社交及应酬也变得多起来了,甚至一月份就排满了各式约见。有的是关系好的专业朋友的周末“恳谈会”,基本是关于2025年经济预判的话题,以及如何稳定工作等话题;但更多的预约是来自几个客户老板及副总裁们的见面,他们为今年的经济预判与企业发展焦虑而来。在聊天过程中,我发现今年的聊天有个很有意思的“点”,挺多人尤其关心我到底是怎么成长成现在的多领域风格的,还能掌握一些经济趋势的分析能力,到底学过哪些专业、在企业管过哪些具体事情?单单就这个一个月内,我就重复了数次“为什么”,再辅以我上次写的:《
    牛言喵语 2025-01-22 17:10 41浏览
  •     IPC-2581是基于ODB++标准、结合PCB行业特点而指定的PCB加工文件规范。    IPC-2581旨在替代CAM350格式,成为PCB加工行业的新的工业规范。    有一些免费软件,可以查看(不可修改)IPC-2581数据文件。这些软件典型用途是工艺校核。    1. Vu2581        出品:Downstream     
    电子知识打边炉 2025-01-22 11:12 49浏览
  • 嘿,咱来聊聊RISC-V MCU技术哈。 这RISC-V MCU技术呢,简单来说就是基于一个叫RISC-V的指令集架构做出的微控制器技术。RISC-V这个啊,2010年的时候,是加州大学伯克利分校的研究团队弄出来的,目的就是想搞个新的、开放的指令集架构,能跟上现代计算的需要。到了2015年,专门成立了个RISC-V基金会,让这个架构更标准,也更好地推广开了。这几年啊,这个RISC-V的生态系统发展得可快了,好多公司和机构都加入了RISC-V International,还推出了不少RISC-V
    丙丁先生 2025-01-21 12:10 111浏览
  • 80,000人到访的国际大展上,艾迈斯欧司朗有哪些亮点?感未来,光无限。近日,在慕尼黑electronica 2024现场,ams OSRAM通过多款创新DEMO展示,以及数场前瞻洞察分享,全面展示自身融合传感器、发射器及集成电路技术,精准捕捉并呈现环境信息的卓越能力。同时,ams OSRAM通过展会期间与客户、用户等行业人士,以及媒体朋友的深度交流,向业界传达其以光电技术为笔、以创新为墨,书写智能未来的深度思考。electronica 2024electronica 2024构建了一个高度国际
    艾迈斯欧司朗 2025-01-16 20:45 423浏览
  •  万万没想到!科幻电影中的人形机器人,正在一步步走进我们人类的日常生活中来了。1月17日,乐聚将第100台全尺寸人形机器人交付北汽越野车,再次吹响了人形机器人疯狂进厂打工的号角。无独有尔,银河通用机器人作为一家成立不到两年时间的创业公司,在短短一年多时间内推出革命性的第一代产品Galbot G1,这是一款轮式、双臂、身体可折叠的人形机器人,得到了美团战投、经纬创投、IDG资本等众多投资方的认可。作为一家成立仅仅只有两年多时间的企业,智元机器人也把机器人从梦想带进了现实。2024年8月1
    刘旷 2025-01-21 11:15 390浏览
  • 本文介绍瑞芯微开发板/主板Android配置APK默认开启性能模式方法,开启性能模式后,APK的CPU使用优先级会有所提高。触觉智能RK3562开发板演示,搭载4核A53处理器,主频高达2.0GHz;内置独立1Tops算力NPU,可应用于物联网网关、平板电脑、智能家居、教育电子、工业显示与控制等行业。源码修改修改源码根目录下文件device/rockchip/rk3562/package_performance.xml并添加以下内容,注意"+"号为添加内容,"com.tencent.mm"为AP
    Industio_触觉智能 2025-01-17 14:09 164浏览
  • Ubuntu20.04默认情况下为root账号自动登录,本文介绍如何取消root账号自动登录,改为通过输入账号密码登录,使用触觉智能EVB3568鸿蒙开发板演示,搭载瑞芯微RK3568,四核A55处理器,主频2.0Ghz,1T算力NPU;支持OpenHarmony5.0及Linux、Android等操作系统,接口丰富,开发评估快人一步!添加新账号1、使用adduser命令来添加新用户,用户名以industio为例,系统会提示设置密码以及其他信息,您可以根据需要填写或跳过,命令如下:root@id
    Industio_触觉智能 2025-01-17 14:14 121浏览
  • 2024年是很平淡的一年,能保住饭碗就是万幸了,公司业绩不好,跳槽又不敢跳,还有一个原因就是老板对我们这些员工还是很好的,碍于人情也不能在公司困难时去雪上加霜。在工作其间遇到的大问题没有,小问题还是有不少,这里就举一两个来说一下。第一个就是,先看下下面的这个封装,你能猜出它的引脚间距是多少吗?这种排线座比较常规的是0.6mm间距(即排线是0.3mm间距)的,而这个规格也是我们用得最多的,所以我们按惯性思维来看的话,就会认为这个座子就是0.6mm间距的,这样往往就不会去细看规格书了,所以这次的运气
    wuliangu 2025-01-21 00:15 183浏览
  • 高速先生成员--黄刚这不马上就要过年了嘛,高速先生就不打算给大家上难度了,整一篇简单但很实用的文章给大伙瞧瞧好了。相信这个标题一出来,尤其对于PCB设计工程师来说,心就立马凉了半截。他们辛辛苦苦进行PCB的过孔设计,高速先生居然说设计多大的过孔他们不关心!另外估计这时候就跳出很多“挑刺”的粉丝了哈,因为翻看很多以往的文章,高速先生都表达了过孔孔径对高速性能的影响是很大的哦!咋滴,今天居然说孔径不关心了?别,别急哈,听高速先生在这篇文章中娓娓道来。首先还是要对各位设计工程师的设计表示肯定,毕竟像我
    一博科技 2025-01-21 16:17 100浏览
  • 日前,商务部等部门办公厅印发《手机、平板、智能手表(手环)购新补贴实施方案》明确,个人消费者购买手机、平板、智能手表(手环)3类数码产品(单件销售价格不超过6000元),可享受购新补贴。每人每类可补贴1件,每件补贴比例为减去生产、流通环节及移动运营商所有优惠后最终销售价格的15%,每件最高不超过500元。目前,京东已经做好了承接手机、平板等数码产品国补优惠的落地准备工作,未来随着各省市关于手机、平板等品类的国补开启,京东将第一时间率先上线,满足消费者的换新升级需求。为保障国补的真实有效发放,基于
    华尔街科技眼 2025-01-17 10:44 221浏览
  • 现在为止,我们已经完成了Purple Pi OH主板的串口调试和部分配件的连接,接下来,让我们趁热打铁,完成剩余配件的连接!注:配件连接前请断开主板所有供电,避免敏感电路损坏!1.1 耳机接口主板有一路OTMP 标准四节耳机座J6,具备进行音频输出及录音功能,接入耳机后声音将优先从耳机输出,如下图所示:1.21.2 相机接口MIPI CSI 接口如上图所示,支持OV5648 和OV8858 摄像头模组。接入摄像头模组后,使用系统相机软件打开相机拍照和录像,如下图所示:1.3 以太网接口主板有一路
    Industio_触觉智能 2025-01-20 11:04 150浏览
我要评论
0
点击右上角,分享到朋友圈 我知道啦
请使用浏览器分享功能 我知道啦