并发编程操作指令

Question

我正在学习一个操作系统类，并试图了解并发编程是如何工作的。

我唯一不能理解的是理解两个或多个进程的操作/指令执行的“顺序”：

例如，给定试图访问关键部分的两个进程的代码

​

​

从Parbegin来看，这段代码的执行顺序是什么？它们以1:1的方式运行(比如，一行代码由Process1和Process2交替执行，如1,1，2,2，3，3.n，n，n与明显的入口/出口点条件)，还是有一些我遗漏的粒子顺序？

据我所知，死刑是这样的：

 var and turn inizialized
turn is equal to 1 then P1 enter in the CS
turn is equal to 1 then P2 enter the while
P2 is now in busy-wait
P1 is doing the critical section
P1 exit from the critical section and set turn=2
P2 exit from the while and enter CS
P1 doing remainder
P2 exit CS and set turn=1
P1 can enter the cycle

诸若此类。我做错什么了吗？

Answer 1

并发性的一个重要特性，也是许多困难的根源，就是跨进程的操作顺序不知道。操作的顺序是非确定性。

首先，你可以认为操作的顺序是随机的。也就是说，考虑处理器(更准确地说，调度器执行多进程程序)如下：

• 随机挑选其中一个过程。
• 执行该过程中的一条指令。
• 重复一遍。

处理器可以依次从每个进程执行一条指令。或者，它可能从流程1执行2.5循环，然后从流程2执行3条指令，而不是在一段时间内恢复进程1，再从进程2执行一些其他的指令。或者它可能从流程1执行3条指令，然后从进程2执行1条指令，然后从流程1执行4条指令，从流程2执行1条指令，从流程1执行5条指令等等。

并发性研究的目的是确定程序的性质，无论随机选择的序列是什么，或者至少对于一类“不太极端”的随机选择。最常见的“不太极端”类是公平假设，粗略地说，这意味着每条未阻塞的指令(阻塞的指令类似于等待输入事件的输入指令)最终都会被执行。这就排除了“永远执行流程1”的可能性，但上面没有任何其他示例。

对于您特别引用的算法，它的目标是只有一个进程可以介于关键部分的开始和结束之间。(请注意，虽然关键部分写在一行上，但它通常由多条指令组成。)无论两个进程的指令如何交织，都需要此属性。

我的回答有几处简化。特别是随机性和非决定论实际上是不同的概念。。使用随机调度程序，您可能会或不会幸运，如果没有，您可以再试一次，而非确定性调度程序可能会给您带来麻烦。一个随机调度程序实际上有点公平，而一个现实世界的调度程序可能根本不公平。并发的重要内化是，您不能预先预测程序的行为:有许多可能的行为。