内存管理器（四）伙伴算法及分配器原理实现

墨蓝 2022-08-09 09:38 190阅读 0赞

# 内存管理器（四） 伙伴算法 #

### 前言 ###

上两篇一共介绍了边界标识算法，以及使用边界标识算法实现了一个堆内存的分配器，现在我们学习下另一种内存管理的算法，我们的Linux的内存管理就广泛应用了伙伴算法。非话不多说。

## \_\_START ##

## 这个算法是什么？ ##

#### 伙伴算法： ####

伙伴算法（系统）是操作系统中用到的另一种动态存储管理方法。它和边界标识法类似。在用户提出申请时，分配一块恰当的内存区域给用户；反之，在用户释放内存区域的时候收回。不同的是，在伙伴系统中，所有的内存块大小都是以2的整数次幂大小，当然这里立刻暴出一个隐含的问题，就是内存碎片可能会很多。

#### 数据结构（纯算法思想的数据结构，并不实用） ####

#define m 16
    typedef struct WORD_B{
        WORD_b *llink;
        int tag;
        int kval ;
        WORD_b *rlink;
        OtherType other;
    }WORD_b,head;
    
    
    typedef struct HEADNODE{
        int nodesize;
        WORD_b *first;
    }FREELIST[m+1];

#### 图解分配过程 ####

![图解][1366520549_3178.png]

下面贴上一个分配器原理实现代码

/************************************************************************* > File Name: buddy.c > Author: > Mail: > Created Time: 2015年10月17日 星期六 19时45分14秒 ************************************************************************/
    
    #include<stdio.h>
    #include<assert.h>
    #include<unistd.h>
    #include<sys/mman.h>
    #include<string.h>
    #include<errno.h>
    #include<fcntl.h>
    #include<pthread.h>
    #include<stdlib.h>
    
    
    #define GET_LEFT(index) ((index) * 2 + 1) //向左边，扩大2^(k+1)
    #define GET_RIGHT(index) ((index) * 2 + 2) //依然是扩大，2^(k+1) 
    #define PARENT(index) (((index) + 1)/2 -1) //寻找父块
    
    #define IS_POWER_OF_2(x) (!((x) & ((x) - 1))) //判断这个数子时不是2的幂次
    #define MAX(a,b) ((a) > (b) ? (a):(b)) //大小
    
    typedef struct node{
    
        unsigned size;
        unsigned list[1];
    
    }node;
    
    static unsigned fixsize(unsigned size);
    struct node * node_new(int size);
    void node_destory(struct node * self);
    int node_malloc(struct node *self,int size);
    void node_free(struct node *self,int offset);
    
    
    void node_free(struct node *self,int offset){ //寻找父块合并大小
    
        unsigned node_size ,index = 0;
        unsigned left_list,right_list;
    
        assert(self && offset >= 0 && offset < self->size);
    
        node_size = 1;
        index = offset + self->size -1;
    
        for(;self->list[index];index = PARENT(index)){
            node_size *= 2;
            if(index == 0)
                return ;
        }
    
        self->list[index] = node_size;
    
        while(index){
            index = PARENT(index);
            node_size *= 2;
            left_list = self->list[GET_LEFT(index)];
            right_list = self->list[GET_RIGHT(index)];
    
            if(left_list + right_list == node_size)
                self->list[index] = node_size;
            else
                self->list[index] = MAX(left_list,right_list);
        }
    
    }
    
    
    int node_malloc(struct node *self,int size){
        unsigned index = 0;
        unsigned node_size;
        unsigned offset = 0;
    
        if(self == NULL){    //如果空间表为空就返回NULL
            return -1;
        }
    
        if(size <= 0)         //如果需要的空间非法返回1
            size = 1;
        else if(!IS_POWER_OF_2(size))
            size = fixsize(size);
    
        if(self->list[index] < size)   //如果第一标准空间小于size ，那么没有可以分配的大小返回-1
            return -1;
    
        for(node_size = self->size;node_size != size;node_size/=2){  //寻找相匹配的大小块头编号
            if(self->list[GET_LEFT(index)] >= size)
                index = GET_LEFT(index);
            else
                index = GET_RIGHT(index);
        }
    
        self->list[index] = 0;                 //设置为空
        offset = (index + 1) * node_size -self->size;  //计算偏移量地址，得出偏移量
    
        while(index){
            index = PARENT(index);
            self->list[index] = MAX(self->list[GET_LEFT(index)],self->list[GET_RIGHT(index)]);
        }
    
    
        return offset;
    }
    
    
    
    
    void node_destory(struct node * self){
        free(self);
    }
    
    
    struct node * node_new(int size){    //创建主要的空闲表结构，参数为希望创建的大小的2的次幂
        struct node * self;
        unsigned node_size;
        int i;
    
        if(size < 1 || !IS_POWER_OF_2(size))     
            return NULL;
    
        self = (node *)malloc(2 * size * sizeof(unsigned));//创建主要的空闲表结构，给与一个标准值
        self->size = size;
        node_size = size *2;
    
        for(i = 0;i < 2*size-1;++i){
            if(IS_POWER_OF_2(i+1))
                node_size /= 2;
            self->list[i] = node_size;
        }
    
        return self;
    }
    
    
    
    
    static unsigned fixsize(unsigned size){                //固定size 的大小
        size |= size >> 1;
        //printf("%d\n",size);
        size |= size >> 2;
        //printf("%d\n",size);
        size |= size >> 4;
        //printf("%d\n",size);
        size |= size >> 8;
        //printf("%d\n",size);
        size |= size >>16;
        //printf("%d\n",size);
        return size+1;
    }
    
    
    
    int main(){
       node * space;
        space = node_new(32);
        int a = node_malloc(space,10);
        int i = 0;
        node_free(space,a);
        for(i = 0;i < 9;i++){
            printf("the %d\n",space->list[i]);
        }
    
    }

其实伙伴算法的思想简单，但是拘泥于特定的场合，也同意产生内存碎片，所以综合，边界标识法也好，伙伴算法也好，各有优势吧，就像windos ,linux,mac os ; 谁又能下一个结论证明谁更好呢？

[1366520549_3178.png]: https://img-my.csdn.net/uploads/201304/21/1366520549_3178.png