精华内容
下载资源
问答
  • Buddy算法

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

    最近在在研究Ext4文件系统,ext4预分配涉及到buddy思想,特转载相关概念。


    Buddy算法的优缺点:

    1)尽管伙伴内存算法在内存碎片问题上已经做的相当出色,但是该算法中,一个很小的块往往会阻碍一个大块的合并,一个系统中,对内存块的分配,大小是随机的,一片内存中仅一个小的内存块没有释放,旁边两个大的就不能合并。

    2)算法中有一定的浪费现象,伙伴算法是按2的幂次方大小进行分配内存块,当然这样做是有原因的,即为了避免把大的内存块拆的太碎,更重要的是使分配和释放过程迅速。但是他也带来了不利的一面,如果所需内存大小不是2的幂次方,就会有部分页面浪费。有时还很严重。比如原来是1024个块,申请了16个块,再申请600个块就申请不到了,因为已经被分割了。

    3)另外拆分和合并涉及到 较多的链表和位图操作,开销还是比较大的。

    Buddy(伙伴的定义):

    这里给出伙伴的概念,满足以下三个条件的称为伙伴:
    1)两个块大小相同;
    2)两个块地址连续;
    3)两个块必须是同一个大块中分离出来的;

    Buddy算法的分配原理:

    假如系统需要4(2*2)个页面大小的内存块,该算法就到free_area[2]中查找,如果链表中有空闲块,就直接从中摘下并分配出去。如果没有,算法将顺着数组向上查找free_area[3],如果free_area[3]中有空闲块,则将其从链表中摘下,分成等大小的两部分,前四个页面作为一个块插入free_area[2],后4个页面分配出去,free_area[3]中也没有,就再向上查找,如果free_area[4]中有,就将这16(2*2*2*2)个页面等分成两份,前一半挂如free_area[3]的链表头部,后一半的8个页等分成两等分,前一半挂free_area[2]
    的链表中,后一半分配出去。假如free_area[4]也没有,则重复上面的过程,知道到达free_area数组的最后,如果还没有则放弃分配。



    Buddy算法的释放原理:

    内存的释放是分配的逆过程,也可以看作是伙伴的合并过程。当释放一个块时,先在其对应的链表中考查是否有伙伴存在,如果没有伙伴块,就直接把要释放的块挂入链表头;如果有,则从链表中摘下伙伴,合并成一个大块,然后继续考察合并后的块在更大一级链表中是否有伙伴存在,直到不能合并或者已经合并到了最大的块(2*2*2*2*2*2*2*2*2个页面)。


    整个过程中,位图扮演了重要的角色,如图2所示,位图的某一位对应两个互为伙伴的块,为1表示其中一块已经分配出去了,为0表示两块都空闲。伙伴中无论是分配还是释放都只是相对的位图进行异或操作。分配内存时对位图的
    是为释放过程服务,释放过程根据位图判断伙伴是否存在,如果对相应位的异或操作得1,则没有伙伴可以合并,如果异或操作得0,就进行合并,并且继续按这种方式合并伙伴,直到不能合并为止。


    Buddy内存管理的实现:

    提到buddy 就会想起linux 下的物理内存的管理 ,这里的memory pool 上实现的 buddy 系统

    和linux 上按page 实现的buddy系统有所不同的是,他是按照字节的2的n次方来做block的size

    实现的机制中主要的结构如下:

    整个buddy 系统的结构:

    struct mem_pool_table

    {

    #define MEM_POOL_TABLE_INIT_COOKIE (0x62756479)

    uint32 initialized_cookie; /* Cookie 指示内存已经被初始化后的魔数,  如果已经初始化设置为0x62756479*/

    uint8 *mem_pool_ptr;/* 指向内存池的地址*/

    uint32 mem_pool_size; /* 整个pool 的size,下面是整个max block size 的大小*/

    uint32 max_block_size; /* 必须是2的n次方,表示池中最大块的大小*/   
    boolean assert_on_empty; /* 如果该值被设置成TRUE,内存分配请求没有完成就返回 并输出出错信息*/
     uint32 mem_remaining; /* 当前内存池中剩余内存字节数*/                                              
    uint32 max_free_list_index; /* 最大freelist 的下标,*/
    struct mem_free_hdr_type     *free_lists[MAX_LEVELS];/* 这个就是伙伴系统的level数组*/

    #ifdef FEATURE_MEM_CHECK
    uint32 max_block_requested;
      uint32 min_free_mem; /* 放mem_remaining */
    #endif /* FEATURE_ONCRPC_MEM_CHECK*/
    }
    ;

    这个结构是包含在free node 或alloc node 中的结构:

    其中check 和 fill 都被设置为某个pattern
    用来检查该node 的合法性
    #define MEM_HDR_CHECK_PATTERN ((uint16)0x3CA4)
    #define MEM_HDR_FILL_PATTERN ((uint8)0x5C)


    typedef struct  tagBuddyMemBlockHeadType

    {

        mem_pool_type pool; /*回指向内存池*/

        uint16 check; 

        uint8 state; /* bits 0-3 放该node 属于那1级 bit 7 如果置1,表示已经分配(not free)

        uint8 fill;

    } BUDDY_MEM_BLOCK_HEAD_TYPE;



    这个结构就是包含node 类型结构的 free header 的结构:

    typedef struct  tagBuddyMemHeadType

    {

        mem_node_hdr_type hdr;

        struct mem_free_hdr_type * pNext;   /* next,prev,用于连接free header的双向 list*/

        struct mem_free_hdr_type * pPrev;

    } mem_free_hdr_type;

    这个结构就是包含node 类型结构的 alloc header 的结构:
    已分配的mem 的node 在内存中就是这样表示的
    1. typedef struct mem_alloc_hdr_type
    2. {
    3.    mem_node_hdr_type hdr;

    4. #ifdef FEATURE_MEM_CHECK_OVERWRITE
    5.    uint32     in_use_size;
    6. #endif

    7. } mem_alloc_hdr_type;
    其中用in_use_size 来表示如果请求分配的size 所属的level上实际用了多少
    比如申请size=2000bytes, 按size to level 应该是2048,实际in_use_size
    为2000,剩下48byte 全部填充为某一数值,然后在以后free 是可以check 
    是否有overwite 到着48byte 中的数值,一般为了速度,只 检查8到16byte

    另外为什么不把这剩下的48byte 放到freelist 中其他level 中呢,这个可能
    因为本来buddy 系统的缺点就是容易产生碎片,这样的话就更碎了

    关于free or alloc node 的示意图:

    假设

    最小块为2^4=16,着是由mem_alloc_hdr_type (12byte)决定的, 实际可分配4byte

    如果假定最大max_block_size =1024,

    如果pool 有mem_free_hdr_type[0]上挂了两个1024的block node

    上图是free node, 下图紫色为alloc node


    接下来主要是buddy 系统的操作主要包括pool init , mem alloc ,mem free

    pool init :
     1. 将实际pool 的大小去掉mem_pool_table 结构大小后的size 放到
         mem_pool_size, 并且修改实际mem_pool_ptr指向前进mem_pool_table
         结构大小的地址
     2.  接下来主要将mem_pool_size 大小的内存,按最大块挂到free_lists 上
        level 为0的list 上,然后小于该level block size 部分,继续挂大下一
        级,循环到全部处理完成  (感觉实际用于pool的size ,应该为减去
        mem_pool_table 的大小,然后和最大块的size 对齐,这样比较好,
        但没有实际测试过)
        
        
    mem alloc:
        这部分相当简单,先根据请求mem的size ,实际分配时需要加上mem_alloc_hdr_type
    这12byte ,然后根据调整后的size,计算实际应该在那个 level上分配,如果有相应级
    很简单,直接返回,如果没有,一级一级循环查找,找到后,把省下的部分,在往下一级
    一级插入到对应级的freelist 上

    mem free:
         其中free 的地址,减去12 就可以获得mem_alloc_hdr_type 结构
         然后确定buddy 在该被free block 前,还是后面, 然后合并buddy,
         循环寻找上一级的buddy ,有就再合并,只到最大block size 那级



    关于这个算法,在<<The Art  of Computer Programming>> vol 1,的
    动态存储分配中有描述,对于那些只有OSAL 的小系统,该算法相当有用
    展开全文
  • buddy算法

    2014-10-16 12:58:00
    buddy算法是用来做内存管理的经典算法,目的是为了解决内存的外碎片。避免外碎片的方法有两种: 1,利用分页单元把一组非连续的空闲页框映射到非连续的线性地址区间。 2,开发适当的技术来记录现存的空闲连续页...

    buddy算法是用来做内存管理的经典算法,目的是为了解决内存的外碎片。
    避免外碎片的方法有两种:

    • 1,利用分页单元把一组非连续的空闲页框映射到非连续的线性地址区间。
    • 2,开发适当的技术来记录现存的空闲连续页框块的情况,以尽量避免为满足对小块的请求而把大块的空闲块进行分割。

    基于下面三种原因,内核选择第二种避免方法:

    • 在某些情况下,连续的页框确实必要。
    • 即使连续页框的分配不是很必要,它在保持内核页表不变方面所起的作用也是不容忽视的。假如修改页表,则导致平均访存次数增加,从而频繁刷新TLB。
    • 通过4M的页可以访问大块连续的物理内存,相对于4K页的使用,TLB未命中率降低,加快平均访存速度。

    buddy算法将所有空闲页框分组为10个块链表,每个块链表的每个块元素分别包含1,2,4,8,16,32,64,128,256,512个连续的页框,每个块的第一个页框的物理地址是该块大小的整数倍。如,大小为16个页框的块,其起始地址是16*2^12(一个页框的大小为4k,16个页框的大小为16*4K,1k=1024=2的10次方,4k=2的12次方)的倍数。
    例,假设要请求一个128个页框的块,算法先检查128个页框的链表是否有空闲块,如果没有则查256个页框的链表,有则将256个页框的块分裂两份,一份使用,一份插入128个页框的链表。如果还没有,就查512个页框的链表,有的话就分裂为128,128,256,一个128使用,剩余两个插入对应链表。如果在512还没查到,则返回出错信号。

    回收过程相反,内核试图把大小为b的空闲伙伴合并为一个大小为2b的单独快,满足以下条件的两个块称为伙伴:1,两个块具有相同的大小,记做b;2,它们的物理地址是连续的,3,第一个块的第一个页框的物理地址是2*b*2^12的倍数,该算法迭代,如果成功合并所释放的块,会试图合并2b的块来形成更大的块。

    转载于:https://www.cnblogs.com/linyx/p/4028537.html

    展开全文
  • buddy算法实现

    千次阅读 2016-12-07 21:35:03
    buddy算法实现 头疼,脖子疼。 #define _CRT_SECURE_NO_WARNINGS /* buddy算法 */#include #include #include typedef struct _NODE { int address; //内存地址 int state; //使用状态 int

    buddy算法实现
    头疼,脖子疼。

     #define _CRT_SECURE_NO_WARNINGS 
    /*
    buddy算法
    */
    
    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    typedef struct _NODE
    {  
        int address; //内存地址
        int state;   //使用状态
        int level;   //内存块的大小
        char name[10];  //内存的名称
        struct _NODE *pre;  //前一个结构体块
        struct _NODE *next;  //后一个结构体块
    }NODE;
    struct _NODE * all[10]; //默认的十个等级
    
    //创建内存块,但是没用到
    NODE * alloca_node(int value){
        NODE* pNODE = NULL;
        pNODE = (NODE*)malloc(sizeof(NODE));
        memset(pNODE, 0, sizeof(NODE));  
        pNODE->address = -1;
        pNODE->next = NULL;
        pNODE->pre = NULL;
        return pNODE;
    }
    
    /*从头往后删*/
    void dNODE(NODE **pNODE){
        NODE **pNext;
        if (NULL == pNODE || NULL == *pNODE){
            return;
        }
        pNext = *pNODE;
        free(*pNODE);
        dNODE(pNext);
    }
    //插入节点,没用到。
    int insert_NODE(NODE **ppNODE, int data){
        NODE * pNODE;
        NODE * pIndex;
        if (NULL == ppNODE){
            return -1;
        } 
        if (NULL == *ppNODE){
            pNODE = alloca_node(data);
            *ppNODE = pNODE;
            (*ppNODE)->pre = (*ppNODE)->next = NULL;
            return 1;
        } 
        pNODE = alloca_node(data);
        pIndex = *ppNODE;
        while (NULL != pIndex->next){
            pIndex = pIndex->next;
        }
        pNODE->pre = pIndex;
        pNODE->next = pIndex->next;
        pIndex->next = pNODE;
        return 1; 
    }
    /*
    待定
    */
    int delete_NODE(NODE **ppNODE, int data){
        NODE * pNODE;
        if (NULL == ppNODE || NULL == *ppNODE){
            return -1;
        } 
    } 
    //根据内存块的名称查找到响应的内存块
    NODE * fNODE(char *name){
        int i, j, n, m, k;
        NODE * tmpNODE;
        NODE * preNODE;
        if (name == NULL || strlen(name) == 0){
            return NULL;
        }
        for (i = 0; i < 10; i++){
            tmpNODE = all[i];
            while (tmpNODE != NULL){
                if (strcmp(tmpNODE->name, name) == 0&&tmpNODE->state==1){
                    return tmpNODE;
                }
                preNODE = tmpNODE;
                tmpNODE = tmpNODE->next; 
            }
        }
        return NULL;
    }
    //得到2的幂级数
    int getMing(int base, int n){
        if (n == 0){
            return 1; 
        }
        return base*getMing(base, n - 1);
    }  
    
    //分配内存
    int alloc_big(NODE *ppNODE,int tmpN,char *name){
        NODE *tmpNODE1;
        if (ppNODE == NULL||tmpN>9||tmpN<0){
            return 0;
        }
        if (ppNODE->state == 1||ppNODE->level<tmpN){
            return alloc_big(ppNODE->next, tmpN,name); 
        }
        if (tmpN==ppNODE->level){
            ppNODE->state = 1;
            strcpy(ppNODE->name, name);
            return 1;
        }
        tmpNODE1 = (NODE*)malloc(sizeof(NODE));
        tmpNODE1->pre = ppNODE;
        tmpNODE1->next = ppNODE->next;
        tmpNODE1->address = ppNODE->address + getMing(2,ppNODE->level-1);
        tmpNODE1->state = 0;
        tmpNODE1->level = ppNODE->level-1; 
        ppNODE->next = tmpNODE1;
        ppNODE->state = 0;
        ppNODE->level = ppNODE->level-1;  
        return alloc_big(ppNODE, tmpN,name);   
    }
    //分配内存
    int alloc(int size,char*name){
        int result = 1;
        int tmpN ;
        int n = 0, i;
        NODE *p = NULL;
        if (fNODE(name) != NULL){
            return -1;
        }
        while (size /= 2)
            n++;
        n++;
        tmpN = n;
         for(;n<10;n++){
            if (alloc_big(all[n],tmpN,name) == 1){
                return 1;
            }
            /*if (all[n]->state == 0&&tmpN==n){
                all[n]->state = 1; 
                all[n]->level = n; 
                all[n]->next = NULL;
                all[n]->pre = NULL; 
                return 1;
            }
            else if (all[n]->state == 0){ 
                alloc_big(all[n], tmpN);
            }
            else{
    
            } 
            n++;*/
        }
        return 0;
    } 
    //释放内存
    void free_all(){
        int i, j;
        NODE * tmpNODE = NULL;
        NODE * preNODE = NULL;
        for (i = 0; i < 10; i++){   
            tmpNODE = all[i]->next;
            while(tmpNODE!=NULL){   
                preNODE = tmpNODE; 
                tmpNODE = tmpNODE->next;
                free(preNODE); 
            } 
        }
    }
    //为默认的内存块分配内存
    void create_All(){
        int i;
        for (i = 0; i < 10; i++){
            all[i] = (NODE*)malloc(sizeof(NODE));
        }
    }
    //打印出所有的内存块的使用情况
    void print_all(){
        int i, j, n, k, m;
        NODE *tmpNODE;
        NODE *preNODE;
        for (i = 0; i < 10; i++){
            tmpNODE = all[i];
        //  while (tmpNODE != NULL&&tmpNODE->state==1){
            while (tmpNODE != NULL){
                preNODE = tmpNODE;
                printf("\naddress:%d    ;state:%d   ;level:%d   ;name:%s    ;",tmpNODE->address,tmpNODE->state,tmpNODE->level,tmpNODE->name);
                tmpNODE = tmpNODE->next; 
                printf("\n");
            } 
        }
    }
    //释放某个节点
    int free_NODE(char *name){
        NODE * tmpNODE=fNODE(name);
        NODE *preNODE = NULL;
        NODE *nextNODE = NULL;
        if (tmpNODE == NULL){
            return -1;
        }
        tmpNODE->state = 0;
        while (1){ 
            preNODE = tmpNODE->pre;
            nextNODE = tmpNODE->next;
            if (preNODE != NULL&&nextNODE!=NULL&&preNODE->level == tmpNODE->level && preNODE->state == 0){
                free(tmpNODE);
                preNODE->level++; 
                preNODE->next = nextNODE;
                nextNODE->pre = preNODE;
                tmpNODE = preNODE;
                preNODE = tmpNODE->pre; 
            }
            else if (nextNODE != NULL&&nextNODE->level == tmpNODE->level && nextNODE->state == 0){
    
                tmpNODE->next = nextNODE->next;   
                if (nextNODE->next != NULL){
                    tmpNODE->next->pre = tmpNODE; 
                }
                free(nextNODE);
                tmpNODE->level++;
            }
            else{
                tmpNODE->state = 0;
                return 1;
            }
        } 
    }
    void main()
    {  
    
        int i, j, m, n, k,msize=0;
        char name[10];
        for (i = 0; i < 10; i++){
            all[i] = (NODE*)malloc(sizeof(NODE)); 
            all[i]->address = getMing(2, i) - 1; 
            all[i]->state = 0;
            all[i]->next = NULL;  
            all[i]->pre = NULL;  
            strcpy(all[i]->name, "");
            all[i]->level = i;
        }
        while (1){
            printf("请输入要求 1,分配;2,释放;3,结束\n");
            memset(name, 0, sizeof(name));
            scanf("%d", &n);
            if (n == 1){
                scanf("%d%s", &msize, name);
                m = alloc(msize, name);
                if (m==1){
                    printf("\n分配成功");
                }
                else if (m == -1){
                    printf("\n名字重复");
                }
                else{
                    printf("\n分配失败");
                } 
            }else if (n == 2){
                printf("输入释放名称");
                scanf("%s", name);
                free_NODE(name); 
            }
            else if (n == 3){
                free_all();
                return;
            }
            print_all();
        }
        free_all();
        return 0;
    }
    
    展开全文
  • linux内核管理内存用二进制伙伴算法(Buddy算法) 伙伴关系:一个母实体分成两个属性相同的子实体,这两个实体就是伙伴关系。 一个内存块分成两个大小相同的子内存块,这两个就是伙伴关系。 满足如下条件: 两个块...

    linux内核管理内存用二进制伙伴算法(Buddy算法)
    伙伴关系:一个母实体分成两个属性相同的子实体,这两个实体就是伙伴关系。
    一个内存块分成两个大小相同的子内存块,这两个就是伙伴关系。
    满足如下条件:

    • 两个块具有相同大小记为 2^K
    • 它们的物理地址是连续的
    • 从同一个大块中拆分出来

    每个内存块有2^order个页面,order相同的放在一个链表中。

    分配算法
    在这里插入图片描述
    假如系统需要4(22)个页面大小的内存块,该算法就到free_area[2]中查找,如果链表中有空闲块,就直接从中摘下并分配出去。如果没有,算法将顺着数组向上查找free_area[3],如果free_area[3]中有空闲块,则将其从链表中摘下,分成等大小的两部分,前四个页面作为一个块插入free_area[2],后4个页面分配出去,free_area[3]中也没有,就再向上查找,如果free_area[4]中有,就将这16(2222)个页面等分成两份,前一半挂如free_area[3]的链表头部,后一半的8个页等分成两等分,前一半挂free_area[2]的链表中,后一半分配出去。假如free_area[4]也没有,则重复上面的过程,知道到达free_area数组的最后,如果还没有则放弃分配。
    内存释放
    内存的释放是分配的逆过程,也可以看作是伙伴的合并过程。当释放一个块时,先在其对应的链表中考查是否有伙伴存在,如果没有伙伴块,就直接把要释放的块挂入链表头;如果有,则从链表中摘下伙伴,合并成一个大块,然后继续考察合并后的块在更大一级链表中是否有伙伴存在,直到不能合并或者已经合并到了最大的块(222222222个页面)。
    在这里插入图片描述

    展开全文
  • Buddy算法和slab分配器

    2018-04-18 16:32:53
    伙伴Buddy算法解决了外部碎片问题.内核在每个zone区管理着可用的页面,按2的幂级(order)大小排成链表队列,存放在free_area数组。具体buddy管理基于位图,其分配回收页面的算法描述如下,buddy算法举例描述:假设...
  • MT#buddy算法#good

    2020-04-16 10:40:27
    Buddy算法的优缺点: 1)尽管伙伴内存算法在内存碎片问题上已经做的相当出色,但是该算法中,一个很小的块往往会阻碍一个大块的合并,一个系统中,对内存块的分配,大小是随机的,一片内存中仅一个小的内存块没有...
  • Buddy算法实现

    千次阅读 2012-10-14 10:08:56
    Buddy算法是为了解决linux内存管理提出的一种高效管理算法,主要解决内存碎片问题,其基本思路如下: 首先把内存中的页框(一个页框大小4kb,对应一个页面,物理的)分为连续的1,2,4,8,16,32,64,128,256,...
  • ######本文只简述Buddy算法在netty内存池中简单实现 内存分配的最小单位为16B。 < 512B的请求为Tiny,< 8KB(PageSize)的请求为Small,<= 16MB(ChunkSize)的请求为Normal,> 16MB(ChunkSize)的请求为...
  • Buddy算法C语言实现

    2012-12-16 17:32:09
    Buddy 伙伴 算法 ,Windows编程环境。
  • 内存分配的buddy算法

    千次阅读 2013-11-29 09:52:35
    buddy算法是用来做内存管理的经典算法,目的是为了解决内存的外碎片。 例子  buddy算法将所有空闲页框分组为10个块链表,每个块链表的每个块元素分别包含1,2,4,8,16,32,64,128,256,512个连续的页框,每个块...
  • Buddy算法改进uCos-II的内存管理方案,值得一看!
  • Buddy算法改进uCos-II的内存管理方案,值得一看!
  • 内存管理简介之Buddy算法和slab分配

    千次阅读 2013-04-13 13:45:05
    1.Buddy算法 linux对空闲内存空间管理采取buddy算法,  Buddy算法: 把内存中所有页面按照2^n划分,其中n=0~5,每个内存空间按1个页面、2个页面、4个页面、8个页面、16个页面、32个页面进行六次划分。划分后形成...
  • Buddy算法是经典的内存管理算法,也是实际在Linux里面运行的一种内存管理算法。它是基于计算机处理二进制具有极高的效率设计的算法。主要是为了解决内存外碎片问题。 页内碎片 内部碎片是已经被分配出去的(能明确...
  • buddy system内存管理,努力让内存分配与相邻内存合并能快速进行(对于普通算法来讲,合并内存相当困难),它利用的是计算机擅长处理2的幂运算。 我们创建一系列空闲块列表,每一种都是2的倍数。 举个例子,如果最小...
  • Buddy算法(雅虎全球研发中心笔试题)

    千次阅读 2012-10-14 10:03:14
    1.Buddy算法 linux对空闲内存空间管理采取buddy算法,  Buddy算法: 把内存中所有页面按照2^n划分,其中n=0~5,每个内存空间按1个页面、2个页面、4个页面、8个页面、16个页面、32个页面进行六次划分。划分后形成...
  • 文章目录伙伴的算法的引入满足以下条件的两个块称为伙伴伙伴位图伙伴算法的思想伙伴算法的数据结构伙伴算法内存分配的过程伙伴算法分配的思想伙伴算法的具体内存分配过程__alloc_pages()函数的实现_rmqueue()函数的...
  • 操作系统课程设计 要求 Linux中内存分配的伙伴堆算法模拟。...(2)实现Buddy heap算法。 (3)通过键盘输入随机产生的申请和释放操作。 (4)每次申请或释放都显示实时的内存分配的对比图。 ...
  • 操作系统buddy源代码。这是我在操作体统课程中做的一个简便模拟程序。

空空如也

空空如也

1 2 3 4 5 ... 19
收藏数 372
精华内容 148
关键字:

buddy算法