详解前驱图与PV操作

前驱图（precedence graph）是一种用于表示并发系统中进程或事件之间依赖关系的有向图。在并发编程和同步领域，前驱图用于说明哪些操作必须先发生，哪些可以并行，哪些需要等待其他操作完成。它有助于理解多个进程如何协调执行，避免冲突或死锁等问题。

PV操作是一种经典的进程同步机制，它源自Dijkstra的信号量（Semaphore）理论。PV操作用于管理进程对共享资源的访问，防止并发进程中的竞争条件。P操作（Proberen，尝试）是对信号量减1的操作，如果信号量大于0，进程继续执行；否则，进程阻塞。V操作（Verhogen，增加）是对信号量加1的操作，释放资源，允许其他进程继续执行。

前驱图与PV操作的结合

在并发系统中，前驱图可以用来直观地描述进程的执行顺序和依赖关系，而PV操作用于实现这些依赖关系所需的同步。二者结合使用，能够通过信号量控制进程的执行，使其严格遵循前驱图的依赖顺序。

例子：两个进程的同步问题

假设有两个进程 A 和 B，它们分别进行以下步骤：

• 进程 A 依次执行操作 A1 和 A2
• 进程 B 依次执行操作 B1 和 B2

但是，它们之间有依赖关系：

• A2 必须在 B1 之后执行，也就是说，A2 的前驱是 B1。

用前驱图来表示这个依赖关系，图中会有一条从 B1 指向 A2 的有向边，表示 A2 依赖于 B1 的完成。

使用PV操作实现同步

我们可以使用信号量 S 来控制 A2 和 B1 之间的执行顺序。初始时，信号量 S=0，表示 A2 不能立即执行。

1. 进程 B 在执行完 B1 后，执行 V(S) 操作，表示 B1 完成并释放信号量。
2. 进程 A 在执行 A2 前，执行 P(S) 操作。由于 S 的初始值为0，A2 会阻塞，直到 B1 完成并且 S 增加到1，A2 才能执行。

前驱图的实际应用

前驱图和PV操作结合的关键在于：

• 前驱图：确定并发系统中事件的依赖顺序。
• PV操作：通过信号量实现这种顺序的同步控制。

通过这种方式，可以确保进程按照预期的顺序执行，避免资源竞争和死锁。例如，在数据库系统中，多个事务对相同数据的并发访问可以通过PV操作控制，保证数据一致性。在操作系统中，多个进程对共享内存的访问也可以通过前驱图建模，并结合PV操作确保正确的同步执行。

更复杂的场景

对于复杂的并发场景，前驱图可能会包含多个有向边，表示多个前驱事件。相应的PV操作可能涉及多个信号量。例如，如果 A3 依赖于 B2 和 C1 的完成，则在 A3 执行前需要等待两个信号量释放。

这种前驱图与PV操作结合的机制不仅限于简单的进程同步，还可以扩展到多进程通信、死锁预防、生产者-消费者问题等各种并发控制问题。

示例

示例1：前驱图与PV操作的结合

假设有三个进程 A、B 和 C，并且它们执行的任务如下：

• 进程 A：任务 A1 -> 任务 A2
• 进程 B：任务 B1 -> 任务 B2
• 进程 C：任务 C1 -> 任务 C2

任务之间有如下依赖关系：

1. A2 必须在 B1 完成后才能执行。
2. B2 必须在 C1 完成后才能执行。

1. 前驱图表示

我们可以用前驱图表示这些依赖关系：

• B1 → A2：表示 A2 依赖 B1，即 A2 只有在 B1 完成后才能执行。
• C1 → B2：表示 B2 依赖 C1，即 B2 只有在 C1 完成后才能执行。

这个前驱图可以画成：

B1 → A2
C1 → B2

2. 使用信号量（PV操作）实现同步

为了实现上述依赖关系，我们引入两个信号量：

• 信号量 S1，用于控制 A2 和 B1 的依赖。初始值为 0。
• 信号量 S2，用于控制 B2 和 C1 的依赖。初始值为 0。

初始情况下，两个信号量 S1 和 S2 都为 0，表示 A2 和 B2 都不能立即执行，必须等待相应的前驱任务完成。

