メモリ管理 - ShuWa

メモリ管理は主に何を行うのか？#

メモリの割り当てと回収：プロセスが必要とするメモリを割り当てたり解放したりする。malloc 関数：メモリを要求する、free 関数：メモリを解放する。
アドレス変換：プログラム内の仮想アドレスをメモリ内の物理アドレスに変換する。
メモリの拡張：システムに十分なメモリがない場合、仮想メモリ技術や自動オーバーライド技術を利用して論理的にメモリを拡張する。
メモリマッピング：ファイルをプロセスのプロセス空間に直接マッピングし、メモリポインタを介してメモリを読み書きすることでファイル内容に直接アクセスでき、速度が向上する。
メモリの最適化：メモリの割り当て戦略や回収アルゴリズムを調整してメモリ使用効率を最適化する。
メモリの安全性：プロセス間でメモリの使用が干渉しないようにし、悪意のあるプログラムがメモリを変更してシステムの安全性を損なうのを防ぐ。

メモリの断片化とは何か？#

メモリの断片化は、メモリの要求と解放によって生じ、通常は以下の 2 種類に分けられる：

内部メモリ断片化（Internal Memory Fragmentation）：プロセスに割り当てられたが使用されていないメモリ。内部メモリ断片化の主な原因は、固定比率（例えば 2 の累乗）でメモリを割り当てると、プロセスに割り当てられたメモリが実際に必要なメモリよりも大きくなることがある。例えば、プロセスが 65 バイトのメモリを必要とするが、128（2^7）バイトのメモリが割り当てられた場合、63 バイトのメモリが内部メモリ断片化となる。
外部メモリ断片化（External Memory Fragmentation）：未割り当ての連続したメモリ領域が小さすぎて、任意のプロセスが必要とするメモリ割り当て要求を満たせない場合、これらの小さな断片で連続していないメモリ空間を外部断片化と呼ぶ。つまり、外部メモリ断片化は、プロセスに割り当てられていないが使用できないメモリを指す。後で紹介するセグメンテーションメカニズムが外部メモリ断片化を引き起こすことになる。

一般的なメモリ管理方法にはどのようなものがあるか？#

連続メモリ管理#

ブロック管理
ブロック管理はメモリをいくつかの固定サイズのブロックに分け、各ブロックには 1 つのプロセスのみを含む。プログラムがメモリを必要とする場合、オペレーティングシステムはそれにブロックを割り当て、プログラムが非常に小さなスペースしか必要としない場合、割り当てられたブロックの大部分がほぼ無駄になる。各ブロック内で未使用のスペースを内部メモリ断片化と呼ぶ。内部メモリ断片化の他に、2 つのメモリブロックの間に外部メモリ断片化が存在する可能性があり、これらの不連続な外部メモリ断片化は小さすぎて再割り当てできない。
Linux システムでは、連続メモリ管理はバディシステム（Buddy System）アルゴリズムを使用して実現されており、これは古典的な連続メモリ割り当てアルゴリズムであり、外部メモリ断片化の問題を効果的に解決できる。バディシステムの主な考え方は、メモリを 2 の累乗に分割することであり（各メモリブロックのサイズは 2 の累乗、例えば 2^6=64 KB）、隣接するメモリブロックをペアに組み合わせる（注意：隣接している必要がある）。
メモリ割り当てを行うとき、バディシステムは最も適切なサイズのメモリブロックを見つけようとする。見つかったメモリブロックが大きすぎる場合は、それを 2 つに分割し、同じサイズのバディブロックに分ける。まだ大きい場合は、適切なサイズに達するまでさらに分割を続ける。
隣接する 2 つのメモリブロックが解放されると、システムはこれらの 2 つのメモリブロックを結合して、次のメモリ割り当てのためにより大きなメモリブロックを形成する。これにより、メモリ断片化の問題を減少させ、メモリ利用率を向上させる。

非連続メモリ管理#

非連続メモリ管理には以下の 3 つの方法がある：

セグメント管理：セグメント（連続した物理メモリのセグメント）の形式で物理メモリを管理 / 割り当てする。アプリケーションの仮想アドレス空間はサイズが異なるセグメントに分割され、セグメントは実際に意味を持ち、各セグメントは主プログラムセグメント MAIN、サブルーチンセグメント X、データセグメント D、スタックセグメント S などの論理情報のセットを定義する。
ページ管理：物理メモリを連続した等長の物理ページに分割し、アプリケーションの仮想アドレス空間も連続した等長の仮想ページに分割される。これは現代のオペレーティングシステムで広く使用されているメモリ管理方法である。
セグメントページ管理メカニズム：セグメント管理とページ管理を組み合わせたメモリ管理メカニズムであり、物理メモリをいくつかのセグメントに分割し、各セグメントをさらに同じサイズのページに分割する。

仮想メモリ#

仮想メモリとは何か？どのように役立つのか？#

** 仮想メモリ（Virtual Memory）** は、コンピュータシステムのメモリ管理において非常に重要な技術であり、本質的には論理的に存在するものであり、想像上のメモリ空間である。主な役割は、プロセスが主記憶（物理メモリ）にアクセスするための橋渡しをし、メモリ管理を簡素化することである。
要約すると、仮想メモリは主に以下の能力を提供する：

