Maple's Story

CSAPP 学习笔记：并发编程

操作系统 学习笔记 并发编程
字数统计: 4.7k阅读时长: 16 min
2020/05/02 Share

概述

如果逻辑控制流在时间上重叠，那么它们就是并发的（concurrent).

内核级并发：

  • 操作系统用来运行多个应用程序的机制

并发不仅仅局限于内核，应用级并发也是很有用的：

  • 访问慢速I/O设备
  • 与人交互
  • 通过推迟工作以降低延迟
  • 服务多个网络客户端
  • 在多核机器上进行并行计算

使用应用级并发的应用程序叫做并发程序（concurrent program）。现代操作系统提供了三种基本的构造并发程序的方法：

  • 进程： 每个逻辑控制流都是一个进程，由内核来调度和维护。因为进程有独立的虚拟地址空间，想要和其他流通信，控制流必须使用某种显式的进程间通信（interprocess communication，IPC）机制。
  • I/O 多路复用： 应用程序在一个进程的上下文中显式地调用它们自己的逻辑流。逻辑流被模型化为状态机，数据到达文件描述符后，主程序显式地从一个状态转换为另一个状态。因为程序是一个单独的进程，所以所有的流都共享同一个地址空间。
  • 线程： 线程是运行在一个单一进程上下文中的逻辑流，由内核进行调度。你可以把线程看成是其他两种方式的混合体，像进程流一样由内核进行调度，而像 I/O 多路复用流一样共享同一个虚拟地址空间。

基于进程的并发编程

构造并发程序最简单的方法就是用进程，使用那些大家都很熟悉的函数，像 fork, exec 和 waitpid。

对于在父、子进程间共享状态信息，进程有一个非常清晰的模型：共享文件表，但是不共享用户地址空间。进程有独立的地址空间既是优点也是缺点。这样一来，一个进程不可能不小心覆盖另一个进程的虚拟存储器，这就消除了许多令人迷惑的错误。

另一方面，独立的地址空间使得进程共享状态信息变得更加困难。为了共享信息，它们必须使用显式的 IPC 机制。

基于进程的设计的另一个缺点是，它们往往比较慢，因为进程控制和 IPC 的开销很高。

Unix IPC 通常指所有允许进程和同一台主机上其他进程进行通信的技术。其中包括管道、先进先出（ FIFO )、系统 V 共享内存、系统 V 信号量。

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

I/O 多路复用可以用做并发事件驱动（event-driven）程序的基础，在事件驱动程序中，某些事件会导致流向前推进。一般的思路是将逻辑流模型化为状态机。不严格地说，一个状态机（state machine）就是一组状态（state）、输入事件（input event）和转移（transition），其中转移是将状态和输入事件映射到状态。通常把状态机画成有向图，其中节点表示状态，有向弧表示转移，而弧上的标号表示输入事件。

逻辑流状态机举例

假设要求编写一个 echo 服务器，它也能对用户从标准输入键入的交互命令做出响应。此时服务器必须响应两个互相独立的I/O事件：1）网络客户端发起的连接请求 2）用户在键盘上键入的命令 ，解决的办法是I/O多路复用技术。基本思想是使用select函数，要求内核挂起进程，只有在一个或多个 I/O 事件发生后，才将控制返回给应用程序。

可以使用 select 、 poll 和 epoll 来实现I/O复用。

I/O 多路复用技术的优点：

  • 比基于进程的设计给了程序员更多的对程序行为的控制。
  • 一个基于I/O多路复用的事件驱动服务器是运行在单一进程上下文中的，因此每个逻辑流都访问该进程的全部地址空间。这使得在流之间共享数据变得很容易。
  • 一个与作为单进程运行相关的优点是，你可以利用熟悉的调试工具，例如GDB来调试你的并发服务器，就像对顺序程序那样。
  • 事件驱动设计常常比基于进程的设计要高效很多，因为它们不需要进程上下文切换来调度新的流。

缺点：

  • 编码复杂。随着并发粒度的减小，复杂性还会上升。这里的粒度是指每个逻辑流每个时间片执行的指令数量。

  • 基于事件的设计的另一重大缺点是它们不能充分利用多核处理器。

基于线程的并发编程

