OS

Operatig System 仮想記憶 2019-11

記憶階層 高速 & 小容量 ( 高価 ) レジスタ アクセスタイム 数ナノ秒 容量 ~1KB ランダムアクセス CPU 内 キャッシュ (SRAM) 主記憶 (DRAM) 数ナノ秒 数十ナノ秒 1MB 程度 数 GB 程度 ランダムアクセス フラッシュメモリ (SSD) 約 100 万倍 シーケンシャルアクセス 磁気ディスク (HDD) 数十ミリ秒 数百 GB 1TB 程度 光磁気ディスク (CD-R DVD-RW 等 ) 磁気テープ 0.1 秒 ~ 1GB~ 低速 & 大容量 ( 廉価 ) 2

仮想記憶 p 仮想記憶 (virtual memory) バーチャル = 実質的に同じ HDD 等の補助記憶の領域を主記憶の延長のように見せかける技術 使わないメモリ領域を HDD に待避し, 使うときに HDD から復帰する 主記憶 (DRAM) p ページング方式 メモリ空間を固定長の区画 ( ページ ) に自動的に分割して管理する p セグメンテーション方式 プログラムで予め設定した可変長の区画 ( セグメント ) で管理する 補助記憶 / ストレージ (HDD 等 ) 3

ページング p メモリのページ化 主記憶を, 固定長 ( 例 :4Kバイト) のブロック ( ページ枠 ) に分割するメモリの内容 ( データ ) も, 同サイズの ページ の集合に分割するどのページをどのページ枠に入れるか, 自由に入れ替え可能にする p アドレスの仮想化 物理アドレス : ハードウェアメモリ内の位置 ページ 枠 のアドレス 仮想アドレス : プロセスが実行中に使うアドレス ページのアドレス プロセスが動くためには, 仮想 物理 の自動アドレス変換が必要 p ページングの効果 物理メモリよりも広い仮想アドレス空間が使用できる 仮想記憶 物理的なメモリコンパクションやプロセスの再配置処理が不要になる 4

ページングの概念 ページ 0 プログラム 1 プログラム 2 プログラム 3 変数 4 ( 空き ) 5 ( 空き ) 6 ( 空き ) 7 データ 8 ( 空き ) 9 変数 10 変数 11 変数 12 ( 空き ) 仮想アドレス空間 ( プロセスから見えるアドレス ) ページ枠 ( ブロック ) 0 ページ 7 1 ページ 1 2 ページ 2 3 ページ 0 4 ページ 3 5 ページ 9 6 ページ 10 7 ページ 11 8 ページ 5 物理アドレス空間 ( 実際の RAM 内のアドレス ) 対応関係は変わるので変換表 ( ページテーブル ) が必要になる 5

多重仮想アドレス p 各プロセスに独立な仮想アドレス空間を提供 動的再配置の問題も解決する OS( カーネル ) プロセス A OS( カーネル ) OS( カーネル ) OS( カーネル ) プロセス A プロセス B プロセス C 変換 プロセス C プロセス B プロセス A の仮想アドレス空間 プロセス B の仮想アドレス空間 プロセス C の仮想アドレス空間 物理メモリ空間 ( 実際のメモリ ) 6

動的アドレス変換 p 動的アドレス変換機構 プロセスが実行時に参照する仮想アドレスを, そのつど物理アドレス ( ハードウェアメモリでのアドレス ) に変換するしくみ MMU(Memory Maagemet Uit) というハードウェアが支援 p 各アドレスの内部形式 32ビットなら, 例えば上位 20ビットと下位 12ビット (4KB 分 ) に分解 例 0x12345678 [ ページ番号 0x12345][ ページ内 0x678] 仮想アドレスの形式 : [ ページ 番号 ][ ページ内アドレス ] 物理アドレスの形式 : [ ページ枠番号 ][ ページ内アドレス ] p ページテーブル ( アドレス変換テーブル ) ページ番号 ページ 枠 番号 のアドレス変換表 多重仮想アドレスの場合は, 各プロセスがページテーブルを持つ 7

動的アドレス変換機構 ページテーブルベースレジスタ (CPU 内 ) tbl 仮想アドレス ページテーブルの位置を保持 p ページ番号 a ページ内アドレス tbl 番地 p MMU で変換 p = tbl[p] tbl[p] p ページ枠番号 ページ内アドレス ページテーブル ( 主記憶内 ) 物理アドレス p a 8

多段ページング p 広大なアドレス空間に対応 必要なときだけ 2 段目以降のテーブルを保持してメモリを節約 Wikipedia から引用 9

X86 のページング PG フラグ CR0 PAE フラグ CR4 表 3-3. ページサイズと物理アドレスサイズ PSE フラグ CR4 PS フラグ PDE PSE-36 CPUID 機能フラグ ページサイズ 物理アドレスサイズ 0 X X X X ページングは ディスエーブル 1 0 0 X X 4K バイト 32 ビット 1 0 1 0 X 4K バイト 32 ビット 1 0 1 1 0 4M バイト 32 ビット 1 0 1 1 1 4M バイト 36 ビット 1 1 X 0 X 4K バイト 36 ビット 1 1 X 1 X 2M バイト 36 ビット IA-32 インテル アーキテクチャソフトウェア デベロッパーズ マニュアル から引用 10

