我一直在調查我正在執行的線程池的不同調度算法。由於我正在解決的問題的性質，我可以假設並行運行的任務是獨立的，不會產生任何新的任務。任務可以具有不同的大小。工作是否總是最合適的用戶級線程調度算法？
我馬上去了最流行的調度算法「偷工減料」，在本地工作隊伍中使用無鎖deque，而且我對這種方法比較滿意。不過，我想知道是否有任何普遍的情況下偷工減料不是最好的方法。
對於這個特定的問題，我對每個單獨任務的大小有一個很好的估計。工作竊取並沒有利用這些信息，我想知道是否有任何調度程序可以提供更好的負載平衡，而不是竊取這些信息（顯然具有相同的效率）。
注意：這個問題與之前的question有關。
我會預先分配任務。利用他們估計的運行時間的信息，您可以將它們分配到各個隊列中，爲每個線程分配一個隊列。
分配任務基本上是knapsack problem，每個隊列應該花費相同的時間量。
您應該在運行時添加一些邏輯來修改隊列。例如，在估計的運行時間與實際運行時間相差一定量之後應該進行重新分配。
另一個複雜因素，哪些可能或可能不適用，是如何處理底層並行執行框架各部分可用性的變化。當你在一個小的專用主機（或集羣）上運行時，這並不重要，但是如果大型集羣不能依賴節點，那麼這並不重要。最簡單的解決方法是重新運行調度，如果改變，並記得要重新安排已開始出現故障的節點太上運行的工作負載;做兩次工作比失去它更好。 – 2010-04-05 10:03:22
@Donal：關於節點可用性的好處，雖然在這種情況下（線程在單個進程中），我不必多想多想。 @Georg：這就是我正在考慮的。就鎖定和CAS呼叫而言，只是預先分配任務應該更便宜。我擔心的是實際負載平衡的質量。 – 2010-04-05 11:49:03
當你沒有這種擔心時很高興。 :-)不能告訴基於給出的信息，所以謝謝澄清。（我知道那些爲博士學習更普遍的問題的人，這真的很難，特別是如果你在組合中有優先級和固定的保留。） – 2010-04-05 12:52:32
這是事實，工作竊取調度程序不會使用該信息，但它是因爲它不依賴於它提供它（例如理論極限，其佔用的內存，工人的預期總的通信以及執行完全嚴格計算的預期時間，因爲您可以在這裏閱讀：http://supertech.csail.mit.edu/papers/steal.pdf）
一篇有趣的論文（我希望您可以訪問：http://dl.acm.org/citation.cfm?id=2442538）實際上使用有界執行時間來提供正式證明（試圖成爲儘量靠近原工作竊取界越好）。
是的，在某些情況下工作竊取並不能達到最佳效果（例如，不平衡的樹搜索和其他特定情況）。但是對於這些情況，已經進行了優化（例如，通過允許偷取一半受害者的deque，而不是隻採取一項任務：http://dl.acm.org/citation.cfm?id=571876）。
我對這個子目標知之甚少，但也許在這個相關問題上的一些答案將有所幫助：http://stackoverflow.com/questions/2552810/work-stealing-vs-work-shrugging – 2010-04-05 08:19:38