第 146 / 187 篇

14.3. 线程同步

说明

本文是个人学习用的非官方中英对照译文,原文:https://diveintosystems.org/book/C14-SharedMemory/synchronization.html。
原书采用 CC BY-NC-ND 4.0 许可(禁止演绎),请勿公开传播本译文。
标为「译注」「现代更新」的内容是译者补充,不代表原书作者观点;代码与原文逐字一致,未作改动。

14.3. Synchronizing Threads

在我们迄今看过的例子中,每个线程在执行时都不与其他任何线程共享数据。例如,在标量乘法程序中,数组的每个元素都完全独立于其他所有元素,因此线程之间无须共享数据。

In the examples we’ve looked at thus far, each thread executes without sharing data with any other threads. In the scalar multiplication program, for instance, each element of the array is entirely independent of all the others, making it unnecessary for the threads to share data.

然而,线程能够方便地与其他线程共享数据,正是它的主要特点之一。回想一下,多线程进程的所有线程共享该进程公共的堆。在本节中,我们详细研究线程可以使用的数据共享和保护机制。

However, a thread’s ability to easily share data with other threads is one of its main features. Recall that all the threads of a multithreaded process share the heap common to the process. In this section, we study the data sharing and protection mechanisms available to threads in detail.

线程同步(thread synchronization)指的是强制线程按特定的顺序执行。尽管同步线程可能会增加程序的运行时间,但为了确保程序的正确性,它常常是必要的。在本节中,我们主要讨论一种同步结构(互斥锁)如何帮助确保多线程程序的正确性。本节最后讨论其他几种常见的同步结构:信号量、屏障和条件变量。

Thread synchronization refers to forcing threads to execute in a particular order. Even though synchronizing threads can add to the runtime of a program, it is often necessary to ensure program correctness. In this section, we primarily discuss how one synchronization construct (a mutex) helps ensure the correctness of a threaded program. We conclude the section with a discussion of some other common synchronization constructs: semaphores, barriers and condition variables.

计数排序(CountSort)

CountSort

我们来研究一个稍微复杂一点的例子:计数排序(CountSort)。计数排序算法是一种简单的线性(O(N))排序算法,用于对取值范围已知且较小(共 R 种取值,R 远小于 N)的数据进行排序。为了说明计数排序如何工作,考虑一个有 15 个元素的数组 A,其中所有元素都是 0 到 9 之间(10 种可能取值)的随机值:

Let’s study a slightly more complicated example called CountSort. The CountSort algorithm is a simple linear (O(N)) sorting algorithm for sorting a known small range of R values, where R is much smaller than N. To illustrate how CountSort works, consider an array A of 15 elements, all of which contain random values between 0 and 9 (10 possible values):

1
A = [9, 0, 2, 7, 9, 0, 1, 4, 2, 2, 4, 5, 0, 9, 1]

对于一个特定的数组,计数排序的工作过程如下:

For a particular array, CountSort works as follows:

  1. 统计数组中每个值出现的频次。
  1. It counts the frequency of each value in the array.
  1. 按照每个值的频次逐个列举,覆盖原数组。
  1. It overwrites the original array by enumerating each value by its frequency.

第 1 步之后,每个值的频次被放进一个长度为 10 的 counts 数组中,其中 counts[i] 的值是值 i 在数组 A 中出现的频次。例如,由于数组 A 中有三个值为 2 的元素,所以 counts[2] 为 3。

After step 1, the frequency of each value is placed in a counts array of length 10, where the value of counts[i] is the frequency of the value i in array A. For example, since there are three elements with value 2 in array A, counts[2] is 3.

上面例子对应的 counts 数组如下:

The corresponding counts array for the previous example looks like the following:

1
counts = [3, 2, 3, 0, 2, 1, 0, 1, 0, 3]

注意,counts 数组中所有元素之和等于 A 的长度,即 15。

Note that the sum of all the elements in the counts array is equal to the length of A, or 15.

第 2 步用 counts 数组覆盖 A,利用频次计数来确定 A 中按排好序的顺序存放每个相继值的下标集合。所以,由于 counts 数组表明数组 A 中有三个值为 0 的元素和两个值为 1 的元素,最终数组的前三个元素将是 0,接下来两个将是 1。

Step 2 uses the counts array to overwrite A, using the frequency counts to determine the set of indices in A that store each consecutive value in sorted order. So, since the counts array indicates that there are three elements with value 0 and two elements with value 1 in array A, the first three elements of the final array will be 0, and the next two will be 1.

运行第 2 步之后,最终的数组如下:

After running step 2, the final array looks like the following:

