76

オペレーティングシステムの開発に関して、「優先順位の逆転」というフレーズを聞いたことがあります。

優先順位の逆転とは正確には何ですか？

それが解決しようとしている問題は何ですか、そしてそれはどのようにそれを解決しますか？

4

11 に答える 11

74

優先度の異なる3つのタスク（tLow、tMed、tHigh）を想像してみてください。tLowとtHighは、異なる時間に同じ重要なリソースにアクセスします。tMedは独自のことを行います。

  1. tLowは実行中であり、tMedとtHighは現在ブロックされています（ただし、クリティカルセクションではありません）。
  2. tLowがやって来て、クリティカルセクションに入ります。
  3. tHighはブロックを解除し、システムで最も優先度の高いタスクであるため、実行されます。
  4. 次に、tHighは重要なリソースに入ろうとしますが、tLowがそこにあるためブロックします。
  5. tMedはブロックを解除し、システムで最も優先度の高いタスクであるため、実行されます。

tHighは、tLowがリソースを放棄するまで実行できません。tLowは、tMedがブロックまたは終了するまで実行できません。タスクの優先順位が逆になりました。tHighは最優先ですが、実行チェーンの最下部にあります。

優先順位の逆転を「解決」するには、tLowの優先順位を少なくともtHighと同じ高さまで上げる必要があります。優先度を可能な限り高い優先度レベルに上げる場合もあります。tLowの優先度を上げるのと同じくらい重要なのは、適切なタイミングでtLowの優先度を下げることです。システムが異なれば、アプローチも異なります。

tLowの優先度を下げるタイミング..。

  1. tLowが持つリソースで他のタスクがブロックされることはありません。これは、タイムアウトまたはリソースの解放が原因である可能性があります。
  2. tLowの優先度レベルの引き上げに寄与する他のタスクは、tLowが持つリソースでブロックされません。これは、タイムアウトまたはリソースの解放が原因である可能性があります。
  3. タスクがリソースを待機している変更がある場合は、tLowの優先度を下げて、そのリソースでブロックされている最高の優先度レベルのタスクの優先度と一致させます。

方法＃2は、tLowの優先度が上昇するまでの時間を短縮するという点で、方法＃1を改善したものです。この期間中、その優先度レベルはtHighの優先度レベルで上昇したままであることに注意してください。

方法3では、tLowの優先度レベルを、1つのオール・オア・ナッシング・ステップではなく、必要に応じて段階的に下げることができます。

システムが異なれば、重要と考える要素に応じて異なる方法が実装されます。

  • メモリフットプリント
  • 複雑
  • リアルタイムの応答性
  • 開発者の知識

お役に立てれば。

于 2010-11-23T15:22:43.983 に答える
64

優先順位の逆転は問題であり、解決策ではありません。典型的な例は、低優先度のプロセスが高優先度のプロセスが必要とするリソースを取得し、次に中優先度のプロセスによってプリエンプトされるため、中優先度のプロセスが終了する間、高優先度のプロセスはリソースでブロックされます（事実上、優先度が低い）。

かなり有名な例は、マーズパスファインダーローバーが経験した問題でした：http ：//www.cs.duke.edu/~carla/mars.html 、それはかなり興味深い読み物です。

于 2010-11-23T02:31:45.407 に答える
22

アプリケーションに3つのスレッドがあるとします。

Thread 1 has high priority.
Thread 2 has medium priority.
Thread 3 has low priority.

スレッド1とスレッド3が同じクリティカルセクションコードを共有していると仮定しましょう

例の最初では、スレッド1とスレッド2がスリープしているかブロックされています。スレッド3が実行され、クリティカルセクションに入ります。

その時点で、スレッド2の優先度が高いため、スレッド2が実行を開始し、スレッド3をプリエンプトします。したがって、スレッド3は引き続きクリティカルセクションを所有します。

その後、スレッド1が実行を開始し、スレッド2をプリエンプトします。スレッド1は、スレッド3が所有するクリティカルセクションに入ろうとしますが、別のスレッドが所有しているため、スレッド1はクリティカルセクションを待機します。

その時点で、スレッド2はスレッド3よりも優先度が高く、スレッド1が実行されていないため、実行を開始します。スレッド2は実行を継続するため、スレッド3はスレッド1が待機しているクリティカルセクションを解放しません。

