CSAPP 第十二章 并发编程

构造并发程序和并发引起的问题

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

并发不仅仅局限于内核，它也可以在应用程序中扮演重要角色。应用级并发在其他情况下也是很有用的：

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

现代操作系统提供三种基本的构造并发程序的方法：进程、I/O 多路复用、线程。

基于进程的并发编程

构造并发程序最简单的方法就是用进程，使用 fork、exec 和 waitpid 等函数。一个构造并发服务器的自然方法就是，在父进程中接受客户端连接请求，然后创建一个新的子进程来为每个新客户端提供服务。

基于进程的并发服务器

服务器通常会运行很长的时间，这意味着操作系统不会帮助进程回收内存，我们需要做到以下几点：

• 包括一个 SIGCHLD 处理程序来回收僵死进程，因为 Linux 的信号是不排队的，所以说一次要处理完所有的子进程。
• 对于父进程，需要在 fork 之后马上 close 建立连接的描述符，对于子进程来说，也要关闭所有的文件描述符。

进程的优劣

进程共享文件表，但是不共享用户地址空间（这既是优点也是缺点），不会发生内存覆盖的情况，但是也造成了通信困难。

为了通信，需要使用 IPC（进程间通信）机制，但它通常比较慢。

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

如果我们同时响应这两个 I/O 事件： 1) 网络客户端发起连接请求，2) 用户在键盘上键人命令行。那我们该先响应哪一个呢？。如果在 accept 中等待一个连接请求，我们就不能响应输入的命令。类似地，如果在 read中
等待一个输人命令，我们就不能响应任何连接请求。

针对这种困境的一个解决办法就是 I/O 多路复用技术。基本的思路就是使用 select 函数，要求内核挂起进程，只有在一个或多个 I/O 事件发生后，才将控制返回给应用程序，

例如下面的示例：

select 是一个复杂的函数，有许多不同的使用场景。我们只讨论第一种场景：等待一组描述符准备好读。

#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$$ 。当且仅当 $$b_k$$=1，描述符才表明是描述符集合的一个元素。

这个函数只允许对描述符集合做三件事：1) 分配它们，2) 将一个此种类型的变量赋值给另一个变量，3) 用 FD ZERO、FD SET、FD CLR 和 FD ISSET 宏来修改和检查它们。

针对我们的目的，select 函数有两个输人：一个称为读集合的**描述符集合(fd_set)和该读集合的基数(n)**（实际上是任何描述符集合的最大基数）。select 函数会一直阻塞，直到读集合中至少有一个描述符准备好可以读。当且仅当一个从该描述符读取一个字节的请求不会阻塞时，描述符 k 就表示准备好可以读了。

我们看下面的例子：

假设有两个文件 fd1、fd2，我要实现当某个描述符准备时进行读取对应的文件。

#include<sys/select.h>
#include<unistd.h>
fd_set readset，ready_set;
FD_CLR(&readset);
FD_SET(fd1,&readset);
FD_SET(fd2,&readset);
while(1)
{
    ready_set = readset;//每次需要重新赋值一遍
    select(listenfd + 1, &readset, NULL, NULL, NULL);
    if(FD_ISSET(fd1,&readset))
    {
        read(fd1,buffer,0x100);
    }
    if(FD_ISSET(fd2),&readset)
    {
        read(fd2,buffer,0x100);
    }
}

如果两个都没有准备好，就会阻塞了。

接下来的小节讲了一个实例，略🤪

I/O 多路复用技术的优劣

优点：

调试方便，每个逻辑流都能访问该进程的全部地址空间，且不需要上下文切换。

缺点：

如果面对网络延迟较高的用户，那么这个用户会阻塞整个服务，甚至会有恶意用户故意只发送部分文本行，导致整个服务被阻塞。

基于线程的并发编程

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

线程执行模型

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