プロセスの隔離：物理メモリは仮想アドレス空間を介してアクセスされ、仮想アドレス空間はプロセスに一対一で対応する。各プロセスは自分が全体の物理メモリを持っていると考え、プロセス間は互いに隔離されており、あるプロセス内のコードは他のプロセスやオペレーティングシステムが使用している物理メモリを変更できない。
物理メモリの利用率の向上：仮想アドレス空間があることで、オペレーティングシステムはプロセスが現在使用している部分のデータや命令のみを物理メモリにロードすればよい。
メモリ管理の簡素化：プロセスは一貫したプライベートな仮想アドレス空間を持ち、プログラマーは実際の物理メモリと対話する必要がなく、仮想アドレス空間を介して物理メモリにアクセスすることでメモリ管理が簡素化される。
複数のプロセスが物理メモリを共有：プロセスが実行中に、多くのオペレーティングシステムの動的ライブラリがロードされる。これらのライブラリは各プロセスにとって共通であり、メモリには実際に 1 つだけがロードされる。この部分は共有メモリと呼ばれる。
メモリ使用の安全性の向上：プロセスの物理メモリへのアクセスを制御し、異なるプロセスのアクセス権を隔離し、システムの安全性を向上させる。
より大きな使用可能なメモリ空間の提供：プログラムがシステムの物理メモリサイズを超える使用可能なメモリ空間を持つことができる。これは、物理メモリが不足している場合、ディスクを利用して物理メモリページ（通常は 4KB のサイズ）をディスクファイルに保存し（読み書き速度に影響を与える）、データやコードページが必要に応じて物理メモリとディスクの間で移動するためである。

仮想アドレスと物理アドレスとは何か？#

** 物理アドレス（Physical Address）** は、実際の物理メモリ内のアドレスであり、より具体的にはメモリアドレスレジスタ内のアドレスである。プログラムがアクセスするメモリアドレスは物理アドレスではなく、** 仮想アドレス（Virtual Address）である。
つまり、プログラミング開発を行う際には、実際には仮想アドレスと対話していることになる。例えば、C 言語では、ポインタに格納されている値はメモリ内のアドレスと理解でき、このアドレスが私たちが言う仮想アドレスである。
オペレーティングシステムは一般的に、CPU チップ内の重要なコンポーネントであるMMU（Memory Management Unit、メモリ管理ユニット）を介して仮想アドレスを物理アドレスに変換し、このプロセスはアドレス翻訳 / アドレス変換（Address Translation）** と呼ばれる。

仮想アドレスと物理メモリアドレスはどのようにマッピングされるのか？#

MMU が仮想アドレスを物理アドレスに翻訳する主なメカニズムは 3 つある：

セグメンテーションメカニズム
ページメカニズム
セグメントページメカニズム

セグメンテーションメカニズム#

** セグメンテーションメカニズム（Segmentation）** は、セグメント（連続した物理メモリのセグメント）の形式で物理メモリを管理 / 割り当てする。アプリケーションの仮想アドレス空間はサイズが異なるセグメントに分割され、セグメントは実際に意味を持ち、各セグメントは主プログラムセグメント MAIN、サブルーチンセグメント X、データセグメント D、スタックセグメント S などの論理情報のセットを定義する。

セグメントテーブルは何のためにあるのか？アドレス翻訳プロセスはどのようになっているのか？#

セグメンテーションメカニズム下の仮想アドレスは、セグメント選択子とセグメント内オフセットの 2 つの部分で構成される。

セグメント選択子とセグメント内オフセット：

セグメント選択子はセグメントレジスタ内に保存されている。セグメント選択子の中で最も重要なのはセグメント番号であり、これはセグメントテーブルのインデックスとして使用される。セグメントテーブルにはこのセグメントの基準アドレス、セグメントの境界、特権レベルなどが保存されている。
仮想アドレス内のセグメント内オフセットは 0 とセグメント境界の間に位置する必要があり、セグメント内オフセットが合法であれば、セグメント基準アドレスにセグメント内オフセットを加えて物理メモリアドレスを得る。

上記のように、仮想アドレスがセグメントテーブルを介して物理アドレスにマッピングされることがわかる。セグメンテーションメカニズムはプログラムの仮想アドレスを 4 つのセグメントに分け、各セグメントにはセグメントテーブル内に項目があり、その項目でセグメントの基準アドレスを見つけ、オフセットを加えることで物理メモリ内のアドレスを見つけることができる。以下の図のように：
セグメンテーションの方法は非常に良く、プログラム自体が具体的な物理メモリアドレスを気にする必要がない問題を解決したが、いくつかの欠点もある：

最初の問題はメモリ断片化の問題である。
2 番目の問題はメモリ交換の効率が低いことである。

メモリのセグメンテーションはメモリ断片化を引き起こすか？#

メモリのセグメンテーション管理は、セグメントが実際の要求に応じてメモリを割り当てることができるため、必要な分だけ大きなセグメントを割り当てることができるため、内部メモリ断片化は発生しない。
しかし、各セグメントの長さが固定されていないため、複数のセグメントが必ずしもすべてのメモリ空間を正確に使用するわけではなく、複数の不連続な小さな物理メモリが発生し、新しいプログラムがロードできなくなるため、外部メモリ断片化の問題が発生する。
「外部メモリ断片化」の問題を解決するのがメモリ交換である。
音楽プログラムが占有している 256MB のメモリをハードディスクに書き込み、その後ハードディスクからメモリに読み戻すことができる。しかし、読み戻すときには、元の位置に戻すのではなく、すでに占有されている 512MB のメモリの後ろに続けて配置する必要がある。こうすることで、連続した 256MB の空間が確保され、新しい 200MB のプログラムがロードできる。
このメモリ交換空間は、Linux システムでは、私たちがよく見る Swap 空間であり、この空間はハードディスクから分割され、メモリとハードディスクの空間交換に使用される。

セグメンテーションがメモリ交換効率の低下を引き起こすのはなぜか？#

