午後問題の歩き方 | 午後問題の読み方~ソフトウェア


2020-03-04 更新

ソフトウェアの午後問題のテーマは、

  • 「 OS 」
  • 「コンパイラ」
  • 「その他」

に大きく分類できます。

これらの中で OS に関する問題がよく出題されるので、過去問題をよく練習しておきましょう。

ここでは、例として、平成 25 年度 春期 午後 問 2「仮想記憶方式」を紹介します。仮想記憶は、OS の機能のひとつです。

error 本記事ではわかりやすいよう、問題に記号を入れています

長々とした説明と難しそうな図にまどわされるな

以下は、問題の冒頭部分です。長々とした説明と、いかにも難しそうな図が示されています。

午後問題の問 2 ~問 7 は、選択問題( 6 問中 4 問選択)です。

はたして、皆さんは、この説明と図を見て、この問題を選択するでしょうか。おそらく、しないでしょう。

しかし、それは誤った判断です。

実は、この問題は、あとで設問を見ればわかりますが、とっても簡単なのです。この説明と図を見なくても解けます。

問 2 仮想記憶方式に関する次の記述を読んで,設問 1 ~ 3 に答えよ。

 OS の主記憶管理において,仮想記憶方式は, OS が提供する論理的な記憶領域 (以下,仮想記憶という) 上のアドレスと主記憶上の物理的なアドレスを対応付けて管理する方式である。仮想記憶方式では,補助記憶装置を仮想記憶として用いるので,仮想記憶上に主記憶の容量を超えるプログラムを格納することができる。仮想記憶上のアドレス空間を仮想アドレス空間,主記憶上のアドレス空間を物理アドレス空間と呼び,それぞれの空間の記憶場所を仮想アドレスと物理アドレスで指定する。

 仮想記憶方式の一つに,ページング方式がある。ページング方式は,仮想アドレス空間と物理アドレス空間のそれぞれをページと呼ぶ固定長の領域に分割しておき,ページ単位でアドレス空間を管理する。ページング方式による仮想アドレス空間のページと物理アドレス空間のページの対応例を,図 1 に示す。図 1 では,補助記憶装置に格納されているプログラム A は a1 , a2 , a3 , a4 , a5 に分割されて,仮想ページ番号 1 ~ 5 のページに格納されている。

 仮想アドレス空間及び物理アドレス空間の各ページには,先頭から順に番号を付け,それぞれを仮想ページ番号,物理ページ番号と呼ぶ。仮想ページと物理ページの対応は,ページテーブルで管理する。ページテーブルの要素の個数は仮想ページの個数と同じであり,各要素が仮想ページの 1 ページに対応している。ページテーブルでは,仮想ページの内容が物理アドレス空間にも存在しているかどうかを示すビット (以下,存在ビットという) と物理ページ番号が管理されている。存在ビットは,ページが存在しているとき 1 ,存在していないとき 0 とする。

それでは、なぜ、問題の冒頭に、長々とした説明と難しそうな図があるのでしょうか。

仮想記憶には、様々な形式があるので、単に「仮想記憶において、以下の設問に答えよ」という問題では、あとで受験者から「どういう形式の仮想記憶を想定しているかによって、答えが違ってくるので、この問題は解けないじゃない!」というクレームが来てしまう かもしれないからです。

もしも、筆者が出題者だったら「ごく普通に基本情報技術者試験の勉強をされた皆さんがご存知の仮想記憶において」という前置きにしますが、実際の試験の出題者は、そんなくだけたことを書けませんので、長々とした説明と難しそうな図があるのです(これは、筆者の推測です)。

先に選択肢を見れば、落ち着いて正解を選べる

冒頭の長々とした説明と難しそうな図は気にしないで、設問 1 を見てみましょう。

ここにも、問題解法のポイントがあります。それは、設問の文章よりも、選択肢に注目することです。

設問の文章は、長々とした説明になっていて難しそうに見える場合がありますが、選択肢を見ると、「な~んだ、自分の知っている言葉ばかりじゃないか!」ということがよくあります。

ですから、まず選択肢を見て、それから設問の文書を読めば、落ち着いて正解を選ぶことができます。

 

以下は、実際の試験問題と同じに「設問の文書」→「選択肢の順」に並べたものです。これは、ちょっと難しい感じがするでしょう。

 プログラムの実行過程で存在ビットを調べプログラムの実行に必要なページが   a   に存在していないときには,ページフォールトという割込みが発生する。ページフォールトが発生すると,ページアウトやページインなどのページ置換え処理が実行される。ページ置換え処理のアルゴリズムには,ページインしてから最も時間が経過しているページを置換え対象とする FIFO アルゴリズムや,参照されていない時間が最も長いページを置換え対象とする。   b   アルゴリズムなどがある。

設問 1

次の記述中の       に入れる正しい答えを,解答群の中から選べ。

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

以下は、実験的に「選択肢」→「設問の文章」の順に並べたものです。

さっきより、簡単になったように感じませんか。問題を解くときには、、選択肢 → 設問の文書 の順に見ることをオススメします。