1
A = [0, 0, 0, 1, 1, 2, 2, 2, 4, 4, 5, 7, 9, 9, 9]

下面是计数排序算法的一个串行实现,其中 count(第 1 步)和 overwrite(第 2 步)函数界限分明。为简洁起见,我们在这里没有列出整个程序,不过你可以下载源代码(countSort.c)。

Below is a serial implementation of the CountSort algorithm, with the count (step 1) and overwrite (step 2) functions clearly delineated. For brevity, we do not reproduce the whole program here, though you can download the source (countSort.c).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#define MAX 10 //the maximum value of an element. (10 means 0-9)

/*step 1:
* compute the frequency of all the elements in the input array and store
* the associated counts of each element in array counts. The elements in the
* counts array are initialized to zero prior to the call to this function.
*/
void countElems(int *counts, int *array_A, long length) {
int val, i;
for (i = 0; i < length; i++) {
val = array_A[i]; //read the value at index i
counts[val] = counts[val] + 1; //update corresponding location in counts
}
}

/* step 2:
* overwrite the input array (array_A) using the frequencies stored in the
* array counts
*/
void writeArray(int *counts, int *array_A) {
int i, j = 0, amt;

for (i = 0; i < MAX; i++) { //iterate over the counts array
amt = counts[i]; //capture frequency of element i
while (amt > 0) { //while all values aren't written
array_A[j] = i; //replace value at index j of array_A with i
j++; //go to next position in array_A
amt--; //decrease the amount written by 1
}
}
}

/* main function:
* gets array length from command line args, allocates a random array of that
* size, allocates the counts array, the executes step 1 of the CountSort
* algorithm (countsElem) followed by step 2 (writeArray).
*/
int main( int argc, char **argv ) {
//code ommitted for brevity -- download source to view full file

srand(10); //use of static seed ensures the output is the same every run

long length = strtol( argv[1], NULL, 10 );
int verbose = atoi(argv[2]);

//generate random array of elements of specified length
int *array = malloc(length * sizeof(int));
genRandomArray(array, length);

//print unsorted array (commented out)
//printArray(array, length);

//allocate counts array and initializes all elements to zero.
int counts[MAX] = {0};

countElems(counts, array, length); //calls step 1
writeArray(counts, array); //calls step2

//print sorted array (commented out)
//printArray(array, length);

free(array); //free memory

return 0;
}

在一个大小为 15 的数组上运行这个程序,得到下面的输出:

Running this program on an array of size 15 yields the following output:

1
2
3
4
5
$ ./countSort 15 1
array before sort:
5 8 8 5 8 7 5 1 7 7 3 3 8 3 4
result after sort:
1 3 3 3 4 5 5 5 7 7 7 8 8 8 8

这个程序的第二个参数是一个 verbose(详细输出)标志,表示程序是否打印输出。对于较大的数组,我们可能想运行程序但不一定要打印输出,这时这个选项就很有用。

The second parameter to this program is a verbose flag, which indicates whether the program prints output. This is a useful option for larger arrays for which we may want to run the program but not necessarily print out the output.

并行化 countElems:初次尝试

Parallelizing countElems: An Initial Attempt

计数排序由两个主要步骤组成,每一步都能从并行化中获益。在本章余下的部分,我们主要集中于第 1 步,即 countElems 函数的并行化。writeArray 函数的并行化留给读者作为练习。

CountSort consists of two primary steps, each of which benefits from being parallelized. In the remainder of the chapter, we primarily concentrate on the parallelization of step 1, or the countElems function. Parallelizing the writeArray function is left as an exercise for the reader.

下面的代码块展示了创建多线程版 countElems 函数的初次尝试。为简洁起见,这个例子省略了部分代码(参数解析、错误处理),完整的源代码可以在这里下载(countElems_p.c)。在下面的代码中,每个线程试图统计全局数组中分配给它的那部分中各元素的频次,并用统计结果更新一个全局的计数数组:

The code block that follows depicts a first attempt at creating a threaded countElems function. Parts of the code (argument parsing, error handling) are omitted in this example for the sake of brevity, but the full source can be downloaded here (countElems_p.c). In the code that follows, each thread attempts to count the frequency of the array elements in its assigned component of the global array and updates a global count array with the discovered counts:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/*parallel version of step 1 (first cut) of CountSort algorithm:
* extracts arguments from args value
* calculates the portion of the array that thread is responsible for counting
* computes the frequency of all the elements in assigned component and stores
* the associated counts of each element in counts array
*/
void *countElems( void *args ) {
struct t_arg * myargs = (struct t_arg *)args;
//extract arguments (omitted for brevity)
int *array = myargs->ap;
long *counts = myargs->countp;
//... (get nthreads, length, myid)

//assign work to the thread
long chunk = length / nthreads; //nominal chunk size
long start = myid * chunk;
long end = (myid + 1) * chunk;
long val;
if (myid == nthreads-1) {
end = length;
}

long i;
//heart of the program
for (i = start; i < end; i++) {
val = array[i];
counts[val] = counts[val] + 1;
}

return NULL;
}

