12.5 用信号量同步线程

12.5 用信号量同步线程

共享变量是十分方便，但是它们也引入了同步错误（synchronization error）的可能性。考虑图 12-16 中的程序 badcnt.c，它创建了两个线程，每个线程都对共享计数变量 cnt 加 1。

code/conc/badcnt.c

/* WARNING: This code is buggy! */
#include "csapp.h"

void *thread(void *vargp);  /* Thread routine prototype */

/* Global shared variable */
volatile long cnt = 0;  /* Counter */

int main(int argc, char **argv)
{
    long niters;
    pthread_t tid1, tid2;

    /* Check input argument */
    if (argc != 2) {
        printf("usage: %s <niters>\n", argv[0]);
        exit(0);
    }
    niters = atoi(argv[1]);

    /* Create threads and wait for them to finish */
    Pthread_create(&tid1, NULL, thread, &niters);
    Pthread_create(&tid2, NULL, thread, &niters);
    Pthread_join(tid1, NULL);
    Pthread_join(tid2, NULL);

    /* Check result */
    if (cnt != (2 * niters))
        printf("BOOM! cnt=%ld\n", cnt);
    else
        printf("OK cnt=%ld\n", cnt);
    exit(0);
}

/* Thread routine */
void *thread(void *vargp)
{
    long i, niters = *((long *)vargp);

    for (i = 0; i < niters; i++)
        cnt++;

    return NULL;
}

图 12-16　badcnt.c：一个同步不正确的计数器程序

因为每个线程都对计数器增加了 niters 次，我们预计它的最终值是 2 × niters。这看上去简单而直接。然而，当在 Linux 系统上运行 badcnt.c 时，我们不仅得到错误的答案，而且每次得到的答案都还不相同！

linux> ./badcnt 1000000
BOOM! cnt=1445085
linux> ./badcnt 1000000
BOOM! cnt=1915220
linux> ./badcnt 1000000
BOOM! cnt=1404746

那么哪里出错了呢？为了清晰地理解这个问题，我们需要研究计数器循环（第 40～41 行）的汇编代码，如图 12-17 所示。我们发现，将线程 i 的循环代码分解成五个部分是很有帮助的：

  • Hi：在循环头部的指令块。
  • Li：加载共享变量 cnt 到累加寄存器 %rdxi 的指令，这里 %rdxi 表示线程 i 中的寄存器 %rdx 的值。
  • Ui：更新（增加）%rdxi 的指令。
  • Si：将 %rdxi 的更新值存回到共享变量 cnt 的指令。
  • Ti：循环尾部的指令块。

注意头和尾只操作本地栈变量，而 Li、Ui 和 Si 操作共享计数器变量的内容。

当 badcnt.c 中的两个对等线程在一个单处理器上并发运行时，机器指令以某种顺序一个接一个地完成。因此，每个并发执行定义了两个线程中的指令的某种全序（或者交叉）。不幸的是，这些顺序中的一些将会产生正确结果，但是其他的则不会。

线程 i 的 C 代码

for (i = 0; i < niters; i++)
    cnt++;

线程 i 的汇编代码

movq    (%rdi), %rcx
testq   %rcx, %rcx
jle     .L2
movl    $0, %eax
.L3:
movq    cnt(%rip), %rdx
addq    %eax
movq    %eax, cnt(%rip)
addq    $1, %rax
cmpq    %rcx, %rax
jne     .L3
.L2:

图 12-17　badcnt.c 中计数器循环（第 40～41 行）的汇编代码

编校注（非原书正文） 原书图中将更新、存储两行印为 addq %eax 和 movq %eax, cnt(%rip)，存在操作数与寄存器宽度疑误。按本节对 Ui、Si 的定义，应理解为对 %rdx 加 1，再将 %rdx 存回 cnt；图中文字在此照录。

这里有个关键点：一般而言，你没有办法预测操作系统是否将为你的线程选择一个正确的顺序。例如，图 12-18a 展示了一个正确的指令顺序的分步操作。在每个线程更新了共享变量 cnt 之后，它在内存中的值就是 2，这正是期望的值。

另一方面，图 12-18b 的顺序产生一个不正确的 cnt 的值。会发生这样的问题是因为，线程 2 在第 5 步加载 cnt，是在第 2 步线程 1 加载 cnt 之后，而在第 6 步线程 1 存储它的更新值之前。因此，每个线程最终都会存储一个值为 1 的更新后的计数器值。我们能够借助于一种叫做进度图（progress graph）的方法来阐明这些正确的和不正确的指令顺序的概念，这个图我们将在下一节中介绍。

a）正确的顺序

步骤 线程 指令 %rdx1 %rdx2 cnt
1 1 H1 — — 0
2 1 L1 0 — 0
3 1 U1 1 — 0
4 1 S1 1 — 1
5 2 H2 — — 1
6 2 L2 — 1 1
7 2 U2 — 2 1
8 2 S2 — 2 2
9 2 T2 — 2 2
10 1 T1 1 — 2

b）不正确的顺序

步骤 线程 指令 %rdx1 %rdx2 cnt
1 1 H1 — — 0
2 1 L1 0 — 0
3 1 U1 1 — 0
4 2 H2 — — 0
5 2 L2 — 0 0
6 1 S1 1 — 1
7 1 T1 1 — 1
8 2 U2 — 1 1
9 2 S2 — 1 1
10 2 T2 — 1 1

图 12-18　badcnt.c 中第一次循环迭代的指令顺序

练习题 12.7　根据 badcnt.c 的指令顺序完成下表：

步骤 线程 指令 %rdx1 %rdx2 cnt
1 1 H1 — — 0
2 1 L1
3 2 H2
4 2 L2
5 2 U2
6 2 S2
7 1 U1
8 1 S1
9 1 T1
10 2 T2

这种顺序会产生一个正确的 cnt 值吗？