webdancer's Blog

阅读《莱昂氏UNIX源代码分析》

malloc.c源代码:
/*
* Structure of the coremap and swapmap   %两类资源:主存(64B); 盘交换区(512B)。
* arrays. Consists of non-zero count            %coremap   swapmap 维护可用资源的列表。
* and base address of that many                 %资源类别都包含连续的单元(map)。 如此下面
* contiguous units.                                      %malloc函数可以连续的查找。
* (The coremap unit is 64 bytes,
* the swapmap unit is 512 bytes)
* The addresses are increasing and              %可用资源列表结束的标志就是map类型单元为0.
* the list is terminated with the
* first zero count.
*/
struct map
{
char *m_size;  //map结构的大小
char *m_addr; //map结构的地址
};
/* -------------------------
*/
/*
* Allocate size units from the given
* map. Return the base of the allocated
* space.
* Algorithm is first fit.
*/
malloc(mp, size)
struct map *mp;
{
register int a;
register struct map *bp;
for (bp = mp; bp->m_size; bp++) {  //bp->m_size等价于:bp->m_size>0; bp++:列表为连续的。
if (bp->m_size >= size) { //找到要用的区域,由于算法采用的为:first fit.
a = bp->m_addr;   //记录该区域的首单元地址,作为返回的地址。
bp->m_addr =+ size;//更改该区域的首单元地址 
if ((bp->m_size =- size) == 0)//减少长度,判断是否恰好适配,恰好适配时,资源列表资源数减少。
do {
bp++;
(bp-1)->m_addr = bp->m_addr;//后续元素下移。
} while((bp-1)->m_size = bp->m_size);  //判断(bp-1)->m_size是否为0
return(a);//返回该区域的地址
}
}
return(0);//返回0,没找到区域。
}
/*----------------------
*/

/*
* Free the previously allocated space aa
* of size units into the specified map.
* Sort aa into map and combine on
* one or both ends if possible.
*/
mfree(mp, size, aa)  //将资源返回给mp指定的资源图。
struct map *mp;
{
register struct map *bp;
register int t;
register int a;
a = aa;
for (bp = mp; bp->m_addr<=a && bp->m_size!=0; bp++);//为了寻找释放资源在资源图中的位置。
if (bp>mp && (bp-1)->m_addr+(bp-1)->m_size == a) {//寻到在它之前插入新元素的元素。是否合并
(bp-1)->m_size =+ size;
if (a+size == bp->m_addr) {//是否应该与下一元素合并
(bp-1)->m_size =+ bp->m_size;
while (bp->m_size) {//元素数减1,位置前移。
bp++;
(bp-1)->m_addr = bp->m_addr;
(bp-1)->m_size = bp->m_size;
}
}
} else {//不能并于列表中的前一元素。
if (a+size == bp->m_addr && bp->m_size) {//是否与后一元素合并
bp->m_addr =- size;
bp->m_size =+ size;
} else if(size) do {//既不能与前面的&&后面的合并,在列表中增加元素。逐一后移。
t = bp->m_addr;
bp->m_addr = a;
a = t;
t = bp->m_size;
bp->m_size = size;
bp++;
} while (size = t);
}
}
/*-----------------------
*/
/*

算法分析:

在《os 概念》中,内存的分配介绍了三种方法:连续,分页,分段。 UNIX v6 是基于pdp11,上面的内存分析显然是简单的连续分配,对pdp11不太了解,不知道为什么用此类方式。采用动态分配的方式,可能含有外部碎片。使用了first fit 算法。这个算法的明显特点(就目前我所知)是搜索的速度快,可快速找到。

malloc :算法就是在资源可用图中连续找到可用元素,采用first fit.

free :将该内存释放在指定的区域,需要仔细的考虑合并的问题。

疑惑:

对malloc函数的连续查找还是不太明白,资源分配图好像可以不连续呀?blush




Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee