使用数据结构作为工作内存的一部分实现特殊的分配和释放方法

Question

您将获得一段内存，例如 1MB，以及一个指向该内存开头的指针

P

您需要实施

void * alloc()

和

void free(void* p)

Alloc

正在分配一块16B的内存块并返回一个指向它开头的指针

Free

接收指向块开头的指针并释放其内存，注意它可以位于给定块中的任何位置

您可以假设调用这些方法总是在

alloc

有空间时调用，对于

free

也是如此，它将始终在块中，因此无需处理此类边缘情况

问题是分配和释放数据结构应该是给定块的一部分。

我尝试的解决方案是使用位图，使每个位都指向一个特定的块，这将占用 2^13B 空间，因为 2^20B/2^4B/2^3B=(总/块大小/位数每个字节）=8192，几乎是 2^20 的 1%。

此外，这意味着

alloc

查找 0 位的运行时间将为 O(n)，而

free

的运行时间将为 O(1)。

问题是，如何使用 O(1) 运行时间来实现

alloc

和

free

并拥有 0% 的已用内存？

请注意，这是一个练习，与语言或操作系统无关。

Answer 1

要实现

O(1) runtime

和

alloc

且内存浪费为 0%，请使用

free

方法。将

segregated free list

分成固定大小的块，每个块要么已分配，要么是空闲列表的一部分。

设置：

从 1MB 内存块开始。

memory block

一个

Initialize

来管理空闲块，包含

"free list header"

到

pointers

用于不同的块大小。

free lists 功能：

根据

alloc

找到合适的

free list

如果存在空闲块，则分配它；否则，分割一个较大的块，添加到较小的列表，然后返回另一个。在恒定时间内访问和更新空闲列表的链表。

block size. 功能：

根据大小计算块的空闲列表。 将块添加到相应的

free

操作中。 最小的内存开销，因为空闲列表头和指针非常高效。两个函数的运行时间都是 O(1)，并且没有内存浪费