TLSF算法分析

TLSF算法分析注:本文的大部分内容摘录自论文《TLSF:aNewDynamicMemoryAllocatorforReal-TimeSystems》,可以通过“科学上网”访问如下链接阅读原文:http://www.gii.upv.es/tlsf/files/ecrts04_tlsf.pdf。什么是TLSFTLSF是TwoLevelSegregatedFitmemoryal

大家好,又见面了,我是你们的朋友全栈君。

注:本文的大部分内容摘录自论文《TLSF: a New Dynamic Memory Allocator for Real-Time Systems》,可以通过“科学上网”访问如下链接阅读原文:http://www.gii.upv.es/tlsf/files/ecrts04_tlsf.pdf。

什么是TLSF

TLSF是Two Level Segregated Fit memory allocator的缩写,是一种动态内存分配算法。名称中有两个关键词,Segregated Fit和Two Level。

首先我们来了解什么是Segregated Fit。在内存分配算法中,空闲内存块的管理是算法的核心。根据寻找空闲内存块的策略,可以将内存分配算法分为以下几种:

  • Sequential Fit:将所有的空闲内存块,放入到一个单向/双向链表中。这是最基础的管理策略。算法非常简单,但寻找空闲内存块的效率依赖于链表的大小。
  • Segregated Fit:将所有的空闲块,放入到一组链表中,每一个链表中只包含某一个大小范围的空闲块。例如最典型的dlmalloc算法。
  • Buddy System: Segregate Fit算法的变种,具有更好的切割和合并效率,又很多变种,如Binary Buddies,Fibonacci Buddies, Weighted Buddies等。通常这类算法的内部碎片化问题比较严重。
  • Indexed Fit:通过一些高阶的数据结构来索引(Index)空闲的内存块。例如基于平衡树的“Best Fit”算法。
  • Bitmap Fit: Indexed Fit算法的变种,通过一小段内存的位图来标记对应的内存是空闲的还是使用中。

所以TLSF是一种通过一组链表来管理不同大小内存块的内存分配算法。

为什么称为Two Level?

基本的Segregated Fit算法是使用一组链表,每个链表只包含特定长度范围来的空闲块的方式来管理空闲块的,这样链表数组的长度可能会很大。如下图,TLSF为了简化查找定位过程,使用了两层链表。第一层,将空闲内存块的大小根据2的幂进行分类,如(16、32、64…)。第二层链表在第一层的基础上,按照一定的间隔,线性分段。比如2的6次方这一段,分为4个小区间【64,80),【80,96),【96,112),【112,128).每一级的链表都有一个bitmap用于标记对应的链表中是否有内存块。比如第一级别bitmap的后4bit位0100,即2的6次方这个区间有空闲块。对应的第二级链表的bitmap位0010及【80,96)这个区间有空闲块,即下面的89 Byte。

TLSF算法分析

给定一个内存块的大小,确定在两级链表中的位置(f,s)的算法如下:

TLSF算法分析

其中2的SLI次幂表示第二级链表的区间大小,比如上图中,区间大小为16,即2的4次方。这样大小为460字节的空闲快在链表中的位置为f=8,s=12,如下图:

TLSF算法分析

TLSF适用环境

实时系统RTOS对内存分配算法有以下两个要求:

  • 内存分配/释放的执行时间可预期,可接受的。由于RTOS对指令的执行时间有严格要求,所以常常采用静态内存分配的方法,以获得一个可以预期的执行时间。
  • 内存分配算法的碎片化程度要低,这是由于RTOS往往长时间执行,碎片化程度高会导致内存分配失败。

TLSF算法的目标运行系统是:

  • 可信的执行环境,Trusted Environment,应用不会故意破坏数据或者窃取数据。
  • 有限的物理内存。
  • 没有物理MMU来支持虚拟内存。

