多线程并发

进程到线程

进程是计算机程序被执行的一个实例(instance), 一个进程可能由一个或者多个线程（thread）组成， 同时执行命令。
线程（thread） 它代表一列有顺序的，需要 CPU 执行的指令，可以随时被内核开始、中断或继续运行。

线程使用栈来记忆如何从函数中返回，以及存储变量和参数等等。在多线程状态下，每个线程拥有一个自己的栈和程序计数器（PC），而堆，地址空间和全局变量则是多个线程共用的。每个线程对应一个叫做 线程控制块（Thread Control Block，TCB） 的数据结构，里面存储了这个线程的栈指针、程序计数器、处理器状态、线程标识符（类似于进程标识符，是系统中唯一标明这个线程的一个数字）等等。

为什么出现线程

我们过去应用多进程是为了使得多个程序并发，改善资源利用效率。但是各个进程之间不共享内存地址，给我
们造成了许多不便。使用多线程则可以避免这些问题。
不同线程之间共享地址空间，只是栈和程序计数器不同，因此两个线程间通信也较为容易。
更为重要的是，在不同进程间切换时，由于进程地址空间不同，我们需要清空翻译快表和基于逻辑地址的高速
缓冲存储器，这一过程会使我们的程序运行效率大打折扣；
线程间切换就没有这个问题，对于提高程序运行效率大有裨益。

多线程经常面临的问题是多个线程的运行顺序是不确定的，且当它们同时修改一个变量时我们最终得到的结果也是不确定的。为了控制多线程运行的结果，我们将引入互斥和同步的概念，并介绍实现互斥和同步的方法。
不过在开始介绍有关互斥和同步的概念以前，让我们先来夯实基础，学习线程的不同类型、Linux 对于线程的实现和 Linux Pthread 库包含的函数。
不同系统对于线程的实现主要分三种类型: 内核级线程、用户级线程和混合式线程。在这里我们首先要强调一点，就是这里的内核级和用户级指的 并不是 线程的特权等级！
一个用户进程建立的线程还是只有原来这个进程的特权等级，不能执行只有内核才能执行的指令。用户级和内核级指的是这个线程是会被用户进程还是内核调度。
我们虽然还没有学到任务调度的算法，但我们已经知道，系统会用某种方式调度不同的任务，使他们在处理器上交替运行，这个过程就是内核对于任务的调度。一个内核级的线程就将在系统中获得被调度的权限，在这种情况下，如果一个进程有两个线程，那么这两个线程会被独立地调度，因此这个进程占取的处理器时间就是这两个线程占取的处理器时间之和。

内核级线程模型 及 用户级线程的模型

在内核级线程模型中，一个线程如果进行 I/O 操作而被阻塞，那么这个进程剩余的线程还可以继续运行，因此线程的状态不等于进程的状态。同样地，如果一个线程给自己的进程发送 sleep 信号，这个线程依然可以继续运行。
与内核级相对的用户级线程就没有这种权限了。如果一个系统使用用户级线程的模式，那么它就只会调度进程，进程内部再自行调度线程。这就是说属于同一个进程的两个线程永远不会同时在两个处理器上运行；进程也不会因为多分出了几个线程就获得更多的处理器时间。更糟糕的是，如果一个线程由于 I/O 或其它原因被阻塞，那么整个进程就都会被阻塞；而在内核级线程的模型中，一个线程被阻塞后其它线程还可以继续运行。看到这里你可能会问，这种用户级线程对于分出线程的进程来讲有什么好处呢？
相对于分出子进程运行同样的内容，用户级线程的优势是显而易见的——多个线程间可以共享地址空间，减少通信带来的麻烦。

相对于内核级线程来讲，用户级线程有两个优点。

一方面，它减少了线程间上下文切换的代价。内核级线程被系统调度，因此同一进程中不同线程间的上下文切换也会导致用户态向内核态的转换，这就包含了从一个用户线程进入内核线程，再进入另一个用户级线程的繁琐过程。用户级线程由于不涉及用户态向内核态的转换，也就没有这些缺点。

另一方面，同一进程不同用户级线程间的调度完全由用户进程本身决定，用户进程就可以用自己的调度算法选择最优的调度方法；

内核级线程在这方面就没有这种优势——内核对于用户级进程来讲相当于一个黑箱，我们无法知道里面运行的是何种调度算法，因此不能预测或控制它的效率。

混合式线程

