UVA1682 独占访问 Exclusive Access

多线程编程中的一个重要问题就是确保共享资源的独占访问。需要独占访问的资源称为临界区（CS），确保独占访问的算法称为互斥协议。 在本题中，假设每个程序恰好有两个线程，每个线程都是一个无限循环，重复进行以下工作：执行其他指令（与临界区无关的代码，称为 NCS），调用 enterCS，执行 CS（即临界区代码），调用 exitCS，然后继续循环。NCS 和 CS 内的代码和协议完全无关。 在本题中，用共享的单比特变量（即每个变量只能储存 $0$ 或 $1$）来实现互斥协议（即上述的 enterCS 和 exitCS）。所有变量初始化为 $0$，且读写任意一个变量只需要一条语句。两个线程可以有一个局部指令计数器 IP 指向下一条需要执行的指令。初始时，两个线程的 IP 都指向第一条指令。程序执行的每一步，计算机随机选择一个线程，执行它的 IP 所指向的指令，然后修改该线程的 IP。为了分析互斥协议，定义“合法执行过程”如下：两个线程都执行了无限多条指令；或者其中一个线程执行了无限多指令，另一个线程执行了有限多条指令以后终止，且 IP 在 NCS 中。 下表中展示了 $3$ 个互斥协议的伪代码。两个线程的 $id$ 分别为 $0$ 和 $1$，变量 $want[0]$、$want[1]$ 和 $turn$ 为共享单比特变量。以“$\texttt{+}$”开头的代码实现了 enterCS，而以“$\texttt{-}$”开头的代码实现了 exitCS，$\rm NCS()$ 和 $\rm CS()$ 表示执行 NCS 和 CS 代码，这些代码的具体内容和本题无关（假设它们不会修改共享变量）。 | 算法 $1$ | 算法 $2$ | 算法 $3$ | | :-: | :-: | :-: | | $\begin{aligned} & \texttt{loop forever} \\ &\quad\texttt{NCS()} \\ &\texttt{+} \ \ \texttt{loop while} \\ &\texttt{+} \ \quad \ \texttt{(turn == 1 - id)} \\ &\quad \texttt{CS()} \\ &\texttt{-} \ \ \texttt{turn

无

无