ICS12 并发编程

type

status

date

slug

summary

并发编程 Concurrent Programming

本文介绍了并发编程的基本概念、潜在风险以及一些常见的并发编程模型，涉及基于进程、I/O多路复用、线程等不同技术实现的服务器设计。同时，也介绍了线程同步机制和信号量等技术，帮助读者理解如何高效地进行多线程编程并避免常见问题，如死锁、活锁、数据竞争等。

并发与并行

并发（Concurrency）是指在同一时间段内处理多个任务。这些任务可能同时进行，也可能交替进行，目的是提高资源利用率和系统响应速度。并发编程常用于多线程、多进程或异步编程模型中。

并行（Parallelism）是指在多个任务在多核或多处理器上并发地执行。并行是并发的子集。

并发编程的潜在风险

并发编程虽然能够提高程序的执行效率，但也带来了一些潜在的风险，主要包括数据竞争、死锁、活锁和饥饿等问题。

数据竞争（data race）：当多个进程并发地访问共享资源且至少有一个进程进行写操作时，可能会出现数据竞争，导致数据不一致性。

死锁（deadlock）：多个进程因争夺资源陷入一种互相等待的状态，导致所有相关进程都无法继续执行，形成僵局。死锁的出现条件包括：

互斥条件（Mutual Exclusion）：至少有一个资源必须处于非共享模式，即一次只能被一个进程使用。如果另一个进程请求该资源，请求进程必须等待，直到资源被释放。
占有并等待（Hold and Wait）：一个进程必须占有至少一个资源，并且正在等待获取其他进程占有的资源。
非抢占（No Preemption）：资源不能被强制从占有它的进程中剥夺，只能由占有它的进程显式释放。
循环等待（Circular Wait）：存在一个进程的循环链，每个进程都在等待链中下一个进程占有的资源。

例如：信号处理程序（signal handler）中若调用printf函数，由于要访问跨进程的缓冲区，会先给缓冲区“上锁”，使其不能被访问。若此时该进程再被信号中断，重入printf时需要等待缓冲区“解锁”，而这永远无法实现，也即出现死锁。

活锁（livelock）：多个进程因争夺资源反复尝试解决冲突，但由于策略不当，导致它们不断重复相同的操作，但始终无法取得进展。

饥饿（starvation）：某些进程由于资源分配策略不当，长期无法获得所需的资源，导致它们无法完成任务或执行操作。

服务器-客户端中的并发问题

在上一章中我们初步实现的是串行/迭代式（iterative）服务器：如果一个请求占用了进程资源，服务器无法处理其他请求，造成阻塞。因此我们需要开发并行服务器：通过进程、事件、线程等技术，服务器能够同时处理多个请求。

基于进程的服务器

基于进程的并发模型在服务器中很常见，通常通过 fork 系统调用来创建新的子进程来处理客户端的请求。

在此模型中，初始进程一直使用 listenfd 进行监听，遇到连接请求时 Fork() 出一个子进程，子进程负责通过 connfd 与客户端建立连接。不同服务器进程之间不交换信息，父进程需要回收僵尸子进程。

优点：能够并发地处理多个请求；简单直接，且进程之间没有共享资源。

缺点：进程间共享信息复杂，进程间通信（Inter-Process Communication，IPC）通常需要通过系统调用进行；fork 带来额外的开销。

基于I/O多路复用的并发编程

I/O多路复用允许进程在等待多个I/O事件时，不需要阻塞，进而提高程序的效率。可以通过select 函数实现。

使用 <sys/select.h> 中的 select 函数，会一直阻塞直到 fdset 中的任何文件描述符准备好读，并返回已准备好的个数，同时修改 fdset 为 ready_set 。

注意：每次使用select都需要重置fdset，因为它在每次调用时会被修改。

优点：一个进程、一个地址空间，减少了进程控制开销；不同事件可以共享数据，方便调试。没有进程/线程控制开销；程序员更全面直接地介入控制。现代高性能服务器仍使用该方式。

缺点：编写较为繁琐，且不能充分利用多核处理器。

基于线程（Thread）的服务器

回忆进程所包含的内容：

（处理器中的）进程上下文（寄存器、条件码、栈指针、PC）

虚拟地址空间（code、data、stack）。

为了适应并发的需求，我们可以对其进行一些改变：使虚拟内存空间变为共用的；这样可以免去复制虚拟地址空间和调页的开销。此即线程（Thread）。一个进程可以创建多个线程，进程的虚拟地址空间包含不同线程的栈。

线程的独立性体现在，它包括独立的处理器上下文：寄存器、条件码、PC、栈指针，同时拥有独立的栈，进而拥有独立的局部变量；有自己的ID；有自己的逻辑控制流。但线程的栈与其他线程的栈处在同一虚拟地址空间中，不受保护，可以被其他线程访问。

