1

優先順位の逆転はよくある、やや古い問題です。特にリアルタイム要件がある場合、OS プロセスのスケジューリングを扱った人はそれに精通しています。この問題に対するよく知られた解決策はほとんどなく、それぞれに長所と短所があります。

  • 重要なセクションを保護するためにすべての割り込みを無効にする
  • 優先度の上限
  • 優先継承
  • ランダムブースティング

優先順位の逆転に対処するためにどの方法を選択してもかまいません。アプリケーションが共有リソースを同期するために明確に定義されたインターフェイスを使用することを考えると、これらはすべて OS カーネルに比較的簡単に実装できます。たとえば、プロセスが などを使用してミューテックスをロックする場合、pthread_mutex_lockOS はその事実を十分に認識しています。これは、この関数がシステム コールを実行するためです (つまりfutex、Linux 上で)。カーネルがこの要求を処理すると、誰が何を待っているかを完全かつ明確に把握し、優先順位の逆転を最適に処理する方法を決定できます。

ここで、プロセスがいつミューテックスをロック/ロック解除しているのかをカーネルが認識していないと想像してください。これは、たとえば、アトミック CPU 命令を使用してミューテックスを実装する場合に発生する可能性があります (「ロックフリー」アルゴリズムなど)。次に、優先度の低いプロセスがロックを取得し、優先度の高いタスクのために実行が中断される可能性があります。次に、優先度の高いタスクがスケジュールされると、「スピンロック」をロックしようとして CPU を焼き尽くすだけです。そのようなデッドロックは、システム全体を役に立たなくします。

上記のシナリオと、共有リソースへのアクセスを同期するためにアトミック操作を使用しないようにプログラムを変更できないという事実を考えると、問題は、コードがそうしようとしているときにそれを検出することに要約されます。

実装が難しく、誤検知を引き起こす可能性のある、やや漠然としたヒューリスティックなアイデアがいくつかありました。どうぞ：

  1. ときどきプログラム カウンターレジスタを見て、コードがタイトなループで CPU を焼き尽くしていることを検出してみてください。コードがその場所で N 回発見された場合、プロセスを一時停止し、他の優先度の低いプロセスを実行してミューテックスのロックを解除できるようにします。この方法は理想からかけ離れており、誤検知が多すぎる可能性があります。
  2. プロセスを実行できる時間に厳密な制限を設けます。これにより、スケジューラのハード リアルタイム機能がすぐに失われますが、機能する可能性があります。ただし、問題は、「デッドロック」の場合、優先度の高いプロセスが使用中のリソースを取得しようとしてすべての時間枠を浪費することです。
  3. これが可能かどうかはわかりませんが、別のアイデアは、アトミック CPU 命令を傍受/挿入して、スケジューラにロック/ロック解除の試みを認識させることです。言い換えれば、基本的にアトミック CPU 操作をある種のシステム コールに変換します。そのメカニズムは、MMU がページ フォールトを通知したときに仮想ページ マッピングが作成される方法にいくらか近いものです。

上記のアイデアについてどう思いますか？そのようなコードを検出する他の方法を考えてみてください。

4

2 に答える 2

1

私はまだあなたの設定に疑問を抱いていますが（コメントを参照）、最も正確な情報を提供するため、3番目のアプローチが最も有望であると考えています。主なアイデアに従う2つのメカニズムを理解できます。

  1. 仮定: ロックのアドレスを知っている。システムの典型的なスピンロック パターン (例: loop: CMPXCHG <adr>, JRZ loop. 次に、 「欠落」または「アクセス不可」として
    マークし、MMU サービス ルーチンをフックします。<adr>
  2. 前提: さらに、バイナリのテキスト セグメントを変更することもできます。
    次に、通常のミューテックスまたはブックキーピングを行う独自のルーチン (実際のロックに加えて) を呼び出して、重要なスピンロックを交換できます。

ポリシーとして、副作用としてデッドロックを回避するため、優先度の継承よりも優先度の上限を優先する必要があります。とにかくスレッドの（潜在的な）ロックを知っているので、それを適用できます。

より精巧なソリューションについては、ハードウェア、OS、およびツールチェーンに関するより多くの情報が必要になります。

さらに、atomar ユーザーレベルのスピンロックを使用する基本的なアプローチは、今日のいくつかのメモリ コヒーレンス モデルでは機能しない可能性があることに注意してください。

于 2013-06-03T13:09:52.387 に答える
1

あなたのオプション1は、あなたが信用するよりもメリットがあると思います。監視が必要なプロセスがいくつかあり、スピンロックのターゲットアドレスがわからないことを前提としています。

ランダムな外部サンプリングよりも、スケジューラのエントリ ポイントをフックして、この時点で統計を収集する方が簡単な場合があります。この利点は、プロセスのアドレス空間にいて、キャッシュがホットであることです。Linux スケジューラーについてはよくわかりませんが、過去に OpenVMS でこのようなことをしたことがあります。多くの場合、スケジューラには自発的 (IO などを待機する) と非自発的の 2 つのエントリ ポイントがあり、スピン ロックの問題はほとんど常に非自発的であるため、これにより作業率が低下します。

明らかに、この時点で中断された PC がありますが、Intel チップには、使用できるパフォーマンス監視カウンター、BTS (ブランチ トレース ストア)、およびおそらく PEBS もあるようですが、これらはパフォーマンスの観点からは「無料」ではない可能性があります。分岐トレースなどの情報は、タイトなループを非常に迅速に示します。これを使用して、ループの原因となっている実際の命令をチェックし (再び、既にキャッシュ内にあります)、それが条件付きのアトミック命令であるか、配列の合計などの「通常の」作業であるかを確認できます。 .

コードを書いていない場合は、インターロックされていない命令が何らかの方法で使用されている可能性が常にありますが、そうでないことを願っています!

オンチップ監視機能のいくつかはここで本当に役立つと思いますが、PC が最後の M スケジュール期間の終わりにほぼ同じであるかどうかを確認し、1 期間をスキップするように強制することもできます。

これらすべてを 2 番目のプロセスとして実行することもできますが、スケジューラ ベースのアプローチほど応答性が高くない可能性がありますが、おそらくはるかに安全であり、システムをクラッシュさせる可能性は低くなります。いずれにせよ、スケジューラから最後の PC を取得する必要があり、2 番目のプロセスは、監視対象のプロセスよりも高いか同じ優先度である必要があります。

于 2013-06-09T06:16:20.063 に答える