インタビューの質問: 新しい "malloc" および "free" 関数をどのように作成しますか? 「new と delete を使用する」ことは受け入れられる答えではないか、LocalAlloc/HeapAlloc のようなものを使用するとは思わない
9493 次
7 に答える
12
これは面接の質問なので、おそらく「正しい」答えはありません。彼らは、あなたの思考過程や、トピックに関する一般的な知識に関心を持っています。
要件を明確にするように依頼するか、状況に応じてさまざまな回答を提供する必要があります。考慮すべきいくつかの問題を次に示します。
- メモリの断片化を避けることは重要ですか? 固定割り当てサイズが役立つ場合があります。
- 割り当てに速度保証が必要ですか? 使用済み/空きブロックのインデックスを使用します。
- 実行された割り当てを簡単に追跡する必要がありますか? ロギング構造を malloc/free ライブラリに追加します。
- メモリのアンダーラン/オーバーランを防止または検出する必要がありますか? 余分なパディングと定期的なパディング チェック。
于 2013-02-06T09:03:13.980 に答える
4
簡単に言えば、
関数mallocは、オペレーティング システムからメモリを取得し、メモリを動的に割り当てるように要求するクライアント (たとえば、C プログラム) に渡すことができる必要があります。これを実装するために、malloc ライブラリには通常、(実装に応じて) 多くのデータ構造mallocがあります。より効率的な方法は、それぞれが特定のサイズ範囲のブロックを含む、リンクされたリストのリストを持つことです。
私はたまたまTCMallocライブラリに取り組んでいました。これは、これをより明確に理解するのに役立つかもしれません
フリーリストによるメモリ割り当て
クラス 0 がサイズ 4k のフリー ブロックのリンク リストであり、クラス 1 がサイズ 8k のフリー ブロックのリンク リストであるとします。
malloc の呼び出しが行われると (たとえば、サイズが 10k の場合)、malloc 実装はフリーリストを走査して、要求を満たす最小の空きブロックを見つけます (この場合、4k ブロックでは不十分なので、 8k ブロックをフェッチし、フリーリストから削除して、プログラムに戻します)。
同様に、 への呼び出しfreeが行われると、実装は (とりわけ) プログラムからブロックを回収し、freelistsの 1 つに適切な場所に追加する必要があります。
于 2013-02-06T09:04:44.373 に答える
3
このサイトはあなたの質問に答えます。
http://www.codeproject.com/Questions/177316/Write-your-own-malloc -- 同じ質問 http://www.inf.udec.cl/~leo/Malloc_tutorial.pdf
于 2013-02-06T09:03:11.730 に答える
3
面接官に聞かれたら
新しい「malloc」および「free」関数をどのように作成すればよいですか?
そして、あなたがやろうとしていることについて話し始めると、あなたはすでに失敗しています。malloc 関数をより正確に使用するには、事前にいくつかの質問をする必要があります。私の頭の上にある最初の質問のいくつかは次のとおりです。
- どのOS向け？
- どの思い出に？ユーザー malloc またはカーネル malloc?
- 最も頻繁に使用されるシナリオはどれですか? 万能malloc？巨大なチャンクまたは小さなチャンクのどちらに適していますか?
コードについて話し始める前に、要件を引き出す最初のラウンドが必要です。
于 2013-02-06T09:06:15.483 に答える
1
malloc()フックと呼び出しについて話している場合はfree()、次のようにして行うことができます。
#define malloc(x) your_malloc(x)
#define free(x) your_free(x)
ただし、独自のメモリ アロケータの作成について話している場合は、Kernighan と Ritchie による著書「The C Programming Language 2nd Edition」で、ヒープ アロケータの実装の 1 つを見たいと思うかもしれません。基本的に、sbrk()システム関数を使用してプロセスのデータ セグメントのサイズを大きくします。
于 2013-02-06T09:02:40.820 に答える
1
要件によって異なります。たとえば、実行時またはパフォーマンス上の理由で malloc/free を実行できない場合がある組み込みソフトウェアを作成したい場合などです。代わりに、メモリの割り当て/解放を行わず、事前に割り当てられたヒープからブロックを取得/再実行する独自のバージョンの malloc/free を作成できます。
于 2013-02-06T08:56:28.873 に答える
0
彼らは別の言い方で質問をすることができる/すべきだと思います：「ヒープメモリはmallocとfreeによってどのように管理されていますか？」.
次に、問題を少し異なる方法で考えることができます-値の線形リストが与えられた場合、リストのチャンクをどのように分割して追跡するか、そのリストのチャンクをどのように戻すか、断片化をどのように管理するかリストなど
つまり、次の空きブロックのアドレスは、割り当てられたブロックの隣のヒープに格納されますが、次の空きメモリが格納されている場所に関する情報はユーザーには見えませんが、同じヒープの一部です。これが、不正に割り当てられたメモリのオーバーランがヒープを完全に破壊し、malloc や free などをクラッシュさせる可能性がある理由です。
通常、インタビュアーは質問を使用して、あなたの知識を示す自由を与えます。基本的な機能から始めて、玉ねぎがさまざまな O/S によってどのように管理されているか、さまざまなアルゴリズムが何であるかなどを理解していれば、結局のところ、あなたが説明するものは、過去 20 年間の R&D に関する過去 20 年間を網羅するものではありません。主題！
于 2013-02-06T08:59:49.860 に答える