現代オペレーティングシステム - 仮想メモリ

なぜ仮想メモリを使用するのか#

一般的なオペレーティングシステムでは、複数のプロセスが同じ物理メモリリソースを使用して実行されます。オペレーティングシステムがメモリ管理を行う際、プロセスが物理メモリを直接使用することを許可すると、いくつかの問題が発生します:

オペレーティングシステムがプロセスに割り当てるスペースが不足し、再度メモリを要求する際にスペースが連続していない可能性があります。
同じ物理アドレス空間を共有しているため、プロセス A がプロセス B が使用しているアドレスに書き込む可能性があります。

効率性と安全性を考慮して、仮想メモリが導入されました：アプリケーションプロセスは仮想アドレスを通じて物理メモリを読み書きし、CPU 内部の MMU が仮想アドレスを具体的な物理アドレスに変換して対応する読み書き操作を行います。オペレーティングシステムは各プロセスの仮想アドレスと物理アドレスのマッピングを構築します。各プロセスは、自分が連続した完全なアドレス空間を持っていると考えることができます。

初期のほとんどのシステムで使用されていた仮想メモリ管理方式はセグメント方式です：オペレーティングシステムは仮想アドレス空間と物理アドレス空間を異なるサイズのセグメント（例えばコードセグメント、データセグメントなど）に分割し、セグメントテーブルを通じて仮想アドレスから物理アドレスへのマッピングを実現しますが、物理セグメント間で断片化が発生しやすくなります。

仮想アドレスは：セグメント番号 + セグメント内アドレス（オフセット）
MMU は セグメントテーブルベースレジスタ に基づいてセグメントテーブルを見つけます。
セグメント番号を使ってセグメントテーブル内で対応するセグメントの開始物理アドレスを見つけます。
物理セグメントの開始アドレス + オフセットで物理アドレスを得ます。

仮想メモリのページング#

現代のオペレーティングシステムは通常、ページングメカニズムを使用して仮想メモリを管理します。

オペレーティングシステムは最初に仮想アドレス空間と物理アドレス空間をより小さく連続した同じサイズのページに分割し、ページテーブルを通じて仮想アドレスから物理アドレスへのマッピングを実現します。ユーザープロセスは全ての仮想アドレス空間を使用でき、カーネルは各プロセスのためにページテーブルを維持します。これにより、たとえ二つのプロセスが同じ仮想アドレスを使用しても、ページテーブルでマッピングされた物理アドレスが異なれば衝突は発生しません。

仮想アドレスは：ページ番号 + ページ内オフセット
MMU は ページテーブルベースレジスタ に基づいて対応するプロセスのページテーブルを見つけます。
ページテーブル内でページ番号に対応する物理ページの開始アドレスを見つけます。
物理ページの開始アドレス + ページ内オフセットで物理アドレスを得ます。

多段ページテーブル#

ページテーブル項目が占める物理メモリ空間を圧縮するために（64 ビットの仮想アドレス空間でページサイズが 4KB の場合、単一ページテーブルが占める空間を考慮）、通常は多段ページテーブルが使用されます。多段ページテーブルは仮想アドレスのページ番号部分をいくつかの部分に分割し、それぞれの部分が 1 つのページテーブル項目に対応します。AArch64 アーキテクチャの例を挙げると、仮想アドレスは 48 ビットの有効ビットを使用し（つまり仮想アドレス空間のサイズは 2^48）、下位 12 ビットがページ内オフセットを示し、残りの 36 ビットが 4 段階のページテーブルに分割されます。

まず TTBR0_EL1 レジスタを通じて第 0 レベルのページテーブルの物理アドレスを見つけます。
第 47-39 ビットを使って第 0 レベルのページテーブル内の項目を見つけます：第 1 レベルのページテーブルの物理アドレス。
第 38-30 ビットを使って第 1 レベルのページテーブル内の項目を見つけます：第 2 レベルのページテーブルの物理アドレス。
第 29-21 ビットを使って第 2 レベルのページテーブル内の項目を見つけます：第 3 レベルのページテーブルの物理アドレス。
第 20-12 ビットを使って第 3 レベルのページテーブル内の項目を見つけます：対応する物理ページ番号。
第 11-0 ビット（ページ内オフセット）を物理ページ番号に加えて真の物理アドレスを得ます。

通常、ページテーブル項目には物理アドレスを格納するだけでなく、ページテーブル項目に対応する物理アドレスが存在するかどうか、またはダーティページかどうかなどのフラグも格納されます。多段ページテーブル項目の検索プロセス中に、特定のページテーブル項目に対応する物理アドレスが存在しない場合、検索を直接終了することができます。

