Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1072363
  • 博文数量: 165
  • 博客积分: 3900
  • 博客等级: 中校
  • 技术积分: 1887
  • 用 户 组: 普通用户
  • 注册时间: 2007-04-06 15:15
文章分类

全部博文(165)

文章存档

2020年(3)

2019年(8)

2017年(2)

2016年(8)

2015年(14)

2013年(15)

2012年(32)

2011年(11)

2010年(14)

2009年(7)

2008年(20)

2007年(31)

分类: LINUX

2013-08-23 14:15:32

在2.6.24之前的内核版本中,free_area结构中只有一个free_list数组,而从2.6.24开始,free_area结构中存有MIGRATE_TYPES个free_list,这些数组是根据页框的移动性来划分的,为什么要进行这样的划分呢?实际上也是为了减少碎片而提出的,我们考虑下面的情况:


图中一共有32个页,只分配出了4个页框,但是能够分配的最大连续内存也只有8个页框(因为伙伴系统分配出去的内存必须是2的整数次幂个页框),内核解决这种问题的办法就是将不同类型的页进行分组。分配出去的页面可分为三种类型:
 
不可移动页(Non-movable pages):这类页在内存当中有固定的位置,不能移动。内核的核心分配的内存大多属于这种类型
可回收页(Reclaimable pages):这类页不能直接移动,但可以删除,其内容页可以从其他地方重新生成,例如,映射自文件的数据属于这种类型,针对这种页,内核有专门的页面回收处理
可移动页(Movable pages):这类页可以随意移动,用户空间应用程序所用到的页属于该类别。它们通过页表来映射,如果他们复制到新的位置,页表项也会相应的更新,应用程序不会注意到任何改变。
   假如上图中大部分页都是可移动页,而分配出去的四个页都是不可移动页,由于不可移动页插在了其他类型页的中间,就导致了无法从原本空闲的连续内存区中分配较大的内存块。考虑下图的情况:

将可回收页和不可移动页分开,这样虽然在不可移动页的区域当中无法分配大块的连续内存,但是可回收页的区域却没有受其影响,可以分配大块的连续内存。
 
内核对于迁移类型的定义如下:
 

 
[cpp]
#define MIGRATE_UNMOVABLE     0  
#define MIGRATE_RECLAIMABLE   1  
#define MIGRATE_MOVABLE       2  
#define MIGRATE_PCPTYPES      3 /* the number of types on the pcp lists */  
#define MIGRATE_RESERVE       3  
#define MIGRATE_ISOLATE       4 /* can't allocate from here */  
#define MIGRATE_TYPES         5  
 
前三种类型已经介绍过
 
MIGRATE_PCPTYPES是per_cpu_pageset,即用来表示每CPU页框高速缓存的数据结构中的链表的迁移类型数目
 
MIGRATE_RESERVE是在前三种的列表中都没用可满足分配的内存块时,就可以从MIGRATE_RESERVE分配
 
MIGRATE_ISOLATE用于跨越NUMA节点移动物理内存页,在大型系统上,它有益于将物理内存页移动到接近于是用该页最频繁地CPU
 
MIGRATE_TYPES表示迁移类型的数目
当一个指定的迁移类型所对应的链表中没有空闲块时,将会按以下定义的顺序到其他迁移类型的链表中寻找: 
static int fallbacks[MIGRATE_TYPES][MIGRATE_TYPES-1] = {  
    [MIGRATE_UNMOVABLE]   = { MIGRATE_RECLAIMABLE, MIGRATE_MOVABLE,   MIGRATE_RESERVE },  
    [MIGRATE_RECLAIMABLE] = { MIGRATE_UNMOVABLE,   MIGRATE_MOVABLE,   MIGRATE_RESERVE },  
    [MIGRATE_MOVABLE]     = { MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE, MIGRATE_RESERVE },  
    [MIGRATE_RESERVE]     = { MIGRATE_RESERVE,     MIGRATE_RESERVE,   MIGRATE_RESERVE }, /* Never used */  
};  

(三) linux内核对伙伴系统的改进--migrate_type 

linux底层使用伙伴系统-buddy管理物理内存,buddy可以被证明是一种很有效的内存管理方式,但是它也拥有很多缺点,其中碎片避免的不完备性 --仅仅寄托于释放时的合并操作而不考虑分配时的策略,这也许是它最大的不足,linux2.6内核的后期版本对这个问题进行了改进,大大避免了碎片的泛 滥。在linux中,buddy是通过下列数据结构表示的(2.6的早期内核): 
struct free_area {
    struct list_head    free_list;
    unsigned long        *map;
};
系统中10个free_area组成一个数组,每一个free_area包含一个链表,每一个链表上链接有空闲内存页面块。后来引入了MIGRATE_TYPE,于是free_area结构体就成了:
struct free_area {
    struct list_head    free_list[MIGRATE_TYPES];
    unsigned long        nr_free;
};
每一个free_area包含多个链表,其中每一个链表中的内存页面按照其自身是否可以释放或者迁移被归为一类,于是凡是请求“不可迁移”页面的分配请求 全部在free_list[MIGRATE_UNMOVABLE]这条链表上分配,和老版本一样,系统中有10个free_area代表大小为2的N次幂 个不同页面的集合。这种归类可以最小化内存碎片。
     buddy系统本身就有效的防止了碎片,然而还不够。
