深入理解计算机系统 第12章 笔记整理

这次回顾深入理解计算机系统第12章并发编程。

电子书地址：

http://eol.bnuz.edu.cn/meol/common/script/preview/download_preview.jsp?fileid=2169600&resid=242120&lid=28605

备注：图片和总结内容均来自于电子书。

第12章：并发编程

重要概念

• 如果逻辑控制流在时间上重叠，那么它们就是并发的，这种常见的现象称为并发。

• 现代操作系统提供了三种基本的构造并发程序的方法：

  • 进程；
  • I/O多路复用；
  • 线程；

• 主线程(main thread)，对等线程(peer thread)，两者的区别；

• 多线程程序中变量的种类：

  • 全局变量；
  • 本地自动变量；
  • 本地静态变量；

• 信号量相关：

  • 进度图（progress graph）
  • 临界区（critical section）
  • 互斥（mutual exclusion）
  • 不安全区（unsafe region）
  • 安全轨迹线（safe trajectory）
  • 不安全轨迹线（unsafe trajectory）
  • 信号量
  • 二元信号量（binary semaphore）
  • 互斥锁（mutex）
  • 对互斥锁加锁
  • 禁止区（forbidden region）

• 生产者-消费者问题和读者-写问题；

• 顺序，并发和并行程序之间的关系；

• 并行程序相关概念：

  • 强扩展（strong scaling）
  • 弱扩展（weak scaling）
  • 加速比
  • 绝对加速比（absolute speedup）
  • 相对加速比（relative speedup）
  • 效率（efficiency）

• 并发相关问题：

  • 线程安全的（thread-safe）和线程不安全的（thread-unsafe）
  • 四个（不相交的）线程不安全函数类
  • 加锁-复制（lock-and-copy）
  • 可重入函数（reentrant function）：当它们被多个线程调用时，不会引用任何共享数据。
    • 可重入，显式可重入，隐式可重入
  • 竞争
  • 死锁
    • 死锁状态
    • 死锁区域

简介

• 如果逻辑控制流在时间上重叠，那么它们就是并发的。这种常见的现象称为并发，出现在计算机系统的许多不同层面上：
  • 内核；
  • 信号处理；
  • 应用级；
• 应用级并发有用的情形：
  • 访问慢速I/O设备；
  • 与人交互；
  • 通过推迟工作以降低延迟；
  • 服务多个网络客户端；
  • 在多核机器上进行并行计算；
• 使用应用级并发的应用程序称为并发程序，现代操作系统提供了三种基本的构造并发程序的方法：
  • 进程；
  • I/O多路复用；
  • 线程；

后续的讨论都以11章的echo服务器为例。

基于进程的并发编程

说明

• 假设我们有两个客户端和一个服务器，服务器正在监听一个监听描述符（比如指述符3）上的连接请求；
• 现在假设服务器接受了客户端1的连接请求，并返回一个已连接描述符（比如指述符4），如图 12-1 所示；
• 在接受连接请求之后，服务器派生一个子进程，这个子进程获得服务器描述符表的完整副本；
• 子进程关闭它的副本中的监听描述符3，而父进程关闭它的已连接描述符4的副本，因为不再需要这些描述符了；
• 这就得到了图12-2中的状态，其中子进程正忙于为客户端提供服务；

图示：

• 现在，假设在父进程为客户端1创建了子进程之后，它接受一个新的客户端2的连接请求，并返回一个新的已连接描述符（比如描述符5），如图 12-3 所示；
• 然后，父进程又派生另一个子进程，这个子进程用已连接描述符5为它的客户端提供服务，如图12-4所示；
• 此时，父进程正在等待下一个连接请求，而两个子进程正在并发地为它们各自的客户端提供服务；

图示：

优劣势

优势：

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

劣势：

• 独立的地址空间使得进程共享状态信息变得更加困难，为了共享信息，它们必须使用显式的IPC（进程间通信）机制；
• 基于进程的设计的另一个缺点是，它们往往比较慢，因为进程控制和IPC的开销很高；

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

