応用情報処理技術者試験の対策サイトです。 応用情報処理技術者試験の午前問題を中心とした基礎用語の解説を中心に掲載します。書き始めたばかりなので、内容はまだまだ不十分です。
カテゴリ:

4.ソフトウェア

共通に使用される擬似言語の記述形式

 擬似言語を使用した問題では,各問題文中に注記がない限り,次の記述形式が適用されているものとする。

〔宣言,注釈及び処理〕
2009h21a_fe_pm_qs_1



〔演算子と優先順位〕
2009h21a_fe_pm_qs_2
注 整数同士の除算では,整数の商を結果として返す。%演算子は,剰余算を表す。

〔論理型の定数〕
true, false


タスク管理に関して、過去問(H20秋FE午前問28)では、「マルチプログラミングの制御を行い,CPUを有効に利用する」とあります。
応用情報技術者試験を勉強する成子

なぜそんな制御が必要なのですか?
CPUは頭脳に例えられるという話をしたと思います。
人間と同じで、コンピュータであっても、複数のことを同時には考えることができません。
応用情報技術者試験を勉強する成子

そうなんですか?
パソコンでは、インターネットで動画を見ながら、メールを書いたりしていますし、その間にプリンタで印刷をかけたりもできますけど。
はい、パソコンでは複数のことを同時に実施しています。
ただ実際には、CPUが短い時間で瞬時に複数の仕事を切り替えています。それがあまりに高速なので、我々には同時に実行しているように見えるのです。
このように、CPUにはいくつものジョブがやってきて、それを効率的に管理する仕事がOSが実行すべきタスク管理です。

タスク管理に関して、応用情報技術者試験のシラバスでは、以下の記載があります。
(4)タスク管理
タスクと状態遷移
タスクとジョブステップ,スレッドとの関係,タスクの生成から実行,消滅までの状態遷移,ディスパッチャの役割を理解する。

用語例 軽量プロセス,実行可能状態,実行状態,待ち状態,プロセス,スレッド

多重(マルチ)プログラミング(マルチタスク)とスケジューリング
多重(マルチ)プログラミングの考え方,タスクのスケジューリングの代表的な方式について,スケジューリングの方法,特徴,スケジューリングにおけるトリガと優先順位の役割,同期制御・排他制御の必要性,実現方法を理解する。また,タスクとタスクの同期,タスク間でのデータの受け渡し,マルチスレッドの考え方,並列処理などを理解する。

用語例 プリエンプティブ方式,ノンプリエンプティブ方式,タイムスライス方式,イベントドリブン方式,フィードバック待ち行列方式,処理時間順方式,優先順,静的優先順位方式,動的優先順位方式,ラウンドロビン,SJF(Short Job First),最短時間順,割込み禁止,マルチCPU,排他制御,FCFS(First Come First Served),タイムクウォンタム,リソーススタベーション,SVC(SuperVisorCall)割込み,入出力終了割込み,ディスパッチ

では、過去問(H20秋FE午前)を見てみましょう。
問28 タスク管理の役割として,適切なものはどれか
ア 各種の補助記憶装置へのアクセス手段を,装置に依存しない形態で提供し,応用プログラム作成の負担を軽減する。
イ 仮想記憶空間を提供し,実記憶を有効に利用する。
ウ 入出力装置の制御を行い,正確かつ効率よく入出力装置を動作させる。
エ マルチプログラミングの制御を行い,  CPUを有効に利用する。
正解は、エです。ウは入出力管理、イは記憶管理、アはデータ管理です。

過去問(H21秋AP午前問19)
問19 リアルタイムOSのマルチタスク管理機能において,タスクAが実行状態から実行可能状態へ遷移するのはどの場合か。
ア タスクAが入出力要求のシステムコールを発行した。
イ タスクAが優先度の低いタスクBに対して,メッセージ送信を行った。
ウ タスクAより優先度の高いタスクBが実行状態となった。
エ タスクAより優先度の高いタスクBが待ち状態となった。
正解は、 

プロセスの状態には、「待ち行列に登録されているプロセスの状態を実行可能状態,実行中のプロセスの状態を実行状態」の他に、「待ち状態」があります。

過去問(H20FE秋午前問29)では、コンピュータのタスクの状態遷移として、次の図が記載されています。
状態遷移
また、実行状態のタスクが、「自分より優先度の高いタスクが実行可能状態になった」ことで、実行可能状態に遷移するともあります。
応用情報技術者試験を勉強する成子

なんかややこしいですね。
なぜ、そんな3つの状態があるのですか?