main 函数看起来与我们之前的示例程序几乎一样:

The main function looks nearly identical to our earlier sample programs:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
int main(int argc, char **argv) {

if (argc != 4) {
//print out usage info (ommitted for brevity)
return 1;
}

srand(10); //static seed to assist in correctness check

//parse command line arguments
long t;
long length = strtol(argv[1], NULL, 10);
int verbose = atoi(argv[2]);
long nthreads = strtol(argv[3], NULL, 10);

//generate random array of elements of specified length
int *array = malloc(length * sizeof(int));
genRandomArray(array, length);

//specify counts array and initialize all elements to zero
long counts[MAX] = {0};

//allocate threads and args array
pthread_t *thread_array; //pointer to future thread array
thread_array = malloc(nthreads * sizeof(pthread_t)); //allocate the array
struct t_arg *thread_args = malloc( nthreads * sizeof(struct t_arg) );

//fill thread array with parameters
for (t = 0; t < nthreads; t++) {
//ommitted for brevity...
}

for (t = 0; t < nthreads; t++) {
pthread_create(&thread_array[t], NULL, countElems, &thread_args[t]);
}

for (t = 0; t < nthreads; t++) {
pthread_join(thread_array[t], NULL);
}

free(thread_array);
free(array);

if (verbose) {
printf("Counts array:\n");
printCounts(counts);
}
return 0;
}

为了结果可复现,随机数生成器用一个固定的值(10)作为种子,以确保 array(进而 counts)总是包含同一组数。另一个函数(printCounts)打印出全局 counts 数组的内容。我们预期,无论使用多少个线程,counts 数组的内容都应当相同。为简洁起见,清单中去掉了错误处理。

For reproducibility purposes, the random number generator is seeded with a static value (10) to ensure that array (and therefore counts) always contains the same set of numbers. An additional function (printCounts) prints out the contents of the global counts array. The expectation is that, regardless of the number of threads used, the contents of the counts array should always be the same. For brevity, error handling has been removed from the listing.

编译这个程序,并分别用一个、两个和四个线程在 1000 万个元素上运行,得到下面的结果:

Compiling the program and running it with one, two, and four threads over 10 million elements produces the following:

1
2
3
4
5
6
7
8
9
10
11
12
13
$ gcc -o countElems_p countElems_p.c -pthread

$./countElems_p 10000000 1 1
Counts array:
999170 1001044 999908 1000431 999998 1001479 999709 997250 1000804 1000207

$./countElems_p 10000000 1 2
Counts array:
661756 661977 657828 658479 657913 659308 658561 656879 658070 657276

$./countElems_p 10000000 1 4
Counts array:
579846 580814 580122 579772 582509 582713 582518 580917 581963 581094

注意,每次运行打印出的结果都有明显变化。尤其是,它们似乎随着线程数的不同而变化!这本不应该发生,因为我们使用了固定的种子,保证每次运行都得到同一组数。这些结果违背了多线程程序的一条基本准则:无论使用多少个线程,程序的输出都应当正确且一致。

Note that the printed results change significantly on each run. In particular, they seem to change as we vary the number of threads! This should not happen, since our use of the static seed guarantees the same set of numbers every run. These results contradict one of the cardinal rules for threaded programs: the output of a program should be correct and consistent regardless of the number of threads used.

由于我们并行化 countElems 的初次尝试似乎没有成功,我们来深入研究一下这个程序在做什么,看看如何修正它。

Since our first attempt at parallelizing countElems doesn’t seem to be working, let’s delve deeper into what this program is doing and examine how we might fix it.

数据竞争

Data Races

为了弄清发生了什么,我们考虑在多核系统的两个不同核心上用两个线程运行的一个例子。回想一下,任何线程的执行都可能随时被操作系统抢占,这意味着在任一时刻,每个线程可能正在执行某个函数的不同指令(也可能是同一条指令)。表 1 展示了经过 countElems 函数的一条可能的执行路径。为了更好地说明发生了什么,我们把 counts[val] = counts[val] + 1 这一行翻译成下面这串等价的指令:

