multithreading - 什么是进程交错？（在并发领域）

Question

我不太确定这个词是什么意思。我在我们学习并发的课程中看到了它。我已经看到了很多数据交错的定义，但我可以找到有关进程交错的任何信息。

当看到这个术语时，我的直觉告诉我它是使用线程同时运行多个进程，对吗？

score 5 · Accepted Answer

如果您将一个过程想象为一个（可能是无限的）语句序列/跟踪（例如，通过循环展开获得），那么几个过程的可能交错的集合由任何这些过程的所有可能的语句序列组成。

例如考虑流程

int i;

proctype A() {
  i = 1;
}

proctype B() {
  i = 2;
}

那么可能的交织是i = 1; i = 2and i = 2; i = 1，即可能的最终值i是 1 和 2。这当然可以更复杂，例如在存在保护语句的情况下：那么交织序列中的下一个可能语句不一定是那些在下一个程序计数器的位置，但仅限于守卫允许的位置；例如考虑proctype

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

那么可能的交错（A()如前所述）是i = 1; skip和i = 2; i = 1，所以只有一个可能的最终值i。

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

score 4 · Accepted Answer

它只是意味着以任意顺序执行（数据访问或执行或...）**（请参阅注释）。在并发的情况下，通常指的是动作交错。如果进程 P 和 Q 是并行组合 (P||Q)，那么它们的动作将交错。考虑以下过程：

PLAYING = (play_music -> stop_music -> STOP).
PERFORMING = (dance -> STOP).

||PLAY_PERFORM = (PLAYING || PERFORMING).

所以每个原始过程可以表示为：（由LTSA模型检查工具生成）

那么作为动作交错的结果可能的痕迹将是：

dance -> play_music -> stop_music
play_music -> dance -> stop_music
play_music -> stop_music -> dance

这是此示例的 LTSA 工具生成的输出。

**注意：这里的“任意”是指进程执行的任意选择，而不是它们的内部代码序列。每个进程中的代码执行将始终按顺序执行。

希望能帮助到你！:)

score 0 · Accepted Answer

操作系统支持任务（或进程）。但是现在让我们考虑一下“活动”。

活动可以并行执行。这里有两个活动，P 和 Q：

    P:      abc
    Q:      def

a, b, c, d, e, f, 是操作。*

每个操作始终具有相同的效果，而与可能同时执行的其他操作无关（原子性）。

同时执行这两个活动的效果是什么？我们不确定，但我们知道这与通过顺序执行两个活动的 INTERLEAVING 获得的结果相同 [interleavings 也称为 SCHEDULES]。以下是这两个活动的可能交错：

    abcdef
    abdcef
    abdecf
    abdefc
    adbcef
    ......
    defabc

也就是说，两个活动的操作以所有可能的方式排序，以保持操作在两个活动中出现的顺序。两个活动的串行交错 [串行调度] 是一个活动的所有操作先于另一活动的所有操作。交错概念的重要性在于，它可以让我们表达并发程序的含义：活动的并行执行等价于这些活动的其中一个交错的顺序执行。

3 回答 3