在循環模擬處理器調度中的資源分配算法

Question

背景：我有獨立的任務顯示爲數據流圖（它永遠迭代）。極其簡單的例子：
任務1：B1 - >Ç
任務2：電子 - > B2

處理器分配中給出。圖形本身解釋了可執行的處理器。上例b1和b2在處理器b上執行，c在c和e上執行。

所有任務的執行時間在編譯時已知。由於是輪循建模，所以修改每個任務的最壞情況執行時間以捕獲循環調度的資源仲裁。例如：假設上例中的所有任務的執行時間爲1.然後我們將時間更改爲b1和b2取兩個時間單位，c和e取1.這是因爲處理器b運行以下代碼： while（1） {0} {0} {0} {0} {0} run_task_b1（）; run_task_b2（）; } 因此，如果我們分析task1（用於吞吐量等）說任務b1需要2個時間單元，則足以在處理器b上共享b1和b2。

我的問題：每個任務使用額外的資源（DMA）。假設我們有2個DMA。如果我們天真地分配D1和D2如下：
b1得到D1
c得到D2
e得到D1
b2得到D2
然後在循環建模之後b1和b2得到執行時間3（coz b1與e1和b1共享D1 ，b2共享處理器b，1 + 1 + 1 = 3），並且c和e得到時間2（共享D2與b2和e共享D1與b1）。所以時間是3,2,2,3。

但是，如果我們給出分配：b1得到D1
c得到D2
e得到D2
b2得到D1
建模的執行時間是2,2,2,2。

那麼如何使一個算法在編譯時（靜態分配）爲給定的任務圖找到資源（DMA）分配，使得模擬的RR時間最小？列表調度將導致效率低下，如上例所述。

Answer 1

這聽起來像是Job Shop Scheduling，這是NP完整。 由於您可能沒有處理器時間來查找針對該問題的全局最優值，因此 只是將任務放入隊列中（按某種任務優先級/難度降序排序），並且每次都選取前者。這不會是最佳的，但它將是實際的:)

另外，你可能想看看工作竊取隊列。