OS11
暗記
-
スワップスケジューリング ３つ 内容それぞれ
・フェッチ(fetch)
ページをメモリ上にいつ読み出すか
デマンドページング、プリページング
・割付け(主記憶のどの位置にスワップインするか)
ページは、実記憶上の任意の位置に割付け可能
・置き換え(主記憶のどのページを追い出すか)
ページフォルトが発生した時に実記憶が満杯だったら、新 たにページインする領域を確保するために、使用中のページ のどれかを選んで追い出す(スワップアウトする)。
ページ置換アルゴリズム
- どんな場合にも最適なアルゴリズムは存在しない
-
デマンドページングとは 利点欠点
要求時ページングとも
プロセスが実行中に、アクセスや参照を要求するページをそのたびに動的に読み込む
利点
必要なページだけを読み込むという点で、無駄がない(要求を予測する必要もない)
欠点
新しいページを参照するたび、プロセスが待たされる特に、プロセスの開始時にはページフォールトが集中的に発生する
-
デマンドページングの効率 式
-
プリページングとは 利点欠点
アクセスされるページをあらかじめ予測し、必要になると考えられるページを実行前に読み込む(予測ページング)
利点
予測の的中率が高ければ、複数ページを一度に読み込む ことでページフォールトのオーバーヘッドを軽減し、高速 化が達成できる
短所
完全な予測を行うことは不可能
不要なページも読み込んでしまう可能性がある
-
プリページングで工夫すること 3つ
デマンドプリフェッチ:ページフォールトの際に関係の あるページも読み込む。
初期ロードプリフェッチ:実行開始直後のデマンドプリ フェッチで、読み込むページ数を通常より増やす
コンパイル時に静的解析を行い、実行時にその情報を利用 する(OSとコンパイラの機能分担)
最近ではメモリが大容量化しているため、プリページングの 短所の影響が少ない。そのため、デマンドページングと組み 合わせて用いることが多くなっている
-
フェーズ化現象とは
・空間局所性をもち、さらにある時点を境にプログラムがアクセスするページが急に切り替わる性質
プログラミング言語で実行される関数や実行箇所(特にループ)が切り替わる時にこのような傾向が現れる
同じページ群をアクセスする期間をフェーズと呼ぶ
プログラムの主な処理はフェーズ内で行われる。このため、フェーズ内でページフォールトができるだけ発生し ないようにする必要がある。
ページフォールトはフェーズの遷移の際に多発する。た だし、遷移時間はプログラムの実行時間全体から見ると 非常に少ないため、遷移の際のページフォールトを低減 させる設計は必要ない。
-
FIFOとは デメリットになりかねない2
到着順: 実メモリにスワップインした時刻が最 も古い(最も長時間存在している)ページを最 優先のスワップアウト対象とする
使われ続けているページがスワップアウトされる
こともある
割付けられるページ枠が増えると、逆にページ フォルトが増えることがある(Beladyの例外)
-
LRUとは 長所短所
最長不使用: 最後にアクセスされた時刻が最も古い(最近使われていない)ページを最優先のスワップアウト対象とする
最近使われていないページは今後も使われない可能性が高 い、という経験則に基づく(常に正しいわけではない)
Beladyの例外は起こらない
長所:時間的参照局所性を反映しているので、ページフォールト率は低くなる
Beladyの例外は起こらない
短所:アクセス履歴を管理する仕組みが複雑になり、ページ置換にも時間がかかる
改良方法として参照ビット法などがある
-
LFUとは 長所短所
最低使用頻度順: 実行開始から最も使用頻度の少ないページを最優先のスワップアウト対象とする
長所:長期間使われるページが追い出されることはない
短所:使用頻度の低いページが追い出されやすい
過去の利用頻度が高いページが、最近の利用傾向を反映せずに優遇されてしまう
新しくスワップインしたページが頻繁に追い出される傾向 がある
-
クロックアルゴリズムとは
参照ビット法のこと
LRUを簡便化した方式のひとつ
各ページ表に参照ビットを設ける。ページが参照・変 更されたら1を立てる。
参照ビットを巡回して調べる「針」を考える。
ページフォールトが発生したら、現在の針の指す参照 ビットを調べる。1だったら0にして次のページへ。 0だったら前回の巡回から参照がないので、このペー ジを追い出す。
実行効率は比較的良く、実現も容易
-
Béládyの例外とは
プロセスに割り当てられているページ数を増やしたのにページフォルトの回数が増加する現象
FIFOのようなアルゴリズムで発生することがある
- FIFOでは、ページ数と等しい周期的なアクセスでページ フォールトが発生しやすい。この関係がずれると、ペー ジフォールトが多発したり、発生しなくなったりする
スタックアルゴリズムと呼ばれるページ置き換えアルゴリズムでは Béládyの例外は発生しない
ページ数 n の時の動作と、ページ数 n+1 の時の動作 で、まったく同じ部分が存在するアルゴリズム
LRU はスタックアルゴリズムである
-
スラッシングとは
プロセッサが、OS機能であるページ置換にかかりきりになり、本来のプログラムの動作に支障をきたす状態
実行に必要な仮想メモリの総容量に比べて、実メモリの容量が小さ過ぎる場合に発生する
「実メモリ容量:仮想メモリ容量」の比率が、ある割合を越えると、急激にスラッシングが発生することが知ら
れている
CPU利用率が上がらない時にプロセスの多重度を上げ過 ぎると、プロセスがページング待ちに入り、CPU利用率 が上がらないという悪循環に陥ることがある
-
大域置き換えとは
すべてのプロセスがページ枠の集合を共有 他のプロセスのページ枠を奪うことがある
- 多くのページが必要なプロセスに、柔軟に割り当てるこ とも可能
- 各プロセスのページフォルト率が、他のプロセスの実行 状況によって変化する
動的ページ置き換え方式が必要となる
-
局所置き換えとは
そのプロセスに割り当てられているページ枠の集合からのみ選択可能
-
ワーキングセットとは
現在の時間を t としたとき、t と t – T の間に参照されたページの集合
ある時点でのワーキングセット(内容とサイズ)を動的に予測することは困難
-
ワーキングセット法とは
・プロセスのワーキングセットをできるだけ主記憶上に維持しようとする技法
ワーキングセットを実メモリ上に確保できているプロセスのみ を実行、あるいは優先して実行する
ワーキングセット以外のページを、優先してスワップアウトの 対象とする
ワーキングセットが実メモリ上に確保できない、優先順位の低 いプロセスは、全ページを解放する
・ワーキングセットの大きさの設定が、大きすぎても、小さすぎても実行効率が悪くなる
大きすぎると、同時に実行できるプロセス数が少なくなる
小さすぎると、ページフォールトが多発しやすい
-
ワーキングセット法の近似
・ワーキングセットを直接調べるのは困難
・ワーキングセットの大きさ ≒ プロセスに割り当てるページフレーム数
・プロセスごとにページフォールト発生の平均間隔を調べることは可能
ページフォールト発生の平均間隔 ≒ ページフォールト率の逆数
ページフォールトの平均間隔が大きいプロセス
プロセスのページフレーム数は比較的十分
ページフォールトの平均間隔が小さいプロセス
プロセスには十分なページフレームが割り当てられていない
-
ページフォールト平均間隔法 説明せよ
ページフォールトの平均間隔の上限を Ut, 下限を Lt と定めておく
ページフォールトごとに、全プロセス { Pn } に対して ページフォールトの平均間隔 In を再計算して:
if ( In > Ut )
このプロセス Pn の最後のページフォールトから、今までに参
照されなかったページをスワップアウトする(プロセスへ Pn のフレーム割り当てを減らす)... LRUを使う
if ( In < Lt )
プロセス Pn で次にページフォールトを起こしたページは、フ レーム内の他のページをスワップアウトすることなく、ス ワップインする(プロセスへのフレーム割り当てを増やす)
-