为了在这样的环境下运行,TLSF算法使用了如下的策略:

  • Immediate coalescing,立即合并,当内存块被释放后,立即与相邻的空闲内存块合并,以获得一个更大的空闲块,插入到链表的相应位置。这样可以减少碎片化。
  • Splitting threshold,分割阈值,最小可分配的内存块大小为16字节,应用一般不会分配一些基本的数据结构,如int、char等。限定最小可分配大小为16字节,这样可以在空闲的内存块中存储一些管理信息。
  • Good-fit strategy,TLSF会尽可能的返回一个最小的、能够满足需求的内存块。
  • Same strategy for all block sizes,对于不同大小的内存请求,TLSF只有一个分配策略,实现相对简单,执行时间可以预期。相应的dlmalloc根据所请求的内存大小不同,有多达4种内存分配策略。
  • Memory is not cleaned-up,分配个应用的内存没有被请0.

TLSF的特点在于:

  • 可以预期的分配执行时间,无论对于多达的内存分配请求,TLSF可以在限定的时间内完成分配。
  • 碎片化程度低。

未完待续

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/147339.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 分布式锁的使用场景_分布式锁的三种实现的对比

    分布式锁的使用场景_分布式锁的三种实现的对比前言对于锁大家肯定不会陌生,比如synchronized关键字和ReentrantLock可重入锁,一般我们用其在多线程环境中控制对资源的并发访问。但是随着业务的发展,分布式的概念逐渐出现在我们系统中,我们在开发的过程中经常需要进行多个系统之间的交互,于是上面的加锁方法就会失去作用。于是在分布式锁就自然而然的诞生了,接下来我们来聊一聊分布式锁实现的几种方式。分布式锁的使用场景 效率性:使用分布式锁可以避免不同节点重复相同的工作。 正确性:分布式锁可以避免破坏正确性的发生,如

  • android 实现自己定义状态栏通知(Status Notification)

    android 实现自己定义状态栏通知(Status Notification)

  • servlet生命周期

    servlet生命周期servlet生命周期

  • FPS游戏:实现GDI方框透视「建议收藏」

    FPS游戏:实现GDI方框透视「建议收藏」FPS游戏可以说一直都比较热门,典型的代表有反恐精英,穿越火线,绝地求生等,基本上只要是FPS游戏都会有透视挂的存在,而透视挂还分为很多种类型,常见的有D3D透视,方框透视,还有一些比较高端的显卡透视

  • 华为Mate40/华为Mate40Pro忘记密码怎么解锁激活手机设备已锁定恢复出厂无法解锁账户ID屏幕锁解除刷机方法教程[通俗易懂]

    华为Mate40/华为Mate40Pro忘记密码怎么解锁激活手机设备已锁定恢复出厂无法解锁账户ID屏幕锁解除刷机方法教程[通俗易懂]今天带来一台用户华为Mate40Pro手机强制清除华为账号锁案例分享,这个台手机是用户公司手机,由于前使用者离职后未能退出手机的华为账号和锁屏密码,导致手机无法使用。自己通过简单的恢复出厂设置后,发现手机有华为账号锁无法激活手机,这才联系到刷机爱好者技术人员,给予远程强制刷机移除华为Mate40Pro的账号锁。在此提醒广大用户,登录的华为账号建议绑定经常使用的手机号码,防止无法找回密码从而到时手机无法使用。在刷机解锁过程中需要准备以下工具:链接:百度网盘请输入提取码提取码:8888–来

  • matlab 关闭axis的图,使用MATLAB中axis实现图形坐标控制[通俗易懂]

    matlab 关闭axis的图,使用MATLAB中axis实现图形坐标控制[通俗易懂]Matlab对图形风格的控制比较完备。一方面,在最通用的层面上,采用了一系列考虑周全的默认设置。另一方面,可用户根据需要去自己设置。坐标控制指令axis使用比较简单,用于控制坐标的可视,取向、取值范围和轴的高宽比等。代码实现程序如下:clearall;closeall;clc;t=0:2*pi/99:2*pi;x=1.5*cos(t);y=3.25*sin(t);subplot(2,3,…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号