令和5年度 秋期 午前Ⅱ 問6
オペレーティングシステム
デッドロックに関する問題
優先度に基づくプリエンプティブスケジューリングのリアルタイムOSを使用した組込みシステムにおいて，入力装置及び出力装置にアクセスする二つのタスクX，Yがある。XはYより優先度が低く，Xが資源待ち状態でない場合にYが資源待ち状態に遷移するとXが実行状態に遷移する。入力装置及び出力装置へのアクセスを排他制御するために，入力装置及び出力装置にそれぞれバイナリセマフォi及びoを用意し，X，Yを図のように実装したとき，デッドロックが発生するのはXの処理A，B，C又はDのうち，どの処理中にプリエンプションが発生してYが実行されたときか。ここで，Yの実行はαから行うものとし，Xの処理A，B，C及びDでは入力装置及び出力装置へのアクセス及びバイナリセマフォの操作は行わないものとする。
タスクX，タスクYの処理の流れ:
タスクX ↓ [出力データの準備] ↓ [処理A] ↓ [セマフォi取得] ↓ [処理B] ↓ [セマフォo取得] ↓ [処理C] ↓ [入力装置及び出力装置へのアクセス] ↓ [処理D] ↓ [セマフォo解放] ↓ [セマフォi解放] ↓ [入力データの加工] タスクY ↓ α [出力データの準備] ↓ [セマフォo取得] ↓ [セマフォi取得] ↓ [入力装置及び出力装置へのアクセス] ↓ [セマフォi解放] ↓ [セマフォo解放] ↓ [入力データの加工]
- ア処理A
- イ処理B
- ウ処理C
- エ処理D
答えと解説を見る
✓ これが正解イ処理B
解説
Xがiだけを持つ処理Bで切り替わると、互いの解放を待ち合います。
デッドロックは、二つのタスクが互いに相手の持つ資源の解放を待ち続け、どちらも進めなくなる状態です。X はセマフォを i、o の順に取得し、Y は o、i の逆の順に取得します。X が i を取得した後、o を取得する前の処理Bで Y に切り替わると、Y は o を取得し、続いて i を取りにいきますが、i は X が持っているので待ち状態になります。すると X が実行を再開し、o を取りにいきますが、o は Y が持っているので X も待ちになります。互いに相手のセマフォを待つ形となり、デッドロックが発生します。複数のセマフォを取得するタスクでは、片方だけを持った区間で切り替わる場合を探すと、答えがすぐ見つかります。
ほかの選択肢はなぜ違うのか
- ア処理A：処理Aの時点では X はまだどのセマフォも持っていません。切り替わった Y は o と i を続けて取得でき、装置へのアクセスを終えて両方を解放するので、X が再開しても待ち合いは生じません。
- ウ処理C：処理Cの時点では X が i と o を両方持っています。Y は o の取得で待ちになりますが、X がそのまま進んで o と i を順に解放するので、Y もやがて両方を取得でき、行き詰まりません。
- エ処理D：処理Dの時点でも X は i と o を両方持っており、Y は o を待つだけです。X が装置へのアクセスを終えて解放すれば Y が続けて取得できるので、互いに待ち続ける形にはなりません。
この問題の用語
- 排他制御同じデータを同時に更新しても、矛盾が起きないようにする仕組みです。先の処理が終わるまで、後の処理を待たせて防ぎます。
出典：令和5年度 秋期 エンベデッドシステムスペシャリスト試験 午前Ⅱ 問6
同じ用語が出る問題
- 令和5年度 秋期 午前Ⅱ 問8：スタベーションに関する記述（排他制御）
- 平成31年度 春期 午前Ⅱ 問8：セマフォに関する問題（排他制御）
- 平成31年度 春期 午前Ⅱ 問7：優先度逆転の原因となるもの（排他制御）
- 平成30年度 春期 午前Ⅱ 問10：優先度逆転に関する問題（排他制御）
- 平成30年度 春期 午前Ⅱ 問8：セマフォに関する記述（排他制御）
この解説に誤りを見つけたら教えてください。直して、直した記録を残します。誤りを報告する（メールが開きます）