引言#
本章导读#
到本章开始之前，我们已经完成了组成应用程序执行环境的操作系统的三个重要抽象：进程、地址空间和文件，让应用程序开发、运行和存储数据更加方便和灵活。特别是操作系统通过硬件中断机制，支持分时多任务和抢占式调度机制。这样操作系统能强制打断进程的执行，及时处理I/O交互操作，从而提高整个系统的执行效率。有了进程以后，可以让操作系统从宏观层面实现多个应用的 并发执行 ，而并发是通过操作系统不断地切换进程来达到的。
对于单核处理器而言，在任意一个时刻只会有一个进程被操作系统调度，从而在处理器上执行。到目前为止的并发，仅仅是进程间的并发，而对于一个进程内部，还没有并发性的体现。而这就是线程（Thread）出现的起因：提高一个进程内的并发性。
注解
Dijkstra 教授团队设计解决并发问题的THE操作系统
早期的计算机硬件没有内存隔离保护机制，多个程序以任务（task）的形式进行执行，但各个任务之间是依次执行（批处理方式）或相互独立执行，基本没有数据共享的情况，所以还没有形成线程的概念。当多个任务需要共享数据和同步行为时，就需要扩展任务针对共享数据的执行特征，并建立相应的同步互斥机制。
在1962年，荷兰的E.W.Dijkstra 教授和他的团队正在为 Electrologica X8 计算机设计开发了 THE 操作系统 。他们观察到如果多个程序在执行中访问共享变量，可能会产生冲突和结果不确定。在E.W.Dijkstra 教授在信号量机制的研究中，提出了多个“sequential processes”可以通过信号量机制合作访问共享变量，避免冲突导致结果不确定。这里的“sequential processes”的含义就是后续的线程。
Dijkstra 教授设计出信号量机制
Dijkstra 教授带领他的小团队在设计开发THE操作系统的过程中，异步中断触发的难以重现的并发错误，让他们在调试操作系统中碰到了困难。这种困难激发了Dijkstra团队的灵感，他们设计了操作系统的分层结构来避免操作系统的复杂性负担，同时还设计了信号量机制和对应的P和V操作，来确保线程对共享变量的灵活互斥访问，并支持线程之间的同步操作。P和V是来自荷兰语单词“测试”和“增加”的首字母，是很罕见的非英语来源的操作系统术语。
贝尔实验室Victor A. Vyssotsky提出线程（thead）概念
1964年开始设计的Multics操作系统已经有进程的概念，也有多处理器并行处理的GE 645硬件设计，甚至提出了线程（ thead ）的概念。1966年，参与Multics开发的MIT博士生 Jerome Howard Saltzer在其博士毕业论文的一个注脚提到贝尔实验室的Victor A. Vyssotsky用 thread 这个名称来表示处理器（processor）执行程序（program）代码序列这个过程的抽象概念，Saltzer进一步把”进程（process）”描述为处理器执行程序代码的当前状态（即线程）和可访问的地址空间。但他们并没有建立类似信号量这样的有效机制来避免并发带来的同步互斥问题。
Brinch Hansen、Tony Hoare和Dijkstra提出管程机制
丹麦的Brinch Hansen，英国的Tony Hoare和Dijkstra并不满足于信号量来解决操作系统和应用中的并发问题。因为对于复杂一些的同步互斥问题（如哲学家问题），如果使用信号量机制不小心，容易引起死锁等错误。在 1971年的研讨会上，他们三人开始讨论管程（Monitor）的想法，希望设计一种更高级的并发管理语言结构，便于程序员开发并发程序。在1972年春天，Brinch Hansen 在他写的“操作系统原理”教科书中，提出了管程的概念，并把这一概念嵌入到了Concurrent Pascal 编程语言中，然后他和他的学生再接再厉，在PDP 11/45计算机上编写了Concurrent Pascal 编译器，并用Concurrent Pascal 编写了Solo操作系统。Brinch Hansen在操作系统和语言级并发处理方面的开创性工作影响了后续的操作系统并发处理机制（如条件变量等）和不少的编程语言并发方案。
Brinch Hansen的两句名言：
写作是对简单性的严格测试：不可能令人信服地写出无法理解的想法。
编程是用清晰的散文写文章并使它们可执行的艺术
有了进程以后，为什么还会出现线程（Thread）呢？提高整个系统的并行/并发执行效率是主要的原因。考虑如下情况，对于很多应用（以单一进程的形式运行）而言，逻辑上由多个可并行执行的任务组成，如果其中一个任务被阻塞，将导致整个进程被阻塞，这意味着不依赖该任务的其他任务也被阻塞，然而它们实际上本不应该受到影响。这就降低了系统的并发执行效率。
举个具体的例子，我们平常用编辑器来编辑文本内容的时候，都会有一个定时自动保存的功能，即把当前文档内容保存到磁盘上。假设磁盘性能导致编辑器自动保存的过程较慢，并影响到整个进程被阻塞，这就会影响到用户编辑文档的人机交互体验：即用户只有等到磁盘写入操作完成后，操作系统重新调度该进程运行，用户才可继续编辑文档。
如果我们把一个进程内的多个可并行执行的任务通过一种更细粒度的方式让操作系统进行调度，那么就可以在进程内实现并发执行。在上面的例子中，负责保存文档内容的任务与负责编辑文档的任务可以并发执行，不会出现一个被阻塞的任务导致其它任务都阻塞的情况。这种任务就是一种更细粒度的调度对象，也就是我们这里说的线程。
线程定义#
简单地说，线程是进程的组成部分，进程可包含1 – n个线程，属于同一个进程的线程共享进程的资源，比如地址空间，打开的文件等。线程基本上由线程ID、执行状态、当前指令指针(PC)、寄存器集合和栈组成。线程是可以被操作系统或用户态调度器独立调度（Scheduling）和分派（Dispatch）的基本单位。
在本章之前，进程是程序的基本执行实体，是程序关于某数据集合上的一次运行活动，是系统进行资源（处理器，地址空间和文件等）分配和调度的基本单位。在有了线程后，对进程的定义也要调整了，进程是线程的资源容器，线程成为了程序的基本执行实体。
提示
线程与进程的区别
下面的比较是以线程为调度对象的操作系统作为分析对象：
进程间相互独立（即资源隔离），同一进程的各线程间共享进程的资源（即资源共享）；
子进程和父进程有不同的地址空间和资源，而多个线程（没有父子关系）则共享同一所属进程的地址空间和资源；
每个线程有其自己的执行上下文（线程ID、程序计数器、寄存器集合和执行栈），而进程的执行上下文包括其管理的所有线程的执行上下文和地址空间（故同一进程下的线程间上下文切换比进程间上下文切换要快）；
线程是一个可调度/分派/执行的实体（线程有就绪、阻塞和运行三种基本执行状态），进程不是可调度/分派/执行的的实体，而是线程的资源容器；
进程间通信需要通过IPC机制（如管道等）， 属于同一进程的线程间可以共享“即直接读写”进程的数据，但需要同步互斥机制的辅助，以保证数据的一致性。
同步互斥#
在上面提到了同步互斥和数据一致性，它们的含义是什么呢？ 当多个线程共享同一进程的地址空间时，每个线程都可以访问属于这个进程的数据（全局变量）。如果每个线程使用到的变量都是其他线程不会读取或者修改的话，那么就不存在一致性问题。如果变量是只读的，多个线程读取该变量也不会有一致性问题。但是，当一个线程修改变量时，其他线程在读取这个变量时，可能会看到一个不一致的值。甚至其他线程可能同时尝试修改变量。这就是数据不一致性的问题。
注解
线程的数据一致性
线程的数据一致性的定义：在单处理器（即只有一个核的CPU）下，如果某线程更新了一个可被其他线程读到的共享数据，那么后续其他线程都能读到这个最新被更新的共享数据。
为什么会出现线程的数据不一致问题呢？其根本原因是 调度的不可控性 ：即读写共享变量的代码片段会随时可能被操作系统调度和切换。先看看如下的伪代码例子：
1//全局共享变量 NUM初始化为 0
2static mut NUM : usize = 0;
3...
4
5//主进程中的所有线程都会执行如下的核心代码
6unsafe { NUM = NUM + 1; }
7...
8
9
10//所有线程执行完毕后，主进程显示num的值
11unsafe {
12 println!("NUM = {:?}", NUM);
13}
如果线程的个数为 n ，那么最后主进程会显示的数应该是多少呢？ 也许同学觉得应该也是 n ，但现实并不是这样。为了了解事实真相，我们首先必须了解Rust编译器对 num = num + 1; 这一行源代码生成的汇编代码序列。
1# 假设NUM的地址为 0x1000
2# unsafe { NUM = NUM + 1; } 对应的汇编代码如下
3addi x6, x0, 0x1000 # addr 100: 计算NUM的地址
4 # 由于时钟中断可能会发生线程切换
5ld x5, 0(x6) # addr 104: 把NUM的值加载到x5寄存器中
6 # 由于时钟中断可能会发生线程切换
7addi x5, x5, 1 # addr 108: x5 <- x5 + 1
8 # 由于时钟中断可能会发生线程切换
9sd x5, 0(x6) # addr 112: 把NUM+1的值写回到NUM地址中
在这个例子中，一行Rust源代码其实被Rust编译器生成了四行RISC-V汇编代码。如果多个线程在操作系统的管理和调度下都执行这段代码，那么在上述四行汇编代码之间（即第4，6，8行的地方）的时刻可能产生时钟中断，并导致线程调度和切换。
设有两个线程，线程A先进入上述汇编代码区，将要把 NUM 增加一，为此线程A将 NUM 的值（假设它这时是 0 ）加载到 x5 寄存器中，然后执行加一操作，此时 x5 = 1 。这时时钟中断发生，操作系统将当前正在运行的线程A的上下文（它的程序计数器、寄存器，包括 x5 等）保存到线程控制块（在内存中）中。
再接下来，线程B被选中运行，并进入同一段代码。它也执行了前两条指令，获取 NUM 的值（此时仍为 0 ）并将其放入 x5 中，线程B继续执行接下来指令，将 x5 加一，然后将 x5 的内容保存到 NUM （地址 0x1000 ）中。因此，全局变量 NUM 现在的值是 1 。
最后又发生一次线程上下文切换，线程A恢复运行，此时的 x5=1，现在线程A准备执行最后一条 sd 指令，将 x5 的内容保存到 NUM （地址 0x1000 ）中，NUM 再次被设置为 1 。
简单总结，这两个线程执行的结果是：增加 NUM 的代码被执行两次，初始值为 0 ，但是结果为 1 。而我们一般理解这两个线程执行的“正确”结果应该是全局变量 NUM 等于 2 。
注解
并发相关术语
共享资源（shared resource）：不同的线程/进程都能访问的变量或数据结构。
临界区（critical section）：访问共享资源的一段代码。
竞态条件（race condition）：多个线程/进程都进入临界区时，都试图更新共享的数据结构，导致产生了不期望的结果。
不确定性（indeterminate）： 多个线程/进程在执行过程中出现了竞态条件，导致执行结果取决于哪些线程在何时运行，即执行结果不确定，而开发者期望得到的是确定的结果。
互斥（mutual exclusion）：一种操作原语，能保证同一时间只有一个线程进入临界区，从而避免出现竞态，并产生确定的执行结果。
原子性（atomic）：一系列操作要么全部完成，要么一个都没执行，不会看到中间状态。在数据库领域，具有原子性的一系列操作称为事务（transaction）。
同步（synchronization）：多个并发执行的进程/线程在一些关键点上需要互相等待，这种相互制约的等待称为进程/线程同步。
死锁（dead lock）：一个线程/进程集合里面的每个线程/进程都在等待只能由这个集合中的其他一个线程/进程（包括他自身）才能引发的事件，这种情况就是死锁。
饥饿（hungry）：指一个可运行的线程/进程尽管能继续执行，但由于操作系统的调度而被无限期地忽视，导致不能执行的情况。
在后续的章节中，会大量使用上述术语，如果现在还不够理解，没关系，随着后续的一步一步的分析和实验，相信大家能够掌握上述术语的实际含义。
实践体验#
获取本章代码：
$ git clone https://github.com/rcore-os/rCore-Tutorial-v3.git
$ cd rCore-Tutorial-v3
$ git checkout ch8
在 qemu 模拟器上运行本章代码：
$ cd os
$ make run
内核初始化完成之后就会进入shell程序，我们可以体会一下线程的创建和执行过程。在这里我们运行一下本章的测例 threads ：
>> threads
aaa....bbb...ccc...
thread#1 exited with code 1
thread#2 exited with code 2
thread#3 exited with code 3
main thread exited.
Shell: Process 2 exited with code 0
>>
它会有4个线程在执行，等前3个线程执行完毕后，主线程退出，导致整个进程退出。
此外，在本章的操作系统支持通过互斥来执行“哲学家就餐问题”这个应用程序：
>> phil_din_mutex
time cost = 7273
'-' -> THINKING; 'x' -> EATING; ' ' -> WAITING
#0: ------- xxxxxxxx---------- xxxx----- xxxxxx--xxx
#1: ---xxxxxx-- xxxxxxx---------- x---xxxxxx
#2: ----- xx---------xx----xxxxxx------------ xxxx
#3: -----xxxxxxxxxx------xxxxx-------- xxxxxx-- xxxxxxxxx
#4: ------ x------ xxxxxx-- xxxxx------ xx
#0: ------- xxxxxxxx---------- xxxx----- xxxxxx--xxx
>>
我们可以看到5个代表“哲学家”的线程通过操作系统的 信号量 互斥机制在进行“THINKING”、“EATING”、“WAITING”的日常生活。没有哲学家由于拿不到筷子而饥饿，也没有相邻的两个哲学家同时拿到同一个筷子。
注解
哲学家就餐问题
计算机科学家Dijkstra提出并解决的哲学家就餐问题是经典的进程同步互斥问题。哲学家就餐问题描述如下：
有5个哲学家共用一张圆桌，分别坐在周围的5张椅子上，在圆桌上有5个碗和5只筷子，他们的生活方式是交替地进行思考和进餐。平时，每个哲学家进行思考，饥饿时便试图拿起其左右最靠近他的筷子，只有在他拿到两只筷子时才能进餐。进餐完毕，放下筷子继续思考。
本章代码树#
1 .
2 ├── bootloader
3 │ └── rustsbi-qemu.bin
4 ├── dev-env-info.md
5 ├── Dockerfile
6 ├── easy-fs
7 │ ├── Cargo.lock
8 │ ├── Cargo.toml
9 │ └── src
10 │ ├── bitmap.rs
11 │ ├── block_cache.rs
12 │ ├── block_dev.rs
13 │ ├── efs.rs
14 │ ├── layout.rs
15 │ ├── lib.rs
16 │ └── vfs.rs
17 ├── easy-fs-fuse
18 │ ├── Cargo.lock
19 │ ├── Cargo.toml
20 │ └── src
21 │ └── main.rs
22 ├── LICENSE
23 ├── Makefile
24 ├── os
25 │ ├── build.rs
26 │ ├── Cargo.lock
27 │ ├── Cargo.toml
28 │ ├── last-qemu
29 │ ├── Makefile
30 │ └── src
31 │ ├── config.rs
32 │ ├── console.rs
33 │ ├── drivers
34 │ │ ├── block
35 │ │ │ ├── mod.rs
36 │ │ │ ├── sdcard.rs
37 │ │ │ └── virtio_blk.rs
38 │ │ └── mod.rs
39 │ ├── entry.asm
40 │ ├── fs
41 │ │ ├── inode.rs
42 │ │ ├── mod.rs
43 │ │ ├── pipe.rs
44 │ │ └── stdio.rs
45 │ ├── lang_items.rs
46 │ ├── link_app.S
47 │ ├── linker-qemu.ld
48 │ ├── loader.rs
49 │ ├── main.rs
50 │ ├── mm
51 │ │ ├── address.rs
52 │ │ ├── frame_allocator.rs
53 │ │ ├── heap_allocator.rs
54 │ │ ├── memory_set.rs
55 │ │ ├── mod.rs
56 │ │ └── page_table.rs
57 │ ├── sbi.rs
58 │ ├── sync
59 │ │ ├── mod.rs
60 │ │ ├── mutex.rs
61 │ │ ├── semaphore.rs
62 │ │ └── up.rs
63 │ ├── syscall
64 │ │ ├── fs.rs
65 │ │ ├── mod.rs
66 │ │ ├── process.rs
67 │ │ ├── sync.rs
68 │ │ └── thread.rs
69 │ ├── task
70 │ │ ├── context.rs
71 │ │ ├── id.rs
72 │ │ ├── manager.rs
73 │ │ ├── mod.rs
74 │ │ ├── processor.rs
75 │ │ ├── process.rs
76 │ │ ├── switch.rs
77 │ │ ├── switch.S
78 │ │ └── task.rs
79 │ ├── timer.rs
80 │ └── trap
81 │ ├── context.rs
82 │ ├── mod.rs
83 │ └── trap.S
84 ├── pushall.sh
85 ├── README.md
86 ├── rust-toolchain
87 └── user
88 ├── Cargo.lock
89 ├── Cargo.toml
90 ├── Makefile
91 └── src
92 ├── bin
93 │ ├── cat.rs
94 │ ├── cmdline_args.rs
95 │ ├── exit.rs
96 │ ├── fantastic_text.rs
97 │ ├── filetest_simple.rs
98 │ ├── forktest2.rs
99 │ ├── forktest.rs
100 │ ├── forktest_simple.rs
101 │ ├── forktree.rs
102 │ ├── hello_world.rs
103 │ ├── huge_write.rs
104 │ ├── initproc.rs
105 │ ├── matrix.rs
106 │ ├── mpsc_sem.rs
107 │ ├── phil_din_mutex.rs
108 │ ├── pipe_large_test.rs
109 │ ├── pipetest.rs
110 │ ├── race_adder_atomic.rs
111 │ ├── race_adder_loop.rs
112 │ ├── race_adder_mutex_blocking.rs
113 │ ├── race_adder_mutex_spin.rs
114 │ ├── race_adder.rs
115 │ ├── run_pipe_test.rs
116 │ ├── sleep.rs
117 │ ├── sleep_simple.rs
118 │ ├── stack_overflow.rs
119 │ ├── threads_arg.rs
120 │ ├── threads.rs
121 │ ├── user_shell.rs
122 │ ├── usertests.rs
123 │ └── yield.rs
124 ├── console.rs
125 ├── lang_items.rs
126 ├── lib.rs
127 ├── linker.ld
128 └── syscall.rs