当サイトについて

仮想記憶―ページ置き換えアルゴリズム(FIFO方式)を極める

当サイトは、「仮想記憶―ページ置き換えアルゴリズム(FIFO方式)を極める」をテーマに情報を掲載しているサイトです。

アルゴリズムとは

アルゴリズムという言葉は、ITやコンピューターに限らず、広くさまざまな場面で使われています。 アルゴリズムとは、一般的には「問題を解決する手順」という説明になります。

ITやコンピューター分野におけるアルゴリズムは、コンピュータで問題を処理するためにプログラムとして表現するのに向いている解決法です。

例をあげると、グラフ理論、オペレーションズリサーチ、数値計算、データ構造の操作、整列、数式処理、言語処理などです。

詳細

仮想記憶方式のページ置き換え

仮想記憶方式では、プログラムの実行中、主記憶領域に存在しないページが参照されると、 ページフォルトという入出力を伴うプログラムの割り込みをきっかけに、必要なページを主記憶領域にロードするページインが行われます。

FIFO(First-In First-Out)

先入れ先出し方式です。 先にページインしたページから先に追い出します。

FIFO方式の例―平成18年春期基本情報技術者午前 問27

仮想記憶におけるページ置き換えアルゴリズムとしてFIFO方式を採用する。 主記憶のページ枠が3で、プログラムが参照するページ番号の順序が、4→3→2→1→3→5→2のとき、ページインは何回行われるか。 ここで、初期状態では、主記憶には何も読み込まれていないものとする。

  [ア] 2   [イ] 3   [ウ] 5   [エ] 6

解説

FIFO(First-In First-Out)は、先入れ先出し方式です。 先にページインしたページから先に追い出します。 また、ページインとは、磁気ディスクから主記憶装置にページをロードすることです。

以下で、ページが読み込まれる順に検討します。

参照枠内イン回数説明
  4[4][][]  14を読み込みます。
  3[4][3][]  23を読み込みます。
  2[4][3][2]  32を読み込みます。
  1[3][2][1]  4一番古い4を消し、1を読み込みます。
  3[3][2][1]  43は読み込まれているのでページインは不要です。
  5[2][1][5]  5一番古い3を消し、5を読み込みます。
  2[2][1][5]  52は読み込まれているのでページインは不要です。

ページインは5回です。

答え:[ウ]

戻る