仮想記憶（仮想メモリ）
現在、CSの勉強のために、コンピュータアーキテクチャ (電子情報通信レクチャーシリーズ)を読んでいる。
前回は、キャッシュメモリに焦点を当てた。今回は、仮想記憶についてまとめていく。
仮想記憶（仮想メモリ）とは
仮想記憶（仮想メモリ）は、物理上のメモリである主記憶装置（RAM）だけでなく、ハードディスクなどの補助記憶装置を組み合わせることで、主記憶装置（RAM）の容量を、命令語に入っているアドレスの許す限りの大きさに拡張する手法である。
- なぜ拡張する必要があるのか
- コンピュータ上に入っている物理上のメモリ（RAM）だけでは容量が足りず、プログラムを実行することができない。
- 拡張する手法？
- メインメモリやキャッシュメモリのように、仮想記憶（仮想メモリ）を「記憶装置」のような表現にしているが、記憶装置ではなく、実質的にユーザーにとってメインメモリの容量を拡張するテクニック（手法）である。
- 「実質的に」が意味するところは、キャッシュメモリ同様に、仮想記憶の主記憶と補助記憶を「巨大な主記憶」として使えるように透過性を持たせている。
- キャッシュメモリ管理はハードウェアによって行われていたが、仮想記憶（メモリ）管理はオペレーティングシステム（OS）によって行われる。
- 命令語に入っているアドレスの許す限りの大きさとは
- 仮想記憶の導入メリット
- 主記憶よりも大きな容量のメモリがあるものとしてプログラムを書くことができる
- メモリ領域の保護
- 複数のプログラムが互いのデータを読み書きする場合、意図的か否かを問わず相互干渉できないようにするための一連の機構。
- 複数のプログラムが1つの物理記憶を共有して安全に分かち合って使えるようになる
仮想記憶の構成
仮想記憶とキャッシュの概念は基本的には同じである。しかし、両者の歴史的背景から異なった用語が使用されている。
- 仮想記憶のブロック：ページ
- 仮想記憶のミス：ページフォールト
仮想記憶を使用する場合、CPUによって仮想アドレスが生成される。この仮想アドレスが、ハードウェアとソフトウェアの連携によって物理アドレスに変換される。物理アドレスに基づいて、実際に主記憶装置へのアクセスが行われる。仮想記憶と物理メモリのアドレス対応付けの過程をアドレス・マッピング、またアドレス変換と呼ぶ。
プロセスを作成するときに、そのプロセスの全てのページ用の領域をフラッシュ・メモリまたはディスク上に取る。このディスク領域をスワップ領域と呼ぶ。同時に、OSは各仮想ページがディスク上のどこに格納されているかを記録するデータ構造を主記憶上に作成する。このデータ構造をページテーブルと呼ぶ。
物理メモリ上に空き領域を作り出すために、あるメモリ領域の記憶内容をストレージ上のスワップ領域に書き出して抹消する操作のことをページアウト（スワップアウト）と呼ぶ。
反対に、ストレージ上に退避した内容へのアクセス要求があり、物理メモリ上の領域に書き戻してアクセス可能にする操作のことをページイン（スワップイン）と呼ぶ。
仮想記憶システムの設計を左右する要因はページフォールトが発生した時の処理コストの高さである。ディスク上での1件のページフォールトの処理に要するクロック・サイクル数は何百万にも及ぶ。この膨大なミス・ペナルティに対処する必要がある。
ページテーブルによるアドレス変換
仮想記憶において、ミスの発生件数を出来るだけ減らすために、競合性ミスが発生しないフルアソシアティブ形を用いる。ただし、キャッシュでやった全エントリのタグ比較による連想処理は現実的ではない。仮想記憶では、ページテーブルを用いて、仮想アドレスのページ番号をインデックスとして、対応する物理ページの所在を突き止める。
仮想アドレスは、仮想ページ番号とページ内オフセットからなる。ページ内オフセットは、仮想アドレスと物理アドレスで共通である。
各プログラムごとにページテーブルが用意され、それを通じてプログラムの仮想アドレス空間が物理メモリにマッピングされる。メモリ中のページテーブルの所在位置を示すために、ページテーブルの始点を指すレジスタ、ページテーブルレジスタをハードウェアに用意する。
ページテーブルの各エントリには、有効ビット、書込み可能ビットなどの制御フラグビットと、物理ページ番号またはディスク上のアドレスが格納されている。有効ビットがオンの場合に、このエントリの物理ページ番号が有効となり、ページ内オフセットと組み合わせて物理アドレスが求められる。
上図では、仮想アドレスを32ビット、ページサイズを4KB、物理アドレスを30ビットと仮定している。ページサイズが4KBなので、ページ内にあるアドレスは全部で4KB、すなわち 212 バイトとなる。212 バイトあれば、ページ内のアドレスを全て表現できるので、ページ内オフセットは12bitとなる。よって、仮想ページ番号は32 - 12 = 20bitとなる。
ページフォールト
仮想ページの有効ビットがオフであると、そのページにアクセスされた時にページフォールトが発生する。ページフォールトは、MMU（Memory Management Unit）により検知される。
- MMUがページフォールトを検知し、例外処理の割り込みが発生する（CPUの処理を中断する）
- OSに制御が移され、OSは特権的な命令を用いて以下の処理を実行する
- 物理メモリ中のページが全て使用されている場合、近い将来に使用される可能性が最も低いと思われるページをディスク上のスワップ領域に書き込む。（ページアウト）
- LRU（Least Recently Used）法
- 過去最も参照されていないページを置き換える
- 厳密に実現しようとするとコストが高くなる
- OSでは、近似的なLRU法が用いられる（使用ビット、参照ビットを用意し、ページにアクセスされるたびにフラグをセットする。OSはこの使用ビットを定期的にクリアし、ある期間にどのページがアクセスされたかを判定できるようにする。）
- LRU（Least Recently Used）法
- ページテーブルのエントリに入っている物理ページ番号から、ディスクの中から該当するページを探し出し、そのページを物理メモリに書き込む。（ページイン）
- 物理メモリのデータが書き換わったので、ページテーブルを更新する
- ページアウトで物理メモリからスワップ領域に書き出したページの有効ビットのフラグをオフにする
- ページインで物理メモリに書き込んだページの物理ページ番号を書き込み、有効ビットのフラグをオンにする
- 物理メモリ中のページが全て使用されている場合、近い将来に使用される可能性が最も低いと思われるページをディスク上のスワップ領域に書き込む。（ページアウト）
上記の流れの一例を示す。
書込みはライト・バック方式
キャッシュへのアクセス時間と主記憶へのアクセス時間の差は数十〜数百クロック・サイクルである。したがって、書き込みにはライト・スルー方式を採用できる。ただし、書き込みにかかる時間をプロセッサに対して隠すために、書き込みバッファを使用する必要がある。
仮想記憶システムでは、補助記憶装置への書き込みには数百万クロック・サイクルを要することがありえる。そのため、書き込みバッファを利用してディスクへも同時に書き込みを行うライト・スルー方式は非現実的である。仮想記憶システムでは、ライト・バック方式を取らざるをえない。ライト・バック方式では、個々の書き込みはページに対してだけ行われる。そして、メモリ内のページが置き換え対象になったときに、ページをディスクにコピーして戻す。
書き戻し操作には高いコストがかかる。そのため、ページを置き換えるときに、そのページを書き戻す必要があるかどうかを判定できるように、ページテーブルにダーティビット（dirty bit）を追加する。ページに何らかの書き込む時には、このダーティビットのフラグも同時にセットする。ダーティビットのフラグが立っているページをダーティ・ページと呼ぶ。
アドレス変換の高速化：TLB
ページ・テーブルは主記憶装置に格納されるので、各メモリ・アクセスには最低でも2倍の時間が必要になる。
アクセスの性能を改善する鍵は、ページテーブルを参照する際の局所性にある。ある仮想ページ番号の変換が行われると、同じ変換が近いうちに再び行われる可能性が高い。なぜならば、そのページ上の語の参照には時間的および空間的局所性があるからである。
そのため、現代のプロセッサには最近行われたアドレス変換の内容を一時的に保存しておく専用のキャッシュが備えられている。この特別なアドレス変換キャッシュはアドレス変換バッファ（TLB：Translation Lookaside Buffer）と呼ばれる。
TLBはフルアソシアティブのキャッシュであり、タグの大きさは仮想ページ番号の大きさとなる。ページテーブルを参照する代わりにTLBにアクセスするので、TLBには参照ビットやダーティビットのような制御ビットも含める必要がある。また、TLBは命令用とデータ用の2種類を持つのが一般的である。
TLBの動作は以下のようになる。
- メモリアクセスが起こると、仮想ページ番号をタグとして、TLBが参照される
- TLBがヒットすると、該当する物理ページ番号が取り出され、ページ内オフセットと合わせて物理アドレスが作られる
- TLBがミスすると、ページテーブルが参照され、TLBの空いているエントリに現在参照している仮想ページ番号に対応する物理ページ番号が入れられる。TLBが空いていない場合、LRUなどのやり方でエントリが一つ空けられる。
仮想アドレスから物理アドレスを求めるときには、TLBミス、ページフォールトの二つの例外が発生する可能性がある。
- TLBミス
- TLBのエントリを一つ空けてページテーブルから対象となる物理ページ番号を書き込む
- ページフォールト
- 主記憶上に物理ページを確保し、補助記憶装置からページを読み出し、ページテーブルを更新する
- 更に、TLBのエントリを一つ空けて、対象となる物理ページ番号を書き込む
キャッシュと仮想記憶
仮想記憶とキャッシュの両方を用いたメモリアクセス機構について整理を行う。キャッシュアクセスとTLB参照を並列化することで、語の読み書きの時間を短縮することができる。キャッシュとTLBのアクセス時間を短くし、キャッシュミス、TLBミス、ページフォールトが起こる確率を出来るだけ低く抑えることが設計上重要となる。キャッシュと仮想記憶の組み合わせには、大きく分けて以下の3種類がある。
- 直列形物理アドレスキャッシュ
- TLBで物理アドレスを生成し、そのアドレスを用いてキャッシュにアクセスする。
- メリット
- 直列形で順番に実行するため、メモリ後にアクセスするまでに時間がかかってしまい、遅い
- デメリット
- キャッシュサイズやアドレスに制約がない
- 並列形物理アドレスキャッシュ
- TLBで物理ページ番号を生成すると同時に、ページ内オフセットを用いてキャッシュにアクセスする。TLBから生成された物理ページ番号とキャッシュのタグを照合し、等しければキャッシュラインが求めるものとなる。
- メリット
- TLBとキャッシュに並列アクセスするので、早い
- デメリット
- キャッシュインデックスが仮想アドレスの”ページ内オフセット”の大きさで決まってしまうため、キャッシュサイズが限定されてしまう。
- 仮想アドレスキャッシュ
- 仮想アドレスを用いてキャッシュにアクセスする。上記の2つと異なり、物理アドレスに変換されていない仮想アドレスを用いて、キャッシュにアクセスするので、TLBのクリティカル・パスが外れ、キャッシュのレイテンシが減少する。
- ただし、キャッシュミスが発生した場合、主記憶からデータを読み出してキャッシュに入れるためには、仮想アドレスを物理アドレスに変換しておく必要がある。
- 仮想アドレスを用いてキャッシュにアクセスした場合、複数のプロセスで共有されているページがあると、各プログラムでの共有ページの仮想アドレスが異なっているためにエイリアスが発生する可能性がある。エイリアスは、同一オブジェクトが複数の名前（アドレス）を持つ時に発生する。この時、一方のプログラムがデータを書き込んだにも関わらず、他方のプログラムはそのデータが変更されたことがわからない、という事態が発生してしまう。そのため、エイリアスが発生しないような制約を追加する必要がある。
- メリット
- TLBとキャッシュに並列アクセスするので、早い
- 仮想アドレスそのもので、キャッシュにアクセスするので容量制限もない
- デメリット
- エイリアスの問題が発生する
まとめ
仮想メモリに関して、知識を整理をすることができた。
キャッシュと仮想メモリの違い
- キャッシュ
- CPUのデータアクセス速度を高速化する、高速小容量の記憶装置
- 直近で使用されたデータのコピーを格納する
- メモリ管理は、ハードウェアによって行われる
- 仮想メモリ
- メインメモリの容量を拡張するテクニック（手法）
- メインメモリよりも大きいプログラムの実行を可能とする
- メモリ管理は、OSによって行われる