buddy主要体现在:1.互为buddy的页面块不可能共存于一个free_area链表,它们总是倾向于合并;2.一个free_area的链表中的 页面order相同,但是它们肯定彼此不互为buddy,这些页面用于该order大小需求的页面分配。但是buddy的碎片防止机制寄托于内存使用者会 及时释放掉内存的情况,如果使用者长期不释放内存,或者说在使用者还没有释放内存的这一段时间期间,碎片将是存在的,并且可能还会导致很大的问题,比如在 物理内存中间分配了一页面,然而仅因为分配的这一个页面不可移动,在它被释放之前,系统可用的最大的连续物理内存就只有不到一半物理内存总大小了。究其根 源,这种问题的根源在于buddy系统仅仅释放页面时的合并操作防止了碎片的产生,不管页面从哪里被分配,只要它能有效被释放,碎片就是可以避免的,也就 是说,buddy系统对于分配并没有更多的约束,仅仅满足在10个free_area中从小到大的顺序扫描即可。
     既然找到了buddy的问题,那么只要对分配动作采取一定的约束,碎片就可以进一步避免了。
最简单而又不引入过多复杂性的办法就是将页面按照“可移动”属性分类,将不可移动的页面分为一类,将可以移动的页面分为一类,它们各自占据一块足够大的连 续物理空间,不可移动的页面分配需求则尽量在它自己的页面类中分配,可移动的页面也一样,这样一来,不可移动的页面的不可移动性仅仅影响它自身的类别而不 会导致一个不可移动的页面两边都是可移动的页面。这就是MIGRATE_TYPE被引入的目的。MIGRATE_TYPE限制了内存页面的分配地点从而避 免碎片,而不再仅仅寄希望于它们被释放时通过合并避免碎片。
     可以说MIGRATE_TYPE仅仅是一种防止碎片的策略,不应该因为它的存在而影响到内存分配的结果,也就是说,如果在一个MIGRATE_TYPE链 表中没有内存可以分配了,那么也还是可以从别的链表中“暂时抢”一些的。另外,还有一个问题,内核载初始化的时候如何为“不可移动类”或者“可移动类”页 面指定初始大小呢?也就是说,一开始,系统的free_area中的这些类别链表的页面各该是多少个呢?事实上,内核从来没有指定过初始大小,而是一开始 将所有页面都归到“可移动”组当中,而别的组全部都是空的,等到真的有不可移动页面需求的时候再从可移动组中拨一批给不可移动组链表,想一下这也是合理 的,毕竟只是一些“不可移动”的页面造成了内存的长期碎片化,如果没有这些长期使用的不可移动页面,碎片的问题是不大的。这个从 __rmqueue_fallback函数中可以看出,系统的内存子系统拥有一个fallbacks序列,该序列展示了一个分配序列,也就是如果一个 migratetype链表中如果分配不到内存的话,下一个应该在哪个migratetype链表中分配。从__rmqueue_fallback可以看 出,如果从要求的migratetype空闲链表中分配不到内存的话,并不是在根据fallbacks序列在“下一个”链表中仅仅分配到自己本次所需的就 完事了,而是一次性从fallbacks序列中指示的链表中转移足够多的页面到分配时要求的migratetype链表,毕竟该种类型的空闲链表已经没有 页面了,确实需要补充了,并且如果补充的页面太少,那么就会给转移的源migratetype类型组造成碎片,只有一次性分配一大块内存,才不至于引入碎 片。
static struct page *__rmqueue_fallback(struct zone *zone, int order,
                        int start_migratetype)
{
    struct free_area * area;
    int current_order;
    struct page *page;
    int migratetype, i;
    //尽量一次性拨出尽可能多的内存页面给“该”migratetype的free_area链表
    for (current_order = MAX_ORDER-1; current_order >= order; --current_order) {
        for (i = 0; i < MIGRATE_TYPES - 1; i++) {
            migratetype = fallbacks[start_migratetype][i];
            if (migratetype == MIGRATE_RESERVE)  //不允许占用保留内存
                continue;
            area = &(zone->free_area[current_order]);
            if (list_empty(&area->free_list[migratetype]))
                continue;
            page = list_entry(area->free_list[migratetype].next, struct page, lru);
            area->nr_free--;
            ...
            list_del(&page->lru);
            rmv_page_order(page);
            __mod_zone_page_state(zone, NR_FREE_PAGES, -(1UL << order));
            if (current_order == pageblock_order)
                set_pageblock_migratetype(page,    start_migratetype);
            //将除去本次自己要用的page[order]之外的其它页面全部补充进该area的migratetype空闲链表
            expand(zone, page, order, current_order, area, migratetype);
            return page;
        }
    }
    return __rmqueue_smallest(zone, order, MIGRATE_RESERVE);
}
     另外,还有一种类似的机制用于避免碎片,那就是使用ZONE的概念,新构造出一个虚拟的ZONE--ZONE_MOVABLE,所谓的虚拟就是它并不和任 何物理内存区间相关联,而是可以附着在任何的物理zone上,用户可以通过命令行参数指定用于“可移动”或者“不可移动”的内存的大小,从而也就规定了虚 拟的ZONE_MOVABLE的大小。一般的最终比较高的物理内存区域用于可移动的虚拟zone(ZONE_MOVABLE)分配,这是因为低地址内存更 多的用于dma或者isa或者内核数据结构(一一线性映射)等,而高内存则一般用于用户进程(可以交换到交换空间...)

阅读(3792) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~