仮想記憶

前回 ： 主記憶管理
主記憶管理の目的 ： 主記憶の効率的利用
（固定区画方式・可変区画方式）
しかし，いかに効率よく使ったとしても，実行可能なプログラムサイズや同時に
実行できるプロセス数は実装されている主記憶の大きさ（容量）に制限される。
① 256kBの主記憶上で，128kBのプロセスを同時に4個実行させることは
できないか ?
② 256kBの主記憶上で，512kBのプロセスを実行させることはできないか ?
① → (1) スワッピング
方策 ：
② → (2) オーバレイ
① ② → (3) 仮想記憶
スワッピング（swapping）
z 主記憶の大きさには限りがあり，実行したいすべてのプログ
ラムを主記憶にロードできるとは限らない
¾ プログラム（プロセス）が待ち状態にあるときはディスクにそのプログ
ラムを退避する（スワップアウト）
¾ ディスクに退避されている実行可能なプログラムを主記憶にロードす
る（スワップイン）
ディスク
主記憶
スワップアウト
プログラムA
プログラムA
プログラムB
プログラムB
スワップイン
ディスクは主記憶に比べ低速であるため，頻繁にスワッピング
が発生するとプログラムの実行効率の低下を起こす
1
オーバレイ（overlay；重ね配置）
z プログラムの実行ではプログラム全体を主記憶にロードする必要はない
→ これから実行しようとする部分だけをロードすればよい
例 ： main 関数が，関数A→関数B→関数C→関数D→関数C→関数B
の順に処理を行う場合
main関数
ディスク
関数A
プログラム
関数B
関数C
関数D
主記憶
main関数
関数A
main関数
main関数
main関数
関数A
関数C
関数C
関数B
関数B
関数B
関数D
関数D
③ Bを退避し
Dをロード
④ Cを退避し
Aをロード
関数B
main関数
関数C
① main，A,B
をロード
関数D
② Aを退避し
Cをロード
オーバレイ（overlay；重ね配置）
z ユーザがプログラムを論理的なプログラム単位（例えば
関数やその集まり）に分割する
z 同時に実行されないプログラム単位を，必要なときに主記
憶上の同じ位置に読み込んで使用する
z 手順はすべてユーザが指定する
－プログラムの動作（構造）の正確な知識を要する
主記憶
main関数
関数A
main関数
関数B
関数C
関数D
関数A,Bで
共用する
関数C,D4で
共用する
2
仮想記憶：virtual memory （1）
補助記憶装置（ディスク）を使って，物理的なメモリ容量に
制限されない主記憶空間（メモリ空間）を提供する仕組み
z 仮想記憶の考え方と原理
z セグメンテーションとページング
主記憶
プログラムC
プログラムB
（物理メモリ）
プログラムA
動的アドレス変換
プログラムE
プログラムD
プログラムA
の論理アドレ
ス空間
ディスク
仮想記憶の考え方
スワッピング ： 頻繁なスワッピングは実行効率の低下を招く
オーバレイ ： オーバレイの制御はユーザの負担を重くする
解決策は？
‹ プログラム実行の時間的局面は，多くの場合プログラムの特定部分が実行されている 。
（＝ 参照の局所性）
‹ ならば，当面実行に必要な部分だけを主記憶（物理メモリ）に入れておけばよく，必要
ない部分はディスクに置いておき，必要になったときにメモリにもってくればよい。
„ 主記憶とディスクを用いて，実際の主記憶容量よりも大きな容量の
「仮想的な主記憶（メモリ）」を提供する。
ディスクの役割り ： 補助記憶（ファイルの格納）
： 仮想メモリの提供（スワップファイル/ページングファイル）
3
仮想記憶の動作概念（1） ： ページング方式
プロセッサ
主記憶
仮想記憶の動作概念（2） ： ページング方式
z 最初，プログラムはディスクに
格納されている。（主記憶は空）
プロセッサ
z プロセッサは主記憶にプログ
ラムがあると思っている。（実際
はディスクにある）
（実記憶）
z プログラムの実行が開始されて，
プロセッサが主記憶をアクセスする。
主記憶
（実記憶）
ページ（4KB～16KB程度）
ディスク
（仮想記憶）
P0 P3 P5
ディスク
P1 P4 P6
（仮想記憶）
P2
ディスク
仮想記憶の動作概念（3） ： ページング方式
プロセッサ
主記憶
（実記憶）
仮想記憶の動作概念（4） ： ページング方式
プロセッサ
z ところが，最初はプログラム
は主記憶に入っていないので，
ページフォルトが発生して，実
行に必要なページが主記憶に
もってこられる。
z 「参照の局所性」により，
しばらくはこの状態でプログラム
が実行される。
主記憶
（実記憶）
ページ単位の転送
ページフォルト：
ディスク
（仮想記憶）
ディスク
（仮想記憶）
仮想記憶において，実行に必要
なプログラム/データが主記憶に
存在しないときに発生する割込み
仮想記憶の動作概念（5） ： ページング方式
プロセッサ
仮想記憶の動作概念（6） ： ページング方式
プロセッサ
z やがて主記憶にない部分■を
プロセッサがアクセスしようとする
と，ページフォールトが発生する。
主記憶
主記憶
（実記憶）
（実記憶）
z ■を含むページが主記憶に
転送される。
ページ単位の転送
ディスク
ディスク
（仮想記憶）
（仮想記憶）
4
仮想記憶の動作概念（7） ： ページング方式
プロセッサ
仮想記憶の動作概念（8） ： ページング方式
プロセッサ
z やがて，主記憶は読み出さ
れたページで埋まってしまう。
主記憶
主記憶
（実記憶）
（実記憶）
ディスク
ディスク
（仮想記憶）
（仮想記憶）
仮想記憶の動作概念（9） ： ページング方式
プロセッサ
主記憶
（実記憶）
プロセッサ
z 新たにページを読み出す
場合には，現在主記憶に存
在するページの中から追出
すページを選び，そのペー
ジを追い出して空いた場所
にページをもってくる。
主記憶
（実記憶）
ディスク
（仮想記憶）
仮想記憶の動作概念（11） ： ページング方式
プロセッサ
主記憶
（実記憶）
ディスク
①このページが必要になったら，
現在主記憶に入っているペー
ジのどれかを追い出して，空き
領域を確保する。
仮想記憶の動作概念（10） ： ページング方式
②このページが追出されるページ
として選ばれたら，
ディスク
（仮想記憶）
z 新たにページを読み出す場
合には，現在主記憶に存在す
るページの中から追出すペー
ジを選び，そのページを追い
出して空いた場所にページを
もってくる。
z 新たにページを読み出す
場合には，現在主記憶に存
在するページの中から追出
すページを選び，そのペー
ジを追い出して空いた場所
にページをもってくる。
④この場所にもってくる
（仮想記憶）
5
z 新たにページを読み出す
場合には，現在主記憶に存
在するページの中から追出
すページを選び，そのペー
ジを追い出して空いた場所
にページをもってくる。
③このページを追い出して（ディス
クに退避して），空き領域を作り，
仮想記憶
ディスクを介在して，実際の主記憶よりも大きな記憶空間を
プログラム（ユーザ）に提供する
仮想記憶空間（論理アドレス）
ディスク
プログラムが想定する
仮想的な記憶装置
ディスクの一部領域を
仮想記憶空間のために
使う（スワップ領域，
ページファイル領域）
動的アドレス変換
主記憶空間
（物理アドレス）
プロセッサ
プロセッサから
アクセス可能な
主記憶
（物理記憶）
仮想記憶
ディスクを介在して，実際の主記憶よりも大きな記憶空間を
プログラム（ユーザ）に提供する
仮想記憶空間（論理アドレス）
ディスク
領域 0
領域 1
領域 2
領域 3
領域 4
プログラムが想定する
仮想的な記憶装置
領域 5
領域 6
領域 7
領域 8
領域 9
ディスクの一部領域を
仮想記憶空間のために
使う（スワップ領域，
ページファイル領域）
6
領域 6
領域 4
領域 9
領域 2
プロセッサから
アクセス可能な
主記憶
（物理記憶）
動的アドレス変換
主記憶空間
（物理アドレス）
プロセッサ
仮想記憶の考え方
z プログラムを一定のブロックサイズに分割し，ブロック単位で
主記憶とディスク領域に割り当てる
z プログラム（ユーザ）は「仮想的な記憶装置」が提供する記憶
空間をアクセスすると考える
z プログラムの実体は，ディスクに置かれ，プログラムの実行時
に「実行に必要な部分」だけが主記憶にもってこられる（ロードさ
れる）
z 「仮想的な記憶装置」のアドレス（仮想アドレス）はアドレス変換
によって，実行時に主記憶のアドレス（物理アドレス）に変換さ
れる（動的アドレス変換）
¾ ユーザ（アプリケーション）/ プロセッサが想定する仮想的（論理的）なアドレス
＝仮想アドレス（virtual address） / 論理アドレス（logical address）
¾ 実際に命令やデータが存在する主記憶のアドレス
＝物理アドレス（physical address）
仮想メモリの方式
(1) セグメンテーション方式
z ユーザがプログラムの内部構造に基づいて分割
z 分割したものをセグメントという
z セグメント単位でアドレス変換と主記憶への割当てを行う
z 領域サイズは可変
セグメンテーション
main関数
関数A
モジュールごとのサイズに応
じて記憶領域を割り当てる
関数B
関数C
関数D
7
(1) セグメンテーション方式
セグメント番号
主記憶
物理アドレス
0
セグメントテーブル
0
main関数
1
関数A
2
関数B
3
関数C
4
関数D
0
1
1
0
2
0
3
1
3000
4
1
2000
1000
1000
main関数
main関数
2000
関数D
関数A
3000
関数C
関数B
関数C
仮想アドレス空間
物理アドレス空間
関数D
存在ビット
セグメントベース
（各セグメントの主記憶上で
の開始アドレス）
ディスク
セグメンテーション方式におけるアドレス変換
仮想アドレス（4250番地）
プログラム
セグメント番号
（仮想アドレス）
0
1
2
3
4
セグメント内アドレス
4
250
主記憶
main関数
（物理アドレス）
セグメントテーブル
関数A
0
1
関数B
2
3
4
関数C
関数D
1
0
0
1000
1
1
3000
2000
0000
1000
4250番地
2250
存在ビット
main関数
+
2000
2250
関数D
物理アドレス
3000
関数C
8
仮想メモリの方式
(2) ページング方式
z プログラム内部の論理構造とは無関係に，自動的に
アドレス空間を分割する
z 分割した空間をページという
z ページサイズは固定
セグメンテーション方式
ページング方式
main関数
モジュールごとの
サイズに応じて
記憶領域を割り
当てる
関数A
関数B
固定したサイズ
の記憶領域を割
り当てる
関数C
関数D
ページング方式におけるアドレス変換
ページ番号
仮想アドレス
ページテーブル
0000
P0
1000
P1
‥‥
0 1
1 0
2000
1
1000
2
3
4
5
6
主記憶
0000
P15
1000
0
P0 P1 P2
P2
0
1
P3 P4 P5
P6
2000
0
P0
3000
‥‥
E000
P14
物理アドレス
E 0
F 1
ディスク
3000
P6
0000
4kbyte
F000
P15
物理アドレス
（16kbyte，1ページ4kbyteとした場合）
存在ビット
ページベース
（各ページの主記憶上での開始アドレス）
仮想アドレス
（64kbyte，1ページ4kbyteとした場合）
9
16bit
仮想アドレス
ページ番号(4bit)
仮想アドレス
ページテーブル
ページ内アドレス(12bit)
物理アドレス
0000
主記憶
0000
P0
0 1
1 0
2000
1
1000
2
3
4
5
6
1000
P1
‥‥
P15
1000
0
P0 P1 P2
P2
P3 P4 P5
0
1
P6
2000
0
P0
3000
‥‥
E000
E 0
F 1
P14
ディスク
3000
P6
0000
F000
物理アドレス空間
P15
仮想アドレス 21A8番地 → 物理アドレス 11A8番地
仮想アドレス空間
仮想アドレス 653A番地 → 物理アドレス 353A番地
仮想アドレスと物理アドレスの対応
z 仮想アドレス空間，物理アドレス空間ともにページとよばれる固定区画
に分割する。物理ページをページフレーム（ページ枠）と呼ぶ。
（ページの大きさは4kbyte程度が一般的）
z 仮想ページ番号 … 仮想アドレス空間内のページに付けられる番号
z 物理ページ番号 … 物理アドレス空間内のページに付けられる番号
z 仮想アドレス＝仮想ページ番号（p)＋ページ内アドレス（a)
16bit （64kbyte）
例えば
仮想アドレス
仮想ページ番号
(p)
ページ内アドレス
(a)
4bit
12bit
ページ番号を4bitとすると，
全ページ数は24=16ページ
ページ内アドレスを12bitとすると，
1ページの大きさは4kbyte
（実際には仮想ページ番号は20bit 程度のbit数をもつ⇒220=100万ページ）
10
仮想アドレスと物理アドレスの対応
15
仮想アドレス
14
13 12 11 10
9
8
ページテーブル
7
6
5
4
3
2
1
0
3
2
1
0
ページ内アドレス
仮想ページ番号
変換
13 12 11 10
物理アドレス
9
8
7
6
5
4
ページ内アドレス
物理ページ番号
P0
P15
P1
P2
P2
P0
P3
P6
P4
物理アドレス空間
（主記憶）
P5
P6
‥‥
P14
P15
仮想アドレス空間
ページング方式における主記憶アクセス
z プロセッサの生成する仮想アドレスは物理アドレスに変換され，
主記憶にアクセスする
z 主記憶に存在する場合（ヒット：hit） → そのままアクセス
アクセス対象が
z 主記憶に存在しない場合（ページフォルト：page fault）
→ アクセス対象を含むページをディスクから主記憶にもってくる
‹ 主記憶上に空き領域がある場合
→ 空き領域にもってくる
‹ 主記憶上に空き領域がない場合
→ ① 当面使いそうにない物理ページを選択
（ページ置換えアルゴリズム：次回）
② 選択されたページ内容をディスクに退避
（ページアウト
）
③ アクセス対象を含むページをディスク
から主記憶上にもってくる
（ページイン
）
④ 主記憶上の物理ページをアクセス
11
割込み処理
ルーチン
OS
ページテーブル
0 1
② ページ
フォルト
割込み
① ページ
参照
⑤ ページテーブル
の再設定
a
ページ
LD R0，a
⑥命令再開
ディスク
③ 空きページ枠
の確保
a番地をアク
セスする命令
空き
ページ枠
a番地の内容が
主記憶にない
④ページ読込み
ページフォールトの処理手順
主記憶
ページフォルトの処理手順
ページフォルト発生（割込み）
空きページの検索
ページをディスク
から読み出す
あり
空きページは？
空きページ枠に読み込む
なし
置換え対象の
ページを追い出す
ページテーブルの存在
ビットを 0 から１に書き換える
空きページ枠を確保
割込み処理から復帰
処理の再開
12
演習問題 6
1. 仮想記憶方式で用いられる記憶管理の手法を二つ選べ。
ア オーバレイ
イ スプーリング
ウ セグメンテーション
エ 動的リンキング
オ ページング
2. (1) 仮想記憶の方式の一つに，プログラムの手続きやデータなど，論理的なひとまとまりを領域の単
位として，仮想アドレス空間を分割して管理するものがある。この可変長の領域を示す用語を何
というか。
(2) 仮想記憶方式の一つに，仮想アドレス空間を固定長の領域に分割して管理するものがある。こ
の固定長の領域を示す用語を何というか。
3. 仮想記憶におけるページング方式に関する記述はどれか。
ア 実記憶空間と仮想記憶空間を固定長の領域に区切り，対応づけて管理する方式
イ 主記憶装置の異なった領域で実行できるように，ブログラムを再配置する方式
ウ 主記憶を同時に並行して読み書き可能な複数の領域に分ける方式
エ ファイル記憶媒体への読み書きをするとき，複数のレコードをまとめて行う方式
オ 論理的なモジュールに分割されたプログラムをモジュール単位で主記憶のページに配
置する方式
4. 仮想記憶におけるページング方式の特徴はどれか。
ア 仮想アドレス空間の管理単位である領域の大きさを，実行時に動的に変更できる。
イ 実記憶領域の利用効率が高く，領域管理が容易である。
ウ プログラムからみた論理的な単位でアクセス保護を行うことができる。
エ プログラム実行中のモジュールの取込みや共有を容易に行うことができる。
5. 動的アドレス変換の説明として，最も適切なものはどれ。
ア 仮想記憶システムにおいて，仮想アドレスから実アドレスへの変換を行うこと。
イ 実行中のプログラムを移動して新しい場所で実行できるように，プログラムのベース
アドレスを変更すること。
ウ 主記憶に対する読み書きを，キャッシュメモリで代行すること。
エ プログラムの実行途中にモジュールを追加するため，モジュール間のアドレス参照を
解決すること。
6. ページング方式の仮想記憶において，実記憶上にないページをアクセスした場合の処理と状態の順
番として，適切なものはどれか。ここで，主記憶には現在，空きページはないものとする。
ア 置換え対象ページの決定→ページアウト→ページフォルト→ページイン
イ 置換え対象ページの決定→ページイン→ページフォルト→ページアウト
ウ ページフォルト→置換え対象ページの決定→ページアウト→ページイン
エ ページフォルト→置換え対象ページの決定→ページイン→ページアウト
13
7. 下の図はページング方式の仮想記憶において，8 ページ（32kbyte）のプログラム Q が 4 ページの主
記憶上で動作している様子を示している。なお，仮想アドレス 16 ビットの内，下位 12 ビットがページ内ア
ドレスを表すものする。（アドレスは 16 進数で表わす）
仮想アドレス
0000
1000
2000
3000
4000
5000
6000
7000
プログラム Q
P0
0
1
P1
1
0
P2
2
0
P3
3
1
0000
P4
4
1
2000
P5
5
0
P6
6
0
P7
7
0
(1 ページ=4KB)
(1)
(2)
(3)
ページテーブル
1000
物理アドレス
0000
1000
2000
3000
主記憶
P3
P0
P4
（空き）
↑存在ビット
1：存在 0：無効
仮想アドレス 31A2 (16) 番地にデータ X がある。プログラムがデータ X を参照したときの
データ X の主記憶上の物理アドレスは何番地か。
仮想アドレス 62C4 (16) 番地にデータ Y がある。プログラムがデータ Y を参照する場合，
どのような現象が発生し，それに対し OS はどのような処理を行うか説明せよ。その結果，
データ Y の物理アドレスは何番地になるか。
(2)のデータアクセスの後，さらに P5 へのアクセスが発生し，P4 がページアウトされ，そ
のページフレームに P5 の内容がページインされたとする。このときのページテーブルの内
容を示せ。
14