カテゴリ:4.記憶管理 > 4.2.2 記憶管理(仮想記憶管理)

 1.仮想記憶管理とは

応用情報技術者試験のシラバスでは、コンピュータシステム>ソフトウェア>オペレーティングシステム の中に「記憶管理」の章があります。
シラバスには次の記載があります。
② 仮想記憶管理
実記憶と仮想記憶の関係,仮想記憶の有効性,仮想記憶方式の種類と特徴,動的アドレス変換の仕組みを理解する。また,ページング方式の代表的なページ置換えアルゴリズムについて,ページ置換え手順を理解する。

用語例 ベースアドレス方式,セグメント方式,セグメントページング方式,単一仮想空間方式, 多重仮想空間方式, スラッシング, DAT ( Dynamic Address Translator:動的アドレス変換),TLB(Translation ookaside Buffer),ページフォールト,ページイン,ページアウト,デマンドページング,ページリプレースメント,LRU,FIFO,ワーキングセット
スワッピングとオーバレイによる主記憶管理よりも、効率的な記憶管理方法が仮想記憶管理です。
具体的には、補助記憶を利用し、主記憶を大容量に見せます。過去問(H21春シスアド問7)では、「仮想記憶方式が主記憶に及ぼす効果」に関して、「主記憶の見掛け上の容量が増加する」とあります。
応用情報技術者試験を勉強する成子 

スワッピングとオーバレイではダメなのですか?
たとえば、スワッピングであれば、プログラムを補助記憶に退避させます。
でも、メインメモリよりも大きなプログラムを使う場合、どうしようもないですよね。
仮想記憶
主記憶の領域を増やせればいいのですが、お金もかかることから、実際にはそう簡単にはいきません。
そこで、仮想記憶です。実際の主記憶領域よりも、仮想的に大きな領域があるように、CPUに見せるのです。
以下、イメージです。
補助記憶
仮想記憶では、主記憶以上の領域を、CPUに見せます。しかし、実際には主記憶の領域が限られています。そこで、補助記憶装置(HDD)の領域を使って仮想記憶を実現します。
このとき、上記のように、仮想記憶の領域と主記憶の領域を、一定の単位で管理するのが便利です。これが、後述するページング方式です。

過去問(H21秋IP問59)では、「OSの機能の一つである仮想記憶方式の目的」として、「主記憶の容量よりも大きなメモリを必要とするプログラムも実行できるようにする」とあります。
応用情報技術者試験を勉強する成子 


OSの機能なんですね。
はい、そうです。実際、Windowsでも自動で処理を行っています。
システムのプロパティ>詳細設定>パフォーマンス>詳細設定>仮想メモリ
で設定できます。
デフォルトでは、コンピュータによる自動管理がなされています。
仮想メモリ

 

 

2.ページング方式

仮想記憶を実現する一つの方式が、ページング方式です。他にもセグメント方式などもありますが、覚える必要はありません。試験では、ページング方式のみを覚えてください。
ページングに関して過去問(H20秋SW午前問27)では、「主記憶とプログラムを固定長の単位に分割し,効率よく記憶管理する。これによって,少ない主記憶で大きなプログラムの実行を可能にする。」とあります。
応用情報技術者試験を勉強する成子 

ちょっと分かりにくいです。
そうですね。
別の過去問(H25春FE午後問2)の説明を見てみましょう。
「仮想記憶方式の一つに,ページング方式がある。ページング方式は,仮想アドレス空間と物理アドレス空間のそれぞれをページと呼ぶ固定長の領域に分割しておき,ページ単位でアドレス空間を管理する。」とあります。
この過去問の図を見てみましょう。
仮装記憶
このように、仮想記憶と主記憶のアドレス空間を、固定長のページという単位で管理します。
応用情報技術者試験を勉強する成子 

でも、主記憶だけでは領域が足らないんですよね。
はい、そうです。だから、補助記憶装置の領域も借りる必要があります。具体的には、まず、ページが主記憶装置に割り当てられていないときにはOSに対してページフォルトの割り込みを発生させます。そして、必要なページを補助記憶装置から持ってきます(ページイン)。このとき、主記憶領域がいっぱいではいけませんので、不要なページを補助記憶に退避します(ページアウト)。
応用情報技術者試験を勉強する成子

