彼得森算法在进程同步中的应用

---

协调并发运行的进程的操作是进程同步的核心关注点，这是计算机科学中的一个基本问题。互斥问题是进程同步的一个关键组成部分，彼得森算法为此提供了一个著名的解决方案。这个互斥算法由 Gary Peterson 于 1981 年提出，是简单易懂且流行的算法之一。本文将深入探讨彼得森算法，包括其描述、正确性证明、优缺点、与其他算法的比较、应用以及结论。

彼得森算法

• 将 turn 设置为 0 或 1，指示哪个进程可以首先进入其临界区。

• 无限循环 -

• 将 flag[i] 设置为 true，表示进程 i 想要进入其临界区。

• 将 turn 设置为 j，另一个进程的索引。

• 当 flag[j] 为 true 且 turn 等于 j 时，等待。

• 进入临界区。

• 将 flag[i] 设置为 false，表示进程 i 已完成其临界区。

• 剩余部分。

算法描述

互斥问题有一个基于软件的解决方案，称为彼得森算法，它旨在确保只有一个进程在任何时候都存在于其临界区。该算法的基础是两个共享变量，一个 flag 数组和一个 turn 变量。flag 数组为每个进程分配一个标志，包含布尔值，表示进程是否对访问其临界区感兴趣。turn 变量是一个数字，指示在发生冲突时哪个进程应该先执行。

每次进程想要进入或退出其临界区时，都会调用算法的两个方法 lock() 和 unlock()。lock() 方法的实现如下 -

void lock(int i) {
   flag[i] = true;
   turn = j; //j is the other process
   while (flag[j] && turn == j);
}

unlock() 方法更容易使用 -

void unlock(int i) {
   flag[i] = false;
} 

lock() 方法首先将调用进程的标志设置为 true，表示调用进程对访问其临界区感兴趣。如果两个进程同时想要访问其临界区，则它将 turn 变量设置为另一个进程的索引 (j)，表示另一个进程应该先执行。然后，该函数进入一个忙等待循环，其中它反复检查另一个进程的标志是否为 true，以及现在是否轮到它进入临界区。如果其中一个条件不满足，则循环继续。当两个条件都满足时，循环结束，并且调用过程继续执行其临界部分。

调用进程可以使用 unlock() 方法简单地将其标志更改为 false，从而退出其临界区，并且不再对进入临界区感兴趣。

语法

int turn = 0;          // shared variable
bool flag[2] = {false, false}; // shared variable

Process 0:
while (true) {
   flag[0] = true;
   turn = 1;
   while (flag[1] && turn == 1) {} // busy wait
   // critical section
   flag[0] = false;
   // remainder section
}

Process 1:
while (true) {
   flag[1] = true;
   turn = 0;
   while (flag[0] && turn == 0) {} // busy wait
   // critical section
   flag[1] = false;
   // remainder section
}

正确性证明

彼得森算法对互斥问题提供了一个有效的解决方案，它满足以下条件 -

互斥

在任何时间点，只有一个进程可以处于其临界区。

进展

如果当前没有进程在其临界区，并且任意数量的进程想要进入，则其中一个进程最终将进入其临界区。

有界等待

对其他进程阻止一个进程访问其临界区的频率有限制。

正确性证明使用不变式，即在算法执行之前、期间和之后都成立的属性。证明包含以下不变式 -

• 如果一个进程想要访问其临界区，则该进程的标志为 true。

• 如果一个进程不想进入其临界区，则该进程的标志为 false。

• 如果一个进程在其临界区，则该进程的 turn 变量将等于其索引。

这些不变式可用于证明互斥属性是有效的，因为如果两个进程尝试同时进入其临界区，则忙等待循环要求至少一个进程等待另一个进程完成执行。进展属性是有效的，因为 turn 变量保证至少有一个进程始终能够进入其临界区，因此即使没有进程在其临界区并且一个或多个进程想要进入，最终其中一个进程将会成功。有界等待属性是有效的，因为忙等待循环确保每个进程最终都会获得进入其临界区的轮次，即使其他进程也对进入临界区感兴趣。

不同方法

彼得森算法是进程同步中解决临界区问题的一种常用方法。它用于确保一次只有一个进程可以访问共享资源。彼得森算法有多种变体，它们在实现方式上有所不同，但都遵循相同的核心思想。

以下是三种常见的彼得森算法实现方法 -

方法 1：使用标志

在这种方法中，每个进程都有一个布尔标志，指示它是否想要访问共享资源。算法的工作原理如下 -

boolean flag[2] = {false, false};
int turn = 0;

/* Process 0 */
flag[0] = true;
turn = 1;
while (flag[1] && turn == 1);
/* critical section */
flag[0] = false;

/* Process 1 */
flag[1] = true;
turn = 0;
while (flag[0] && turn == 0);
/* critical section */
flag[1] = false;

这种方法使用一个名为 flag 的布尔变量数组来指示进程是否想要访问临界区。整数变量 turn 确定哪个进程首先进入临界区。该算法确保如果一个进程想要进入，则另一个进程必须等到 turn 被传递，从而防止两个进程同时进入临界区。

方法 2：仅使用 turn 变量

在这种方法中，只有一个变量用于确定哪个进程可以访问临界区，即 turn。算法的工作原理如下 -

int turn = 0;

/* Process 0 */
turn = 1;
while (turn == 1);
/* critical section */
turn = 1;

/* Process 1 */
turn = 0;
while (turn == 0);
/* critical section */
turn = 0;

在此实现中，变量 turn 用于选择哪个进程可以访问临界区。如果 turn 等于进程 ID，则进程可以访问临界区。如果 turn 不等于进程 ID，则进程必须等待轮到它。

方法 3：使用锁变量

这种方法使用一个锁变量来指示临界区是否已锁定。算法的工作原理如下 -

boolean lock = false;

/* Process 0 */
while (lock);
lock = true;
/* critical section */
lock = false;

/* Process 1 */
while (lock);
lock = true;
/* critical section */
lock = false;

在此实现中，变量 lock 表示临界区的锁定状态。如果 lock 等于 true，则临界区已锁定，进程必须等待直到它变为 false。如果 lock 等于 false，则进程可以访问临界区并将其锁定。当进程完成临界区后，它通过将 lock 设置为 false 来解锁它。

应用

彼得森算法被应用于计算机科学的多个领域，特别是操作系统和分布式系统。该算法可用于确保代码关键部分的互斥，例如文件系统操作、网络连接和共享内存访问。在分布式系统中，例如具有分布式数据库和消息队列的系统，该算法也可用于协调对共享资源的访问。

结论

总之，彼得森算法是解决互斥问题的一种著名且仍在使用的算法。该算法简单易懂，使其成为小型系统的一个理想选择。该算法也有一些缺点，包括容易发生忙等待以及依赖共享变量。尽管存在这些缺点，但彼得森算法在计算机科学中仍然有许多应用，特别是在操作系统和分布式系统中。总的来说，彼得森算法是进程同步发展中的一个重要里程碑，并且在现代计算系统中仍然是一种有效的确保互斥的方法。