第四章：并发编程

第四章：并发编程
4.1 并行计算导论
在过去，大多数计算机只有一个处理组件，称为处理器或中央处理器（CPU）。由于这个硬件限制，计算机程序通常是为串行计算编写的。为了解决问题，算法被设计为逐步解决问题的步骤，并以串行指令流的形式在计算机程序中实现。在只有一个CPU的情况下，一次只能执行一个指令和步骤。然而，基于分治原则（如二叉树搜索和快速排序）的算法经常具有高度的并行性，可以通过并行或并发执行来提高计算速度。并行计算是一种计算方案，利用多个执行并行算法的处理器来更快地解决问题。在过去，由于并行计算对计算资源的大量需求，普通程序员很少能进行并行计算。然而，随着多核处理器的出现，大多数操作系统（如Linux）都支持对称多处理（SMP）。即使对于普通程序员来说，现在也可以实现并行计算。显然，并行计算是计算的未来发展方向。

4.1.1 顺序算法与并行算法
顺序算法中的begin-end代码块可能包含多个步骤。所有步骤都是通过单个任务依次执行的，每次只执行一个步骤。当所有步骤执行完成时，算法结束。相反，对于并行算法的描述，它使用cobegin-coend代码块来指定并行算法的独立任务。在cobegin-coend块中，所有任务都是并行执行的，紧随cobegin-coend代码块的下一个步骤将只在所有这些任务完成之后执行。

4.1.2 并行性与并发性
通常，并行算法只识别可并行执行的任务，但不规定如何将任务映射到处理组件。在理想情况下，并行算法中的所有任务都应同时实时执行。然而，真正的并行执行只能在具有多个处理组件的系统中实现，如多处理器或多核系统。在单个CPU系统中，一次只能执行一个任务。在这种情况下，不同的任务只能并发执行，即在逻辑上并行执行。在单CPU系统中，并发性通过多任务处理来实现。

4.2 线程
4.2.1 线程的原理
一个操作系统（OS）包含许多并发进程。在进程模型中，进程是独立的执行单元。所有进程都在内核模式或用户模式下执行。在内核模式下，进程在唯一地址空间上执行，与其他进程是分开的。虽然每个进程都是一个独立的单元，但它只有一个执行路径。当某个进程必须等待某个事件发生时，比如I/O完成事件，它就会暂停，整个进程都停止执行。线程是在同一个地址空间中执行的进程的独立执行单元。创建一个进程就是在唯一地址空间中创建一个主线程。当一个进程开始时，它执行该进程的主线程。如果只有一个主线程，那么进程和线程实际上是没有区别的。然而，主线程可能会创建其他线程，每个线程又可以创建更多的线程，以此类推。进程的所有线程都在同一个地址空间中执行，但每个线程是独立的执行单元。在线程模型中，如果一个线程被挂起，其他线程可以继续执行。除了共享相同的地址空间之外，线程还共享进程的许多其他资源，如用户ID、打开的文件描述符和信号等。可以将其类比为进程是一个有房屋管理员（主线程）的房子，线程是住在进程房子里的人。房子里的每个人都可以独立执行自己的任务，但他们会共用一些公共设施，比如同一个邮箱、厨房和浴室等。过去，大多数计算机供应商都在自己的专有操作系统中支持线程。不同系统之间的实现有很大的差异。目前，几乎所有的操作系统都支持 Pthread，它是IEEE POSIX 1003.1c的线程标准（POSIX 1995）。

4.2.2 线程的优点
线程的创建和切换速度更快。
当在进程中创建线程时，操作系统不需要为新的线程分配内存和创建页表，因为线程与进程共享同一个地址空间。因此，创建线程比创建进程更快。
线程的响应速度更快。
一个进程只有一个执行路径。当一个进程被挂起时，整个进程都会停止执行。相反，当一个线程被挂起时，同一进程中的其他线程可以继续执行。
线程更适合并行计算。
并行计算的目标是利用多个执行路径更快地解决问题。基于分治原则（如二叉树搜索和快速排序）的算法经常表现出高度的并行性，可以通过并行或并发执行来提高计算速度。

4.2.3 线程的缺点
由于地址空间共享，线程需要明确同步来避免冲突。
许多库函数可能不是线程安全的，例如传统的strtok()函数将一个字符串分成一系列标记。通常，任何使用全局变量或依赖静态内存内容的函数都是线程不安全的。为了使库函数适应线程环境，需要进行大量的工作。
在单个CPU系统上，使用线程解决问题实际上比使用顺序程序更慢，这是由于运行时创建线程和切换上下文的系统开销造成的。

4.3 线程操作
线程的执行轨迹与进程类似。线程可以在内核模式或用户模式下执行。在用户模式下，线程在进程的相同地址空间中执行，但每个线程都有自己的执行堆栈。线程是独立的执行单元，可以根据操作系统内核的调度策略对内核进行系统调用，挂起和激活以继续执行等。

4.4 线程管理函数
4.4.1 创建线程
使用pthread_create()函数创建线程：
int pthread_create(pthread_t *thread, const pthread_attr_t *attr, void *(*start_routine)(void *), void *arg);
如果成功则返回0，如果失败则返回错误代码。pthread_create()函数的参数为：

