区块链技术博客
www.b2bchain.cn

TLSF算法(一)分配中的位图计算

这篇文章主要介绍了TLSF算法(一)分配中的位图计算的讲解,通过具体代码实例进行17568 讲解,并且分析了TLSF算法(一)分配中的位图计算的详细步骤与相关技巧,需要的朋友可以参考下https://www.b2bchain.cn/?p=17568

本文实例讲述了2、树莓派设置连接WiFi,开启VNC等等的讲解。分享给大家供大家参考文章查询地址https://www.b2bchain.cn/7039.html。具体如下:

TLSF算法(一)分配中的位图计算

  • 一、什么是TLSF算法
  • 二,f的确定
  • 三、s的确定
  • 四、实验结果

一、什么是TLSF算法

在嵌入式系统中,内存需要在分配和释放时有一个确定的相应时间,才能进一步分析其实时任务的可调度性。因此TLSF算法是一个十分适用嵌入式领域的动态内存分配算法。在关于TLSf算法的经典文章中《TLSF: a New Dynamic Memory Allocator for Real-Time Systems》详细介绍了TLSF算法相关知识。

TLSF算法使用隔离匹配机制来实现良好匹配策略。基本的隔离匹配机制使用一组空闲列表,每个数组都包含一定大小范围内的空闲块。为了加快访问空闲块以及访问管理大量的隔离列表(以减少碎片),列表数组已组织为两个级别数组。一级数组将空闲块划分为类是2的幂(16、32、64、128等);和第二级将每个第一级类别线性划分,划分的数量(简称第二级别索引数,2SLI)是用户可配置的参数。每个数组列表具有关联的位图,用于标记哪些列表是为空,哪些包含空闲块。每个块有关的信息都存储在块本身中。
TLSF算法(一)分配中的位图计算
在TLSf的结构中,最主要的算法是位的操作,本文重点分析有关位的操作的原理与代码。当系统需要分配一个指定大小为r的内存时,需要计算出相应的两级位图的值,其公式如下所示:
TLSF算法(一)分配中的位图计算
为了有一个直观的结果,我们假设SLI=4,即第二级索引将一级的内存块大小范围划分为24=16块,则一级索引f=8,二级索引s=12。
TLSF算法(一)分配中的位图计算

二,f的确定

很显然,f的值就是所需内存大小的二进制位的最高非0位的数。首先最简单可以考虑到的就是从低位遍历即可,不断的对r进行”>>”操作,只要r不为0,就不断执行,同时定义一个变量统计移位的次数。但是因为是嵌入式系统,当然不能采用遍历的方法,会导致内存分配的不确定性。
方法一:首先考虑折半查找的方式,32位的数字,折半对比5此即可求出f的值。代码参考如下:

方法一首先考虑折半查找的方式,32位的数字,折半对比5此即可求出f的值。代码参考如下:

int getF1(int r){ 	int f = 0; 	if(!r){ 		return 0; 	} 	if(r & 0xffff0000){ 		r >>= 16; 		f += 16; 		printf("first method:16n"); 	} 	if(r & 0xff00){ 		r >>= 8; 		f += 8; 		printf("first method:8n"); 	} 	if(r & 0xf0){ 		r >>= 4;  		f += 4; 		printf("first method:4n"); 	} 	if(r & 12){ 		r >>= 2;  		f += 2; 		printf("first method:2n"); 	} 	if(r & 2){ 		r >>= 1;  		f += 1; 		printf("first method:1n"); 	} 	return f; } 

方法二:方法一需要进行6次比较,消耗时间较旧,因此采用空间换时间的方式,一个有8个bit位的数,可以通过一个数组索引出来28=256个数最高的位是几,最后就可以通过查表快速得知最高的bit位数。索引数组的初始化如下:

int TLSF_Table[256];	 int i; int j = 0; int k = 0; TLSF_Table[0] = 0xffffffff;	 for(i=2;i<=256;i=i*2,k++){ 	for(;j<i;j++){ 		TLSF_Table[j]=k; 	} } 

此时,我们看到进行两次对比后,通过查表和移位运算就可以快速确定相应的f值了。

三、s的确定

从公式中可以知道s,和f,SLI都相关。当然如果先求出f,而SLI已知,自然可以通过计算得出s的值。
方法一,直接通过公式完成相应的计算即可:

int getS1(int r, int f){ 	return (r - (1<<f))>>(f-SLI); } 

方法一计算过程比较繁琐,我们先通过将公式进行简单的化简,再考虑程序的实现。公式化简如下所示:
TLSF算法(一)分配中的位图计算
此时减少了频繁的左移和右移,移动一次,再相减即可。最终减少了计算量。

int getS2(int r, int f){ 	return (r >> (f - SLI))- (1<<SLI) ; } 

四、实验结果

将上面几个计算函数实现有后,在main函数中添加测试数据,进行验证,整个程序代码如下。

#include <stdio.h>  static int TLSF_Table[256]; static int SLI = 4;  int getF1(int r){ 	int f = 0; 	if(!r){ 		return 0; 	} 	if(r & 0xffff0000){ 		r >>= 16; 		f += 16; 	} 	if(r & 0xff00){ 		r >>= 8; 		f += 8; 	} 	if(r & 0xf0){ 		r >>= 4;  		f += 4; 	} 	if(r & 12){ 		r >>= 2;  		f += 2; 	} 	if(r & 2){ 		r >>= 1;  		f += 1; 	} 	return f; }  int getF2(int r){ 	int  a; 	a = r <= 0xffff ? (r <= 0xff ? 0 : 8) : (r <= 0xffffff ? 16 : 24); 	return TLSF_Table[r >> a] + a; } 	 int getS1(int r, int f){ 	return (r - (1<<f))>>(f-SLI); }  int getS2(int r, int f){ 	return (r >> (f - SLI))- (1<<SLI) ; }  main(){ 	int i; 	int j = 0; 	int k = 0; 	TLSF_Table[0] = 0xffffffff;	 	for(i=2;i<=256;i=i*2,k++){ 		for(;j<i;j++){ 			TLSF_Table[j]=k; 		} 	} 	int a=460; 	int f1 = getF1(a); 	int f2 = getF2(a); 	printf("compute fn"); 	printf("first method get f:%dn", f1); 	printf("second method get f:%dn", f2); 	printf("compute sn"); 	printf("first method get s:%dn", getS1(a,f1)); 	printf("second method get s:%dn", getS2(a,f2)); } 

程序运行结果,如下。
TLSF算法(一)分配中的位图计算
针对内存需求r=460,验证结果符合预期。

本文转自互联网,侵权联系删除TLSF算法(一)分配中的位图计算

赞(0) 打赏
部分文章转自网络,侵权联系删除b2bchain区块链学习技术社区 » TLSF算法(一)分配中的位图计算
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

b2b链

联系我们联系我们