マルチプロセスシステムでは、セグメンテーション方式を使用すると、外部メモリ断片化が簡単に発生し、外部メモリ断片化が発生すると、メモリ領域を再度Swapしなければならず、このプロセスはパフォーマンスのボトルネックを引き起こす。
ハードディスクのアクセス速度はメモリよりもはるかに遅いため、メモリ交換のたびに、大量の連続したメモリデータをハードディスクに書き込む必要がある。
したがって、メモリ交換時に、メモリ空間を大きく占有しているプログラムを交換すると、全体のマシンが遅くなる。
セグメンテーションの「外部メモリ断片化とメモリ交換効率の低下」の問題を解決するために、メモリページングが登場した。

ページメカニズム#

ページングは、仮想メモリと物理メモリ空間全体を固定サイズのセグメントに分割する。このような連続した固定サイズのメモリ空間をページ（Page）と呼ぶ。Linux では、各ページのサイズは4KBである。
仮想アドレスと物理アドレスの間のマッピングはページテーブルを介して行われる。以下の図のように：

ページテーブルはメモリに保存されており、メモリ管理ユニット（MMU）が仮想メモリアドレスを物理アドレスに変換する作業を行う。
プロセスがアクセスする仮想アドレスがページテーブルで見つからない場合、システムはページフォールト例外を発生させ、カーネル空間に入り、物理メモリを割り当て、プロセスのページテーブルを更新し、最後にユーザースペースに戻り、プロセスの実行を再開する。

ページテーブルは何のためにあるのか？アドレス翻訳プロセスはどのようになっているのか？#

ページングメカニズム下の各アプリケーションプログラムには、対応するページテーブルが存在する。
ページングメカニズム下の仮想アドレスは 2 つの部分で構成される：

ページ番号：仮想ページ番号を使用してページテーブルから対応する物理ページ番号を取得できる；
ページ内オフセット：物理ページの開始アドレス + ページ内オフセット = 物理メモリアドレス。

具体的なアドレス翻訳プロセスは以下の通り：

MMU は最初に仮想アドレス内の仮想ページ番号を解析する；
仮想ページ番号を使用して、そのアプリケーションのページテーブルから対応する物理ページ番号を取得する（対応するページテーブル項目を見つける）；
その物理ページ番号に対応する物理ページの開始アドレス（物理アドレス）に仮想アドレス内のページ内オフセットを加えて最終的な物理アドレスを得る。

ページングはどのようにセグメンテーションの「外部メモリ断片化とメモリ交換効率の低下」の問題を解決するのか？#

メモリページングは、メモリ空間が事前に分割されているため、メモリセグメンテーションのようにセグメント間に非常に小さな隙間ができることはない。これがセグメンテーションが外部メモリ断片化を引き起こす原因である。ページングを採用することで、ページ間は密に配置されるため、外部断片化は発生しない。
しかし、メモリページングメカニズムでは、メモリの最小単位が 1 ページであるため、プログラムが 1 ページ未満のサイズであっても、最小で 1 ページを割り当てなければならず、ページ内でメモリの無駄が発生するため、メモリページングメカニズムでは内部メモリ断片化が発生する。
メモリ空間が不足している場合、オペレーティングシステムは他の実行中のプロセスの「最近使用されていない」メモリページを解放し、これを一時的にハードディスクに書き込む。これを ** スワップアウト（Swap Out）と呼ぶ。必要なときに再度読み込むことをスワップイン（Swap In）** と呼ぶ。したがって、一度にディスクに書き込まれるのはごく少数のページまたは数ページであり、あまり時間がかからず、メモリ交換の効率は相対的に高い。

さらに、ページング方式により、プログラムをロードする際に、プログラム全体を物理メモリに一度にロードする必要がなくなる。仮想メモリと物理メモリのページ間のマッピングを行った後、実際にページを物理メモリにロードするのではなく、プログラムが実行中に対応する仮想メモリページ内の命令やデータが必要になったときにのみ、物理メモリにロードすることができる。

単一レベルページテーブルにはどのような問題があるのか？なぜ多段ページテーブルが必要なのか？#

オペレーティングシステムは非常に多くのプロセスを同時に実行できるため、これはページテーブルが非常に大きくなることを意味する。
32 ビット環境では、仮想アドレス空間は合計 4GB であり、ページのサイズが 4KB（2^12）だと仮定すると、約 100 万（2^20）ページが必要であり、各「ページテーブル項目」は 4 バイトのサイズで保存されるため、全体の 4GB 空間のマッピングには4MBのメモリが必要となる。
この 4MB のページテーブルは、見た目にはそれほど大きくはない。しかし、各プロセスには独自の仮想アドレス空間があるため、各プロセスには独自のページテーブルがある。
したがって、100個のプロセスがある場合、ページテーブルを保存するために400MBのメモリが必要となり、これは非常に大きなメモリである。64 ビット環境ではさらに大きくなる。

多段ページテーブル#

上記の問題を解決するために、** 多段ページテーブル（Multi-Level Page Table）** という解決策を採用する必要がある。
この 100 万以上の「ページテーブル項目」の単一レベルページテーブルを再度ページングし、ページテーブル（一次ページテーブル）を1024個のページテーブル（二次ページテーブル）に分割し、各テーブル（二次ページテーブル）には1024個の「ページテーブル項目」が含まれ、二次ページングを形成する。以下の図のように：

