misazu 2022年07月27日 カード18 いいね0
AIによる要約・使い方の説明

AIによる分析のため、間違った解釈や説明をしている場合があります。

要約

本書はオペレーティングシステム(OS)におけるメモリ管理技術、特に「仮想記憶」の仕組みに焦点を当てた学習用カードセットです。スワップスケジューリングにおけるフェッチ・割付け・置き換えの3要素から始まり、デマンドページングやプリページングといったメモリ読み込み戦略、FIFO・LRU・LFU・クロックアルゴリズムといったページ置換アルゴリズムの特性と欠点について体系的に解説しています。また、メモリ管理の悪循環である「スラッシング」の概念や、局所置き換えと大域置き換えの差異、ワーキングセットを用いた効率的なメモリ割り当て制御手法についても網羅しています。プログラムの実行効率を左右するOSの低レイヤーにおける動的制御について、アルゴリズムの理論的背景と実践的なトレードオフをバランスよく学べる内容となっています。

使い方

本カードセットは、大学の計算機科学系学科やOSの基礎知識を必要とするエンジニア、情報処理技術者試験(応用情報技術者試験やネットワークスペシャリスト等)の学習者を主な対象としています。単なる暗記ではなく、各アルゴリズムが「どのような前提条件や経験則(参照局所性など)に基づいているか」を理解することが推奨されます。

効率的な学習方法として、まず各手法の利点と欠点(トレードオフ)を比較表にまとめると理解が深まります。また、ページフォールト平均間隔法のような応用的な制御手法については、具体的な数値モデルを想定してシミュレーションを行うとより深く定着します。OSの設計判断には常にトレードオフが存在するため、特定の方式が万能ではない理由を考えながら学習してください。試験対策としては、Béládyの例外が起こるケースと起こらないケース(スタックアルゴリズム)の区別が重要です。

#オペレーティングシステム #メモリ管理 #仮想記憶 #ページング #ページ置換アルゴリズム #スラッシング #ワーキングセット

広告

テスト

ビューア設定

[Enter]で回答、[Shift + Enter]で改行します。テスト結果は全て回答すると保存されます。キーボードショートカットテストビューア設定

OS11
広告
  • スワップスケジューリング 3つ 内容それぞれ
    ・フェッチ(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 で次にページフォールトを起こしたページは、フ レーム内の他のページをスワップアウトすることなく、ス ワップインする(プロセスへのフレーム割り当てを増やす)
よく頑張りました
テストスタート
ログイン
オンライン単語帳

このページを利用するにはログインする必要があります。ログインするとAnkilotをより便利にご利用いただけます。すでにアカウントをお持ちの方はログイン、お持ちでない方は新しくアカウントを登録してください。