`

linux内核对伙伴系统的改进(转)

阅读更多

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或者内核数据结构(一一线性映射)等,而高内存则一般用于用户进程(可以交换到交换空间...)

 

分享到:
评论

相关推荐

    Linux内核完全注释V3.0_linux内核_linux_

    在"Linux内核完全注释V3.0"这本书中,作者详细地解释了内核源代码的各个部分,这对于开发者、系统管理员以及对操作系统原理感兴趣的人来说是一份宝贵的资料。通过深入阅读这本书,我们可以了解以下关键知识点: 1. ...

    伙伴算法在Linux内核中的应用及其改进.pdf

    《伙伴算法在Linux内核中的应用及其改进》 伙伴算法是计算机操作系统内存管理中的一种常见策略,尤其在Linux内核中得到了广泛的应用。该算法的核心思想是通过将大块内存分割成大小相等的两部分,形成伙伴关系,以便...

    深入分析Linux内核源码

    随着开源软件的兴起,尤其是Linux操作系统在全球范围内的广泛应用,对Linux内核的研究变得越来越重要。了解Linux内核的工作原理不仅对于开发者来说至关重要,同时也对教育和科学研究领域有着深远的影响。 #### 第一...

    linux内核图解 内核一目了然分解

    《Linux内核图解》是一本旨在...这将有助于系统管理员、开发人员和对Linux内核感兴趣的任何人都能更高效地学习和工作。无论你是初学者还是有经验的从业者,这本书都能提供宝贵的洞见,帮助你揭开Linux内核的神秘面纱。

    深入了解Linux内核

    【深入理解Linux内核】 Linux内核是操作系统的核心部分,负责管理硬件资源,提供系统调用...辅助文件"软件下载说明.txt"和"更多软件下载.url"可能是为了方便读者获取相关工具和资源,以加深对Linux内核的理解和实践。

    linux内核架构2018最新版本

    Linux内核还使用了伙伴系统(Buddy System)来分配和回收内存页。Slab分配器提供了一种管理内核对象缓存的方法,以减少内存碎片并提高性能。kmalloc和kfree是内核提供的内存分配和释放接口。 虚拟文件系统(VFS)是...

    linux内核0.11和2.40

    Linux内核是操作系统的核心部分,负责管理系统的硬件资源、提供系统调用接口以及调度进程等。本主题将探讨两个重要的Linux内核版本:Linux 0.11和2.4.0,它们在Linux发展史上具有里程碑式的意义。 **Linux 0.11内核...

    Linux内核源码(2.6.24)

    Linux内核源码是Linux操作系统的核心部分,它负责管理系统的硬件资源、进程调度、内存管理、文件系统以及网络协议等核心功能。对于那些热衷于Linux内核编程、系统开发或者想要深入理解操作系统原理的人来说,研究...

    Linux内核代码2.4.0版本

    Linux内核代码2.4.0版本是Linux操作系统发展历史中的一个重要里程碑,它标志着Linux从一个相对简单的实验性操作系统向成熟、稳定的企业级平台迈进了一大步。这个版本的内核包含了众多改进和新功能,使得它在当时成为...

    Linux-2.6.11内核源码

    Linux内核是操作系统的核心部分,负责管理系统的进程、内存、设备驱动、文件系统以及网络协议等。Linux-2.6.11内核是Linux发展历史中的一个重要版本,发布于2005年,它在前一版本的基础上进行了许多改进和优化。这个...

    Linux内核源码

    Linux内核是操作系统的核心部分,它负责管理系统的硬件资源,调度进程,实现内存管理,提供文件系统和网络接口,以及安全机制等。这份压缩包包含了有关Linux内核源码的详细资源,对于想要深入理解Linux操作系统工作...

    linux0.11内核源码

    同时,这也是理解后续 Linux 内核发展演变的重要起点,例如后来的多线程支持、更复杂的内存管理策略、更丰富的文件系统支持和设备驱动模型的改进等。 总之,Linux 0.11 内核源码不仅是学习操作系统原理的宝贵教材,...

    Linux内核源码-3.18.13版本|linux-3.18.13.tar.gz

    3.18.13版本的Linux内核是Linux发展历史中的一个稳定分支,包含了众多改进和修复,对于理解Linux内核的工作原理、编写内核驱动以及进行系统优化具有重要的学习价值。 1. **内核架构** Linux内核采用了微内核设计,...

    Linux内核设计与实现(英文版.第3版)

    3. **内存管理**:深入解析Linux内核的内存分配策略,如伙伴系统和slab分配器,以及如何实现虚拟地址到物理地址的映射,确保内存的有效使用和管理。 4. **设备驱动**:介绍设备驱动程序的基本概念,如何编写和注册...

    《深入理解linux内核》

    《深入理解Linux内核》是一本深受欢迎的书籍,它为读者揭示了Linux操作系统的内部运作机制,提供了宝贵的洞察力,使开发者能够更好地理解和优化Linux系统。第三版基于Linux 2.6.11内核,这是一个相对稳定且广泛使用...

    操作系统实验指导——基于Linux内核(第2版)

    在"操作系统实验指导——基于Linux内核(第2版)"中,我们将深入学习Linux操作系统的核心原理和实际操作,这是一本针对实践操作而设计的教程。该书不仅包含理论知识,还附带了完整的源码,为读者提供了亲自动手探索...

    Linux内核笔记

    Linux内核,作为开源操作系统的重要组成部分,由林纳斯·托瓦兹于1991年创建,如今已经成为全球最广泛使用的开源操作系统内核之一。 **1. 源码分析** Linux内核是开放源码的,这意味着任何人都可以查看、学习和...

    Linux内核完全注释

    这本书详细地对Linux内核的源代码进行了注释,旨在帮助读者理解内核的工作原理,从而能够更有效地进行系统级编程和优化。 Linux内核是开源的,这使得全世界的开发者都有机会参与到其开发和改进中。通过阅读和理解...

    linux内核源代码分析

    通过深入阅读和分析Linux内核源代码,不仅可以提升对操作系统原理的理解,也有助于开发者编写更高效、更稳定的系统级程序,甚至参与到Linux内核的开发和改进中去。对于想要深入研究Linux内核的人来说,《Linux内核源...

Global site tag (gtag.js) - Google Analytics