• 如果有多个I/O事件，一个解决办法就是I/O多路复用（I/O multiplexing）技术；
• 基本的思路就是使用select函数，要求内核挂起进程，只有在一个或多个I/O事件发生后，才将控制返回给应用程序；

示例：

• 当集合$\{0,4\}$中任意描述符准备好读时返回。
• 当集合$\{1,2,7\}$中任意描述符准备好写时返回。
• 如果在等待一个I/O事件发生时过了$152.13$秒，就超时。

函数接口：

#include <sys/select.h>

int select(int n, fd_set *fdset, NULL, NULL, NULL); 
返回已准备好的描述符的非零的个数，若出错则为-1。
    
FD_ZERO(fd_set *fdset);				/* Clear all bits in fdset */
FD_CLR(int fd, fd_set *fdset);	 	/* Clear bit fd in fdset */
FD_SET(int fd, fd_set *fdset);	 	/* Turn on bit fd in fdset */
FD_ISSET(int fd, fd_set *fdset); 	/* Is bit fd in fdset on? */
处理描述符集合的宏。

说明：

• select函数处理类型为fd_set的集合，也叫做描述符集合。逻辑上, 我们将描述符集合看成一个大小为$n$的位向量：

  $$b_{n-1}, \cdots, b_{1}, b_{0}$$

  每个位$b_{k}$对应于描述符$k$ 。

  • 当且仅当$b_{k}=1$，描述符$k$才表明是描述符集合的一个元素。

• 只允许对描述符集合做三件事:

  • 1)分配它们；
  • 2)将一个此种类型的变量赋值给另一个变量；
  • 3)用FD_ZERO、FD_SET、FD_CLR 和FD_ISSET宏来修改和检查它们；

select函数详细说明：

• select函数有两个输入：
  • 读集合的描述符集合(fdset)；
  • 该读集合的基数(n)，任何描述符集合的最大基数；
• select函数会一直阻塞，直到读集合中至少有一个描述符准备好可以读：
  • 当且仅当一个从该描述符读取一个字节的请求不会阻塞时，描述符$k$就表示准备好可以读了；
• select有一个副作用，它修改参数fdset指向的fd_set，指明读集合的一个子集，称为准备好集合(ready set)，这个集合是由读集合中准备好可以读了的描述符组成的；
  • 注意，由于这个副作用，我们必须在每次调用select时都更新读集合；
• 该函数返回的值指明了准备好集合的基数；

例子见课本12.2.1。

优劣势

优点：

• 比基于进程的设计给了程序员更多的对程序行为的控制；
  • 例如，我们可以设想编写一个事件驱动的并发服务器，为某些客户端提供它们需要的服务，而这对于基于进程的并发服务器来说是很困难的；
• 一个基于I/O多路复用的事件驱动服务器是运行在单一进程上下文中的，因此每个逻辑流都能访问该进程的全部地址空间，这使得在流之间共享数据变得很容易；
• 事件驱动设计常常比基于进程的设计要高效得多，因为它们不需要进程上下文切换来调度新的流；

缺点：

• 编码复杂；
• 不能充分利用多核处理器；

基于线程的并发编程

介绍：

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

说明：

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

线程执行模型

介绍：

• 每个进程开始生命周期时都是单一线程，这个线程称为主线程(main thread)；
• 在某一时刻，主线程创建一个对等线程(peer thread)，从这个时间点开始，两个线程就并发地运行；
• 最后，因为主线程执行一个慢速系统调用，例如read或者sleep，或者因为被系统的间隔计时器中断，控制就会通过上下文切换传递到对等线程；
• 对等线程会执行一段时间，然后控制传递回主线程，依次类推；

图示：

线程和进程的区别：

