不確定特異点

広く深く、ところどころ超深く

リソースアクセスプロトコルのまとめ

マルチタスク環境において複数のタスクがリソースを共有し合うと、

という問題が起こります。これらを解決するためのリソースアクセスプロトコルについて、代表的なものをまとめてみました。

  • Non-Preemptive Protocol (NPP)
  • Highest Locker Protocol (HLP)
  • Priority Inheritance Protocol (PIP)
  • Priority Ceiling Protocol (PCP)

注:個人的な調査メモなので間違いを含んでいる可能性が大いにあります。

Non-Preemptive Protocol (NPP)

リソースを確保したタスクを最高優先度に引き上げ、他のタスクからプリエンプトされないようにする。優先度逆転やデッドロックは発生しないが、優先度の低いタスクがいつまでもリソースを取っていると、優先度の高いタスクが例えリソースを共有しないとしても、割り込む事ができないため、リアルタイム性が悪い。

Highest Locker Protocol (HLP)

リソースを確保したタスクの優先度を、NPP のように最高優先度に引き上げるのではなく、そのリソースを共有するタスクの最高優先度(上限優先度)まで引き上げる。優先度の引き上げレベルを NPP よりも弱くした感じ。

優先度逆転、デッドロックは発生しないが、最高優先度タスクが他のすべてのタスクとリソースを共有するような極端な場合、低優先度タスクでもリソースを確保した時点で最高優先度を獲得してしまうため、結局 NPP と同等になってしまう。リソースを確保したらすぐに優先度を引き上げるため、Immediate Priority Ceiling とも呼ばれる。

Priority Inheritance Protocol (PIP)

NPP, HLP はすぐに優先度を上げてしまうため、必要以上に高優先度タスクをブロックしてしまうことが問題であった。そこで、高優先度の割り込みを許可し、リソースの競合が起きた場合のみ優先度の引き上げを行う方法が PIP。遅延優先度引き上げ、みたいな。

優先度が高いタスク T1 が優先度が低いタスク T3 がロックしているリソースを取得しようとした場合、T1 はブロックされ(これを direct blocking という)、T1 ⇒ T3 の優先度の継承が行われる。つまり、T3 は T1 の優先度まで引き上げられる。途中、優先度中の T2 がアクティブになっても、T3 の優先度が勝り、T2 はブロックされる(これを push-through blocking という)。

優先度逆転は起きないが、デッドロックとブロック連鎖が発生する。ブロック連鎖(chained blocking)とは、高優先度タスクが取得するリソースを考慮せず、おかまいなしに低優先度タスクによるリソース確保を許すため、高優先度タスクがリソースを確保しようする度に、何度も優先度継承が起こり、ブロックされる状態。この状態は優先度逆転における無制限のブロック状態とは異なり、有限回で解消されるものの、必要以上のプリエンプションを引き起こしブロック時間の見積もりを困難にする。

Priority Ceiling Protocol (PCP)

優先度逆転が起きないようにするためには、高優先度タスクの処理が阻害されないように、リソースを共有している低優先度タスクのクリティカルセクションを早く抜けさせる必要がある。そのため、低優先度タスクの優先度を適切に引き上げる必要があるが、HLP では早すぎ、PIP では遅すぎだった。PCP はその折衷案。

PCP は PIP に対して、「リソースの取得を試みようとしているタスクの優先度」が「それ以外のタスクがすでに確保しているリソースの上限優先度」よりも本当に大きい場合のみ、リソースの取得を許す、という条件が加わる。PIP と同様に、リソースを確保しただけではタスクの優先度は変わらず、もし高優先度のタスクが共有リソースを取得しようとして、タスク優先度がこのリソース上限優先度を超えられない場合、高優先度のタスクはブロックされる(これを ceiling blocking という)が、そのときは PIP と同様に低優先度タスクは高優先度タスクの優先度を継承する。したがって、HLP のように不必要に高優先度タスクをブロックすることはない。

また、リソースの確保条件は上限優先度に従うことで、他のタスクが確保しているリソースを加味することに繋がるため、PIP の弱点だったデッドロックは起きない。さらに、PIP は direct blocking/push-through blocking/ceiling blocking の 3 種類のブロック条件が存在するが、ブロックされる回数は高々 1 回に収まるため、PIP で起きたようなブロック連鎖のような問題を抱える事はない。

というわけで、PCP すげーなって思いました。

ちなみに μITRON仕様書では優先度上限プロトコルPCP)を HLP の意味で使っているため、非常に混乱を招きやすいです。(というか、用語は正しい意味で使ってほしい…)

参考文献