02. 连续分配管理

连续分配管理方式

连续分配是指为进程分配一块连续的内存空间。这种分配方式简单直观，但容易产生内存碎片问题。

单一连续分配

基本原理

单一连续分配是最简单的内存分配方式，整个内存空间只分配给一个进程使用。

内存布局

┌─────────────────────────────────────┐
│              操作系统                │
├─────────────────────────────────────┤
│              用户程序                │
├─────────────────────────────────────┤
│              空闲区域                │
└─────────────────────────────────────┘

特点分析

优点：

• 实现简单，管理开销小
• 地址转换简单，只需基址寄存器
• 适合单道程序系统

缺点：

• 内存利用率低
• 不支持多道程序设计
• 程序大小受内存限制

实现示例

// 单一连续分配的内存管理
typedef struct {
    int base;          // 程序基址
    int limit;         // 程序长度
    int total_memory;  // 总内存大小
} SingleContiguousMemory;

void init_memory(SingleContiguousMemory *mem, int total) {
    mem->total_memory = total;
    mem->base = 0;
    mem->limit = 0;
}

int load_program(SingleContiguousMemory *mem, int program_size) {
    if (program_size > mem->total_memory) {
        return -1;  // 程序太大，无法装入
    }

    mem->base = 0;
    mem->limit = program_size;
    return 0;
}

int address_translation(int logical_addr, SingleContiguousMemory *mem) {
    if (logical_addr >= mem->limit) {
        return -1;  // 地址越界
    }
    return mem->base + logical_addr;
}

固定分区分配

基本原理

将内存空间划分为若干个固定大小的分区，每个分区分配给一个进程。

分区表结构

typedef struct {
    int start_addr;    // 分区起始地址
    int size;          // 分区大小
    int status;        // 分区状态：0-空闲，1-已分配
    int process_id;    // 占用进程ID
} Partition;

#define MAX_PARTITIONS 10
Partition partition_table[MAX_PARTITIONS];
int partition_count;

分区分配算法

1. 首次适应算法（First Fit）

int first_fit_allocate(int process_size, int process_id) {
    for (int i = 0; i < partition_count; i++) {
        if (partition_table[i].status == 0 &&
            partition_table[i].size >= process_size) {
            partition_table[i].status = 1;
            partition_table[i].process_id = process_id;
            return partition_table[i].start_addr;
        }
    }
    return -1;  // 没有合适的分区
}

2. 最佳适应算法（Best Fit）

int best_fit_allocate(int process_size, int process_id) {
    int best_index = -1;
    int min_fragment = INT_MAX;

    for (int i = 0; i < partition_count; i++) {
        if (partition_table[i].status == 0 &&
            partition_table[i].size >= process_size) {
            int fragment = partition_table[i].size - process_size;
            if (fragment < min_fragment) {
                min_fragment = fragment;
                best_index = i;
            }
        }
    }

    if (best_index != -1) {
        partition_table[best_index].status = 1;
        partition_table[best_index].process_id = process_id;
        return partition_table[best_index].start_addr;
    }
    return -1;
}

3. 最坏适应算法（Worst Fit）

int worst_fit_allocate(int process_size, int process_id) {
    int worst_index = -1;
    int max_fragment = -1;

    for (int i = 0; i < partition_count; i++) {
        if (partition_table[i].status == 0 &&
            partition_table[i].size >= process_size) {
            int fragment = partition_table[i].size - process_size;
            if (fragment > max_fragment) {
                max_fragment = fragment;
                worst_index = i;
            }
        }
    }

    if (worst_index != -1) {
        partition_table[worst_index].status = 1;
        partition_table[worst_index].process_id = process_id;
        return partition_table[worst_index].start_addr;
    }
    return -1;
}

算法比较

可变分区分配

基本原理

根据进程的实际需要动态划分内存空间，避免固定分区造成的内碎片。

空闲分区表

typedef struct {
    int start_addr;    // 起始地址
    int size;          // 分区大小
    int next;          // 下一个空闲分区索引
} FreePartition;

