スポンサードリンク
こんにちは、ももやまです。
今回は仮想記憶やページングについて、具体的には
- 仮想記憶とはどんなものなのか
- 仮想アドレス空間（仮想メモリの空間）と物理アドレス空間（物理メモリの空間）の違い
- 4GBの壁の正体
- ページング・ページフォルトについて
についてをまとめています。ぜひご覧ください！
前回の計算機システム（Part18）の記事はこちら！
プロセスの3状態（実行状態・実行可能状態・待ち状態）や、スケジューリングアルゴリズムについての記事なのでもしよかったらご覧ください！
スポンサードリンク
１．仮想記憶（仮想メモリ）とは
コンピュータ上に入っている物理上のメモリだけでは、容量が足りないことがあります。
そこで、物理上のメモリ(RAM)だけでなく、ハードディスクなどの補助記憶装置を組み合わせることで、見かけ上でより多くのメモリ領域を使えるようにしたのが仮想記憶となります。
仮想記憶を用いるもう1つのメリットとして、メモリ領域の保護があります。
プログラムが直接物理上のメモリにアクセスすると、他のプロセスで使うメモリ領域を勝手に書き換えてしまうなどの予期せぬ動作をする可能性があります。
そこで、直接物理上のメモリにアクセスするのではなく、仮想記憶を用いてアクセスを行うことで、OS側がメモリを管理するため、メモリの領域を保護することができます。
そのため、現在のプログラムのほとんどは直接物理上のメモリにアクセスするのではなく、仮想記憶を用いてアクセスを行っています。
スポンサードリンク
２．仮想アドレス空間・物理アドレス空間の違い
(1) 仮想アドレス空間
仮想アドレスが振られたアドレス空間を仮想アドレス空間と呼びます。
プログラムに割り当てられるアドレス空間です。
仮想アドレス空間の容量
また、仮想アドレス空間の容量は、物理メモリの容量とは関係なく、常に一定です。
パソコンを買う際などに32bit版OS, 64bit版OSという単語を聞いたことがある人は結構いるかと思います。
OSのbit数は、仮想アドレス空間の大きさを表しているのです！
例えば32bitOSであれば仮想アドレス空間の大きさは4GB、最近のパソコンで主流の64bitOS仮想アドレス空間の大きさは、なんと16EB（約16,000PB、1,600万TB）になります！
仮想アドレス空間の容量計算方法
32bitOSの仮想アドレス空間がなぜ4GBになるのかを説明していきます。
32bitの bit は2進数における桁数を表します。
32bit（つまり32桁）のときに表現できる数の総数を考えてみましょう。
2進数において1つの桁で表現できる数は、0, 1の2通りですね。
今回は32桁あるので、2を32回掛けた数、つまり \( 2^{32} \) 通りの場所を管理することができますね。
メモリは、データの場所を1バイト単位で管理しています。
つまり、データの場所1箇所につき、1バイトの領域を使っていると言えます。
今回は \( 2^{32} \) 通りのデータの場所を管理できるので、32bitOSの場合、 \( 2^{32} \) バイトのメモリ場所を管理できますね。
つまり、仮想アドレス空間の大きさは \( 2^{32} \) バイト、単位を変えると 4GB となります。
よって、32bit版のOSでの仮想アドレス空間の大きさは4GBであることがわかりますね。
(2) 物理アドレス空間
物理アドレスが振られたアドレス空間を物理アドレス空間と呼びます。
メインメモリに割り振られているアドレス空間だと思ってください。
コンピュータに入っているメインメモリ（RAM）の量がそのまま物理アドレス空間の容量となります。
ただし、どんなに物理アドレス空間（つまり物理メモリ）の容量が大きくてもOSは仮想アドレス空間（つまり仮想メモリ）の容量以上を使うことができません*1。
余談：32bitOSにおける4GBの壁
物理メモリ容量がどんなに大きくても仮想メモリ容量以上に使うことはできません。
また、32bitOSの仮想メモリの大きさは4GBでしたね。
そのため、32bitOSには4GBを超えるメモリを積んでも4GB以上の領域は無駄になります。これを「4GBの壁」と呼びます。
4GBと言っても、物理メモリの一部（4GBの場合は1GB程度）は、他のデバイスによって独占されてしまうので実際に32bitOSが使えるのは3GB程度です。
そのため、32bitのOSに4GBを超えるメモリを搭載しても、3GBまでしか認識せず意味をなしません。
これが「4GBの壁」の正体です！
ちなみに64bitOSの場合、最大で1,600万TBの仮想記憶があるため、8GB以上の物理メモリを搭載してもちゃんと認識します。
ですが1,600万TBの物理メモリは理論上のお話で、実際にはハードウェア上による制限などがかかるので、1,600万TBまでの物理メモリが認識できるわけではありません。
皆さんがよく使っているWindows10 Homeの64bit版であれば128GBまでの物理メモリ、Windows10 Proの64bit版であれば512GBの物理メモリが搭載できます。
スポンサードリンク
３．ページング
(1) ページングとは
仮想記憶の実装方法の1つにページングと呼ばれるものがあります。
ページングでは、仮想アドレス空間、物理アドレス空間をページという単位に分割し、仮想アドレス空間と物理アドレス空間を対応付けて管理します。
また、仮想アドレス空間、物理アドレス空間の対応付けにはページテーブルという表が用いられます。
ページテーブルには、
- それぞれの仮想ページ番号にあるデータが物理アドレス空間（メインメモリ）に存在するかどうか
（存在ビットで管理。あれば1、なければ0を表している） - 存在するのであれば、どの物理アドレス番号にあるか
などの情報が入っており、主に上の2つの情報から仮想アドレス空間と物理アドレス空間を対応付けます。
例えば仮想アドレス空間上のページ番号1にある「A」が物理アドレス空間ではどこにあるのかを探してみましょう。
まず、ページ番号1のページテーブルをみてみると、存在ビットが1になっていますね。
つまり、物理アドレス空間にデータ「A」が存在していることがわかりますね。
次に、ページテーブルにかかれている対応付けを確認すると、2と書かれていますね。
つまり、物理アドレス空間のページ番号2に「A」があることがわかりますね。
(2) アドレス変換（仮想アドレス→物理アドレス）
アドレスは、
- ページ番号
- ページ内アドレス（変位）
の2つで構成されており、アドレスの上位部分がページ番号、下位部分がページ内のアドレスを表します。
ページングにより仮想アドレス空間から物理アドレス空間に変換する際に、仮想ページ番号はハードウェア内にあるMMU(Memory Management Unit)により物理ページ番号に変換されますが、ページ内変位は変化しません。
ここで1問例題をはさみましょう。
例題
仮想アドレスが32ビット（つまり32ビットOS）で、ページサイズが4KB、ページテーブルのエントリが4バイトの仮想記憶を考える。
このとき、
(1) 仮想空間の大きさ
(2) 仮想ページ番号、ページ内変異のビット数
(3) 仮想アドレスが 0x0334dead のときの仮想ページ番号・ページ内変位の値
(4) ページテーブルの大きさ
を求めなさい。
解答
(1) 4GB
(2) 仮想ページ番号：20ビット ページ内変異：12ビット
(3) 仮想ページ番号：0x0334d ページ内変異：0xead
(4) 4MB
(1)
仮想アドレスが32bitなので、全部で \( 2^{32} \) 通りの場所を表せる。
1つの場所あたり1バイトの領域が必要なので、全部で \( 2^{32} \) バイト、適切な単位に直すと 4GB となる。
(2)
ページ内変異とは、ページ内にあるアドレスのことである。
問題文より、ページサイズが4KBなので、ページ内にあるアドレスは全部で4KB、単位をバイトに直すと \( 2^{12} \) バイトとなる。
つまり、\( 2^{12} \) バイトあればページ内のアドレスを全部表現できるので、ページ内変位は12bitとなる。
また、仮想ページ番号は32ビットからページ内変位で使う12ビットを引いた残りの20ビット分となる。
（つまり仮想ページ番号は \( 2^{20} \) 通り存在する。よって仮想アドレス空間に存在するページは \( 2^{20} \) ページとなる。）
(3)
上位となる仮想ページ番号が20ビット、下位となるページ内変位が12ビットである。
16進数だと、上位5桁が仮想ページ番号、下位3桁がページ内変異となるので、
仮想ページ番号：0x0334d
ページ内変異：0xead
が答え。
(4)
ページテーブルのエントリの大きさは問題文より4バイトである。
それぞれのページごとに4バイトのエントリが必要なので、（ページ数）×（エントリの大きさ）でページサイズを求めることができる。
(2)より、仮想アドレス空間のページ数は \( 2^{20} \) ページあるので、ページテーブルの大きさは、\[
2^{20} \times 4 = 2^{22}
\]となり、ページテーブルの大きさは \( 2^{22} \) バイト、適切な単位に揃えると 4MB となる。
★参考★
(2)の誘導がない場合はページの総数を、仮想空間の大きさ（4GB）、1ページあたりのページサイズ（4KB）から、\[
2^{32} \div 2^{12} = 2^{20}
\]と求めたほうが早い。
４．ページフォルト
(1) ページフォルトとは
基本的に仮想アドレス空間に比べ、物理アドレス空間（メインメモリ）は少ないです。
そのため、仮想アドレス空間上にはデータがあっても、物理アドレス空間上にはデータがないことがあります。
このようなデータ、つまりメインメモリ（つまり物理アドレス空間）に存在しない仮想アドレス空間上のページにアドレスしようとすることをページフォルトとよび、MMU(Memory Management Unit)により検知されます。
(2) ページフォルト発生時の流れ
では、実際に1つ例を挙げながらページフォルトが発生したときの流れを説明していきましょう。
下の図の仮想ページ番号7のデータ「G」をアクセスすることを考えます。
Step1：ページフォルト発生
仮想ページ番号7のページテーブルの存在ビットを確認すると、0になっていますね。
なので、物理アドレス空間にデータがないことがわかります。
よってMMUがページフォルトを検知し、割込みが発生します。
Step2：いらなさそうなデータを補助記憶へ避難（ページアウト）
ページフォルトが発生すると、まず物理アドレス空間のいらなさそうなデータを補助記憶装置に書き込みます。これをページインと呼びます。
今回は物理ページ番号1にある「C」を補助記憶装置に書き込みます。
なお、メインメモリに空いている枠があれば、このステップ（ページアウト）は行われません。
Step3：今必要なデータをメインメモリへ（ページイン）
つぎにアクセスしたいデータを、先程書き込んだデータがあるページへ読み込みます。
今回は「G」にアクセスしたいので、「G」を補助記憶から先程データを退避させたページ番号1に読み込みます。
これをページアウトと呼びます。
（もともとあったデータ「C」は上書きされてなくなります。）
なお、メインメモリに空いている枠があれば、空いている枠にページが読み込まれます。
Step4：ぺージテーブルに登録
物理アドレス空間のデータが書き換わったのでページテーブル（対応付け）も当然変化します。
今回は物理ページ1のデータが「C」から「G」に変化したので、「C」の存在ビットは1→0となり、「G」の存在ビットは0→1となり、Gのデータの場所である「ページ番号1」もページテーブルに記録されます。
以上がページフォルト発生時の処理内容です。
ページテーブルの存在ビットが0のときにページフォルトによる割込みが発生し、1～4の流れで処理される。
- MMUによるページフォルト割込み
- 空きページ枠がなければ、いらなさそうなデータを決めてから補助記憶装置に退避
（ページアウト） - 空きページがある場合は、空きページに必要なデータを読み込む
空きページがない場合は、退避したページに必要なデータを読み込む
（ページイン） - ページテーブルの書き換え
（存在ビット・物理ページ番号の変更）
ページフォルト時の流れ
(3) ページフォルトと速度低下
ページフォルトが発生すると、メインメモリに比べてアクセスが遅い補助記憶装置のページ読み込みを待つ必要がありますよね。
そのため、ページフォルトが発生するとシステムのスループット（実行効率）が低下します。
また、ページフォルトは仮想記憶に対して主記憶が少なければ少なくなるほど発生します。
主記憶が仮想記憶に対して少なすぎるとページフォルトが多発し、システムのスループットが極端に低下します。
この現象のことをスラッシングと呼びます。
５．ページ置き換えアルゴリズム（発展）
先程のページフォルト発生時の処理で、「いらなさそうなデータ」を補助記憶装置に避難させると説明しましたね。
この「いらなさそうなデータ」を選ぶアルゴリズム、つまりページ置き換えアルゴリズムにはいくつか種類があります。
例えば、
- FIFOアルゴリズム
（最も古くページイン（読み込み）したページを置き換える） - LRUアルゴリズム
（過去最も参照されていないページを置き換える）
があります。
ページ置き換えアルゴリズムについては、こちらの記事で詳しく説明しているので、もしよかったらご覧ください！
（基本情報や応用情報など出てくるページ置き換え問題の解き方などもこちらで説明しています！）
６．練習問題
では、何問か基本情報や応用情報の過去問で練習をしてみましょう！
練習1
仮想記憶を用いたコンピュータでのアプリケーション利用に関する記述のうち，適切なものはどれか。
[基本情報技術者平成22年春期 午前問20]ア：アプリケーションには、仮想記憶を利用するためのモジュールを組み込んでおく必要がある。
イ：仮想記憶は、磁気ディスクにインストールされたアプリケーションだけが利用できる。
ウ：仮想記憶を使用していても主記憶が少ないと、アプリケーション利用時にページフォールトが多発してシステムのスループットは低下する。
エ：仮想記憶を利用するためには、個々のアプリケーションで仮想記憶を使用するという設定が必要である。
練習2
仮想記憶方式の一つに、仮想アドレス空間を固定長の領域に分割して管理するものがある。この固定長の領域を示す用語はどれか。
[基本情報技術者平成16年春期 午前問30]ア：セクタ
イ：セグメント
ウ：フレーム
エ：ページ
練習3
ページング方式の仮想記憶において、ページフォールトの発生回数を増加させる要因はどれか。
[基本情報技術者平成29年秋期 午前問20]ア：主記憶に存在しないページへのアクセスが増加すること
イ：主記憶に存在するページへのアクセスが増加すること
ウ：主記憶のページのうち、更新されたページの比率が高くなること
エ：長時間アクセスしなかった主記憶のページをアクセスすること
練習4
ページング方式の仮想記憶において、あるプロセスが仮想アドレス空間全体に対応したページテーブルを持つ場合、ページテーブルに必要な領域の大きさを \( 2^x \) バイトで表すとすると、xを表す式はどれか。
ここで、仮想アドレス空間の大きさは \( 2^L \) バイト、ページサイズは \( 2^N \) バイト、ページテーブルの各エントリの大きさは \( 2^E \) バイトとし、その他の情報については考慮しないものとする。
[ソフトウェア開発技術者平成20年春期 午前問22]ア：L + N + E
イ：L + N - E
ウ：L - N + E
エ：L - N - E
練習5（応用問題）
仮想記憶方式に関する次の記述を読んで、設問1～3に答えなさい。
[基本情報技術者過去問題 平成31年春期 午後問2]
仮想記憶方式は、OSが提供する論理的な記憶領域(以下、仮想記憶という)上のアドレスと物理的な主記憶上のアドレスを対応付けて管理する方式である。仮想記憶方式では、補助記憶装置を仮想記憶の実装媒体として用いることによって、プログラムが主記憶の容量を超える大きさであっても、これを仮想記憶上のデータとして格納し、実行することができる。仮想記憶上のアドレス空間を仮想アドレス空間、主記憶上のアドレス空間を物理アドレス空間と呼び、それぞれの空間における記憶場所は仮想アドレス、物理アドレスで指定する。
仮想記憶方式の実現方法の一つにページング方式がある。この方式では、仮想アドレス空間と物理アドレス空間をそれぞれ仮想ページ、物理ページと呼ぶ固定長の領域に分割し、管理する。ページング方式では、プログラムの実行過程で、実行に必要な仮想ページのデータが物理アドレス空間に存在していないときは、そのデータが格納されている仮想ページからデータを物理ページに読み込んで利用する。
ページング方式のページ管理方法の例を次の1～3に示す。
- 仮想アドレス空間及び物理アドレス空間の各ページには、1から順に番号を付け、それぞれを仮想ページ番号、物理ページ番号と呼ぶ。
- 仮想ページと物理ページの対応は、ページテーブルで管理する。ページテーブルの各要素は仮想ページと1対1に対応付けられており、要素の個数は仮想ページの個数と同じである。
- ページテーブルには、仮想ページのデータが物理アドレス空間に存在しているかどうかを示すビット(以下、存在ビットという)と、存在している場合に対応する物理ページ番号を登録する領域がある。存在ビットは、当該仮想ページのデータが物理アドレス空間に存在している場合は1、存在していない場合は0である。
仮想アドレス空間の仮想ページと物理アドレス空間の物理ページとの対応例を、図1に示す。ここで、図1中のA～Hは、仮想ページ及び物理ページに格納されているデータを示す。
図1 仮想アドレス空間の仮想ページと物理アドレス空間の物理ページとの対応例
設問1
図1中の [ ] に入れる正しい答えを、解答群の中から選べ。ここで、a1～a4に入れる答えは、aに関する解答群の中から組合せとして正しいものを選ぶものとする。
設問2
次の記述中の [ ] に入れる適切な答えを、解答群の中から選べ。ここで、b1とb2、c1とc2に入れる答えは、それぞれb、cに関する解答群の中から組合せとして適切なものを選ぶものとする。
ページング方式では、プログラムの実行過程で、実行に必要なデータが物理アドレス空間に存在していないときには、ページフォールトという割込みが発生する。ページフォールトが発生すると、仮想ページに格納されているデータを物理ページに読み込む処理(以下、ページフォールト割込み処理という)を行う。
〔ページフォールト割込み処理〕
- 物理ページのうち、仮想ページと対応付けられていない物理ページ(以下、空きページという)を一つ探す。
- 空きページがなかった場合、空きページにする [ b1 ] ページを一つ選び、その選んだページに格納されているデータを [ b2 ] 。その後、対応するページテーブルの要素の存在ビットを0にする。これによって空きページを確保する。
- 空きページがあった場合、又はなかった場合では2の処理後に、その空きページにプログラムの実行に必要な [ c1 ] ページに格納されているデータを [ c2 ] 。その後、対応するページテーブルの要素に物理ページ番号を登録して、その存在ビットを1にする。
設問3
次の記述中の [ ] に入れる正しい答えを、解答群の中から選べ。
ページング方式において、ページフォールトの発生回数を少なくするためには、どの物理ページを空きページにするかが重要になる。
一般的に知られているアルゴリズムであるFIFOとLRUについて、あるプログラムの実行過程で仮想ページが次の順で参照される場合を考える。ここで、プログラムの実行開始時点では、このプログラムの実行のために割り当てられた物理ページは全て空きページである。
〔仮想ページの参照順〕
4→2→1→5→4→2→3→4→2→1→5→3→5
FIFOを用いると、割り当てられた物理ページの個数が3のときは、ページフォールトの発生回数は9回である。物理ページの個数が4ならば、物理ページの個数が3のときと比べて、ページフォールトの発生回数は [ d ]。
一方、LRUを用いると、物理ページの個数が3のときは、ページフォールトの発生回数は10回である。物理ページの個数が4ならば、物理ページの個数が3のときと比べて、ページフォールトの発生回数は [ e ]。
７．練習問題の答え
解答1
解答：ウ
選択肢ごとに見ていきましょう
ア：アプリケーションには、仮想記憶を利用するためのモジュールを組み込んでおく必要がある。
→仮想記憶はアプリケーション（プログラム）側で何か組み込む必要なしに実現が可能（OS側で提供される）なので間違い。
イ：仮想記憶は、磁気ディスクにインストールされたアプリケーションだけが利用できる。
→磁気ディスクに限定なしに仮想記憶は利用可能なので間違い。
ウ：仮想記憶を使用していても主記憶が少ないと、アプリケーション利用時にページフォールトが多発してシステムのスループットは低下する。
→正しい。主記憶が少ないとページフォルトが多発し、スループットが低下する（スラッシングと呼ばれます）。
エ：仮想記憶を利用するためには、個々のアプリケーションで仮想記憶を使用するという設定が必要である。
→設定なしに仮想記憶は利用可能。よって間違い。
解答2
解答：エ
仮想アドレス空間を固定長の領域に分割して管理するときの領域は、ページと呼ばれます。
ちなみに、アの「セクタ」は磁気ディスクのデータ領域の最小単位を表します。
解答3
解答：ア
メインメモリ（主記憶）に存在しない仮想アドレス空間上のページにアドレスしようとしたときにページフォルトが発生します。
なので、主記憶に存在しないページへのアクセスが増加すればするほどページフォルトもたくさん発生します。
よって答えはアです。
解答4
仮想アドレス空間の大きさは \( 2^{L} \) バイト、1ページあたりの大きさが \( 2^N \) なので、仮想アドレス空間にあるページの合計は、\[
2^L \div 2^N = 2^{L-N}
\]で求められます。
また、それぞれのページごとに \( 2^E \) バイトのエントリが必要なので、ページサイズの合計 \( 2^x \) は\[
2^x = 2^{L-N} \times 2^E
\]で求められます。
よって、\( x = L - N + E \) となり、ウが答えとなります。
解答5
★解答★
設問１ (a) ウ
設問２ (b) エ (c) ア
設問３ (b) ア (c) エ
★解説★
設問1
ページテーブルは、それぞれの仮想アドレス番号に格納されているデータが
- 物理アドレス空間（メインメモリ）に登録されているか [存在ビット]
- データがどの物理ページ番号にあるか
を表しています。
仮想ページNo.1のデータA → 物理ページNo.2に存在するので [ a1 ] は2
仮想ページNo.2のデータB → 物理ページNo.5に存在するので [ a2 ] は5
仮想ページNo.3のデータC → 物理ページNo.7に存在するので [ a3 ] は7
仮想ページNo.4のデータD → 物理ページNo.3に存在するので [ a4 ] は3
なので、組み合わせとして正しいのはウとなります。
設問2
物理ページが空いていない場合は、物理ページからデータを1つ選び、いったん補助記憶装置に退避させます。
（待避させたいデータは必ず物理ページにありますよね。）
そして、仮想ページにあるデータを、補助記憶装置から先程退避させたページに読み込みます。
（今からメインメモリ、つまり物理ページに読み込むデータが物理ページにあるわけないですよね。なので消去法で仮想ページと選ぶのもありです。）
よって答えは(d)がエ、(e)がアなります。
「データを補助記憶装置に退避 → 退避させたページにデータ読み込み」 の順番を間違えないようにしましょう。
設問3
FIFOは、一最も古く読み込んだページを置き換えるアルゴリズムでしたね。
ページ枠が4のときのページ枠の変化、ページフォルトの発生場所を表にすると、下のようになります。
よってページフォルトは10回となるので、3枠のとき（ページフォルト9回）よりも1回ページフォルトが増え、答えはアとなります。
LRUは、過去最も参照されていないページを置き換えるアルゴリズムでしたね。
先程と同じようにページ枠が4のときのページ枠の変化、ページフォルトの発生場所を表にすると、下のようになります。
よってページフォルトは8回となるので、3枠のとき（ページフォルト10回）よりも2回ページフォルトが減り、答えはエとなります。
８．さいごに
今回は仮想記憶、およびページングについてまとめていきました。
次回からはアセンブリ言語についてまとめていきたいと思います。
ではまた次回、さらば！
*1:理由としては、仮想アドレス空間と物理アドレス空間はページテーブル（後ほど説明します）で1対1対応させるので、仮想アドレス空間の容量以上に物理アドレス空間を対応させることができないからです。
関連広告・スポンサードリンク
