阅读《莱昂氏UNIX源代码分析》 - webdancer's Blog

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

webdancer posted @ 2010年9月12日 07:33 in 工具 with tags UNIX 源码 , 2449 阅读

1	`<span style="font-size:16px;"><span style="font-family:verdana,geneva,sans-serif;"><span` `class="Apple-style-span"` `style="white-space: normal;">malloc.c源代码：</span></span></span>`

<span style="font-size:16px;"><span style="font-family:verdana,geneva,sans-serif;">/*
* 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);
}
}
/*-----------------------
*/
/*</span></span>

算法分析：

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

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

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

疑惑：

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