本文へ移動
雑学書庫好奇心が集まる場所
日本語

急ぎの仕事ほど後回し、優先度逆転(Priority Inversion)

その日いちばん急ぎの会議を控えたチームリーダーが、会議室の鍵を待っています。ところが鍵を持つ新入社員は、ほかの先輩たちの細かい用事に次々と呼ばれ、なかなか会議室を空けられません。いちばん大事な仕事がいちばん後回しになるこの奇妙な状況は、コンピューターの中でもまったく同じように起こり、「優先度逆転(Priority Inversion)」と呼ばれます。

優先度逆転とは、簡単に言えば「優先度の高いタスクが、優先度の低いタスクが握っている共有資源を待つうちに、事実上さらに低い順位へ押し下げられてしまう現象」を意味します。複数のタスクが決められた優先度に従ってプロセッサーを分け合うリアルタイムシステムで古くから知られる問題で、1997年に火星探査機マーズ・パスファインダー(Mars Pathfinder)が火星で再起動を繰り返す事故を起こしたことで広く知られるようになりました。

本稿では、優先度逆転が起こる過程、三つのタスクで見る仕組み、火星で実際に起きたパスファインダー事件、そしてそれを防ぐ方法と教訓までを順に見ていきます。


高い優先度が低い優先度を待つとき

1. 優先度逆転はどのように起こるのか

赤い土と石が散らばる火星の平原で、花びらのようにパネルを広げた着陸機の前に、車輪の跡を残した六輪の小型探査ローバーが立っている様子

優先度スケジューリングでは、実行準備のできたタスクのうち最も優先度の高いものが、常に先にプロセッサーを使います。この単純なルールが揺らぐのは、複数のタスクが同じ資源を共有するときです。

(1)共有資源とロック
複数のタスクが同じメモリーや装置を同時に書き換えると、データが壊れてしまいます。そこでオペレーティングシステムはミューテックス(Mutex)のようなロックを置き、一度に一つのタスクだけが資源を使えるようにします。先にロックを取ったタスクは、優先度に関係なく、仕事を終えてロックを解放するまで資源を独占します。

(2)高優先度タスクの待機
低優先度タスクがロックを握っているときに高優先度タスクが同じ資源を求めると、高優先度タスクはロックが解放されるまで止まらなければなりません。低優先度タスクが短いクリティカルセクションを終えればすぐに解放されるため、この程度の待ちはあらかじめ計算できる「有界な逆転」です。

(3)中優先度タスクの割り込み
本当の問題は、その間にロックと関係のない中優先度タスクが目を覚ましたときに起こります。中優先度タスクは低優先度タスクより優先度が高いのでプロセッサーを奪い、低優先度タスクはロックを握ったまま止まります。結局、高優先度タスクは自分より優先度の低い中優先度タスクが終わるまで待つことになり、中優先度タスクが多ければ待ち時間は際限なく延びていきます。


2. 三つのタスクで見る仕組み

緑の野原の間にある狭い一車線の古い石橋を古いトラクターがゆっくり渡り、橋の手前の道で赤いスポーツカーが止まって待っている様子

優先度逆転は、ふつう高・中・低の三つのタスクで説明します。優先度だけを見れば高優先度タスクが最初に終わるはずですが、ロックが一つ絡むだけで実際の実行順序がひっくり返ります。

優先度逆転(Priority Inversion)の発生と解決のインフォグラフィック:低優先度タスクがロックを保持、高優先度タスクは待機、中優先度タスクが割り込み、優先度継承で一時的に上昇しすぐ実行
低優先度タスクが握るロックのせいで高優先度タスクは中優先度タスクより遅れて終わりますが、優先度継承を使えば低優先度タスクが一時的に優先度を上げ、すばやくロックを解放します。
  • 優先度スケジューリング(Priority Scheduling):タスクごとに優先度を付け、実行準備のできたタスクのうち最も優先度の高いものから処理する方式です。高優先度タスクが目を覚ますと、低優先度タスクを止めてプロセッサーを引き継ぎます。
  • ミューテックス(Mutex):相互排除(Mutual Exclusion)を縮めた言葉で、一度に一つのタスクだけが共有資源を使えるようにするロックです。
  • クリティカルセクション(Critical Section):ロックを握ったまま共有資源を扱うコードの区間です。短いほど、ほかのタスクが待つ時間も短くなります。
  • 有界な逆転と無界な逆転(Bounded and Unbounded Inversion):高優先度タスクが低優先度タスクのクリティカルセクションの分だけ待つなら有界な逆転、中優先度タスクまで割り込んで待ち時間の上限が決められなくなれば無界な逆転といいます。

リアルタイムシステムで恐ろしいのは無界な逆転です。決められた時間内に必ず終わらなければならないタスクが、いつ終わるのか分からなくなるからです。見た目にはすべてのタスクがルールどおり優先度を守っているのに、全体の結果は優先度がひっくり返ったように現れる点が、この問題を見つけにくくしています。


