バイナリセマフォの逆順獲得によるデッドロック発生条件の解析

2つのタスク X（低優先度）と Y（高優先度）の資源獲得順序をトレースしてデッドロック発生箇所を特定します。 1. 各タスクのセマフォ獲得順序 : - タスク X: 処理 A → セマフォ $i$ 獲得（Wait $i$） → 処理 B → セマフォ $o$ 獲得（Wait $o$） → 処理 C → 入出力アクセス → 各セマフォ解放 → 処理 D - タスク Y: 出力データ準備 → セマフォ $o$ 獲得（Wait $o$） → セマフォ $i$ 獲得（Wait $i$） → 入出力アクセス → 各セマフォ解放 2. デッドロックの発生機構 : - 低優先度のタスク X が「処理 B」を実行中であるということは、タスク X は既に セマフォ $i$ を保持 しています。 - この時点で高優先度のタスク Y が起動（プリエンプション）すると、Y はまず セマフォ $o$ を正常に獲得 します。 - 続いて Y はセマフォ $i$ を獲得しようとしますが、セマフォ $i$ は既にタスク X が保持しているため、Y はセマフォ $i$ の資源待ち状態となりブロックされます。 - 優先度スケジューリングによりタスク X に実行権が戻り、X は処理 B を終えて セマフォ $o$ を獲得しようとします 。 - しかし、セマフォ $o$ はタスク Y が保持しているため、タスク X もセマフォ $o$ 待ちでブロックされます。 - この結果、X は Y が保持する $o$ を待ち、Y は X が保持する $i$ を待つという 相互待ち（循環待機） が成立し、永久に処理が進まないデッドロック状態に陥ります。 したがって、デッドロックが発生するのはタスク X の 処理 B の実行中にプリエンプションが発生したときであり、正解は イ です。 ア: 処理 A の時点ではタスク X はまだどのセマフォも獲得していないため、Y が実行されても Y はセマフォ $o$ と $i$ を両方獲得して正常終了し、デッドロックにはなりません。 ウ: 処理 C の時点ではタスク X はセマフォ $i$ と $o$ の両方を既に獲得しているため、Y が起動してもセマフォ $o$ 待ちで即座にブロックされ、X が処理を完了して解放した後に Y が実行されるためデッドロックは起きません。 エ: 処理 D の時点ではタスク X は両方のセマフォを解放済みであるため、デッドロックは発生しません。

優先度に基づくプリエンプティブスケジューリングのリアルタイム OS を使用した組込みシステムにおいて，入力装置及び出力装置にアクセスする二つのタスク X，Y がある。X は Y より優先度が低く，X が資源待ち状態でない場合に Y が資源待ち状態に遷移すると X が実行状態に遷移する。入力装置及び出力装置へのアクセスを排他制御するために，入力装置及び出力装置にそれぞれバイナリセマフォ ii 及び oo を用意し，X，Y を図のように実装したとき，デッドロックが発生するのは X の処理 A，B，C 又は D のうち，どの処理中にプリエンプションが発生して Y が実行されたときか。ここで，Y の実行は初めから行うものとし，X の処理 A，B，C，D では入力装置及び出力装置へのアクセス及びバイナリセマフォの操作は行わないものとする。

問題画像
出典令和5年度 秋期 エンベデッドシステムスペシャリスト試験 午前Ⅱ 問6
ア
処理 A
イ
処理 B
ウ
処理 C
エ
処理 D