第五章并发

导读

并发（Concurrency）是操作系统和现代软件系统中最重要也最复杂的主题之一。当多个执行流（进程或线程）同时访问共享资源时，如果不加以正确的同步和控制，就会出现竞态条件（Race Condition），导致程序行为不确定甚至错误。

本章将系统介绍并发的基本原理和同步机制。我们将从线程的概念开始，逐步深入锁（Lock）、条件变量（Condition Variable）、信号量（Semaphore）等核心同步原语，讨论经典的并发问题（生产者-消费者、读者-写者等），最后介绍无锁编程和并发编程的最佳实践。理解并发原理，对于编写正确的多线程程序、设计高效的操作系统至关重要。

5.1 并发的基本概念

5.1.1 什么是并发

并发是指多个计算活动在重叠的时间段内执行。在单核处理器上，并发通过时间片轮转实现——多个线程交替执行，宏观上看起来是"同时"运行。在多核处理器上，并发可以通过真正的并行实现——多个线程在不同核心上同时执行。

并发带来了巨大的好处：

提高资源利用率：一个线程等待I/O时，其他线程可以继续执行。
提高响应性：长时间运行的任务可以在后台执行，不阻塞用户交互。
利用多核：将工作分散到多个核心，提高吞吐量。

但并发也带来了严峻的挑战：

竞态条件：多个线程访问共享数据时，执行顺序不确定，可能导致错误结果。
死锁：多个线程互相等待对方持有的资源，导致所有线程都无法继续。
饥饿：某些线程长期得不到资源，无法执行。
调试困难：并发bug通常是非确定性的，难以复现和定位。

5.1.2 原子性与竞态条件

原子性（Atomicity）：一个操作是原子的，意味着它要么完全执行，要么完全不执行，中间状态对外不可见。

竞态条件（Race Condition）：当多个线程访问共享数据，且最终结果取决于线程的执行顺序时，就存在竞态条件。

经典示例：

// 共享变量
int counter = 0;

// 线程A和线程B都执行以下操作
void increment() {
    counter++;  // 这不是原子操作！
}

counter++ 实际上包含三个步骤：

从内存读取 counter 的值到寄存器。

寄存器值加1。

将寄存器的值写回内存。

如果线程A和线程B交错执行，可能出现以下情况：

A读取counter=0
B读取counter=0
A将counter写为1
B将counter写为1
最终结果：counter=1（期望是2）

这就是典型的竞态条件。

5.1.3 临界区与互斥

临界区（Critical Section）：访问共享资源的代码段。在临界区中，必须保证互斥——同一时刻最多只有一个线程在临界区内执行。

互斥（Mutual Exclusion）：保证同一时刻最多只有一个线程进入临界区的机制。

临界区问题的解决方案必须满足以下要求：

互斥：同一时刻最多一个线程在临界区。

进步（Progress）：如果没有线程在临界区，且有线程想进入，则必须允许其中一个进入。

有界等待（Bounded Waiting）：线程请求进入临界区后，必须在有限步内被允许进入（不能无限等待）。

5.2 线程

5.2.1 线程的概念

线程（Thread）是进程内的执行单元。一个进程可以包含多个线程，它们共享进程的地址空间（代码、数据、堆）和文件描述符，但每个线程有独立的栈和寄存器状态。

线程的优势：

轻量级：创建和销毁线程的开销远小于进程。
共享方便：同一进程的线程天然共享内存，通信方便。
响应性好：长时间操作可以在后台线程执行，不阻塞主线程。

5.2.2 用户级线程与内核级线程

用户级线程（User-Level Thread）

线程管理在用户空间完成，内核不可见。
优点：切换开销小（无需陷入内核）、调度灵活。
缺点：一个线程阻塞会导致整个进程阻塞、无法利用多核。

内核级线程（Kernel-Level Thread）

线程管理由内核完成，内核为每个线程维护TCB（Thread Control Block）。
优点：一个线程阻塞不影响其他线程、可以利用多核。
缺点：切换开销大（需要陷入内核）。

现代操作系统的选择：Linux、Windows等现代操作系统都采用内核级线程。在Linux中，线程通过 clone() 系统调用创建，每个线程对应一个 task_struct。

5.2.3 POSIX线程（pthreads）

POSIX线程（pthreads）是UNIX/Linux系统的标准线程API：

#include <pthread.h>

// 创建线程
int pthread_create(pthread_t *thread, const pthread_attr_t *attr,
                   void *(*start_routine)(void *), void *arg);