线程的上下文切换速度比进程要快的多，因为线程大部分数据是共享的。同时，线程不像进程那样有严格的父子层次关系。和一个进程相关的线程组成一个对等(线程)池，独立于其他线程创建的线程。主线程和其他线程的区别仅在于它总是进程中第一个运行的线程。

对等(线程)池概念的主要影响是，一个线程可以杀死它的任何对等线程，或者等待它的任意对等线程终止。

POSIX 线程

Posix 线程（Pthreads）就是在 C 程序中处理线程的一个标准接口。Pthreads 定义了大约 60个函数，允许程序创建杀死和回收线程，与对等线程安全地共享数据，还可以通知对等线程系统状态的变化。

创建线程

线程通过 pthread_create 函数来创建其他线程。

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

int pthread_create(pthread_t *tid, pthread_attr_t *attr,
                   func *f, void *arg);
// 若成功则返回 0，若出错则为非零。

pthread_create 函数创建一个新的线程，并带着一个输入变量 arq，在新线程的上下文中运行线程例程 f 。能用 attr 参数来改变新创建线程的默认属性。

当 pthread_create 返回时，参数 tid 包含新创建线程的 ID。新线程可以通过调用 pthread_self 函数来获得它自己的线程 ID 。

#include <pthread.h>

pthread_t pthread_self(void);
//返回调用者的线程 ID。

终止线程

一个线程是以下列方式之一来终止的：

• 当顶层的线程例程返回时，线程会隐式地终止。
• 通过调用 pthread_exit 函数，线程会显式地终止。如果主线程调用 pthread_exit，它会等待所有其他对等线程终止，然后再终止主线程和整个进程，返回值为 thread_return 。

#include <pthread.h>

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

• 某个对等线程调用 Linux 的 exit 函数，该函数终止进程以及所有与该进程相关的线程。
• 另一个对等线程通过以当前线 ID 作为参数调用 pthread_cancel 函数来终止当前线程。

#include <pthread.h>

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

回收已终止线程的资源

线程通过调用 pthread_join 函数等待其他线程终止。

#include <pthread.h>

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

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，若出错则为非客

对于一些 web 服务器，我们就可以分离线程让主线程不必等待，等到线程自己执行完毕后等待系统回收内存资源。

初始化线程

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。

当你第一次用参数 once_control 调用 pthread_once 时，它调用 init_routine，这是一个没有输人参数、也不返回什么的函数。接下来的以 once_control 为参数的 pthread_once 调用不做任何事情。

当我们需要动态初始化多个线程共享的全局变量时，pthread_once 函数是很有用的。

基于线程的并发服务器

在 accept 请求时会返回一个连接描述符，假如在线程中还没有拿这个值，此时主线程下一个 accept 已经到来。就会导致这个线程取出了一个错误的描述符。这就导致了一个竞争的危险。

多线程程序中的共享变量

主要就是在讲线程中什么变量是共享的

线程内存模型

寄存器是不共享的，但是虚拟内存是共享的。它们的栈说是独立的，其实也可以是共享的，只要知道内存地址，便可以轻松访问其它线程的栈，

将变量映射到内存

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

• 全局变量，在 bss 或者 data 段上。
• 本地变量，在栈或者是寄存器上。
• 本地静态变量，在 bss 或者 data 段上。

共享变量

我们说一个变量 “是共享的，当且仅当它的一个实例被一个以上的线程引用。

用信号量同步线程

共享变量引入了同步错误的可能性。

例如，多线程执行 cnt++ ，我们预测最终的结果是每个线程做加法的和，但实际上并不是相加的次数。

我们需要了解一下执行计数的这一句代码，它在汇编层面被分成了三步：

movq 	cnt(%rip),%rdx
addq	$1,%rdx
movq	%rdx,cnt(%rip)

我们知道，多线程同时运行时，并不能保证这个 cnt++ 代码完整的执行完以后才转换到另一个线程。可能发生这种情况：线程 1 从内存中取值，正在进行 add 操作，但并没有返回内存。这时线程 2 从内存中取值，取到的值还是线程 1 没有处理过的值，所以这两个线程分别进行加一的操作并存储回内存，得到的结果只是加了一次，就出现了错误。

