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 で次にページフォールトを起こしたページは、フ レーム内の他のページをスワップアウトすることなく、ス ワップインする(プロセスへのフレーム割り当てを増やす)

広告

コメント