chapter 4：并发编程

学习笔记：并发编程

4. 并发编程

概要：
- 介绍了并发编程的概念，对比了顺序算法与并行算法，以及并行性与并发性之间的区别。
- 解释了线程的原理及其优势，覆盖了在Pthreads中的线程操作。
- 展示了通过示例实现线程的并发编程，如矩阵计算、快速排序以及通过并发线程解决线性方程组的问题。
- 解释了死锁问题以及如何预防在并发程序中的死锁。
- 涵盖了信号量的内容，并展示了其相对于条件变量的优势。
- 阐述了Linux中支持线程的独特方式。

4.1 并行计算介绍

早期情况：
- 计算机通常只有一个处理元素，即处理器或中央处理单元（CPU）。
- 由于硬件限制，传统上计算机程序是为串行计算而编写的。
并行计算的发展：
- 随着多核处理器的出现，大多数操作系统（如Linux）支持对称多处理（SMP），并行计算已经成为普通程序员的现实。
未来方向：
- 计算的未来显然是朝着并行计算的方向发展。
- 为了让计算机科学和计算机工程的学生能够更早地接触到并行计算，有必要在早期阶段引入并发编程的基本概念和技术。

4.1.1 顺序算法 vs 并行算法

区别：
- 顺序算法是串行执行的，而并行算法可以并行执行多个任务。
- 并行算法采用cobegin-coend块来指定并行算法的不同任务，实现多个任务并行执行。

4.1.2 并行性 vs 并发性

概念对比：
- 并行算法只标识可以并行执行的任务，但不指定如何将任务映射到处理元素。
- 在单CPU系统中，不同的任务只能以并发方式执行，即逻辑上的并行。
- 在单CPU系统中，通过多任务处理实现并发性，本章末尾的编程项目将重新解释和演示多任务处理的原理和技术。

4.2 线程

4.2.1 线程原理

操作系统模型：
- 进程中的线程是相对独立的执行单元，处于相同的地址空间。
比喻：
- 进程像是一个房子，而线程就像是在同一个房子里生活的人，各自独立活动但共享一些共同资源。
Pthreads支持：
- 几乎所有操作系统支持Pthreads，这是IEEE POSIX 1003.1c（POSIX 1995）的线程标准。

4.2.2 线程的优势

优势：
- 线程创建和切换更快，因为线程共享相同的地址空间，无需额外的内存和页面表。
- 线程更具响应性，一个线程被阻塞时，其他线程仍可继续执行。
- 更适合并行计算，因为线程可以更自然地共享数据，不像进程需要进行进程间通信（IPC）来交换数据。

4.2.3 线程的劣势

劣势：
- 因为线程共享地址空间，需要用户显式同步。
- 许多库函数可能不支持线程安全，需要调整以适应线程环境。
- 在单CPU系统中，线程的开销可能导致运行速度比串行程序更慢。

4.3 线程操作

执行位置：
- 线程可以在内核模式或用户模式下执行，拥有各自的执行栈。
Pthreads支持：
- 几乎所有操作系统都支持POSIX Pthreads，提供了一套标准的API用于支持线程编程。

参考书目：Buttlar et al. 1996, Pthreads 2017, Goldt et al 1995, IBM, Love 2005, Linux Man Page Project 2017.

4.4 线程管理函数

Pthreads库API：
- 提供以下线程管理API：
  - pthread_create: 创建线程
  - pthread_exit: 终止线程
  - pthread_cancel: 取消线程
  - pthread_attr_init: 初始化线程属性
  - pthread_attr_destroy: 销毁线程属性

4.4.1 创建线程

pthread_create()函数创建线程，其参数包括：
- pthread_create(pthread_t *pthread_id, pthread_attr_t *attr, void *(*func)(void *), void *arg)
attr参数是最复杂的，步骤如下：
1. 定义pthread_attr_t attr线程属性变量。
2. 通过pthread_attr_init(&attr)初始化属性。
3. 设置属性变量，使用在pthread_create()调用中。
4. 如果需要，通过pthread_attr_destroy(&attr)释放资源。
示例展示了如何创建一个非可连接线程。

