c - 自分のメモリマネージャを書く

Question

巨大な動的メモリを割り当てて、それに対して独自のメモリマネージャを作成したいと思います。つまり、コードにメモリが必要な場合は、このメモリプールから割り当てます。内部および外部の断片化をアルゴリズムで処理する必要があります。このための最も効率的なアルゴリズムはどれですか？

Answer 1

これらの基準については、Doug Lea のhttp://g.oswego.edu/dl/html/malloc.htmlを使用します。これは、さまざまなサイズごとにストア ブロックのコレクションを保持しています。サイズをすばやく見つけることができます。同じサイズのブロックを再利用すると、断片化が減少します。これはマルチスレッド用に調整されていないことに注意してください ( http://entland.homelinux.com/blog/2008/08/19/practical-effective-memory-management/ )。

私が自分で作成していた場合、http://en.wikipedia.org/wiki/Buddy_memory_allocationを使用します。高速であり、ユーザー空間では一般的に使用されていないためです (可能なブロック サイズが制限され、内部エラーにつながるため、一般的には使用されません)断片化)。実際、私は少し前にそうしました - http://www.mcdowella.demon.co.uk/buddy.html

Answer 2

「最も効率的」という用語が明確でないため、この質問はあいまいです。どの用語で最も効率的であるべきかは言いません。

例として: first fit と呼ばれる戦略があります。これは best fit よりも高速ですが、ヒープの断片化がさらに進む可能性があります (非常に悪いことです)。一方、ベスト フィットは外側の断片化をいくらか減らしますが、空きメモリのチャンクを見つけるのにより多くの時間がかかりますが、依然として影響を受けます。外側の断片化ではなく内側の断片化に悩まされるバディヒープと呼ばれる戦略もあります。しかし、少なくとも空きブロックを見つけることは、通常は高速です。

アルゴリズムの選択は、実際には要件に依存することがわかります。割り当てを高速にするか、断片化を低くする必要がありますか? 割り当ての動作は何ですか? 頻繁に割り当ておよび解放される小さな不均一なチャンクがありますか、それとも大きなチャンクだけですか? そして、ここで役割を果たすさらに多くの要因があります。

こういう答えが欲しかったのかもしれません。そうでない場合は、要件を明確にすることをお勧めします。