• 一个线程的上下文要比一个进程的上下文小得多，所以线程的上下文切换要比进程的上下文切换快得多；
• 另一个不同就是线程不像进程那样，不是按照严格的父子层次来组织的；
  • 和一个进程相关的线程组成一个对等（线程）池，独立于其他线程创建的线程，主线程和其他线程的区别仅在于它总是进程中第一个运行的线程；
  • 对等（线程）池概念的主要影响是，一个线程可以杀死它的任何对等线程，或者等待它的任意对等线程终止；
  • 每个对等线程都能读写相同的共享数据；

创建线程

接口：

#include <pthread.h>
typedef void *(func)(void *);

int pthread_create(pthread_t *tid, pthread_attr_t *attr, func *f, void *arg);
若成功则返回0，若出错则为非零。
    
pthread_t pthread_self(void);
返回调用者的线程ID。

说明：

• pthread_create函数创建一个新的线程，并带着一个输人变量arg，在新线程的上下文中运行线程例程f ；
• 能用attr参数来改变新创建线程的默认属性，在我们的示例中，总是用一个为NULL的attr参数来调用 pthread_create函数；
• 当pthread_create返回时，参数tid包含新创建线程的ID；
• 新线程可以通过调用pthread_self函数来获得它自已的线程ID。

终止线程

接口：

#include <pthread.h>

void pthread_exit(void *thread_return);
从不返回。

int pthread_cancel(pthread_t tid);
若成功则返回0，若出错则为非零。

说明：

• 一个线程是以下列方式之一来终止的：
  • 当顶层的线程例程返回时，线程会隐式地终止；
  • 通过调用pthread_exit函数，线程会显式地终止；
    • 如果主线程调用pthread_exit，它会等待所有其他对等线程终止，然后再终止主线程和整个进程，返回值为thread_return；
  • 如果某个对等线程调用Linux的exit函数，该函数终止进程以及所有与该进程相关的线程；
  • 另一个对等线程通过以当前线程ID作为参数调用pthread_cancel函数来终止当前线程；

回收已终止线程的资源

接口：

#include <pthread.h>

int pthread_join(pthread_t tid, void **thread_return);
若成功则返回0，若出错则为非零。

说明：

• 线程通过调用pthread_join函数等待其他线程终止；
• pthread_join函数会阻塞，直到线程tid终止，将线程例程返回的通用(void*)指针赋值为thread_return指向的位置，然后回收已终止线程占用的所有内存资源；
• 和Linux的wait函数不同，pthread_join函数只能等待一个指定的线程终止；
  • 没有办法让pthread_wait等待任意一个线程终止；

分离线程

说明：

• 在任何一个时间点上，线程是可结合的(joinable)或者是分离的(detached)；
• 一个可结合的线程能够被其他线程收回和杀死，在被其他线程回收之前，它的内存资源（例如栈）是不释放的；
• 相反，一个分离的线程是不能被其他线程回收或杀死的，它的内存资源在它终止时由系统自动释放；
• 默认情况下，线程被创建成可结合的。为了避免内存泄漏，每个可结合线程都应该要么被其他线程显式地收回，要么通过调用pthread_detach函数被分离；

接口：

#include <pthread.h>

int pthread_detach(pthread_t tid);
若成功则返回0，若出错则为非零。

补充：

• pthread_detach函数分离可结合线程tid；
• 线程能够通过以pthread_self()为参数的pthread_detach调用来分离它们自己；
• 大部分情况想都将使用分离的线程；

初始化线程

• pthread_once函数允许你初始化与线程例程相关的状态；
• once_control变量是一个全局或者静态变量，总是被初始化为PTHREAD_ONCE_ INIT；
• 当第一次用参数once_control调用pthread_once时，它调用init_routine, 这是一个没有输人参数、也不返回什么的函数；
• 接下来的以once_control为参数的pthread_once调用不做任何事情；
• 无论何时，当你需要动态初始化多个线程共享的全局变量时，pthread_once函数是很有用的；

接口：

#include <pthread.h>

pthread_once_t once_control = PTHREAD_ONCE_INIT;
int pthread_once(pthread_once_t *once_control, void(*init_routine)(void));
总是返回0。