学完了内核级线程和用户级线程，你可能会问一个问题：有没有一种线程的设计方法，能综合内核级线程和用户级线程的优点呢？这就是混合式线程。在混合式线程中，用户即可以建立用户级线程，也可以通过系统调用建立内核级线程。假设一个进程建立了 N 个用户级线程， M 个内核级线程，那么 N≥M，且用户可以自己调整用户级进程向内核级线程的映射。这种方法使对应着同一个内核级线程的用户级线程之间的切换更加高效，同时又使一个进程能够获得更多处理器时间、不会被一个线程阻塞。

这种线程模型的缺点就在于它非常复杂、不利于实现。FreeBSD 和 NetBSD 两个系统都曾经使用过华盛顿大学在一篇论文中提出的混合式线程模型，但它们现在都已经放弃了这种模型；大部分 Linux 系统中使用的也是较为简单的内核级线程模型。 可以假设我们所讲的线程都是内核级线程 ，而非用户级线程。

在命名线程模型时，我们也可以用不同模型中内核级线程和用户级线程之间的对应关系来区别这些模型。内核级线程模型中，由于每个线程都是一个可以被内核调度的任务，用户级线程与内核级线程的对应关系是 1:1 的，我们就叫它 1:1 线程模型；与之形成对比的是用户级线程模型，在这种模型中一个进程中的多个用户级线程都被映射到一个可以调度的任务中，因此用户级线程与内核级线程的对应关系是 N:1 的，我们就叫它N:1 模型；最后，混合式线程模型中，一个进程可以建立 N 个用户级线程和 M 个内核级线程，因此它就被称为 N:M 模型。

线程的创建与回收

Linux 中对于 POSIX 标准定义的线程的实现。这种线程被称为pthread，是 POSIX thread 的缩写。你可以通过调用函数pthread_create来创建一个新的pthread线程:

#include <pthread.h> 
int pthread_create(pthread_t *thread, const pthread_attr_t *attr,
    void *(*start_routine) (void *), void *arg);

它的第一个参数是一个指向 Linux 线程标识符的指针。pthread_t这个类型在bits/pthreadtypes.h中定义（在 Linux man pages的网站上你可以找到这个头文件并阅读其中的源代码），是一个无符号的长整数型，它类似于我们之前看到的pid_t，pthread_t可以在系统中唯一标识你正要创建的这个线程。（因为pthread.h里已经#include <bits/pthreadtypes.h>（在 Linux man pages的网站上你可以找到这个头文件并阅读其中的源代码），因此实际编程中我们一般不再额外#include <bits/pthreadtypes.h>）

attr是一个指向定义新线程特性的结构的指针，你可以用函数来设置这个结构里不同域的值，但一般我们都直接代入NULL，使用默认值运行。

#include <pthread.h>
int pthread_create(pthread_t *thread, const pthread_attr_t *attr,
    void *(*start_routine) (void *), void *arg);

start_routine是一个指向函数的指针，这个被创建的新线程将只执行这一个函数；你可以看到，它的参数必须是一个泛型指针，它的返回值也必须是一个泛型指针。
最后一个参数arg就是用来传递给start_routine的参数。之所以要使用泛型指针，是因为我们希望传入数据的类型不要被限制。我们可以自己定义一个需要的数据结构，然后将指向该结构的指针作为泛型指针传入，函数也能够正常运行。

pthread_create成功运行后会将新线程的标识符存入thread所指的位置，并返回 \ 0 0，否则它就会返回一个错误号，这时thread所指的位置存入的内容是没有被定义的。如果你想了解pthread_create具体定义了哪些错误号，请参阅 Linux man pages。

一个线程被创建后，创建这个线程的原线程仍会继续运行 ，一个新的线程会进入就绪态，等待运行。一旦新线程开始运行，它就会开始执行你输入pthread_create()的函数，它会有一个自己独立的栈。这时如果我们想从原来的线程中获得新线程的返回值就需要调用pthread_join：

#include <pthread.h>
int pthread_join(pthread_t thread, void **retval);

它的第一个参数thread就是我们从pthread_create获得的线程标识符，这个函数会等待线程标识符等于thread的线程运行完毕，并将它的返回值存入后一个参数**retval所指的位置。

