操作系统概念第七版习题 3.10 代码详解

3.10题目要求我们实现一个简单的“内存分配器”，可以动态地分配和释放内存。以下是代码详解。

首先，我们需要定义一个结构体`Block`，用于表示内存块。

struct Block {
    int size; // 内存块大小
    bool free; // 内存块是否空闲
    struct Block *next; // 指向下一个内存块
};

其中，`size`表示内存块大小，`free`表示内存块是否空闲，`next`指向下一个内存块。

然后，我们需要定义一个全局变量`head`，表示内存块链表的头指针。

struct Block *head = NULL;

接下来，我们需要实现两个函数：`malloc()`和`free()`。这两个函数的功能与标准库中的`malloc()`和`free()`相似。

首先，我们来看`malloc()`函数的实现。

void *malloc(int size) {
    struct Block *p, *prev;
    void *mem;
    p = head;
    while (p != NULL) {
        if (p->free && p->size >= size) {
            p->free = false;
            mem = (void *)(p + 1); // 指向内存块之后的空间
            return mem;
        }
        prev = p;
        p = p->next;
    }
    // 没有合适的内存块，需要分配新的内存
    p = sbrk(sizeof(struct Block) + size); // 分配内存
    if (p == (void *)-1) { // 分配失败
        return NULL;
    }
    p->size = size;
    p->free = false;
    p->next = NULL;
    if (head == NULL) { // 如果链表为空，将p设置为头指针
        head = p;
    } else { // 否则插入到链表末尾
        prev->next = p;
    }
    mem = (void *)(p + 1); // 指向内存块之后的空间
    return mem;
}

`malloc()`函数接受一个整数参数`size`，表示需要分配的内存大小。

首先，我们定义了两个指针变量`p`和`prev`，分别指向当前遍历到的内存块和上一个内存块。然后，我们将`p`初始化为链表头指针。

接下来，我们使用一个`while`循环遍历整个内存块链表。对于每个内存块，我们判断它是否空闲，并且大小是否足够。如果满足条件，我们将该内存块标记为已占用，然后返回指向内存块之后空间的指针。

如果遍历完整个链表都没有找到合适的内存块，我们需要分配新的内存。我们使用`brk()`系统调用分配一块大小为`sizeof(struct Block) + size`的内存，其中`sizeof(struct Block)`表示内存块结构体的大小。如果分配失败，`brk()`将返回`-1`，于是我们返回`NULL`表示分配失败。

如果分配成功，我们将新分配的内存块初始化，并将其插入到链表末尾。如果链表为空，我们将该内存块设置为链表头指针。最后，我们返回指向内存块之后空间的指针。

接下来，我们来看`free()`函数的实现。

void free(void *ptr) {
    struct Block *p;
    p = (struct Block *)ptr - 1; // 获取内存块指针
    p->free = true; // 标记为空闲
}

`free()`函数接受一个指针参数`ptr`，表示需要释放的内存块指针。

首先，我们将该指针转换为一个`struct Block`类型的指针，然后将该内存块标记为已空闲。

这样，我们就完成了简单的内存分配器的实现。注意，这个实现仅仅是为了演示内存分配器的基本原理和实现方式，并不适用于实际生产环境中。在实际生产环境中，应该使用更加健壮和高效的内存分配器，例如`malloc()`和`free()`函数所使用的系统默认内存分配器。