动态分区分配算法的模拟

动态分区分配算法是一种内存分配方式，它将内存分为若干个大小不等的分区，每个分区可以被分配给一个进程使用。常见的动态分区分配算法有首次适应算法、最佳适应算法和最坏适应算法等。下面是首次适应算法的模拟过程：

// 定义空闲分区结构体
typedef struct free_block {
    int size;  // 空闲分区大小
    struct free_block *next;  // 指向下一个空闲分区
} FreeBlock;

// 定义已分配分区结构体
typedef struct allocated_block {
    int size;  // 已分配分区大小
    int pid;  // 进程ID
    struct allocated_block *next;  // 指向下一个已分配分区
} AllocBlock;

// 定义空闲分区链表头指针
FreeBlock *free_block_head = NULL;

// 定义已分配分区链表头指针
AllocBlock *alloc_block_head = NULL;

// 首次适应算法分配内存
void *alloc_mem_first_fit(int size, int pid) {
    FreeBlock *p = free_block_head;
    FreeBlock *prev = NULL;
    while (p != NULL) {
        if (p->size >= size) {  // 找到合适的空闲分区
            AllocBlock *alloc_block = (AllocBlock *)malloc(sizeof(AllocBlock));            alloc_block->size = size;
            alloc_block->pid = pid;
            alloc_block->next = alloc_block_head;
            alloc_block_head = alloc_block;
            if (p->size == size) {  // 空闲分区大小刚好等于所需大小
                if (prev == NULL) {
                    free_block_head = p->next;
                } else {
                    prev->next = p->next;
                }
                free(p);
            } else {  // 空闲分区大小大于所需大小
                p->size -= size;
            }
            return (void *)alloc_block;
        }
        prev = p;
        p = p->next;
    }
    return NULL;  // 没有找到合适的空闲分区
}

// 回收内存
void free_mem(void *ptr) {
    AllocBlock *p = (AllocBlock *)ptr;
    AllocBlock *prev = NULL;
    while (p != NULL) {
        if (p == alloc_block_head) {
            alloc_block_head = p->next;
        } else {
            prev->next = p->next;
        }
        FreeBlock *free_block = (FreeBlock *)malloc(sizeof(FreeBlock));
        free_block->size = p->size;
        free_block->next = NULL;
        FreeBlock *q = free_block_head;
        FreeBlock *q_prev = NULL;
        while (q != NULL && q < free_block) {
            q_prev = q;
            q = q->next;
        }
        if (q == NULL) {  // 插入到链表尾部
            if (q_prev == NULL) {
                free_block_head = free_block;
            } else {
                q_prev->next = free_block;
            }
        } else {  // 插入到链表中间
            if (q_prev == NULL) {
                free_block_head = free_block;
            } else {
                q_prev->next = free_block;
            }
            free_block->next = q;
        }
        prev = p;
        p = p->next;
        free(prev);
    }
}