To understand what’s going on, let’s consider an example run with two threads on two separate cores of a multicore system. Recall that the execution of any thread can be preempted at any time by the OS, which means that each thread could be running different instructions of a particular function at any given time (or possibly the same instruction). Table 1 shows one possible path of execution through the countElems function. To better illustrate what is going on, we translated the line counts[val] = counts[val] + 1 into the following sequence of equivalent instructions:

  1. 读取 counts[val],放入一个寄存器。
  1. Read counts[val] and place into a register.
  1. 修改寄存器,把它加一。
  1. Modify the register by incrementing it by one.
  1. 把寄存器的内容写回 counts[val]。
  1. Write the contents of the register to counts[val].

这称为读-改-写(read-modify-write)模式。在表 1 所示的例子中,每个线程在不同的核心上执行(线程 0 在核心 0 上,线程 1 在核心 1 上)。我们从时间步 i 开始考察进程的执行,此时两个线程的 val 都是 1。

This is known as the read-modify-write pattern. In the example shown in Table 1, each thread executes on a separate core (Thread 0 on Core 0, Thread 1 on Core 1). We start inspecting the execution of the process at time step i, where both threads have a val of 1.

表 1. 两个线程运行 countElems 的一种可能的执行序列

Table 1. A Possible Execution Sequence of Two Threads Running countElems

时间 线程 0 线程 1
i 读取 counts[1],放入核心 0 的寄存器 …​
i+1 寄存器加 1 读取 counts[1],放入核心 1 的寄存器
i+2 用寄存器的内容覆盖 counts[1] 寄存器加 1
i+3 …​ 用寄存器的内容覆盖 counts[1]
Time Thread 0 Thread 1
i Read counts[1] and place into Core 0’s register …​
i+1 Increment register by 1 Read counts[1] and place into Core 1’s register
i+2 Overwrite counts[1] with contents of register Increment register by 1
i+3 …​ Overwrite counts[1] with contents of register

假设在表 1 的执行序列之前,counts[1] 的值为 60。在时间步 i,线程 0 读取 counts[1],把值 60 放入核心 0 的寄存器。在时间步 i+1,线程 0 把核心 0 的寄存器加一,与此同时,线程 1 把 counts[1] 的当前值(60)读入核心 1 的寄存器。在时间步 i+2,线程 0 用值 61 更新 counts[1],同时线程 1 把存放在它本地寄存器中的值(60)加一。最终结果是,在时间步 i+3,counts[1] 被线程 1 用值 61 覆盖,而不是我们预期的 62!这实际上让 counts[1]「丢失」了一次加一!

Suppose that, prior to the execution sequence in Table 1, counts[1] contains the value 60. In time step i, Thread 0 reads counts[1] and places the value 60 in Core 0’s register. In time step i+1, while Thread 0 increments Core 0’s register by one, the current value in counts[1] (60) is read into Core 1’s register by Thread 1. In time step i+2, Thread 0 updates counts[1] with the value 61 while Thread 1 increments the value stored in its local register (60) by one. The end result is that during time step i+3, the value counts[1] is overwritten by Thread 1 with the value 61, not 62 as we would expect! This causes counts[1] to essentially “lose” an increment!

我们把两个线程试图写同一个内存位置的情形称为数据竞争(data race)。更一般地说,竞态条件(race condition)指的是两个操作同时执行会得到错误结果的任何情形。注意,同时读取 counts[1] 这个位置本身并不构成竞态条件,因为一般来说,单纯从内存中读取值不会有问题。是这一步与对 counts[1] 的写操作结合在一起,才导致了错误的结果。在大多数多线程程序中,这种读-改-写模式是一种特定类型的竞态条件,即数据竞争的常见来源。在讨论竞态条件及其修正方法时,我们集中讨论数据竞争。

We refer to the scenario in which two threads attempt to write to the same location in memory as a data race condition. More generally, a race condition refers to any scenario in which the simultaneous execution of two operations gives an incorrect result. Note that a simultaneous read of the counts[1] location would not in and of itself constitute a race condition, because values can generally read alone from memory without issue. It was the combination of this step with the writes to counts[1] that caused the incorrect result. This read-modify-write pattern is a common source of a particular type of race condition, called a data race, in most threaded programs. In our discussion of race conditions and how to fix them, we focus on data races.

原书注 · 原子操作(Atomic operations)