したがって、システム内の最も優先度の高いスレッドであるスレッド1はブロックされ、優先度の低いスレッドが実行されるのを待ちます。

于 2013-10-01T22:45:18.577 に答える
18

それは解決策ではなく問題です。

これは、優先度の低いスレッドが作業中にロックを取得するときに、優先度の高いスレッドが終了するのを待たなければならない状況を説明しています（優先度が低いため、特に時間がかかる場合があります）。ここでの反転は、優先度の高いスレッドは優先度の低いスレッドが続行するまで続行できないため、実際には優先度も低くなっています。

一般的な解決策は、優先度の低いスレッドに、保持しているロックを待機しているすべての人の優先度の高いスレッドを一時的に継承させることです。

于 2010-11-23T02:27:42.703 に答える
5

[仮定、低プロセス= LP、中プロセス= MP、高プロセス= HP]

LPはクリティカルセクションを実行しています。クリティカルセクションに入るときに、LPはOBJなどのオブジェクトのロックを取得している必要があります。LPはクリティカルセクション内にあります。

その間に、HPが作成されます。優先度が高いため、CPUはコンテキストスイッチを実行し、HPは現在実行中です（同じクリティカルセクションではなく、他のコード）。HPの実行中のある時点で、同じOBJのロックが必要になります（同じクリティカルセクションにある場合とない場合があります）が、クリティカルセクションの実行中にプリエンプトされたため、OBJのロックはLPによって保持されます。 。プロセスが実行中ではなく準備完了状態にあるため、LPは現在放棄できません。これで、HPはBLOCKED/WAITING状態に移行します。

これで、MPが入り、独自のコードを実行します。MPはOBJをロックする必要がないため、正常に実行され続けます。HPはLPがロックを解放するのを待ち、LPはMPが実行を終了するのを待って、LPがRUNNING状態に戻ることができるようにします（..そしてロックを実行して解放します）。LPがロックを解放した後でのみ、HPはREADYに戻ることができます（次に、優先度の低いタスクをプリエンプトしてRUNNINGに戻ります）。

つまり、事実上、MPが終了するまで、LPは実行できず、したがってHPは実行できません。したがって、OBJロックを介して直接関連付けられていなくても、HPはMPを待機しているようです。->優先順位の逆転。

優先順位の逆転の解決策は優先度継承です-

プロセス（A）の優先度を、Aがリソースロックを持っているリソースを待機している他のプロセスの最大優先度に上げます。

于 2014-12-16T06:19:00.927 に答える
3

非常に単純明快にしましょう。（この回答は上記の回答に基づいていますが、鮮明な方法で提示されています）。

リソースRと3つのプロセスがあるとします。L、、。M_ Hここでp(L) < p(M) < p(H)（p(X)はの優先順位ですX）。

言う

  • L最初に実行を開始し、をキャッチしますR。（への排他的アクセスR）
  • H後で来て、それを保持しているので、それRへの排他的アクセスも望んでいるので、待たなければなりません。LH
  • M後に来るHとそれは必要ありませんR。そして、M実行したいすべてのものを持っているのでL、に比べて優先度が高いため、強制的に終了しLます。ただし、実行に必要なHリソースがロックされているため、これを行うことはできません。L

問題をより明確にしたので、実際には、それが起こらなかったので完了するのMを待つ必要があり、これ自体が問題です。のような多くのプロセスがやって来て、の実行と解放を許可しない場合、ロックは実行されません。タイムクリティカルなアプリケーションでは危険な場合がありますHp(H) > p(M)MLH

そして解決策については上記の答えを参照してください:)

于 2017-09-02T04:56:38.793 に答える
2

優先順位の逆転とは、優先順位の低いプロセスが優先順位の高いプロセスが必要とするリソースを取得し、リソースが解放されるまで優先順位の高いプロセスが続行できないようにすることです。

例：FileAはProc1とProc2からアクセスする必要があります。Proc 1はProc2よりも優先度が高くなりますが、Proc2は最初にFileAを開くことができます。

通常、Proc1はProc2の10倍の頻度で実行されますが、Proc2がファイルを保持しているため、何も実行できません。