// 等待线程结束
int pthread_join(pthread_t thread, void **retval);

// 线程退出
void pthread_exit(void *retval);

5.3 锁（Lock）

5.3.1 锁的基本概念

锁（Lock）是最基本的同步原语，用于实现互斥。锁有两种状态：锁定（Locked）和未锁定（Unlocked）。

加锁（Lock/Acquire）：如果锁未锁定，则将其设为锁定状态并继续；如果锁已锁定，则等待直到锁可用。
解锁（Unlock/Release）：将锁设为未锁定状态，允许其他线程获取。

使用锁保护临界区：

lock_t mutex;

void critical_section() {
    lock(&mutex);
    // 临界区代码
    counter++;
    unlock(&mutex);
}

5.3.2 锁的实现

基于硬件的原子指令

现代处理器提供了一些原子指令，可以用来实现锁：

测试并设置（Test-and-Set, TAS）：原子地读取一个内存位置的值并将其设为1，返回旧值。
比较并交换（Compare-and-Swap, CAS）：原子地比较内存位置的值与预期值，如果相等则写入新值，返回旧值。
获取并相加（Fetch-and-Add, FAA）：原子地将内存位置的值加1，返回旧值。

基于TAS的自旋锁实现：

typedef struct {
    int flag;  // 0: unlocked, 1: locked
} lock_t;

void init(lock_t *lock) {
    lock->flag = 0;
}

void lock(lock_t *lock) {
    while (test_and_set(&lock->flag) == 1) {
        // 自旋等待
    }
}

void unlock(lock_t *lock) {
    lock->flag = 0;
}

5.3.3 锁的评价标准

互斥性：锁是否正确地实现了互斥？
公平性：是否每个请求锁的线程最终都能获得锁？
性能：

- 无竞争时的开销（单线程获取和释放锁的开销）。

- 有竞争时的开销（多线程竞争锁的开销）。

- 单CPU上的开销。

- 多CPU上的开销。

5.3.4 锁的类型

自旋锁（Spinlock）

获取锁失败的线程不断循环检查（自旋）。
优点：无需上下文切换，延迟低。
缺点：浪费CPU时间。
适用场景：锁持有时间短、多处理器系统。

互斥锁（Mutex）

获取锁失败的线程被阻塞（睡眠），让出CPU。
优点：不浪费CPU时间。
缺点：涉及上下文切换，延迟较高。
适用场景：锁持有时间长、单处理器或多处理器系统。

读写锁（Read-Write Lock）

允许多个读者同时访问，但写者独占。
适用于读多写少的场景。

乐观锁（Optimistic Lock）

不加锁执行操作，提交时检查是否有冲突。
适用于冲突概率低的场景。

5.4 条件变量（Condition Variable）

5.4.1 条件变量的概念

条件变量（Condition Variable）用于线程间的协调——一个线程等待某个条件成立，另一个线程在条件成立时唤醒等待的线程。

条件变量提供两个基本操作：

wait(cv, mutex)：释放mutex，等待cv被通知。被唤醒后重新获取mutex。
signal(cv)：唤醒一个等待cv的线程（如果有）。
broadcast(cv)：唤醒所有等待cv的线程。

5.4.2 生产者-消费者问题

生产者-消费者问题（ bounded-buffer problem）是经典的并发问题：

// 共享缓冲区
int buffer[MAX];
int count = 0;
lock_t mutex;
cond_t cond_prod, cond_cons;

void producer(int item) {
    lock(&mutex);
    while (count == MAX) {
        wait(&cond_prod, &mutex);
    }
    buffer[count++] = item;
    signal(&cond_cons);  // 通知消费者
    unlock(&mutex);
}

void consumer() {
    lock(&mutex);
    while (count == 0) {
        wait(&cond_cons, &mutex);
    }
    int item = buffer[--count];
    signal(&cond_prod);  // 通知生产者
    unlock(&mutex);
    return item;
}

5.4.3 使用条件变量的注意事项

始终在循环中检查条件：使用 while 而非 if，因为可能存在虚假唤醒（Spurious Wakeup）或多个线程被同时唤醒。

始终配合互斥锁使用：条件变量必须与互斥锁配合使用，以避免竞态条件。

注意信号丢失：如果在 signal() 时没有线程在等待，信号会丢失。

注意死锁：确保在正确的时机获取和释放锁。

5.5 信号量（Semaphore）

5.5.1 信号量的概念

信号量（Semaphore）由Dijkstra提出，是一个更通用的同步原语。信号量是一个整数变量，支持两个原子操作：