設問 1

次の記述中の       に入れる正しい答えを,解答群の中から選べ。

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

(設問の文章)
 プログラムの実行過程で存在ビットを調べプログラムの実行に必要なページが   a   に存在していないときには,ページフォールトという割込みが発生する。ページフォールトが発生すると,ページアウトやページインなどのページ置換え処理が実行される。ページ置換え処理のアルゴリズムには,ページインしてから最も時間が経過しているページを置換え対象とする FIFO アルゴリズムや,参照されていない時間が最も長いページを置換え対象とする。   b   アルゴリズムなどがある。

仮想記憶では、プログラムを「ページ」と呼ばれる固定サイズに区切り、実行に必要なページを「物理メモリ(電子的なメモリ)」に置きます。必要なページが実メモリに存在しないことを「ページフォルト( page fault )」と呼びます。

したがって、空欄 a に入るのは、選択肢オの「物理アドレス空間」です。

PR

3 点セットで覚えてほしい FIFO、LRU、LFU

今度は、設問 1 の空欄 b です。

ページフォルトが生じたときには、物理メモリに置かれたページの中で、今後使われる可能性が最も低いページを、「仮想メモリ(ハードディスク)」に書き込んで(ページアウト)から、必要なページを物理メモリに読み込み(ページイン)します。

今後使われる可能性が最も低いページを判断する方法には、「 FIFO 」「 LRU 」「 LFU 」の3つがあり、これらを「ページ置換えアルゴリズム」と呼びます。

 

ページ置換えアルゴリズムは、午前問題でとてもよく出題されています。

筆者は、独自に「よく出る問題と用語 Top 100」を調べたことがあるのですが、ページ置換えアルゴリズムの中の LRU は、Top 10 に入っています。

この問題の答えも、LRU(選択肢ウ)です。

 

FIFO 、LRU 、LFU は、3 点セットで覚えてください。略語のままではなく、略語の意味を調べて、日本語に訳して覚えましょう。

FIFO = First In First Out

最初にページインしたページを最初にページアウトする。

LRU = Least Recently Used

最も最近に使われていないページをページアウトする(最後に使われてから最も時間が経過しているページをページアウトする)

LFU = Least Frequently Used

最も頻繁に使われていないページをページアウトする(使われた回数が最も少ないページをページアウトする)

label 関連タグ: FIFO LRU LFU

処理の順番を問う問題は、消去法でやればいい

設問 2 は、ページフォルトが発生したときに、どのような順序でページの置き換え(ページアウトとページイン)が行われるかという問題です。この問題を見て、どう思いますか?

「そんなの知らないよ!」と思うでしょう。筆者も、同じです。

でも、大丈夫です。知らなくても、常識的な判断で正解できます。

設問 2

プログラム A を実行するために割り当てられた物理アドレス空間の物理ページの個数が 3 の場合を考える。プログラム A の実行過程において,物理アドレス空間に a1, a2, a3 が存在している状態で a4 を参照するとページフォールトが発生する。このページフォールトが発生した後の処理の流れとして適切な答えを,解答群の中から選べ。ここで,解答群中の処理は左から右に向かって行うものとする。

【処理の単位】

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

解答群
ア ①→②→③→④→⑤→⑥  
イ ①→③→②→④→⑦→⑤
ウ ②→①→④→③→⑤→⑥  
工 ②→①→④→③→⑦→⑤
オ ②→③→①→④→⑤→⑥  
力 ②→③→⑤→⑥→①→④

処理の順番を問う問題は、選択肢の違いに注目して「これば違う」と判断できたものを消して行けばよい のです。つまり消去法です。

 

選択肢には、1 番目の手順が ①(ページアウトする)のものと、②(ページアウトするページを決定する)のもの があります。

常識的に考えて、ページアウトするページを決定しなければ、ページアウトできないはずですから、1 番目の手順が ① の選択肢に clear を付けて消去します。

解答群

clearア①→②→③→④→⑤→⑥  
clearイ①→③→②→④→⑦→⑤
ウ ②→①→④→③→⑤→⑥  
工 ②→①→④→③→⑦→⑤
オ ②→③→①→④→⑤→⑥  
力 ②→③→⑤→⑥→①→④

残った選択肢には、2 番目の手順が ①(ページアウトする)のものと、③(ページインする)のもの があります。

常識的に考えて、ページアウトしてページを空けないとページインできないはずですから、2 番目の手順が ③ の選択肢に clear を付けて消去します。

解答群

clearア①→②→③→④→⑤→⑥  
clearイ①→③→②→④→⑦→⑤
ウ ②→①→④→③→⑤→⑥  
工 ②→①→④→③→⑦→⑤
clearオ ②→③→①→④→⑤→⑥  
clear力 ②→③→⑤→⑥→①→④

残った選択肢は、ウとエです。

両者は、②(ページアウトするページを決定する)→ ①(ページアウトする)→ ④(ページアウトしたページの存在ビットを 0 にする)→ ③(ページインする)まで同じ です。