如果一个线程感觉某个操作是不间断地执行的(换句话说,是一个「要么全做、要么不做」的动作),这个操作就被定义为原子的(atomic)。在一些库中,会用一个关键字或类型来指明某块计算应当被视为原子的。在前面的例子中,counts[val] = counts[val] + 1 这一行(即使写成 counts[val]++)不是原子的,因为这一行在机器层面实际上对应好几条指令。需要互斥这样的同步结构,才能确保没有数据竞争。一般来说,除非显式地强制互斥,否则应当假定所有操作都是非原子的。

An operation is defined as being atomic if a thread perceives it as executing without interruption (in other words, as an “all or nothing” action). In some libraries, a keyword or type is used to specify that a block of computation should be treated as being atomic. In the previous example, the line counts[val] = counts[val] + 1 (even if written as counts[val]++) is not atomic, because this line actually corresponds to several instructions at the machine level. A synchronization construct like mutual exclusion is needed to ensure that there are no data races. In general, all operations should be assumed to be nonatomic unless mutual exclusion is explicitly enforced.

译注 · 用机器码看「读-改-写」与 C11 原子操作

译者在 Apple Silicon Mac 上用 clang -O2 -S 编译 plain[val] = plain[val] + 1;,得到的正是上文所说的三步:ldr(读)、add(改)、str(写)。C11 起,标准库 <stdatomic.h> 提供了原子类型和原子操作,例如 atomic_fetch_add,它以原子方式把一个值加到原子对象上,相当于一次原子的读-改-写(见 cppreference:atomic_fetch_add)。把 counts 声明为 atomic_long counts[10]; 并改用 atomic_fetch_add(&counts[val], 1); 后,同样的编译得到的是单条 ARMv8.1 原子指令 ldaddal,这类简单的计数器就不再需要互斥锁了。

要记住,并非两个线程的所有执行序列都会导致竞态条件。考虑表 2 中线程 0 和线程 1 的示例执行序列。

Keep in mind that not all execution sequences of the two threads cause a race condition. Consider the sample execution sequence of Threads 0 and 1 in Table 2.

表 2. 两个线程运行 countElems 的另一种可能的执行序列

Table 2. Another Possible Execution Sequence of Two Threads Running countElems

时间 线程 0 线程 1
i 读取 counts[1],放入核心 0 的寄存器 …​
i+1 寄存器加 1 …​
i+2 用寄存器的内容覆盖 counts[1] …​
i+3 …​ 读取 counts[1],放入核心 1 的寄存器
i+4 …​ 寄存器加 1
i+5 …​ 用寄存器的内容覆盖 counts[1]
Time Thread 0 Thread 1
i Read counts[1] and place into Core 0’s register …​
i+1 Increment register by 1 …​
i+2 Overwrite counts[1] with contents of register …​
i+3 …​ Read counts[1] and place into Core 1’s register
i+4 …​ Increment register by 1
i+5 …​ Overwrite counts[1] with contents of register

在这个执行序列中,线程 1 直到线程 0 用新值(61)更新了 counts[1] 之后才读取它。最终结果是,线程 1 在时间步 i+3 从 counts[1] 中读到值 61,把它放入核心 1 的寄存器,并在时间步 i+5 把值 62 写入 counts[1]。

In this execution sequence, Thread 1 does not read from counts[1] until after Thread 0 updates it with its new value (61). The end result is that Thread 1 reads the value 61 from counts[1] and places it into Core 1’s register during time step i+3, and writes the value 62 to counts[1] in time step i+5.

要修正数据竞争,首先必须把临界区(critical section)隔离出来,即为了确保正确的行为而必须原子地(孤立地)执行的那部分代码。在多线程程序中,更新共享资源的代码块通常被认定为临界区。

To fix a data race, we must first isolate the critical section, or the subset of code that must execute atomically (in isolation) to ensure correct behavior. In threaded programs, blocks of code that update a shared resource are typically identified to be critical sections.

在 countElems 函数中,对 counts 数组的更新应当放在临界区中,以确保值不会因多个线程更新同一内存位置而丢失:

In the countElems function, updates to the counts array should be put in a critical section to ensure that values are not lost due to multiple threads updating the same location in memory:

1
2
3
4
5
long i;
for (i = start; i < end; i++) {
val = array[i];
counts[val] = counts[val] + 1; //this line needs to be protected
}

由于 countElems 中的根本问题是多个线程同时访问 counts,所以需要一种机制来确保一次只有一个线程在临界区内执行。使用同步结构(例如下一节介绍的互斥锁)会强制线程依次进入临界区。

Since the fundamental problem in countElems is the simultaneous access of counts by multiple threads, a mechanism is needed to ensure that only one thread executes within the critical section at a time. Using a synchronization construct (like a mutex, which is covered in the next section) will force the threads to enter the critical section sequentially.