第６回　仮想記憶とページング ページング ページ取り出し方式 ページ置き換え方式 中間テスト（４０分）

Presentation on theme: "第６回　仮想記憶とページング ページング ページ取り出し方式 ページ置き換え方式 中間テスト（４０分）"— Presentation transcript:

1 第６回　仮想記憶とページング ページング ページ取り出し方式 ページ置き換え方式 中間テスト（４０分）

2 ページング 仮想アドレス空間、物理アドレス空間ともにページとよばれる固定区画に分割される
仮想ページ番号　…　仮想アドレス空間内のページに付け られる番号 物理ページ番号　…　物理アドレス空間内のページにつけ られる番号 ページ枠　…　物理ページ 仮想アドレス（L)　＝　ページ番号（P)＋ページ内変位（O) P　＝　L　/ N ※　Nはページサイズ O ＝　L mod N

3 ページング（図解） A B C D E F G 物理ページ番号 （ページ枠番号） A G C F 1 存在ビット 2 仮想ページ番号
A G C F 1 存在ビット 2 仮想ページ番号 物理ページ番号 3 A B C D E F G 4 1 2 3 4 5 6 1 2 7 11 5 1 5 2 6 3 7 A B C 8 4 D E F 9 5 G 10 6 11 ページテーブル 12 仮想記憶 補助記憶 13 14 主記憶

4 ページングにおけるアドレス変換 物理アドレス ＝ 物理ページ番号＋ページ内変位 p d p' p’ d’ ページテーブル ベースレジスタ b
物理アドレス　＝　物理ページ番号＋ページ内変位 ページテーブル ベースレジスタ b 仮想アドレス 仮想ページ番号 ページ内変位 p d + ｂ p 物理アドレス 存在ビット 修正ビット 参照ビット アクセス保護情報 p' p’ d’ ページテーブル

5 ページに対するアクセスと、ページフォルト
セグメンテーションと同様の手順で、仮想アドレスから物理アドレスを変換 ページフォルト...　仮想アドレスから物理アドレスへの変換時に、主記憶上にページが不在 ページフォルト割込み...　ページフォルトが発生すると割り込みによって主記憶上に空きページ枠を探し、そこに補助記憶のページを読み込む ページの置き換え...　ページフォルト割込み時に、空きページ枠が存在しないときに、主記憶上のぺーじ１つを掃き出してページ枠を確保する ページ枠テーブル...　ページ枠の番号（物理ページ番号）をインデックスとして、あいているかどうかを示す存在ビットを記載したテーブル

6 ページフォルトの手順 ページフォルト発生 ページを補助記憶から 取り出す ページフォルト割込みで 割り込みハンドラへ 空きページ枠に読み込む
空きページの検索 あり 空きページは？ ページテーブルの存在 ビットを 0 から１に書き換える なし ページ置き換えに よりページを掃き出す ページ枠テーブルの 空きビットをクリアする 割込み処理から復帰 空きページを確保 処理の再開

7 ページの取り出し方式 デマンドページング プリページング ページが参照され、ページフォルトが発生したときに主記憶にページを読み込む
ページ転送に無駄がない ページアクセスのオーバヘッドが大きい プリページング ページが参照される前に、予めページを主記憶に読み込んでおく ページアクセスによるオーバヘッドが小さい 使用されるページ予想が難しい 無駄なページ転送が生じる 実際には、デマンドページングと併用して用いられ、ページフォルトが発生した場合に、仮想アドレス空間の連続したページを一緒に読み込む プログラム実行開始時にまとめて数ページ読み込んでおく

8 ページの置き換え方式 ページ置き換えアルゴリズム...ページフォルト率を下げることが目標 LRU（Least Recently Used)
ページ参照の時間的局所性（locality) LRU近似アルゴリズム クロックアルゴリズム　...　FINUFO（first in not used first out) 大域LRU　⇔　局所LRU ワーキングセット法 ワーキングセット...　過去一定時間T内に参照されたページ集合 ウィンドウサイズ（T) PFF法（page fault frequency strategy) スラッシング...　どのプログラムに対しても十分なページ枠が与えられないほどページ枠が不足することによって、頻繁にページ置き換えが起きる現象

9 ページングに使われる技巧 多段ページング アドレス変換の高速化
仮想アドレス全体空間全体がフルに使用されることはないため必要な部分だけページテーブルを持たせる ページテーブルの共用が可能となり、記憶領域が節約でき、ページ置換時にエントリの変更がスムーズになる アドレス変換の高速化 TLB（translation look-aside buffer) or ATB(address translation buffer) 最近アドレス変換したページのページテーブルを高速なバッファに格納しておく