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