ページング方式とは？＆ページ置き換えアルゴリズムの種類【備忘録-基本情報技術者試験対策 #53】

※ 本記事では、基本情報技術者試験の対策として私が勉強したことを備忘録的にまとめておきたいと思います。
少しでも参考になれば嬉しいです。

はじめに

さて今回は、基本情報技術者試験対策として、ページング方式とページ置き換えのアルゴリズムについてまとめたいと思います。

仮想記憶の実装方式には、仮想のアドレス空間を固定長の領域に区切って管理する「ページング方式」と、可変長の領域に区切って管理する「セグメント方式」の2つがあります。

今回ご紹介するのは「ページング方式」です。（「セグメント方式」は気が向いたらまとめますね・・・）

仮想記憶とは何？？みたいなところと合わせて覚えておくようにしましょう。

特に、ページ置き換えアルゴリズムはよく問われる問題なので必ず覚えておくようにしましょう。まぁ英語の頭文字からある程度想像できるんですけどね・・・。

それでは見ていきましょう！

ちなみに私はこの参考書を使って勉強してました。

漫画形式で読みやすく、分かりやすい内容になっているため、無理なく学習を進められると思います。

過去問を解きまくり、不明点があれば参考書で知識を補う、このサイクルで試験対策するのが私のオススメです！

最新版はこちらです。

少し内容が異なる部分もあるかもしれませんが、大まかには変わらないはずですので、安心して下さい。

ページング方式

ページング方式とは、プログラムやデータを「ページ」と呼ばれる固定サイズのブロックに分割し、それを「ページフレーム」として主記憶装置に割り当てる方式です。プログラムが動作する際、必要なページだけを主記憶装置にロードし、残りは補助記憶装置（例えばハードディスク）に保存されます。これにより、主記憶装置の容量が物理的に制限されていても、より大きなプログラムを実行できるようになります。

ページング方式は、以下のステップで動作します。

• プログラムの分割：
  プログラムやデータを固定サイズのページに分割します。このページサイズは通常4KBや8KBです。

• ページテーブルの作成：
  各ページがどのページフレームに割り当てられるかを管理するためのページテーブルを作成します。ページテーブルは主記憶装置と補助記憶装置の間で、ページがどこにあるかを追跡します。

• メモリ変換ユニット (MMU) の利用：
  MMUは、仮想アドレスを物理アドレスに変換する役割を担います。プログラムが仮想アドレスを指定すると、MMUがページテーブルを参照し、対応する物理アドレスを計算します。

• 動的アドレス変換機構 (DAT)：
  ページング方式において、仮想アドレスから物理アドレスへの変換はリアルタイムで行われます。これを動的アドレス変換機構（DAT）と呼びます。DATにより、プログラムは仮想アドレスを用いて実行され、主記憶装置の物理アドレスに直接依存しない形で処理されます。

• ページフォールトの処理：
  プログラムが必要とするページが主記憶装置に存在しない場合、ページフォールトが発生します。これにより、補助記憶装置から該当ページを読み込み、主記憶装置にロードするプロセスが開始されます。

ページ置き換えアルゴリズム

ページ置き換えアルゴリズムは主に4種類ありますが、よく問われるので必ず覚えておくようにしましょう！

FIFO（First In First Out）方式

最初にページイン（First In）したページを最初にページアウト（First Out）対象とする方式です。

LIFO（Last In First Out）方式

最後にページイン（Last In）したページを最初にページアウト（First Out）対象とする方式です。

LRU（Least Recently Used）方式

最も長い間参照されていないページ（Least Recently Used）をページアウト対象とする方式です。

「Least」は「最も少ない、最少の」、「Recently」は「最近」、「Used」は「使われた」的な意味合いです。直訳イメージだと、「最近使われていない」的な感じですかね。

LFU（Least Frequently Used）方式

最も参照回数の少ないページ（Least Frequently Used）をページアウト対象とする方式です。

「Frequently」は「頻出」的な意味合いです。直訳イメージだと、「最も頻出していない」的な感じですかね。

ページングとスワッピング

さて、ここ数回では、主記憶装置と補助記憶装置の中身を出し入れする話をしてきました。詳細まできっちりと読んでくださっている方なら気づくと思いますが、以前「スワッピング」という話をしたのを覚えていますでしょうか？？あれも補助記憶装置から出し入れする話でしたが、今回ご紹介したページングも同様の内容です。となると気になるのはそれぞれの違いですよね。まぁ大した話はないのですが、念のためおさえておいてください。

• ページング：ページ単位で領域の出し入れ

• スワッピング：プロセス単位で領域の出し入れ

最後に

さて今回は、基本情報技術者試験対策として、ページング方式とページ置き換えのアルゴリズムについてまとめました。

何度も言っていますが、特にページ置き換えアルゴリズムは頻出ですので、しっかりと違いを理解しておくようにしましょう！

以上！

前回まとめた記事も読んでもらえると嬉しいです！

基本情報以外の勉強記事も是非！

オススメ参考書 & Udemy講座

過去問編

兎にも角にも過去問を解かないことには始まりません。解いて解いて解きまくりましょう！

特に以下の参考書は問題数が多いのでオススメです。

この1冊だけ買って、とりあえず1周すれば合格がかなり近くなると思います！

科目A+B両方合わせて4セット収録されてるとかヤバすぎます・・・

知識網羅編

以下は知識網羅編として、講義系の参考書、動画をピックアップしています。

1からしっかりと学習し、知識を身に着けたい方はとてもオススメです。

過去問を解きまくり、不明点を参考書で補う。これが最高の勉強サイクルです～

私が勉強する際に使用していたオススメ参考書は以下です。

上記シリーズの最新版は以下です。（内容はそこまで変わらないはずですが・・・）

私がぜひオススメしたい、Udemyの講座もいくつかピックアップしておきます。

誰かに解説してもらった方が分かりやすい場合もありますからね～

画像でもボタンでも、どちらを押下しても講座へ飛べるようにしてありますので是非！