フリーストアの一般的な(確かに唯一ではありませんが)実装は、メモリの空きブロック(つまり、現在使用されていないブロック)のリンクリストです。ヒープマネージャは通常、オペレーティングシステムからメモリの大きなブロック(たとえば、一度に1メガバイト)を割り当て、これらのブロックを分割して、コードで使用する場合new
などに使用します。を使用するdelete
と、使用をやめたメモリのブロックがそのリンクリストのノードとして追加されます。
これらの無料ブロックをどのように使用するかについては、さまざまな戦略があります。3つの一般的なものは、ベストフィット、ワーストフィット、ファーストフィットです。
最適な方法として、必要な割り当てに最も近いサイズの空きブロックを見つけようとします。必要以上に大きい場合(通常は割り当てサイズを丸めた後)、2つに分割します。1つは割り当てに戻るためのもので、もう1つは他の割り当て要求を満たすためにリストに戻すための新しい(小さい)空きブロックです。これは良い戦略のように思えるかもしれませんが、しばしば問題があります。問題は、最も近いものを見つけたときに、残ったブロックが小さすぎてあまり役に立たないことが多いということです。しばらくすると、空き領域の小さなブロックが大量に発生しますが、どれも何にも適していません。
ワーストフィットは、代わりにフリーブロックの中でワーストフィットを見つけることによってそれと戦います-IOW、フリースペースの最大のブロック。そのブロックを分割すると、残っているものが可能な限り大きくなり、他の割り当てに役立つ可能性が最大になります。
最初の拳は、空きブロックのリストをたどるだけで、(名前から推測できるように)要件を満たすのに十分な大きさの最初のブロックを使用します。
かなりの数が正確な適合の検索から始まり、ブロックを分割するよりもそれを使用します。
かなりの数が、適切なサイズのブロックの検索を最小限に抑えるために、(たとえば)さまざまな割り当てサイズの個別のリンクリストをいくつか保持しています。
かなりの数のケースで、マネージャーは、空きブロックのリストを調べて、隣り合っているブロックを見つけるためのコードも持っています。それらが見つかった場合は、2つの小さなブロックを1つの大きなブロックに結合します。時々これはあなたfree
/delete
ブロックのときに正しく行われます。多くの場合、同じサイズのブロックを多数使用している場合(かなり一般的です)にブロックを結合して再分割することを避けるために、それは怠惰に行われます。
多数の同じサイズのアイテム(特に小さいアイテム)を処理するときに一般的なもう1つの可能性は、空きまたは使用中のアイテムを指定するビットセットを持つブロックの配列です。この場合、通常、最後の空きブロックが見つかったビットセットへのインデックスを追跡します。ブロックが必要な場合は、最後のインデックスから前方に検索して、ブロックが空いているとビットセットが示す次のインデックスを見つけます。