4.4.2 线程ID

线程ID是一个不透明的数据类型，应避免直接比较。可以使用pthread_equal()函数进行比较。

4.4.3 线程终止

线程在函数结束时终止，也可以通过pthread_exit()显式终止。退出状态为0表示正常终止，非零值表示异常终止。

4.4.4 线程加入

一个线程可以通过pthread_join()等待另一个线程的终止，获取其退出状态。

4.5 线程示例程序

4.5.1 矩阵求和

示例展示了如何通过多线程计算N × N矩阵中所有元素的总和。
主线程创建N个工作线程，每个线程计算一个独立行的部分和，存储在全局数组中。
最后，主线程将所有部分和相加，得到总和。

4.5.2 快速排序

通过并发线程实现了一个并行快速排序程序。
主线程调用qsort()函数，其中使用了快速排序算法。
在算法中，创建子线程对两个分区进行递归排序，然后等待子线程结束。

4.6 线程同步

线程共享的问题

线程在同一个进程的地址空间中执行，共享所有全局变量和数据结构。
当多个线程尝试修改相同的共享变量或数据结构时，如果结果依赖于线程的执行顺序，则称为“竞争条件”。
竞争条件在并发程序中不应存在，否则结果可能不一致。

线程同步和互斥锁

同步是用于确保共享数据对象的完整性和并发执行实体协调的机制和规则。
为了防止竞争条件并支持线程协作，线程需要同步。
在Pthreads中，互斥锁是最简单的同步工具，用于实现互斥。

4.6.1 互斥锁（Mutex Locks）

互斥锁是一种锁，允许执行实体仅在拥有锁的情况下继续执行。
在Pthreads中，互斥锁被称为互斥量（mutex），用pthread_mutex_t类型声明。
互斥量需要初始化，可以通过静态或动态方式进行。
- 静态方式使用 pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER; 进行初始化。
- 动态方式使用 pthread_mutex_init(&m, NULL); 进行初始化。
互斥锁使用函数 pthread_mutex_lock、pthread_mutex_unlock、pthread_mutex_trylock 和 pthread_mutex_destroy。
互斥锁用于保护共享数据对象，典型使用是在关键区域（Critical Region）中对共享数据进行访问。

4.6.2 死锁预防

死锁是一种情况，其中多个执行实体相互等待，导致无法继续。
避免死锁是关于并发程序处理可能死锁的唯一实际方式。方法包括死锁预防、死锁避免、死锁检测和恢复等。
死锁预防试图在设计并行算法时防止死锁，例如通过互斥量的顺序化和条件锁的使用。

4.6.3 条件变量（Condition Variables）

条件变量用于线程协作，与互斥锁一起使用。
在Pthreads中，条件变量使用 pthread_cond_t 类型声明，需要初始化。
条件变量与互斥锁结合使用，包括 pthread_cond_wait、pthread_cond_signal 和 pthread_cond_broadcast 等函数。

4.6.4 生产者-消费者问题

实现生产者-消费者问题的简化版本，使用线程和条件变量。
生产者和消费者共享有限数量的缓冲区，条件变量用于等待空缓冲区或满缓冲区。

4.6.5 信号量（Semaphores）

信号量是用于进程同步的通用机制。Pthreads中的信号量函数包括 sem_init、sem_wait 和 sem_post。
与条件变量相比，信号量具有计数器，并在关键区域内进行操作，适用于更广泛的场景。

4.6.6 屏障（Barriers）

屏障允许一组线程在同步点等待，然后一起继续执行。通过 pthread_barrier_init 和 pthread_barrier_wait 来实现。

4.6.7 通过并发线程解线性方程组

使用线程来解线性方程组，通过高斯消元算法并利用屏障和线程等待操作。

4.6.8 Linux中的线程

在Linux中，线程和进程没有区别，都是通过 clone() 系统调用创建。
clone() 可以创建共享资源的子进程，包括内存、文件系统、打开文件等。

并发编程知识总结