线程的共享性体现在，同一进程的不同线程共享内存空间和内核代码，进而共享文件描述符表、堆、全局变量、共享库映射、代码段和数据段。

线程的运行时间存在交错时，称为线程的并发（concurrent）。

由于线程的上下文比进程小得多，线程的控制开销约为进程的一半。

线程的调度和切换由操作系统（线程调度器）负责。

优点：线程控制开销小于进程，线程间的通信更简单。

缺点：线程之间共享内存，容易发生意外的共享，带来不稳定因素。

Posix-Pthread编程

Posix线程库（Pthread）提供了多线程编程的基本接口，可以用来创建、管理线程。一些函数的用法如下：

线程有一个入口函数；线程被创建时，初始的PC指向该函数入口点。该函数必须符合特定格式，即参数和返回值为 void* 。

可结合线程（joinable thread）：可以被其他线程回收，必须显式回收。

分离线程（detached thread）：线程结束后由操作系统自动回收资源。

子线程使用 pthread_detach(pthread_self()) 将自己设为分离线程；或者主线程使用 pthread_detach(thread) 将子线程 thread 设为分离线程

以下是一个在C++中使用Pthread实现服务器的例子：

注意：我们不能假定线程被调度和执行的先后顺序，这点与进程类似。初始线程向子线程传参数时，参数类型为 void* 。若传递的是局部变量的地址（例如 (void*)(&cnt)），则不同线程容易产生竞争。想象这样一个场景：主线程在for循环中，每次循环均创建一个线程，并把循环变量 i 的地址作为参数传递给子线程。线程0应该从地址中读出参数0 。然而存在一种可能，线程0被创建后，线程调度器继续让主线程执行，循环变量 i 变为1 。此时如果线程0被调度执行，它将从地址中取出1，而非我们期望的0 。

正确的传参方法如上，应该先 malloc 或 new 一个独立的地址空间，放入数据，再把其地址传给子线程；子线程提取数据后再执行 free 或 delete 。

注意，某个线程调用 exit() 函数，将会终止本进程，从而终止进程中的所有线程。

基于线程的优缺点

优点：线程之间的数据传递方便，开销较小。

缺点：线程共享资源带来的同步问题难以解决，调试难度较大。容易发生“无意共享”（unintentional sharing）。线程各自的栈不受保护、隔离性差，带来风险。

硬件层面上，可以在CPU的单个核心内堆叠多套PC、寄存器等，从而实现单核多线程。

线程的同步 Synchronization

为了解决线程间的竞争条件和不一致性问题，可以使用线程同步机制。常见的同步机制包括互斥锁、条件变量、信号量等。

想象这样一个情形：两个子线程都运行 cnt++，其中 cnt 是全局变量。但编译后的汇编语言有三条指令：

如果线程A的 addq 执行完毕后，操作系统进行线程切换，另一个线程B读入了未被线程A写入的 cnt，会导致两个线程最后都向 cnt 写入了相同的值，cnt实际上只加了1 。

可以用一个图来表示两个线程的调度关系，横轴和纵轴分别是线程的指令，操作系统的内存调度器的每次调度，均可以表示为向右走或者向上走。

对于如 cnt++ 这样的不可拆分的多条指令，会构成一个不可进入的矩形“危险区”。线程调度进入该区域会产生意料之外的行为。因此线程间需要同步。

信号量的基本操作

信号量（Semaphore）是一种用于控制多个线程对共享资源访问的同步机制。它是一个整数变量，用于表示可用资源的数量。信号量像是一种“权限”或“令牌”，只允许一定数量的线程对某资源或变量进行读写。信号量可以用来解决以下问题：

限制同时访问某个资源的线程数量。

实现线程之间的同步。

信号量的操作包括初始化、P操作、V操作等，能够有效地解决线程同步问题。Posix标准提供了以下C函数用于操作信号量：

P 操作：检查信号量的值。如果信号量的值为 0，则将当前线程加入等待队列，挂起。如果信号量的值大于 0，则将其减 1，继续执行后面的代码。

V 操作：将信号量的值加 1。从等待队列中唤醒一个线程。

对于二元信号量，P/V操作也称为“锁”和“解锁”操作，pthread 库提供了对 pthread_mutex_t 互斥锁的 pthread_mutex_init/lock/unlock 操作。

操作系统确保信号量的P和V操作是原子化的，可以有效避免竞态条件。

不能假定每次V操作会唤醒等待队列中的哪一个线程。

每次进行信号量操作需要陷入到内核态，会增加时间开销。

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

