平成25年度春期 データベーススペシャリスト 午前Ⅰ 問3

同期点ごとに処理の進み方を追う

並列に動く処理の流れを読むときは、各処理がどこで他の処理を待ち、どこから再び進めるのかを一つずつ区切って考えることが大切です。同期の箇所を境目として時間の順に並べ直すと、動作の全体像が整理しやすくなります。

この問題で問われていること

この問題で確認したいのは、同期の箇所で各処理が待つ条件と再開する条件を正しく対応づけられるかどうかです。待つ側と知らせる側の関係を取り違えないよう、一つの観点に絞って流れを確かめてください。

視点

並列処理では、複数の処理がそれぞれ独立に進みます。その一方で、同期の仕組みによって特定の地点で互いの進み具合を合わせます。流れ図を読むときは、各処理の経路を別々に追ってください。あわせて、同期に関わる記号や操作がどの処理の進行に影響するのかを書き出すと、時間の前後関係を整理しやすくなります。

確認ポイント

• 同期に関わる箇所が流れ図のどこにあり、どの処理の経路に属しているかを書き出したか
• 各同期の箇所で処理が先へ進むには何がそろう必要があるかを、自分の言葉で確認したか
• 時間の順に並べ直したとき、待ちと再開の関係に矛盾がないかを見直したか

正解

ウ

解説

Aの後、上の二重線でBとCが並列に始まり、下の二重線で両方の終了を待って同期します。その後、線はBとCの入口へ戻るので、並列実行と同期が繰り返されます。このため、BC又はCBを繰り返すウが正解です。

理由

Aの後にある上の二重線で、処理はBとCの二つに分かれて並列に実行されます。BとCは並列なので、どちらが先に終わるかは決まっておらず、BC、CBのどちらの順もあり得ます。下の二重線は両方の終了を待つ同期で、両方がそろった後、線はそれぞれBとCの入口の上側へ戻ります。そのため再びBとCが並列に実行され、これが終わりなく繰り返されます。

比較

下の二重線はBとCの両方が終わるのを待つだけで、互いに相手の資源を握ったまま待ち続ける構造ではないため、デッドロック（ア・イ）にはなりません。また、戻り線は同期を通ってから入口へ戻るので、Bだけ、Cだけの無限ループ（エ）にもなりません。

選択肢ア

これは不正解だよ。デッドロックは、複数の処理が互いに相手の資源の解放や完了を待ち続けて進めなくなる状態だよ。この図のBとCは、下の二重線で互いの終了を待つだけなんだ。両方が終われば同期が成り立ち、線は再びBとCの入口へ戻るよ。互いに待ち合って止まる構造はないから、ABCやACBを実行した後に止まるという記述は図と合わないよ。

選択肢イ

これは不正解だよ。上の二重線で、Aの後の処理はBとCの二つに分かれ、両方が並列に実行されるよ。BかCのどちらか一方だけを選ぶ分岐ではないから、ABやACだけで終わることはないんだ。それに、下の二重線は両方の完了を待つ同期で、両方が終われば先へ進めるから、デッドロックにもならないよ。

選択肢ウ（正解）

これは正解だよ。Aの後、上の二重線で処理がBとCに分かれて並列に進むよ。並列だから、終わる順はBCでもCBでもあり得るんだ。下の二重線で両方の終了を待って同期し、そこから出る線はそれぞれBとCの入口の上側へ戻るから、再びBとCが並列に実行されるよ。この同期と再実行が終わりなく続くので、BC又はCBの繰返しという記述が図と一致するよ。

選択肢エ

これは不正解だよ。BとCから出る線は、下の二重線を通ってから入口へ戻るので、Bだけ、Cだけで回り続けるループではないよ。下の二重線は同期を表すから、Bが先に終わってもCの終了を待ち、両方がそろってから再びBとCが並列に始まるんだ。どちらか一方だけの無限ループになるという記述は、同期の意味と合わないよ。

学習のポイント

二重線を「分岐」と「合流の待ち合わせ」と読み分け、戻り線の行き先を追うことが大切です。