バディブロック

ウィキペディア小見出し辞書

バディブロック

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/06/25 02:37 UTC 版)

「動的メモリ確保」の記事における「バディブロック」の解説

別の解決策として「バディブロック・アロケータ」がある。このシステムでは、メモリは2の冪乗サイズの大きなブロックとして最初に確保される。要求されたサイズがブロックサイズの半分以下ならば、それを二つの同じサイズのブロックに分割する。これらを互いにバディブロック（Buddy Block; 相棒ブロック）と呼ぶ。その一方を選択して、要求されたサイズがブロックサイズの半分以上になるまで分割を続ける。残った各サイズのバディブロックはソートされた線形リストか木構造、あるいはサイズ毎の線形リストに保持される。ブロックが解放されると、対応するバディをチェックし、両方が解放された状態であれば、これを結合して一段上のサイズのブロックとし、さらに結合できないかチェックしていく。 ページングによる仮想記憶システムでバディブロックを使う場合、ページサイズ以上のメモリアロケーションは仮想記憶機構に任せるのが一般的である。そのため、ページサイズがバディブロック・アロケータの対象とするブロックサイズの上限となる。 バディブロック・アロケータはリアルタイムオペレーティングシステムでよく使われるが、通常のオペレーティングシステムでも使われている（例えばLinuxカーネル）。SVR4やSolarisなどのカーネルでもこの機構をカーネル内の動的メモリアロケーションに使用している（Kernel Memory Allocatorと呼ばれている）。