信号量

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

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

使用信号量来实现互斥

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

以提供互斥为目的的二元信号量常常也称为互斥锁（mutex）。在一个互斥锁上执行 P 操作称为对互斥锁加锁。类似地，执行 V 操作称为对互斥锁解锁。对一个互斥锁加了锁但是还没有解锁的线程称为占用这个互斥锁。

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

实现我真的看不懂我就写写问题原理啥的剩下的再补，也可能不会补(x

信号量调度对共享资源的访问。在这种场景中，一个线程用信号量操作来通知另一个线程，程序状态中的某个条件已经为真了。

两个经典的例子是生产者-消费者和读者-写者问题。

生产者-消费者

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

我们必须保证对缓冲区的访问是互斥的，还需要调度对缓冲区的访问。如果缓冲区是满的，那么生产者必须等待直到有一个槽位变为可用。与之相似，如果缓冲区是空的，那么消费者必须等待直到有一个项目变为可用。

生产者和消费者共用一个信号量，同时也共用锁。

读者-写者

修改对象的线程叫做写者。只读对象的线程叫做读者。写者必须拥有对对象的独占的访问，而读者可以和无限多个其他的读者共享对象。一般来说，有无限多个并发的读者和写者。

例如我们抢演唱会门票，我和另一个人选了同一个座位，点进去的时候显示是有票（读数据库）。这时我结算订单比她快（写数据库），她付款的时候就会显示没票。

这个问题分读者有限和写者优先两种方案。

其他并发问题

线程安全

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

以下四种函数被认为是不安全的：

• 不保护共享变量的函数
• 保持跨越多个调用状态的函数
• 返回指向静态变量的指针的函数
• 调用线程不安全函数的函数

处理线程不安全函数有两种方法：1）重写函数 ，2）使用加锁 - 复制技术

竞争和死锁

竞争

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

例如下面的实例：

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#define N 4

void *thread(void *vargp)
{
    int myid=*((int *)vargp);
    printf("Hello from thread %d\n",myid);
    return NULL;
}

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

    for (i = 0; i < N; i++) { 
        pthread_create(&tid[i], NULL, thread, &i);
    }
    for (i = 0; i < N; i++) {
        pthread_join(tid[i], NULL); 
    }
    exit(0);
}

我们理想的状态是依次输出 ID 0，1，2，3。但实际上的运行结果如下：

这就是由每个对等线程和主线程之间的竞争引起的。

代码中的两个 for 循环中，第一个 for 循环传递了一个指向本地栈变量的指针。在下一次 for 循环对 i 加1和*thread 参数的间接引用和赋值之间就发生了竞争。如果对等线程在主线程执行对加1之前就执行了 *thread ，那么 myid 变量就得到正确的 ID。否则，它包含的就会是其他线程的 ID。

解决方案就是为每个整数 ID 分配一个独立的快，并传递给线租例程一个指向这个块的指针。如下：

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#define N 4

void *thread(void *vargp)
{
    int myid = *((int *)vargp);
    free(vargp);
    printf("Hello from thread %d\n"，myid);
    return NULL;
}

int main()
{
    pthread_t tid[N];
    int i,*ptr;
    
    for (i =0;i<N;i++) 
    {
        ptr = Malloc(sizeof(int));
        *ptr = i;
        pthread_create(&tid[i],NULL，thread,ptr);
    }
    
    for (i=0;i<N;i++)
    {
        pthread_join(tid[i]，NULL);
    }
    exit(0);
}

死锁

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

比较糟糕的是，死锁错误不可预测，且错误不可重读，因为每一不同的执行都有不同的轨迹线。很有可能我们执行很多次测试都没有出现问题，最后交给上面领导运行一下就死锁了。

当使用二元信号量来实现互斥时，我们可以应用互斥锁加锁顺序规则来避免死锁。

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

---

大板砖 overover !!

明天去杭电吃饭！