1

我决定学习并发性,并想了解来自两个不同进程的指令有多少种重叠方式。这两个过程的代码只是一个 10 次迭代循环,每次迭代执行 3 条指令。我发现问题在于将 X 指令固定在一个点上,然后在空间之间拟合来自其他进程的其他 X 指令,同时考虑到它们必须是有序的(进程 B 的指令 4 必须始终位于指令 20 之前)。

我编写了一个程序来计算这个数字,查看结果我发现解决方案是 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 条指令。你能解释一下吗?

提前致谢。

4

3 回答 3

6

FWIW 可以这样查看:您有一个带有k个蓝色和k个红色球的袋子。相同颜色的球是无法区分的(类似于同一进程/线程中指令顺序固定的限制——顺便说一句,这在现代处理器中并非如此,但现在让我们保持简单)。你可以用多少种不同的方法从袋子里取出所有的球?

我的组合技巧很生疏,但我的第一个猜测是

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

根据维基百科,这确实等于

(2k)
(k )

(对不起,我不知道如何展示这一点)。

对于n 个过程,可以通过在袋子中放置n 个不同颜色的球来概括。

更新:请注意,严格来说,这仅模拟在单个处理器上执行不同进程的情况,因此来自所有进程的所有指令必须在处理器级别上线性排序。在多处理器环境中,可以同时执行几条指令。

于 2010-04-10T12:35:54.940 回答
2

一般来说,我同意 Péter 的回答,但由于它似乎没有完全点击 OP,这是我的镜头(纯粹从数学/组合的角度来看)。

您有 2 组 30 (k) 条指令放在一起,总共 60 (n) 条指令。由于每组 30 条必须保持有序,因此我们不需要跟踪每组中的哪条指令,只需跟踪一条指令来自哪个组。因此,我们有 60 个“插槽”,用于放置一组(例如红色)中的 30 条指令和另一组(例如蓝色)中的 30 条指令。

让我们首先将 30 条红色指令放入 60 个插槽中。有 (60 choose 30) = 60!/(30!30!) 方法可以做到这一点(我们选择 60 个插槽中的 30 个由红色指令填充)。现在,我们还有 30 个蓝色指令,但我们只剩下 30 个空位。有 (30 选择 30) = 30!/(30!0!) = 1 种方式将蓝色指令放置在剩余的插槽中。因此,总共有 (60 选择 30) * (30 选择 30) = (60 选择 30) * 1 = (60 选择 30) 方法来做到这一点。

现在,假设您有 3 组(红色、绿色、蓝色)k 条指令,而不是 2 组 30 条指令。您总共有 3k 个插槽要填充。首先,放置红色的:(3k选择k)=(3k)!/(k!(3k-k)!)=(3k)!/(k!(2k)!)。现在,将绿色的放入剩余的 2k 个插槽中:(2k 选择 k)=(2k)!/(k!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 的指令,则可能性的数量为 (a+b+c)!/(a!b!c!)。
  • 如果您有 n 组指令,其中第 i 组有 ki 指令,则可能性的数量为 (k1+k2+...+kn)!/(k1!k2!...kn!)。
于 2010-04-10T17:44:18.080 回答
1

彼得的回答很好,但这并不能解释为什么并发是困难的。这是因为现在越来越多的时候你有多个可用的执行单元(无论是内核、CPU、节点、计算机等等)。这反过来意味着指令之间重叠的可能性进一步增加。无法保证使用任何传统的交错可以正确模拟所发生的事情。

这就是为什么正确使用信号量/互斥量以及内存屏障很重要的原因。那是因为所有这些事情最终都会把真正令人讨厌的画面变成更容易理解的东西。但是由于互斥体减少了可能的执行次数,它们正在降低整体性能和潜在效率。这绝对是一件棘手的事情,而这反过来就是为什么如果您可以在不交互的活动线程之间进行消息传递方面工作会更好;它更容易理解,同步次数越少越好。

于 2010-04-10T13:12:26.643 回答