wait(S) / P(S) / down(S)：S = S - 1；如果 S < 0，则阻塞。
signal(S) / V(S) / up(S)：S = S + 1；如果 S ≤ 0，则唤醒一个等待的线程。

5.5.2 信号量的类型

二值信号量（Binary Semaphore）

信号量值只能是0或1。
等价于互斥锁。
用于实现互斥。

计数信号量（Counting Semaphore）

信号量值可以是任意非负整数。
用于控制对有限资源的访问。
初始值为可用资源的数量。

5.5.3 用信号量解决生产者-消费者问题

sem_t empty;   // 空槽位数，初始为MAX
sem_t full;    // 满槽位数，初始为0
sem_t mutex;   // 互斥锁，初始为1

void producer(int item) {
    wait(&empty);      // 等待空槽
    wait(&mutex);      // 进入临界区
    buffer[add(item);
    signal(&mutex);    // 离开临界区
    signal(&full);     // 增加满槽数
}

void consumer() {
    wait(&full);       // 等待满槽
    wait(&mutex);      // 进入临界区
    int item = remove();
    signal(&mutex);    // 离开临界区
    signal(&empty);    // 增加空槽数
    return item;
}

5.5.4 读者-写者问题

读者-写者问题允许多个读者同时读，但写者独占：

sem_t rw_mutex;   // 读写互斥，初始为1
sem_t mutex;      // 读者计数互斥，初始为1
int read_count = 0;

void reader() {
    wait(&mutex);
    read_count++;
    if (read_count == 1) {
        wait(&rw_mutex);  // 第一个读者获取读写锁
    }
    signal(&mutex);
    
    // 读操作
    read_data();
    
    wait(&mutex);
    read_count--;
    if (read_count == 0) {
        signal(&rw_mutex);  // 最后一个读者释放读写锁
    }
    signal(&mutex);
}

void writer() {
    wait(&rw_mutex);
    // 写操作
    write_data();
    signal(&rw_mutex);
}

5.6 经典并发问题

5.6.1 哲学家就餐问题

五个哲学家围坐在圆桌旁，每人左右各有一支筷子。哲学家需要同时拿到左右两支筷子才能就餐。如何避免死锁？

解决方案：

资源分级：规定哲学家先拿编号小的筷子，再拿编号大的筷子。

限制就餐人数：最多允许四个哲学家同时拿筷子。

Chandy/Misra算法：分布式解决方案，使用消息传递。

5.6.2 吸烟者问题

三个吸烟者共享一张桌子，桌上有烟草、纸和火柴。每个吸烟者需要其中两种材料才能吸烟。一个代理轮流在桌上放两种材料，对应的吸烟者取走材料吸烟。

5.6.3 睡眠理发师问题

一个理发师、一把理发椅、N把等待椅。没有顾客时理发师睡觉。顾客来了如果理发师在睡觉则唤醒他，否则在等待椅等待。如果等待椅满了，顾客离开。

5.7 死锁

5.7.1 死锁的条件

死锁（Deadlock）是指两个或多个线程互相等待对方持有的资源，导致所有线程都无法继续。死锁发生的四个必要条件（Coffman条件）：

互斥（Mutual Exclusion）：资源一次只能被一个线程使用。

持有并等待（Hold and Wait）：线程持有至少一个资源，同时请求另一个被其他线程持有的资源。

不可抢占（No Preemption）：资源只能由持有者主动释放，不能被强制剥夺。

循环等待（Circular Wait）：存在一个线程等待环路。

5.7.2 死锁的处理策略

预防（Prevention）

破坏四个必要条件之一。
例如：要求线程一次性申请所有资源（破坏"持有并等待"）。

避免（Avoidance）

在运行时动态检查资源分配状态，确保系统始终处于安全状态。
经典算法：银行家算法（Banker's Algorithm）。

检测与恢复（Detection and Recovery）

允许死锁发生，定期检测，发现后采取措施恢复。
恢复方法：终止死锁线程、抢占资源等。

忽略（Ignorance）

假装死锁不会发生（如Linux和Windows的默认策略）。
如果发生死锁，手动重启系统。

5.8 无锁编程

5.8.1 无锁数据结构

无锁（Lock-Free）数据结构不依赖传统的锁，而是使用原子操作实现并发访问。无锁数据结构可以保证至少一个线程在有限步内完成操作。

无锁栈示例（基于CAS）：

typedef struct node {
    int data;
    struct node *next;
} node_t;

typedef struct {
    node_t *top;
} stack_t;

void push(stack_t *s, int data) {
    node_t *new_node = malloc(sizeof(node_t));
    new_node->data = data;
    do {
        new_node->next = s->top;
    } while (!CAS(&s->top, new_node->next, new_node));
}

int pop(stack_t *s) {
    node_t *old_top;
    do {
        old_top = s->top;
        if (old_top == NULL) return -1;  // 栈空
    } while (!CAS(&s->top, old_top, old_top->next));
    return old_top->data;
}

5.8.2 无锁编程的挑战

ABA问题：CAS检查值是否变化，但值可能从A变为B再变回A，CAS无法检测到这种变化。
内存回收：无锁数据结构中，节点的内存回收需要特别小心，避免其他线程仍在使用该节点。
复杂性：无锁算法通常比加锁算法复杂得多，正确性证明困难。

5.9 常见误区

误区一：使用volatile可以替代锁

volatile 关键字只保证编译器不会优化掉对变量的访问，但不保证原子性。在多线程环境中，volatile 不能替代锁。

误区二：加锁粒度越细越好

细粒度锁可以减少竞争，但增加了死锁风险和代码复杂度。锁的粒度需要根据具体场景权衡。

误区三：无锁编程总是比加锁快

无锁编程在某些场景下性能更好，但并非总是如此。在高竞争场景下，CAS的重试开销可能超过锁的开销。此外，无锁代码更复杂、更容易出错。

误区四：死锁只发生在多线程程序中

死锁也可以发生在多进程环境中（如两个进程互相等待对方持有的文件锁）。分布式系统中的死锁更加隐蔽和复杂。

误区五：条件变量的signal会立即唤醒等待线程

signal() 只是标记条件可能成立，等待线程被唤醒后需要重新获取互斥锁才能继续执行。如果此时互斥锁被其他线程持有，等待线程会继续阻塞。

5.10 实践应用

5.10.1 使用pthreads编程

#include <stdio.h>
#include <pthread.h>
#include <unistd.h>

#define NUM_THREADS 4
int counter = 0;
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;

void *thread_func(void *arg) {
    for (int i = 0; i < 100000; i++) {
        pthread_mutex_lock(&mutex);
        counter++;
        pthread_mutex_unlock(&mutex);
    }
    return NULL;
}

int main() {
    pthread_t threads[NUM_THREADS];
    
    for (int i = 0; i < NUM_THREADS; i++) {
        pthread_create(&threads[i], NULL, thread_func, NULL);
    }
    
    for (int i = 0; i < NUM_THREADS; i++) {
        pthread_join(threads[i], NULL);
    }
    
    printf("Final counter: %d\n", counter);
    pthread_mutex_destroy(&mutex);
    return 0;
}

5.10.2 使用Thread Sanitizer检测并发bug

bash

# 编译时启用Thread Sanitizer
gcc -fsanitize=thread -g program.c -o program -lpthread

# 运行程序，TSan会报告数据竞争
./program

5.10.3 并发编程最佳实践

最小化共享：尽量减少线程间共享的数据。

不可变数据：如果数据在创建后不再修改，可以安全地共享。

线程局部存储：使用线程局部变量（__thread 或 thread_local）避免共享。

高级抽象：优先使用高级并发抽象（如并发队列、actor模型）而非原始锁。

形式化验证：对关键并发代码使用模型检查工具验证正确性。

5.11 本章小结

本章系统介绍了并发的基本原理和同步机制，主要内容包括：

并发基础：并发带来好处也带来挑战。竞态条件和原子性是理解并发的关键概念。

线程：线程是进程内的执行单元，共享地址空间但有独立的栈和寄存器。现代操作系统使用内核级线程。

锁：锁是实现互斥的基本机制。自旋锁适合短临界区，互斥锁适合长临界区。锁的实现依赖硬件原子指令。

条件变量：用于线程间协调，配合互斥锁使用。生产者-消费者问题是经典应用。

信号量：更通用的同步原语，可以实现互斥和资源计数。读者-写者问题是典型应用。

经典并发问题：哲学家就餐、吸烟者问题、睡眠理发师等问题展示了并发编程的复杂性。

死锁：四个必要条件（互斥、持有并等待、不可抢占、循环等待）。处理策略包括预防、避免、检测与恢复。

无锁编程：使用原子操作实现并发数据结构，避免锁的开销，但实现复杂。

并发是操作系统和现代软件系统的核心挑战。正确理解和使用同步机制，是编写可靠并发程序的基础。

第五章 并发

导读