在條件變量中實現一個優先級隊列C

Question

我當前對條件變量的理解是所有被阻塞的（等待的）線程都被插入到一個基本的FIFO隊列中，當signal（）被調用時，第一個隊列被喚醒。

有沒有什麼辦法可以修改這個隊列（或創建一個新的結構）來執行優先級隊列呢？我一直在考慮這個問題，但大多數解決方案最終都受到C.V.和互斥體固有的隊列結構的阻礙。

謝謝！

Answer 1

我認爲你應該重新考慮你想要做的事情。如果你試圖優化你的表現，你可能會吼出錯誤的樹。

pthread_cond_signal()甚至不保證準確解鎖一個線程 - 它保證疏通至少一個線程，因此能夠處理多個線程暢通，同時這種情況你的代碼更好。執行此操作的典型方法是，每個線程在解鎖後重新檢查條件，如果爲false，則返回到等待。

你可以實現某種方案，讓你保持自己的線程優先級隊列在等待，並且每個線程在它開始等待之前立即將自己添加到該隊列中，然後在解除阻塞時檢查隊列，但是這樣做會增加很多複雜性和很大的潛在嚴重問題（比賽條件，死鎖等）。這也增加了一筆不小的開銷。

此外，如果優先級更高的線程在條件變量被髮送信號的同時開始等待條件變量，會發生什麼情況？誰獲得暢通，新到達的高優先級線程或以前的最高優先級線程？

線程得到解鎖的順序完全取決於內核的線程調度程序，所以你是在仁慈的。我甚至不會承擔FIFO排序。

Answer 2

由於條件變量基本上只是一個障礙，您無法控制等待線程的隊列，因此沒有真正的方法來應用優先級。假設等待的線程以FIFO的方式工作是無效的。

利用原子，附加條件變量和預先知道的線程/優先級，您可以構建一個解決方案，其中一個信號線程將重新發信號通知主CV，然後重新阻塞優先級CV，但它當然不會是一個通用的解決方案。這也是我的頭頂，所以也可能有其他缺陷。

Answer 3

調度程序確定哪個線程將運行。您可以查看pthread_setschedparam和pthread_getschedparam，並查看策略（SCHED_OTHER,SCHED_FIFO或SCHED_RR）和優先級。但它可能不會讓你到我懷疑你想去的地方。

聽起來好像你想從固有的非確定性中做出某些可預測的事情。正如Andrew所說，你可能會破解一些東西，但我的猜測是，這會導致心痛或者很多代碼，你會在六個月（或兩者）中討厭自己編寫代碼。