线程（thread） 就是运行在进程上下文中的逻辑流。程序都是由每个进程中的至少一个线程组成的。线程由内核自动调度。每个线程都有它自己的线程上下文（thread context），包括一个唯一的整数线程 ID（Thread ID，TID）、栈、栈指针、程序计数器、通用目的寄存器和条件码。所有的运行在一个进程里的线程共享该进程的整个虚拟地址空间。

基于线程的逻辑流集合了基于进程和基于 I/O 多路复用的流的特性:

  • 同进程一样，线程由内核自动调度，并且内核通过一个整数ID来识别线程。
  • 同 I/O 多路复用的流一样，多个线程运行在同一进程的上下文中，共享虚拟地址空间的所有内容，包括代码、数据、堆、共享库和打开的文件。

线程执行模型

每个进程开始生命周期时都是单一线程，这个线程称为主线程（main thread）。在某一时刻，主线程创建一个对等线程（peer thread），从这个时间点开始，两个线程就并发地运行。

  • 线程的上下文切换要比进程的上下文切换快得多。
  • 线程不像进程那样，不是按照严格的父子层次来组织的。
  • 和一个进程相关的线程组成对等线程池。
  • 主线程与其他线程的区别仅在于它总是进程中第一个运行的线程。
  • 一个线程可以杀死任何对等线程，或等待任意对等线程终止，都能读写相同的共享数据。

Posix 线程

Posix 线程（Pthreads)是在C程序中处理线程的标准接口，在所有的Linux程序上都可用

  1. 创建线程：
1
2
3
4
5
6
7
#include<pthread.h>

// tid为返回的新创建线程ID, attr设置新线程默认熟悉，f为新线程运行程序，arg为f的参数
int pthread_create(pthread_t *tid, pthread_attr_t *attr, func *f, void *arg);

// 子线程通过其获取自己的线程ID
pthread_t pthread_self(void);
  1. 终止线程：
  • 顶层的线程例程返回时，线程隐式终止
  • 通过调用 pthread_exit 函数显式终止。如为主线程调用，则会等待所有对等线程终止，再终止主线程以及整个进程。
1
2
// thread_return 为线程例程的返回值
void pthread_exit(void *thread_return);
  • 某个对等线程调用 Linux 的 exit 函数，则该函数终止进程及所有相关线程。
  • 另一个对等线程以该线程 ID 作为参数调用pthread_cancel函数。
1
int pthread_cancel(pthread_t tid);
  1. 回收已终止线程资源
1
2
// 阻塞，直到线程 tid 终止， 回收其占有的所有内存资源
int pthread_join(pthread_t tid, void **thread_return);
  1. 分离线程

线程可以是可结合的（ joinable ） 或者是分离的（ detached )。一个可结合的线程能被其他线程回收、杀死，且被其他线程回收前，内存资源（例如栈）不会释放。反之，分离的线程不能被其他线程回收、杀死，内存资源在它终止时自动释放。

默认情况下，线程被创建为可结合的。为避免内存泄漏，可结合线程都需要被其他线程显性地回收，或通过pthread_detach函数分离。

1
2
// 线程以pthread_self()为参数来分离自己
int pthread_detach( pthread_t tid);

多线程程序中的共享变量

多个线程很容易共享相同的程序变量。然而，这种共享也是很棘手的。为了编写正确的线程化程序，我们必须对所谓的共享以及它是如何工作的有很清楚的了解。

为了理解变量是否是共享的，有一些基本的问题要解答：

  1. 线程的基础存储器模型是什么？
  2. 根据这个模型，变量实例是如何映射到存储器的？
  3. 最后，有多少线程引用这些实例？

一个变量是共享的，当且仅当多个线程引用这个变量的某个实例。

线程内存模型

线程独立的上下文包括：线程ID、栈、栈指针、程序计数器、条件码和通用寄存器。共享进程上下文的其它部分，包括代码段、数据段、堆、共享库代码、打开的文件集合等。

实际操作中无法访问其它线程的寄存器值，但是由于所有的线程栈都保存在虚拟地址空间的栈区域，如果某个线程以某种方式得到了指向其它线程栈的指针，则可以读写这个栈的任何部分。

变量映射到内存

多线程的 C 程序中的变量根据存储类型被映射到虚拟内存：

  • 全局变量： 定义在函数之外，只有一个实例， 任何线程都可以引用。
  • 本地自动变量： 定义在函数内，没有static的变量。每个线程栈都包含它自己的所有本地变量的实例。
  • 本地静态变量： 函数内部static变量。多个线程共享。

