【基本情報頻出問題】ページング方式の種類とページ置き換えまとめ

今回は、基本情報技術者試験の午前試験で頻出されているメモリ管理についてと、ページング方式やページの置き換え方式についてを解説します。

この記事を読むことで、「LRU方式」とか、「ページング方式」「スラッシング」といった用語そのものが持つ意味がわかるようになったり、

「ページの置き換え」とはなにか。ページの置き換えがいつ起きて、どの順番で追い出されるのか。などがわかるようになります。

メモリ管理方式について

メモリ管理の管理方式には、固定区画方式と可変区画方式があります。

固定区画方式はメモリを同じ要領の区画に分割して、必要な区画データに割り当てるメモリ管理方式で、メモリの管理が容易である点と、メモリの割当て、開放が高速である点がメリットで、メモリの使用効率が悪いのがデメリットです。

可変区画方式はメモリをデータの大きさに応じた区画を割当てるメモリ管理方式で、メモリの使用効率が良いメリット、フラグメンテーションが発生したり、メモリの割当て、開放に手間がかかる点がデメリットです。

それぞれの特徴をしっかり覚えておくのと同時に、可変区画方式に関しては下記でもう少し掘り下げていきます。

フラグメンテーション

可変区画方式では、空き領域により小さいデータを読み込むので、領域の確保と解放を繰り返していくと、細かい領域がたくさん発生することがあります。

細分化された使いみちのない領域が発生することをフラグメンテーションと呼びます。

コンパクション

コンパクションは断片化された領域をまとめて大きな領域にすることです。

ページング方式とは？仮想記憶システムについて

仮想記憶システムとは、磁気ディスク装置などの補助記憶装置を用いて、主記憶装置の容量以上のアドレス空間を作り出すことです。

今回は、基本情報技術者午前試験でよく目にする、4つ「仮想記憶と実記憶」「ページング方式」「スラッシング」「ページフォルト」って用語についてまとめておきます。

仮想記憶OS

仮想記憶と実記憶の違いをしっかり押さえておきましょう！

仮想記憶とは、仮想記憶OSで作られたアドレス空間のことで、論理アドレス空間とも呼ばれます。

それに対して、実記憶は、主記憶装置の実際のアドレス空間のことで、物理アドレス空間とも呼ばれます。

仮想記憶OSってなんだろう？ってのを説明するならば、仮想記憶を作ろうとするOSの機能のことを呼ぶと思ってください！

ページング方式

ページング方式は、仮想記憶を作成する1つの方式のことで、OSがデータを一定の大きさの単位に分割したする(ページ)ことで、フラグメンテーションを起こらないようにする方式。

論理的な構造とは無関係に分割するので、他のページを頻繁に参照するプログラムなどでは、次に説明するスラッシングが起こってしまうのがポイント。

スラッシング

スラッシングとは、複数のタスクが実記憶を求めて、競合することで頻繁にページの交換が起こることです。

スラッシングの影響で、CPUはページ交換するのに使われてしまうので、本来のソフトを実行したいのに、なかなかCPUが働いてくれない！いわゆる重い状態になってしまうのがポイントです。

ページフォルト

ページフォルトとは、実記憶にページが存在しないことです。

ページが存在しない際に発生する割り込みのエラーのことをページフォルトと呼ぶこともあれば、存在しない事自体を指すこともあるので、ページフォルトといったら、実記憶に存在しないページを参照したんだなぁと思ってもらえばOKです！

ページの置き換えについて

ページング方式をもっと掘り下げて行きましょう。

例えば、主記憶装置には3ページ分の領域があり、すでに1.2.3のデータが入っているとします。

次に4を参照したい時、主記憶装置にはデータが入らないので、1つ追い出して、4を主記憶装置に入れる処理を行います。

この処理をページの置き換えと呼びます。

そして、ページの置き換えにはFIFO方式やLRU方式などといった種類があります。

「FIFO」「LRU」「LIFO」「LFU」などたくさん名前が出てきますが、これらは「どの順番でデータを追い出すのか」を定めたものだと思ってください。

