multithreading - 什么是过程交错？ (在并发领域)

Question

对于这个术语的含义，我不太确定。我在我们学习并发的类(class)中看到了它。我已经看到了许多有关数据交织的定义，但是我可以找到有关进程交织的任何信息。

当我的直觉告诉我这是使用线程同时运行多个进程时，是正确的吗？

Answer 1

如果您将一个流程想象成语句的(可能是无限的)序列/轨迹(例如通过循环展开获得的)，那么几个流程的可能交织的集合由那些流程中任何一个的所有可能的语句序列组成。

考虑例如过程

int i;

proctype A() {
  i = 1;
}

proctype B() {
  i = 2;
}

那么可能的交织是 i = 1; i = 2和 i = 2; i = 1，即 i的最终值可能是1和2。这当然会更加复杂，例如在存在 protected 语句的情况下:则交织序列中的下一个可能的语句不一定位于下一个程序计数器位置的那些，但是只有 guard 允许的那些；考虑例如proctype

proctype B() {
  if
    :: i == 0 -> i = 2
    :: else   -> skip
  fi
}

然后，可能的交织(如前所述的 A())是 i = 1; skip和 i = 2; i = 1，因此 i只有一个可能的最终值。

确实，交错的概念对于Spin的并发观点至关重要。在跟踪语义中，并发进程的可能跟踪的集合是各个进程的跟踪的可能交错的集合。