c - C で条件変数を使用してプライオリティ キューを実装する

Question

条件変数に関する私の現在の理解では、すべてのブロックされた (待機中の) スレッドは基本的な FIFO キューに挿入され、その最初の項目は signal() が呼び出されたときに呼び出されます。

このキューを変更 (または新しい構造を作成) して優先キューとして実行する方法はありますか? 私はしばらくそれについて考えてきましたが、CV とミューテックスに固有の既存のキュー構造によって、私が経験した解決策のほとんどが妨げられてしまいます。

ありがとう！

Answer 1

自分が何をしようとしているのかを考え直すべきだと思います。パフォーマンスを最適化しようとしている場合は、おそらく間違ったツリーを作成している可能性があります。

pthread_cond_signal()正確に 1 つのスレッドのブロックを解除することさえ保証されていません。少なくとも1 つのスレッドのブロックを解除することが保証されているため、複数のスレッドが同時にブロック解除される状況をコードでより適切に処理できます。これを行う一般的な方法は、ブロックが解除された後に各スレッドが状態を再チェックし、false の場合は再び待機状態に戻ることです。

スレッドの独自の優先キューを待機させ、各スレッドが待機を開始する直前にそのキューに追加し、ブロック解除時にキューをチェックする、ある種のスキームを実装できますが、これは多くのことを追加します複雑であり、深刻な問題 (競合状態、デッドロックなど) が発生する可能性が高くなります。また、かなりの量のオーバーヘッドが追加されました。

また、優先順位の高いスレッドが、条件変数が通知されているのと同時に条件変数の待機を開始した場合はどうなるでしょうか? ブロック解除されるのは、新しく到着した優先度の高いスレッドですか、それとも以前の優先度の最も高いスレッドですか?

スレッドのブロックが解除される順序は、カーネルのスレッド スケジューラに完全に依存するため、それに翻弄されます。FIFOの順序付けも想定していません。

Answer 2

条件変数は基本的に単なる障壁であり、待機中のスレッドのキューを制御できないため、優先順位を適用する実際の方法はありません。待機中のスレッドが FIFO 方式で動作すると仮定するのは無効です。

アトミック、追加の条件変数、関連するスレッド/優先度の事前知識を組み合わせることで、シグナルされたスレッドがマスター CV に再シグナルし、優先度 CV で再ブロックするソリューションを構築できますが、それは確かにそうではありません。一般的な解決策ではありません。それは私の頭の上から外れているので、他の欠陥もあるかもしれません。

Answer 3

実行するスレッドを決定するのはスケジューラーです。ポリシー（、、、または）と優先順位を確認し、いじることができpthread_setschedparamます。しかし、それはおそらくあなたが行きたいと思う場所にあなたを連れて行かないでしょう。pthread_getschedparamSCHED_OTHERSCHED_FIFOSCHED_RR

本質的に非決定論的なものから何かを予測可能にしたいように聞こえます。Andrewが指摘しているように、何かをハックする可能性がありますが、これは心痛または6か月以内に書くことを嫌う多くのコード（またはその両方）につながると思います。