如果这个函数运行成功，那么它会返回 \ 0 0，并将线程返回值存储到retval所指的位置；否则它会返回一个错误码（见 Linux man pages）。还记得上一章我们介绍的种种进程间通信的方法吗？我们之所以需要这些方法就是因为我们不能直接获得另一个进程中的数据；而利用线程我们则可以直接获得一个自定义数据结构的返回值，这就是多线程相对于多进程的优势。
在非并发的程序中，我们的指令执行是有先后关系的；在多线程并发的程序中，我们可以将没有先后关系的程序放到多个线程中并发运行，然而并不是所有指令都可以无顺序运行（比如，我们可能会需要前面计算的结果进行新的运算），因此我们就需要在代码中的某一位置等待所有前面运行的代码结束后再运行，这时我们就会调用pthread_join。
除了pthread_join我们也可以用pthread_cancel来撤销线程。在线程中调用pthread_exit也可以撤销线程。

#include <pthread.h>
int pthread_cancel(pthread_t thread);
void pthread_exit(void *retval);

注意，pthread_exit是在我们希望停止的线程内被调用的，而pthread_cancel是在别的线程中被调用的。一旦撤销一个线程，我们就不能从这个线程中获得任何返回值了。cancel实际上被人们使用得不多，因为它没有给线程清理自己资源的机会（一些线程没办法关掉已打开的文件）。

除了上面这两种结束线程的方式外，我们还可以通过调用exit()或者在主函数中return结束同一个进程中的其它线程。一些信号（比如SIGTERM）也可以终止进程内的所有线程。

资源竞争与互斥

多线程虽然方便快捷，但是问题也不少。在第一节的小诗中我们已经见识到了多线程执行顺序的不确定性所带来的问题；多线程程序还面临着另一个问题：由于不同线程间共享内存地址空间，一旦两个线程同时试图修改同一个地址，我们就面临着 资源竞争（race condition） ，而竞争的结果是不确定的。这一节我们来见识一下资源竞争带来的问题。
出于某种原因，你需要将一个整数从零逐个增加到一千万。为了节约时间，我们将使用两个线程分别增加这个整数。我们有如下代码：

#include <pthread.h>
#include <stdlib.h>
#include <stdio.h>

int *number;

void *adding(void *arg){
  for(int i = 0; i < 5000000; i++){
    (*(int *)arg)++;
  }
  return NULL;
}
void *adding(void *arg);
int main(){
  number = malloc(sizeof(int));
  pthread_t p[2];
  pthread_create(&p[0], 0, adding, number);
  pthread_create(&p[1], 0, adding, number);
  pthread_join(p[0], (void**)NULL);
  pthread_join(p[1], (void**)NULL);
  printf("%d\n", *number);
  return 0;
}

编译执行之后，我们的程序会在屏幕上打印出什么呢？
我们增加number的方法是使用+=操作符。问题在于，这个指令并不是不可拆分的（atomic）。如果你学过一些计算机组成原理，你可能知道，这个指令实际上是 CPU 先将这个数字读取到寄存器中，然后增加 1，然后写回内存。在这个过程中，很可能出现的一个情况是当一个线程从内存中读取这个整数之后，还尚未增加或者写回它，另一个线程也从内存中读取了它。这样两个线程写回内存的值其实是一样的。也就是说，两个线程同时抓取内存资源时若无一定先后顺序，会造成资源竞争。

为了避免上述这种情况，当两段代码同时运行会影响计算结果的正确性时，我们就需要将这两段代码分开运行，这就是 互斥（mutual exclusion） 。我们将同时只能有一个线程执行的一段代码称为 临界区（critical section） 。那么我们如何才能判断两个线程是否能够同时运行还产生正确结果呢？我们可以分两种情况考虑——在上面的例子中，产生错误的主要原因是两个线程在同时修改一个变量，因此它们必然会相互影响；另一种情况是，一个线程引用了已经被另一个线程修改的变量。这两种情况共同构成了 Bernstein 条件：假设我们有两个线程 A， B； RA 和 RB 分别是它们运行过程中引用的全部变量，WA 和 WB
​分别是他们运行过程中修改的全部变量，那么只要它们满足下面三个条件，它们就不会在并发执行时影响彼此运行结果的正确性：

• RA∩WB=∅
• RB∩WA=∅
• WA∩WB =∅
  满足 Bernstein 条件的两个线程不会相互影响，因此我们无需考虑它们的运行顺序如何。但对于不满足 Bernstein 条件的两个线程，我们就必须设计一些机制使它们能够安全地同时运行。接下来我们就来讲解一下这些机制。