不要なページはどういう基準で決めるのですか?
いい質問ですね。ページアウトするページを決める方法にはいくつかあり、FIFOやLRUなどがあります。詳しくは後述します。

では、別の過去問をみてみましょう。
■H20秋FE午前
問27 ページング方式の仮想記憶において,主記憶に存在しないページをアクセスした場合の処理や状態の順番として,適切なものはどれか。ここで,主記憶には現在,空きのページ枠はないものとする。
ア 置換え対象ページの決定→ページイン→ページフォールト→ページアウト
イ 置換え対象ページの決定→ページフォールト→ページアウト→ページイン
ウ ページフォールト→置換え対象ページの決定→ページアウト→ページイン
エ ページフォールト→置換え対象ページの決定→ページイン→ページアウト




正解:ウ

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

ページング方式の代表的なページ置換えアルゴリズムには以下の4つがあります。よく問われるのはLRUです。
①FIFO(First In First Out):先入れ先出し法。過去問(H24春FE午前問22不正解選択肢)では、「最も古くから存在するページを置き換える方式」とあります。
②LIFO(Last In First Out):後入れ先出し法。最も新しいページを置き換える方法です。
③LFU(Least Frequently Used):Frequentlyは「頻繁に」という意味です。過去問(H24春FE午前問22不正解選択肢)では、「最も参照回数の少ないページを置き換える方式」とあります。
④LRU(Least Recently Used):Recently は「最近」という意味で、Least Recentlyなので、「最近ではない」という意味になります。過去問(H24春FE午前問22不正解選択肢)では、「最後に参照されてからの経過時間が最も長いページを置き換える方式」とあります。

4.仮想記憶に関する過去問(午前問題)

(1)H29春AP

問16 4ブロックのキャッシュメモリC0~C3が表に示す状態である。ここで,新たに別のブロックの内容をキャッシュメモリにロードする必要が生じたとき,C2のブロックを置換の対象とするアルゴリズムはどれか。
H29h-問16
ア FIFO     イ LFU     ウ LIFO     エ LRU

【解説】
ページ置換えアルゴリズムには、主に選択肢の4つがあります。
この中で、C2を置き換えるには「最終参照時刻が最も遅い」ことに着目します。
最も使っていないと言う意味で、LRU(選択肢エ)が正解です。
参考ですが、それぞれの選択肢ではどれが置き換えられるでしょうか。
ア:FIFO⇒ロード時間が最も早いC0です。
イ:LFU⇒最も使われてないC1です。
ウ:LIFO→もっとも後にロードされたC3です。

【正解】エ

(2)H28春AP午前

問18 仮想記憶方式に関する記述のうち,適切なものはどれか。
ア LRUアルゴリズムは,使用後の経過時間が最長のページを置換対象とするページ置換アルゴリズムである。
イ アドレス変換をインデックス方式で行う場合は,主記憶に存在する全ページ分のページテーブルが必要になる。
ウ ページフォールトが発生した場合は,ガーベジコレクションが必要である。
エ ページングが繰り返されるうちに多数の小さな空きメモリ領域が発生することを,フラグメンテーションという。

⇒正解は、ア
エですが、ページングはページ単位で記憶領域を管理するため、小さな空きメモリ領域が発生しません。

問17 仮想記憶管理のページ入替え方式のうち,最後に使われてからの経過時間が最も長いページを入れ替えるものはどれか。
ア FIFO  イ LFU  ウ LIFO 工 LRU

⇒正解は、エのLRU(Least Recently Used)です。

(3)H25春AP午前
問19 仮想記憶方式におけるプログラムやデータの格納方法に関する記述のうち,適切なものはどれか。
ア 一つのプログラムや一連のデータは,主記憶装置及び補助記憶装置で必ず連続した領域に格納される。
イ 頻繁に参照されるプログラムやデータが主記憶装置に格納されているので,仮想記憶を用いない場合に比べて主記憶の平均アクセス時間が短くなる。
ウ プログラムやデータを補助記憶装置に格納し,必要に応じて主記憶に読み込むので,主記憶の見かけの容量を拡大できる。
エ ページアウトされたプログラムやデータがシステムの停止後も補助記憶装置に保持されるので,再起動後に主記憶の内容が復元される。