例えがいいか分かりませんが、以下と考えてはどうでしょう。
大きな病院で初診受付をしたとします。
・最初は、病院側の先生が決っていない状態で、今すぐ診察を受けられない状態ですから、受付でしばらく待ちます(⇒待ち状態)
・病院側は、問診票や先生の空き状況などを踏まえて先生が決ったら、患者さんに連絡します「○○先生の診察になりますので、第△診察室の前でお待ちください。これで、先生が空いたら診察を受けることができます。(⇒実行可能状態)
・前の患者さんの診察が終わったら、診察を受けられます(⇒実行状態)
※ここで、実行状態にあっても、途中で検査したりすると、もう一度診察を受けるまで、診察室の前で待つことがあります。(⇒実行可能状態に戻ります)

患者さんの数に対し、先生の数は圧倒的に少ないものです。よって、患者さんの状態(優先度)も確認しながら、患者さんを先生に割り当てていく作業が必要になります。

コンピュータも同じで、CPUにはいくつものプロセスがやってきます。CPUの数は限られていますから、そのプロセスの実行順序を決めるのがOSの役割であり、これがタスク管理です。
また、プロセスの実行順序を決定する方式にはいくつかの方式があり、到着順方式や、ラウンドロビン方式、優先度順方式などがあります。

過去問
過去問(H21秋AP午前問19)
問19 リアルタイムOSのマルチタスク管理機能において,タスクAが実行状態から実行可能状態へ遷移するのはどの場合か。
ア タスクAが入出力要求のシステムコールを発行した。
イ タスクAが優先度の低いタスクBに対して,メッセージ送信を行った。
ウ タスクAより優先度の高いタスクBが実行状態となった。
エ タスクAより優先度の高いタスクBが待ち状態となった。
正解は、ウです。
優先度の高いタスクBが実行状態となると、タスクAは実行可能状態になります。

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

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

応用情報技術者試験を勉強する成子 


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

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


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

タスクのスケジューリング方式には、到着順方式、ラウンドロビン、優先度方式など、いくつかの方式があります。
到着順方式
到着順にタスクを実行状態にします。

処理時間順(残余処理時間順)方式
過去問(H27春FE午前問19不正解選択肢)では、「新しいタスクが実行可能状態になるたびに,各タスクの残りの実行時間を評価し,その時間が短いものから順に実行する」とあります。

ラウンドロビン
過去問(H27春FE午前問19不正解選択肢)では、「実行状態としたタスクが決められた時間内に待ち状態に遷移しないときに,そのタスクを中断して実行待ち行列にある次のタスクを実行状態とする」とあります。

優先度順
過去問(H27春FE午前問19不正解選択肢)では、「タスクが実行可能状態になったときに,そのタスクの優先度と,その時,実行状態であるタスクの優先度とを比較して,優先度が高い方のタスクを実行状態とする」とあります。

では、具体的な内容を過去問(H23春FE午後問2)で確認しましょう。
問2 CPUの割当て方式に関する次の記述を読んで,設問1,  2に答えよ。
オペレーティングシステムの役割の一つとして,プロセスにCPUを割り当てることがある。そして,プロセスの実行順序を決定する方式には,次のようなものがある。
(1)到着順方式
到着順にプロセスを待ち行列の末尾に登録する。実行中のプロセスが終了すると,待ち行列の先頭からプロセスを一つ取り出して実行を開始する。
到着順方式を図1に示す。待ち行列に登録されているプロセスの状態を実行可能状態,実行中のプロセスの状態を実行状態と呼ぶ。
プロセス
(2)ラウンドロビン方式
到着順にプロセスを待ち行列の末尾に登録する。実行中のプロセスが終了すると,待ち行列の先頭からプロセスを一つ取り出して実行を開始する。また,実行中のプロセスが一定時間(以下,タイムクウォンタムという)を経過したら,実行を中断して,待ち行列の末尾に再登録し,待ち行列の先頭からプロセスを一つ取り出して実行を開始する。
ラウンドロビン方式を図2に示す。
ラウンドロビン
これらの方式の効率を示す指標としてター'ンアラウンドタイムがある。ここで,ターンアラウンドタイムとは,プロセスが待ち行列に到着してから実行が終了するまでの時間であり,プロセスの実行順序に影響される。

(中略)

プロセスの実行順序を決める別の方式に優先度順方式がある。優先度順方式の例を図3に示す。プロセスにはあらかじめ優先度が付けてあり,待ち行列は優先度ごとに用意してある。ここで,優先度は1~10の10種類で,値の大きい方が優先度は高い。

