平成25年度春季解答

問題1

ハミング符号とは，データに冗長ビットを付加して， 1ビットの誤りを訂正できるようにしたものである。ここでは，X₁，X₂，X₃，X₄の4ビットから成るデータに，3ビットの冗長ビットP₃，P₂，P₁を付加したハミング符号 X₁X₂X₃P₃X₄P₂P₁を考える。付加ビットP₁，P₂，P₃は，それぞれ
　 X₁⊕X₃⊕X₄⊕P₁＝0
　 X₁⊕X₂⊕X₄⊕P₂＝0
　 X₁⊕X₂⊕X₃⊕P₃＝0
となるように決める。ここで⊕は排他的論理和を表す。
　 ハミング符号 1110011 には1ビットの誤りが存在する。誤りビットを訂正したハミング符号はどれか。

ア	0110011
イ	1010011
ウ	1100011
エ	1110111

解答：ア

＜解説＞

1. X₁X₂X₃P₃X₄P₂P₁=1110011の時、問題文の各式の値がどのような値になるか計算する。

   X1⊕X3⊕X4⊕P1	＝1⊕1⊕0⊕1	0⊕1	=1
   X1⊕X2⊕X4⊕P2	＝1⊕1⊕0⊕1	0⊕1	=1
   X1⊕X2⊕X3⊕P3	＝1⊕1⊕1⊕1	0⊕1	=1

2. これらの式は本来なら全て結果が0になるように P₁～P₃が定められたはずだが結果は全部1となる。
3. したがって、これら3つの式すべてに共通して含まれているX₁のビットに誤りがあることが分かる。
4. X₁のビットを1から0に変換すると0110011となる。

したがって、アが正解である。

問題へ

問題2

func(n)は、非負の整数nに対してnの階乗を返す。fanc(n)の再帰的な定義はどれか。

ア	if n=0 then return 0 else return n×fact(n-1)
イ	if n=0 then return 0 else return n×fact(n+1)
ウ	if n=0 then return 1 else return n×fact(n-1)
エ	if n=0 then return 1 else return n×fact(n+1)

解答：ウ

＜解説＞

nの階乗（n!）を求める式は、n1=n×(n-1)×(n-2)×．．．×2×1=n×(n-1)!である。ただし数学の規則により0!=1である。

ア	×	n=0として値を求めるとfact(0)=0となる。0!=1とならない。
イ	×	n=0として値を求めるとfact(0)=0となる。0!=1とならない。
ウ	○	階乗と一致する
エ	×	n>0の時、 fact(n) =n×fact(n+1)   =n×(n+1) ×fact(n+2)   =n×fact(n+1) ×fact(n+2) ×fact(n+3) となる。したがって階乗を求める式と一致しない。

問題へ

問題3

流れ図に示す処理の動作として、適切なものはどれか。ここで、二重線は並列処理の同期を表す。

ア	ABC又はACBを実行してデッドロックになる。
イ	AB又はACを実行してデッドロックになる。
ウ	Aの後にBC又はCB、BC又はCB、・・・と繰り返して実行する。
エ	Aの後にBの無限ループ又はCの無限ループになる。

解答：ウ

＜解説＞

流れ図に示された処理は次のように実行される。

1. 「A」を実行しポイント1になる。
2. ポイント1で処理を開始すると「B」か「C」を実行する。
3. どちらかの処理が終了すると先に終了した処理はポイント2でもう一方の処理が終了するまで待機する。
4. 「B」,「C」両方の処理が終了するとポイント1に戻って処理を再開し「B」か「C」を実行する。

したがって「A」を実行した後に「BC」または「CB」が繰り返し実行される。

よって、ウが正解である。

問題へ

問題4

キャッシュの書込み方式には、ライトスルー方式とライトバック方式がある。ライトバック方式を使用する目的として、適切なものはどれか。

ア	キャッシュと主記憶の一貫性(コヒーレンシ)を保ちながら、書込みを行う。
イ	キャッシュミスが発生したときに、キャッシュの内容の主記憶への書き戻しを不要にする。
ウ	個々のプロセッサがそれぞれのキャッシュをもつマルチプロセッサシステムにおいて、キャッシュ管理を簡単な回路構成で実現する。
エ	プロセッサから主記憶への書込み頻度を減らす。

解答：エ

＜解説＞

書込み命令が実行された時に、キャッシュメモリと主記憶の両方を書き換える方式のことを、ライトスルー方式(write through) ，キャッシュメモリだけを書き換えておき、主記憶の書き換えはブロックの入れ替え時に行う方式のことを、ライトバック(write back) 方式という。

ライトスルー方式

• キャッシュへの書込みと同時に主記憶にも書き込む方式
• キャッシュと主記憶の一貫性(コヒーレンシ)は常に保たれる
• 書き込みの高速化はできない

ライトバック方式

• キャッシュから追い出された時点で主記憶へ書き込む方式
• 主記憶への書込みが終了するまでキャッシュとの一貫性(コヒーレンシ)が保たれない
• 書込みも高速化できる

ア	×	ライトスルー方式の説明である。ライトバック方式では、キャッシュと主記憶の一貫性(コヒーレンシ)が保たれないことがある。
イ	×	ライトスルー方式の説明である。ライトバック方式では、キャッシュミスが発生したとき、キャッシュの内容を主記憶に書き戻す必要がある。
ウ	×	ライトスルー方式の説明である。ライトバック方式では、個々のプロセッサのもつキャッシュと主記憶の一貫性を調整するため回路構成は複雑になる。
エ	○	ライトバック方式の説明である。ライトバック方式では、プロセッサが主記憶に書き込みを行うのはキャッシュをフラッシュする場合だけなので、書込み頻度を減らすことができる。

問題へ

問題5

密結合マルチプロセッサの性能が、1台当たりのプロセッサの性能とプロセッサ数の積に等しくならない要因として、最も適切なものはどれか。

ア	主記憶へのアクセスの競合
イ	通信回線を介したプロセッサ間通信
ウ	プロセッサのディスパッチ処理
エ	割込み処理

解答：ア

＜解説＞

マルチプロセッサシステムの構成には以下の二つがある。

密結合マルチプロセッサシステム

複数のプロセッサが主記憶を共有（共有メモリ型）

疎結合マルチプロセッサシステム

プロセッサごとにローカルメモリとOSをもったモジュールを単位として、複数のプロセッサを結合

ア	○	主記憶へのアクセスの競合によって密結合プロセッサではデータの整合性を保つため排他処理を行なう。その結果、頻繁にプロセッサが処理待ち状態になり性能が低下する。
イ	×	通信回線を介したプロセッサ間通信による性能低下は、疎結合マルチプロセッサシステムによって発生する要因である。
ウ	×	プロセッサのディスパッチ処理は、マルチプロセッサ以外でも発生する。すなわち、プロセッサのマルチ化に伴う性能低下の要因ではない。
エ	×	割込み処理は、マルチプロセッサ以外でも発生する。すなわち、プロセッサのマルチ化に伴う性能低下の要因ではない。

問題へ