资源竞争出现的条件，这一节中我们就来介绍一下解决资源竞争的方法。在讲解这一部分内容时，教授经常使用的一个例子就是牛奶过量问题（Too Much Milk）。
假设你和你妈每天早晨都要喝牛奶，有一天你回家发现冰箱里没有牛奶了，于是你出去买牛奶；等你回到家、打开冰箱，却发现已经有一盒牛奶了，因为你妈妈不知道你去买牛奶了，所以也去买了一盒牛奶。这样有了两盒牛奶，你们就不一定能在牛奶过期以前把它们全部喝完了。我们可以把买牛奶这一行为看做临界区，它必须遵守由 Dijkstra 提出的临界区调度的三个原则：

  1. 一次只有一个线程执行临界区的指令；   
  2. 如果一个线程已经在执行临界区指令则其它线程必须等待；   
  4. 一个等待中的线程在有限的等待时间后会进入临界区；
     前两条原则保证了线程的安全性，第三条保证了程
     序运行的活性（即，程序不会在某个指令永远的卡住）。

为了实现上面三条原则，我们需要一种通知另一个线程的办法；现实生活中我们可以在冰箱上留一个便签，写上“我去买牛奶了”，对方就不会再买牛奶了，我们可以尝试把这个过程写成代码：

int note = 0;
int milk = 0;
if(!milk) {   	   //A 
	if(!note){     // B 
		note  = 1  // C
		milk ++;   //D
		note = 0;  // E 
	}
}

现在加入我们有两个线程执行这段代码，会不会出现问题呢？让我们将这两个线程命名为 1，2；我们用数字角标表示这个指令是由哪个线程执行的，那么下面这个指令序列就会给我们造成问题：
A1， B1， A2， B2， C1， D1，E1， C2， D2
​， E2。
两个线程分别判断没有牛奶也没有字条以后分别进入了买牛奶的过程，这样尽管我们有了字条，还是买了两盒牛奶，违反了第一条原则。这里我们面临的主要问题是人的行为是连续的，所以我们不会在发现没有纸条之后离开一段时间再去留下纸条、买牛奶（当然，如果你非要这么干那也没有办法），但线程可能在任何指令处被系统调度器打断，所以我们不能保证上面这段代码在两个线程中运行的结果。

怎样才能解决上面提到的问题呢？上面的问题似乎主要来源于一点，就是我们先检查了note的值、后将note值设为 \ 1 1。如果在这两个指令之间另一个线程查看了note的值就不会知道我们已经决定去买牛奶了。因此我们可以先写字条，然后再查看对方是否已经留下字条来决定我们是否去买牛奶：

int note1 = 1; //线程2会把这一行替换为 note2 = 1;
               //并把下面的 if 判断换为判断 note1 是否为 1
if (!milk) {
    if (!note2) {
        milk++;
    }
}
note1 = 0;

很可惜，这种方法会违反第三条原则，因为如果线程 1 和线程 2 分别检查发现没有牛奶，然后分别发现对方已经留下字条，那么就没有人会去买牛奶了。我们希望如果两个线程中有一个在发现对方已经留下字条后再等待一会儿，之后重新查看冰箱里是否有牛奶。这就给了我们下面这种解决方法：
线程 1 执行的代码与前面差别不大：

int note1 = 1;
if (!milk) {
    if (!note2) {
        milk++;
    }
}
note1 = 0;

线程 2 执行的代码却与前面的有一定的差别：

int note2 = 1;
while (note1){
    ;
}
if (!milk) {
    milk++;
}
note2 = 0;

这段代码可以确保在没有牛奶的情况下，有且只有一个人回去买牛奶。如果你不信的话我们可以来分析一下这两个线程的运行过程。假如线程 1 先开始运行，那么线程 1 就会先将note1设为 1，之后分为两种情况，如果线程 2 在线程 1 买牛奶以前就开始运行，那么note2也会被设为 1，然后线程 2 就会卡在 while loop 中，直到系统调度使得线程 1 继续运行，线程 1 发现note2为 1，就不会买牛奶，而直接将note1设为0，这时线程 2 就可以继续运行，去买牛奶。另一种情况是，线程 2 在线程 1 买完牛奶后再进入系统，那么它就会直接跳过 while loop，发现已经有牛奶，就会拿走字条。最后一种情况是，线程 2 先进入系统，那它就会直接去买牛奶，这时线程 1 如果进入发现有牛奶或有字条就会直接拿走字条。因此我们可以保证有且只有一个人会买牛奶。
这种算法实际上就是 Peterson 算法.
从上面这个例子中我们可以看出，在并发多线程中实现互斥是比较复杂的。我们上面提到的方法虽然确实保证了中间的临界区只有一段代码运行，但它只适用于 2 个线程，如果我们想将它推广到多个进程那么问题就会更加复杂，而且如果我们想用两个线程执行同一段代码，那么上面代码中的note1，note2就不适用了，因为运行中的线程不会知道自己是 1 还是 2。接下来的章节我们会介绍两种更为简便实用的概念：锁和条件变量。