優先度
この方式では,次のとおりにプロセスの実行を制御する。
プロセスを優先度に対応した待ち行列の末尾に登録する。
プロセスが登録されている優先度の最も高い待ち行列の先頭からプロセスを一つ取り出して実行を開始する。
実行中のプロセスの優先度が2以上のとき,実行時間が20ミリ秒経過するごとに優先度を一つ下げる。優先度を下げた結果,実行中のプロセスの優先度が実行可能状態にある優先度の最も高いプロセスよりも低くなった場合,実行中のプロセスを中断して,,北瓩襦
実行中のプロセスが終了した場合,△北瓩襦

問2 オーバレイに関する次の記述を読んで,設問1,2に答えよ。

 近年,組込み(embedded)システムに利用されるプログラムの規模拡大に伴い,オーバレイが必要になってきている。オーバレイとは,プログラムを幾つかのオーバレイセグメント(以下,単にセグメントと呼ぶ)に分割しておき,OSがプログラムの実行に必要なモジュールを含むセグメントだけを主記憶領域に読み込んで実行する方法である。
 (1)10個のモジュールA〜Jで構成されるプログラムがあり,各モジュールは図1に示す呼出し構造になっている。例えば,モジュールGは二つのモジュールH及びIを呼び出す。
17-FE問2-4
図1 モジュールの呼出し構造


 (2)このプログラムのモジュールの実行順序は,図2のとおりである。
17-FE問2-5
図2 モジュールの実行順序

 (3)A〜Jの各モジュールの実行に必要な主記憶領域の大きさは,表のとおりである。なお,セグメントの大きさは,セグメントを構成するモジュールの大きさを合計したものになる。

        表 モジュールの大きさ
モジュール
A
B
C
D
E
F
G
H
I
J
大きさ(Mバイト)
10
8
6
5
6
4
6
2
3
15


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

 プログラムのオーバレイ構造と各セグメントを構成するモジュールを図3に示す。図3は,モジュールDがモジュールAから呼び出されたとき,主記憶領域にセグメントP0及びP2が読み込まれていることを表している。また,セグメントP1,P2及びP3は,主記憶領域の同じ番地を先頭としてそれ以降に読み込まれることを表している。
17-FE問2-1
図3 オーバレイ構造とセグメント


 このプログラムを実行したとき,プログラムの実行が終了するまでに,セグメントはP0,P1,P2,P3の順に,計4回だけ主記憶領域に読み込まれる。図3のオーバレイ構造で実行するのに必要な主記憶領域は,[    ]Mバイトである。

解答群
ア 24   イ 25   ウ 35   エ 36
オ 37   カ 38   キ 39   ク 40
正解は、エです。

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

 プログラムの実行時に利用する主記憶領域を減らすことが必要になったので,オーバレイ構造及びセグメントの見直しを行って,図4と図5に示す二つの案を作成した。
17-FE問2-2
図4 オーバレイ構造とセグメント案1

17-FE問2-3

図5 オーバレイ構造とセグメント案2

 図3のオーバレイ構造に比べて,プログラムの実行時に利用する主記憶領域を,案1では10 Mバイト,案2では[  a  ]Mバイト減らすことができる。
 プログラムを実行したとき,図2中のαの位置にあるモジュールFの実行が終了するまでに主記憶領域にセグメントが読み込まれる回数は,案1では合計6回,案2では合計[  b  ]回である。
 プログラムの実行が終了するまでに主記憶領域にセグメントが読み込まれる回数は,図3のオーバレイ構造に比べて,案1では合計[  c  ]回,案2では合計6回増える。

aに関する解答群
ア 10   イ 11   ウ 12
エ 13   オ 14   カ 15

b,cに関する解答群
ア 1   イ 2   ウ 3   エ 4   オ 5
カ 6   キ 7   ク 8   ケ 9   コ 10
正解は、
a イ
b キ
c エ です。

応用情報技術者試験のシラバスでは、実記憶管理に関して、以下の記載があります。
実記憶管理
記憶領域の管理方式である固定区画方式,可変区画方式など,実アドレス空間の割当て方式の特徴,フラグメンテーションとその対策を理解する。また,主記憶装置を効率良く使うためのスワッピングとオーバレイを理解する。

用語例 実アドレス方式,単一連続割当て方式,記憶域管理アルゴリズム(ファーストフィット,ベストフィット,ワーストフィット),メモリコンパクション,ロールイン,ロールアウト,スワップイン,スワップアウト,セグメント方式,コンパクション
応用情報技術者試験を勉強する成子 

そもそも、「実記憶管理」ってどういう意味ですか?
CPUが頭脳で、メインメモリが机の上の作業場所に例える場合があります。
仕事をするときに、机の上の書類で作業するのですが、机の広さが足らない時がありませんか? 

