任務委託調度

Question

我實現了調度程序任務委託調度程序而不是任務竊取調度程序。所以這種方法的基本思想是每個線程都有自己的私有本地隊列。每當任務產生時，在任務被排隊到本地隊列之前，在這些隊列之間進行搜索操作，並且通過比較每個隊列的大小來找到最小大小隊列。每次使用這個最小大小的隊列來排隊任務。這是一種將工作壓力從繁忙線程的隊列中轉移出來並將作業委派給最不忙碌的線程隊列的方法。

這個調度技術的問題是，我們不知道每個任務需要多少時間才能完成。即。隊列的計數可能最小，但任務可能仍在運行，另一方面，隊列可能具有較高的值計數器，但任務可能會很快完成。任何想法來解決這個問題？

我正在使用Linux，C++編程語言在我們自己的多線程庫中實現一個多速率同步數據流範例。

Answer 1

據我記得，從我的排隊理論類最公平（他們所有;）系統是有一個單一的隊列和多個服務器。使用這樣的系統可以確保所有任務的平均預期執行時間最低，最大的利用率（工作時間的百分比，我不確定該術語是否正確）。

換句話說，除非您有一些優先級任務，否則請重新考慮您的任務委託調度程序實現。

Answer 2

看來你的調度策略不適合手頭的工作。通常，這種忽略任務完成時間的樸素調度只有在任務執行時間相對相等時纔有意義。 我建議做一些研究。開始的好地方是Wikipedia's Scheduling article，但這當然只是冰山一角。 我還想給任務委託要求提供第二個（和第三個）想法，因爲時間片任務操作允許您通過考慮任務的「歷史」來細化隊列管理。但是，如果客戶端的設計使每個客戶端始終發送相同的「類型」任務，那麼您可以憑藉此知識獲得類似的結果。