线程程序中的共享变量

线程内存模型

• 一组并发线程运行在一个进程的上下文中；
• 每个线程都有它自己独立的线程上下文，包括
  • 线程ID、栈、栈指针、程序计数器、条件码和通用目的寄存器值。
• 每个线程和其他线程一起共享进程上下文的剩余部分，这包括
  • 整个用户虚拟地址空间，是由只读文本 (代码)、读/写数据、堆以及所有的共享库代码和数据区域组成的。
  • 线程也共享相同的打开文件的集合。
• 寄存器是不共享的，虚拟内存是共享的。
• 不同的线程栈是不对其他线程设防的，如果一个线程以某种方式得到一个指向其他线程栈的指针，那么它就可以读写这个栈的任何部分。

将变量映射到内存

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

• 全局变量
  • 全局变量是定义在函数之外的变量。
  • 在运行时，虚拟内存的读/写区域只包含每个全局变量的一个实例，任何线程都可以引用。
• 本地自动变量
  • 本地自动变量就是定义在函数内部但是没有static属性的变量。
  • 在运行时，每个线程的栈都包含它自己的所有本地自动变量的实例，即使多个线程执行同一个线程例程时也是如此。
• 本地静态变量
  • 本地静态变量是定义在函数内部并有static属性的变量。
  • 和全局变量一样，虚拟内存的读/写区域只包含在程序中声明的每个本地静态变量的一个实例。

共享变量

我们说一个变量v当且仅当它的一个实例被一个以上的线程引用。

用信号量同步线程

示例

共享变量是十分方便，但是它们也引人了同步错误(synchronization error)的可能性，考虑如下例子：

/* 
 * badcnt.c - An improperly synchronized counter program 
 */
/* $begin badcnt */
/* WARNING: This code is buggy! */
#include "csapp.h"

void *thread(void *vargp);  /* Thread routine prototype */

/* Global shared variable */
volatile long cnt = 0; /* Counter */

int main(int argc, char **argv) 
{
    long niters;
    pthread_t tid1, tid2;

    /* Check input argument */
    if (argc != 2) { 
	printf("usage: %s <niters>\n", argv[0]);
	exit(0);
    }
    niters = atoi(argv[1]);

    /* Create threads and wait for them to finish */
    Pthread_create(&tid1, NULL, thread, &niters);
    Pthread_create(&tid2, NULL, thread, &niters);
    Pthread_join(tid1, NULL);
    Pthread_join(tid2, NULL);

    /* Check result */
    if (cnt != (2 * niters))
	printf("BOOM! cnt=%ld\n", cnt);
    else
	printf("OK cnt=%ld\n", cnt);
    exit(0);
}

/* Thread routine */
void *thread(void *vargp) 
{
    long i, niters = *((long *)vargp);

    for (i = 0; i < niters; i++) //line:conc:badcnt:beginloop
	cnt++;                   //line:conc:badcnt:endloop

    return NULL;
}
/* $end badcnt */

因为每个线程都对计数器增加了$\mathrm {niters}$次，我们预计它的最终值是$2\times \mathrm {niters}$，但是最后结果却不是这样，并且运行结果都不同。

将循环部分的汇编代码分成五个部分：

• $H_{i}$：在循环头部的指令块。
• $L_{i}$：加载共享变量$\mathrm{cnt}$到累加寄存器$\mathrm{\%rdx_i}$的指令, 这里表示线$\mathrm{\%rdx_i}$程$i$中的寄存器$\mathrm{\%rdx}$的值。
• $U_{i}$：更新（增加）$\mathrm{\%rdx_i}$的指令。
• $S_{i}$：将$\mathrm{\%rdx_i}$的更新值存回到共享变量$\mathrm{cnt}$的指令。
• $T_{i}$：循环尾部的指令块。

注意头和尾只操作本地栈变量，而$L_{i},U_{i}$和$S_{i}$操作共享计数器变量的内容。