二次リストは一次ページテーブルと二次ページテーブルに分かれている。一次ページテーブルには 1024 個のページテーブル項目があり、一次ページテーブルは二次ページテーブルに関連付けられ、二次ページテーブルにも同様に 1024 個のページテーブル項目がある。二次ページテーブル内の一次ページテーブル項目は一対多の関係であり、二次ページテーブルは必要に応じてロードされる（ごく少数の二次ページテーブルのみが使用されるため）、これによりスペースの占有を節約する。
仮に 2 つの二次ページテーブルが必要な場合、2 段ページテーブルのメモリ占有状況は：4KB（一次ページテーブル占有）+ 4KB * 2（二次ページテーブル占有）= 12 KB となる。
多段ページテーブルは時間と引き換えにスペースを節約する典型的なシナリオであり、ページテーブルの検索回数を増やすことでページテーブルの占有スペースを減少させる。

あなたはおそらく、二次テーブルを分割すると、4GB のアドレス空間をマッピングするのに 4KB（一次ページテーブル）+ 4MB（二次ページテーブル）のメモリが必要になり、これでは占有スペースが大きくなってしまうのではないかと疑問に思うかもしれない。#

もちろん、4GB の仮想アドレスがすべて物理メモリにマッピングされている場合、二次ページングの占有スペースは確かに大きくなるが、通常、私たちはプロセスにそれほど多くのメモリを割り当てることはない。
実際、私たちは問題を別の角度から見るべきである。コンピュータの構成原理の中で常に存在する局所性の原理を覚えているだろうか？
各プロセスは 4GB の仮想アドレス空間を持っているが、明らかにほとんどのプログラムにとって、その使用する空間は 4GB に達していない。なぜなら、対応するページテーブル項目の一部は空であり、まったく割り当てられていないからである。割り当てられたページテーブル項目があり、最近一定の時間アクセスされていないページテーブルが物理メモリが逼迫している場合、オペレーティングシステムはページをスワップアウトしてハードディスクに書き込む。つまり、物理メモリを占有しない。
二次ページングを使用すると、一次ページテーブルは 4GB の仮想アドレス空間全体をカバーできるが、もしある一次ページテーブルのページテーブル項目が使用されていない場合、そのページテーブル項目に対応する二次ページテーブルを作成する必要はなく、必要なときにのみ二次ページテーブルを作成することができる。簡単な計算をすると、仮に一次ページテーブル項目の 20％だけが使用されている場合、ページテーブルの占有メモリ空間は 4KB（一次ページテーブル）+ 20％ * 4MB（二次ページテーブル）=0.804MBとなり、これは単一レベルページテーブルの4MBと比較して大きな節約となる。

TLB#

多段ページテーブルはスペースの問題を解決したが、仮想アドレスから物理アドレスへの変換にはいくつかの変換手順が追加され、明らかにこの 2 つのアドレス変換の速度が低下し、時間的なオーバーヘッドが発生する。
プログラムには局所性があり、ある期間内にプログラム全体の実行はプログラム内の特定の部分に制限される。したがって、アクセスされるストレージスペースも特定のメモリ領域に制限される。
この特性を利用して、最も頻繁にアクセスされるページテーブル項目をより高速なハードウェアに保存することができる。そこで、コンピュータ科学者たちは CPU チップに、プログラムが最も頻繁にアクセスするページテーブル項目を保存するためのキャッシュを追加した。このキャッシュは TLB（Translation Lookaside Buffer）と呼ばれ、通常はページテーブルキャッシュ、アドレスバイパスキャッシュ、クイックテーブルなどと呼ばれる。
TLB があると、CPU はアドレス指定時に最初に TLB を確認し、見つからない場合にのみ通常のページテーブルを確認する。

セグメントページメモリ管理#

メモリのセグメンテーションとページングは対立するものではなく、同じシステムで組み合わせて使用することができる。組み合わせた場合、通常はセグメントページメモリ管理と呼ばれる。

セグメントページメモリ管理の実装方法：

まずプログラムを論理的に意味のある複数のセグメントに分割する。これは前述のセグメンテーションメカニズムである；
次に、各セグメントを複数のページに分割する。これはセグメンテーションで分割された連続空間を固定サイズのページに再分割することである；

このように、アドレス構造はセグメント番号、セグメント内ページ番号、ページ内オフセットの 3 つの部分で構成される。
セグメントページアドレス変換に使用されるデータ構造は、各プログラムに 1 つのセグメントテーブルがあり、各セグメントにはページテーブルが作成され、セグメントテーブル内のアドレスはページテーブルの開始アドレスであり、ページテーブル内のアドレスは特定のページの物理ページ番号である。以下の図のように：

セグメントページアドレス変換で物理アドレスを得るには、3 回のメモリアクセスが必要である：

最初にセグメントテーブルにアクセスし、ページテーブルの開始アドレスを得る；
次にページテーブルにアクセスし、物理ページ番号を得る；
最後に物理ページ番号とページ内オフセットを組み合わせて物理アドレスを得る。

ソフトウェアとハードウェアを組み合わせた方法でセグメントページアドレス変換を実現することができ、これによりハードウェアコストとシステムオーバーヘッドが増加するが、メモリの利用率が向上する。

malloc はどのようにメモリを割り当てるのか？#

Linux プロセスのメモリ分布はどのようになっているのか？#

Linux オペレーティングシステムでは、仮想アドレス空間はカーネル空間とユーザー空間の 2 つに分かれており、異なるビット数のシステムではアドレス空間の範囲も異なる。例えば、最も一般的な 32 ビットおよび 64 ビットシステムは以下のようになる：

ここからわかることは：

32ビットシステムのカーネル空間は1Gを占め、最上部に位置し、残りの3Gはユーザー空間である；
64ビットシステムのカーネル空間とユーザー空間はそれぞれ128Tであり、全メモリ空間の最上部と最下部を占め、残りの中間部分は未定義である。

