c++ - C++ での malloc のカスタム実装

Question

C++ で malloc() と free 関数を実装するように求められたインタビューの質問に出くわしました。

最初に、サイズ 50000 の char 配列が宣言されます (50000 バイト)。これがヒープ メモリであると仮定して、malloc 関数と free 関数を記述し、メモリ ブロックを割り当ててメモリを解放します。

誰も私にC++の作業/疑似コードを提供したり、メカニズムを説明したりできますか? （明らかに、コードを使用すると、理解しやすくなります）。

ありがとう、ロヒット

Answer 1

本番レベルの動的メモリアロケータを作成するのは非常に難しい作業ですが、おもちゃのアロケータを作成するのは簡単です。質問は明らかにあなたのスキルをテストすることを意図していますが、他の人の作品からインスピレーションを探すことは依然として公正です。

Kernighan＆Ritchieによる「Cプログラミング言語」には、の簡単な実装が含まれていmallocます。それを研究し、その設計と実装の意味を検討してください。パフォーマンスを向上させたり、フラグメントを減らしたり、複数のスレッドを処理したりするために、どのように改善するかを検討してください。その後、独自のおもちゃのアロケータを作成し、発生した質問に答えるのは難しくありません。

Answer 2

使用できるアルゴリズムはいくつかあります。このような小さなメモリの場合、各ブロックの前に次のブロックへのポインターと、それが割り当てられているか解放されているかを示すフラグを付けるだけです。割り当ては、十分な大きさの空きブロックを見つけ、必要に応じて分割し、返されたブロックを割り当て済みとしてマークすることで構成されます。フリーは、ブロックをフリーとしてマークすることで構成されます。ある時点で、ブロックを結合する必要もあります。2 つの空きブロックが続く場合、それらは 1 つにマージされます。(実装の割り当て中にこれを行いました。)

上記のアルゴリズム自体はそれほど難しくありません。本当の秘訣は、さまざまなキャストなどをすべて正しく取得することです。非常に低レベルのプログラミングの良い練習になります。

Answer 3

これまでテストしたことはありませんが、新しいキーワードとテンプレートを使用して、目的の型の配列を作成するための一般的な状態をサポートすることでこれを行うことができると思いますが、この質問に従って、C++ヒーローの応答を調べます。