神秘的组合

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，节点，计算机等等）。这又意味着指令之间重叠的可能性进一步增加;不能保证所发生的事情可以用的任何传统的交织来正确建模。

这就是为什么正确使用信号量/互斥体以及为什么记忆障碍很重要这一点很重要。这是因为所有这些事情最终都会将真正令人讨厌的画面变成更容易理解的东西。但是因为互斥体减少了可能的执行次数，它们正在降低总体性能和潜在效率。这绝对是棘手的，而这又是为什么如果你可以在消息传递之间进行消息传递，而这些线程之间没有交互作用，那么它会更好。它更容易理解，同步越少越好。