多段ページテーブルの第 i レベルでは、すべてのページテーブル項目が第 i+1 レベルのページテーブルを指すわけではありません。あるプロセスが 4KB のメモリ空間のみを使用している場合、その第 0 レベルのページテーブルには実際に第 1 レベルのページテーブルを指す項目が 1 つだけ存在し、第 1 レベルのページテーブルにも第 2 レベルのページテーブルを指す項目が 1 つだけ存在します。以降も同様です。このように、合計で 4 つのページテーブルページしか使用されません。もし連続した 4KB*64 のメモリ空間を使用した場合、これら 64 ページの前の 3 レベルのページテーブルアドレスがちょうど同じであれば、最終的に 4 つのページテーブルページしか使用されず、非常にスペースを節約できます。以下の図を参照してください:

アドレス変換

アドレス変換キャッシュ TLB とページテーブル切り替え#

アドレス変換の効率を向上させるために、MMU 内には仮想ページ番号から物理ページ番号へのマッピングをキャッシュするための TLB ハードウェアがあります。TLB 内部には CPU のような多層キャッシュ（例えば L1 命令キャッシュ、L1 データキャッシュ、L2 キャッシュなど）が存在します。一般的に、TLB 内に格納できるエントリは少なく、数千のエントリしかありません。一度のアドレス変換プロセスで、MMU は最初に TLB を通じてキャッシュを照会し、キャッシュがヒットすれば直接返します。ヒットしなければ多段ページテーブルを照会し、最終的に結果を TLB に書き戻します。TLB が満杯の場合は、ハードウェアのポリシーに基づいて特定の項目を置き換えます。また、オペレーティングシステムでは通常、複数のプロセスが実行されており、異なるプロセスが使用する仮想アドレスが同じである可能性があるため、TLB 内のキャッシュ内容が現在のプロセスのページテーブルと一致することを確認する必要があります。オペレーティングシステムはプロセス切り替え（ページテーブル切り替え時）を実行する際に TLB を積極的にフラッシュします。

プロセス切り替えのたびに TLB をフラッシュ（クリア）することは、プロセスが開始されたときに大量の TLB ミスを引き起こす可能性があるため、現代の CPU ハードウェアはプロセスタグ機能を提供しています。例えば amd64 の下でのProcess Context IDentifier、オペレーティングシステムは異なるプロセスに異なる PCID を割り当て、それをページテーブルベースレジスタと TLB のキャッシュ項目に書き込みます。これにより、プロセスを切り替えても TLB は現在のページテーブルベースレジスタ内の PCID とキャッシュエントリ内の PCID を使用して異なるプロセスのキャッシュエントリを区別でき、TLB をクリアする必要がなくなります。しかし、ページテーブルを変更する際には、オペレーティングシステムは一貫性を保つために TLB を適時にフラッシュする必要があります。この方法の欠点は、単一のプロセスが使用できる TLB エントリがさらに減少することです。

AArch64 アーキテクチャでは、一般にカーネルとユーザープロセスは異なるページテーブルベースレジスタを使用するため、カーネルモード（システムコールを実行）に切り替える際にページテーブルを切り替える必要はありません。一方、x86-64 アーキテクチャではページテーブルベースレジスタは 1 つしかありませんが、カーネルは独自のページテーブルを使用せず、各プロセスのアドレス空間の上位部分に自分のアドレス空間をマッピングしています（複数のユーザープロセスが同じカーネルアドレス空間を共有しているのに相当します）ので、ページテーブルを切り替える必要もありません。

ページ置換とページフォルト#

注意：以下での割り当ては、プロセスがオペレーティングシステムに一定のサイズのスペースを要求し、オペレーティングシステムがプロセスに仮想アドレス空間内の一部のスペースを割り当て、その開始アドレスと終了アドレスをプロセスに返すことを指します。

アプリケーションプロセスの実行中に、事前にメモリスペースを要求します（例えば Linux では brk または mmap システムコールを使用）。これらのスペースのアドレスに対して読み書きを行う前に、オペレーティングシステムはそれを実際の物理ページにマッピングしません。つまり、ページテーブル内のこれらのアドレスが示す仮想ページに対応する物理ページのマッピングは存在しません。最初の読み書き時に CPU がページテーブルをチェックし、対応する物理ページが存在しないことを発見すると、ページフォルト例外が発生します。この時、CPU はオペレーティングシステムが事前に設定したpage fault handler関数を実行し、適切な物理ページを見つけてアドレスをページテーブルに書き込みます。実際には、ページフォルト例外が発生する回数を減らすために、ページフォルト処理関数を実行する際に隣接する複数の仮想ページに物理ページを同時にマッピングすることがあります。

プロセスが実行中に物理メモリのサイズを超えるメモリリソースを使用する可能性があり、その際にページフォルト例外が再度発生した場合、オペレーティングシステムは一部の物理ページをディスクなどのより低レベルのストレージデバイスに書き込むことによって、現在実行中のプロセスに空いている物理ページを提供します。このプロセスはページ置換 / ページアウトと呼ばれ、ページ置換を実行する際にオペレーティングシステムは物理ページの内容をディスクに書き込み、対応するページテーブル項目をクリアし、物理ページがディスク上にある位置を保存する必要があります。置換された仮想ページが再度アクセスされると、オペレーティングシステムは以前にディスクに置換した内容を再び物理ページに書き込み、プロセスのページテーブルを変更して仮想ページを新しい物理ページに再マッピングします。このプロセスはページインと呼ばれます。

