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