algorithm - メモリ割り当てアルゴリズム

Question

次の制約を使用して、メモリを割り当てて追跡するデータ構造を実装するにはどうすればよいですか

1. O(1) でのメモリの割り当てと解放
2. 最小の断片化。

1 KB 単位のメモリがあるとします。2kB ～ 64 KB のメモリを割り当てる必要があります

例えば

A-1

B-1

C-4

D-2

0 1 2 3 4 5 6 7 8 9 10

x A x BCCCCDD x

メモリを解放するときに使用可能な最小アドレスにメモリを割り当てると (上記の x で示されます)、断片化が発生します。したがって、上記の例では、3 ユニットが空いていても、連続する 3 ユニットのメモリを割り当てることはできません。

Answer 1

「バディ システム」または「バディ メモリ割り当て」を検索します。それがおそらくあなたが見つける最善の解決策です。ただし、純粋な O(1) ではなく、内部の断片化が発生し、外部の断片化も発生する可能性があります...

拡張ツリーを使用すると、内部の断片化を完全に回避できますが、操作に O(log N) の時間がかかります。そして、まだ外部の断片化があります。