全部博文（573）
分类： LINUX
2016-10-12 17:46:03
对伙伴系统种的位图的作用没有搞的清楚
就是说：系统在确定一个块的伙伴块是否是空闲时，是在空闲链表种查找有无
伙伴块呢还是利用位图种的状态来判断，
总觉得是和位图有关，可是位图中的一位表示一对伙伴块的状态
又觉得好象信息不太够用。
当位图中的一位为0，表示两块都空或都闲
当位图中的一位为1，表示有一块为忙
哪位大侠能详细谈谈位图的动作哪？
到底是怎么异或的？
位图的某位对应于两个伙伴块，为1就表示其中一块忙，为0表示两块都闲。
所谓异或，是指刚开始两块都闲为0，后来其中一块用了异或一下得1，后来另一块也用
了异或一下得0，后来前面一块回收了异或一下得1，后来另一块也回收了异或一下得0，
这样（如果为1就不合并）就又可以和前面一块合并成一大块了。
位图的主要用途是在回收算法中指示是否可以和伙伴块合并，分配时只要搜索空闲链表
就足够了。当然，分配的同时还要对相应位异或一下了，这是为回收算法服务。
讲的太好了，一下清楚了许多，谢谢了。
我对分配时相应的位异或这个地方还有点晕，就是说对位图的位异或时
是只对该大小队列的位图进行呢？还是所有10条中可能用到该块的都进行处理呢？
比如说：4页这个位置，如果是1页大小的块，其伙伴块是第5页，如果是2页大小的块时
其伙伴块是6，7页组成的，如果是4页大小的块时，其伙伴块是以0页大头的块
那么当第4页（一页大小）回收时（或释放时），其一页大小队列的位图肯定是处理了
那么其它大小的位图是否变化呢？比方说第二条队列位图的第2位是不是也要异或呀？
总感觉不太连冠似的
就拿你的例子来说明吧。
对于回收算法：
1. 当回收序号为4的1页块时，先找到order为0的area，把该页面块加入到该area的空闲
链表中，然后判断其伙伴块（序号为5的1页块）的状态，读该area（不是其它area！ ）
的map的第2位（ 4>>(1+order) ）,假设伙伴块被占，则该位为0（回收4块前，4、5块
都忙），现异或一下得1，并不再向上合并。
2. 当回收序号为5的1页块时，同理，先找到order为0的area，把该页面块加入到该are
a的空闲链表中，然后判断其伙伴块（序号为4的1页块）的状态，读该area的map的第2位
（ 5>>(1+order) ）, 这时该位为1（4块已回收），现异或一下得0，并向上合并，把序
号为4的1页块和序号为5的1页块从该area的空闲链表中摘除，合并成序号为4的2页块，
并放到order为1的area的空闲链表中。同理，此时又要判断合并后的块的伙伴块（序号
为6的2页块）的状态，读该area（ order为1的area，不是其它！ ） 的map的第1位（
4>>(1+order) ）,假设伙伴块在此之前已被回收，则该位为1，现异或一下得0，并向上
合并，把序号为4的2页块和序号为6的2页块从order为1的area的空闲链表中摘除，合并
成序号为4的4页块，并放到order为2的area的空闲链表中。然后再判断其伙伴块状态，
如此反复。
本来还想再说一下分配算法的，发现已经这么多了，我想也应该能明白了。
多谢了，现在清楚了许多
看来：
1。通过异或后是否为0判断是否继续向上合并
2。初始状态位图为全0
3。每次无论分配还是回收，都只对相应大小的位图处理（在没有分裂或合并的情况）
而并不是同时处理全部10条队列的。
现在再来举例谈一谈分配算法。
假设在初始阶段，全是大小为2^9大小的块（ MAX_ORDER为10），序号依次为0, 512, 1
024等等，并且所有area的map位都为0（实际上操作系统代码要占一部分空间，但这里只
是举例），现在要分配一个2^3大小的页面块，有以下动作：
1. 从order为3的area的空闲链表开始搜索，没找到就向高一级area搜索，依次类推，按
照假设条件，会一直搜索到order为9的area，找到了序号为0的2^9页块。
2. 把序号为0的2^9页块从order为9的area的空闲链表中摘除并对该area的第0位（ 0>>
(1+9) ）异或一下得1。
3. 把序号为0的2^9页块拆分成两个序号分别为0和256的2^8页块，前者放入order为8的
area的空闲链表中，并对该area的第0位（ 0>>(1+8) ）异或一下得1。
4. 把序号为256的2^8页块拆分成两个序号分别为256和384的2^7页块，前者放入order为
7的area的空闲链表中，并对该area的第1位（ 256>>(1+7) ）异或一下得1。
5. 把序号为384的2^7页块拆分成两个序号分别为384和448的2^6页块，前者放入order为
6的area的空闲链表中，并对该area的第3位（ 384>>(1+6) ）异或一下得1。
6. 把序号为448的2^6页块拆分成两个序号分别为448和480的2^5页块，前者放入order为
5的area的空闲链表中，并对该area的第7位（ 448>>(1+5) ）异或一下得1。
7. 把序号为480的2^5页块拆分成两个序号分别为480和496的2^4页块，前者放入order为
4的area的空闲链表中，并对该area的第15位（ 480>>(1+4) ）异或一下得1。
8. 把序号为496的2^4页块拆分成两个序号分别为496和504的2^3页块，前者放入order为
3的area的空闲链表中，并对该area的第31位（ 496>>(1+3) ）异或一下得1。
9. 序号为504的2^3页块就是所求的块。
如果有兴趣可以分配和回收一起演算举例，我就不再赘述。
|
|
2.4版内核的页分配器引入了"页区"(zone)结构, 一个页区就是一大块连续的物理页面. Linux 2.4将整个
物理内存划分为3个页区, DMA页区(ZONE_DMA), 普通页区(ZONE_NORMAL)和高端页区(ZONE_HIGHMEM).
页区可以使页面分配更有目的性, 有利于减少内存碎片. 每个页区的页分配仍使用伙伴(buddy)算法.
伙伴算法将整个页区划分为以2为幂次的各级页块的集合, 相邻的同次页块称为伙伴, 一对伙伴可以合并
到更高次页面集合中去.
下面分析一下伙伴算法的页面释放过程.
; mm/page_alloc.c:
#define BAD_RANGE(zone,x) (((zone) != (x)->zone) || (((x)-mem_map) < (zone)->offset) || (((x)-mem_map) >= (zone)->offset+(zone)->size))
#define virt_to_page(kaddr) (mem_map + (__pa(kaddr) >> PAGE_SHIFT))
#define put_page_testzero(p) atomic_dec_and_test(&(p)->count)
void free_pages(unsigned long addr, unsigned long order)
{ order是页块尺寸指数, 即页块的尺寸有(2^order)页.
if (addr != 0)
__free_pages(virt_to_page(addr), order);
}
void __free_pages(struct page *page, unsigned long order)
{
if (!PageReserved(page) && put_page_testzero(page))
__free_pages_ok(page, order);
}
static void FASTCALL(__free_pages_ok (struct page *page, unsigned long order));
static void __free_pages_ok (struct page *page, unsigned long order)
{
unsigned long index, page_idx, mask, flags;
free_area_t *area;
struct page *base;
zone_t *zone;
if (page->buffers)
BUG();
if (page->mapping)
BUG();
if (!VALID_PAGE(page))
BUG();
if (PageSwapCache(page))
BUG();
if (PageLocked(page))
BUG();
if (PageDecrAfter(page))
BUG();
if (PageActive(page))
BUG();
if (PageInactiveDirty(page))
BUG();
if (PageInactiveClean(page))
BUG();
page->flags &= ~((1<<
page->age = PAGE_AGE_START;
zone = page->zone; 取page所在的页区
mask = (~0UL) << order; 求页面指数的掩码
base = mem_map + zone->offset; 求页区的起始页
page_idx = page - base; 求page在页区内的起始页号
if (page_idx & ~mask) 页号必须在页块尺寸边界上对齐
BUG();
index = page_idx >> (1 + order);
; 求页块在块位图中的索引, 每一索引位置代表相邻两个"伙伴"
area = zone->free_area + order; 取该指数页块的位图平面
spin_lock_irqsave(&zone->lock, flags);
zone->free_pages -= mask; 页区的自由页数加上将释放的页数(掩码值为负)
while (mask + (1 << (MAX_ORDER-1))) { 当mask所遮掩的位长为(MAX_ORDER-1)时,和恰好为零,即达到了最大块指数
struct page *buddy1, *buddy2;
if (area >= zone->free_area + MAX_ORDER) 如果超过了最高次平面
BUG();
if (!test_and_change_bit(index, area->map)) 测试并取反页块的索引位
/*
* the buddy page is still allocated.
*/
break; 如果原始位为0, 则说明该页块原来没有伙伴, 操作完成
/*
* Move the buddy up one level. 如果原始位为1, 则说明该页块存在一个伙伴
*/
buddy1 = base + (page_idx ^ -mask); 对页块号边界位取反,得到伙伴的起点
buddy2 = base + page_idx;
if (BAD_RANGE(zone,buddy1)) 伙伴有没有越过页区范围
BUG();
if (BAD_RANGE(zone,buddy2))
BUG();
memlist_del(&buddy1->list); 删除伙伴的自由链
mask <<= 1; 求更高次掩码
area++; 求更高次位图平面
index >>= 1; 求更高次索引号
page_idx &= mask; 求更高次页块的起始页号
}
memlist_add_head(&(base + page_idx)->list, &area->free_list); 将求得的高次页块加入该指数的自由链
spin_unlock_irqrestore(&zone->lock, flags);
/*
* We don't want to protect this variable from race conditions
* since it's nothing important, but we do want to make sure
* it never gets negative.
*/
if (memory_pressure > NR_CPUS)
memory_pressure--;
}
|
|
|
2.4版内核的页分配器引入了"页区"(zone)结构, 一个页区就是一大块连续的物理页面. Linux 2.4将整个
物理内存划分为3个页区, DMA页区(ZONE_DMA), 普通页区(ZONE_NORMAL)和高端页区(ZONE_HIGHMEM).
页区可以使页面分配更有目的性, 有利于减少内存碎片. 每个页区的页分配仍使用伙伴(buddy)算法.
伙伴算法将整个页区划分为以2为幂次的各级页块的集合, 相邻的同次页块称为伙伴, 一对伙伴可以合并
到更高次页面集合中去.
下面分析一下伙伴算法的页面释放过程.
; mm/page_alloc.c:
#define BAD_RANGE(zone,x) (((zone) != (x)->zone) || (((x)-mem_map) < (zone)->offset) || (((x)-mem_map) >= (zone)->offset+(zone)->size))
#define virt_to_page(kaddr) (mem_map + (__pa(kaddr) >> PAGE_SHIFT))
#define put_page_testzero(p) atomic_dec_and_test(&(p)->count)
void free_pages(unsigned long addr, unsigned long order)
{ order是页块尺寸指数, 即页块的尺寸有(2^order)页.
if (addr != 0)
__free_pages(virt_to_page(addr), order);
}
void __free_pages(struct page *page, unsigned long order)
{
if (!PageReserved(page) && put_page_testzero(page))
__free_pages_ok(page, order);
}
static void FASTCALL(__free_pages_ok (struct page *page, unsigned long order));
static void __free_pages_ok (struct page *page, unsigned long order)
{
unsigned long index, page_idx, mask, flags;
free_area_t *area;
struct page *base;
zone_t *zone;
if (page->buffers)
BUG();
if (page->mapping)
BUG();
if (!VALID_PAGE(page))
BUG();
if (PageSwapCache(page))
BUG();
if (PageLocked(page))
BUG();
if (PageDecrAfter(page))
BUG();
if (PageActive(page))
BUG();
if (PageInactiveDirty(page))
BUG();
if (PageInactiveClean(page))
BUG();
page->flags &= ~((1<<
page->age = PAGE_AGE_START;
zone = page->zone; 取page所在的页区
mask = (~0UL) << order; 求页面指数的掩码
base = mem_map + zone->offset; 求页区的起始页
page_idx = page - base; 求page在页区内的起始页号
if (page_idx & ~mask) 页号必须在页块尺寸边界上对齐
BUG();
index = page_idx >> (1 + order);
; 求页块在块位图中的索引, 每一索引位置代表相邻两个"伙伴"
area = zone->free_area + order; 取该指数页块的位图平面
spin_lock_irqsave(&zone->lock, flags);
zone->free_pages -= mask; 页区的自由页数加上将释放的页数(掩码值为负)
while (mask + (1 << (MAX_ORDER-1))) { 当mask所遮掩的位长为(MAX_ORDER-1)时,和恰好为零,即达到了最大块指数
struct page *buddy1, *buddy2;
if (area >= zone->free_area + MAX_ORDER) 如果超过了最高次平面
BUG();
if (!test_and_change_bit(index, area->map)) 测试并取反页块的索引位
/*
* the buddy page is still allocated.
*/
break; 如果原始位为0, 则说明该页块原来没有伙伴, 操作完成
/*
* Move the buddy up one level. 如果原始位为1, 则说明该页块存在一个伙伴
*/
buddy1 = base + (page_idx ^ -mask); 对页块号边界位取反,得到伙伴的起点
buddy2 = base + page_idx;
if (BAD_RANGE(zone,buddy1)) 伙伴有没有越过页区范围
BUG();
if (BAD_RANGE(zone,buddy2))
BUG();
memlist_del(&buddy1->list); 删除伙伴的自由链
mask <<= 1; 求更高次掩码
area++; 求更高次位图平面
index >>= 1; 求更高次索引号
page_idx &= mask; 求更高次页块的起始页号
}
memlist_add_head(&(base + page_idx)->list, &area->free_list); 将求得的高次页块加入该指数的自由链
spin_unlock_irqrestore(&zone->lock, flags);
/*
* We don't want to protect this variable from race conditions
* since it's nothing important, but we do want to make sure
* it never gets negative.
*/
if (memory_pressure > NR_CPUS)
memory_pressure--;
}
|
呵呵, 蓝色经典!
Space AllocBuddy(FreeList &avail, int n)
{
//avail[0..m]为可利用空间表, n为申请分配量, 若有不小于n的空闲块, //则分配相应的存储块, 并返回其首地址, 否则返回NULL for(k=0; k<=m && (avail[k].nodesize < n+1 || !avail[k].first); ++k);//查找满足分配要求的子表 if(k>m) return NULL;//分配失败, 返回NULL;
else {//可进行分配 pa = avail[k].first;//指向可分配子表的第一个节点 pre = pa->llink; suc = pa->rlink;//分配指向前驱和后继 if(pa == suc) avail[k].first = NULL;//分配后该子表变为空表 else {//从子表删除*pa节点 pre->rlink = suc; suc->llink = pre; avail[k].first = suc;
} } for(i = 1; avail[k-i].nodesize >= n+1; ++i) { pi = pa + pow(2, k-i); pi-> rlink = pi; pi ->llink = pi; pi -> tag = 0; pi -> kval = k-i; avail[k-i].first = pi; }//将剩余块插入相应子表 pa -> tag = 1; pa -> kval = k-(--i); return pa;
}
关于存储块回收算法, 书上没有现成的, 日后笑侃一定提供给大家, 呵呵, 今日工作繁忙, 精力不济, 要挂起了. 感谢大家的关注!
对系统中物理页面的请求十分频繁。例如当一个可执行映象被调入内存时，操作系统必须为其分配页面。当映象执行完毕和卸载时这些页面必须被释放。物理页面的另一个用途是存储页表这些核心数据结构。虚拟内存子系统中负责页面分配与回收的数据结构和机制可能用处最大。
系统中所有的物理页面用包含mem_map_t结构的链表mem_map来描叙，这些结构在系统启动时初始化。每个 mem_map_t描叙了一个物理页面。其中与内存管理相关的重要域如下：
count
记录使用此页面的用户个数。当这个页面在多个进程之间共享时，它的值大于1。 age 此域描叙页面的年龄，用于选择将适当的页面抛弃或者置换出内存时。 map_nr 记录本mem_map_t描叙的物理页面框号。页面分配代码使用free_area数组来寻找和释放页面，此机制负责整个缓冲管理。另外此代码与处理器使用的页面大小和物理分页机制无关。
free_area中的每个元素都包含页面块的信息。数组中第一个元素描叙1个页面，第二个表示2个页面大小的块而接下来表示4个页面大小的块，总之都是2的次幂倍大小。list域表示一个队列头，它包含指向mem_map数组中page数据结构的指针。所有的空闲页面都在此队列中。map域是指向某个特定页面尺寸的页面组分配情况位图的指针。当页面的第N块空闲时，位图的第N位被置位。
图free-area-figure画出了free_area结构。第一个元素有个自由页面（页面框号0），第二个元素有4个页面大小的2个自由块，前一个从页面框号4开始而后一个从页面框号56开始。
Linux使用Buddy算法来有效的分配与回收页面块。页面分配代码每次分配包含一个或者多个物理页面的内存块。页面以2的次幂的内存块来分配。这意味着它可以分配1个、2个和4个页面的块。只要系统中有足够的空闲页面来满足这个要求(nr_free_pages > min_free_page)，内存分配代码将在free_area中寻找一个与请求大小相同的空闲块。free_area中的每个元素保存着一个反映这样大小的已分配与空闲页面 的位图。例如，free_area数组中第二个元素指向一个反映大小为四个页面的内存块分配情况的内存映象。
分配算法首先搜寻满足请求大小的页面。它从free_area数据结构的list域着手沿链来搜索空闲页面。如果没有这样请求大小的空闲页面，则它搜索两倍于请求大小的内存块。这个过程一直将持续到free_area 被搜索完或找到满足要求的内存块为止。如果找到的页面块大于请求的块则对其进行分割以使其大小与请求块匹配。由于块大小都是2的次幂所以分割过程十分简单。空闲块被连进相应的队列而这个页面块被分配给调用者。
在图3.4中，当系统中有大小为两个页面块的请求发出时，第一个4页面大小的内存块（从页面框号4开始）将分成两个2页面大小的块。前一个，从页面框号4开始的，将分配出去返回给请求者，而后一个，从页面框号6开始，将被添加到free_area数组中表示两个页面大小的空闲块的元素1中。
将大的页面块打碎进行分配将增加系统中零碎空闲页面块的数目。页面回收代码在适当时机下要将这些页面结合起来形成单一大页面块。事实上页面块大小决定了页面重新组合的难易程度。
当页面块被释放时，代码将检查是否有相同大小的相邻或者buddy内存块存在。如果有，则将它们结合起来形成一个大小为原来两倍的新空闲块。每次结合完之后，代码还要检查是否可以继续合并成更大的页面。最佳情况是系统的空闲页面块将和允许分配的最大内存一样大。
在图3.4中，如果释放页面框号1，它将和空闲页面框号0结合作为大小为2个页面的空闲块排入free_area的第一个元素中。
映象执行时，可执行映象的内容将被调入进程虚拟地址空间中。可执行映象使用的共享库同样如此。然而可执行文件实际上并没有调入物理内存，而是仅仅连接到进程的虚拟内存。当程序的其他部分运行时引用到这部分时才把它们从磁盘上调入内存。将映象连接到进程虚拟地址空间的过程称为内存映射。
每个进程的虚拟内存用一个mm_struct来表示。它包含当前执行的映象（如BASH）以及指向vm_area_struct 的大量指针。每个vm_area_struct数据结构描叙了虚拟内存的起始与结束位置，进程对此内存区域的存取权限以及一组内存操作函数。这些函数都是Linux在操纵虚拟内存区域时必须用到的子程序。其中一个负责处理进程试图访问不在当前物理内存中的虚拟内存(通过页面失效)的情况。此函数叫nopage。它用在Linux试图将可执行映象的页面调入内存时。
可执行映象映射到进程虚拟地址时将产生一组相应的vm_area_struct数据结构。每个vm_area_struct数据结构表示可执行映象的一部分：可执行代码、初始化数据(变量)、未初始化数据等等。Linux支持许多标准的虚拟内存操作函数，创建vm_area_struct数据结构时有一组相应的虚拟内存操作函数与之对应