本章介绍了并发编程的概念。首先解释了并行计算的重要性，对比了顺序算法和并行算法，以及并行与并发的区别。接着阐述了线程的原理，强调了线程相对于进程的优势。内容涵盖了Pthreads中线程的操作方法，如线程的管理函数、互斥锁、线程等待、条件变量和屏障。通过详细示例演示了如何使用线程进行并发编程，包括矩阵计算、快速排序以及使用并发线程解决线性方程组。章节也解释了死锁问题，提供了避免并发程序中死锁的方法。讨论了信号量的特点，并展示了它们相对于条件变量的优势。另外，还介绍了Linux支持线程的独特方式。最后的编程项目是实现用户级线程，为读者提供了基础系统，支持并发任务的动态创建、执行和终止，类似线程在同一进程的地址空间中执行。编程项目要求读者实现线程的连接、互斥锁和信号量，以展示它们在并发编程中的应用。

问题

修改示例程序C4.1
- 通过并发线程找到N×N矩阵的最大元素值。
在示例程序C4.2的qsort()函数中
- 使用未排序间隔的最左侧元素作为枢纽点。比较两种情况下所需的排序步骤数。
修改示例程序C4.4
- 创建多个生产者和消费者线程。
使用信号量实现生产者-消费者问题
- 参考第4.5节的示例4.5。
在示例程序C4.5中
- 将工作线程的数量N修改为NTHREADS，其中NTHREADS <= N。例如，当N=8时，NTHREADS可以是2、4或任何小于等于N的数字。
修改示例程序C4.1
- 在MT系统中使用并发任务计算矩阵中所有元素的和。结果应与第4.1节中的示例相同。
实现texit()和join()
- 在用户级线程MT系统中，确保每个任务都由其他任务连接。当系统结束时，不应该留下僵尸任务。

苏格拉底挑战

点击查看问答过程

并发编程原子性理解

Shared Chat•

Default (GPT-3.5)

并发编程原子性理解

October 28, 2023

我在学习并发编程知识点，请你以苏格拉底的方式对我进行提问，一次一个问题

当你思考并发编程时，你是如何理解“原子性”？

“原子性”指的是一个操作要么被执行完全，要么不被执行（即具有不可分割性），这样可以保证多个并发操作不会互相干扰导致不可预期的结果。在并发编程中，原子性的概念强调了保证多个线程对共享变量的操作不会出现相互干扰的情况。例如，对于一个变量，如果多个线程都想要改变它的值，保证这个操作是原子性的，则只有一个线程可以完成这个操作，其他线程必须等待该操作完成并释放该变量后，才能进行自己的操作。常见的实现方式是使用锁或CAS等机制来保证原子性。这样可以避免并发操作带来的不可预期的结果，确保程序正确性和稳定性。

在你学习并发编程的过程中，你是如何区分“并行性”和“并发性”这两个概念？

广义上来说，“并发性”和“并行性”都表达了一种多任务处理的能力，但它们的含义略有不同。

在并发编程中，“并发性”指的是在一个时间段内，同时运行多个任务（至少有两个）的能力，即通过时间片轮转等机制，使得多个任务交替执行，从而实现多个任务同时进行的假象。

而“并行性”则是指在同一时间内，同时执行多个任务的能力，即通过多个线程或多个处理器并行的执行多个任务。

简单来说，“并发性”是一种逻辑上的概念，它通过时间切片的方式来让多个任务共享CPU时间；而“并行性”则是物理上的概念，它通过多个CPU或多个线程来并行处理多个任务。

在实际的并发编程中，我们需要考虑如何在多个并发任务中协调各自的执行，以达到最优的性能和最佳的用户体验。因此，对“并发性”和“并行性”的区分是非常重要的。

你在研究并发编程时，你是如何看待死锁（Deadlock）以及如何预防或解决这种并发编程中常见的问题？

死锁是并发编程中常见的问题，指的是两个或多个进程（线程）持有相互需要的资源，并且由于资源互斥的特性导致它们相互等待，从而无法继续执行下去。