如果$L_i, U_i, S_i$的顺序正确，则结果正确，否则可能产生错误结果：

进度图

• 进度图(progress graph)将$n$个并发线程的执行模型化为一条$n$维笛卡儿空间中的轨迹线。
• 每条轴$k$对应于线程$k$的进度。每个$\left(I_{1}, I_{2}, \cdots, I_{n}\right)$代表线程$k(k=1, \cdots, n)$已经完成了指令$I_{k}$这一状态。
• 图的原点对应于没有任何线程完成一条指令的初始状态。

一个程序的执行历史被模型化为状态空间中的一条轨迹线，图12-20展示了下面指令顺序对应的轨迹线：

$$H_{1}, L_{1}, U_{1}, H_{2}, L_{2}, S_{1}, T_{1}, U_{2}, S_{2}, T_{2}$$

图示：

回到之前的例子：

• 对于线程$i$，操作共享变量$\mathrm{cnt}$内容的指令$\left(L_{i}, U_{i}, S_{i}\right)$构成了一个（关于共享变量$\mathrm{cnt}$的）临界区（critical section），这个临界区不应该和其他进程的临界区交替执行。
• 换句话说，我们想要确保每个线程在执行它的临界区中的指令时，拥有对共享变量的互斥的访问（mutually exclusive access）。
• 通常这种现象称为互斥（mutual exclusion）。
• 两个临界区的交集形成的状态空间区域称为不安全区（unsafe region）。
• 绕开不安全区的轨迹线叫做安全轨迹线（safe trajectory），接触到任何不安全区的轨迹线就叫做不安全轨迹线（unsafe trajectory）。

同步线程的方式是使他们总是有一条安全轨迹线，一种方式是使用信号量。

信号量

信号量$s$是具有非负整数值的全局变量，只能由两种特殊的操作来处理，这两种操作称为$P$和$V$：

• $P(s)$：如果$s$是非零的，那么$P$将$s$减1，并且立即返回。如果$s$为零，那么就挂起这个线程，直到$s$变为非零，而一个$V$操作会重启这个线程。在重启之后，$P$操作将$s$减1，并将控制返回给调用者。
  • $P$ 中的测试和减1操作是不可分割的，也就是说， 一旦预测信号量$s$变为非零，就会将$s$减1，不能有中断。
• $V(s)$：$V$操作将$s$加1。如果有任何线程阻塞在$P$操作等待$s$变成非零，那么$V$操作会重启这些线程中的一个，然后该线程将$s$减1，完成它的$P$操作。
  • $V$中的加1操作也是不可分割的，也就是加载、加1和存储信号量的过程中没有中断。
  • $V$的定义中没有定义等待线程被重启动的顺序，唯一的要求是$V$必须只能重启一个正在等待的线程。因此，当有多个线程在等待同一个信号量时，无法预测$V$操作要重启哪一个线程。

接口：

#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) */

返回：若成功则为0，若出错则为-1。

说明：

• sem_init函数将信号量sem初始化为value，每个信号量在使用前必须初始化，针对我们的目的，中间的参数总是零。
• 程序分别通过调用sem_wait和sem_post函数来执行$P$和$V$操作。

等价的$P, V$接口：

#include "csapp.h"

void P(sem_t *s);	/* wrapper function for sem_wait */
void v(sem_t *s);	/* Wrapper function for sem_post */

返回：无。

使用信号量来实现互斥

• 信号量提供了一种很方便的方法来确保对共享变量的互斥访问。
  • 基本思想是将每个共享变量（或者一组相关的共享变量）与一个信号量$s$（初始为1）联系起来，然后用$P(s)$和$V(s)$操作将相应的临界区包围起来。
• 以这种方式来保护共享变量的信号量叫做二元信号量（binary semaphore），因为它的值总是0或者1 。
• 以提供互斥为目的的二元信号量常常也称为互斥锁（mutex）。
• 在一个互斥锁上执行$P$操作称为对互斥锁加锁，执行$V$操作称为对互斥锁解锁。
• 对一个 互斥锁加了锁但是还没有解锁的线程称为占用这个互斥锁。
• 一个被用作一组可用资源的计数器的信号量被称为计数信号量。