“生产者-消费者”模型中，生产者负责生产数据，消费者负责处理数据。例如面包店中，面包师可视为生产者线程，买面包的顾客可视为消费者线程。生产和消费的过程通常是异步的，因此需要一个缓冲区（例如面包店中的货架）来进行耦合。生产者生产时，将数据放入缓冲区；消费者消费时，将缓冲区中的数据移除。

注意到缓冲区被多个线程所共享，并且线程对缓冲区的访问必须是互斥的。需要通过信号量操作来保证访问的互斥性。同时，生产者在缓冲区满时、消费者在缓冲区空时，均需要进行等待/挂起操作，这也需要信号量的调度。

以下是一个使用信号量解决生产者-消费者问题的代码示例：

注意，其中P操作的顺序不能调换。

sem_wait(&empty) 和 sem_wait(&mutex) 的顺序不能调换，否则可能会导致死锁。

sem_wait(&empty)：等待空闲缓冲区。如果缓冲区已满，生产者会阻塞，直到消费者释放一个缓冲区。

sem_wait(&mutex)：等待进入临界区，保护对共享资源（buffer、in、out）的访问。

如果调换顺序，生产者会先尝试获取互斥锁（mutex），然后再检查是否有空闲缓冲区（empty）。假设这样一种情形：

缓冲区已满，empty 的值为 0。

生产者先获取 mutex，进入临界区。

生产者尝试获取 empty，但缓冲区已满，生产者阻塞。

消费者需要获取 mutex 才能消费数据，但 mutex 已被生产者持有，消费者阻塞。

生产者和消费者互相等待，导致死锁。

在正确的顺序下，应该产生以下情形：

生产者先检查是否有空闲缓冲区（sem_wait(&empty)），如果没有则阻塞，不会进入临界区。

只有在有空闲缓冲区时，生产者才会尝试获取 mutex，进入临界区操作缓冲区。

这样，消费者仍然可以获取 mutex 并消费数据，释放缓冲区，避免死锁。

使用信号量实现读者-写者问题

读者-写者问题中，读者只允许读数据；写者允许读写数据。允许任意多数量的读者访问数据；但同一时间只能有一个写者访问数据。在生活中，订票系统就是一个典型的读者-写者问题：查询余票即进行读者操作，购票即进行写者操作。

根据读者和写者的权限差异，该问题又分为两类：

第一类读者-写者（读者优先）

读者请求不能被挂起，除非已经有写者正在访问

等待访问的读者拥有比写者更高的优先级

写者只有在没有读者访问、没有写者等待时才能访问

如果读者源源不断，写者将面临饥饿

第二类读者-写者（写者优先）

一旦写者准备好写，尽可能快地完成写操作

等待访问的写者拥有比读者更高的优先级

写者进入等待区，通过P(&readTry) 阻止后续读者进入访问；待所有读者完成访问后，写者内部通过 wrt 协调写入的先后

读者只有在等待区没有写者时才能进入访问数据

总结

竞争（Race）：尽量避免变量被不同线程共享；对于共享变量加上互斥锁

死锁（Deadlock）：当不同线程使用PV操作的顺序不当，就陷入死锁；在线程调度图中表现为多个互斥锁的屏蔽区域的并集，产生了一些死锁区域：调度一旦进入该区域，既无法向上走也无法向右走。

可能产生死锁的充分必要条件：线程之间的等待关系构成一个环；也即加锁顺序构不成一个偏序（存在a<b && b<a）
解决方法：不同线程以相同的顺序加锁并以相反顺序解锁

线程安全（Thread safety）：一个线程安全的函数应具有以下性质：

保护共享变量：加互斥锁。
多个调用之间不共享状态：例如 rand() 函数共享随机种子，当多线程交替使用rand()种子时，获取的随机数的子列的随机质量会下降；应使用多线程版本，使用指针传递随机数种子。
避免传递指向静态变量的指针，例如 itoa() 返回一个 static char* 指针；应重写线程安全版本；或调用函数前对静态变量加锁。
使用其他线程安全的函数。调用线程不安全函数的函数不一定是线程不安全的 （一些封装函数）。

可重入函数：一部分线程安全函数，可以被多次重进入。具有以下性质：

不依赖静态或全局数据，只使用局部变量
所有参数都是传值而非传指针

满足以上两点的函数是显式可重入的；若谨慎地传递指针，则是隐式可重入的。

若函数中使用PV互斥锁，则不可重入（例如printf函数）

所有的C标准库函数均是线程安全的；大部分Unix系统调用也是线程安全的

不应在signal handler中使用异步不安全函数，例如printf 。

.lazy-image-placeholder{ background: linear-gradient(90deg,#0001 33%,#0005 50%,#0001 66%) #f2f2f2; background-size:300% 100%; animation: l1 1s infinite linear; } @keyframes l1 { 0% {background-position: right} } ICS12 并发编程