ファイルシステム内のスワップパーティションは、仮想メモリがページ置換時に使用するディスクパーティションです。ディスク IO の効率が低いことを考慮して、オペレーティングシステムはページインを実行する際に、アクセスされる可能性のある複数のページを予測し、一緒にページインして IO の回数を減らします。

アプリケーションが特定の仮想ページにアクセスしてページフォルト例外を引き起こすと、オペレーティングシステムはこの仮想ページが未割り当て状態にあるのか、割り当て済みだが未マッピング状態にあるのかを判断する必要があります。オペレーティングシステムは、割り当て済みの仮想ページに対してのみ物理ページへのマッピングを実行します。Linux では、プロセスの仮想アドレス空間は複数のVirtual Memory Areaに分割されており、各 VMA には一定の範囲（領域の開始アドレスから領域の終了アドレスまで）が存在します。例えば、コード、スタック、ヒープはそれぞれ異なる VMA に対応します。ページフォルト例外が発生した際、オペレーティングシステムは仮想ページが特定の VMA に属しているかどうかを確認することで、割り当て済みかどうかを判断できます。

仮想メモリの機能#

共有メモリ#

仮想ページはプロセスのページテーブルを通じて物理ページにマッピングされているため、オペレーティングシステムはプロセス A とプロセス B の二つの仮想ページ A1 と B1 を同じ物理ページ P にマッピングすることで、プロセス間のメモリ共有を実現できます。任意のプロセスが共有メモリに書き込むと、別のプロセスがそれを読み取ることができます。

書き込み時コピー#

共有メモリを通じてCopy On Write、つまり書き込み時コピー機能を実現できます。例えば、Linux ではプロセスが fork を通じて子プロセスを作成できます。子プロセスが作成されたとき、親子プロセスのメモリデータは完全に同じであるため、Linux は子プロセスのためにページテーブルのコピーを作成するだけで、マッピングを変更せず、同時に Linux はページテーブル内のこの共有メモリの権限を読み取り専用に設定します。いずれかのプロセスがこの仮想ページに書き込むと、権限不足によりページフォルト例外が発生し、その後オペレーティングシステムはページフォルト部分のデータを新しい物理ページにコピーし、新しい物理ページをページフォルト例外を引き起こしたプロセスのページテーブル項目に書き込み、権限を回復します。fork 以外にも、複数のプロセスが共有メモリを通じて同じ動的リンクライブラリにマッピングすることで、メモリ使用量を削減できます。

共有メモリと書き込み時コピー

メモリ重複排除#

COW に基づいて、オペレーティングシステムは（定期的に）複数の同じ内容の物理ページを 1 つに統合し、すべての関連するページテーブルマッピングをこの唯一の物理ページに変更することで、メモリ利用効率を向上させる機能を持っています。この機能はメモリ重複排除と呼ばれます。Linux ではこの機能が実装されており、Kernel Same-page Mergingと呼ばれます。この機能を使用すると、パフォーマンスに一定の影響を与えることが想像できます。また、特定のセキュリティ問題も発生する可能性があります。例えば、攻撃者はデータを列挙して構築し、その後メモリ重複排除を待つことで、アクセス遅延（COW によって引き起こされるページフォルトによる）を確認し、メモリ重複排除が発生したかどうかを推測できます。もし発生した場合、攻撃者は現在の物理アドレス空間内に現在構築したものと同じデータが存在することを推測できます。しかし、オペレーティングシステムは同一ユーザーのプロセス間でのみ重複排除を行うことで、この問題を回避できます。

メモリ圧縮#

オペレーティングシステムは、あまり使用されないメモリデータを圧縮することで物理ページの使用を減少させることができます。Linux では、メモリ内に zswap 領域があり、圧縮されたメモリデータを保存します。メモリデータが圧縮されると、最初に zswap に置かれ、物理メモリリソースが不足すると、zswap は一括でディスクにページアウトします。これにより、即座のページアウトによるディスク IO を減少させ、メモリ使用効率を向上させることができます。

大ページ#

前述のように、TLB のキャッシュエントリは少なく、4KB のメモリページサイズの場合、十分でない可能性があります（頻繁に TLB ミスが発生し、効率が非常に低下します）。そのため、多くのオペレーティングシステムは大ページ機能を提供しています。メモリページのサイズを 2MB または 1GB に増やすことで、TLB の占有量を減少させます。Linux では、transparent huge page、つまり透明大ページメカニズムが提供されており、連続する 4KB ページを自動的に 1 つの 2MB ページに統合します。

大ページを使用することで、TLB キャッシュエントリの占有を大幅に減少させ、TLB のヒット率を向上させることができますが、大ページはメモリの使用効率を低下させる可能性もあります。例えば、2MB の大メモリページが実際には 256KB しか使用されていない場合、非常に高いリソースの浪費を引き起こします。

参考と引用
《現代オペレーティングシステム：原理と実装》