用二元信号量来正确同步程序计数器的示例：

• 用$P,V$创建一组状态，叫做禁止区（forbidden region），其中$s<0$ 。
• 因为信号量的不变性，没有实际可行的轨迹线能够包含禁止区中的状态。
• 而且，因为禁止区完全包括了不安全区，所以没有实际可行的轨迹线能够接触不安全区的任何部分。
• 因此，每条实际可行的轨迹线都是安全的，而且不管运行时指令顺序是怎样的，程序都会正确地增加计数器值。

代码

/* 
 * goodcnt.c - A correctly synchronized counter program 
 */
/* $begin goodcnt */
#include "csapp.h"

void *thread(void *vargp); /* Thread routine prototype */

/* Global shared variables */
/* $begin goodcntsemdef */
    volatile long cnt = 0; /* Counter */
    sem_t mutex;           /* Semaphore that protects counter */
/* $end goodcntsemdef */

int main(int argc, char **argv) 
{
    int niters;
    pthread_t tid1, tid2;

    /* Check input argument */
    if (argc != 2) {
	printf("usage: %s <niters>\n", argv[0]);
	exit(0);
    }
    niters = atoi(argv[1]);

    /* Create threads and wait for them to finish */
/* $begin goodcntseminit */
    Sem_init(&mutex, 0, 1);  /* mutex = 1 */
/* $end goodcntseminit */
    Pthread_create(&tid1, NULL, thread, &niters);
    Pthread_create(&tid2, NULL, thread, &niters);
    Pthread_join(tid1, NULL);
    Pthread_join(tid2, NULL);

    /* Check result */
    if (cnt != (2 * niters))
	printf("BOOM! cnt=%ld\n", cnt);
    else
	printf("OK cnt=%ld\n", cnt);
    exit(0);
}

/* Thread routine */
void *thread(void *vargp) 
{
    int i, niters = *((int *)vargp);

/* $begin goodcntthread */
    for (i = 0; i < niters; i++) {
	P(&mutex);
	cnt++;
	V(&mutex);
    }
/* $end goodcntthread */
    return NULL;
}
/* $end goodcnt */

图示：

利用信号量来调度共享资源

信号量的另一个重要作用是调度对共享资源的访问，有两个经典例子。

生产者-消费者问题

• 生产者和消费者线程共享一个有$n$个槽的有限缓冲区。
• 生产者线程反复地生成新的项目（item），并把它们揷人到缓冲区中。
• 消费者线程不断地从缓冲区中取出这些项目，然后消费（使用）它们。
• 示例：多媒体系统。

图示：

读者-写者问题

• 一组并发的线程要访问一个共享对象，例如一个主存中的数据结构，或者一个磁盘上的数据库。
• 有些线程只读对象，而其他的线程只修改对象。
• 修改对象的线程叫做写者，只读对象的线程叫做读者。
• 写者必须拥有对对象的独占的访问，而读者可以和无限多个其他的读者共享对象。
• 一般来说，有无限多个并发的读者和写者。
• 示例：航班预订系统。

使用线程提高并行性

顺序，并发和并行程序之间的关系：

• 写顺序程序只有一条逻辑流。
• 写并发程序有多条并发流。
• 并行程序是一个运行在多个处理器上的并发程序。

图示：

说明：

• 操作（$P$和$V$）代价太大。
• 这突显了并行编程的一项重要教训：同步开销巨大，要尽可能避免。
• 如果无可避免，必须要用尽可能多的有用计算弥补这个开销。

刻画并行程序的性能