用信号量同步线程

线程共享变量的遍历，也引入了 同步错误 的可能性。

一种经典的解决同步不同执行线程问题的方法：基于一种叫做 信号量( semaphore) 的特殊类型变量的。信号量s是具有非负整数值的全局变量,只能由两种特殊的操作来处理,这两种操作称为P和V。

  • P(s): 如果s是非零的,那么P将s减1,并且立即返回。如如果s为零,那么就挂起进程, 直到s变为非零,并且该进程被一个V操作重启。在重启之后,P操作将s减1,并将控制 返回给调用者。
  • V(s): 操作将s加1。如果有任何进程阻塞在P操作等待s变成非零,那么V操作会重启 这些进程中的一个,然后该进程将s减1,完成它的P操作

P 和 V 的定义确保了一个运行程序绝不可能进入这样一种状态,也就是一个正确初始化了的信号量有一个负值。这个属性称为信号量不变性( semaphore invariant ),为控制并发程序的轨迹线而避免不安全区提供了强有力的工具。

Posix 标准定义了许多操作信号量的函数

1
2
3
4
5
6
7
8
9
#include <semaphore.h>

int sem_init(sem_t *sem, 0, unsigned int value);
int sem_wait(sem_t *s); /* P(s) */
int sem_post(sem_t *s); /* V(s) */

// 或者自行封装
void P(sem_t *s);
void V(sem_t *s);

利用信号量实现互斥

基本的思想是将每个共享变量(或者相关共享变量集合)与一个信号量 s (初始为1) 联系起来, 然后用P(s)和V(s)操作将相应的临界区包围起来。以这种方式来保护共享变量的信号量叫做二元信号量( binary semaphore)，因为它的值总是0或者1。

以提供互斥为目的的二元信号量也叫互斥锁（ mutex )。在互斥锁上执行 P 操作称为对互斥锁枷锁，执行 V 操作为对互斥锁解锁。

利用信号量调度共享资源

信号量的另一个重要的作用是调度对共享资源的访问。一个线程用信号量操作来通知另一个线程，程序状态中的某个条件已经为真了。两个经典的例子是生产者-消费者问题和读者-写者问题。

  1. 生产者-消费者问题

生产者和消费者线程共享有一个 n 个槽的有限缓冲区。生产者线程反复地生成新的项目（item），并把它们插入到缓冲区中。消费者线程不断地从缓冲区中取出这些项目，然后消费（使用）它们。

因为插入和取出项目都涉及更新共享变量，所以我们必须保证对缓冲区的访问是互斥的。此外，如果缓冲区是满的，那么生产者必须等待直到有一个槽位变为可用。与之相似，如果缓冲区是空的，那么消费者必须等待直到有一个项目变为可用。

生产者-消费者问题

  1. 读者-写者问题

读者-写者问题是互斥问题的一个概括。一组并发的线程要访问一个共享对象，例如一个主存中的数据结构，或者一个磁盘上的数据库。有些线程只读对象（读者），有些线程只修改对象（写者）。写者必须拥有对对象的独占的访问，而读者可以和无限多个其他的读者共享对象。一般来说，有无限多个并发的读者和写者。

读者-写者问题存在几种变种，分别基于读者和写者的优先级。

使用线程提高并行性

写顺序程序只有一条逻辑流。写并发程序有多条并发流。并行程序是一个运行在多个处理器上的并发程序。因此，并行程序的集合是并发程序集合的真子集。

顺序、并发和并行程序集合之间的关系

并行程序由于涉及到内存共享与数据同步，而同步开销极为巨大，需要尽量避免。对代码看上去一点小小的改动都可能对性能造成极大的影响。

其他并发问题

线程安全

当用线程编写程序时，必须小心地编写那些具有线程安全性（thread safety）属性的函数。一个函数被称为线程安全的（ thread-safe ), 当且仅当被多个并发线程反复地调用时，会一直产生正确的结果。

通常有四类线程不安全函数：

  1. 不保护共享变量的函数
  2. 保持跨越多个调用的状态的函数

一个伪随机数生成器是属于这一类。rand 函数是线程不安全的，因为当前调用的结果依赖于前次调用的中间结果。解决办法是重写它，使得它不再使用任何 static 数据。

  1. 返回指向静态变量的指针的函数
  2. 调用线程不安全函数的函数