进程的执行逻辑：

• 进程 A：

  1. 执行 A1。
  2. 执行 P(S1) 操作（等待信号量 S1），当 S1 > 0 时，才执行 A2。

• 进程 B：

  1. 执行 B1。
  2. 执行 V(S1) 操作，释放信号量 S1，允许 A2 执行。
  3. 执行 P(S2) 操作（等待信号量 S2），当 S2 > 0 时，才执行 B2。

• 进程 C：

  1. 执行 C1。
  2. 执行 V(S2) 操作，释放信号量 S2，允许 B2 执行。

3. 示例代码

#include <stdio.h>
#include <pthread.h>
#include <semaphore.h>// 定义信号量
sem_t S1, S2;void* processA(void* arg) {printf("Process A: Executing A1\n");// 等待信号量S1，确保A2在B1之后执行sem_wait(&S1);printf("Process A: Executing A2 after B1\n");return NULL;
}void* processB(void* arg) {printf("Process B: Executing B1\n");// B1完成后，释放信号量S1，允许A2执行sem_post(&S1);// 等待信号量S2，确保B2在C1之后执行sem_wait(&S2);printf("Process B: Executing B2 after C1\n");return NULL;
}void* processC(void* arg) {printf("Process C: Executing C1\n");// C1完成后，释放信号量S2，允许B2执行sem_post(&S2);return NULL;
}int main() {// 初始化信号量sem_init(&S1, 0, 0); // S1 初始为0，A2不能立即执行sem_init(&S2, 0, 0); // S2 初始为0，B2不能立即执行pthread_t threadA, threadB, threadC;// 创建线程，模拟三个进程的执行pthread_create(&threadA, NULL, processA, NULL);pthread_create(&threadB, NULL, processB, NULL);pthread_create(&threadC, NULL, processC, NULL);// 等待线程完成pthread_join(threadA, NULL);pthread_join(threadB, NULL);pthread_join(threadC, NULL);// 销毁信号量sem_destroy(&S1);sem_destroy(&S2);return 0;
}

4. 解释

• 信号量的初始化：sem_init(&S1, 0, 0) 和 sem_init(&S2, 0, 0) 将信号量 S1 和 S2 初始化为 0。表示 A2 和 B2 不能立即执行，必须等待它们的依赖任务完成。

• 进程 A：A1 立即执行，执行到 A2 时，它会阻塞在 sem_wait(&S1) 处，直到 B1 完成并释放 S1。

• 进程 B：B1 执行后调用 sem_post(&S1)，释放信号量 S1，允许 A2 执行。B2 需要等待 C1 完成，调用 sem_wait(&S2) 进行同步。

• 进程 C：C1 执行后调用 sem_post(&S2)，释放信号量 S2，允许 B2 执行。

5. 输出结果示例：

Process B: Executing B1
Process A: Executing A1
Process C: Executing C1
Process A: Executing A2 after B1
Process B: Executing B2 after C1

示例2：信号量分配

1. 示例背景

假设我们有三个进程 A、B 和 C，它们执行的任务如下：

• 进程 A：A1 -> A2
• 进程 B：B1 -> B2
• 进程 C：C1 -> C2

任务之间有以下依赖关系：

1. A2 必须在 B1 完成后执行。
2. B2 必须在 C1 完成后执行。

2. 信号量的分配

我们将使用信号量 S1 和 S2 来同步这些依赖关系：

1. 信号量 S1 用于控制 A2 和 B1 之间的依赖。
2. 信号量 S2 用于控制 B2 和 C1 之间的依赖。

3. 信号量初始值：

• S1 = 0：表示 A2 在 B1 完成之前不能执行。
• S2 = 0：表示 B2 在 C1 完成之前不能执行。

4. 信号量的分配与操作

1. 初始状态：所有信号量的初始值为 0，表示依赖任务尚未完成，相关任务需要等待前驱任务完成后才能执行。

2. 进程 A：

   • A1 任务可以立即执行，不依赖任何其他任务。
   • A2 任务需要等待 B1 任务完成。我们使用 sem_wait(S1) 来阻塞 A2 的执行，直到 B1 释放信号量 S1。

