某些給定任務的最佳任務調度算法是什麼？

Question

我們有不同長度的任務列表,一些CPU核心和a上下文切換時間。 我們希望在覈心之間找到最佳的任務調度，以最大化處理器利用率。 我們怎麼能找到這個？ 是不是就像我們從列表中選擇最大的可用任務並將它們逐一提供給當前就緒核心，這將會是最好的，或者您認爲我們必須嘗試所有的命令以找出哪個是最好的？

我必須補充說，所有內核都準備好在時間單元0，任務應該同時工作。

Answer 1

這裏的想法是，沒有銀彈，你必須考慮什麼是正在執行的任務類型，並儘量安排它們儘可能好。

• CPU密集型任務不使用多通信（I/O），因此，需要被連續地執行，並且中斷只在必要時 - 根據正在使用的策略;

• I/O綁定任務可能會在執行過程中不斷放在一邊，允許其他進程工作，因爲它會在很多時間段內等待數據檢索到主存儲器;

• 交互任務必須連續執行，但不需要中斷執行，因爲它會產生中斷，等待用戶輸入，但它需要具有高優先級，以免讓用戶注意到延遲在執行中。

考慮到這一點，和上下文切換成本，您必須評估哪些類型你的任務，選擇，因此，一個或多個對您的調度策略。

編輯：

我認爲這是一個簡單的概念上的問題。考慮到您必須實施解決方案，您必須分析需求。

由於您具有任務的長度和上下文切換時間，並且必須維持內核繁忙，所以這成爲一個優化問題，您必須在內核達到過程，但是您需要保持最少的上下文切換次數，以便您的總體執行時間不會增長太多。

正如svick所指出的，這聽起來像是一個分區問題，它是NP完全的，並且需要將一系列數字分成給定數量的列表，這樣每個列表的總和等於彼此。

在你的問題中，你會放鬆目標，這樣你就不再需要所有的內核來執行相同的時間，但是你希望任何兩個內核的執行時間之間的差異小到可能。

在svick給出的參考資料中，您可以看到一種動態編程方法，您可以將其映射到您的問題上。