#define MAX_FREE_PARTITIONS 100
FreePartition free_table[MAX_FREE_PARTITIONS];
int free_count;
int free_head;  // 空闲分区链表头

分配算法实现

1. 首次适应算法

int first_fit_allocate_variable(int process_size, int process_id) {
    int current = free_head;
    int prev = -1;

    while (current != -1) {
        if (free_table[current].size >= process_size) {
            // 找到合适的分区
            int allocated_addr = free_table[current].start_addr;

            if (free_table[current].size == process_size) {
                // 完全匹配，删除该空闲分区
                if (prev == -1) {
                    free_head = free_table[current].next;
                } else {
                    free_table[prev].next = free_table[current].next;
                }
            } else {
                // 分割分区
                free_table[current].start_addr += process_size;
                free_table[current].size -= process_size;
            }

            return allocated_addr;
        }

        prev = current;
        current = free_table[current].next;
    }

    return -1;  // 没有合适的分区
}

2. 最佳适应算法

int best_fit_allocate_variable(int process_size, int process_id) {
    int current = free_head;
    int best_index = -1;
    int min_fragment = INT_MAX;

    while (current != -1) {
        if (free_table[current].size >= process_size) {
            int fragment = free_table[current].size - process_size;
            if (fragment < min_fragment) {
                min_fragment = fragment;
                best_index = current;
            }
        }
        current = free_table[current].next;
    }

    if (best_index != -1) {
        int allocated_addr = free_table[best_index].start_addr;

        if (free_table[best_index].size == process_size) {
            // 删除该空闲分区
            remove_free_partition(best_index);
        } else {
            // 分割分区
            free_table[best_index].start_addr += process_size;
            free_table[best_index].size -= process_size;
        }

        return allocated_addr;
    }

    return -1;
}

3. 循环首次适应算法

int next_fit_allocate(int process_size, int process_id) {
    static int last_allocated = 0;  // 上次分配的位置
    int start = last_allocated;
    int current = start;

    do {
        if (free_table[current].size >= process_size) {
            // 找到合适的分区
            int allocated_addr = free_table[current].start_addr;
            last_allocated = current;

            if (free_table[current].size == process_size) {
                remove_free_partition(current);
            } else {
                free_table[current].start_addr += process_size;
                free_table[current].size -= process_size;
            }

            return allocated_addr;
        }

        current = free_table[current].next;
        if (current == -1) current = free_head;
    } while (current != start);

    return -1;
}

内存回收

void free_memory(int start_addr, int size) {
    // 查找插入位置
    int current = free_head;
    int prev = -1;

    while (current != -1 && free_table[current].start_addr < start_addr) {
        prev = current;
        current = free_table[current].next;
    }

    // 创建新的空闲分区
    int new_index = get_free_slot();
    free_table[new_index].start_addr = start_addr;
    free_table[new_index].size = size;

    // 插入到链表中
    if (prev == -1) {
        free_table[new_index].next = free_head;
        free_head = new_index;
    } else {
        free_table[new_index].next = free_table[prev].next;
        free_table[prev].next = new_index;
    }

    // 合并相邻的空闲分区
    merge_adjacent_partitions();
}

void merge_adjacent_partitions() {
    int current = free_head;

    while (current != -1 && free_table[current].next != -1) {
        int next = free_table[current].next;

        if (free_table[current].start_addr + free_table[current].size ==
            free_table[next].start_addr) {
            // 合并相邻分区
            free_table[current].size += free_table[next].size;
            free_table[current].next = free_table[next].next;
            free_table[next].size = 0;  // 标记为无效
        } else {
            current = free_table[current].next;
        }
    }
}

内存碎片问题

碎片类型

1. 内碎片

• 分配给进程的内存块中未被使用的部分
• 固定分区分配中常见
• 无法被其他进程使用

2. 外碎片

• 内存中无法分配给任何进程的小块空闲区域
• 可变分区分配中常见
• 可以通过内存紧凑解决

内存紧凑