次に、カーネル空間とユーザー空間の違いについて説明する：

プロセスがユーザーモードのとき、ユーザー空間のメモリにのみアクセスできる；
カーネルモードに入ったときのみ、カーネル空間のメモリにアクセスできる；

各プロセスは独自の仮想メモリを持っているが、各仮想メモリ内のカーネルアドレスは実際には同じ物理メモリに関連付けられている。したがって、プロセスがカーネルモードに切り替わると、カーネル空間のメモリに簡単にアクセスできる。
次に、仮想空間の分割状況をさらに詳しく見てみる。ユーザー空間とカーネル空間の分割方法は異なり、カーネル空間の分布についてはあまり詳しく説明しない。
ユーザー空間の分布状況を見てみると、32 ビットシステムの例を挙げて、関係を示す図を描いた：
この図から、ユーザー空間のメモリは低から高にかけて 6 つの異なるメモリセグメントがあることがわかる：

コードセグメント：バイナリ実行コードを含む；
データセグメント：初期化された静的定数やグローバル変数を含む；
BSS セグメント：未初期化の静的変数やグローバル変数を含む；
ヒープセグメント：動的に割り当てられたメモリであり、低アドレスから上に向かって成長する；
ファイルマッピングセグメント：動的ライブラリ、共有メモリなどを含み、低アドレスから上に向かって成長する（ハードウェアやカーネルバージョンに依存する）；
スタックセグメント：ローカル変数や関数呼び出しのコンテキストを含む。スタックのサイズは固定されており、一般的には8 MBである。もちろん、システムはサイズをカスタマイズするためのパラメータも提供している；

これら 6 つのメモリセグメントの中で、ヒープとファイルマッピングセグメントのメモリは動的に割り当てられる。例えば、C 標準ライブラリのmalloc()やmmap()を使用すると、ヒープとファイルマッピングセグメントで動的にメモリを割り当てることができる。

malloc はどのようにメモリを割り当てるのか？#

malloc がメモリを要求する際には、オペレーティングシステムに対してヒープメモリを要求する 2 つの方法がある。

方法 1：brk () システムコールを介してヒープからメモリを割り当てる
方法 2：mmap () システムコールを介してファイルマッピング領域からメモリを割り当てる；

方法 1 の実装は非常にシンプルで、brk () 関数を使用して「ヒープの頂点」ポインタを高アドレスに移動させ、新しいメモリ空間を取得する。以下の図のように：

方法 2 は、mmap () システムコールの「プライベート匿名マッピング」方式を使用して、ファイルマッピング領域からメモリを割り当てる。つまり、ファイルマッピング領域から「盗んだ」メモリを割り当てる。以下の図のように：

malloc () のソースコードでは、デフォルトでしきい値が定義されている：

ユーザーが割り当てるメモリが 128KB 未満の場合、brk () を介してメモリを要求する；
ユーザーが割り当てるメモリが 128KB を超える場合、mmap () を介してメモリを要求する；

malloc () が割り当てるのは物理メモリか？#

いいえ、malloc () が割り当てるのは仮想メモリである。

malloc (1) はどのくらいの仮想メモリを割り当てるのか？#

malloc () がメモリを割り当てる際、ユーザーの期待するバイト数に従ってメモリ空間のサイズを割り当てるのではなく、より大きなスペースを事前に割り当ててメモリプールとして使用する。
具体的にどのくらいのスペースが事前に割り当てられるかは、malloc が使用するメモリ管理者に依存する。
この例では、割り当てられるメモリが 128KB 未満であるため、brk () システムコールを介してヒープ空間からメモリを要求している。そのため、最右側に [heap] のラベルがある。
ヒープ空間のメモリアドレス範囲は 00d73000-00d94000 であり、この範囲のサイズは 132KB であることがわかる。つまり、malloc (1) は実際には 132K バイトのメモリを事前に割り当てている。

free はメモリを解放し、オペレーティングシステムに返却するのか？#

malloc が **brk ()** 方式で要求したメモリは、free がメモリを解放する際に、オペレーティングシステムにメモリを返却するのではなく、malloc のメモリプールにキャッシュされ、次回使用されるのを待つ；
malloc が **mmap ()** 方式で要求したメモリは、free がメモリを解放する際に、オペレーティングシステムにメモリを返却し、メモリが実際に解放される。

なぜすべてのメモリを mmap で割り当てないのか？#

すべて mmap を使用してメモリを割り当てると、毎回システムコールを実行することになる。
さらに、mmap で割り当てられたメモリは、解放されるたびにオペレーティングシステムに返却されるため、mmap で割り当てられた仮想アドレスは毎回ページ欠落状態となり、最初にその仮想アドレスにアクセスするとページ欠落割り込みが発生する。
頻繁に mmap で割り当てられたメモリは、毎回実行状態の切り替えが発生し、ページ欠落割り込み（最初に仮想アドレスにアクセスした後）が発生し、これにより CPU の消費が大きくなる。
これら 2 つの問題を改善するために、malloc は brk () システムコールを使用してヒープ空間からメモリを要求する際、ヒープ空間が連続しているため、より大きなメモリを事前に割り当ててメモリプールとして使用し、メモリが解放されると、次回のメモリ要求時にメモリプールから対応するメモリブロックを直接取得できる。
次回のメモリ要求時には、メモリブロックの仮想アドレスと物理アドレスのマッピング関係がまだ存在する可能性があるため、これによりシステムコールの回数が減少し、ページ欠落割り込みの回数も減少し、CPU の消費が大幅に削減される。

