平成23年度 特別 午前Ⅱ 問9

優先度に基づくプリエンプティブスケジューリングのリアルタイムOSを使用した組込みシステムで，入力装置及び出力装置にアクセスする二つのタスクX，Yがある。XはYより優先度が低く，Yが待ち状態となったときにXに処理が戻る。X，Yのアクセスを排他制御するために，入力装置及び出力装置それぞれに資源数1のセマフォを用意し，X，Yを図のように実装したとき，デッドロックが発生するのはXが処理中のどのタイミングでYが起床したときか。ここで，Yは起床するとαから処理を行うこととする。

タスクX，Yの処理の流れ（原典は図。上から下の順に箱を書き写し，矢印に付いた記号を添えた）:

X                              Y
↓                              ↓ α
入出力データの準備              入出力データの準備
↓ A                            ↓
入力装置用セマフォ取得          出力装置用セマフォ取得
↓ B                            ↓
出力装置用セマフォ取得          入力装置用セマフォ取得
↓ C                            ↓
入出力処理                      入出力処理
↓ D                            ↓
出力装置用セマフォ解放          入力装置用セマフォ解放
↓                              ↓
入力装置用セマフォ解放          出力装置用セマフォ解放
↓                              ↓