5

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

マロック講義。 私はこのリンクをオンラインで見つけました。スライド7を見て、私が話していることを確認できます。

分離されたリスト割り当てスキームを見ると、これらのリストは一方向ですよね？また、合体メカニズムとは正確には何ですか？たとえば、4つの単語が解放された場合、それぞれの分離されたリンクリストに挿入する前に、まず周囲の空きスペースに参加してみますか？または、それぞれの分離されたリンクリストの「4ワード」セクションに4ワードブロックを挿入するだけですか？

ありがとうございました。

4

1 に答える 1

4

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

ブロックを解放するとき。考えられるケースは4つだけです。

  • フリーブロックは、フリーブロックの後に隣接しています。
  • フリーブロックは、フリーブロックの前に隣接しています。
  • フリーブロックは、その前後の両方のフリーブロックの間にあり、隣接しています。
  • フリーブロックはどのフリーブロックにも隣接していません。

隣接するフリーブロックを合体させる目的は次のとおりです。

  • リンクリストの長さを短くするには
  • 2つのブロックが隣接しているかどうかを確認するためにアロケータに負担をかけずに、空きブロックのサイズを正確に反映する

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

于 2012-04-04T05:54:01.733 に答える