Linux カーネルのメモリ管理アルゴリズム Buddy と Slab

[[251667]]

バディ割り当てアルゴリズム

これはページ フレームの連続セクションであると仮定します。網掛け部分は、使用されているページ フレームを示します。次に、5 つのページ フレームの連続セクションを申請する必要があります。この時点で、このメモリ セグメント内に 5 つの連続した空きページ フレームが見つからない場合は、別のメモリ セグメントを使用して 5 つの連続したページ フレームを検索します。これにより、時間の経過とともにページ フレームが無駄になります。この状況を回避するために、Buddy システム アルゴリズムが Linux カーネルに導入されました。すべての空きページ フレームは 11 個のブロック リストにグループ化され、各リストには 1、2、4、8、16、32、64、128、256、512、および 1024 個の連続したページ フレームのサイズのページ フレーム ブロックが含まれます。最大 1024 の連続ページ フレームを適用でき、これは 4 MB の連続メモリに相当します。各ページ フレーム ブロックの最初のページ フレームの物理アドレスは、図に示すように、ブロック サイズの整数倍になります。

256 ページ フレームのブロックを申請する場合、まず 256 ページ フレームのリンク リストで空きブロックを探します。見つからない場合は、512 ページ フレームのリンク リストで探します。見つかった場合は、ページ フレーム ブロックを 256 ページ フレームの 2 つのブロックに分割し、1 つはアプリケーションに割り当て、もう 1 つは 256 ページ フレームのリンク リストに移動します。 512 ページ フレームのリンク リストにまだ空きブロックがない場合は、1024 ページ フレームのリンク リストの検索を続行します。それでも空きブロックがない場合は、エラーが返されます。ページ フレーム ブロックが解放されると、連続する 2 つのページ フレーム ブロックがアクティブにマージされ、より大きなページ フレーム ブロックになります。

上記から、Buddy アルゴリズムがページ フレームを分割および結合していることがわかります。 Buddy アルゴリズムは、世界中のあらゆる正の整数が 2^n の合計で構成できるという事実を利用している点で優れています。これは、空きページ テーブルを管理する Buddy アルゴリズムの本質でもあります。

次のコマンドで空きメモリ情報を取得できます。

また、 echo m > /proc/sysrq-trigger を使用して、/proc/buddyinfo の情報と一致する buddy ステータスを観察することもできます。

ＣＭＡ

注意深い読者は、Buddy アルゴリズムがメモリを分割して結合すると断片化が発生し、メモリには連続した大きなメモリ ブロックがなくなり、小さなメモリ ブロックのみになることに気付くでしょう。もちろん、これはアプリケーションには影響しません (前述したように、ページ テーブルを使用すると、不連続な物理アドレスを仮想アドレスで連続させることができます)。ただし、カーネル モードで連続したメモリの大きなブロックを取得する方法はありません (たとえば、DMA、カメラ、GPU はすべて、連続した物理アドレスを持つ大きなメモリ ブロックを必要とします)。

CMA は、上記の問題を解決するために、組み込みデバイスで一般的に使用されます。 CMA の正式名称は連続メモリ アロケータです。その動作原理は、メモリのセクションがドライバーが使用するために予約されていますが、ドライバーが使用されていない場合は、CMA 領域をユーザー プロセスに割り当てて、匿名メモリまたはページ キャッシュとして使用できるというものです。ドライバーが使用する必要がある場合、プロセスによって占有されているメモリはリサイクルまたは移行され、ドライバーが使用するために以前に占有されていた予約済みメモリが解放されます。

スラブ

Linux では、バディ システムがページ単位でメモリを管理および割り当てます。しかし、実際の需要はバイト単位です。20 バイトを適用する必要がある場合、1 ページを割り当てることはできません。これはメモリの重大な無駄になります。では、どのように割り当てるのでしょうか? 小さなメモリ割り当て用に特別に設計されたスラブ アロケータが誕生しました。スラブ アロケータはバイト単位でメモリを割り当てます。ただし、スラブ アロケータはバディ システムから逸脱するものではなく、バディ システムによって割り当てられた大きなメモリを小さなメモリ割り当てにさらに細分化します。まずは写真を見てみましょう

kmem_cache は、キャッシュを記述する cache_chains のリンク リストです。各 cache_chains には、通常は連続したメモリ ブロックであるスラブのリストが含まれます。スラブには 3 つの種類があります。

• slabs_full (完全に割り当てられたスラブ)
• slabs_partial (部分的に割り当てられたスラブ)
• slabs_empty (空のスラブ、またはオブジェクトが割り当てられていません)。

スラブはスラブ アロケータの最小単位です。実装では、スラブは 1 つ以上の連続した物理ページ (通常は 1 ページのみ) で構成されます。単一のスラブをスラブ リスト間で移動できます。たとえば、半分いっぱいのスラブがオブジェクトの割り当て後にいっぱいになった場合、そのスラブは slabs_partial から削除され、slabs_full に挿入されます。

さらに詳しく説明すると、struct kmem_cache 構造体によって記述されるメモリのセクションがスラブ キャッシュ プールと呼ばれることを示す例がここにあります。スラブ キャッシュ プールは牛乳の箱のようなものです。箱の中には牛乳のボトルがたくさん入っており、それぞれの牛乳のボトルがオブジェクトになっています。メモリを割り当てるときは、牛乳パックからボトルを取り出すようなものです。いつかすべてがなくなる日が来るでしょう。箱が空になったら、スーパーマーケットに行って別の箱を買う必要があります。スーパーマーケットは部分リンクリストに相当し、スーパーマーケットには牛乳の箱がたくさん保管されています。スーパーマーケットで商品が売り切れた場合は、当然メーカーから商品を仕入れて販売することになります。メーカーはパートナーシステムに相当します。

次のコマンドを使用して、スラブ キャッシュ情報を表示できます。

要約する

メモリ DDR をさまざまなゾーンに分割することから、CPU がアクセスするページをページ テーブルを介してゾーンにマッピングすること、そしてこれらのページを Buddy アルゴリズムと Slab アルゴリズムを介して管理することまで、次の図を感覚的な観点から理解できるはずです。