3. 火星で起きたパスファインダー事件

明るい実験室の金属製作業台の上に、太陽電池パネルを載せた六輪の探査ローバー試験モデル、緑の回路基板、開いた機材ケース、ケーブルの束が置かれている様子

優先度逆転を世界に最も広く知らせた出来事は、火星で起こりました。1997年7月4日に火星に降り立ったアメリカ航空宇宙局(NASA)のマーズ・パスファインダーは、着陸の数日後からシステム全体が突然再起動する問題に見舞われました。

(1)繰り返す再起動
パスファインダーのコンピューターは、ウインドリバー(Wind River Systems)のリアルタイムOS、VxWorksで動いていました。問題は、探査機が気象データを集め始めたころから現れました。再起動が起こるとその日に予定していた作業が翌日に持ち越されるため、地球の運用チームは急いで原因を突き止める必要がありました。

(2)地球で再現した原因
ジェット推進研究所(JPL)のチームは、地球の試験装置で記録機能をオンにしたまま同じ状況を走らせ、18時間足らずで再起動をもう一度起こすことに成功しました。原因は教科書どおりの優先度逆転でした。低優先度の気象データタスクがロックを握っている間に中優先度タスクが実行され、そのロックを待っていた高優先度の情報バス管理タスクが決められた周期内に終われなかったのです。これを見つけた上位の管理タスクが深刻なエラーと判断し、再起動を起こしたのでした。

(3)グローバル変数一つで直した遠隔修正
問題のロックは、性能上の理由から優先度継承機能がオフになった既定の設定で作られていました。チームはこの機能をオンにするためにグローバル変数一つの値を変える修正を火星の探査機へ送り、問題を解決しました。この件は同じ年の12月にリアルタイムシステムの学会で紹介されて広く知られ、飛行ソフトウェアの責任者グレン・リーブス(Glenn Reeves)も自ら経緯を説明しました。


4. 優先度逆転を防ぐ方法

朝日が差し込む古い木のテーブルの上に、つるの開いた真ちゅうの南京錠と真ちゅうの鍵が一本置かれている様子

ロックを使う限り優先度逆転を完全になくすことは難しいものの、待ち時間が際限なく延びることは防げます。代表的な解決策は、1990年にLui Sha、Ragunathan Rajkumar、John Lehoczkyが発表した優先度継承プロトコル(Priority Inheritance Protocols)の論文にまとめられています。

(1)優先度継承
高優先度タスクがロックを待ち始めたら、ロックを握る低優先度タスクの優先度を一時的に高優先度タスクと同じにまで上げます。すると中優先度タスクは割り込めず、低優先度タスクはクリティカルセクションをすばやく終え、ロックを解放するとすぐ元の優先度に戻ります。パスファインダーを救ったのがまさにこの方法です。

(2)優先度上限プロトコル
ロックごとに、そのロックを使う可能性のあるタスクのうち最も高い優先度を「上限」として決めておく方式です。同じ論文で提案されたこの方法は、最大の待ち時間をあらかじめ計算できるようにし、ロック同士が互いにかみ合って止まってしまうデッドロックも防ぎます。

(3)設計から得られる教訓
ロックを握る区間を短くし、優先度の大きく異なるタスクが同じ資源を共有しないように設計することも大切です。今日では多くのリアルタイムOSやLinuxも、優先度継承に対応したロックを提供しています。パスファインダーの事例は、既定の設定を一つ確かめることや、問題を再現できる記録機能を残しておくことがどれほど重要かも示しています。

「急ぎの仕事をふさいでいる遅い仕事を少し後押しして、先に終わらせる」という単純な考え、それが優先度逆転を理解する第一歩です。

この記事をPDFで手元に

今読んでいる記事の、選択した言語の版を購入できます。

US$1.00
選択中の言語: 日本語

US$1.00 · 1記事・1言語

購入方法を選んでください

会員として購入
  • どの端末でもログインすれば再ダウンロードできます
  • 購入履歴に保存されます
会員登録せずに購入
  • 登録不要ですぐに支払えます
  • このブラウザで再ダウンロードできます
  • 他の端末では、購入後に表示される専用リンクを使います
  • 後でこのブラウザで会員としてログインすると、購入がアカウントに移ります
  • リンクをなくし、ブラウザのCookieを削除すると再ダウンロードできない場合があります

購入履歴を確認しています…

販売者情報

商号
아카이지
代表者
안호원
事業者登録番号
530-02-04118
通信販売届出番号
2026-경기군포-0626
届出先
경기도 군포시
事業所所在地
경기도 군포시 산본천로 119-9, 1109동 405호 (산본동, 주공아파트)
ホスティング提供者
카페24(주)
お問い合わせメール
sgjjojo@gmail.com
お問い合わせ電話番号
010-4194-0821

事業者情報の確認(韓国公正取引委員会)