X86 のページング p 1 段ページング (4M バイト 2 10 ページ ) リニアアドレス 31 22 21 ディレクトリ オフセット 0 10 ページ ディレクトリ 22 4M バイト ページ 物理アドレス ディレクトリ エントリ 10 32* CR3 (PDBR) 1024 PDE = 1024 ページ * 4K バイト境界にアライメントを合わせられた 32 ビット 図 3-13. リニアアドレス変換 (4M バイト ページ ) IA-32 インテル アーキテクチャソフトウェア デベロッパーズ マニュアル から引用 11

X86 のページング p 2 段ページング (4K バイト 最大 2 20 ページ ) リニアアドレス 31 22 21 12 11 ディレクトリテーブルオフセット 0 12 4K バイト ページ 10 ページ ディレクトリ 10 ページテーブル 物理アドレス ページ テーブル エントリ 20 ディレクトリ エントリ 32* CR3 (PDBR) 1024 PDE 1024 PTE = 2 20 ページ * 4K バイト境界にアライメントを合わせられた 32 ビット 図 3-12. リニアアドレス変換 (4K バイト ページ ) IA-32 インテル アーキテクチャソフトウェア デベロッパーズ マニュアル から引用 12

X86 のページング 31 ページ ディレクトリ エントリ (4K バイト ページ テーブル ) 12 11 9 8 7 6 5 4 3 2 1 0 ページテーブルのベースアドレス 使用可能 G P S 0 A P C D P W T U / S R / W P システム プログラマが使用可能グローバル ページ ( 無視される ) ページサイズ (0 は 4K バイトを示す ) 予約済み (0 に設定 ) アクセスキャッシュ ディスエーブルライトスルーユーザ / スーパーバイザ読み取り / 書き込み存在 31 ページ テーブル エントリ (4K バイト ページ ) ページのベースアドレス 12 11 9 8 7 6 5 4 3 2 1 0 使用可能 P P G A D A C T D P W T U / S R / W P システム プログラマが使用可能グローバル ページページテーブル属性インデックスダーティアクセスキャッシュ ディスエーブルライトスルーユーザ / スーパーバイザ読み取り / 書き込み存在 図 3-14. 4K バイト ページと 32 ビット物理アドレスを使用する場合のページ ディレクトリ エントリとページ テーブル エントリのフォーマット IA-32 インテル アーキテクチャソフトウェア デベロッパーズ マニュアル から引用 13

X86_64 のページング p 4 段ページング (4K ページ 最大 2 36 ページ ) 47 PML4 Liear Address 39 38 30 29 Directory Ptr Directory 21 20 Table 12 11 Offset 0 9 9 9 12 4-KByte Page Physical Addr Page-Directory- Poiter Table PDPTE PDE with PS=0 40 Page-Directory 40 PTE Page Table 40 9 PML4E 40 40 CR3 Figure 4-8. Liear-Address Traslatio to a 4-KByte Page usig IA-32e Pagig Itel 64 ad IA-32 Architectures Software Developer s Maual から引用 14

ページングによる仮想記憶 p 仮想アドレス空間の一部だけ, 物理アドレス空間に保持する ページ枠の集合 ページイン ( 読み込み ) 補助記憶 (HDD など ) ページの集合 ( ページファイル ) ページアウト ( 使用解除 ) プロセス A 仮想アドレス空間 主記憶物理アドレス空間 プロセス B 仮想アドレス空間 15

ページテーブルのフラグ 31 ページ テーブル エントリ (4K バイト ページ ) 12 11 9 8 7 6 5 4 3 2 1 0 ページのベースアドレス 使用可能 G P A T D A P C D P W T U / S R / W P Dirty: 内容変更済み Preset: ページがメモリ内に存在 システム プログラマが使用可能グローバル ページページテーブル属性インデックスダーティアクセスキャッシュ ディスエーブルライトスルーユーザ / スーパーバイザ読み取り / 書き込み存在 IA-32 インテル アーキテクチャソフトウェア デベロッパーズ マニュアル から引用 16

ページングによる仮想記憶の実現 p ページファイル 主記憶に読み込みきれないページを保持しておくためのファイル ( または独立のディスクパーティンション ) Widows の場合 C: pagefile.sys ( 設定を変えないと不可視 ) 仮想記憶の容量 物理メモリ容量 + このファイルの容量 p ページフォールト プロセスが仮想アドレスにアクセスしたとき, そのページに対応するページ枠がページテーブルにない ( 物理アドレス空間にない ) こと 例外トラップ ( 一種の割り込み ) というしくみで,OS に通知される p ページの置き換え カーネルのページ置き換え機能が, 主記憶のページをどれかひとつ追い出して, 仮想記憶のアクセスされたページと交換する 17

