2个进程的语句有多少种方式可以交错

Question

我想知道，2个进程的语句有多少种方式可以交错？我知道什么是交错，但我似乎无法推导出公式。

Answer 1

它是二项式系数，它负责可能交错的组合爆炸，这使得多线程代码的分析即使不是不切实际也非常具有挑战性。

因此，给定的P1带有N指令的过程P2和带有M您获得的指令的过程N+M over N，即(N+M)! / N!M!交错，即使每个过程的指令数量相对较少，它也会呈指数增长。例如，如果您有两个进程，每个进程有 5 条指令，则可能的交错数为252。然而，大多数现实世界的应用程序都有数百万条指令，而且通常涉及的进程（或线程）不止两个。