在研究并发编程时，我认为死锁是需要引起注意的一个重要问题。以下是一些预防和解决死锁的常见策略：

避免使用多个锁：当多个锁被用于资源访问时，有可能产生死锁。可以尝试使用更细粒度的锁，或者通过重构代码来减少锁的数量。
保持锁的顺序一致性：当多个线程需要获取多个锁时，保持每个线程获取锁的顺序一致可以减少死锁的可能性。
设置超时时间：可以在获取锁的过程中设置超时，并在超时后释放已经获取的锁，避免长时间等待导致死锁。
死锁检测和恢复：可以使用死锁检测算法，定期检查系统中是否存在死锁，并采取相应的措施解决。
使用资源分配图：通过建立资源分配图，可以可视化地表示资源之间的依赖关系，进而预测和避免潜在的死锁情况。
避免循环等待：当多个线程需要获取多个资源时，可以使用资源的有序分配来避免循环等待的情况。

以上只是一些常见的策略，具体的应用将取决于并发编程环境和具体的应用场景。在实际应用中，综合考虑性能、可维护性和可扩展性等因素，并采取合适的策略来预防和解决死锁问题是非常重要的。

在并发编程中，你是如何理解并发安全（Concurrency Safety），以及你是如何保证数据结构或代码在多线程环境下的并发安全性？

并发安全（Concurrency Safety）指的是在多线程环境下，某个对象或者变量可以被多个线程安全地访问和修改，且程序不会出现不可预期的结果。

保证数据结构或代码在多线程环境下的并发安全性通常有以下几个策略：

加锁：使用锁来控制对变量或对象的访问，在访问时获取锁，在完成访问后释放锁，以保证同一时间只有一个线程可以访问该变量或对象。但加锁会造成性能损失，同时也可能引入死锁等问题，需要谨慎使用。
并发容器：Java提供了一些并发容器来替代同步容器，如ConcurrentHashMap、ConcurrentLinkedQueue等，这些容器可以在并发环境下进行操作，不需要显式的加锁，从而提高程序性能。
线程本地存储：线程本地存储是指对每个线程维护一份独立的变量副本，可以避免竞态条件的出现，提高并发性。
原子变量：Java提供了一些原子类型，如AtomicInteger、AtomicLong等，这些类型可以保证多线程对变量进行操作时的原子性，从而避免竞态条件的出现。
函数式编程：函数式编程的一个特点就是不会改变数据的状态，而是通过创建新的数据来实现计算。这样，在多线程环境下，不会存在对同一个数据状态进行修改的情况，从而避免竞态条件的发生。
无锁算法：无锁算法是指不使用锁来保证并发安全，而是通过其他方式来实现。通常采用CAS（Compare And Swap）等方式来实现，但也会带来一定的复杂性。

以上都是一些常见的策略，针对不同的需求和场景，使用合适的策略避免竞态条件和数据不一致是非常重要的。同时，在并发编程中，要避免常见的并发问题，如死锁、活锁、饥饿等，确保程序的正确性和可靠性。

在学习并发编程时，你是如何理解并发中的“竞态条件”（Race Condition）以及你是如何通过编程技巧或工具来避免或减少这种情况的发生？

竞态条件（Race Condition）指的是在多个线程并发访问同一资源时，由于访问顺序的不确定性，导致出现不可预期的行为。通常会导致数据不一致、程序崩溃等问题。

在学习并发编程时，我认为避免竞态条件的发生是非常重要的，以下是一些常见的编程技巧或工具：

同步机制：使用同步机制来保证多个线程对同一个资源的访问的互斥性，如synchronized、ReentrantLock等，从而避免多个线程同时访问同一个资源的情况。
原子操作：使用原子操作来进行并发控制，Java提供了一些原子类型，如AtomicInteger、AtomicReference等，这些类型可以保证操作的原子性，从而避免竞态条件的出现。
线程本地存储：将要访问的数据存储在线程本地，避免多个线程同时访问同一个数据的情况。
缓存一致性协议（Cache Coherence Protocol）：缓存一致性协议是指多个处理器之间分别有自己的缓存，但缓存之间的数据要保持一致性。这个协议通常由硬件控制实现，可以减少竞态条件的情形出现。
死锁检测：使用一些工具来检测死锁等并发问题，例如Java中的ThreadMXBean、VisualVM等。
避免共享状态：设计时尽可能减少共享状态的情况，避免多个线程同时修改同一个数据的情况。