void memory_compaction() {
    // 将所有进程移动到内存低端
    int new_addr = 0;

    for (int i = 0; i < process_count; i++) {
        if (process_table[i].status == 1) {
            int old_addr = process_table[i].start_addr;
            int size = process_table[i].size;

            // 移动进程
            memmove((void*)new_addr, (void*)old_addr, size);

            // 更新进程地址
            process_table[i].start_addr = new_addr;
            new_addr += size;
        }
    }

    // 重新整理空闲分区表
    rebuild_free_table(new_addr);
}

伙伴系统

基本原理

将内存划分为大小为 2^k 的块，分配时找到最接近的 2^k 块，避免产生过多碎片。

实现示例

#define MAX_ORDER 10
#define PAGE_SIZE 4096

typedef struct {
    int order;         // 块大小级别
    int start_addr;    // 起始地址
    int status;        // 状态：0-空闲，1-已分配
} BuddyBlock;

BuddyBlock buddy_table[1 << MAX_ORDER];
int free_lists[MAX_ORDER + 1];  // 各大小级别的空闲链表

void init_buddy_system() {
    // 初始化伙伴系统
    int total_pages = (1 << MAX_ORDER);

    for (int i = 0; i < total_pages; i++) {
        buddy_table[i].order = 0;
        buddy_table[i].start_addr = i * PAGE_SIZE;
        buddy_table[i].status = 0;
    }

    // 初始化空闲链表
    for (int i = 0; i <= MAX_ORDER; i++) {
        free_lists[i] = -1;
    }

    // 将最大块加入空闲链表
    free_lists[MAX_ORDER] = 0;
}

int buddy_allocate(int size) {
    int order = get_order(size);

    // 查找合适大小的空闲块
    for (int i = order; i <= MAX_ORDER; i++) {
        if (free_lists[i] != -1) {
            return split_and_allocate(i, order);
        }
    }

    return -1;  // 没有足够的空闲空间
}

int get_order(int size) {
    int order = 0;
    int page_count = (size + PAGE_SIZE - 1) / PAGE_SIZE;

    while ((1 << order) < page_count) {
        order++;
    }

    return order;
}

int split_and_allocate(int large_order, int target_order) {
    if (large_order == target_order) {
        // 直接分配
        int block_index = free_lists[large_order];
        free_lists[large_order] = buddy_table[block_index].next;
        buddy_table[block_index].status = 1;
        return buddy_table[block_index].start_addr;
    }

    // 分割块
    int block_index = free_lists[large_order];
    free_lists[large_order] = buddy_table[block_index].next;

    // 创建两个伙伴块
    int buddy_index = block_index + (1 << (large_order - 1));

    buddy_table[block_index].order = large_order - 1;
    buddy_table[buddy_index].order = large_order - 1;
    buddy_table[block_index].status = 0;
    buddy_table[buddy_index].status = 0;

    // 将伙伴块加入空闲链表
    buddy_table[buddy_index].next = free_lists[large_order - 1];
    free_lists[large_order - 1] = buddy_index;

    // 递归分配
    return split_and_allocate(large_order - 1, target_order);
}

实际应用

Linux 伙伴系统

Linux 内核使用伙伴系统管理物理内存页框：

// Linux内核中的伙伴系统
struct zone {
    struct free_area free_area[MAX_ORDER];
    // ...
};

struct free_area {
    struct list_head free_list[MIGRATE_TYPES];
    unsigned long *map;
    unsigned long count;
};

Windows 内存管理

Windows 使用分页内存管理，但也保留了连续分配的概念：

// Windows内存分配
LPVOID VirtualAlloc(
    LPVOID lpAddress,
    SIZE_T dwSize,
    DWORD flAllocationType,
    DWORD flProtect
);

总结

连续分配管理方式是内存管理的基础，从简单的单一连续分配到复杂的伙伴系统，每种方式都有其适用场景。选择合适的分配算法对于提高内存利用率和系统性能至关重要。现代操作系统通常结合多种分配方式，以满足不同应用的需求。