1. 多线程程序中的共享变量

一组并发线程运行在一个进程的上下文中。每个线程都有自己独立的线程上下文,包括线程 ID、栈、
栈指针、程序计数器、条件码和通用目的寄存器值。每个线程和其他线程共享进程上下文的剩余部分,
包括用户虚拟地址空间,它是由只读文本(代码)、读/写数据、堆以及共享库代码和
数据区组成的。线程也共享相同的打开文件的集合。

寄存器是从不共享的,虚拟内存总是共享的。

多线程的 C 程序中的变量根据它们的存储类型被影射到虚拟内存:

  • 全局变量:定义在函数之外的变量,虚拟内存中只有一个实例,任何线程都能引用。
  • 本地自动变量:定义在函数内但没有 static 属性的变量,每个线程都有自己的实例。
  • 本地静态变量:定义在函数内并有 static 属性的变量,和全部变量一样。

多线程实现计数器,每个线程对共享变量操作,容易出现同步错误。

进度图将 n 个并发线程的执行,模型化为一条 n 维笛卡尔空间中的轨迹线。每条轴 k 对应
线程 k 的进度,每个点代表线程 k 已经完成指令的状态。

每个线程在执行临界区(critical section)的指令时,拥有对共享变量的互斥(mutual exclusion)访问。
在进度图中,两个临界区的交集形成的状态空间称为不安全区,绕开不安全区的轨迹线叫做安全轨迹线。

任何安全轨迹线都会正确地更新共享变量,为了保证线程化程序的正确执行,我们必须以某种方式同步线程。

安全和不安全轨迹线

2. 使用信号量同步线程

一种经典的解决线程同步问题的方法:信号量(semephore)。它是具有非负整数的全局变量,只能由两种特殊的操作处理,成为 P 和 V。P 和 V 来源于荷兰语,分别表示测试和增加。

P 中的测试和减一操作是不可分割的,V 中的加一操作也是不可分割的。当多个线程等待同一个信号量时,
无法预测 V 操作也重启哪个线程。

使用信号量可以确保对共享变量的互斥访问。基本思想是将每个共享变量与一个信号量 s (初始为 1)关联起来,
然后用 P(s) 和 V(s) 操作将相应的临界区包围起来。这种保护共享变量的信号量称为二元信号量,
以提供互斥为目的的二元信号量称为互斥锁。

除了提供互斥外,信号量的另一个重要作用是调度对共享资源的访问。比如生产者-消费者问题,读者-写者问题。

3. 使用线程提高并行性

所有程序的集合被划分为不相交的顺序程序集合和并发程序的结合,并行程序是一种运行在多个处理器上的并发程序。

来看一个用多线程对整数序列求和的问题,将序列划分为多个不相交的区域,给每个线程分配一个区域。

  • 第一种做法,将每个线程求得的和放入共享的全局变量中,用互斥锁保护这个变量。结果性能非常差,同步操作的代价太大。
  • 第二种做法,定义一个全局数组,每个对等线程把和累积在数组的不同位置。同时,使用局部变量消除不必要的内存引用。最终性能提升明显。

同步开销巨大,要尽可能避免。如果无可避免,必须要用尽可能多的有用计算弥补这个开销。

随着线程数量的增加,程序运行时间不会一直减少,由于线程上下文切换的开销。

4. 其他并发问题

可重入(reentrant)函数:当被多个线程调用时,不会引用任何共享数据。比不可重入的线程安全的函数高效一些,因为它不需要同步操作。

避免死锁(deadlock):给定所有互斥操作的一个全序,如果每个线程都以一种顺序获得互斥锁并以相反的顺序
释放,那么这个程序就是无死锁的。