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

Question

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

Answer 1

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

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