26. Concurrency: An Introduction

在前面很长的部分里我们讨论了虚拟化的问题，主要是对CPU和内存的虚拟化。在接下来的部分里，我们将学习一个进程（process）的抽象，那就是线程（thread）。一个进程可以包含多个线程，也是就multi-thread program，每个线程像一个单独的进程，但是区别在于同一进程的线程之间共享地址空间，因此可以访问相同的数据。
线程和进程十分相似。线程有自己的PC来表明当前指令的地址；线程有自己的寄存器用来做计算；因此如果有两个线程在一个处理器上运行，就会面临context switch的问题。对于进程来说，context switch时将进程信息保存在process control block（PCB）中；而对于线程来说，context switch时将线程信息保存在thread control block（TCB）中。但是有一点不同，对于线程来说，context switch时并不会改变地址空间，也就是说使用的page table不需要改变。
线程和进程的另一个区别在于stack。在之前的进程中（现在叫single-thread process），只有一个stack；但是在multi-thread process中，每一个线程都对应一个stack。

26.1 Why Use Threads?

如题，为何要使用线程？
第一，并行性。假设有一个很大的数组，现在要把数组的每一个元素都加1。在single-thread的程序中，就只能按部就班地从头做到尾。但是现在如果有了multi-thread程序，并且有多核CPU，就可以让每个CPU运行一个线程，每个线程完成一部分任务，提高了并行性。
第二，避免由于I/O而block程序。假设一个程序中需要发起不同的I/O请求，对于single-thread的进程来说，发起I/O请求就会被block，但是如果想在发起I/O请求后还做一些事情，比如计算或者是提出别的I/O请求应该怎么办？在multi-thread进程中，可以让一个线程来发起I/O请求，其他线程继续运行，也就是说block的是发起I/O的那个线程而不是整个儿进程。

Pthread_create用于创建一个新的线程并完成一些事情。具体来说，第17行，创建p1线程，完成mythread函数，参数是“A”。

Pthread_join用于等待某一个线程结束。具体来说。第20行，等待p1线程运行结束。

对于上述代码，有着多种不同的执行顺序：

可以看到，线程让事情变得更复杂，到底让哪个线程上CPU运行？计算机如果没有concurrency，就无法回答这个问题。但是有了concurrency，就变得更worse。

正如上面这个栗子，在所有代码都执行完后，我们期待最终counter的结果是2e7：

但事实并非如此。实际运行后的结果：

再运行一次康康？

可以看到每次的结果都不一样，也就是说结果是不确定的。

上述问题到底是什么原因导致的？为了搞清楚这个问题，就必须从汇编语言的层面来康康在更新counter时到底发生了什么。实际上，在对counter更新时执行了一下三条汇编指令：

第一条是将0x8049a1c地址中的值取出，保存到eax寄存器；

第二条是对eax寄存器中的值做加1；

第三条是将eax寄存器中的值保存到0x8049a1c地址。

问题的本质就在于，一个线程执行这三条指令时并不是原子的，如下图：

解释一下几个术语：

当超过两个线程在共享数据并且试图同时修改一个数据时，这种现象叫做race condition（或者data race）。

当发生race condition的时候，把修改数据的那段代码叫做critical section。

我们期望的结果是mutual exclusion，也就是说在执行critical section的代码时，其他的线程不能执行这段代码。

想要解决上面这个问题，就必须实现原子性。也就是说对于更新counter的三条汇编指令，要么全部执行，要么全不执行。所以我们又需要硬件的帮助了，可以基于硬件提供的指令，可以构建一套指令叫做synchronization primitives。有了硬件的帮助，再加上OS就可以多线程同步地访问critical section，保证顺序可控。这一部分会在这个章节的后面继续讲解。