無料リスト

フリー リスト(またはフリーリスト) は、動的メモリ割り当てのスキームで使用されるデータ構造です。これは、割り当てられていないメモリ領域をリンク リストで接続し、割り当てられていない各領域の最初のワードを次の領域へのポインタとして使用することによって動作します。これは、すべてのオブジェクトのサイズが同じであるメモリ プールから割り当てる場合に最適です。

フリー リストを使用すると、割り当てと割り当て解除の操作が非常に簡単になります。領域を解放するには、その領域をフリー リストにリンクするだけです。領域を割り当てるには、フリー リストの末尾から 1 つの領域を削除してそれを使用します。領域のサイズが可変である場合、十分な大きさの領域を検索する必要があり、コストがかかる可能性があります。

フリー リストには、リンク リストに由来する、参照の局所性が低いためデータ キャッシュの利用率が低いという欠点があり、バディ割り当てシステムとは異なり、大きな領域に対する割り当て要求を満たすために隣接する領域を自動的に統合しません。ただし、本格的なメモリ アロケータが不要であったり、オーバーヘッドが大きすぎるさまざまな単純なアプリケーションでは、依然として役立ちます。

OCamlランタイムは割り当て要求を満たすためにフリーリストを使用します^[1]。AndroidランタイムのRosAllocも同様です^{[2] 。}

• バディメモリ割り当て

• メモリ管理用語集
• メモリ割り当ての講義スライド (ppt)