ページ置換方式 p ページ置換処理 ページアウト : ページ枠を空けるために, 主記憶に読み込まれているどれかのページを補助記憶に退避すること ページイン : 実行中のプロセスがアクセスしたページを補助記憶から主記憶のページ枠に読み込むこと p ページ置換アルゴリズム では, ページフォルトが起きたとき, どのページをアウトすべきか? ランダム : 追い出すページは乱数で決める ( 性能比較の基準 ) FIFO: 先に入ったページを, 先に追い出す OPT: 最適な方法, 今後一番先まで使わないページを追い出す LRU: 最も長い時間使われなかったページを追い出す NRU: 一定時間使われなかったページからランダムに決める LFU: 使用頻度 ( 回数 ) が最低のページを追い出す 18

FIFO アルゴリズム p 到着順ページ置き換え方式 First I, First Out ( 先入れ, 先出し ) 先に入ったページを, 先に追い出す性能はまあまあで, 処理が簡単で高速である Widows はこれの改良版 ( らしい ) p FIFO アルゴリズムによるページングの例 ページ参照順 0 1 2 3 0 1 4 0 1 2 3 4 ページフォルト発生 v v v v v v v v v ページ枠の内容 ( 主記憶 ) 0 0 0 0 3 3 3 4 4 4 4 4 4 1 1 1 1 0 0 0 0 0 2 2 2 2 2 2 2 1 1 1 1 1 3 3 19

OPT アルゴリズム p 最適アルゴリズム Optimum 理論上 の最適な方法 ( 他の方法の評価用 ) 今後一番先まで使わないページを追い出す 未来を予知していないと決められない 実現不可能! p OPT アルゴリズムによるページングの例 ページ参照順 0 1 2 3 0 1 4 0 1 2 3 4 ページフォルト発生 v v v v v v v ページ枠の内容 ( 主記憶 ) 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 2 3 3 2 2 3 3 3 4 4 4 4 4 4 20

LRU アルゴリズム p 最長不使用ページ置き換え方式 Least Recet Used 最も長い時間使われなかったページを追い出す 置換回数の性能は良いが, 実現しようとすると処理が複雑で遅い Liux や Mac は, これを簡単化した NRU(Not Recet Used) p LRU アルゴリズムによるページングの例 ページ参照順 0 1 2 3 0 1 4 0 1 2 3 4 ページフォルト発生 v v v v v v v v v v ページ枠の内容 ( 主記憶 ) 0 0 0 0 3 3 3 4 4 4 2 2 2 1 1 1 1 0 0 0 0 0 0 3 3 2 2 2 2 1 1 1 1 1 1 4 21

参照の局所性 p 仮想記憶がうまく動く理由 実メモリにプロセスの一部しか読み込まなくてもなぜうまく動くか? プロセスが参照するアドレスは, 空間的 時間的に偏る傾向がある p 空間局所性 プログラムが同時に使うメモリは,( 空間的に ) 近くにあることが多い例 ) 逐次処理のプログラムコード, ローカル変数の配置など ただし, オブジェクト指向プログラミングではそうならないことも多い p 時間局所性 プログラムは, 同じメモリを ( 時間的に ) 使い続けることが多いある時間を見ると, 同じ領域のメモリを繰り返しアクセスしている 例 ) ループ実行中のプログラムコード, 関数内での変数アクセス 22

スラッシング p スラッシング OS がページ置換処理に忙殺され, 他の処理が滞ってしまう状態 多数のプロセスを実行させると, プロセス切り替えによって, 頻繁にページフォールトが起こり, ページ置換処理が追いつかなるなる 主記憶に対して仮想記憶を大きく取りすぎた場合に発生しやすい 処理能力 0( スループット ) プロセス数 ( 多重度 ) システムがほとんど停止 ディスクがカリカリカリカリ 23

仮想記憶の弱点 p 処理の遅延 ページ置換処理 (HDD 等からの読み込み ) は時間がかかる特に, リアルタイム処理では, 予測できない遅延は問題になる p 処理が複雑 専用のハードウェア機能 (MMU) が不可欠組み込み用マイコンの多くでは,MMUの機能がないページ置換アルゴリズムも含めて, プログラムが複雑化する p 補助記憶装置の使用が前提 多くの組み込み OS ゲーム機では仮想記憶をサポートしない 24

演習課題 ( 後日提出 ) p 課題 11a ページ置換方式 以下の表は, ページ枠が 3 つしかないコンピュータにおける仮想記憶のページ参照順を示している このページ参照順の場合に,FIFO,LRU,OPT の各ページ置換方式によって, どのようにページ枠の内容が変化するか, それぞれの表を完成させよ ページフォルトが発生する場合には, チェック印 (v) を記入すること ページ参照順 0 1 3 0 2 0 3 4 2 0 1 2 ページフォルト発生 ページ枠の内容 ( 主記憶 ) 0 1 2 25