## 实验二：内存分配

### 实验之前

- 阅读实验指导二。
- checkout 到仓库中的 `lab-2` 分支，实验题将以此展开。

### 实验题

1.  原理：.bss 字段是什么含义？为什么我们要将动态分配的内存（堆）空间放在 .bss 字段？

    {% reveal %}
> 对于一个 ELF 程序文件而言，.bss 字段一般包含全局变量的名称和长度，在执行时由操作系统分配空间并初始化为零。
>
> *不过，在我们执行 `rust-objcopy` 时，不同的字段会相应地被处理而形成一段连续的二进制数据，这段二进制数据会直接写入到 QEMU 所模拟的机器的 `0x80200000` 位置。这是因为我们写的操作系统是直接运行在机器上的，而不是一个被操作系统加载的程序。*
>
> 我们一般遇到应用程序的动态内存分配（堆）是由其操作系统提供的。例如在 C 语言中的 `malloc()`，glibc 运行库会维护一个堆空间，而这个空间是通过 `brk()` 等系统调用向内核索要的。由于我们编写操作系统，自然就无法像这样获取空间。但是此时我们具有随意使用内存空间的权力，因此我们可以在内存中随意划一段空间，然后用相应的算法来实现一个堆。
>
> 至于为何堆在 .bss 字段，实际上这也不是必须的——我们完全可以随意指定一段可以访问的内存空间。不过，在代码中用全局变量来表示堆并将其放在 .bss 字段，是一个很简单的实现：这样堆空间就包含在内核的二进制数据之中了，而自 `KERNEL_END_ADDRESS` 以后的空间就都可以给进程使用。
    {% endreveal %}

    <br>
2.  分析：我们在动态内存分配中实现了一个堆，它允许我们在内核代码中使用动态分配的内存，例如 `Vec` `Box` 等。那么，如果我们在实现这个堆的过程中使用 `Vec` 而不是 `[u8]`，会出现什么结果？

    - 无法编译？

    - 运行时错误？

    - 正常运行？
    <br>

    {% reveal %}
> **都不会！**程序会陷入一个循环：它需要在堆上分配空间，但是分配器又需要在堆上分配空间……
    {% endreveal %}

    <br>
3.  实验
    1.  回答：`algorithm/src/allocator` 下有一个 `Allocator` trait，我们之前用它实现了物理页面分配。这个算法的时间和空间复杂度是什么？

        {% reveal %}
> 时间复杂度是 O(1)，空间复杂度是 O(n)
        {% endreveal %}

        <br>
    2.  二选一：实现基于线段树的物理页面分配算法（不需要考虑合并分配）；或尝试修改 `FrameAllocator`，令其使用未被分配的页面空间（而不是全局变量）来存放页面使用状态。

    <br>
4.  挑战实验（选做）
    1.  在 `memory/heap2.rs` 中，提供了一个手动实现堆的方法。它使用 `algorithm::VectorAllocator` 作为其根本分配算法，而我们目前提供了一个非常简单的 bitmap 算法（而且只开了很小的空间）。请在 `algorithm` crate 中利用伙伴算法实现 `VectorAllocator` trait。

        <br>
    2.  前面说到，堆的实现本身不能完全使用动态内存分配。但有没有可能让堆能够利用动态分配的空间，这样做会带来什么好处？

        {% reveal %}
> 我们以一个朴素的分配器算法为例：将每一次内存分配记录用链表存起来。
>
> 分配器最初必须具有一个节点的静态空间。而每当它仅剩一个节点空间时，都可以用它来为自己分配一块更大的空间。如此，就实现了分配器动态分配自己。
>
> 再考虑到，每次分配 1KB 或 1MB 都需要额外保存一份元信息。如果只用静态分配，就必须按最坏情况（每次都只分配最小单元）来预先留好空间。使用动态分配就可以减少空间浪费。
        {% endreveal %}
