面试题：C语言内存分配中的内存碎片问题及解决方案

内存碎片产生原因

分配和释放的不一致：当频繁分配不同大小的内存块，并且这些内存块的释放顺序与分配顺序不一致时，会导致内存空间不能被有效利用。例如，先分配三个连续的小内存块A、B、C，然后释放B，此时A和C之间就会留下一个空闲块，若后续需要分配的内存块大小大于这个空闲块，该空闲块就无法被利用，形成碎片。
内存对齐：在C语言中，内存分配通常要满足一定的对齐要求（如4字节对齐、8字节对齐等）。这意味着即使实际需要的内存空间较小，但由于对齐要求，分配的内存块可能会比实际需求大一些。当这些内存块被释放后，剩余的空闲空间可能因为对齐限制无法被后续分配使用，从而产生碎片。

对程序的影响

内存利用率降低：内存碎片使得可用内存空间变得零散，导致程序在需要分配较大内存块时，尽管总的空闲内存足够，但由于碎片的存在无法分配成功，浪费了内存资源。
性能下降：频繁的内存分配和释放操作，以及寻找合适内存块的过程，会增加CPU的开销，降低程序的运行效率。同时，内存碎片还可能导致虚拟内存系统频繁换页，进一步影响性能。

减少或避免内存碎片的方法

1. 内存池（Memory Pool）

内存池是一种预先分配一定数量和大小的内存块的技术，程序在需要内存时从内存池中获取，释放时再归还到内存池中。这样可以减少系统级别的内存分配和释放次数，从而减少碎片。

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

#define POOL_SIZE 10
#define BLOCK_SIZE 100

// 内存块结构体
typedef struct MemoryBlock {
    struct MemoryBlock* next;
} MemoryBlock;

// 内存池结构体
typedef struct MemoryPool {
    MemoryBlock* freeList;
} MemoryPool;

// 创建内存池
MemoryPool* createMemoryPool() {
    MemoryPool* pool = (MemoryPool*)malloc(sizeof(MemoryPool));
    pool->freeList = NULL;

    for (int i = 0; i < POOL_SIZE; i++) {
        MemoryBlock* block = (MemoryBlock*)malloc(BLOCK_SIZE);
        block->next = pool->freeList;
        pool->freeList = block;
    }
    return pool;
}

// 从内存池获取内存块
void* allocateFromPool(MemoryPool* pool) {
    if (pool->freeList == NULL) {
        return NULL;
    }
    MemoryBlock* block = pool->freeList;
    pool->freeList = block->next;
    return block;
}

// 归还内存块到内存池
void freeToPool(MemoryPool* pool, void* block) {
    ((MemoryBlock*)block)->next = pool->freeList;
    pool->freeList = (MemoryBlock*)block;
}

// 销毁内存池
void destroyMemoryPool(MemoryPool* pool) {
    MemoryBlock* current = pool->freeList;
    MemoryBlock* next;
    while (current != NULL) {
        next = current->next;
        free(current);
        current = next;
    }
    free(pool);
}

int main() {
    MemoryPool* pool = createMemoryPool();
    void* block1 = allocateFromPool(pool);
    void* block2 = allocateFromPool(pool);
    freeToPool(pool, block1);
    void* block3 = allocateFromPool(pool);
    destroyMemoryPool(pool);
    return 0;
}

2. 伙伴算法（Buddy Algorithm）

伙伴算法是一种用于管理内存空间的算法，它将内存空间划分为不同大小的块，并通过特定的规则来合并和分配这些块，以减少碎片。

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

#define MAX_ORDER 10
#define BASE_SIZE (1 << MAX_ORDER)

typedef struct BuddyBlock {
    int order;
    struct BuddyBlock* next;
    char data[BASE_SIZE];
} BuddyBlock;

typedef struct BuddySystem {
    BuddyBlock* freeLists[MAX_ORDER + 1];
} BuddySystem;

// 创建伙伴系统
BuddySystem* createBuddySystem() {
    BuddySystem* system = (BuddySystem*)malloc(sizeof(BuddySystem));
    memset(system->freeLists, 0, sizeof(system->freeLists));

    // 初始化最大块
    BuddyBlock* root = (BuddyBlock*)malloc(sizeof(BuddyBlock));
    root->order = MAX_ORDER;
    root->next = NULL;
    system->freeLists[MAX_ORDER] = root;
    return system;
}

// 分配内存块
void* allocateBuddyBlock(BuddySystem* system, int order) {
    if (order < 0 || order > MAX_ORDER) {
        return NULL;
    }

    BuddyBlock* block = system->freeLists[order];
    if (block != NULL) {
        system->freeLists[order] = block->next;
        return block;
    }

    for (int i = order + 1; i <= MAX_ORDER; i++) {
        if (system->freeLists[i] != NULL) {
            block = system->freeLists[i];
            system->freeLists[i] = block->next;
            for (int j = i - 1; j >= order; j--) {
                BuddyBlock* newBlock = (BuddyBlock*)((char*)block + (1 << j));
                newBlock->order = j;
                newBlock->next = system->freeLists[j];
                system->freeLists[j] = newBlock;
            }
            return block;
        }
    }
    return NULL;
}

// 释放内存块
void freeBuddyBlock(BuddySystem* system, void* block) {
    BuddyBlock* buddyBlock = (BuddyBlock*)block;
    int order = buddyBlock->order;
    while (order < MAX_ORDER) {
        BuddyBlock* buddy = (BuddyBlock*)((char*)buddyBlock ^ (1 << order));
        int found = 0;
        BuddyBlock* prev = NULL;
        BuddyBlock* current = system->freeLists[order];
        while (current != NULL) {
            if (current == buddy) {
                found = 1;
                if (prev == NULL) {
                    system->freeLists[order] = current->next;
                } else {
                    prev->next = current->next;
                }
                break;
            }
            prev = current;
            current = current->next;
        }
        if (!found) {
            break;
        }
        order++;
        buddyBlock = (order == 0)? buddyBlock : (BuddyBlock*)((char*)buddyBlock < (char*)buddy? buddyBlock : buddy);
    }
    buddyBlock->order = order;
    buddyBlock->next = system->freeLists[order];
    system->freeLists[order] = buddyBlock;
}

// 销毁伙伴系统
void destroyBuddySystem(BuddySystem* system) {
    for (int i = 0; i <= MAX_ORDER; i++) {
        BuddyBlock* current = system->freeLists[i];
        BuddyBlock* next;
        while (current != NULL) {
            next = current->next;
            free(current);
            current = next;
        }
    }
    free(system);
}

int main() {
    BuddySystem* system = createBuddySystem();
    void* block1 = allocateBuddyBlock(system, 3);
    void* block2 = allocateBuddyBlock(system, 2);
    freeBuddyBlock(system, block1);
    void* block3 = allocateBuddyBlock(system, 4);
    destroyBuddySystem(system);
    return 0;
}

星途面试题库

面试题：C语言内存分配中的内存碎片问题及解决方案

知识考点

面试题答案

内存碎片产生原因

对程序的影响

减少或避免内存碎片的方法

1. 内存池（Memory Pool）

2. 伙伴算法（Buddy Algorithm）