精华内容
下载资源
问答
  • 1.前言: PooledByteBufAllocator 实现相当复杂,其中涉及许多复杂的数据结构类: 1)PoolArena ...其核心思想是利用了为 FreeBSD 设计的 jemalloc 内存分配算法和 buddy 分配算法。为了更好地解...

    1.前言:

    PooledByteBufAllocator 实现相当复杂,其中涉及许多复杂的数据结构类:

    1)PoolArena

    2)PoolChunk 

    3)PoolSubpage

    5)PoolThreadCache

    还有其他相关辅助类包括 PoolChunkList

    其核心思想是利用了为 FreeBSD 设计的 jemalloc 内存分配算法和 buddy  分配算法。为了更好地解读 netty 内存分配,本节首先着重介绍 buddy  分配算法。

    2.算法

    内存管理,特别是内存分配一直是操作系统一个基本问题。固定的划分模式会限制活跃进程的数量,而且如果进程请求的大小与可用的分割大小匹配效果不佳,会导致内存空间的使用效率很低。动态划分模式使得维护更复杂,包括内存合并的开销。而伙伴算法就是权衡折中的一种算法。最早由贝尔电话实验室的 Ken C Knowlton 在1965年的《A fast storage allocator》一文中提出。

    在伙伴算法中,把用来分配的内存作为一整块2次幂大小的空间。当请求到达时,如果请求的大小大于初始大小空间的一半,那么整块内存都会被分配。否则,这个内存块会一分为二(这两块内存块互为伙伴,算法名即来源于此),这时候再一次判断请求的大小是否大于其中一块子内存块的一半,如果大于,则这块子块将被分配。如果小于,那么再将其中一个子块一分为二,以此类推,直到请求的大小大于分割后的子块的一半,若未找到,则直到分割系统允许的最小单位为止,然后再将相应内存块分配。

    在此算法中,当一个进程结束时,分配给进程的内存块会被释放。只要有可能,一个未分配的内存块就会试图与其伙伴块合并以便形成一个更大的空闲内存块。如果两个内存块是由同一个父内存块一分为二产生的,那么他们就互为伙伴。

    下面的例子展示了伙伴算法的具体分配过程。假设初始内存块大小为1024KB,表左侧为进程每次请求的内存大小。

    分配时优先考虑从低地址开始适配内存块。

    展开全文
  • 内存分配算法代码模拟。包含 首次适应算法(First Fit) 最佳适应算法(Best Fit)最差适应算法(Worst Fit)伙伴算法(buddy) https://blog.csdn.net/GreyBtfly/article/details/84646981
  • 本节,我将介绍linux系统物理内存分配时所用到的技术——伙伴系统和slab缓存。 伙伴系统 使用场景:内核中很多时候要求分配连续页,为快速检测内存中的连续区域,内核采用了一种技术:伙伴系统。 原理:系统中...

    本节,我将介绍linux系统物理内存分配时所用到的技术——伙伴系统和slab缓存。
    伙伴系统
    使用场景:内核中很多时候要求分配连续页,为快速检测内存中的连续区域,内核采用了一种技术:伙伴系统。

    原理:系统中的空闲内存总是两两分组,每组中的两个内存块称作伙伴。伙伴的分配可以是彼此独立的。但如果两个小伙伴都是空闲的,内核将其合并为一个更大的内存块,作为下一层次上某个内存块的伙伴。如下图给出了一对伙伴,初始大小均为8页。

    内核对所有大小相同的小伙伴,都放置到统一列表中管理。如果系统现在需要8个页帧,则将16个页帧组成的块拆分为两个伙伴。其中一块用于满足应用程序的请求,而剩余的8个页帧则放置到对应8页大小内存块的列表中。

    如果下一个请求只需要2个连续页帧,则由8页组成的块分裂成2个伙伴,每个包含4个页帧。其中一块放置回伙伴列表中,而另一个再次分裂成2个伙伴,每个包含2页。其中一个回到伙伴系统,另一个则传递给应用程序。

    在应用程序释放内存时,内核可以直接检查地址,来判断是否创建一组伙伴,并合并为一个更大的内存块放回到伙伴列表中,这刚好是内存块分裂的逆过程,提高了较大内存块的可用性。

    slab缓存
    适用场景:内核本身经常需要比完整页帧小的多的内存块。

    原理:在伙伴系统基础上自行定义额外的内存管理层,将伙伴系统提供的页划分为更小的部分。

    方法1:对频繁使用的对象,内核定义了只包含了所需类型对象实例的缓存。每次需要某种对象时,可以从对应的缓存快速分配(使用后释放到缓存)。slab缓存自动维护与伙伴系统的交互,在缓存用尽时会请求新的页帧。

    方法2:对通常情况下小内存块的分配,内核针对不同大小的对象定义了一组slab缓存,可以像用户空间编程一样,用相同的函数访问这些缓存。不同之处是这些函数都增加了前缀k,表明是与内核相关联的:kmalloc和kfree。

    1.原理

    Linux的伙伴算法把所有的空闲页面分为10个块组,每组中块的大小是2的幂次方个页面,例如,第0组中块的大小都为20 (1个页面),第1组中块的大小为都为21(2个页面),第9组中块的大小都为29(512个页面)。也就是说,每一组中块的大小是相同的,且这同样大小的块形成一个链表。

    我们通过一个简单的例子来说明该算法的工作原理。

    假设要求分配的块其大小为128个页面(由多个页面组成的块我们就叫做页面块)。该算法先在块大小为128个页面的链表中查找,看是否有这样一个空闲块。如果有,就直接分配;如果没有,该算法会查找下一个更大的块,具体地说,就是在块大小为256个页面的链表中查找一个空闲块。如果存在这样的空闲块,内核就把这256个页面分为两等份,一份分配出去,另一份插入到块大小为128个页面的链表中。如果在块大小为256个页面的链表中也没有找到空闲页块,就继续找更大的块,即512个页面的块。如果存在这样的块,内核就从512个页面的块中分出128个页面满足请求,然后从384个页面中取出256个页面插入到块大小为256个页面的链表中。然后把剩余的128个页面插入到块大小为128个页面的链表中。如果512个页面的链表中还没有空闲块,该算法就放弃分配,并发出出错信号。

    以上过程的逆过程就是块的释放过程,这也是该算法名字的来由。满足以下条件的两个块称为伙伴:

    · 两个块的大小相同

    · 两个块的物理地址连续

    伙伴算法把满足以上条件的两个块合并为一个块,该算法是迭代算法,如果合并后的块还可以跟相邻的块进行合并,那么该算法就继续合并。

    6.3.3 Slab分配机制

    采用伙伴算法分配内存时,每次至少分配一个页面。但当请求分配的内存大小为几十个字节或几百个字节时应该如何处理?如何在一个页面中分配小的内存区,小内存区的分配所产生的内碎片又如何解决?

    Linux2.0采用的解决办法是建立了13个空闲区链表,它们的大小从32字节到132056字节。从Linux2.2开始,MM的开发者采用了一种叫做slab的分配模式,该模式早在1994年就被开发出来,用于Sun Microsystem Solaris 2.4操作系统中。Slab的提出主要是基于以下考虑:

    · 内核对内存区的分配取决于所存放数据的类型。例如,当给用户态进程分配页面时,内核调用get_free_page()函数,并用0填充这个页面。 而给内核的数据结构分配页面时,事情没有这么简单,例如,要对数据结构所在的内存进行初始化、在不用时要收回它们所占用的内存。因此,Slab中引入了对象这个概念,所谓对象就是存放一组数据结构的内存区,其方法就是构造或析构函数,构造函数用于初始化数据结构所在的内存区,而析构函数收回相应的内存区。但为了便于理解,你也可以把对象直接看作内核的数据结构。为了避免重复初始化对象,Slab分配模式并不丢弃已分配的对象,而是释放但把它们依然保留在内存中。当以后又要请求分配同一对象时,就可以从内存获取而不用进行初始化,这是在Solaris 中引入Slab的基本思想。

    实际上,Linux中对Slab分配模式有所改进,它对内存区的处理并不需要进行初始化或回收。出于效率的考虑,Linux并不调用对象的构造或析构函数,而是把指向这两个函数的指针都置为空。Linux中引入Slab的主要目的是为了减少对伙伴算法的调用次数。

    · 实际上,内核经常反复使用某一内存区。例如,只要内核创建一个新的进程,就要为该进程相关的数据结构(task_struct、打开文件对象等)分配内存区。当进程结束时,收回这些内存区。因为进程的创建和撤销非常频繁,因此,Linux的早期版本把大量的时间花费在反复分配或回收这些内存区上。从Linux2.2开始,把那些频繁使用的页面保存在高速缓存中并重新使用。

    · 可以根据对内存区的使用频率来对它分类。对于预期频繁使用的内存区,可以创建一组特定大小的专用缓冲区进行处理,以避免内碎片的产生。对于较少使用的内存区,可以创建一组通用缓冲区(如Linux2.0中所使用的2的幂次方)来处理,即使这种处理模式产生碎片,也对整个系统的性能影响不大。

    · 硬件高速缓存的使用,又为尽量减少对伙伴算法的调用提供了另一个理由,因为对伙伴算法的每次调用都会“弄脏”硬件高速缓存,因此,这就增加了对内存的平均访问次数。

    Slab分配模式把对象分组放进缓冲区(尽管英文中使用了Cache这个词,但实际上指的是内存中的区域,而不是指硬件高速缓存)。因为缓冲区的组织和管理与硬件高速缓存的命中率密切相关,因此,Slab缓冲区并非由各个对象直接构成,而是由一连串的“大块(Slab)”构成,而每个大块中则包含了若干个同种类型的对象,这些对象或已被分配,或空闲,如图6.12所示。一般而言,对象分两种,一种是大对象,一种是小对象。所谓小对象,是指在一个页面中可以容纳下好几个对象的那种。例如,一个inode结构大约占300多个字节,因此,一个页面中可以容纳8个以上的inode结构,因此,inode结构就为小对象。Linux内核中把小于512字节的对象叫做小对象。

    实际上,缓冲区就是主存中的一片区域,把这片区域划分为多个块,每块就是一个Slab,每个Slab由一个或多个页面组成,每个Slab中存放的就是对象。

    因为Slab分配模式的实现比较复杂,我们不准备对其进行详细的分析,只对主要内容给予描述。

    Jeff 发现对内核中普通对象进行初始化所需的时间超过了对其进行分配和释放所需的时间。因此他的结论是不应该将内存释放回一个全局的内存池,而是将内存保持为针对特定目而初始化的状态。

    展开全文
  • 内含伙伴系统、最坏、最佳三种分配方式的演示,有内存分配动态变化图。
  • 实现了一个小的伙伴系统内存分配算法,和linux的页框分配算法类似
  • 内存分配算法伙伴算法

    千次阅读 2011-03-21 18:13:00
    Next Fit算法 首先为了作一个对比,使用了一个来自于《C程序设计语言》上面的malloc版本来进行比对。 这个简单版本的思想是使用一个循环单链表来进行空闲块的维护,base变量表示该链表的头,freep表示上次操作的

    References:

    1. http://blog.csdn.net/zhouzhanglong/archive/2009/04/17/4086349.aspx

    Next Fit算法

    首先为了作一个对比,使用了一个来自于《C程序设计语言》上面的malloc版本来进行比对。

    这个简单版本的思想是使用一个循环单链表来进行空闲块的维护,base变量表示该链表的头,freep表示上次操作的(malloc或者free)的空闲块。

    分配一定大小的块的时候,从freep开始找,知道找到一个空闲块其大小大于等于请求块的大小。如果大小刚好,则直接分配出去,否则从尾部开始分配请求大小的块,剩余的大小就变成新的空闲块,这样做的好处是不用维护一个指向freep前一个空闲块的指针,而只需要改变size值就可以。这个算法在操作系统的术语里面叫做Next Fit。

    这个算法具有一定的随机性的思想,所以总体来说块的分配会比较平均。

     

    以下是malloc.h的内容:

     

    下面是malloc和free的函数定义:


    Buddy Algorithm(伙伴算法)

    就如Reference里面的算法描述,伙伴算法的核心思想是把块的大小都定好,一般是2的幂的大小。

    在这里我们会有一个最大的幂值,称为u,也就是最大块就是2^u那么大。

    有一个最小幂值,称为l,最小块的大小就是2^l那么大。

    然后不同大小的块使用不同的链表来管理,总的是一个free_area的数组来存储这些链表的表头。其中数组free_area里面的下标表示的就是这个链表对应的块的大小的幂数。

    然后在分配空闲块的时候首先从最小的大于申请大小的块开始查找。如果这个申请块的幂数是7那么就从free_area[7]开始查找。如果这个链表为空,则往大的链表开始搜索,如果搜索到了的话,将大块分割成两个小块,其中一块用来分配,另外一块用来存在小的块的链表里面。

     

    这里我的实现是使用了双向链表来实现。

    而在free的过程中,就查看这个释放块的相邻块是否也是空闲,这里相邻块称为伙伴(buddy)。如果伙伴也是在空闲块的块的话,那么就将这两个块合并,这个过程递归,不能再合并为止。


    下面是buddy.h里面关于函数的定义:

    下面相关的数据结构和函数定义:

     

    可以看到伙伴算法对于零散块的处理是比较好的。伙伴算法相对于Next Fit算法的好处是减少了External Fragmentation(外部碎块,也就是在分配块之间的洞),但是增加了Internal Fragmentation(内部碎块,也就是在申请块内部有一部分是没有被用到的)。

     

    经过测试,使用了100次随机从20到120的随机大小块分配,然后再随机的从这些分配块里面释放。

    得到的结果是Next Fit的碎片数目是16,而Buddy的数目是11。

    从这个数字多少可以感受到对于碎片的处理,Buddy的确是优于Next Fit。

    展开全文
  • #include #include #include #include //双向链表 struct list_head { ...//拉链法存储空闲内存 typedef struct free_area { struct list_head free_list; //把空闲内存块链接到空闲链表 uns

       伙伴系统是常用的内存分配算法,linux内核的底层页分配算法就是伙伴系统,伙伴系统的优点就是分配和回收速度快,减少外部碎片。算法描述: 

     https://en.wikipedia.org/wiki/Buddy_memory_allocation                                      http://dysphoria.net/OperatingSystems1/4_allocation_buddy_system.html

    网上也搜了大牛的实现。 云风:https://github.com/cloudwu/buddy  

    对云风的精简版 https://github.com/wuwenbin/buddy2

                这两个版本思想一样都是维护一棵满二叉树,进行分配和回收,云风版的通过标记内存节点状态进行分配,第二个版本是保存当前内存最大的连续可用数,在某些情况下避免了无效的遍历,第二个版本也可以修改为保存最大连续内存数目的阶,内存消耗就会变小。这两个算法分配和回收复杂度都是logn,并且空闲内存必须是2^n个基本分配单位。

          然后又看了一下linux4.8的buddy system实现,linux的buddy system主要进行page分配也是linux最底层的分配,其他的分配算法都是以这个分配为基础,在x86架构下一个page是4KB。linux对内存进行了分区包括低端内存区,高端内存区,dma区,而且还对numa架构做了很多处理,对页面也进行了分类,这些不是讨论的重点,现在主要是提取linux的buddy算法,只提取核心部分,可以在控制台下运行。buddy system的数据结构就是下图所示,看着像哈希表中的拉链法,每个链表保存相同大小的内存块。最大的是10,也就是1024个基本单位,所以linux在x86下一次最多可分配4MB内存。


               顺便学习下linux内核对链表的各种操作,代码实现

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <assert.h>
    //双向链表
    struct list_head {
        struct list_head *prev, *next;
    };
    
    //拉链法存储空闲内存
    typedef struct free_area {
        struct list_head free_list;  //把空闲内存块链接到空闲链表
        unsigned long nr_free;       //每个链表空闲块的个数
    } free_area_t;
    
    struct page {
        struct list_head page_link;
        int order;                  //当前页面所处的阶
        unsigned int size;          //如过当前页面是起始页面则size表示连续的页面数,如过不是起始页面则是0
    };
    
    typedef unsigned char uint8_t ;
    
    #define   MAX_ORDER    11         //最大阶是10,也就是最大的分配单位是2^10,在此程序中一次最多分配4MB内存
    #define   PAGE_SIZE    4096       //基本分配单位
    #define   PAGE_NUMS    4096       //页面个数
    
    uint8_t mem_size[PAGE_SIZE * PAGE_NUMS];   //需要管理的内存
    
    struct page mem_map[PAGE_NUMS];
    
    free_area_t free_area[MAX_ORDER];
    
    #define PAGE_TO_PFN(page)    ((unsigned int)(page - mem_map))
    
    #define ADDR_TO_PAGE(addr)   (((unsigned int)((uint8_t*)addr - mem_size)) / PAGE_SIZE)
    #define PAGE_TO_ADDR(page)    (unsigned int)(PAGE_TO_PFN(page) * PAGE_SIZE + mem_size)
    /**
     *获取成员在结构体中的相对偏移大小
     */
    #define offsetof(TYPE, MEMBER)	((unsigned int)&((TYPE *)0)->MEMBER)
    
    /**
     *获取结构体地址
     */
    #define container_of(ptr, type, member) ({			\
    	const typeof( ((type *)0)->member ) *__mptr = (ptr);	\
    	(type *)( (char *)__mptr - offsetof(type,member) );})
    
    /**
     *初始化双向链表
     */
    #define LIST_HEAD_INIT(name) { &(name), &(name) }
    
    /**
     *用宏快速定义双向链表
     */
    #define LIST_HEAD(name) \
        struct list_head name = LIST_HEAD_INIT(name)
    
    static inline void INIT_LIST_HEAD(struct list_head *list)
    {
        list->next = list;
        list->prev = list;
    }
    
    
    /**
     *在任意两个元素之间插入一个entry
     */
    static inline void __list_add(struct list_head *new,
                                  struct list_head *prev,
                                  struct list_head *next)
    {
        new->next = next;
        prev->next = new;
        next->prev = new;
        new->prev = prev;
    }
    
    
    /**
     *在链表头插入一个新元素,相当于头插法
     */
    static inline void list_add(struct list_head *new, struct list_head *head)
    {
        __list_add(new, head, head->next);
    }
    
    
    /**
     *在链表尾部插入一个新元素,相当于尾插法
     */
    static inline void list_add_tail(struct list_head *new, struct list_head *head)
    {
        __list_add(new, head->prev, head);
    }
    
    /**
     *删除节点操作,删除两个节点之间的操作
     */
    static inline void __list_del(struct list_head *prev, struct list_head *next)
    {
        prev->next = next;
        next->prev = prev;
    }
    
    /**
     *删除节点
     */
    static inline void __list_del_entry(struct list_head *entry)
    {
        __list_del(entry->prev, entry->next);
    }
    
    /**
     *删除节点,并且将next和prev置空,linux内核中是指向一个指定的地址
     */
    static inline void list_del_entry(struct list_head *entry)
    {
        __list_del_entry(entry);
        entry->next = NULL;
        entry->prev = NULL;
    }
    
    /**
     *替换某个节点
     */
    static inline void list_replace(struct list_head *old, struct list_head *new)
    {
        new->next = old->next;
        new->prev = old->prev;
        new->prev->next = new;
        old->next->prev = new;
    }
    
    /**
     *把其中一个链表的节点移动到另一个链表头
     */
    static inline void list_move(struct list_head *list, struct list_head *head)
    {
        __list_del_entry(list);
        list_add(list, head);
    }
    
    /**
     *把其中一个链表的节点移动到另一个链表末端
     */
    static inline void list_move_tail(struct list_head *list, struct list_head *head)
    {
        __list_del_entry(list);
        list_add_tail(list, head);
    }
    
    /**
     *判断链表是否是最后一个节点
     */
    static inline int list_is_last(const struct list_head *list, const struct list_head *head)
    {
        return list->next == head;
    }
    
    /**
     *判断链表是否为空
     */
    static inline int list_empty(const struct list_head *head)
    {
        struct list_head *next = head->next;
        return (next == head) && (head->prev == next);
    }
    
    /**
     * 获取包含链表节点的结构体
     * ptr   链表节点地址
     * type  结构体类型
     * member 结构体成员
     */
    #define list_entry(ptr, type, member) \
        container_of(ptr, type, member)
    
    /**
     * 获取链表第一个元素的结构体
     * ptr = head
     */
    #define list_first_entry(ptr, type, member) \
        list_entry((ptr)->next, type, member)
    
    #define list_first_entry_or_null(ptr, type, member) \
        (ptr)->next == ptr ? NULL : list_first_entry(ptr, type, member)
    /**
     * 获取链表最后一个元素的结构体
     */
    #define list_last_entry(ptr, type, member) \
        list_entry((ptr)->prev, type, member)
    
    /**
     * 获取下一个元素结构体
     */
    #define list_next_entry(pos, member) \
        list_entry((pos)->member.next, typeof(*(pos)), member)
    
    /**
     * 获取上一个元素结构体
     */
    #define list_prev_entry(pos, member) \
        list_entry((pos)->member.prev, typeof(*(pos)), member)
    
    /**
     * 遍历链表
     */
    #define list_for_each(pos, head) \
        for(pos = (head)->next; pos != (head); pos = pos->next)
    
    /**
     * 遍历链表结构体
     */
    #define list_for_each_entry(pos, head, member) \
        for(pos = list_first_entry(head, typeof(*(pos)), member); \
            &(pos->member) != (head);                               \
            pos = list_next_entry(pos, member))
    
    static inline int page_to_pfn(struct page *page)
    {
        return PAGE_TO_PFN(page);
    }
    static inline int fix_size(unsigned int size)
    {
        size -= 1;
        size |= size >> 1;
        size |= size >> 2;
        size |= size >> 4;
        size |= size >> 8;
        size |= size >> 16;
        return size + 1;
    }
    static inline int get_order(unsigned int size)
    {
        int i = 0;
        while(i < 32) {
            if(size & (1 << i))
                return i;
            i++;
        }
        return -1;
    }
    
    static inline unsigned int
    __find_buddy_index(unsigned int page_idx, unsigned int order)
    {
    	return page_idx ^ (1 << order);
    }
    
    static inline int page_is_buddy(struct page *buddy, int order)
    {
        return buddy->order == order;
    }
    static inline void expand(unsigned int low, unsigned int high,
                              struct page *page, struct free_area *area)
    {
        unsigned int size;
        while(low < high) {
            high--;
            area--;
            size = 1 << high;
            list_add(&page[size].page_link, &area->free_list);
            area->nr_free++;
            page[size].order = high;
            page[size].size = size;
        }
    
    }
    static inline struct page *__alloc_pages(unsigned int order)
    {
        unsigned int current_order;
    	struct free_area *area;
    	struct page *page;
    	for(current_order = order; current_order < MAX_ORDER; current_order++) {
            area = &(free_area[current_order]);
            page = list_first_entry_or_null(&area->free_list, struct page, page_link);
            if(!page)
                continue;
            list_del_entry(&(page->page_link));
            page->order = -1;
            page->size = 1 << order;
            area->nr_free--;
            expand(order, current_order, page, area);
            return page;
    	}
    	return NULL;
    
    }
    static struct page *alloc_pages(unsigned int size)
    {
        struct page *page;
        unsigned int alloc_size = fix_size(size);
        unsigned int order = get_order(alloc_size);
        if(order < 0)
            assert(0);
        if(order >= MAX_ORDER)
            assert(0);
        page = __alloc_pages(order);
        if(page)
            return page;
        return NULL;
    }
    static void __free_pages(struct page *page, int order)
    {
        unsigned int page_idx;
        unsigned int combined_idx;
    	unsigned int buddy_idx;
    	unsigned int pfn;
    	struct page *buddy;
    
    	pfn = page_to_pfn(page);
    	page->size = 0;
    	page_idx = pfn & ((1 << MAX_ORDER) - 1);
    	while(order < MAX_ORDER - 1) {
            buddy_idx = __find_buddy_index(page_idx, order);
            buddy = page + (buddy_idx - page_idx);
            //buddy可能会越界如果有4097个页面,则idx为4096的页面的buddy越界
            if(buddy > (mem_map + PAGE_NUMS - 1))
                break;
            if(!page_is_buddy(buddy, order))
                break;
            list_del_entry(&buddy->page_link);         //buddy从当前链表删除
            free_area[order].nr_free--; //当前链表空闲数减一
            buddy->order = -1;
            buddy->size = 0;
            combined_idx = buddy_idx & page_idx;
            page = page + (combined_idx - page_idx);
            page_idx = combined_idx;
            order++;
    	}
    	page->order = order;
    	page->size = 1 << order;
    	list_add(&(page->page_link), &(free_area[order].free_list));
    	free_area[order].nr_free++;
    }
    static void free_pages(struct page *page)
    {
        int order = get_order(page->size);
        __free_pages(page, order);
    }
    
    static void buddy_free(void *addr)
    {
        struct page *page = &mem_map[ADDR_TO_PAGE(addr)];
        free_pages(page);
    }
    
    static void *buddy_malloc(unsigned int size)
    {
        struct page *page = alloc_pages(size);
        if(page)
            return mem_size + (PAGE_TO_PFN(page) * PAGE_SIZE);
        return NULL;
    }
    
    static void init_free_area()
    {
        int cur_order = 0;
        for(; cur_order < MAX_ORDER; cur_order++)
            INIT_LIST_HEAD(&(free_area[cur_order].free_list));
    }
    static void init_pages()
    {
        int i;
        for(i = 0; i < PAGE_NUMS; i++) {
            mem_map[i].order = -1;
            mem_map[i].size = 0;
        }
    }
    static void free_mem_to_buddy()
    {
        int i;
        for(i = 0; i < PAGE_NUMS; i++)
            __free_pages(&mem_map[i], 0);
    }
    
    static void init_mm()
    {
        init_free_area();
        init_pages();
        free_mem_to_buddy();
    }
    /*
     * 打印空闲链表的状态
     */
    static void __dump()
    {
        int order;
        for(order = 0; order < MAX_ORDER; order++) {
            struct page *page;
            if(list_empty(&free_area[order].free_list)) {
                printf("order: %d is NULL\n\n", order);
            } else {
                printf("order: %d, nr_free: %d :\n", order, free_area[order].nr_free);
                list_for_each_entry(page, &free_area[order].free_list, page_link)
                    printf("pfn: %d, page_addr: 0x%p, mem_addr: 0x%p, size: %d\n\n",PAGE_TO_PFN(page), page, PAGE_TO_ADDR(page), page->size);
            }
        }
    }
    static void buddy_test()
    {
        uint8_t *p1 = buddy_malloc(1);
        assert(free_area[MAX_ORDER - 1].nr_free == 3 && free_area[0].nr_free == 1);
        __dump();
        buddy_free(p1);
        __dump();
        assert(free_area[MAX_ORDER - 1].nr_free == 4 && free_area[0].nr_free == 0);
        uint8_t *p2 = buddy_malloc(1024);
        uint8_t *p3 = buddy_malloc(1024);
        uint8_t *p4 = buddy_malloc(2);
        assert(p2 == p1);
        assert(free_area[MAX_ORDER - 1].nr_free == 1);
        assert(free_area[0].nr_free == 0);
        buddy_free(p2);
        buddy_free(p4);
        uint8_t *p5 = buddy_malloc(1024);
        uint8_t *p6 = buddy_malloc(1);
        assert(p5 == p4);
        assert(p6 == p2);
        buddy_free(p5);
        buddy_free(p6);
        assert(free_area[MAX_ORDER - 1].nr_free == 3);
        buddy_free(p3);
        assert(free_area[MAX_ORDER - 1].nr_free == 4 && free_area[0].nr_free == 0);
        p1 = buddy_malloc(3);
        p2 = buddy_malloc(4);
        assert(p1 + PAGE_SIZE * 4 == p2);
        p3 = buddy_malloc(16);
        assert(p2 + PAGE_SIZE * 12 == p3);
        p4 = buddy_malloc(16);
        buddy_free(p3);
        buddy_free(p4);
        assert(free_area[4].nr_free == 1);
        p3 = buddy_malloc(512);
        p4 = buddy_malloc(1);
        buddy_free(p1);
        p1 = buddy_malloc(1);
        assert(p1 == p4 + PAGE_SIZE);
        buddy_free(p1);
        buddy_free(p3);
        buddy_free(p4);
        buddy_free(p2);
        assert(free_area[MAX_ORDER - 1].nr_free == 4);
    
    }
    int main()
    {
        init_mm();
        buddy_test();
        return 0;
    }




    展开全文
  • 内存分配算法

    2019-11-26 20:09:51
    首次适配算法,存储管理器沿着段链表进行搜索,找到第一个足够大的空闲块,将一部分分配给进程使用,另一部分作为空闲块,等待下一次分配。 首次适配尽可能减少搜索链表节点。对首次适配进行很小的修改就能得到下次...
  • 文章目录目录内存分配算法物理内存分配内存碎片伙伴(Buddy)分配算法申请和回收反碎片机制Slab 算法slab 分配器的结构slab 高速缓存分区页框分配器非连续内存内存的分配虚拟内存的分配内核空间内存分配...
  • 分区分配算法:  首次适应算法(First Fit):从空闲分区表的第一个表目起查找该表,把最先能够满足要求的空闲区分配给 作业,这种方法的目的在于减少查找时间。为适应这种算法,空闲分区表(空闲区链)中的空闲...
  • 位图算法 概念: 这种位图即二维数组,通过二维数组来保存内存的使用情况,每个位的值代表...概念: 这种分配算法通过链表来保存和维护块的使用信息,它包括多个单元,每个单元是一个连续的数组,数组的第一位用来表...
  • 自己写的内存分配算法,即伙伴算法,尝试在网上搜索伙伴算法,发现要么找不到,要么写的看不懂,根据原理自己实现了一个。
  • buddy内存分配算法浅析

    千次阅读 2016-08-02 20:46:37
    buddy内存分配算法技术是一种内存分配算法,将内存划分分区,试图以适当地满足内存请求。buddy内存分配算法是比较容易实行。它支持有限,高效的分裂和内存块的合并。目的是为了解决内存的外碎片。 避免外碎片的...
  • 内存管理问题: 内存碎片大小和管理内存碎片的效率问题(即空间和时间效率的问题): 内存碎片是指当回收一块内存时,一般将内存直接放入free链表中,由于内存分配越小,内存块就会特别多...2.伙伴算法. 3.slab算法. ...
  • Buddy内存分配算法

    2019-10-06 09:57:29
    1)尽管伙伴内存算法内存碎片问题上已经做的相当出色,但是该算法中,一个很小的块往往会阻碍一个大块的合并,一个系统中,对内存块的分配,大小是随机的,一片内存中仅一个小的内存块没有释放,旁边两个大...
  • 网上能够找到的关于Linux内存分配伙伴算法的介绍不是很多,而且大多是进行较为抽象的介绍。为了能够让初学者能够快速建立起伙伴算法中提及的空闲链表、位图与内存间的对应关系,我做了以下几张图片,希望能够给初学...
  • 内部碎片是已经被分配出去(能明确指出属于哪个进程)的内存空间,却不能被利用的内存空间.(就是已经被分配出去的内存空间大于请求所需的内存空间,而导致有些内存自己不使用,别的也不能使用) 外部碎片是指还...
  • 内存分配算法(FF、BF、MF)

    千次阅读 2019-05-09 17:58:48
    在实现动态分区分配时,将涉及到分区分配中所用到的数据结构、分区分配算法和分区的分配与回收操作三方面的问题。 我的理解是,动态分区分配是按照作业需要的主存空间大小来分配的,当要装入一个作业时,根据作业...
  • 在Linux系统中,内存分配与回收速率直接影响系统的存取...在进行内存分配时,该算法通过不断平分较大的空闲内存块来获得较小的空闲内存块,直到获得所需要的内存块;在进行内存回收时,该算法尽可能地合并空闲块。
  • 算法已获得满绩 (1)空闲页面分为10个块组,块组编号为0,1,2,……,8,9; (2)内存空间及其划分(界面): 内存物理空间大小可选择:256M bytes,512M bytes; 每个页框的大小可选择:1K bytes,2K bytes,4K bytes...
  • 精品文档 课程设计报告 设计题目 内存的连续分配算法 班级 : 学号 姓名 指导老师 设计时间 摘要 精品文档 精品文档 1主要算法包括 固定分区分配动态分区分配伙伴算法可重定位分区分配 2 内容要求 1定义与算法相关的...
  • 课程设计报告 设计题目内存的连续分配算法 班级 : 学号 姓名 指导老师 设计时间 2012年8月 1 摘要 1主要算法包括 固定分区分配动态分区分配伙伴算法可重定位分区分配 2内容要求 1定义与算法相关的数据结构如PCB空闲...
  • 作者简介: jemalloc 作者 Jason Evans 系统软件工程师,在美国爱达荷大学获得计算机科学理学学士和生物信息学博士,分别在期间激发了他对...下一篇我们会介绍 netty 分配用到的另一个算法 buddy 伙伴分配算法
  • 内存管理算法--Buddy伙伴算法

    千次阅读 2015-12-01 15:29:34
    Buddy算法的优缺点:1)尽管伙伴内存算法内存碎片问题上已经做的相当出色,但是该算法中,一个很小的块往往会阻碍一个大块的合并,一个系统中,对内存块的分配,大小是随机的,一片内存中仅一个小的内存块没有释放...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 13,734
精华内容 5,493
关键字:

内存伙伴分配算法