如何隨着時間的推移獲得最小數量的「衝突」

我正在開發嵌入式系統的調度器。該調度程序將每X毫秒調用一次進程;當然，這個時間可以爲每個進程單獨配置。如何隨着時間的推移獲得最小數量的「衝突」

所有東西都被編碼並調用每個過程，因爲它應該;我所面臨的問題是這樣的：想象我設置4個過程被稱爲每10，15，第5和30毫秒分別爲：

A: 10ms 
B: 15ms 
C: 5ms 
D: 30ms

所得主叫隨着時間的推移將是：

     A   | 
     A B A  B   | 
    C C C C C C C  | processes being called 
         D   | 
---------------------------------- 
0 5 10 15 20 25 30 35... ms

問題是，當達到30ms時，所有進程都在同一時刻（一個接一個）被調用，並且這可能會延遲從此處執行的正確執行。

這可以通過爲每個進程添加延遲（但保留其呼叫頻率）來解決，因此頻率不再是對方的倍數。我的問題是，我不知道如何計算應用到每個過程的延遲，以便最小化碰撞次數。

是否有任何已知的算法，或一些數學指導？

謝謝。

來源

2010-01-16 Raúl Ferràs

間隔之間的碰撞將是他們區間的LCM。所以當你所有的時間間隔都是互質的時候，你會有最小的碰撞。 – 2010-01-17 13:45:45

給定一組間隔時間，通過查找Jason在您的帖子的評論中提到的least common multiple，您可以找到開始時間重合的時間（假設沒有偏移量）。您可以通過對一組任務執行間隔素因子分解來查找LCM。

儘管如此，greatest common divisor（或最大公因子GCF）可能是計算最有用的數字。這個數字會給你重複將會發生的間隔。在您的示例中，GCF爲5.使用GCF爲5時，可以爲每個任務添加初始偏移量1,2,3等，以避免重疊的開始時間。因此，GCF爲5時，最多可以有5個任務的開始時間不會重疊。 GCF爲20時，最多可以安排20個任務，不會有重疊的開始時間。如果兩個（或更多）任務是相對主要的（GCF = 1），那麼無論您在這些任務中使用什麼偏移（如果間隔永不改變），肯定會發生重疊。

來源

2010-01-17 14:43:46

如果我有5個進程的多個進程和7個進程的混合進程？例如：A = 5，B = 7，C = 20 – 2010-01-18 09:07:58

5和7的GCF是1（它們相對爲素數）。給定整數開始時間，不可能安排這兩項任務，以便它們每5和7次重複一次而不會相互衝突。我不知道更多關於這個問題的限制，我的想法是，最好把剩餘任務的GCF（在這種情況下是5），並安排這些任務永遠不會相互衝突。然後計劃任務B的偏移量爲0，最多同時啓動2個任務。如果可以使用非整數偏移量，則給定任務B的偏移量爲.5ms。 – 2010-01-18 13:20:58

有沒有完美的解決方案，他們會不時碰撞。我建議在週期長度上加上小的（0.01-0.1ms）隨機值，所以從長遠來看，它們很少會同時被調用。另外，如果你有5ms的調度程序粒度，第一個線程總是在X + 1ms處調用，第二個在X + 2處等，這樣它總是保證1ms的不間斷運行（如果你有10個線程，那麼它將是X + 0.5，X + 1，X + 1.5）。但是這可能會非常棘手的實施。

來源

2010-01-16 15:42:05 BarsMonster

調度程序的粒度爲1ms。以上只是一個很容易展示問題的例子。 – 2010-01-16 15:48:11

調度器沒有無限的粒度太糟糕;那麼你可以添加sqrt（2）到第一個進程的時間段，sqrt（3）到第二個，sqrt（5）到第三個... :) – 2010-01-17 13:47:18

這類問題直接關係到實時編程和調度算法的領域。我在大學裏就這個課題上了一堂課，如果我沒記錯的話，Rate-monotonic scheduling就是你要找的算法。

這個想法是，您將優先級分配給與他們的期間成反比的作業，即期限越小，優先級越高。但是，如果您可以中斷您的工作並在以後恢復工作，那麼這會更好。

雖然有其他的選擇，但是，像EDF (earliest deadline first)，但這些是動態調度算法（即優先級在執行過程中分配）。

來源

2010-01-16 16:59:39 Wookai

簡單的解決方案是更改調用子例程的時間表。即而不是5,10,15和30毫秒，你可以住在5,15,15和30？然後你可以用以下方式：（A = 5毫秒PROC，B，C = 15個毫秒PROC，d = 30毫秒PROC）：

AAAAAAAAAAAAAAAAAAAA ... 
B B B B B B B ... 
    C C C C C C C ... 
    D  D  D  ...

我敢肯定，你可以概括這樣的想法，但它的工作原理只有當你實際上可以改變靜態時間間隔。

如果你不能改變的時間間隔，也需要嚴格遵守它們，然後我你是那種運氣不好，因爲沒有參數，兩個進程之間進行切換:)

來源

2010-01-18 08:56:12

我寫的時間間隔只是一個例子。我不知道調度器將面對哪些時間間隔。這個想法是調度器本身能夠調整延遲來減小衝突。顯然，如果時間總是靜態的，我可以手動調整它們，但我不知道要使用的時間間隔。 – 2010-01-18 09:26:36

如何隨着時間的推移獲得最小數量的「衝突」

回答

相關問題