c - ユーザー定義の malloc() 関数を実装しますか?

Question

C言語で定義された新しいmalloc()関数をどのように作成しますか?

これを行う方法、仮想空間アドレスを物理空間にマップする方法、どのアルゴリズムに従うべきかについてのエルフのようなヒントさえありません。malloc() は断片化を引き起こす可能性があるため、あまり効率的ではないことは知っています。したがって、効率的なものを作成できます。効率的でなくても、単純な C の malloc 関数を実装するにはどうすればよいですか?

最近インタビューで聞かれました。

Answer 1

ウィキペディアには、特定の条件に合わせて最適化されたものを含む、さまざまな malloc 実装の優れた概要と、実装について詳しく知るためのリンクが実際に提供されています。

http://en.wikipedia.org/wiki/C_dynamic_memory_allocation

dlmalloc

汎用アロケーター。GNU C ライブラリ (glibc) は、dlmalloc に基づくアロケータを使用します。

ジェマロック

ロックの競合を避けるために、jemalloc は CPU ごとに別々の「アリーナ」を使用します。マルチスレッド アプリケーションで 1 秒あたりの割り当て数を測定した実験では、これによりスレッド数に比例してスケーリングされることが示されましたが、phkmalloc と dlmalloc の両方のパフォーマンスはスレッド数に反比例しました。

ホード メモリ アロケータ

Hoard は mmap のみを使用しますが、スーパーブロックと呼ばれる 64 キロバイトのチャンクでメモリを管理します。Hoard のヒープは、単一のグローバル ヒープと多数のプロセッサごとのヒープに論理的に分割されます。さらに、限られた数のスーパーブロックを保持できるスレッド ローカル キャッシュがあります。スレッドごとまたはプロセッサごとのローカル ヒープ上のスーパーブロックからのみ割り当て、ほとんど空のスーパーブロックをグローバル ヒープに移動して他のプロセッサで再利用できるようにすることで、Hoard は断片化を低く抑えながら、スレッド数に応じてほぼ線形のスケーラビリティを実現します。 .

tcmalloc

すべてのスレッドには、小さな割り当て用のローカル ストレージがあります。大規模な割り当てには、mmap または sbrk を使用できます。Google が開発した malloc である TCMalloc には、デッド スレッドのローカル ストレージ用のガベージ コレクションがあります。TCMalloc は、マルチスレッド プログラムの glibc の ptmalloc よりも 2 倍以上高速であると考えられています。

dmalloc (ウィキペディアではカバーされていません)

デバッグ メモリ割り当てまたは dmalloc ライブラリは、システムの malloc、realloc、calloc、free、およびその他のメモリ管理ルーチンの代替として設計されており、実行時に構成可能な強力なデバッグ機能を提供します。これらの機能には、メモリ リークの追跡、フェンス ポスト書き込みの検出、ファイル/行番号のレポート、統計の一般的なログなどがあります。

Answer 2

C プログラミング言語ブックの第 8.7 章の例の malloc の良い例だと思います。