なぜすべてのメモリを brk で割り当てないのか？#

brk を介してヒープ空間から割り当てられたメモリは、オペレーティングシステムに返却されないため、連続して 10k、20k、30k のメモリを要求した場合、10k と 20k のメモリが解放されて空きメモリ空間となった場合、次回のメモリ要求が 30k 未満であれば、この空きメモリ空間を再利用できる。
しかし、次回のメモリ要求が 30k を超える場合、利用可能な空きメモリ空間がないため、OS に要求する必要があり、実際の使用メモリが増加し続ける。
そのため、システムが頻繁に malloc と free を行うと、特に小さなメモリの場合、ヒープ内にますます多くの利用できない断片が発生し、「メモリリーク」を引き起こす。この「リーク」現象は valgrind では検出できない。
したがって、malloc の実装では、brk と mmap の動作の違いや利点・欠点を十分に考慮し、デフォルトで大きなメモリブロック（128KB）を割り当てる際に mmap を使用することにしている。

free () 関数は 1 つのメモリアドレスを受け取るだけで、どのようにして解放するメモリのサイズを知るのか？#

malloc がユーザーモードに返すメモリの開始アドレスは、プロセスのヒープ空間の開始アドレスよりも 16 バイト多い。
この多くの16 バイトは、メモリブロックの記述情報を保存しており、例えばそのメモリブロックのサイズが含まれている。
したがって、free () 関数を実行すると、free は渡されたメモリアドレスを左に 16 バイトオフセットし、この 16 バイトから現在のメモリブロックのサイズを分析することで、解放するメモリのサイズを自然に知ることができる。

メモリが満杯になると、何が起こるのか？#

メモリの割り当てと回収のプロセスはどのようになっているのか？#

アプリケーションがこの仮想メモリを読み書きすると、CPU はこの仮想メモリにアクセスしようとする。このとき、この仮想メモリが物理メモリにマッピングされていないことがわかり、CPU はページフォールト割り込みを発生させ、プロセスはユーザーモードからカーネルモードに切り替わり、ページフォールト割り込みをカーネルのページフォールトハンドラー（ページフォールト関数）に処理させる。
ページフォールト割り込み処理関数は、空いている物理メモリがあるかどうかを確認し、あれば物理メモリを直接割り当て、仮想メモリと物理メモリの間のマッピング関係を確立する。
空いている物理メモリがない場合、カーネルはメモリ回収の作業を開始する。回収の方法は主に 2 つある：直接メモリ回収とバックグラウンドメモリ回収。

バックグラウンドメモリ回収（kswapd）：物理メモリが逼迫しているとき、kswapd カーネルスレッドを起動してメモリを回収する。このメモリ回収プロセスは非同期的であり、プロセスの実行をブロックしない。
直接メモリ回収（direct reclaim）：バックグラウンドの非同期回収がプロセスのメモリ要求の速度に追いつかない場合、直接回収を開始する。このメモリ回収プロセスは同期的であり、プロセスの実行をブロックする。
もし直接メモリ回収後も空いている物理メモリが今回の物理メモリの要求を満たせない場合、カーネルは最後の手段を取る。すなわち、OOM（Out of Memory）メカニズムを発動する。

OOM Killer メカニズムは、アルゴリズムに基づいて物理メモリを高く占有しているプロセスを選択し、それを終了させてメモリリソースを解放する。物理メモリが依然として不足している場合、OOM Killer は物理メモリを高く占有しているプロセスをさらに終了させ、十分なメモリを解放するまで続ける。

どのメモリが回収可能か？#

主に 2 種類のメモリが回収可能であり、それぞれの回収方法は異なる。

ファイルページ（File-backed Page）：カーネルがキャッシュしたディスクデータ（Buffer）やカーネルがキャッシュしたファイルデータ（Cache）をファイルページと呼ぶ。ほとんどのファイルページは、直接メモリを解放でき、必要なときに再びディスクから読み込むことができる。ただし、アプリケーションによって変更され、まだディスクに書き込まれていないデータ（つまり、ダーティページ）は、まずディスクに書き込んでからメモリを解放する必要がある。したがって、クリーンページの回収方法はメモリを直接解放し、ダーティページの回収方法はまずディスクに書き戻してからメモリを解放する。
匿名ページ（Anonymous Page）：この部分のメモリには実際の媒体がなく、ファイルキャッシュのようなハードディスクファイルの媒体がない。例えば、ヒープやスタックデータなど。この部分のメモリは再度アクセスされる可能性が高いため、直接メモリを解放することはできず、回収の方法は Linux のスワップメカニズムを介して行われる。スワップは、あまりアクセスされないメモリを最初にディスクに書き込み、そのメモリを解放して他のより必要なプロセスに使用させる。再度これらのメモリにアクセスする際には、ディスクから再びメモリに読み込むことができる。

ファイルページと匿名ページの回収は LRU アルゴリズムに基づいており、つまり、あまりアクセスされていないメモリを優先的に回収する。LRU 回収アルゴリズムは、実際には active と inactive の 2 つの双方向リストを維持している：

active_list：最近アクセスされた（アクティブな）メモリページを保持する；
inactive_list：あまりアクセスされていない（非アクティブな）メモリページを保持する；
リストの尾に近いほど、そのメモリページはあまりアクセスされていないことを示す。したがって、メモリを回収する際、システムは活性度に基づいて優先的に非アクティブなメモリを回収できる。

メモリ回収がもたらすパフォーマンスへの影響#