FIFO方式・LIFO方式

FIFO 👉 ファースト・イン・ファースト・アウトの略称で、そのまま訳せば、「最初に入ったものを最初に出す」みたいなイメージを持ってもらええたらOKです。

一番古くからあるデータを最初に実記憶から追い出して仮想記憶に入れるのがFIFO方式です。

逆に、LILOは ラスト・イン・ファースト・アウトの略称なので、「最後に入ったものを最初に出す」方式で、一番新しいデータを最初に実記憶から追い出して仮想記憶に入れる方式と覚えておきましょう。

LRU方式・LFU方式

LRU 👉 リースト・リーセントリー・ユーズドの略称で、そのまま訳せば、「最も最近使わてない」なのでちょっと分かりづらいですが、なんとなく一番使われてないやつみたいなイメージができそうです。

最後に参照されてから一番経過時間が長いページから実記憶から追い出す方式です。

LRU方式は、一番参照されていないデータを実記憶から追い出す方式です。

LFU 👉 Least Frequantly Used の略称で、そのまま訳すと、「少なくとも頻繁な使われたやつ」って意味なので、一番最近使われたやつみたいなイメージができます。

LFU方式は、一番最近使われたデータを実記憶から追い出す方式です。

【頻出】過去問にチャレンジ！

ページング方式の用語の意味を回答する問題

ページング方式の説明として，適切なものはどれか。

1. 仮想記憶空間と実記憶空間を，固定長の領域に区切り，対応づけて管理する方式
2. 主記憶装置の異なった領域で実行できるように，プログラムを再配置する方式
3. 主記憶装置を，同時に並行して読み書き可能な複数の領域に分ける方式
4. 補助記憶装置に，複数のレコードをまとめて読み書きする方式

出典：平成29年春期　問15

👉 1

ページング方式は、仮想記憶空間と実記憶空間を、固定長の領域に区切って、対応付けて管理する方式のことです。

1つ1つの領域をページと呼び、実記憶に無いページを参照しようとすると、ページフォルトと呼ばれる割り込み込みが発生するので、仮想記憶空間とページの置き換えを行うことで、参照したいデータを実記憶にいれます。

実記憶にデータを入れることをページイン、実記憶からデータを出すことをページアウトと呼びます。

ページング方式のアルゴリズム種類を知っているかを問う問題

LRUアルゴリズムで，ページ置換えの判断基準に用いられる項目はどれか。

1. 最後に参照した時刻
2. 最初に参照した時刻
3. 単位時間当たりの参照頻度
4. 累積の参照回数

出典：平成28年秋期　問19

👉 1

LRUアルゴリズムは、Least Recently Used の頭文字をとったものなので、一番使われてないやつから追い出すアルゴリズムです。

つまり、最後に参照されてから、一番時間が経過しているページのデータを追い出すので、判断基準は「最後に参照した時刻」。

よって答えは1。

仮想記憶システムの用語の意味を知っているかを問う問題

仮想記憶システムにおいて主記憶の容量が十分でない場合，プログラムの多重度を増加させるとシステムのオーバヘッドが増加し，アプリケーションのプロセッサ使用率が減少する状態を表すものはどれか。

1. スラッシング
2. フラグメンテーション
3. ページング
4. ボトルネック

出典：平成28年秋期　問17

👉 1

スラッシングは主記憶の容量が十分でない場合、プログラムの多重度を増加させるとシステムのオーバーヘッドが増加し、アプリケーションのプロセッサ使用率(CPU使用率)が減少して、処理速度が遅くなる現象のこと。

フラグメンテーションはディスク装置の記憶領域の中に使用されない領域の断片が存在した状態になりアクセス効率が低下する減少。

ページングは仮想記憶管理方式の一つで、仮想アドレス空間と主記憶アドレス空間を「ページ」と呼ばれる固定長の区画に分割し、このページ単位で主記憶と補助記憶装置のアドレス変換を行う方式です。

ボトルネックは処理性能や通信性能の向上を阻む要素のこと。

LRU方式でページを置き換える順番がわかる？って問題

