基本情報技術者試験 令和元年度 秋季 午前 問13
CPU の割込み処理についての問題。
--------------------------
令和元年度 秋期 午前 問13
メイン処理、及び表に示す二つの割込み A、B の処理があり、多重割込みが許可されている。割込み A、B が図のタイミングで発生するとき、0 ミリ秒から 5 ミリ秒までの間にメイン処理が利用できる CPU 時間は何ミリ秒か。ここで、割込み処理の呼出し及び復帰に伴うオーバヘッドは無視できるものとする。
ア 2
イ 2.5
ウ 3.5
エ 5
--------------------------
解説
選択肢の有効桁数表示があっていないことにムズムズする。
ア 2.0
イ 2.5
ウ 3.5
エ 5.0
この問題は CPU の割込みについての問題。
CPU が何かの処理（メイン処理）をしているときでも、ユーザのキーボード操作等があればそちらの処理を優先する。
そうしないと、キーボードを操作しても画面に反映されるのがメイン処理が終わった後になってしまい、操作性が非常に悪くなってしまう。
この場合はキーボード操作の処理が割込み処理になる。
問題の図に CPU がその時間にどの処理をしているかと、メイン処理の列を追加する。
図の ①～⑨ の処理状況について以下に記載する。
［①：メイン処理を実行中］
割込み B が発生するまでは CPU でメイン処理が実行されている。
問題が聞いているのは図の 0 ミリ秒以降のことなので、この時間は関係ない。
［②：割込み B 処理を実行中］
割込み B が発生したので、CPU は割込み B の処理を実行している。
［③：割込み A 処理を実行中］
割込み A が発生し、割込み B と割込み A では割込み A の方が優先度高いため、CPU は割込み A の処理を実行することになる。
問題文より多重割込みが許可されているので、割込み B の処理中にさらに別の割込み A がはいってこれる。
［④：割込み B 処理を実行中］
割込み A が 0.5 ミリ秒で終了するので、割込み B の処理に戻る。
②で割込み B は 1.0 ミリ秒処理済みなので、④の長さは 0.5 ミリ秒になる。
［⑤：メイン処理を実行中（0.5ミリ秒）］
割込み B も終了したので、やっと CPU がメイン処理を実行できる。
［⑥：割込み A 処理を実行中］
割込み A が発生したので、また CPU が割込み処理の実行をすることになる。
［⑦：メイン処理を実行中（0.5ミリ秒）］
割込み A が終了したので、再び CPU がメイン処理を実行できる。
［⑧：割込み A 処理を実行中］
また割込み A が発生したので、また CPU が割込み処理の実行をすることになる。
［⑨：メイン処理を実行中（1.0ミリ秒）］
割込み A が終了したので、再び CPU がメイン処理を実行できる。
問題文が聞いている 5.0 ミリ秒まで処理が続けられる。
⑤、⑦、⑨でメイン処理を実行できていて、その時間は合計で 2.0 ミリ秒になる。
ということで正解は選択肢アとなる。
この問題では割込み処理への切り替えにかかるオーバヘッドを無視できるとしているが、実際には多少なりオーバヘッドで無駄な時間がかかるため、割込みにより切り替えが頻繁に起きないような設計が必要になる。
例としてこの問題の割込み A と割込み B の優先度を反対にした場合は以下のようになる。
優先度を反対にする前と比較して、切り替えの回数が 1 回減っている。
一方で、1.0 ミリ秒で発生した割込み A の開始が 0.5 ミリ秒遅れてしまっている（割込み A の応答性が悪くなっている）。
割込み A の応答性を優先するのか、全体としてオーバヘッドの削減を優先するのかは、そのシステムの目的次第で決めるものになる。
前後の問題はこちら。
基本情報技術者試験 令和元年度 秋季 午前 問12
CPU のクロックに関しての問題。ついでに演算性能（FLOPS）についても。
--------------------------
令和元年度 秋期 午前 問12
1 GHz のクロックで動作する CPU がある。この CPU は、機械語の 1 命令を平均 0.8 クロックで実行できることが分かっている。この CPU は 1 秒間に平均何万命令を実行できるか。
ア 125
イ 250
ウ 80,000
エ 125,000
--------------------------
解説
CPU についての問題。
Central Processing Unit：中央演算装置
システムエンジニアは CPU を「石」と呼ぶこともある。なんでだろう。
「1 GHz のクロックで動作する CPU」
CPU は一定間隔のリズムで CPU 内部の各パーツを動かして処理をしている。
リズムが早いほど、高速に処理ができる。
そのリズム（クロック）が 1 GHz であるということ。
つまり、1 秒間に 1 G（ギガ）クロック分の処理ができる CPU となる。
G（ギガ）は 10⁹ なので、1 G クロック = 1 × 10⁹ クロック = 1,000,000,000 クロックである。
「機械語の 1 命令を平均 0.8 クロックで実行できる」
0.8 クロックあれば平均して 1 命令を処理できるということ。
この CPU は 1 秒間に 1,000,000,000 クロックなので、1 秒間に処理できる命令は
1,000,000,000 [クロック] ÷ 0.8 [クロック/命令] ＝1,250,000,000 命令となる。
「この CPU は 1 秒間に平均何万命令を実行できるか」
1 秒間に 1,250,000,000 命令を実行できるが、問題が聞いているのは何万命令かなので、
1,250,000,000 命令 ＝ 125,000 × 10,000 命令 ＝ 125,000 万命令 であり、正解は選択肢エとなる。
CPU の問題ついでに CPU の演算性能について少し書いてみる。
Intel Xeon Gold 6152 という CPU を例にしてみる。
Intel Xeon Gold 6152 Processor 30.25M Cache 2.10 GHz 製品仕様
周波数 2.10 GHz で、コア数が 22 となっている。
昔の CPU は 1 コアしかないものもあったが、今の CPU はほぼマルチコアプロセッサとなっている。
コア毎に異なる処理を割り当てて、複数の命令を並列に処理することができる。
人によっては 「CPU の数は？」 と言いながら、意図としては 「コアの数は？」 を聞いているケースもあるので注意が必要である。
Intel Xeon Gold 6152 は周波数 2.10 GHz で動くコアが 22 個搭載されている。
各コアは浮動小数点演算ができるユニットを 32 個搭載している（この個数は CPU のアーキテクチャで決まってくるもの）。
※「32個搭載」と書くと厳密には異なるけども、概念の説明ということでご勘弁を。。。
これら数値の掛け算が FLOPS（Floating-point Operations Per Second）という性能指標になる。
2.10 GHz × 22 コア × 32 ユニット = 1,478.4 GFLOPS
FLOPS は 1 秒あたり（Per Second）に何回の浮動小数点演算（Floating-point Operations）ができるか、という指標である。
22 コアが各々 32 個の浮動小数点演算ユニットをもつので、CPU としては 22 × 32 = 704 個の浮動小数点演算ユニットをもつことになる。
704 個の各ユニットが 2.10 GHz（＝1 秒間に 2.10 G回）のリズムで動作ができるので、
1 秒間に 704 × 2.10G = 1,478.4 G 回の浮動小数点演算ができる CPU である、ということになる。
ただし、この CPU には AVX という機能があり、その機能を利用した場合は周波数が 1.40GHz となるため、 性能は 985.6 GFLOPS となる。
GFLOPS の数値は低く見えるが AVX の機能で効率よく計算ができるので、計算にかかる時間は短くなる（可能性もある）。
FLOPS の性能指標は上のとおり全ての浮動小数点演算ユニットが常に動いた場合の数値となっているが、実際に使われるようなソフトウェアで、そんな状況はまず起こらない。
ディスクやメモリの I/O 待ち、複数コアを使うために処理を割り振るオーバーヘッド等で仕事をしていないユニットは必ず発生する。
また、コア数を多くすれば CPU としての FLOPS はよくなるが、業務で使うソフトウェアが複数コアを使う並列化に向いていないものであると全く意味がない。
CPU の FLOPS 値は理論上の参考値とはなるが、業務で実際に使うソフトウェアの特性も考慮にいれて最適な CPU を選ぶ必要がある。
とはいっても精度の高い推測は難易度が高いので、いくつかの CPU で実際にソフトウェアを動かしてみるベンチマークがよく行われる。
前後の問題はこちら。
基本情報技術者試験 令和元年度 秋季 午前 問11
--------------------------
令和元年度 秋期 午前 問11
自然数 n に対して、次の通り再帰的に定義される関数 を考える。
の値はどれか。
: if n ≦ 1 then return 1 else return
ア 6
イ 9
ウ 15
エ 25
--------------------------
解説
再帰的に定義される関数については以下で書いてみている。
再帰（さいき）とは、ある記述をする際に、その記述の中に自身への参照が含まれていること。
: if n ≦ 1 then return 1 else return
一行で書くとわかりにくいので、少し工夫して、プログラムみたく改行とインデントを加えてみる。
:
if n ≦ 1
then
return 1
else
return
n が 1 以下のときは 1 を返し、そうでないときは を返すということ。
問題としては を聞いているので、
の定義に従うと以下のようになる。
=
=
=
=
=
=
=
=
= f(1) は n ≦ 1 のときなので 1 になる
=
となるので、正解は選択肢ウの 15。
計算の途中を見ての通り、この関数は n 以下の正の整数の和を求めている。
等価な数式にするとこんな感じ。
ちなみに問題では自然数 n と書いているが、自然数には 0 を含まない流儀と含む流儀がある。
- 0 を含まない流儀の場合は、ここまでの話に問題はない。
- 0 を含む流儀の場合は、ちょっと問題が起きてくる。
問題の では n ≦ 1 で return 1 なので、
になる。
一方で、
では とはならないので、等価な数式ではなくなってしまう。
勝手に等価な数式は～とか言い出して、勝手に問題が～とか言っているだけなのでどうでもいいことではあるけれど。
関数は定義域もちゃんと意識しましょう、という話でした。
前後の問題はこちら。
基本情報技術者試験 令和元年度 秋季 午前 問10
ハッシュ法についての問題。ついでに衝突時の話も。
--------------------------
令和元年度 秋期 午前 問10
10 進法で 5 桁の数 を、ハッシュ法を用いて配列に格納したい。ハッシュ関数を
とし、求めたハッシュ値に対応する位置の配列要素に格納する場合、54321 は配列のどの位置に入るか。
ここで、 は、
を 13 で割った余りとする。
--------------------------
解説
5 + 4 + 3 + 2 + 1 = 15
mod(15 , 13) = 2
なので正解は選択肢イの 2。
としか書くことがない。。。
ハッシュ法については以下の問題で少し書いてみてはいる。
折角なので、ハッシュ値が衝突した場合のことを書いてみる。
ハッシュ値が衝突することはコリジョン（collision）とも呼ばれる。英単語そのまま。
ハッシュ値が衝突するデータの集まりをシノニム（synonym）と呼ぶ。
この問題のように格納先が 13 種類（0 ～ 12）しかないと、かなり頻繁に衝突が起きる。
衝突が起きた場合にどうするか。
オープンアドレス法
衝突が起きたら、何らかの手順で次の空いている格納先を探す。
- 54321 が問題のとおり配列 2 に格納されている。
- 54388 は mod(28 , 13) = 2 となるが、配列 2 にはもう 54321 がいる。
- なので、一つ後ろの配列 3 に 54388 を格納する（線形走査法）
線形走査法埋は単純でわかりやすいが、連続して配列が埋まってしまうことで衝突が起こりやすくなってしまうデメリットがある。
ちょっとだけ改良したのが二重ハッシュ法。
- 54321 が問題のとおり配列 2 に格納されている。
- 54388 は mod(28 , 13) = 2 となるが、配列 2 にはもう 54321 がいる。
- 54388 に mod(28 , 13) とは別のハッシュ関数を当てはめて格納配列を決める。
そもそもの考え方を変えてみる。
直接連鎖法（ハッシュチェイン法）
格納先を一つの箱ではなく、連結リストとする。
- 54321 が問題のとおり配列 2（の 1 番目）に格納されている。
- 54388 は mod(28 , 13) = 2 となるので、配列 2（の 2 番目）に格納される。
連結リストが長くなってしまうと検索のときに結局時間がかかってしまう。
どちらにせよ、ハッシュ値が衝突しないような工夫が大事になる。
前後の問題はこちら。
基本情報技術者試験 令和元年度 秋季 午前 問9
配列と流れ図と回転をネタにした問題。
--------------------------
令和元年度 秋期 午前 問9
配列 A が図 2 の状態のとき、図 1 の流れ図を実行すると、配列 B が図 3 の状態になった。図 1 の a に入れる操作はどれか。
ここで、配列 A、B の要素をそれぞれ A( i, j )、B( i, j ) とする。
ア B( 7-i, 7-j ) ← A( i, j )
イ B( 7-j, i ) ← A( i, j )
ウ B( i, 7-j ) ← A( i, j )
エ B( j, 7-i ) ← A( i, j )
--------------------------
解説
配列 A は図 2 の通りで、A( 0, 0 ) や A (1, 2 ) とかは空白、A( 0, 1 ) や A( 1, 1 ) には値（＊）が入っている状態になっている。
縦が添字 i の番号、横が添字 j の番号を表している。配列の位置を示す i や j のことを "添字（そえじ）" と呼ぶ。インデックスと呼ぶ人もいる。好みの世界。
これをどういったルールで B( i, j ) に入力すれば、図 3 となるような配列 B が出来上がるのか、といった問題である。
一個一個の空白や値（＊）は区別できないが、配列 A と B の全体を眺めると、配列 A を時計回りに 90 度回転したら配列 B になることが分かる。
（配列で描かれている Ｆ の文字が右に倒れている。）
なので、F の左上部分 A( 0, 1 ) と対応しているのは B( 1, 7 ) であり、F の一番下部分 A( 7, 1 ) と対応しているのは B( 1, 0 ) ということになる。
つまり、流れ図のループの中で、以下のような代入があったことになる。
- B( 1, 7 ) ← A( 0, 1 )
- B( 1, 0 ) ← A( 7, 1 )
各選択肢をみて、上の代入と一致するものを探せばいい。
すると、選択肢エ B( j, 7-i ) ← A( i, j ) だけが一致することが分かる。
ということで、問題の正解は選択肢エである。
「回転」にパワー使ったからな。
元ネタわかってくれる同志はいるだろうか。
|
|
![[商品価格に関しましては、リンクが作成された時点と現時点で情報が変更されている場合がございます。]](https://hbb.afl.rakuten.co.jp/hgb/1d6e79a0.6eab03bd.1d6e79a1.59b07dcf/?me_id=1213310&item_id=16199243&pc=https%3A%2F%2Fthumbnail.image.rakuten.co.jp%2F%400_mall%2Fbook%2Fcabinet%2F6979%2F9784088706979.jpg%3F_ex%3D240x240&s=240x240&t=picttext "[商品価格に関しましては、リンクが作成された時点と現時点で情報が変更されている場合がございます。]")
前後の問題はこちら。
基本情報技術者試験 令和元年度 秋季 午前 問8
スタック（データ構造）についての問題。
--------------------------
令和元年度 秋期 午前 問8
A, C, K, S, T の順に文字が入力される。スタックを利用して、S, T, A, C, K という順に文字を出力するために、最小限必要となるスタックは何個か。ここで、どのスタックにおいてもポップ操作が実行されたときには必ず文字を出力する。また、スタック間の文字の移動は行わない。
ア 1
イ 2
ウ 3
エ 4
--------------------------
解説
スタックについてはこちらの問題で（雑な）絵とともに説明している。
スタックは先に入れたデータほど後に取り出されるデータ構造である。
この方式は LIFO（Last In First Out）と呼ばれる。
Last In（最後に入れたもの）が First Out（最初に取り出される）。
なので、一つのスタックに連続して文字を入力（プッシュ）すると、取り出す（ポップ）ときは逆の順序になる。
スタックの数が少ない選択肢から考えてみる。
スタックが 1 個の場合（選択肢ア）
- 最初にポップ操作で出力したい文字は "S" なので、"S" が入力されるまでの "A, C, K" はスタックに溜めておく必要がある。ということで、"A, C, K" は全てプッシュして同じスタックに入力することになる。
- 次に "S" がプッシュされた後すぐにポップ、その次に "T" がプッシュされた後すぐにポップ、とすれば "S, T" までは欲しい順序で出力できる。
- しかし、その後のポップ操作で出力されるのは "K, C, A" となってしまう（"A, C, K" の順で同じスタックに入力しているので、逆の順序でしか取り出せない）。
スタックが 2 個の場合（選択肢イ）
- スタックが 1 個の場合を反省すると、"S" が入力されるまでの "A, C, K" は 3 文字とも別々のスタックに入力する必要があることが分かる。
- 上の理由は、"A, C, K" の 3 文字だけに着目すると、入力される順序も、欲しい出力の順序も同じであるためである。同じスタックに入力してしまうと順序が逆転して出力されてしまい、欲しい文字列の順序にならなくなってしまう。
- ということで、スタックが 2 個の場合は "S" が入力されるまでの "A, C, K" を別のスタックに入力しておくことができないので不正解となる。
スタックが 3 個の場合（選択肢ウ）
- スタックが 3 個あるので、"A, C, K" を別々にスタックに入れることができる。
- 次の "S" はどのスタックでもいいので入れて、すぐにポップしてしまう。その次の "T" も同じようにプッシュ＆ポップ。
- 後は 3 つのスタックに分かれて入っている "A, C, K" を順番通りにポップすれば、"S, T, A, C, K" の順の出力を得ることができる。
- ということで、正解は選択肢ウとなる。
"S, T, A, C, K" を見てまず思いついたもの。
前後の問題はこちら。
基本情報技術者試験 令和元年度 秋季 午前 問7
BNF についての問題。
--------------------------
令和元年度 秋期 午前 問7
次の BNF で定義される ＜変数名＞ に合致するものはどれか。
＜数字＞ :: = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
＜英字＞ :: = A | B | C | D | E | F
＜英数字＞ :: = ＜英字＞ | ＜数字＞ | _
＜変数名＞ :: = ＜英字＞ | ＜変数名＞＜英数字＞
ア _B39
イ 246
ウ 3E5
エ F5_1
--------------------------
解説
BNF とは、バッカス・ナウア記法（Backus-Naur Form) の略。
"文脈自由文法を定義するためのメタ言語" とのことであるが、この文章がまずわかりにくい。
文法（この問題だと "＜変数名＞" とかの構造）を定義するためのもの、と思えばいい。
＜数字＞ :: = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
順番に見ていくとして、上の BNF における "＜数字＞" は 0 から 9 のどれかという意味になる。
なので、ここでは 10 とか 100 は "＜数字＞" ではない（定義に当てはまらない）。
"＜数字＞＜数字＞" という BNF がもしあれば、10 とか 99 とかが当てはまる。
"＜数字＞＜数字＞＜数字＞" という BNF がもしあれば、100 とか 256 とかが当てはまる。
＜英字＞ :: = A | B | C | D | E | F
次に上の BNF について。
ここでは "＜英字＞" は A か B か C か D か E か F のどれかという意味になる。
なので、ここでは Z は "＜英字＞" ではないし、2 文字以上でも "＜英字＞" ではない。
＜英数字＞ :: = ＜英字＞ | ＜数字＞ | _
続いて上の BNF について。
"＜英数字＞" という定義の中に、先に説明した "＜英字＞" と "＜数字＞" が入っている。
"＜英数字＞" は "＜英字＞" か "＜数字＞" か _ のどれか、という意味になる。
"＜英字＞" と "＜数字＞" については上の説明の通り。
ということで、ここでは "＜英数字＞" は A, B, C, D, E, F, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, _ のうちどれか一文字という意味になる。
＜変数名＞ :: = ＜英字＞ | ＜変数名＞＜英数字＞
最後の BNF について。
"＜変数名＞" の定義の中に自分自身である "＜変数名＞" が含まれていてややこしい。
"＜変数名＞" は "＜英字＞" か "＜変数名＞＜英数字＞" のどちらか、という意味になる。
"＜英字＞" の場合は A, B, C, D, E, F のどれかなのでわかりやすい。
A の一文字だけでも、"＜変数名＞" の定義には当てはまることになる。
"＜変数名＞＜英数字＞" の場合は再び "＜変数名＞" がでてきてしまう。
以下、少しでも見やすくするため ＜変数名＞ に色を付けてみる。
"＜変数名＞" は "＜英字＞" か "＜変数名＞＜英数字＞" なので、
"＜変数名＞＜英数字＞" は "＜英字＞＜英数字＞" か "＜変数名＞＜英数字＞＜英数字＞" になる。
同じようにして、"＜変数名＞＜英数字＞＜英数字＞" は "＜英字＞＜英数字＞＜英数字＞" か "＜変数名＞＜英数字＞＜英数字＞＜英数字＞" になる。
なんとなくパターンが見えてきた通り、"＜変数名＞" は
"＜英字＞"
"＜英字＞＜英数字＞"
"＜英字＞＜英数字＞＜英数字＞"
"＜英字＞＜英数字＞＜英数字＞＜英数字＞"
"＜英字＞＜英数字＞＜英数字＞＜英数字＞・・・＜英数字＞"
といった様に先頭が "＜英字＞" で、その後ろに任意の数だけ "＜英数字＞" が続く BNF になる。
問題の各選択肢がこの定義にあっているかをみてみる。
選択肢ア "_B39"、選択肢イ "246"、選択肢ウ "3E5"、はどれも先頭が "＜英字＞" ではないので誤り。
選択肢エ "F5_1" は先頭が "＜英字＞" の定義に当てはまり、"＜英字＞＜英数字＞＜英数字＞＜英数字＞" の BNF に合致する。ということで正解は選択肢エ。
前後の問題はこちら。
