嵌入式操作系统内核原理和开发(最快、最优、最差内存分配算法)-1
上一篇 / 下一篇 2012-06-29 13:53:29 / 个人分类:杂谈
rWcxE,P4S J0 首先,为了灵活对这三种分配算法进行配置,我们定义了宏开关,需要哪个就把那个开关放开。暂时默认打开的算法的是最快分配算法。51Testing软件测试网0k!k*A*Yy;p$i
51Testing软件测试网!W&qH7QhO-OJ2s^F/h&|9S \;l-v0
#define MAX_SPEED_MALLOC 0 Mes*uu0#define MIN_SIZE_MALLOC 0 +g(A9w;^[/k;\K5b0#define MAX_SIZE_MALLOC 1 |
因为之前已经讨论过最快分配算法,所以这里着重讨论的最优分配算法和最差分配算法。又由于两者的差别极小,所以单独分析其中一种算法也行。就拿最优分配算法来说,为了寻找到最小的节点,我们需要对整个链表进行遍历,这个还是比较消耗时间的。
N*Wa UI3e4l,[7D0 51Testing软件测试网X };^CZ)X.M&K@2A,Jo.|:mHg0
51Testing软件测试网-|\W7d4[Q;k/\ while(pCur)51Testing软件测试网/?M/q-}&O&{1f pPre = pCur;51Testing软件测试网%sv+u
QC#x1tH)HU} |
6}3D bZ_7S'PQ0 寻找到pFind这个我们需要的节点之后,还需要从pFreeList中删除该节点。所以,我们需要进一步的判断和分析,51Testing软件测试网/o SF hu(X
51Testing软件测试网r s*L0`E_D51Testing软件测试网ri}hQV Y_8W
l8ZG~ZG0 if(NULL == pFind) pPre = find_previous_node_in_list(pFind, pFreeList);51Testing软件测试网-Mt Z*B1@/L y/h4sBW
m4s0 return pFind;51Testing软件测试网:|mR+c2y |
首先判断pFind前面有没有节点,如果没有表示pFreeList就是pFind,那么pFreeList需要自行向后退缩;当然如果当前的 pFind节点是有前节点的,那么只需要把前节点的next指针重新更改一下即可。当然,这里还对原来的查找节点函数作了一下修改,使之更合理更通用。
5E2fG.rd6tl0d1ES1@2O1V{j8[0
_D7I!C{0
!~'|$t5[M0/*************************************************51Testing软件测试网4DG!d0SPQsb $w!E(C
GlSQ0MNG_NODE* find_previous_node_in_list(MNG_NODE* pNode, MNG_NODE* pList)51Testing软件测试网*z^.k(QdC if(NULL == pFind) return pPre; |
51Testing软件测试网 T^&KFV7Wd1m
上面也只是说了个大概,具体的内容可以参见下面的源代码。既可以在VC上编译,也可以在GCC上面编译,都没有问题。当然,如果本地os没有编译器,可以选择网上在线编译,也是个不错的选择。
,u8}S:vh:G$Ch0 51Testing软件测试网+B%lF_wB6p2W51Testing软件测试网'{!?iMOJ6?&VS(t|
3q;\uS{0/*************************************************51Testing软件测试网9os5c\~1m:^;Ps.|
* malloc & free in link node algorithm
Ma:f_[/h0y3U0**************************************************/
8k#i&vuk0wj(Q v0#include <string.h>51Testing软件测试网C/gQ/_z0DYs#H0L
#include <malloc.h>
"L3h7n,ldV2h&Z0/*************************************************51Testing软件测试网F%s/l2B-o#Sos
* struct definition51Testing软件测试网Nf ArLJq
**************************************************/51Testing软件测试网lf8I
K8Z-sd
b5hw
typedef struct _MNG_NODE
V8|S3{kW*G0{51Testing软件测试网0n`6}%CJ7pBD3o'}
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#?9GT051Testing软件测试网9COo| V3Ba
f4f
/*************************************************
Tl Emw'_/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软件测试网G&]yH.Fw`9}51Testing软件测试网B+U:`U-B!e)V
/*************************************************
p1N gs}a\4J8}0* global variable declaration51Testing软件测试网8LwIM8WGB6X@1^Y
**************************************************/51Testing软件测试网+KP1m+UDJ
static void* pGlbData;51Testing软件测试网VQZO F0G/e3h
static MNG_NODE* pFreeList;51Testing软件测试网'qaS'W|w ad
static MNG_NODE* pAllocList;51Testing软件测试网&U