したがって、最終的に発生するのは、Proc2がFileAで終了するまで、Proc1がブロックすることです。基本的に、Proc2がFileAのハンドルを保持している間、それらの優先順位は「反転」されます。

「問題の解決」に関する限り、優先順位の逆転は、それが継続して発生する場合、それ自体が問題になります。最悪のケース（ほとんどのオペレーティングシステムではこれが発生しません）は、Proc1が実行されるまでProc2の実行が許可されなかった場合です。これにより、Proc1が割り当てられたCPU時間を取得し続けるため、システムがロックされ、Proc2がCPU時間を取得することはないため、ファイルが解放されることはありません。

于 2010-11-23T02:24:54.147 に答える
1

優先順位の逆転は次のように発生します。名前が高、中、低の優先順位を表すプロセスH、M、およびLが与えられた場合、HとLのみが共通のリソースを共有します。

たとえば、Lは最初にリソースを取得し、実行を開始します。Hもそのリソースを必要とするため、待機キューに入ります。Mはリソースを共有せず、実行を開始できるため、共有します。Lが何らかの方法で割り込みをかけられると、Mは優先度が高く、割り込みが発生した瞬間に実行されるため、実行状態になります。HはMよりも優先度が高いですが、待機キュー上にあるため、リソースを取得できず、Mよりも優先度が低くなります。Mが終了すると、Lが再びCPUを引き継ぎ、Hがずっと待機します。

于 2013-11-04T22:12:37.387 に答える
0

ブロックされた高優先度スレッドが、リソースを保持している低優先度スレッドに高優先度を転送する場合、優先度の逆転を回避できます。

于 2015-07-28T16:34:22.997 に答える
0

スケジューリングの課題は、優先度の高いプロセスが、優先度の低いプロセスまたは一連のプロセスによって現在アクセスされているカーネルデータを読み取ったり変更したりする必要がある場合に発生します。カーネルデータは通常、ロックで保護されているため、優先度の高いプロセスは、優先度の低いプロセスがリソースを終了するまで待機する必要があります。優先度の低いプロセスが優先され、優先度の高い別のプロセスが優先される場合、状況はさらに複雑になります。例として、優先順位がL <M <Hの順序に従う3つのプロセス（L、M、およびH）があるとします。プロセスHには、現在プロセスLによってアクセスされているリソースRが必要であると想定します。通常、プロセスHは次のようになります。 LがリソースRの使用を終了するのを待ちます。ただし、プロセスMが実行可能になり、プロセスLがプリエンプトされると仮定します。間接的に、優先度の低いプロセス（プロセスM）は、プロセスHがLがリソースRを放棄するのを待機する時間に影響します。この問題は優先度の逆転と呼ばれます。これは、優先度が2つを超えるシステムでのみ発生するため、1つの解決策があります。ただし、ほとんどの汎用オペレーティングシステムでは、これでは不十分です。通常、これらのシステムは、優先度継承プロトコルを実装することで問題を解決します。このプロトコルによれば、優先度の高いプロセスが必要とするリソースにアクセスしているすべてのプロセスは、問題のリソースが終了するまで優先度が高くなります。終了すると、優先度は元の値に戻ります。上記の例では、優先度継承プロトコルにより、プロセスLはプロセスHの優先度を一時的に継承できます。これにより、プロセスMがその実行をプリエンプトするのを防ぎます。プロセスLがリソースRの使用を終了すると、継承された優先度をHから放棄し、元の優先度を引き継ぎます。リソースRが使用可能になるため、次にプロセスH（Mではなく）が実行されます。参照：ABRAHAM SILBERSCHATZ

于 2016-03-05T10:22:14.537 に答える
0

H優先度の高いプロセスLと低いプロセスの2つのプロセスがあるシステムについて考えてみます。スケジューリングルールはH、優先度が高いため、準備完了状態のときに実行されるようなものです。ある時点でL、その重要な領域で、H実行の準備が整います（たとえば、I / O操作が完了します）。H現在、ビジーウェイトを開始しますが、実行L中にスケジュールが設定されることはないため、クリティカルセクションを離れる機会はありません。したがって、永遠にループします。 HLH

この状況はと呼ばれPriority Inversionます。優先度の高いプロセスが優先度の低いプロセスを待機しているためです。

于 2017-08-20T08:20:46.110 に答える