数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学Peterson 问题
Peterson 解法很好地描述了解决临界区问题的算法，并阐明了设计满足互斥、进展和有限等待要求的软件中涉及的一些复杂性。
do {
flag[i] = true;
turn = j;
while (flag[j] && turn == j);
/* critical section */
flag[i] = false;
/* remainder section */
}
while (true);Peterson 解法中进程 Pi 的结构。此解法仅限于两个交替执行临界区和剩余区的进程。进程编号为 P0 和 P1。为方便起见，当存在 Pi 时，我们使用 Pj 表示另一个进程；即 j 等于 1 − I。Peterson 解法要求这两个进程共享两个数据项：
int turn; boolean flag[2];
变量 turn 表示轮到哪个进程进入其临界区。即，如果 turn == i，则允许进程 Pi 在其临界区中执行。如果进程准备进入其临界区，则使用标志数组来指示。例如，如果 flag[i] 为真，则此值表示 Pi 准备进入其临界区。在对这些数据结构的解释完成后，我们现在可以描述上面所示的算法。为了进入临界区，进程 Pi 首先将其 flag[i] 设置为 true，然后将 turn 设置为值 j，从而断言如果另一个进程希望进入临界区，则可以这样做。如果两个进程同时尝试进入，则 turn 将大致同时设置为 i 和 j。最终只有一个赋值会发生；另一个会发生，但会立即被覆盖。turn 的最终值决定了这两个进程中哪个进程首先允许进入其临界区。我们现在证明此解法是正确的。我们需要证明：
- 保持互斥。
- 满足进展要求。
- 满足有限等待要求。
为了证明 1，我们注意到每个 Pi 仅当 flag[j] == false 或 turn == i 时才进入其临界区。还要注意，如果两个进程可以同时在其临界区中执行，则 flag[0] == flag[1] == true。这两个观察结果表明，P0 和 P1 不可能在大致相同的时间成功执行其 while 语句，因为 turn 的值可以是 0 或 1，但不能同时是两者。因此，其中一个进程（例如，Pj）必须成功执行 while 语句，而 Pi 必须至少执行一个附加语句（“turn == j”）。但是，那时，flag[j] == true 且 turn == j，并且只要 Pj 处于其临界区，此条件就会持续存在；因此，保持互斥。
为了证明特性 2 和 3，我们注意到，如果一个进程卡在 while 循环中，条件为 flag[j] == true 且 turn == j，则只能阻止进程 Pi 进入临界区；这是唯一可能的循环。如果 Pj 不准备进入临界区，则 flag[j] 将为 == false，并且 Pi 可以进入其临界区。如果 Pj 已设置 flag[j] = true 并也在其 while 语句中执行，则 turn == i 或 turn == j。如果 turn == i，则 Pi 将进入临界区。如果 turn == j，则 Pj 将进入临界区。尽管一旦 Pj 退出其临界区，它将把 flag[j] 重置为 false，从而允许 Pi 进入其临界区。如果 Pj 将 flag[j] 重置为 true，则 Pj 还必须将 turn 设置为 i。因此，由于 Pi 在执行 while 语句时不会更改变量 turn 的值，因此 Pi 将最多在 Pj 进入一次后进入临界区（进展）（有限等待）。
缺点
Peterson 解法适用于两个进程，但此解法是用户模式下临界区最佳方案。
此解法也是一种忙等待解法，因此会浪费 CPU 时间。因此可能会出现**“自旋锁”**问题。任何忙等待解法都可能出现此问题。
17K+ 次浏览
