Linux系统---简易伙伴系统

顾得泉：个人主页

个人专栏：《Linux操作系统》《C/C++》《LeedCode刷题》

键盘敲烂，年薪百万！

一、题目要求

1.采用C语言实现

2.伙伴系统采用free_area[11]数组来组织。要求伙伴内存最小为一个页面，页面大小为4KB，最大为4MB，即1024个页面。描述一个空闲伙伴内存块的数据结构为

struct chunk
{

       unsigned int power;  //内存块大小的2次幂指数，如12，13，...，22

       unsigned int start;   //内存块的起始地址

       struct chunk* next;  //后向指针

       Struct chunk* prev;  //前向指针

}

3.如何辨识两个内存块c1和c2互为伙伴（buddy）？

条件1：c1.power=c2.power，即两个块的大小相同；

条件2：c1和c2的地址start（二进制）的第power位不同，其他位完全相同。比如，大小为256KB的两个伙伴，一个地址为0x0000,0000，另一个为0x0004,0000，这两个地址的第18位（二进制位，从0开始起位）一个为0，一个为1，其余位完全相同，因此它们互为buddy。

再如，大小为256KB的两个伙伴，一个地址为0x0008,0000，另一个为0x000C,0000，它们的第power位，即第18位一个为0，一个为1，其余位完全相同。

而地址为0x4,0000和0x8,0000的chunk不是伙伴，尽管它们是相邻的。

因此可以设计判断两个chunk是否是伙伴的函数：

int isBuddy(struct chunk* c1, struct chunk* c2)

{

    if(c1->power!=c2->power)

        return 0;

    if((c1->start^c2->start)>>c1->power!=1) //先异或，再移位

        return 0;

    return 1;

}

二、模块描述

本文实现了一个内存管理程序，用于分配和释放内存块。它使用了内存池技术，通过将内存块划分为大小为2^n的块来提高内存分配的效率。

程序中定义了一个结构体chunk，表示内存块，包含以下成员变量：

power：表示内存块的大小，即2^n。
start：表示内存块的起始地址。
next：指向下一个内存块的指针。
prev：指向上一个内存块的指针。

程序还定义了一个全局数组free_area，用于存储空闲的内存块。数组的索引表示内存块的大小，数组的元素是指向对应大小的内存块链表的头指针。

程序提供了以下函数：

is_buddy(struct chunk *c1 , struct chunk *c2)：判断两个内存块是否为“伙伴”关系，即它们的power相同且它们的起始地址相邻。
init()：初始化内存池，将最大内存块分配给free_area[8]。
pick(unsigned int k)：从free_area中选择一个大小为2^k的内存块，并将其分割成两个大小为2^(k-1)的内存块。
allocate(unsigned int req)：请求分配一个大小为req字节的内存块，如果无法满足请求，则返回NULL。
release(struct chunk *c)：释放一个内存块，将其与相邻的伙伴内存块合并，并更新free_area。
check()：打印当前内存池的状态，包括每个大小的内存块链表。

在main()函数中，首先调用init()函数初始化内存池，然后依次请求分配100KB、256KB和500KB的内存块，并打印分配前后的内存池状态。最后，释放这些内存块，并再次打印内存池状态。

三、代码实现

#include <stdio.h>
#include <stdlib.h>

struct chunk{
    unsigned int power;
    unsigned int start;
    struct chunk *next;
    struct chunk *prev;
};

struct chunk* free_area[11];

int is_buddy(struct chunk *c1 , struct chunk *c2)
{
    if(c1 -> power != c2 -> power) return 0;
    if((c1 -> start ^ c2 -> start) >> c1 -> power != 1) return 0;
    return 1;
}

void init()
{
    for(int i = 0 ; i < 11 ; i ++)
    free_area[i] = NULL;

    struct chunk *max_chunk = (struct chunk*) malloc(sizeof(struct chunk));
    max_chunk -> power = 20;
    max_chunk -> start= 0;
    max_chunk -> next = NULL;
    max_chunk -> prev = NULL;
    free_area[8] = max_chunk;
}

struct chunk *pick(unsigned int k)
{
    struct chunk *c = NULL;
    struct chunk *left = NULL;
    struct chunk *right = NULL;

    int i;
    for(i = k ; i <= 10 ; i ++)
    {
        if(free_area[i] != NULL)
        {
            c = free_area[i];
            free_area[i] = c -> next;
            break;
        }
    }


    if(i > 10){
        printf("Failed to pick up a trunk\n");
        return NULL;
    }


    for(int j = i - 1 ; j >= k ; j --)
    {
        left = (struct chunk*)malloc(sizeof(struct chunk));
        left -> power = c -> power - 1;
        left -> start = c -> start;
        left -> next = free_area[j];
        left -> prev = NULL;
        if(free_area[j] != NULL)
        {
            free_area[j] -> prev = left;
        }
        free_area[j] = left;

        right = (struct chunk *) malloc(sizeof (struct chunk));
        right -> power = c -> power - 1;
        right -> start = c -> start + (1 << right -> power);
        right -> next = NULL;
        right -> prev = NULL;

        free(c);
        c = right;
    }

    return c;
}



struct chunk * allocate(unsigned int req){
    unsigned int power = 0;
    while((1 << power) < req)
        power ++;
    return pick(power - 12);

}


void release(struct chunk *c)
{
    unsigned int k = c -> power - 12;
    struct chunk * buddy = NULL;

    int merged = 1;
    while(merged){
        merged = 0;
        buddy = free_area[k];

        while(buddy != NULL){
            if(is_buddy(c , buddy))
            {
                 c -> power ++;
                 if(buddy -> prev == NULL)
                 free_area[k] = buddy -> next;
                 else 
                    buddy -> prev -> next = buddy -> next;
                 if(buddy -> next != NULL)
                    buddy -> next -> prev = buddy -> prev;

                    if(c -> start > buddy -> start) 
                        c -> start = buddy -> start;

            free(buddy);
            merged = 1;
            k ++;
            break;
       }
       buddy = buddy -> next;
    }
    }


    c -> next = free_area[k];
    if(free_area[k] != NULL)
        free_area[k] -> prev = c;
     free_area[k] = c;
}

void check()
{
    for(int i = 0 ; i < 11 ; i ++)
    {
      printf("free_area[%d]: " , i);
      struct chunk * chunk = free_area[i];
      while(chunk != NULL)
      {
        printf("(%u  , %x) ->" , chunk -> power , chunk -> start);
        chunk = chunk -> next;
      }
       printf("NULL\n");
    }
    printf("\n");
}


int main()
{
    init();
    printf("inintal state\n");
    check();

    struct chunk *c100 = allocate(100 * 1024);
    printf("ask for 100kb allocate\n");
    check();

    struct chunk *c256 = allocate(256 * 1024);
    printf("ask for 256kb allocate\n");
    check();

    struct chunk *c500 = allocate(500 * 1024);
    printf("ask for 500kb allocate\n");
    check();


    release(c100);
    printf("release c100\n");
    check();

    release(c256);
    printf("release c256\n");
    check();

    release(c500);
    printf("release c500\n");
    check();
}