可重入性

有一类重要的线程安全函数叫做可重入函数（reentrant function），其特点在于它们被多个线程调用时，不会引用任何共享数据。可重入函数通常要比不可重入的线程安全的函数高效一些，因为它们不需要同步操作。

三类函数之间的关系

大多数 Linux 函数，包括定义在标准 C 库中的函数（例如 malloc、free、realloc、printf 和 scanf）都是线程安全的，只有一小部分是例外。Linux 系统提供大多数线程不安全函数的可重入版本，且函数名字总是以_r后缀结尾的。

竞争

当一个程序的正确性依赖于一个线程要在另一个线程到达 y 点之前到达它的控制流中的 x 点时，就会发生竞争（race）。通常发生竞争是因为程序员假定线程将按照某种特殊的轨迹线穿过执行状态空间，而忘记了另一条准则规定：多线程的程序必须对任何可行的轨迹线都正确工作。

死锁

信号量引入了一种潜在的令人厌恶的运行时错误，叫做死锁（deadlock），它指的是一组线程被阻塞了，等待一个永远也不会为真的条件。

一个会死锁的程序的进度图

  • 程序员使用 P 和 V 操作顺序不当，使得每个线程都在等待其他线程执行一个根本不可能发生的 V 操作。
  • 死锁是一个相当困难的问题，因为它不重视可预测的。你可以运行一个程序 1000 次不出任何问题，但是下一次它就死锁了。最糟糕的是，错误常常是不可重复的，因为不同的执行有不同的轨迹线。

互斥锁加锁顺序规则：给定所有互斥操作一个全序，如果每个线程都是以一种顺序获得互斥锁并以相反的顺序释放，那么这个程序就是无死锁的。

例如：在每一个线程都是先对 s 加锁，再对 t 加锁。

一个无死锁程序的进度图

总结

一个并发程序由时间上重叠的一组逻辑流组成。本文共总结了三种不同构造并发程序的机制：进程、 I/O 多路复用和线程。

进程和线程都是由内核自动调度的。其中进程有各自独立的虚拟地址空间，所以要实现共享数据，必须有显式的 IPC 机制。 事件驱动程序创建自己的并发逻辑流，这些逻辑流被模型化为状态机，用 I/O 多路复用来显式地调度这些流。因为程序运行在单一进程中，所以流之间共享数据速度很快且很容易。线程是上述两者的混合，由内核自动调度，运行在单一进程的上下文中，可以快速方便地共享数据。

通过对信号量的 P 和 V 操作可以帮助解决对共享数据的并发访问问题。信号量既可以提供对共享数据的互斥访问，也可以提供对共享对象的资源访问调度。

并发还引入了线程安全、竞争、死锁等问题。

参考资料

《深入理解计算机系统》
CSAPP / CSE 351 学习笔记（并发编程）
深入理解计算机系统：并发编程

原文作者：枫逸

原文链接：https://www.pengchen.top/posts/41580/

发表日期：May 2nd 2020, 4:47:45 pm

更新日期：September 5th 2020, 1:44:05 am

版权声明：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. 概述
  2. 2. 基于进程的并发编程
  3. 3. 基于 I/O 多路复用的并发编程
  4. 4. 基于线程的并发编程
    1. 4.1. 线程执行模型
    2. 4.2. Posix 线程
  5. 5. 多线程程序中的共享变量
    1. 5.1. 线程内存模型
    2. 5.2. 变量映射到内存
  6. 6. 用信号量同步线程
    1. 6.1. 利用信号量实现互斥
    2. 6.2. 利用信号量调度共享资源
  7. 7. 使用线程提高并行性
  8. 8. 其他并发问题
    1. 8.1. 线程安全
    2. 8.2. 可重入性
    3. 8.3. 竞争
    4. 8.4. 死锁
  9. 9. 总结
  10. 10. 参考资料
Total : 15
2020
2019
操作系统 学习笔记 并发编程 Fall Detection Machine Learning Deep Learning C++ 剑指offer 算法笔记 计算机组成原理 MySQL 数据库 Redis 实习总结 运维 集群监控 GO语言 后台开发 转载笔记
学习笔记 机器学习 实习总结 转载笔记