锁

为了实现互斥，我们需要简便的方法来判定一个线程是否有权利执行一段临界区的代码。锁就是这样一种方法：为了防止你妈妈和你同时去买牛奶，你可以在去买牛奶以前给冰箱上个锁，这样你妈妈看到冰箱已经上锁就知道，你一定已经去买牛奶了。在程序中，锁也是这样一种存在——我们为保护一些共享的数据而建立一个锁，每次修改这些数据以前都先试图获得锁，成功获得锁后再进入临界区修改数据。

在这里我们需要强调一点：锁是用来锁住数据的，而不是用来锁住代码的。你的每个锁一定会有它保护的共享数据，所有调用和修改该数据的操作都会被锁保护。如果你发现自己想不明白自己写的代码中的锁在保护哪些数据，那么你可能需要重新设计锁了。

锁最常用的地方是在一个共享的对象中。虽然 C 不是一门面向对象的语言，但我们仍然可以用它来实现面向对象的思想：现在就让我们来用一个面向对象的例子来带你认识锁的应用。假设我们已经实现了一个锁struct lock和用来获得锁、解锁的函数void lock_acquire(struct lock *my_lock);和void lock_unlock(struct lock *my_lock);：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct word{
    struct lock *word_lock;
    char *word;
    int count;
}

int count_word(struct word *my_word){
    lock_acquire(my_word->word_lock);
    my_word->count += 1;
    lock_unlock(my_word->word_lock);
    return 0;
}

int modify_word(struct word *my_word, char *new_word){
    lock_acquire(my_word->word_lock);
    my_word->word = realloc(my_word->word, (strlen(new_word)+1)*sizeof(char));
    strcpy(my_word->word, new_word);
    lock_unlock(my_word->word_lock);
    return 0;
}

struct word中的word_lock保护了struct word中的两个成员，word和count，在我们需要修改这两个变量时，我们都必须先获得锁，然后再修改其中的值。

锁的用法是比较好理解的，现在我们需要考虑的是如何实现一个这样的锁。

你可能很容易就能想到上一节中买牛奶的例子：如果我们用一个位表示目前锁是否被持有， 0 表示空闲， 1 表示被持有，那我们就可以在发现这一位为 0 时将其设为 1，成功获得锁。但这样有一个问题：如果在一个线程检查这一位为 0 后立刻被内核中断、切换至下一个线程，下一个线程查看这一位为 0，获得了锁，执行临界区代码至一半，又被切换回原来的线程，原来的线程也认为锁是空闲的，因此将其设为1，获得锁后运行临界区。这样我们就有两个线程同时执行临界区代码，锁就形同虚设了。

为了避免上面提到的这种问题，我们希望读取和设置值能成为一个不可分割的操作，这样就没有第二个进程可以插进这两个操作之间了。这就是 测试并设置指令（Test and Set） 。这一指令由硬件提供，它会读取一个内存位置的值，然后将 1 存入这个位置。这样，如果我们将一个整数设为 0，然后在试图获得锁时用 Test and Set 将它设为 1，在返回值为 0 时成功获得锁，并在解锁时将这个值重新设为0，这个整数就可以成为一个锁。

struct lock{
    int value;
}

void lock_acquire(struct lock *my_lock){
    while (test_and_set(&my_lock->value))
        ;
    return;
}

void lock_unlock(struct lock *my_lock){
    my_lock->value = 0;
    return;
}

上面是一种实现锁的方法；由于不能获得锁的线程会在 while loop 中不断循环，这种实现方法被很形象地称为 自旋锁（Spinlock） 。这种方法有一个显而易见的缺点，那就是它的效率很低，假设一个线程企图获得一个另一个线程已经持有的锁时，它会不断循环，浪费处理器时间。因此，自旋锁只适用于已知单个线程持有锁时间很短的情况。
​为了解决上面提到的效率低的问题，我们可以把未能成功获得锁的线程加入到这个锁的等待名单上，在持有锁的线程解锁时再选择一个线程获得锁。为了实现这一功能，我们就需要使用下面的章节中我们要讲到的条件变量。