Malloc割り当てスキーム

Question

はい、私はコンピュータシステムコースを受講しています。 mallocを実装するためのさまざまな割り当て方式についていくつか質問がありました。 明示的なリストの場合、LIFOのようなスタックを使用してmallocを実装すると、以前に解放されたメモリへのポインタを持つ目的は何ですか？なぜ二重連結リストが必要なのか？単独でリンクされたリストも同様に機能しませんか？

Malloc lecture. 私はこのリンクをオンラインで見つけました。スライド7を見て、私が何を話しているのか見ることができます。

分離リスト割り当て方式を見ているとき、これらのリストは一方向の権利ですか？また、合体メカニズムは正確に何ですか？たとえば、4つの単語が解放されている場合は、周りの空き領域が分離されたリンクリストに挿入される前に、まずそれを結合してみましょうか？または、それぞれの分離リンクリストの '4ワード'セクションに4ワードブロックを挿入するだけですか？

ありがとうございます。

Answer 1

解放されたブロックは常に2つのポインタのための余裕があるので、リストを二重化しないのはなぜですか？合体コードを簡素化するので、リストをトラバースしている間に末尾のポインタを維持する必要はありません。また、リストの終わりが検索を開始するためのヒントがある場合には、どちらの方向にもリストをトラバースすることができます。私が一度見てきた1つのあいまいなシステムは、最後のアクティビティが発生した「中間」にポインタを置いていました。

ブロックを解放するとき。唯一の四つの可能なケースがあります。

• 空きブロックが空きブロックの後隣接しています。
• フリーブロックは、フリーブロックであるより前には、に隣接しています。
• 空きブロックは、その前後の空きブロックの間にあります。
• 空きブロックが空きブロックに隣接していません。隣接する空きブロックを合体する

目的は以下のとおりです。

• 正確に確認するために先読みするアロケータに負担をかけず空きブロックの大きさを反映するために、リンクリスト
• の長さを短くします2つのブロックが隣接している場合

フリー・ブロックを特定の長さのフリー・リストにソートすることはしばしば利点がありますが、ほとんどの実際的な実装では、合体が優先され、alloc()異なるサイズの空きブロックが多数ある場合、異なるサイズのブロックに対する要求が不適切に拒否されることはありません。