メモリ回収の操作は基本的にディスク I/O が発生するため、メモリ回収の操作が非常に頻繁に行われると、ディスク I/O の回数が多くなり、このプロセスはシステムのパフォーマンスに影響を与え、全体のシステムが非常に遅く感じられる。
解決方法。

ファイルページと匿名ページの回収傾向を調整する#

ファイルページと匿名ページの回収操作を見てみると、ファイルページの回収操作はシステムへの影響が匿名ページの回収操作よりも少ない。なぜなら、ファイルページのクリーンページ回収はディスク I/O を発生させないが、匿名ページのスワップ入出力の両方の操作はディスク I/O を発生させるからである。
Linux は/proc/sys/vm/swappinessオプションを提供しており、ファイルページと匿名ページの回収傾向を調整するために使用される。
swappiness の範囲は 0-100 であり、数値が大きいほど、スワップを積極的に使用し、匿名ページの回収により傾く。数値が小さいほど、スワップを消極的に使用し、ファイルページの回収により傾く。
一般的には、swappiness を 0 に設定することが推奨されている（デフォルト値は 60）。これにより、メモリ回収時にファイルページの回収により傾くが、匿名ページの回収を行わないわけではない。

kswapd カーネルスレッドによるメモリの非同期回収を早期に発動する#

カーネルは、現在の残りメモリ（pages_free）が十分か逼迫しているかを評価するために、3 つのメモリ閾値（watermark、または水位）を定義している：

ページ最小閾値（pages_min）；
ページ低閾値（pages_low）；
ページ高閾値（pages_high）；

これら 3 つのメモリ閾値は、4 つのメモリ使用状況に分けられる。

図のオレンジ色の部分：残りメモリ（pages_free）がページ低閾値（pages_low）とページ最小閾値（pages_min）の間にある場合、メモリの圧力が高く、残りメモリが少ないことを示す。この時、kswapd0 がメモリ回収を実行し、残りメモリが高閾値（pages_high）を超えるまで続ける。メモリ回収が発生するが、アプリケーションの実行をブロックすることはない。なぜなら、両者の関係は非同期的であるからである。
図の赤色の部分：残りメモリ（pages_free）がページ最小閾値（pages_min）を下回る場合、ユーザーが利用可能なメモリがすべて消費されていることを示し、この時直接メモリ回収が発動され、アプリケーションがブロックされる。なぜなら、両者の関係は同期的であるからである。

ページ低閾値（pages_low）は、カーネルオプション/proc/sys/vm/min_free_kbytesを介して間接的に設定することができる（このパラメータは、システムが保持する空きメモリの最低限度を示す）。
min_free_kbytes はページ最小閾値（pages_min）を設定するが、ページ高閾値（pages_high）とページ低閾値（pages_low）はページ最小閾値（pages_min）に基づいて計算される。これらの計算関係は以下の通り：

pages_min = min_free_kbytes
pages_low = pages_min*5/4
pages_high = pages_min*3/2

4. プロセスが OOM によって殺されないように保護するには？#

Linux は、どの基準で殺されるプロセスを選択するのか？これについては、Linux カーネル内にoom_badness()関数があり、システム内で殺される可能性のあるプロセスをスキャンし、各プロセスにスコアを付け、スコアが最も高いプロセスが最初に殺される。
「システム全体の利用可能なページ数」に「OOM 調整値 oom_score_adj」を掛けて 1000 で割り、最後にプロセスがすでに使用している物理ページ数を加えた値が大きいほど、そのプロセスが OOM Kill される可能性が高くなる。

もし特定のプロセスが最初に殺されないようにしたい場合、そのプロセスの oom_score_adj を調整して、そのプロセスのスコア結果を変更し、OOM によって殺される確率を下げることができる。
もし特定のプロセスがどんな場合でも殺されないようにしたい場合、その oom_score_adj を - 1000 に設定することができる。

7. プリフェッチの無効化とキャッシュ汚染の問題を回避するには？#

1.Linux と MySQL のキャッシュ#

Linux オペレーティングシステムのキャッシュ#

アプリケーションがファイルのデータを読み取るとき、Linux オペレーティングシステムは読み取ったファイルデータをキャッシュし、ファイルシステム内のページキャッシュに保存する。
ページキャッシュはメモリ空間内のデータであり、メモリアクセスはディスクアクセスよりもはるかに速いため、次回同じデータにアクセスする際にはディスク I/O を介さず、キャッシュにヒットすれば直接データを返すことができる。
したがって、ページキャッシュはデータアクセスを加速する役割を果たす。

MySQL のキャッシュ#

MySQL のデータはディスクに保存されており、データベースの読み書き性能を向上させるために、InnoDB ストレージエンジンはバッファプール（Buffer Pool）を設計している。バッファプールはメモリ空間内のデータである。
バッファプールがあることで：

データを読み取る際、データがバッファプール内に存在する場合、クライアントはバッファプール内のデータを直接読み取り、そうでない場合はディスクから読み取る。
データを変更する際、まずバッファプール内のデータが存在するページを変更し、そのページをダーティページに設定し、最後にバックグラウンドスレッドがダーティページをディスクに書き込む。

2. 従来の LRU はメモリデータをどのように管理しているのか？#

従来の LRU アルゴリズムは、Linux や MySQL では使用されていない。なぜなら、従来の LRU アルゴリズムは以下の 2 つの問題を回避できないからである：

プリフェッチの無効化がキャッシュヒット率の低下を引き起こす；
キャッシュ汚染がキャッシュヒット率の低下を引き起こす；

2. プリフェッチの無効化、どうするか？#

プリフェッチメカニズムとは何か？#