⇒正解はウです。

(4)H19春FE午前
問28 仮想記憶方式の一つに,仮想アドレス空間を固定長の領域に分割して管理するものがある。この固定長の領域を示す用語はどれか。
ア セクタ  イ セグメント  ウ フレーム  エ ページ
⇒正解はエ

(5)H26春AP午前
問18 仮想記憶方式において,論理アドレスから物理アドレスへの変換を行うのはいつか。
ア 主記憶に存在するページをアクセスするとき
イ ページフォールドが発生したとき
ウ ページを主記憶にページインするとき
エ ページを補助記憶にページアウトするとき

⇒正解は、ア

(6)H17春SW午前
問26 仮想記憶方式において,仮想アドレスと物理アドレスとを対応付けるアドレス変換機能に付加情報を与えることで,実現が容易になるものはどれか。
ア オーバレイ      ウ メモリインタリーブ
イ 記憶保護       エ メモリコンパクション

⇒正解は、イ

(7)平成28年秋期 午前 問18
問18 プログラムで使用可能な実メモリ枠が3ページである仮想記憶システムにおいて大きさ6ページのプログラムが実行されたとき,ページフォールトは何回発生するか。ここで,プログラム実行時のページ読込み順序は, 0,1,2, 3,4,0,2,4,3,1,4,5とする。ページング方式は,LRU (Least Recently Used)とし,初期状態では,実メモリにはいずれのページも読み込まれていないものとする。
ア 9   イ 10   ウ 11   エ 12



正解は、イです。

問2 仮想記憶方式に関する次の記述を読んで,設問1~3に答えよ。
 OSの主記憶管理において,仮想記憶方式は,OSが提供する論理的な記憶領域(以下,仮想記憶という)上のアドレスと主記憶上の物理的なアドレスを対応付けて管理する方式である。仮想記憶方式では,補助記憶装置を仮想記憶として用いるので,仮想記憶上に主記憶の容量を超えるプログラムを格納することができる。仮想記憶上のアドレス空間を仮想アドレス空間,主記憶上のアドレス空間物理アドレス空間と呼び,それぞれの空間の記憶場所を仮想アドレスと物理アドレスで指定する。
 仮想記憶方式の一つに,ページング方式がある。ページング方式は,仮想アドレス空間物理アドレス空間のそれぞれをページと呼ぶ固定長の領域に分割しておき,ページ単位でアドレス空間を管理する。ページング方式による仮想アドレス空間のページと物理アドレス空間のページの対応例を,図1に示す。図1では,補助記憶装置に格納されているプログラムAはa1, a2, a3, a4, a5に分割されて,仮想ページ番号1~5のページに格納されている。
 
仮装記憶

 仮想アドレス空間及び物理アドレス空間の各ページには,先頭から順に番号を付け,それぞれを仮想ページ番号,物理ページ番号と呼ぶ。仮想ページと物理ページの対応は,ページテーブルで管理する。ページテーブルの要素の個数は仮想ページの個数と同じであり,各要素が仮想ページの1ページに対応している。ページテーブルでは,仮想ページの内容が物理アドレス空間にも存在しているかどうかを示すビット(以下,存在ビットという)と物理ページ番号が管理されている。存在ビットは,ページが存在しているとき1,存在していないとき0とする。
 
設問1 次の記述中の[  ]に入れる正しい答えを,解答群の中から選べ。
 プログラムの実行過程で存在ビットを調べ,プログラムの実行に必要なページが[ a ]に存在していないときには,ページフォールドという割込みが発生する。ページフォールドが発生すると,ページアウトやページインなどのページ置換え処理が実行される。ページ置換え処理のアルゴリズムには,ページインしてから最も時間が経過しているページを置換え対象とするFIFOアルゴリズムや,参照されていない時間が最も長いページを置換え対象とする[ a ]アルゴリズムなどがある。