ページング方式の仮想記憶において，ページ置換えアルゴリズムにLRU方式を採用する。主記憶に割り当てられるページ枠が4のとき，ページ1，2，3，4，5，2，1，3，2，6の順にアクセスすると，ページ6をアクセスする時点で置き換えられるページはどれか。ここで，初期状態では主記憶にどのページも存在しないものとする。

1. 1
2. 2
3. 4
4. 5

出典：平成27年春期　問20

👉 4

LRU方式は「最後に参照されてから一番時間が経過しているものから追い出して置き換える方式です。

ページ枠は4つなので、一番最初に主記憶に割当てられているのは、「1,2,3,4」

5を参照する時、一番参照されていない1とページの置き換えをする。👉 「2,3,4,5」

2の参照は主記憶から参照できるのでページの置き換えはなし。 👉 「3,4,5,2」

1の参照する時、一番参照されていない3とページの置き換えをする。👉 「4,5,2,1」

3の参照する時、一番参照されていない4とページの置き換えをする。 👉 「5,2,1,3」

2を主記憶から参照する。👉 「5,1,3,2」

6の参照は、一番参照されていない4とページの置き換えをする。 よって答えは4。

ページの置き換え回数を求める問題

仮想記憶方式のコンピュータにおいて，実記憶に割り当てられるページ数は3とし，追い出すページを選ぶアルゴリズムは，FIFOとLRUの二つ考える。あるタスクのページアクセス順序が

　　1, 3, 2, 1, 4, 5, 2, 3, 4, 5

のとき，ページを置き換える回数の組合せとして適切なものはどれか。

出典：平成29年春期　問19

👉 イ

実記憶に最初に割当てられるのは、「1,3,2」の3つ。次に1を参照したいときは、すでに実記憶にあるページを参照したいので、問題ないのですが、次の4を参照したい時、実記憶にはないページなので、ページフォルトが発生します。

ページ置き換えを行います。

FIFO 👉 First In First Out 「最初に入れたものを最初に出す」アルゴリズムなので、4をページインするときは、最初から入っている1をページアウトして、4を入れます。 ・・・切り替え①

5を参照したい時。実記憶に入っているのは、「3,2,4」の3つ。一番最初にいる3をページアウトの、5をページイン。・・・切り替え②。

次の2を参照したい時。実記憶に入っているのは。「2,4,5」なので問題なく参照できる。
次の3を参照したい時。一番最初から入っている、2をページアウトの、3をページイン。実記憶は「4,5,3」。・・・切り替え③

次の4を参照する時、と5を参照するときは、実記憶にあるページの参照なので、問題なく参照できる。よってFIFOのアルゴリズムなら、ページの切り替えは3回。

続いて、LRUのアルゴリズムでのページの切り替え。

LRU方式 👉 最後に参照されてから一番時間が経過しているページのデータを追い出す方式。

よって、4を参照する時。「1,3,2」の中で一番時間が経過しているのは 3 なので、3 をページアウトの4をページイン。・・・切り替え① 実記憶の中は「1,2,4」。

次5を参照 👉 実記憶にないので一番時間が経過している 2 と置き換え。 ・・・② 実記憶の中は「1,4,5」

次2を参照 👉 実記憶にないので一番時間が経過している 1 と置き換え。 ・・・③ 実記憶の中は「4,5,2」

次3を参照 👉 実記憶にないので一番時間が経過している 4 と置き換え。・・・④ 実記憶の中は「5,2,3」

次4を参照 👉 実記憶にないので一番時間が経過している 5 と置き換え。・・・⑤ 実記憶野中は「2,3,4」

次5を参照 👉 実記憶にないので一番時間が経過している 2 と置き換え。・・・⑥

よって置き換えの回数は 6 回。よって答えはイ。

まとめ

今回はメモリ管理の中でも仮想記憶システムについての問題を解けるように、用語の意味の解説と、ページの置き換えのイメージを固めてもらえるように解説していきました。

当サイトでは他にも、頻出問題の解説をしています。ぜひ合格に役立ててください！