Linux オペレーティングシステムは、ページキャッシュに基づく読み取りキャッシュメカニズムにプリフェッチメカニズムを提供している。例えば：

アプリケーションがディスク上のファイル A のオフセット 0-3KB の範囲内のデータを読み取ろうとする場合、ディスクの基本的な読み書き単位はブロック（4KB）であるため、オペレーティングシステムは少なくとも 0-4KB の内容を読み取る必要がある。これはちょうど 1 ページに収まる。
しかし、オペレーティングシステムは空間局所性の原理に基づいて（現在アクセスされているデータに近いデータは、将来的に高い確率でアクセスされる）、ディスクブロックオフセット [4KB,8KB)、[8KB,12KB)、[12KB,16KB) もメモリに読み込むことを選択し、追加でメモリに 3 つのページを要求する。
以下の図は、オペレーティングシステムのプリフェッチメカニズムを示している：

したがって、プリフェッチメカニズムによってもたらされる利点は、ディスク I/O の回数を減少させ、システムのディスク I/O スループットを向上させることである。
MySQL InnoDB ストレージエンジンのバッファプールにも類似のプリフェッチメカニズムがあり、MySQL はディスクからページをロードする際に、隣接するページも一緒にロードする。これはディスク I/O を減少させることを目的としている。

プリフェッチの無効化はどのような問題を引き起こすのか？#

もしこれらの事前に読み込まれたページがアクセスされなかった場合、このプリフェッチ作業は無駄になる。これがプリフェッチの無効化である。
従来の LRU アルゴリズムを使用すると、「プリフェッチページ」は LRU リストの先頭に配置され、メモリ空間が不足している場合、末尾のページを淘汰する必要がある。
もしこれらの「プリフェッチページ」が常にアクセスされない場合、非常に奇妙な問題が発生する。アクセスされないプリフェッチページが LRU リストの前方の位置を占め、末尾で淘汰されるページはホットデータである可能性があり、これによりキャッシュヒット率が大幅に低下する。

プリフェッチの無効化による影響を回避するには？#

Linux オペレーティングシステムと MySQL InnoDB は、従来の LRU リストを改善することでプリフェッチの無効化による影響を回避している。具体的な改善は以下の通り：

Linux オペレーティングシステムは、2 つの LRU リストを実装している：アクティブ LRU リスト（active_list）と非アクティブ LRU リスト（inactive_list）；
MySQL の InnoDB ストレージエンジンは、1 つの LRU リストを 2 つの領域に分割している：young 領域と old 領域。
これら 2 つの改善方法は、設計思想が類似しており、データを冷データとホットデータに分割し、それぞれに LRU アルゴリズムを適用する。従来の LRU アルゴリズムのように、すべてのデータが 1 つの LRU アルゴリズムで管理されるわけではない。
例を挙げてみよう。
長さ 10 の LRU リストがあり、young 領域が 70％、old 領域が 30％を占めていると仮定する：

今、番号 20 のページがプリフェッチされた場合、このページは old 領域の先頭に挿入され、old 領域の末尾のページ（10 号）は淘汰される。

もし 20 号ページが常にアクセスされない場合、young 領域の位置を占有することはなく、old 領域のデータよりも早く淘汰される。
もし 20 号ページがプリフェッチされた後、すぐにアクセスされた場合、young 領域の先頭に挿入され、young 領域の末尾のページ（7 号）は old 領域に押し出され、old 領域の先頭となる。このプロセスではページが淘汰されることはない。

3. キャッシュ汚染、どうするか？#

キャッシュ汚染とは何か？#

大量のデータを一度に読み取ると、それらのデータが一度アクセスされるため、これらの大量のデータがすべて「アクティブ LRU リスト」に追加され、その結果、以前アクティブ LRU リスト（または young 領域）にキャッシュされていたホットデータがすべて淘汰される。もしこれらの大量のデータが長い間アクセスされない場合、全体のアクティブ LRU リスト（または young 領域）が汚染される。

キャッシュ汚染による影響を回避するには？#

前述の LRU アルゴリズムでは、データが一度アクセスされると、データがアクティブ LRU リスト（または young 領域）に追加される。この LRU アルゴリズムは、アクティブ LRU リスト（または young 領域）への入り口が低すぎる！まさにこの入り口が低すぎるため、キャッシュ汚染が発生したときに、アクティブ LRU リスト内のホットデータが簡単に淘汰されてしまう。
したがって、アクティブ LRU リスト（または young 領域）への入り口を高くすることで、アクティブ LRU リスト（または young 領域）内のホットデータが簡単に置き換えられないようにすることができる。
Linux オペレーティングシステムと MySQL InnoDB ストレージエンジンは、それぞれ次のようにして入り口を高くしている：

Linux オペレーティングシステム：メモリページが2 回目にアクセスされたときにのみ、ページを inactive list から active list に昇格させる。
MySQL InnoDB：メモリページが2 回目にアクセスされたとき、そのページが old 領域から young 領域に昇格することはなく、old 領域に留まる時間を判断する：
- 2 回目のアクセス時間と最初のアクセス時間が1 秒以内（デフォルト値）であれば、そのページは昇格しない；
- 2 回目のアクセス時間と最初のアクセス時間が1 秒を超える場合、そのページは昇格する；
  アクティブ LRU リスト（または young 領域）への入り口を高くすることで、キャッシュ汚染による影響を回避することができる。
  大量のデータを一度に読み取る場合、これらの大量のデータが一度しかアクセスされない場合、それらはアクティブ LRU リスト（または young 領域）に入らず、ホットデータが淘汰されることはなく、非アクティブ LRU リスト（または old 領域）に留まることになり、後で早く淘汰される。