408操作系统考点：简单同步问题

知识点

同步的概念

同步是一种按照一定规则执行任务，是进程之间的先后次序关系。

注意，不能把同步错误理解为同时。

同步与互斥的区别

针对同一个信号量 S。

同步：先 V 后 P，而且 V 操作和 P 操作一般分属两个进程，进程 A 执行 V(S)，进程 B 才能执行 P(S)，同步信号量初始值一般为 0。

互斥：先 P 后 V，而且 P 操作和 V 操作必须属于同一个进程，进程 A 执行 P(S)，此时对临界区上锁，相当于操作系统中的关中断，然后进行临界区操作，然后进程 A 执行 V(S)，此时对临界区解锁，相当于操作系统中的开中断。互斥信号量初始值必须为 1。

同步过程分析

AOV 网每一个顶点代表一个任务，每一条有向边代表一个同步关系，对于任意一条边，必须在之前完成。分析每一个顶点所代表的任务、该顶点的入边（该任务的前置任务）表示的同步关系以及该顶点的出边（该任务的后序任务）表示的同步关系。

为了方便，可以先对 AOV 网进行拓扑排序，按照拓扑排序序列顺序依次对每个任务进行分析。

历年真题

2020 年第 45 题

现有 5 个操作 A、B、C、D 和 E ，操作 C 必须在 A 和 B 完成后执行，操作 E 必须在 C 和 D 完成后执行。请使用信号量的 wait()，signal() 操作（P、V 操作）描述上述操作之间的同步关系，并说明所用信号量和初值。

解答：

列出前置关系：

任务前置任务无无无 $任务前置任务无无无$

可以画出 AOV 网：

进行拓扑排序：

方法一：每个任务一个信号量

即每个 AOV 网中每个顶点构造一个信号量，默认初始为 0。

每个操作需要消耗前置操作信号量，生成当前操作信号量。

semaphore A = 0;   // 可用的A操作数量
semaphore B = 0;   // 可用的B操作数量
semaphore C = 0;   // 可用的C操作数量
semaphore D = 0;   // 可用的D操作数量
semaphore E = 0;   // 可用的E操作数量
 
cobegin
Process A() {
    完成操作A;
    signal(A);    // V(A);
}
Process B() {
    完成操作B;
    signal(B);    // V(B);
}
Process C() {
    wait(A);    // P(A);
    wait(B);    // P(B);
    完成操作C;
    signal(C);    // V(C);
}
Process D() {
    完成操作D;
    signal(D);    // V(D);
}
Process E() {
    wait(C);    // P(C);
    wait(D);    // P(D);
    完成操作E;
    signal(E);    // V(E);
}
coend

严格来说这种写法在某些场景会出问题，比如一个任务是多个任务的前驱的情况，因为没有明确资源的同步关系，使用接下来的每个同步关系一个信号量更加严谨。

方法二：每个同步关系一个信号量

即每个 AOV 网中每条有向边（表示一个同步关系）构造一个信号量，默认初始为 0。

semaphore S_AC = 0;    //控制操作A和C的执行顺序
semaphore S_BC = 0;    //控制操作B和C的执行顺序
semaphore S_CE = 0;    //控制操作C和E的执行顺序
semaphore S_DE = 0;    //控制操作D和E的执行顺序
 
cobegin
Process A() {
    完成操作A;
    signal(S_AC);    // V(S_AC);
}
Process B() {
    完成操作B;
    signal(S_BC);    // V(S_BC);
}
Process C() {
    wait(S_AC);    // P(S_AC);
    wait(S_BC);    // P(S_BC);
    完成操作C;
    signal(S_CE);    // V(S_CE);
}
Process D() {
    完成操作D;
    signal(S_DE);    // V(S_DE);
}
Process E() {
    wait(S_CE);    // P(S_CE);
    wait(S_DE);    // P(S_DE);
    完成操作E;
}
coend

2022 年第 46 题

某进程的两个线程 T1 和 T2 并发执行 A、B、C、D、E 和 F 共 6 个操作，其中 T1 执行 A、E 和 F ，T2 执行 B、C 和 D。题 46 图表示上述 6 个操作的执行顺序所必须满足的约束：C 在 A 和 B 完成后执行， D 和 E 在 C 完成后执行，F 在 E 完成后执行，请使用信号量 wait()、signal() 操作描述 T1 和 T2 之间的同步关系，并说明所用信号量的作用及其初值。

解答：

题目已经给出了 AOV 网。

列出前置关系：

$任务前置任务无无$

进行拓扑排序：

因为比如 C 是 D 和 E 的前驱的情况，因为没有明确资源的同步关系，所以使用每个任务一个信号量的方法会出问题，这里必须使用每个同步关系一个信号量的方法。

每个同步关系一个信号量

即每个 AOV 网中每条边（表示一个同步关系）构造一个信号量，默认初始为 0。

semaphore S_AC = 0;    //控制操作A和C的执行顺序
semaphore S_BC = 0;    //控制操作B和C的执行顺序
semaphore S_CD = 0;    //控制操作C和D的执行顺序
semaphore S_CE = 0;    //控制操作C和E的执行顺序
semaphore S_EF = 0;    //控制操作E和F的执行顺序
 
cobegin
Process T1() {
    // process A
    完成操作A;
    signal(S_AC);    // V(S_AC);
    // process E
    wait(S_CE);    // P(S_CE);
    完成操作E;
    signal(S_EF);    // V(S_EF);
    // process F
    wait(S_EF);    // P(S_EF);
    完成操作F;
}
Process T2() {
    // process B
    完成操作B;
    signal(S_BC);    // V(S_BC);
    // process C
    wait(S_AC);    // P(S_AC);
    wait(S_BC);    // P(S_BC);
    完成操作C;
    signal(S_CD);    // V(S_CD);
    signal(S_CE);    // V(S_CE);
    // process D
    wait(S_CD);    // P(S_CD);
    完成操作D;
}
coend

上述同步关系可以进行简化，同一个线程中的同步关系可以不用设置信号量，跨线程执行的只有 C 的前置 A 和 E 的前置 C。只需要删除不跨线程的信号量即可，简化后如下：

semaphore S_AC = 0;    //控制操作A和C的执行顺序
semaphore S_CE = 0;    //控制操作C和E的执行顺序
 
cobegin
Process T1() {
    // process A
    完成操作A;
    signal(S_AC);    // V(S_AC);
    // process E
    wait(S_CE);    // P(S_CE);
    完成操作E;
    // process F
    完成操作F;
}
Process T2() {
    // process B
    完成操作B;
    // process C
    wait(S_AC);    // P(S_AC);
    完成操作C;
    signal(S_CE);    // V(S_CE);
    // process D
    完成操作D;
}
coend

当然，考场上时间紧迫，没有优化到最简也是没有关系的。

YiNotes

Explorer