2つのスレッドの優先順位が同じである場合、プライオリティとFirst-Come-First Serve（FCFS）によってスレッドをスケジュールする方法を探しています。私はキューのヒープを使用することを考えていました。問題は、私自身の優先度キューを実装しても、優先度を変更する能力がこのキューへの挿入の順序を失うことです。優先順位キューの優先順位を変更して、要素の順序を維持する
この問題を解決するには、各スレッドの挿入時間を節約し、プライオリティキューを（プライマリPriorityパラメータのセカンダリパラメータとして）挿入時間でソートすることもできますが、データの組み合わせ挿入時間を使わずに問題を解決できる構造。
複雑さは、O(N)という複雑な解決策（普通のキューを持ち、スレッドをポップする必要があるたびにキューを繰り返すなど）があるはずです。
問題を正しく解決できなかった可能性がありますが、優先度ごとに別々のリストを作成することもできます。
各スレッドは、優先順位に基づいて対応するリストに追加されます。あなたは常にリストの最後に追加して頭から取り除くので、あなたはFCFSの行動を取るでしょう。
プライオリティキューを作成して、優先順位が最も低い次のスレッド（O（1）は次のスレッド、O（logN）は挿入する）を取得することもできます。それぞれのノード。
これは、可能性のある優先順位のセットが小さい場合にのみ機能します。それはおそらくここのケースですが、必ずしもそうである必要はありません。 – svick
これは、私が優先度キューを常に処理した方法です。優先度によってインデックスされたFIFOキューの配列です。私は、優先度の小さなセット以上のものは何も求めていませんでした。私は実際のスレッドの優先待ち行列を見たことはありませんでした。ただ、タスク（まあ、OK、それらを見たマルチスレッドOSカーネルの中にあります）。 –
ありがとうございます。私は実際に優先順位の小さなセットを持っています。私があなたの解決策を理解していれば、スレッドの優先順位を変更することで、新しい優先順位のリストの最後にそれを置きます。これはスレッドの挿入順序を保存したい（と優先順位の変更は挿入時間をリセットしない）良いbeacauseではありません。 – Lior
OSカーネルの場合、私は各スレッドの挿入時間を節約しようとするのではなく、多大な労力を要しません。あるスレッドからスレッドを削除し、別のスレッドにスレッドを移動します。優先順位が上がった場合は、スレッドを先頭に置きます（スレッドが減少した場合は末尾に配置します）優先度の高いキューを作成し、下向きに作業し、通常の方法でスレッドをプロセッサに割り当てる方法を決定します。 –
本当に今混乱しています:(スレッドに追加されたスレッドは0の時間を持つことが保証されています - それはちょうど今挿入されているので、キューの後ろに行くべきです。以前のキューからの挿入時間を使用することはできましたが、スレッドは直前のキューから移動されていた可能性があります。この要件を取得せず、解決しようとしているものが想像できません。それについてもう少し考える必要があります... –
挿入時間を節約することによって、実際に時間を節約することを意味するのではなく、カウンターを持って、実行準備ができたら各スレッドにタイムスタンプを与えるスレッドをタイムスタンプで順序付けることができます。あまりにも費用がかかりますか？ – Lior