応用情報技術者 2013年 春期 午前2 問08

同期による交互実行【午前2解説】

正解の理由

解法ステップ

1. 並列領域（上下の二重線）を見つける：ここが分岐と同期の範囲であると認識する。
2. 各分岐のループ経路を追う：B・C は下段から上段へ戻るループを持つ。
3. 上部の矢印の向きを確認する：B 側の矢印は左→右、C 側の矢印は右→左。
4. トークンの移動を具体的に追跡する：一方が終わってループで上段に戻ると、その上段で矢印に従い相手分岐を起動する。
5. このサイクルが繰り返されることから、交互実行であると結論づける。

• A 実行 → トークンが左（B）側に進入 → B 実行 → B は下段へ出る → ループで上段左へ戻る → 上部の矢印（左→右）によりトークンが右（C）に渡る → C 実行 → C がループで上段右へ戻る → 上部の矢印（右→左）でトークンが左へ渡る → 以後同様に繰り返し。

選択肢別の誤答解説

• ア: 「ABC 又は ACB を実行してデッドロックになる」
  誤り。ABC の順に同時に実行して互いに待ち合うという構造はなく、むしろループで戻ったトークンは上部矢印により相手へ渡るためデッドロックにはならない。
• イ: 「AB 又は AC を実行してデッドロックになる」
  誤り。単独で AB や AC が止まって互いに待つような閉塞は生じない。上部の矢印がトークンを反対側に送るため、片側だけが永久に止まる構造ではない。
• ウ: 「A の後に BC 又は CB, BC 又は CB, ・・・と繰り返して実行する」
  正しい。上段での矢印向きと下段ループにより、実行トークンが分岐間で渡されるため B と C が交互に繰り返される。
• エ: 「A の後に B の無限ループ又は C の無限ループになる」
  誤り。各分岐がループで上段に戻るが、上段で相手側へトークンを渡す仕組みがあるため、一方のみが無限に単独実行される構造ではない。

よくある誤解

• 「二重線＝必ず同時並列で同時に実行される」
  誤り。二重線は並列領域を示しますが、内部の矢印やループ経路により実行トークンの受け渡しが制御され、同時実行にならない場合がある点を見落としやすいです。
• 「ループがある＝その分岐が単独で永久に実行される」
  誤り。ループで戻る先が相手側の入口へトークンを渡す構成なら、単独ループではなく相互に回るだけです。

補足コラム

# 擬似シミュレーション（説明用）
steps = []
current = 'B'  # A の後、B から開始すると仮定
for i in range(6):
    steps.append(current)
    # 終了して上段へ戻ると反対側に渡される
    current = 'C' if current == 'B' else 'B'
print(steps)  # ['B','C','B','C','B','C']

FAQ