• 并行程序的加速比（speedup）：

  $$S_{p}=\frac{T_{1}}{T_{p}}$$
  • 这里$p$是处理器核的数量，$T_{K}$是在$k$个核上的运行时间。
  • 这个公式有时被称为强扩展（strong scaling）。
  • 当$T_{1}$是程序顺序执行版本的执行时间时，$S_{p}$称为绝对加速比（absolute speedup）。
  • 当$T_{1}$是程序并行版本在一个核上的执行时间时，$S_{p}$称为相对加速比（relative speedup）。
  • 绝对加速比比相对加速比能更真实地衡量并行的好处。因为即使是当并行程序在一 个处理器上运行时，也常常会受到同步开销的影响，而这些开销会人为地增加相对加速比的数值,因为它们增加了分子的大小。
  • 另一方面，绝对加速比比相对加速比更难以测量，因为测量绝对加速比需要程序的两种不同的版本。对于复杂的并行代码，创建一个独立的顺序版本可能不太实际，或者因为代码太复杂，或者因为源代码不可得。

• 一种相关的测量量称为效率（efficiency），定义为

  $$E_{p}=\frac{S_{p}}{p}=\frac{T_{1}}{p T_{p}}$$
  • 通常表示为范围在$(0,100]$之间的百分比。
  • 效率是对由于并行化造成的开销的衡量，具有高效率的程序比效率低的程序在有用的工作上花费更多的时间，在同步和通信上花费更少的时间。

• 加速比还有另外一面，称为弱扩展(weak scaling)。

  • 在增加处理器数量的同时，增加问题的规模，这样随着处理器数量的增加，每个处理器执行的工作量保持不变。
  • 在这种描述中，加速比和效率被表达为单位时间完成的工作总量。

其他并发问题

线程安全

• 一个函数被称为线程安全的（thread-safe），当且仅当被多个并发线程反复地调用时, 它会一直产生正确的结果。
• 如果一个函数不是线程安全的，我们就说它是线程不安全的（thread-unsafe）。

四个（不相交的）线程不安全函数类：

• 第1类：不保护共享变量的函数。

  • 示例：badcnt。
  • 将这类线程不安全函数变成线程安全函数的方法是使用$P,V$。
  • 优点：调用程序中不需要做任何修改。
  • 缺点：缺点是同步操作将减慢程序的执行时间。

• 第2类：保持跨越多个调用的状态的函数。

  • 示例：rand。

    #include <stdio.h>
    
    /* $begin rand */
    unsigned next_seed = 1;
    
    /* rand - return pseudorandom integer in the range 0..32767 */
    unsigned rand(void)
    {
        next_seed = next_seed*1103515245 + 12543;
        return (unsigned)(next_seed>>16) % 32768;
    }
    
    /* srand - set the initial seed for rand() */
    void srand(unsigned new_seed)
    {
        next_seed = new_seed;
    } 
    /* $end rand */
    
    int main()
    {
        srand(100);
        printf("%d\n", rand());
        printf("%d\n", rand());
        printf("%d\n", rand());
        return 0;
    }

  • 将这类线程不安全函数变成线程安全函数的方法重写。

  • 缺点：需要修改调用程序，工作量很大。

• 第3类：返回指向静态变量的指针的函数。

  • 示例：ctime，gethostbyname，计算结果放在一个静态变量里，然后返回指向该静态变量的指针。

  • 有两种方法来处理这类线程不安全函数。

    • 一种选择是重写函数，使得调用者传递存放结果的变量的地址。这就消除了所有共享数据，但是它要求程序员能够修改函数的源代码。

    • 另一种方式是在调用时候加锁-复制（lock-and-copy）技术，将线程不安全函数与互斥锁联系起来。

      • 在每一个调用位置，对互斥锁加锁，调用线程不安全函数，将函数返回的结果复制到一个私有的内存位置，然后对互斥锁解锁。
      • 一般会写一个包装函数。

      /* 
       * ctime_ts - A thread-safe wrapper for ctime
       */
      #include "csapp.h"
      #define MAXSTR 128
      
      static sem_t mutex; /* protects calls to ctime */
      
      static void init_ctime_ts(void)
      {
          Sem_init(&mutex, 0, 1);
      }
      
      /* $begin ctime_ts */
      char *ctime_ts(const time_t *timep, char *privatep)
      {
          char *sharedp; 
      
          P(&mutex);
          sharedp = ctime(timep);
          strcpy(privatep, sharedp); /* Copy string from shared to private */
          V(&mutex);
          return privatep;
      }
      /* $end ctime_ts */
      
      int main()
      {
          char timestr[MAXSTR];
          time_t timeval;
      
          /* Thread-safe code to print the current time string */
          init_ctime_ts();
          timeval = time(NULL);
          ctime_ts(&timeval, timestr);
          printf("%s", timestr);
          exit(0);
      }