その後は、

選択肢ウでは、⑤(ページインしたページの存在ビットを1にする)→ ⑥(ページアウトしたページの物理ページ番号を設定する)です。

選択肢エ では、⑦(ページインしたページの物理ページ番号を設定する)→ ⑤(ページインしたページの存在ビットを 1 にする)です。

 

ここは、ちょっと悩むかもしれませんが、常識的に考えてください。

ページアウトしたページは、もはや物理メモリには存在していないのです。

したがって、手順の中に ⑥(ページアウトしたページの物理ページ番号を設定する)がある選択肢ウは、不適切であるとわかります。

残った選択肢エが正解です。

label 関連タグ: 消去法のやり方

コツコツと解く問題も練習しておこう

最後の設問 3 は、「 FIFO( First In First Out )のページ置換えアルゴリズムで、物理ページが 3 の場合と 4 の場合において、それぞれページフォルトが何回発生するか実際にやってみよ」という問題です。

この手の問題は、絵を描いてコツコツと解くしかありません。ひたすら練習あるのみです。

実際の試験の前に、この手の問題に遭遇できたことをラッキーだと思って、丁寧に練習してください。

設問 3

次の記述中の       に入れる正しい答えを,解答群の中から選べ。

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

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

解答群

ア 8  イ 9  ゥ 10  ェ 11  オ 12

物理ページが 3 の場合は、以下のようになります。ここでは、[ ]でページを示しています。

ページフォルト(参照するページがないので、ページインする)は、全部で 10 回なので、空欄 c はウです。

[ ] [ ] [ ] 初期状態
[1] [ ] [ ] 1 を参照(ページフォルト)
[1] [4] [ ] 4 を参照(ページフォルト)
[1] [4] [3] 3 を参照(ページフォルト)
[2] [4] [3] 2 を参照(ページフォルト)
[2] [1] [3] 1 を参照(ページフォルト)
[2] [1] [4] 4 を参照(ページフォルト)
[5] [1] [4] 5 を参照(ページフォルト)
[5] [1] [4] 1 を参照
[5] [1] [4] 4 を参照
[5] [3] [4] 3 を参照(ページフォルト)
[5] [3] [2] 2 を参照(ページフォルト)
[5] [3] [2] 5 を参照
[1] [3] [2] 1 を参照(ページフォルト)

物理ページが 4 の場合は、以下のようになります。ページフォルトは、全部で 11 回なので、空欄 d はエです。

[ ] [ ] [ ] [ ] 初期状態
[1] [ ] [ ] [ ] 1 を参照(ページフォルト)
[1] [4] [ ] [ ] 4 を参照(ページフォルト)
[1] [4] [3] [ ] 3 を参照(ページフォルト)
[1] [4] [3] [2] 2 を参照(ページフォルト)
[1] [4] [3] [2] 1 を参照
[1] [4] [3] [2] 4 を参照
[5] [4] [3] [2] 5 を参照(ページフォルト)
[5] [1] [3] [2] 1 を参照(ページフォルト)
[5] [1] [4] [2] 4 を参照(ページフォルト)
[5] [1] [4] [3] 3 を参照(ページフォルト)
[2] [1] [4] [3] 2 を参照(ページフォルト)
[2] [5] [4] [3] 5 を参照(ページフォルト)
[2] [5] [1] [3] 1 を参照(ページフォルト)

午後問題の多くは、常識的な判断で解けます。そして、常識的な知識は、午前問題の学習によって得られます。

もしも、午後問題で苦手な分野があるなら、その分野の午前問題を数多く解いてください。きっと、苦手を克服できるはずです。

それではまた、お会いしましょう!

 

label 関連タグ
実は、午前試験を『免除』できます 独習ゼミで午前免除試験を受けた 86% の方が、
午前試験を免除しています。
今なら最大 2 回の
午前免除チャンス
info_outline
今なら最大 2 回の
午前免除チャンス
詳しく見てみるplay_circle_filled
label これまでの『午後問題の歩き方』の連載一覧 label 著者

『プログラムはなぜ動くのか』(日経BP)が大ベストセラー
IT技術を楽しく・分かりやすく教える“自称ソフトウェア芸人”

大手電気メーカーでPCの製造、ソフトハウスでプログラマを経験。独立後、現在はアプリケーションの開発と販売に従事。その傍ら、書籍・雑誌の執筆、またセミナー講師として活躍。軽快な口調で、知識0ベースのITエンジニアや一般書店フェアなどの一般的なPCユーザの講習ではダントツの評価。
お客様の満足を何よりも大切にし、わかりやすい、のせるのが上手い自称ソフトウェア芸人。

主な著作物

  • 「プログラムはなぜ動くのか」(日経BP)
  • 「コンピュータはなぜ動くのか」(日経BP)
  • 「出るとこだけ! 基本情報技術者」 (翔泳社)
  • 「ベテランが丁寧に教えてくれる ハードウェアの知識と実務」(翔泳社)
  • 「ifとelseの思考術」(ソフトバンククリエイティブ) など多数