Operating System 仮想記憶 2018-12
記憶階層 高速 & 小容量 ( 高価 ) レジスタ アクセスタイム 数ナノ秒 容量 ~1KB CPU 内キャッシュ (SRAM) 数ナノ秒 1MB 程度 ランダムアクセス 主記憶 (DRAM) 数十ナノ秒 数 GB 程度 ランダムアクセス フラッシュメモリ (SSD) 約 100 万倍 シーケンシャルアクセス 磁気ディスク (HDD) 数十ミリ秒 数百 GB 1TB 程度 光磁気ディスク (CD-R DVD-RW 等 /MO) 磁気テープ 0.1 秒 ~ 1GB~ 低速 & 大容量 ( 廉価 ) 2
仮想記憶 p 仮想記憶 (virtual memory) n 仮想 = 本物でないが実質的に同じ n HDD 等の補助記憶の領域を主記憶の延長のように見せかける技術 n 使わないメモリ領域を HDD に待避し, 使うときにディスクから復帰する 主記憶 (DRAM) p ページング方式 n メモリ空間を固定長の区画 ( ページ ) に自動的に分割して管理する 補助記憶 (HDD) p セグメンテーション方式 n プログラムで予め設定した可変長の 区画 ( セグメント ) で管理する 3
ページング p メモリのページ化 n 主記憶を, 固定長 ( 例 :4Kバイト) のブロック ( ページ枠 ) に分割する n メモリの内容 ( データ ) も, 同サイズの ページ の集合に分割する n どのページをどのページ枠の入れるのかは, 入れ替え可能にする p 物理アドレスと仮想アドレス n 物理アドレス : ハードウェアRAM 上の場所 ページ 枠 のアドレス n 仮想アドレス : プロセスが実行中に使うアドレス ページのアドレス n プロセスが動くためには, 仮想 物理の自動アドレス変換が必要 p ページングの効果 n 物理メモリよりも広い仮想アドレス空間が考えられる 仮想記憶 n メモリコンパクションやプロセスの再配置処理が不要になる 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 各プロセスに独立の仮想アドレスを提供 n 動的再配置の問題も完全解決 OS( カーネル ) プロセス A OS( カーネル ) プロセス B OS( カーネル ) プロセス C 変換 OS( カーネル ) プロセス A プロセス C プロセス B プロセス A の 仮想アドレス空間 プロセス B の 仮想アドレス空間 プロセス C の 仮想アドレス空間 物理メモリ空間 ( 実際のメモリ ) 6
動的アドレス変換 p 動的アドレス変換機構 n プロセスの実行中に参照されるアドレス ( 仮想アドレス ) を, そのつど物理アドレス ( ハードウェア上でのアドレス ) に変換するしくみ n MMU(Memory Management Unit) というハードウェアが支援 p アドレスの内部形式 n 32 ビットなら, 例えば上位 20 ビットと下位 12 ビット (4KB 分 ) に分解 n 例 0x12345678 [ ページ番号 0x12345][ ページ内 0x678] n 仮想アドレス =[ ページ番号 ][ ページ内アドレス ] n 物理アドレス =[ ページ枠番号 ][ ページ内アドレス ] p ページテーブル ( アドレス変換テーブル ) n ページ番号 ページ 枠 番号のアドレス変換表 n 多重仮想アドレスの場合は, 各プロセスがページテーブルを持つ 7
動的アドレス変換機構 ページテーブルベースレジスタ (CPU 内 ) tbl 仮想アドレス ページテーブルの位置を保持 p ページ番号 a ページ内アドレス tbl 番地 p MMU で変換 p = tbl[p] tbl[p] p ページ枠番号 ページ内アドレス ページテーブル ( 主記憶内 ) 物理アドレス p a 8
多段ページング p 広大なアドレス空間に対応 n 必要なときだけ 2 段目以降のテーブルを保持してメモリを節約 Wikipedia から引用 9
ページングによる仮想記憶 p 仮想アドレス空間の一部だけ, 物理アドレス空間に保持する ページ枠の集合 ページイン ( 読み込み ) 補助記憶 (HDD など ) ページの集合 ( ページファイル ) ページアウト ( 使用解除 ) プロセス A 仮想アドレス空間 主記憶物理アドレス空間 プロセス B 仮想アドレス空間 10
ページングのしくみ p ページファイル n 主記憶に読み込みきれないページを保持しておくためのファイル ( または独立のディスクパーティンション ) n Windows の場合 C:\pagefile.sys ( 設定を変えないと不可視 ) n 仮想記憶の容量 物理メモリ容量 + このファイルの容量 p ページフォルト n プロセスが仮想アドレスにアクセスしたとき, そのページに対応するページ枠がページテーブルにない ( 物理アドレス空間にない ) こと n 例外トラップ ( 一種の割り込み ) というしくみで OS に通知される p ページの置き換え n カーネルのページ置き換え機能が, 主記憶のページをどれかひとつ追い出して, 仮想記憶のアクセスされたページと交換する 11
ページ置換方式 p ページング処理 n ページアウト : ページ枠を空けるために, 主記憶に読み込まれているどれかのページを補助記憶に退避すること n ページイン : 実行中のプロセスがアクセスしたページを補助記憶から主記憶のページ枠に読み込むこと p ページ置換アルゴリズム n では, ページフォルトが起きたとき, どのページをアウトすべきか? n ランダム : 追い出すページは乱数で決める ( 性能比較の基準 ) n FIFO: 先に入ったページを, 先に追い出す n OPT: 最適な方法, 今後一番先まで使わないページを追い出す n LRU: 最も長い時間使われなかったページを追い出す n NRU: 一定時間使われなかったページからランダムに決める n LFU: 使用頻度 ( 回数 ) が最低のページを追い出す 12
FIFO アルゴリズム p 到着順ページ置き換え方式 n First In, First Out ( 先入れ, 先出し ) n 先に入ったページを, 先に追い出す n 性能はまあまあで, 処理が簡単で高速である n Windows はこれの改良版 ( らしい ) 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 13
OPT アルゴリズム p 最適アルゴリズム n Optimum n 理論上 の最適な方法 ( 他の方法の評価用 ) n 今後, 一番先まで使わないページを追い出す n 未来を予知していないと決められない 実現不可能! 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 14
LRU アルゴリズム p 最長不使用ページ置き換え方式 n Least Recent Used n 最も長い時間使われなかったページを追い出す n 置換回数の性能は良いが, 実現しようとすると処理が複雑で遅い n Linux や Mac は, これを簡単化した NRU(Not Recent 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 15
参照の局所性 p 仮想記憶がうまく動く理由 n 実メモリにプロセスの一部しか読み込まなくてもなぜうまく動くか? n プロセスが参照するアドレスは, 空間的 時間的に偏る傾向がある p 空間局所性 n プログラムが同時に使うコードやデータは, 近くにあることが多い n 例 : 関数のなかの変数など n ただし, オブジェクト指向プログラミングでは例外もある p 時間局所性 n プログラムは, 同じコードやデータを連続的に使い続けることが多い n ある時間を見ると, ほぼ同じ領域のメモリを繰り返しアクセスしている n 例 : ループの実行中など 16
スラッシング p スラッシング n OS がページング処理に忙殺され, 他の処理が滞ってしまう状態 n 多数のプロセスが活発に動作すると, プロセス切り替えにともなって, 頻繁にページフォルトが起こり, ページング処理が追いつかなるなる n 主記憶に対して仮想記憶を大きく取りすぎた場合に発生しやすい 処理能力 ( スループット ) システムがほとんど停止 ディスクがカリカリカリカリ 0 プロセス数 ( 多重度 ) 17
仮想記憶の弱点 p 処理の遅延 n ページング処理 (HDDからの読み込み) は時間がかかる n リアルタイム処理では, 予測できない遅延は問題になる p 処理が複雑 n 専用のハードウェア機能 (MMU) が不可欠 n 組み込み用マイコンの多くでは,MMUの機能がない n ページ置換アルゴリズムも含めて, プログラムが複雑化 p 補助記憶装置の使用が前提 多くの組み込み OS では仮想記憶をサポートしない 18
演習課題 ( 後日提出 ) p 課題 12a ページ置換方式 n 以下の表は, ページ枠が 3 つしかないコンピュータにおける仮想記憶のページ参照順を示している n このページ参照順の場合に,FIFO,LRU,OPT の各ページ置換方式によって, どのようにページ枠の内容が変化するか, それぞれの表を完成させよ n ページフォルトが発生する場合には, チェック印 (v) を記入すること ページ参照順 0 1 3 0 2 0 3 4 2 0 1 2 ページフォルト発生 ページ枠の内容 ( 主記憶 ) 0 1 2 19