这些编程技巧和工具可以帮助我们在多线程编程中避免竞态条件的发生。需要注意的是，不同的方法适用于不同的场景和需求，需要根据具体情况选择合适的方法。同时，在编程时还应该特别注意并发安全性，遵循一些规范和最佳实践，确保程序的正确性和可靠性。

在你的并发编程学习中，你是如何理解“线程安全性”以及如何评估、确保代码在多线程环境下的线程安全性？

线程安全性指的是在多线程环境下，某个代码或者数据结构可以被多个线程同时访问和修改，而不会出现不可预期的结果。

在我学习并发编程时，我对线程安全性的理解主要有以下几点：

原子性：线程安全的代码应该具有原子性，即对于某个操作，要么全部执行成功，要么全部不执行。可以通过使用原子类型（如AtomicInteger、AtomicLong）或者加锁来确保操作的原子性。
可见性：线程安全的代码应该保证数据的可见性，即当一个线程修改了某个共享变量的值，其他线程应该能够立即看到修改后的值。可以通过使用volatile关键字或者使用同步机制来确保数据的可见性。
有序性：线程安全的代码应该保证操作的有序性，即按照特定的顺序执行，不会出现重排序或乱序执行的情况。可以通过使用volatile关键字或者使用同步机制来确保操作的有序性。
无竞态条件：线程安全的代码应该避免竞态条件的发生，即多个线程对共享资源进行访问时不会出现不一致或破坏数据完整性的情况。可以使用同步机制、原子类型或者尽量避免共享状态来减少竞态条件的发生。

评估代码在多线程环境下的线程安全性可以有以下几个方面：

静态分析工具：使用静态分析工具来检测代码中是否存在潜在的并发问题，如FindBugs、Checkstyle等。
动态测试：通过编写多线程的测试用例，模拟实际的多线程环境，来测试代码的线程安全性。可以利用JUnit、TestNG等测试框架进行测试。
代码审查：结合代码审查的方式，多人一起审查代码，特别关注是否存在潜在的线程安全问题。
思考并发场景：考虑各种并发场景，分析代码在这些场景下的行为，是否会导致线程安全问题。

通过综合以上评估的结果，可以进一步改进代码，确保代码在多线程环境下的线程安全性。此外，在并发编程中，还应遵循一些通用的规范和最佳实践，如避免使用共享数据、不可变性、封装、可重入性等，以提高线程安全性。

在学习并发编程时，你是如何理解和处理“ABA 问题”以及如何利用CAS（Compare-And-Swap）来解决这类问题？

ABA问题指的是在多线程环境下，由于线程的交替执行导致的并发问题，即一个值A先被线程1读取，然后被线程2修改为B，最后又被线程1修改回了A，但此时线程1并不知道A已经被修改过了，而继续执行修改操作，从而导致问题的发生。

在学习并发编程时，我认为解决ABA问题的一种常见方法是使用CAS（Compare-And-Swap）原子指令，其大体思路如下：

CAS是一种原子指令，可以确保某个变量在并发情况下的原子性操作，它包含三个参数：变量的内存地址V、期望的值A和新的值B。
假设多个线程要对某个变量进行修改，首先使用CAS指令读取该变量的当前值C，然后判断C是否等于期望的值A，如果是则将变量的值修改为新的值B。
如果当前的值C不等于期望值A，说明该变量在并发环境下被其他线程修改过，此时CAS指令不会执行任何操作，而是重新读取变量的当前值C，继续进行步骤2。
如果多个线程同时执行CAS指令，但只有一个线程能够成功修改变量的值，其它线程会不断地尝试修改，直到成功为止。

