神祕的組合

Question

我決定學習併發性，並想知道來自兩個不同進程的指令可以重疊多少種方式。這兩個進程的代碼只是一個10迭代循環，每次迭代執行3條指令。我發現問題包括將X指令固定在某一點上，然後在考慮到它們必須被訂購（過程B的指令4必須始終在指令20之前）的情況下，將空間之間的其他過程的其他X指令裝入其中。

我寫了一個程序來計算這個數字，看着結果我發現解決方案是n組合k，其中k是在一個進程的整個循環中執行的指令的數量，所以對於10次迭代它會是30，並且n是k * 2（2個過程）。換句話說，n個固定n/2的物體並且必須在空間中適合n/2而沒有n/2丟失它們的順序。

好的問題解決了。不，不是。我不知道爲什麼會這樣，我知道一個組合的定義是，在多少種方式中，你可以從一組n個元素中取出k個元素，這樣所有的組都是不同的，但是元素的順序並不是'沒關係。在這種情況下，我們有n個元素，並且我們實際上將它們全部取出，因爲所有指令都被執行（n C n）。

如果用一個袋子裏有2k個藍色（A）和紅色（B）物體來解釋它，並且從包裏取出k個物體，那麼當實際執行2k個指令時，您仍然只需要k個指令。你能否介紹一下這個問題？

在此先感謝。

Answer 1

一般來說，我同意佩特的答案，但由於它似乎沒有完全點擊OP，這裏是我的注意力（純粹從數學/組合的角度）。

您有兩組30（k）條說明，您要放在一起，總共有60（n）條說明。由於每組30個必須保持有序，所以我們不需要跟蹤每組中的哪個指令，哪個指令來自哪個指令。因此，我們有60個「插槽」，在其中放置30組指令（例如，紅色）和30個指令（例如藍色）。

讓我們先將30條紅色指令放入60個插槽。有（60選擇30）= 60！/（30！30！）方法來做到這一點（我們選擇60箇中的30個插槽由紅色指令填充）。現在，我們仍然有30條藍色指令，但我們只剩下30個空位。有（30選擇30）= 30！/（30！0！）= 1種方式將藍色指令放置在剩餘的插槽中。所以總共有（60選30）*（30選30）=（60選30）* 1 =（60選30）這樣做。現在，讓我們假設代替2組30個，你有3組k（k，k）指令集（紅色，綠色，藍色）。你總共有3k個時隙來填補。首先，放置紅色：（3k選擇k）=（3k）！/（k！（3k-k）！）=（3k）！/（k！（2k）！）。現在，將綠色放入剩餘的2k時隙中：（2k選擇k）=（2k）！/（k！k！）。 （k選擇k）= k！/（k！0！）= 1。總共：（3k選擇k）*（2k選擇k）*（k選擇k） =（3k）！*（2k）！* k！）/（k！（2k）！* k！k！* k！0！）=（3k）！/（k！k！k！）。

如進一步擴展（雖然我不打算提供全面的解釋）：

• ，如果你有3套的長度爲A，B和C的指令，可能性的數量是（一+ b + C）！/（一個！b！！C）。
• 如果您有n組指令，其中第i組具有ki指令，則可能數目爲（k1 + k2 + ... + kn）！/（k1！k2！... kn！）。

Answer 2

FWIW它可以這樣看待：你有一個袋子k藍色和k紅色的球。相同顏色的球是無法區分的（類似於相同進程/線程內的指令順序是固定的 - 在現代處理器btw中不是這樣，但現在讓我們保持簡單）。你有多少種不同的方式可以將全部從包裏拿出來？

我的組合技能是非常生疏，但我的第一個猜測是

(2k!) 
----- 
2*k! 

其中，根據Wikipedia，確實等於

(2k) 
(k) 

（抱歉，我沒有更好的主意如何顯示此）。

對於Ñ過程，它可以通過Ñ不同的顏色在所述袋的具有球一概而論。

更新：請注意，嚴格意義上，這隻模擬在單個處理器上執行不同進程時的情況，因此所有進程的所有指令都必須在處理器級別進行線性排序。在多處理器環境中，可以同時執行幾個指令。

Answer 3

Péter的答案很好，但這並不能解釋爲什麼併發很難。這是因爲越來越多的時候你有多個可用的執行單元（無論是核心，CPU，節點，計算機等等）。這又意味着指令之間重疊的可能性進一步增加;不能保證所發生的事情可以用的任何傳統的交織來正確建模。

這就是爲什麼正確使用信號量/互斥體以及爲什麼記憶障礙很重要這一點很重要。這是因爲所有這些事情最終都會將真正令人討厭的畫面變成更容易理解的東西。但是因爲互斥體減少了可能的執行次數，它們正在降低總體性能和潛在效率。這絕對是棘手的，而這又是爲什麼如果你可以在消息傳遞之間進行消息傳遞，而這些線程之間沒有交互作用，那麼它會更好。它更容易理解，同步越少越好。