内存分配器 (malloc/free) 是 libc 的核心组件，负责管理程序运行时动态申请和释放内存的过程。在多处理器系统中，内存分配器面临更大的挑战：运行在多个处理器上的多个线程可能同时请求分配或释放内存，我们当然希望多个处理器上的 malloc 和 free 都可以并行执行，以获得更好的性能。与此同时，mmap 给我们的 "大段" 内存必须用合适的数据结构管理，数据结构的并发访问又需要小心的并发控制。
实现多处理器安全的内存分配器，包括以下两个函数：
void *mymalloc(size_t size); // 内存分配
void myfree(void *ptr); // 内存释放你的 malloc/free 实现允许使用以下两个函数（框架代码中提供了实现）：
void *vmalloc(void *addr, size_t length); // length 必须是 4096 的倍数
void vmfree(void *addr, size_t length);它们是 mmap 和 munmap 的封装，允许你申请和释放大块的内存。你可以在操作系统允许的范围内自由使用它们——vmalloc 成功会返回一段长度为 length 的可读、可写的内存；vmfree 会释放这段内存。除此之外，你提交的代码不能使用任何其他库函数（freestanding 环境）。
- 原子性：当多个处理器同时请求内存分配或释放时，分配器必须确保同时进行的分配/回收操作能够正确完成。注意，在一个处理器上分配的内存，可能在另一个处理器上被释放。
- 无重叠：分配器返回的内存块之间不能有重叠。每次调用 mymalloc 时，它必须返回一个独特的内存区域，该区域在其生命周期内不与任何其他分配的内存块共享地址空间。
- 对齐：内存为 8 字节对齐，即 mymalloc 返回地址的低 3 位必须总是 0。
- 无内存泄漏：使用 myfree 释放的内存应当支持重用，而不是成为无法再分配的 "死内存"。这意味着分配器需要准确跟踪哪些内存是空闲的，哪些是已分配的。
- 错误处理：当无法满足内存分配请求时（例如，因为没有足够的空闲内存），mymalloc 应该返回 NULL (0)。
💡 注意：不必初始化返回的内存（libc 的 malloc 为了性能并不清除内存），当然，对返回的内存赋上初始值（例如零）也许是个不错的主意。
对于简单的需求，为了实现线程安全性，只要借助框架代码中实现的自旋锁，"一把大锁保平安" 就可以了。在本次实验中，你只能使用自旋的方式实现互斥，不得调用 pthreads 等库。
我们希望你的分配器应该尽量高效地使用内存，减少碎片，同时保持快速的分配和释放操作：
- 在 mymalloc/myfree 实现正确的前提下，尽可能使不同处理器上的内存分配能够并行。
- 受分配算法的局限，可能系统中仍然有空闲的内存，但形成了碎片的内存，或是你的算法不能找到它从而分配失败。这是允许的；但在系统内存压力很小的时候依然频繁分配失败，可能导致 hard test failure。
- 如果你代码的性能过低（例如用全局的锁保护空闲链表，并用遍历链表的方式寻找可用的内存），可能会导致 hard test failure。
回顾多处理器上的内存分配和释放带来额外的挑战：
- 正确性：用一把大锁保护一个串行数据结构（例如算法导论上的 "区间树" 就能在 O(log n) 的时间内完成分配和释放操作）就能正确实现多处理器上的内存分配。
- 性能和扩展性 (scalability)：不同的处理器能够并行地申请内存，尽可能减少因为同时申请而发生一个处理器等另一个处理器的情况。
上面两点需求是矛盾的，这也是本次实验的重点挑战。在这个实验里，我们通过 "system" 的方法解决问题，而不是巧妙的算法/数据结构。
☕️ 不要使用区间树：树型的数据结构很容易在并行时遇到瓶颈——虽然不代表你不能实现高效的树型数据结构，但现代流行的内存分配器都使用了更简单、更 "system" 的方式解决问题：我们观察实际操作系统中内存分配的模式，提出最佳的算法。
基于 vmalloc/vmfree 分配 "大区间的内存"，在可用的内存（区间）上实现数据结构（抽象数据类型），维护一个不相交区间的集合（堆区）：
初始时，$H = \emptyset$。对于任意时刻的当前堆区
分配
- 分配发生在堆区中：$L \leq \ell < r < R$
- 分配的内存不与已分配内存重叠：$\forall [\ell_i, r_i) \in H.\ [\ell, r) \cap [\ell_i, r_i) = \emptyset$
- 分配后新的堆区：$H' = H \cup {[\ell, r)}$
- 返回分配区间的左端点
$\ell$
删除一个已有区间
当