こんにちは、ナナです。
「セマフォ」や「ミューテックス」を利用した排他制御について解説してきました。
セマフォによる排他制御では、実は「優先度逆転問題」と呼ばれる問題が潜んでいます。
優先度逆転問題とはいったい何なのか？それをどのように防ぐのか？を解説していきましょう。
本記事では次の悩みを解消する内容となっています。
それでは、「優先度逆転問題」を解説しましょう！
セマフォによる優先度逆転問題とは？
はい、はーい！何やら僕の使った「セマフォ」にはとんでもない問題が潜んでいるとの密告がありました。
い、い、いったいどんな問題があるのでしょうか・・・眠れない。
「優先度逆転問題」のことだね。心配しなくても誰の身にも降りかかる問題だから、気に病むことはないよ。
それじゃあ、まずはどんな問題なのかを教えようね。
「優先度が逆転する」という問題です。もちろん、この優先度とは「タスク優先度」のことですね。
これが逆転するとはどういうことなのか、その理由を解説していきましょう。
振り返り：マルチタスクにおける優先度ベーススケジューリング
ITRONでは「優先度ベーススケジューリング」と呼ばれる方式で、タスク優先度を元に動作順を決定しています。
例えば、次のように３つのタスクが存在していたとしましょう。
「タスク」とは仕事人であり、仕事内容に応じて緊急度が異なります。より緊急度の高い仕事人はタスク優先度が高く設定されます。
優先度ベースのスケジューリングにおいて優先度の低いタスクは、優先度が高いタスクが動いていない時にしか仕事ができません。
逆に言うと、優先度の高いタスクが動く必要性があれば、優先度の低いタスクは即座に「実行権」をお譲りするというルールなのです。
これが、タスク優先度をベースとしたスケジューリングです。
このスケジューリングはRTOSにおいて最も基本となるスケジューリング知識です。絶対に覚えておきましょう！
セマフォの排他制御によるタスク優先度の逆転現象の基礎
それでは「バイナリセマフォ」を使った排他制御の要素を加えてみましょう。
新人タスクはコピー機で印刷する仕事を頼まれました。100部の印刷が必要なため、時間が掛かります。そして、使用している間は他の人はコピー機は使えなくなります。
つまり、コピー機は排他資源ということになります。
この状態で、優先度の高い社長タスクがコピー機を使いたい用事ができました。しかし、コピー機は新人タスクに使われています。
社長と言えども、先に資源を取られている状態でコピー機を奪い取ることはできません。つまり、この排他区間においては、新人の方が社長よりも優先して動くことになります。
ここで「無理やり社長が資源を奪えばいいのでは？」と、思う方がいるかもしれませんが、それでは排他区間の意味がないのです。
途中で資源を奪わせないことこそが「排他制御」なのです。
これがまず抑えるべき、優先度逆転の基礎です。
排他制御とは、時にはタスク優先度を上回る可能性を秘めているということになります。
優先度逆転が引き起こす本当の問題
先ほどの例は、2つのタスク間において排他資源が競合する場合は、時に優先度が逆転しているように動くということでした。
この動き自体は「排他制御」というものの本質を考えると、受け入れるべき動きです。
しかし、一般的な「優先度逆転問題」とは、もう少し複雑な３つ以上のタスクになると発生する問題なのです。その現象を解説しましょう。
先ほどからの続きのストーリーです。
コピー機で作業していた新人に、新人よりも優先度の高い上司が雑談をしに来ました。上司は優先度が高いわけですから「実行権」を奪われます。
上司の雑談に付き合うのも新人の役目と割り切り、新人は耳を傾けます。そうするとコピーする作業の手が止まり、なかなか仕事が終わりません。
社長と新人の関係性では排他資源の競合が起きているので、優先度が逆転するのは仕方のないことです。
しかし、社長と上司の関係性では、排他資源の競合が起きていないわけですから、本来は社長の仕事が優先なのです。
しかし、新人のコピー作業は上司の雑談が終わるまで手が付けられず、結果的に社長の仕事が止まるのです。
このような３つタスクの関係性が成立してしまうと、緊急度の高い社長が延々と待たされることになるのです。
これが「優先度逆転問題」です。
「セマフォ」による排他制御は、この問題を常に抱えることになります。
タスクをたくさん作っているシステムでは、実はこのような逆転現象が気づかないところで発生してたりします。
火星探査機マーズ・パスファインダーで、この問題が発生したこともあるそうです。
ミューテックスによる優先度逆転問題の解決方法
これが「優先度逆転問題」。火星探査機なんてものすら故障しかねない問題になるだなんて・・・、なんて恐ろしい。
もうダメだ、絶望だ。いったい、この問題に僕はどう立ち向かえばいいって言うんですかっ！
そんなに絶望しなくてもいいよ。この問題は「ミューテックス」を使うことで解決するんだよ。
「セマフォ」と「ミューテックス」による排他制御の方法をここまで解説してきました。
「セマフォ」は排他の専門家ではないため、様々な問題を抱えています。
しかし、「ミューテックス」は排他の専門家であるがゆえに、この「優先度逆転問題」をも解決するのです。
その方法を解き明かしていきましょう。
ミューテックスの「優先度上限プロトコル」による解決方法
ミューテックスが提供するプロトコルのひとつが「優先度上限プロトコル」です。
優先度上限プロトコルは、ミューテックスオブジェクトの生成時に「上限優先度」を付与するのが特徴です。
この「上限優先度」の決め方は、対象ミューテックスをロックするタスクにおいて最大優先度の値を設定します。
これで前準備が整いました、セマフォの時と比べてどのような違いが出るかを見ていきましょう。
再び新人がコピー機を使ったコピー作業を行うことになりました。今度は「ミューテックス」を利用してロックを行います。
「優先度上限プロトコル」では、ロックを行った瞬間からタスク優先度が「上限優先度」に変化することになります。
この状態でいつものように、上司が雑談をしようと近づいてきました。
しかし、上限優先度まで引き上げられた新人は、上司に実行権を奪われることなく仕事を進めることができるのです。
これが「優先度上限プロトコル」による優先度逆転の解決原理です。
「優先度上限プロトコル」の扱いの難しさは、上限優先度の値を決定することです。
大規模システムになると、メンテナンス工程も大変で、タスク優先度を途中で変更することもあります。その際に上限優先度も合わせて管理することは現実的にはかなり難しいと言えます。
ミューテックスの「優先度継承プロトコル」による解決方法
ミューテックスが提供するもうひとつのプロトコルが「優先度継承プロトコル」です。
優先度継承プロトコルの良さは、「上限優先度」を指定する必要がないことです。これはすごく便利な構造です。
それではいつも通り、新人がコピー作業を行います。
優先度上限プロトコルと異なり、「優先度継承プロトコル」ではこの時点で特にタスク優先度に変化を与えないのが特徴です。
この後、上司がまた雑談をしにやってきました。
この時点ではタスク優先度が低いため新人タスクの実行権は上司に奪われてしまいます。
ここからが「優先度継承プロトコル」の出番です。
社長が緊急でコピー機を使うためにやってきました。もちろんミューテックスをロックしますが、すでにロック済みのため社長タスクはアンロック待ち状態になります。
ここで、ようやく「優先度継承プロトコル」が発動します。
社長がアンロック待ちに入ったため、新人はタスク優先度を社長の優先度まで引き上げることが許されます。
つまり、優先度の高い社長が待っているのだから、その時の新人は社長と同じ優先度であるべきという考え方です。
引き上げられるタスク優先度の値は、待っているタスクの優先度となります。これこそが「上限優先度」を指定する必要がない理由です。
優先度が高いタスクがアンロック待ちになったタイミングで発動するのが特徴です。無駄がなくて効率的ですね。
タスク優先度が自動的に変化するため、優先度継承プロトコルは運用面でも優秀です。このプロトコルは必ず有効にしておきましょう！
優先度逆転問題のまとめ
それでは優先度逆転問題を振り返りましょう。
- 排他資源によって、タスク優先度が時に逆転して動くことがある
- セマフォを利用した排他制御では「優先度逆転問題」が起こる
- 「優先度逆転問題」を解決するにはミューテックスを使って排他制御を行う
- 「優先度上限プロトコル」と「優先度継承プロトコル」で解決できる
- 「優先度継承プロトコル」は優秀であり、有効化しておくとよい
ここまではタスク間の排他制御でした。RTOSにおいて労働者とはタスクと割り込みの２者が存在します。タスクと割り込みとの排他制御について学びましょう！