その狭いスペース(メインメモリの領域)を効率良く使うための仕組みが実記憶管理です。
具体的には、スワッピングとオーバレイ、この後に記載する仮想記憶管理があります。

スワッピングに関して過去問(H20秋SW午前問27)では、「プログラムを一時的に停止させ,使用中の主記憶の内容を補助記憶に退避する。再開時には,退避した内容を主記憶に再ロードし,元の状態に戻す」とあります。

オーバレイに関して過去問(H20秋SW午前問27)では、「あらかじめプログラムを幾つかの単位に分けて補助記憶に格納しておき,プログラムの指定に基づいて主記憶に読み込む」とあります。
ようは、全てを一度に読み込むのではなく、必要なプログラムだけを主記憶(メインメモリ)に読み込むのです。
スワップ

過去問(H20秋SW午前問27)では、スワッピングに関して、「プログラムを一時的に停止させ,使用中の主記憶の内容を補助記憶に退避する。再開時には,退避した内容を主記憶に再ロードし,元の状態に戻す」とあります。

H16秋AD午前
問13 仮想記憶方式においてスワッピングが多発しているシステムに対して,主記憶を増設することの効果はどれか。
ア 画像修正ソフトで取り扱える色の数が増える。
イ 表計算ソフトの計算精度が向上する。
ウ より大きいサイズのファイルが処理できるようになる。
エ ワープロソフトが速く動作するようになる。

H20秋AD
問10 仮想記憶機能をもつサーバで新しいプログラムを追加して実行したところ,スワッピングが多発し,以前から動作しているプログラムの処理効率が低下した。解決策として,最も適切なものはどれか。
ア 高速なCPUに変更する。
イ 高速な主記憶に変更する。
ウ 磁気ディスク装置を増設し,補助記憶の容量を拡大する。
エ 主記憶を増設する。


H27春AP午前
問17 プロセスのスケジューリングに関する記述のうち,ラウンドロビン方式の説明とし
  て,適切なものはどれか。
ア 各プロセスに優先度が付けられていて,後に到着してもプロセスの優先度が実行
 中のプロセスよりも高ければ,実行中のものを中断し,到着プロセスを実行する。
イ 各プロセスに優先度が付けられていて,イベントの発生を契機に,その時点で最
 高優先度のプロセスを実行する。
ウ 各プロセスの処理時間に比例して,プロセスのタイムクウォンタムを変更する。
エ 各プロセスを待ち行列の順にタイムクウォンタムずつ実行し,終了しないときは
 待ち行列の最後につなぐ。
 
H17秋SW午前
問24 ジョブスケジューリングに関する記述として,適切なものはどれか。
ア FCFS (First Come First Served)方式は,ジョブの到着順に処理を行うもので,長大なジョブがあってもスループットが高い。
イ SPT (Shortest Processing Time First)方式は,処理時間の短いジョブの順に処理を行うので,対話型処理の平均応答時間を最小にできる。
ウ デッドラインスケジューリング方式は,目標の時間帯内に処理を完了することを目的に処理の優先度を決定するので,タイマ割込みのオーバヘッドが影響し,時間の制約の厳しいリアルタイム処理には向いていない。
工 優先度順方式は,バッチ処理の優先度を高く設定し,リアルタイム処理の優先度を低くして運用するのが一般的である。

H19春DB午前
問3 ラウンドロビン方式のタスクスケジューリングの説明として,適切なものはどれか。
ア 一定時間ごとにタイマ割込みを発生させ,実行可能の待ち行列の先頭のタスクにCPU資源を割り当てる。
イ 各タスクの優先度に従ってCPU資源を割り当てる。
ウ 処理時間の短いタスクから順にCPU資源を割り当てる。
工 何らかの割込みが発生したときに,直ちに起動する必要のあるタスクにCPU資源を割り当てる。

H23秋SM午前
問3 コンピュータシステムにおけるジョブスケジューリングの特徴のうち,適切なものはどれか。
ア CPUに割り当てるジョブをOSが強制的に切り替えるタイムスライス方式では,タイマ割込みが多発するので,スループットが低下する。
イ FCFS (first-come first-served)方式のジョブスケジューリングは,ジョブ間にCPUを公平に割り当てるので,スループットや応答時間の保証が可能となる。
ウ 対話型処理とバッチ処理が混在するシステムでは,対話型処理の優先度を高くすることによって,対話型処理の応答性能の向上が期待できる。
エ 入出力を多用するジョブよりもCPUを多用するジョブの処理優先度を上げた方が,CPUの待ち時間が少なくなるので,全体のスループットの向上が期待できる。

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

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

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

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

では、別の過去問をみてみましょう。

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

このページのトップヘ