嵌入式操作系统内核原理和开发（最快、最优、最差内存分配算法）-1

上一篇 / 下一篇 2012-06-29 13:53:29 / 个人分类：杂谈

前面我们说到了基于链表的内存分配算法。但是之前我们也说过，其实内存分配一般有三个原则，最快、最优和最差。最快比较好理解，就是寻找到合适的节点就立即分配内存，我们在前面一篇博客采用的就是这个方法。最优呢，就是寻找可以满足当前内存分配的最小节点，这样不会有很大的浪费，但是有可能会产生碎片节点。最后一种就是最差分配算法，说是最差效果未必最差。因为在大的内存分配的时候至少不会很快产生内存碎片，对整个系统的稳定来说有可能是好事。所以这三种方法很难说哪一种好，哪一种不好，需要结合具体的应用场景客观进行分析。不过话说回来，内存碎片是无论如何都避免不了的。

rWcxE,P4S J0　　首先，为了灵活对这三种分配算法进行配置，我们定义了宏开关，需要哪个就把那个开关放开。暂时默认打开的算法的是最快分配算法。51Testing软件测试网0k!k*A*Yy;p$i

#define MAX_SPEED_MALLOC   0
#define MIN_SIZE_MALLOC    0
#define MAX_SIZE_MALLOC    1

　　因为之前已经讨论过最快分配算法，所以这里着重讨论的最优分配算法和最差分配算法。又由于两者的差别极小，所以单独分析其中一种算法也行。就拿最优分配算法来说，为了寻找到最小的节点，我们需要对整个链表进行遍历，这个还是比较消耗时间的。

    while(pCur)51Testing软件测试网/?M/q-}&O&{1f
    { 51Testing软件测试网)XG_G-p
        if(pCur->size > (size + sizeof(MNG_NODE)))
        {
            if(NULL == pFind || pFind->size > pCur->size)
Ve j'GV^0            {
;L,^P:f:r z0                pFind = pCur;
|%wD!w&vzx0            }
!k8B lC8Uxr3O0        }

        pPre = pCur;
        pCur = pCur->next;51Testing软件测试网Mw N:_a7?mD
    }

6}3D bZ_7S'PQ0　　寻找到pFind这个我们需要的节点之后，还需要从pFreeList中删除该节点。所以，我们需要进一步的判断和分析，51Testing软件测试网/o SFhu(X

l8ZG~ZG0 if(NULL == pFind)
5XJtt'WE0 return NULL;

    pPre = find_previous_node_in_list(pFind, pFreeList);51Testing软件测试网-Mt Z*B1@/L
    if(NULL == pPre)
        pFreeList = pFreeList->next;51Testing软件测试网.h Y1i7ww!P
    else51Testing软件测试网B:ya%y;p
        pPre->next = pFind->next;

y/h4sBW m4s0 return pFind;51Testing软件测试网:|mR+c2y

　　首先判断pFind前面有没有节点，如果没有表示pFreeList就是pFind，那么pFreeList需要自行向后退缩；当然如果当前的 pFind节点是有前节点的，那么只需要把前节点的next指针重新更改一下即可。当然，这里还对原来的查找节点函数作了一下修改，使之更合理更通用。