3. 进程 B：

   • B1 任务可以立即执行，不依赖其他任务。
   • 执行完 B1 后，进程 B 调用 sem_post(S1)，将 S1 的值从 0 增加到 1，释放信号量，使 A2 能够继续执行。
   • B2 任务依赖于 C1 任务的完成，因此在 B2 任务执行前调用 sem_wait(S2)，阻塞 B2，直到 C1 完成并释放信号量 S2。

4. 进程 C：

   • C1 任务可以立即执行，不依赖任何其他任务。
   • 执行完 C1 后，进程 C 调用 sem_post(S2)，将 S2 的值从 0 增加到 1，允许 B2 执行。

5. 信号量分配的详细步骤

为了使这个过程更加清晰，让我们以具体的执行步骤和信号量状态变化为例：

6. 初始状态：

• S1 = 0（A2 需要等待 B1 完成）
• S2 = 0（B2 需要等待 C1 完成）

操作	说明	S1 信号量状态	S2 信号量状态
A1 执行	无需等待，直接执行	0	0
B1 执行	无需等待，直接执行	0	0
sem_post(S1)	B1 完成，释放 S1，允许 A2 执行	1	0
A2 执行	A2 依赖 B1，S1 = 1，可以执行	0	0
C1 执行	无需等待，直接执行	0	0
sem_post(S2)	C1 完成，释放 S2，允许 B2 执行	0	1
B2 执行	B2 依赖 C1，S2 = 1，可以执行	0	0

7. 信号量状态变化的解释：

1. 初始状态：S1 = 0 和 S2 = 0，这意味着 A2 和 B2 不能立即执行。
2. B1 完成后：B1 执行完毕后，进程 B 通过 sem_post(S1) 将信号量 S1 增加到 1，表示 A2 可以执行。
3. A2 执行：A2 检查 S1 是否大于 0，发现信号量已被释放，于是继续执行。
4. C1 完成后：C1 执行完毕后，进程 C 通过 sem_post(S2) 将信号量 S2 增加到 1，表示 B2 可以执行。
5. B2 执行：B2 检查 S2 是否大于 0，发现信号量已被释放，于是继续执行。

8. 示例代码

#include <stdio.h>
#include <pthread.h>
#include <semaphore.h>// 定义信号量
sem_t S1, S2;void* processA(void* arg) {printf("Process A: Executing A1\n");// 等待信号量S1，确保A2在B1之后执行sem_wait(&S1);printf("Process A: Executing A2 after B1\n");return NULL;
}void* processB(void* arg) {printf("Process B: Executing B1\n");// B1完成后，释放信号量S1，允许A2执行sem_post(&S1);// 等待信号量S2，确保B2在C1之后执行sem_wait(&S2);printf("Process B: Executing B2 after C1\n");return NULL;
}void* processC(void* arg) {printf("Process C: Executing C1\n");// C1完成后，释放信号量S2，允许B2执行sem_post(&S2);return NULL;
}int main() {// 初始化信号量sem_init(&S1, 0, 0); // S1 初始为0，A2不能立即执行sem_init(&S2, 0, 0); // S2 初始为0，B2不能立即执行pthread_t threadA, threadB, threadC;// 创建线程，模拟三个进程的执行pthread_create(&threadA, NULL, processA, NULL);pthread_create(&threadB, NULL, processB, NULL);pthread_create(&threadC, NULL, processC, NULL);// 等待线程完成pthread_join(threadA, NULL);pthread_join(threadB, NULL);pthread_join(threadC, NULL);// 销毁信号量sem_destroy(&S1);sem_destroy(&S2);return 0;
}

9. 总结

• **信

号量分配的关键在于将每个信号量与特定的任务依赖关系相关联，以确保进程按照正确的顺序执行。

在这个示例中：

• S1 控制 A2 任务在 B1 任务完成后执行。
• S2 控制 B2 任务在 C1 任务完成后执行。

通过初始化信号量为 0，我们确保依赖任务（如 A2 和 B2）不会提前执行，只有在前驱任务完成并释放信号量时，依赖任务才能继续运行。

这种信号量的分配和使用可以广泛应用于多进程或多线程程序中，帮助有效地管理复杂的同步问题，避免竞争条件和不确定的执行顺序。