伙伴系统算法的c语言实现,数据结构C语言版 伙伴系统

伙伴系统（Buddy System）是一种动态内存分配算法，它的主要思想是将内存空间划分为一些大小相等的块，每个块的大小为2的幂次方，且每个块的大小是相邻两个块大小的二分之一。这样，内存中的所有块大小都是2的幂次方，且相邻块大小之间的比例为1:2。

伙伴系统分配内存时，首先按照内存大小找到对应的块。如果找到的块正好可以分配给用户，那么就直接将该块分配给用户；如果找到的块比用户所需的块大，那么就将该块分成两个大小相等的块，其中一个块分配给用户，另一个块留作备用。如果备用块大小正好与用户所需的块大小相等，那么就直接将备用块分配给用户；否则就将备用块继续分成两个大小相等的块，其中一个块分配给用户，另一个块留作备用。这样，直到找到一个大小正好能够分配给用户的块或者无法再次分割备用块为止。

以下是基于C语言实现的伙伴系统算法：

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

#define MAX_SIZE 1024  // 内存最大大小
#define MIN_SIZE 4     // 内存最小大小
#define FREE 0         // 空闲块
#define BUSY 1         // 忙碌块

struct block {
  int size;         // 块大小
  int status;       // 块状态
  int buddy;        // 伙伴块位置
};

static struct block mem[MAX_SIZE];   // 内存块数组

// 打印内存块信息
void print_mem() {
  int i;

  printf("Memory Map:\n");
  for (i = 0; i < MAX_SIZE; i += mem[i].size) {
    printf("[%d:%d:%d] ", i, mem[i].size, mem[i].status);
  }
  printf("\n");
}

// 求以2为底的对数
int log2(int n) {
  int k = 0;

  while (n > 1) {
    n /= 2;
    k++;
  }

  return k;
}

// 求大于等于n的最小2的幂次方
int ceil2(int n) {
  return pow(2, ceil(log2(n)));
}

// 初始化内存块数组
void init_mem() {
  int i, size;

  // 初始化内存块
  for (i = 0, size = MAX_SIZE; size >= MIN_SIZE; size /= 2) {
    mem[i].size = size;
    mem[i].status = FREE;
    mem[i].buddy = -1;
    i += size;
  }
}

// 合并空闲块
void merge(int p) {
  int q;

  // 找到伙伴块位置
  q = p ^ mem[p].size;

  // 判断伙伴块是否为空闲块
  if (mem[q].status == FREE && mem[q].size == mem[p].size) {
    // 合并块
    mem[p].size *= 2;
    mem[q].status = BUSY;
    mem[p].buddy = -1;
    mem[q].buddy = -1;
    merge(p);
  }
}

// 分配内存块
int alloc(int size) {
  int p, q, k;

  // 找到第一个大小大于等于size的空闲块
  for (p = 0; p < MAX_SIZE && (mem[p].size < size || mem[p].status == BUSY); p += mem[p].size);

  // 如果找到空闲块
  if (p < MAX_SIZE) {
    k = log2(mem[p].size) - log2(size);

    while (k >= 0) {
      q = p ^ (1 << k);

      // 如果伙伴块为空闲块或伙伴块大小小于size，则不再分割
      if (mem[q].status == BUSY || mem[q].size < size) {
        k--;
      } else {
        // 分割块
        mem[q].status = BUSY;
        mem[p].buddy = q;
        mem[q].buddy = p;
        mem[q].size = mem[p].size / 2;
        mem[p].size /= 2;
        k--;
        merge(p);
      }
    }

    mem[p].status = BUSY;
    mem[p].buddy = -1;

    return p;
  } else {
    // 没有空闲块可用
    return -1;
  }
}

// 释放内存块
void free_mem(int p) {
  int q;

  mem[p].status = FREE;

  // 递归合并块
  while (p >= 0) {
    // 找到伙伴块位置
    q = p ^ mem[p].size;

    // 如果伙伴块为空闲块，则合并块
    if (mem[q].status == FREE) {
      // 分割块
      mem[p].size *= 2;
      mem[q].status = BUSY;
      mem[p].buddy = -1;
      mem[q].buddy = -1;
      p = (p < q ? p : q);
    } else {
      break;
    }
  }
}

int main() {
  int p, size;

  // 初始化内存块数组
  init_mem();

  // 打印初始内存块状态
  print_mem();

  // 分配内存
  size = 16;
  p = alloc(size);
  printf("Alloc %d bytes at position %d.\n", size, p);
  print_mem();

  // 分配内存
  size = 32;
  p = alloc(size);
  printf("Alloc %d bytes at position %d.\n", size, p);
  print_mem();

  // 释放内存
  free_mem(p);
  printf("Free block at position %d.\n", p);
  print_mem();

  // 分配内存
  size = 64;
  p = alloc(size);
  printf("Alloc %d bytes at position %d.\n", size, p);
  print_mem();

  return 0;
}

以上是伙伴系统算法的C语言实现，可以用来动态分配内存。