通过使用CAS指令，可以确保变量在并发环境下的原子性操作和线程安全性。对于ABA问题，我们可以利用CAS指令的特性，将期望值从A改为一个版本号，每次修改值时将版本号加1，这样即使值修改回了A也不会被误认为是没有变化的值。

除了使用CAS指令，还有一些其他的方法可以避免ABA问题的出现，如使用锁、使用读写锁、使用能够保证顺序的细粒度锁等。需要根据具体的业务需求和场景特点来选择合适的方法。

在你的学习中，你是如何理解并处理“线程间通信”以及你是如何选择合适的机制来实现线程间的协作与通信？

线程间通信指的是在多线程环境下，不同的线程之间通过某种机制进行信息的传递和协作。

在我的学习中，我理解并处理线程间通信主要有以下几点：

共享变量：使用共享变量是一种简单的线程间通信的方式。多个线程可以通过读写共享变量来实现信息的传递。但是在使用共享变量时，需要注意线程安全性问题，并采用适当的同步机制（如锁、volatile关键字等）来保证数据的一致性和可见性。
管程（Monitor）：管程是一种高级的线程间通信机制，它提供了一种结构化的方式来协调线程的执行。在管程中，可以定义共享变量和相关的操作方法，并通过互斥锁来保证共享资源的访问顺序和一致性。线程可以通过等待、通知等操作来进行协作，并在合适的时机释放资源。
信号量（Semaphore）：信号量是一种经典的线程间通信的机制，它可以用来控制对共享资源的访问数量。线程可以通过获取信号量来获取资源的访问权限，而其他线程需要等待信号量的释放才能获取资源。信号量的数量和初始化值可以根据需求来调整。
线程间消息队列（Message Queue）：线程间消息队列是一种消息传递机制，其中一个线程（生产者）将消息放入队列，而另一个线程（消费者）从队列中取出消息并进行处理。通过消息队列可以实现不同线程之间的异步通信，提高系统的可扩展性和解耦性。

在选择合适的线程间通信机制时，需要根据具体的业务需求和场景来进行考虑：

如果只是简单的数据共享和传递，可以使用共享变量和适当的同步机制来实现。
如果需要实现复杂的线程协作和资源访问控制，可以选择管程或信号量来管理资源的访问顺序和一致性。
如果需要实现异步的线程间通信，可以选择使用消息队列来进行消息传递。

需要根据具体情况综合考虑各种因素，如性能、可扩展性、代码复杂性、易用性等来选择合适的线程间通信机制。

在并发编程中，你是如何理解“上下文切换”以及它如何影响系统的性能？你在编写多线程应用程序时是如何尽量减少上下文切换的次数？

线程间通信指的是在多线程环境下，不同的线程之间通过某种机制进行信息的传递和协作。

在我的学习中，我理解并处理线程间通信主要有以下几点：

共享变量：使用共享变量是一种简单的线程间通信的方式。多个线程可以通过读写共享变量来实现信息的传递。但是在使用共享变量时，需要注意线程安全性问题，并采用适当的同步机制（如锁、volatile关键字等）来保证数据的一致性和可见性。
管程（Monitor）：管程是一种高级的线程间通信机制，它提供了一种结构化的方式来协调线程的执行。在管程中，可以定义共享变量和相关的操作方法，并通过互斥锁来保证共享资源的访问顺序和一致性。线程可以通过等待、通知等操作来进行协作，并在合适的时机释放资源。
信号量（Semaphore）：信号量是一种经典的线程间通信的机制，它可以用来控制对共享资源的访问数量。线程可以通过获取信号量来获取资源的访问权限，而其他线程需要等待信号量的释放才能获取资源。信号量的数量和初始化值可以根据需求来调整。
线程间消息队列（Message Queue）：线程间消息队列是一种消息传递机制，其中一个线程（生产者）将消息放入队列，而另一个线程（消费者）从队列中取出消息并进行处理。通过消息队列可以实现不同线程之间的异步通信，提高系统的可扩展性和解耦性。

在选择合适的线程间通信机制时，需要根据具体的业务需求和场景来进行考虑：