解答群
 ア LFU  イ LIFO  ウ LRU 
 工 仮想アドレス空間  オ 物理アドレス空間

設問2 プログラムAを実行するために割り当てられた物理アドレス空間の物理ページの個数が3の場合を考える。プログラムAの実行過程において,物理アドレス空間にal, a2, a3が存在している状態でa4を参照するとページフォールドが発生する。このページフォールドが発生した後の処理の流れとして適切な答えを,解答群の中から選べ。ここで,解答群中の処理は左から右に向かって行うものとする。
【処理の単位】
① 退避させるページをページアウトする。
② ページ置換えアルゴリズムによって,物理アドレス空間からページアウトするページを決定する。
③ 実行に必要なページをページインする。
④ ページアウトしたページに対応するページテーブルの要素の存在ビットを0にする。
⑤ ページインしたページに対応するページテーブルの要素の存在ビットを1にする。
⑥ ページアウトしたページに対応するページテーブルの要素の物理ページ番号を設定する。
⑦ ページインしたページに対応するページテーブルの要素の物理ページ番号を設定する。

解答群
ア ①→②→③→④→⑤→⑥
イ ①→③→②→④→⑦→⑤
ウ ②→①→④→③→⑤→⑥
エ ②→①→④→③→⑦→⑤
オ ②→③→①→④→⑤→⑥
カ ②→③→⑤→⑥→①→④

設問3 次の記述中の[  ]に入れる正しい答えを,解答群の中から選べ。
 ページ置換えアルゴリズムとしてFIFOアルゴリズムを採用する。プログラムの実行過程で仮想ページが次の順で参照されるとき,物理ページの個数が3の場合のページフォールドの回数は[ c ]回である。そして,物理ページの個数を4に増やした場合のページフォールドの回数は[ d ]回である。ここで,プログラムの実行開始時点では,物理アドレス空間にはどのページも存在していないものとする。

【仮想ページの参照順を示す仮想ページ番号の並び】
 1→4→3→2→1→4→5→1→4→3→2→5→1

解答群
 ア 8  イ 9  ウ 10  エ 11  オ 12
正解は、以下です。
設問1 a オ 物理アドレス空間
     b ウ LRU

設問2 エ 
② ページ置換えアルゴリズムによって,物理アドレス空間からページアウトするページを決定する。
① 退避させるページをページアウトする。
④ ページアウトしたページに対応するページテーブルの要素の存在ビットを0にする。
③ 実行に必要なページをページインする。
⑦ ページインしたページに対応するページテーブルの要素の物理ページ番号を設定する。
⑤ ページインしたページに対応するページテーブルの要素の存在ビットを1にする。

設問3
c ウ 10回
d エ 11回

スラッシングに関して過去問(H27春AP午前 問16)では、「仮想記憶方式では,割り当てられる実記憶の容量が小さいとページアウト,ページインが頻発し,スループットが急速に低下することがある。このような現象」と述べています。
スラッシング対策の最も分かりやすい方法は、メインメモリを追加購入して増やすことです。それ以外には、プログラムの多重度を下げることがあります。

■過去問(H18春SM午前 問26)
問26 システム運用部門がCPU利用率,ページフォールト頻度などを測定したところ,スラッシングの発生が多くなっていることが分かった。処理能力を改善するために運用部門だけでできる当面の対応処置として,適切なものはどれか。
ア 磁気ディスクの作業域(ワークエリア)の割当てを変更する。
イ ジョブの多重度を下げて,メモリの使用を抑制する。
ウ ページ置換方式を変更する。
エ 補助記憶装置を増設して,作業域を再配置する。

正解は、イ。

■H25春FE午前
問19 主記憶の管理方式とマルチプログラミングでのプログラムの多重度の組合せで,スラッシングが発生しやすいのはどれか。
a
⇒正解は、ア

基本情報技術者 平成15年 午前 問30
スラッシングが発生しているときの状態

・アプリケーションのCPU使用率:低い
・主記憶と補助記憶の間のページ転送量:多い

↑このページのトップヘ