d1ES1@2O1V{j8[0

!~'|$t5[M0/*************************************************51Testing软件测试网4DG!d0SPQsb
* function: find previous node
SV,t2x'x3VkK0**************************************************/

$w!E(C GlSQ0MNG_NODE* find_previous_node_in_list(MNG_NODE* pNode, MNG_NODE* pList)51Testing软件测试网*z^.k(QdC
{
    MNG_NODE* pFind = pList;
    MNG_NODE* pPre = NULL;51Testing软件测试网? uw$Fu

    while(pFind && pFind != pNode)
5G(leygk,Lbd"d0    {51Testing软件测试网1r-x'EM[
        pPre = pFind;51Testing软件测试网2ul"l:r3@B{
        pFind = pFind->next;
dW'TT5}8H6K0    }

if(NULL == pFind)
^{AZQVN-Af0 return NULL;

return pPre;
yYcyDwZ;Vp%w z"K0}

　　上面也只是说了个大概，具体的内容可以参见下面的源代码。既可以在VC上编译，也可以在GCC上面编译，都没有问题。当然，如果本地os没有编译器，可以选择网上在线编译，也是个不错的选择。

3q;\uS{0/*************************************************
* malloc & free in link node algorithm
Ma:f_[/h0y3U0**************************************************/

8k#i&vuk0wj(Q v0#include <string.h>
#include <malloc.h>

"L3h7n,ldV2h&Z0/*************************************************
* struct definition51Testing软件测试网NfArLJq
**************************************************/

typedef struct _MNG_NODE
V8|S3{kW*G0{
struct _MNG_NODE* next;
Mji;zIX#R G2d0 unsigned int size;
'`ezSVc]0}MNG_NODE;51Testing软件测试网j%d I_y%ss'~

H1s#c'?l IO#?9GT0
/*************************************************
TlEmw'_/UU(o'd0* macro declaration
Y ~']'j_6@;A0**************************************************/51Testing软件测试网e1r,|'swj

#define MAX_SPEED_MALLOC   1
Y K6g9x z1L L E6h`t0#define MIN_SIZE_MALLOC    0
\%D7^od5m:?"s$]Cj0#define MAX_SIZE_MALLOC    0

q5umQ:O+X/kA0Q0#define MEM_BUFFER_LENGTH (0x1 << 24)51Testing软件测试网Ut*@V'ImUR

51Testing软件测试网B+U:`U-B!e)V
/*************************************************
p1N gs}a\4J8}0* global variable declaration
**************************************************/51Testing软件测试网+KP1m+UDJ

static void* pGlbData;51Testing软件测试网VQZO F0G/e3h
static MNG_NODE* pFreeList;51Testing软件测试网'qaS'W|w ad
static MNG_NODE* pAllocList;51Testing软件测试网&UA9C;JWF#i"U

A O`dF6H@0/*************************************************
2k2b}3C&}!v0* function declaration
w4ZgWS.k4]h0**************************************************/51Testing软件测试网.Hj){.[*L,?

4zvt `3x1A:W'Q.L8X6A0MNG_NODE* find_previous_node_in_list(MNG_NODE* pNode, MNG_NODE* pList);

6v]"_&ok0
_0\ e mp&]D'^0/*************************************************51Testing软件测试网)K]Sz:U^+x7B
* function: add node into headlist
Vs^+gmsY0**************************************************/51Testing软件测试网6h*Ns1k8I(AU

HNIGd7M-@\II0static void add_node_into_list_head(MNG_NODE* pNode, MNG_NODE** ppList)51Testing软件测试网7mQ4m"N]V
{51Testing软件测试网2jj(Xd6`F!S
pNode->next = *ppList;
o)N"QJ&E"e#v-P0 *ppList = pNode;
1c@ N7k{|s!T[t"Ge0}51Testing软件测试网6Om/b B@^l

wB;m @5vL0
1g`fX`R0#if MAX_SPEED_MALLOC
0Gn0`x6bH(fU0/*************************************************
$N*oP~.H-`d0* function: find best fit node in max_speed
**************************************************/51Testing软件测试网 ]{rR2]4y7V

static MNG_NODE* find_best_fit_node(unsigned int size)51Testing软件测试网?:u-[N T!W
{51Testing软件测试网%cP2?*My?mD
MNG_NODE* pFind = pFreeList;51Testing软件测试网['u0qU%W
MNG_NODE* pPre = pFind;

    while(pFind && pFind->size < (size + sizeof(MNG_NODE)))51Testing软件测试网g'{1B['}
    { 51Testing软件测试网 hlO.pE+ya
        pPre = pFind;
SDW8zavb r3m|"My0        pFind = pFind->next;51Testing软件测试网;qtzX}E%P
    }

v7[,G'ZRN1q_0 if(NULL == pFind)
return NULL;

if(pFreeList == pFind)51Testing软件测试网 `"vq$}Q4f
        pFreeList = pFreeList->next;
.\ `7pv7W#k4\.f0    else
        pPre->next = pFind->next;51Testing软件测试网:Q1C:}c P#mz'^

return pFind;
asuzvh0}
Z5GN_U&rF P0#endif

#if MIN_SIZE_MALLOC51Testing软件测试网(n`qmBxE.q
/*************************************************
s+G)nO'D^.u6e'K|0* function: find best fit node in min size
z#I%UJ!J8NzsQ0**************************************************/

MNG_NODE* find_best_fit_node(unsigned int size)
{ as(W#pZ?8l w0{
&Eni/X RF!k0 MNG_NODE* pCur = pFreeList;51Testing软件测试网}9ax@~r8M
MNG_NODE* pPre = pCur;
#L9p?!@1] i~ `0 MNG_NODE* pFind = NULL;

[%PI;mE0    while(pCur)51Testing软件测试网.Gaj@%o:o
    { 51Testing软件测试网?s {5ajbyg
  if(pCur->size > (size + sizeof(MNG_NODE)))
m"W&Nro6yHim0  {
Q/IHf[mR;l0      if(NULL == pFind || pFind->size > pCur->size)51Testing软件测试网b!|[&D2l4D
   {51Testing软件测试网T2Z,e.hn ?F
       pFind = pCur;
7Aca [a^`p%Mt0   }
/`fM"[9[b([0  }

        pPre = pCur;
"zMhW)JC[Ce0        pCur = pCur->next;
)]2Z6RT0MIn)X&g&s0    }

%p:V9i0o$F.S8S0 if(NULL == pFind)
pk3@G:g}0 return NULL;

pPre = find_previous_node_in_list(pFind, pFreeList);
u)h6Kl:h7E-x+u0    if(NULL == pPre)
Q)Y?zP B0        pFreeList = pFreeList->next;51Testing软件测试网 A~pN-[ G!@
    else
&nB'AL0Rd)l#x,?8V0        pPre->next = pFind->next;

return pFind;
}
$U,P_M(dh2C3Z0#endif

收藏举报

TAG:

查看全部评论

bob123654

不要让那些真正对你好的人，慢慢的从你的生活中消失，无论爱情还是友情，都需要用心经营。

嵌入式操作系统内核原理和开发（最快、最优、最差内存分配算法）-1

用户菜单

我的栏目

标题搜索

日历

我的存档

数据统计

RSS订阅