thread是指向pthread_t类型变量的指针，用于存储线程的ID。
attr是指向线程属性的指针，可以为NULL表示使用默认属性。
start_routine是新线程执行的函数的入口地址。
arg是指向线程函数参数的指针。
线程属性参数attr最复杂，可以使用pthread_attr_init()函数进行初始化，并设置属性，最后通过pthread_attr_destroy()函数释放资源。通常情况下，可以使用NULL作为属性参数，以使用默认属性。

4.4.2 线程ID
线程ID是一个不透明的数据类型，取决于具体实现。因此，不应直接比较线程ID。如果需要，可以使用pthread_equal()函数进行比较：
int pthread_equal(pthread_t t1, pthread_t t2);

4.4.3 线程终止
线程函数执行结束后，线程即终止。或者，线程可以显式调用函数
void pthread_exit(void *value_ptr);
进行终止，其中value_ptr是线程的退出状态。通常，退出值为0表示正常终止，非0值表示异常终止。

4.4.4 线程连接
一个线程可以等待另一个线程终止，通过调用pthread_join()函数进行连接，并将线程的退出状态作为value_ptr返回。

4.5 线程示例程序
计算一个N×N整数矩阵中所有元素的和：

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#define N 4
int A[N][N], sum[N];
void *func(void *arg)
{
// 线程函数
int j, row;
pthread_t tid = pthread_self(); // 获取线程ID号
row = (int)arg;
printf(“Thread %d [%lu] computes sum of row %d\n”, row, tid, row);

// 计算A[row]的和并存入全局变量sum[row]
for (j = 0; j < N; j++)
    sum[row] += A[row][j];

printf("Thread %d [%lu] done: sum[%d] = %d\n", row, tid, row, sum[row]);

pthread_exit((void *)0); // 线程退出，0表示正常终止

}

int main(int argc, char *argv[])
{
pthread_t thread[N]; // 线程ID
int i, j, r, total = 0;
void *status;

printf("Main: initialize A matrix\n");

// 初始化A矩阵
for (i = 0; i < N; i++) {
    sum[i] = 0;
    for (j = 0; j < N; j++) {
        A[i][j] = i * N + j + 1;
        printf("%4d", A[i][j]);
    }
    printf("\n");
}

printf("Main: create %d threads\n", N);

// 创建并发执行的线程
for (i = 0; i < N; i++) {
    pthread_create(&thread[i], NULL, func, (void *)i);
}

printf("Main: try to join with threads\n");

// 等待线程终止并获取退出状态
for (i = 0; i < N; i++) {
    pthread_join(thread[i], &status);
    printf("Main: joined with %d [%lu]: status = %d\n", i, thread[i], (int)status);
}

printf("Main: compute and print total sum: ");

// 计算并打印所有行的和
for (i = 0; i < N; i++)
    total += sum[i];
printf("total = %d\n", total);

pthread_exit(NULL);

}

4.6 线程同步
由于线程在进程的同一地址空间中执行，它们共享所有全局变量和数据结构。当多个线程尝试修改同一个共享变量或数据结构时，如果修改的结果取决于线程的执行顺序，就称为竞态条件。在并发程序中，竞态条件是绝对不能发生的，否则结果可能不一致。除了连接操作之外，并发执行的线程通常需要相互协作。为了避免竞态条件并支持线程协作，需要进行线程同步。通常，同步是一种机制和规则，用于确保共享数据对象的完整性和并发实体的协调性。它可以应用于内核模式下的进程，也可以应用于用户模式下的线程。

4.6.1 互斥量
在Pthread中，锁被称为互斥量，意味着它们彼此互斥。

静态方式：
pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;

动态方式：
pthread_mutex_t mutex;
pthread_mutex_init(&mutex, NULL);

4.6.2 避免死锁
死锁是一种状态，在该状态下，许多执行实体相互等待，因此无法继续进行。有多种方法可以解决潜在的死锁问题，包括死锁预防、死锁规避、死锁检测和死锁恢复等。在实际系统中，唯一可行的方法是死锁预防，即试图在设计并发算法时防止死锁的发生。

4.6.3 条件变量
条件变量提供线程协作的一种方法。在Pthread中，使用pthread_cond_t类型来声明条件变量，必须在使用之前进行初始化。条件变量可以通过静态或动态方式进行初始化。

4.6.4 生产者-消费者问题
一组生产者进程和一组消费者进程共享一个初始为空、大小为n的缓冲区。只有当缓冲区为空时，生产者才能将消息放入缓冲区；只有当缓冲区不为空时，消费者才能从中取出消息。由于缓冲区是一个临界资源，它只允许一个生产者放入消息或一个消费者取出消息。

4.6.5 信号量
信号量和条件变量之间的主要区别在于，信号量包含一个计数器，并且可以对计数器进行操作、测试计数器的值并做出决策等，所有这些操作都是临界区的原子操作或基本操作，而条件变量则需要特定的互斥量来执行临界区。在Pthreads中，互斥量严格用于互斥保护。条件变量可用于线程协作。相反，可以将使用初始值1初始化的信号量视为锁。带有其他初始值的信号量可以用于协作。因此，信号量比条件变量更通用、更灵活。

4.6.6 屏障
创建一个屏障对象：
pthread_barrier_t barrier;
调用pthread_barrier_init(&barrier, NULL, nthreads);
在线程中使用barrier对其进行初始化，然后主线程创建工作线程来执行任务。工作线程使用pthread_barrier_wait(&barrier)进行同步后继续执行。