• 第4类：调用线程不安全函数的函数。

  • 如果是被调用的函数是第2类，则是线程不安全的；否则可能为线程安全的。

可重入性

• 有一类重要的线程安全函数，叫做可重入函数（reentrant function）。
• 其特点在于它们具有这样一种属性：当它们被多个线程调用时，不会引用任何共享数据。

线程安全函数，可重入函数的关系：

显式可重入和隐式可重入：

• 如果所有的函数参数都是传值传递的（即没有指针），并且所有的数据引用都是本地的自动栈变量（即没有引用静态或全局变量），那么函数就是显式可重入的（explicitly reentrant）。
  • 无论它是被如何调用的，都可以断言它是可重人的。
• 如果允许显式可重人函数中一些参数是引用传递的（即允许它们传递指针），那么我们就得到了一个隐式可重入的（implicitly reentrant）函数。
  • 也就是说，如果调用线程小心地传递指向非共享数据的指针，那么它是可重入的。

竞争

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

示例：

/* 
 * race.c - demonstrates a race condition
 */
/* $begin race */
/* WARNING: This code is buggy! */
#include "csapp.h"
#define N 4

void *thread(void *vargp);

int main() 
{
    pthread_t tid[N];
    int i;

    for (i = 0; i < N; i++)                        //line:conc:race:incri
	Pthread_create(&tid[i], NULL, thread, &i); //line:conc:race:createthread
    for (i = 0; i < N; i++) 
	Pthread_join(tid[i], NULL);
    exit(0);
}

/* Thread routine */
void *thread(void *vargp) 
{
    int myid = *((int *)vargp);  //line:conc:race:derefarg
    printf("Hello from thread %d\n", myid);
    return NULL;
}
/* $end race */

解决方法是为每个线程分配一个独立的块：

/* 
 * norace.c - fixes the race in race.c
 */
/* $begin norace */
#include "csapp.h"
#define N 4

void *thread(void *vargp);

int main() 
{
    pthread_t tid[N];
    int i, *ptr;

    for (i = 0; i < N; i++) {
        ptr = Malloc(sizeof(int));                    //line:conc:norace:createthread1
        *ptr = i;                                     //line:conc:norace:createthread2
        Pthread_create(&tid[i], NULL, thread, ptr);   //line:conc:norace:createthread3
    } //line:conc:norace:endloop
    for (i = 0; i < N; i++) 
        Pthread_join(tid[i], NULL);
    exit(0);
}

/* Thread routine */
void *thread(void *vargp) 
{
    int myid = *((int *)vargp); //line:conc:norace:assign
    Free(vargp); 
    printf("Hello from thread %d\n", myid);
    return NULL;
}
/* $end norace */

死锁

死锁（deadlock），指的是一 组线程被阻塞了，等待一个永远也不会为真的条件。

示例：

说明：

• 如果使用$P$和$V$操作顺序不当，以至于两个信号量的禁止区域重叠。如果某个执行轨迹线碰巧到达了死锁状态$d$，那么就不可能有进一步的进展了，因为重叠的禁止区域阻塞了每个合法方向上的进展。
• 重叠的禁止区域引起了一组称为死锁区域（deadlock region）的状态。

规避死锁的规则：

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

示例：