# Concurrency: Processes & Threads

以下是 CS162 课程的整体结构：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_L4SdNUZxx_R1FaNGP%2F-L_KrSTn-vM2jqXC5GgF%2FScreen%20Shot%202019-03-07%20at%209.56.28%20AM.jpg?alt=media\&token=09c17263-0cce-425c-a9bf-10f7d2218e8e)

前面几节课完成了 intro 和 OS Concepts 两部分，本节将进入 Concurrency 的第一个话题：Processes & Threads

## Traditional UNIX Process

传统的 UNIX Process 通常称为 "HeavyWeight Process"，在 Process 内部不存在并发。它主要由两个部分构成：

* 顺序执行的程序
* 被保护的资源
  * Main memory state (contents of address space)
  * I/O state (i.e. file descriptors)

每个 Process 的运行状态被保存在 Process Control Block（PCB）中，PCB 中始终保存着 Process 的一个快照，包括它的执行环境和被保护的资源。在 OS 调度的过程中，始终只有 1 个 PCB 处于活跃状态，OS 的职责就是在分配 CPU 和 Non-CPU 资源的过程中尽量实现公平与效率。

OS 切换 Processes 的过程，被称为 context switch，下图所示的是 OS 在两个 Processes 之间切换的过程：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_L4SdNUZxx_R1FaNGP%2F-L_KxKHfecji1O-PWgHs%2FScreen%20Shot%202019-03-07%20at%2010.22.08%20AM.jpg?alt=media\&token=3b88aa16-5ecc-4f45-917b-2513a3466cd7)

切换的过程需要 save P0 state、reload P1 state，会带来开销。

### Lifecycle of a Traditional Process

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_L4SdNUZxx_R1FaNGP%2F-L_KxoRKc58VNs_Osq3l%2FScreen%20Shot%202019-03-07%20at%2010.24.15%20AM.jpg?alt=media\&token=4d64e6a9-3e6d-4afa-919a-b955c8369c67)

Process 的生命周期包括以下几种状态：

* New：新创建的 Process
* Ready：Process 准备完毕，等待 CPU 资源，随时可以执行
* Running：执行中
* Waiting：等待其它事件的发生，如 I/O
* Terminated：Process 完成执行，保存执行返回值，等待 parent process 回收

### Traditional Process Scheduling

在 kernel 中维护者若干个 queues，如下图所示：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_L4SdNUZxx_R1FaNGP%2F-L_KylzKt9UB49Sm4tK9%2FScreen%20Shot%202019-03-07%20at%2010.28.27%20AM.jpg?alt=media\&token=a0785982-6fc2-4568-9f91-3122bf976b4f)

PCBs 状态的改变就是从一个 queue 移动到另一个 queue 的过程，如：

* ready queue => CPU：ready => running
* CPU => I/O queue：running => waiting
* I/O => ready queue：waiting => ready

实际上 I/O queue 还可以继续细分为 USB Unit 0、Disk Unit 0、Disk Unit 2、Ethernet 0 等等各种 queues。

## Modern Process With Threads

将 Process 的执行抽象成一个新的概念，即 thread，且 Process 中能有多个 threads 共存：

* Thread：在 Process 中的单个顺序执行的命令流，不可再分
  * Thread 使用 Process 的 Address Space
  * Threads 之间不存在隔离保护，因为它们共用 Address Space，且它们可以修改 Process 中的共享信息
* Multithreading：一个 Process 中有多个 Threads 并发执行，完成各自的工作

如下图所示：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_L4SdNUZxx_R1FaNGP%2F-L_L1LYt3sdFzVtb2vys%2FScreen%20Shot%202019-03-07%20at%2010.44.03%20AM.jpg?alt=media\&token=9e85c713-98ba-4ec8-aace-dd105db2653a)

* Thread 是并发的最小单元
* Address spaces 是保护的最小单元

### Thread State

Thread state 主要包括 2 部分：

* State shared by all threads in process/address space
  * Content of memory
  * I/O State (file descriptors, network connections, etc)
* State "private" to each thread
  * TCB
  * CPU registers
  * Execution stack（具体可以翻阅 CS107 相关课程，介绍地很透彻）
    * Parameters, temporary variables
    * Return PCs are kept while called procedures are executing

### Motivational Example for Threads

想象如下程序：

```c
main() {
  ComputePI("pi.txt");
  PrintClassList("clist.text");
}
```

由于计算 pi 的过程不会结束，PrintClassList 永远不会被执行，利用 Threads 修改程序：

```c
main() {
  ThreadFork(ComputePI("pi.txt"));
  ThreadFork(PrintClassList("clist.text"));
}
```

这样两个 Threads 就可以并发执行，而这时候 Process 的 memory footprint 如下图所示：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_L4SdNUZxx_R1FaNGP%2F-L_L758ziG2kD7MjrRgz%2FScreen%20Shot%202019-03-07%20at%2011.09.09%20AM.jpg?alt=media\&token=fba36584-16a0-48d3-b384-2a23e73ea45d)

此时在 Process 中可以看到两套 CPU registers、Execution stacks，但这也会引入新的问题：

* 如何放置两个 stacks 的位置
* stacks 的最大限制怎么定
* 如何检查 stacks 之间发生重叠

这些都是 thread package 需要解决的问题。

### Actual Thread Operations

threads 标准支持的基本操作如下所示：

* thread\_fork(func, args)：创建一个新的 thread，执行 func(args)
* thread\_yield()：主动放弃 CPU 使用权
* thread\_join(thread)：在 parent 中，等待 forked 的 thread 执行结束
* thread\_exit()：关闭 thread 并清理，唤醒等待 join 的 thread

pThreads 是符合 POSIX 标准的 thread package。

### Dispatch Loop

OS 的调度程序：

```c
Loop {
  RunThread();
  ChooseNextThread();
  SaveStateOfCPU(curTCB);
  LoadStateOfCPU(newTCB);
}
```

当 OS 启动时，这个 loop 就会被启动，直到系统关机。

### Running a Thread

Dispatcher 如何运行一个 thread？

* 加载 thread 的状态到 CPU，包括 registers、PC 和 SP
* 加载运行环境 --- virtual memory space
* 跳到 PC 处启动 thread 运行

Dispatcher 如何重新获取控制权？

* Internal events：thread 主动返回控制权
* External events：thread 被剥夺控制权

#### Internal Events

* Blocking on I/O
* Waiting on a "signal" from other thread
* Thread executes a yield()

*yield*

```c
computePI() {
    while (true) {
        ComputeNextDigit();
        yield();
    }
}
```

程序的运行栈如下图所示：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_UqOJXufoRqMkuyVWh%2F-L_UsEDcefF-DGJYlgQM%2FScreen%20Shot%202019-03-09%20at%208.36.03%20AM.jpg?alt=media\&token=30c9b41a-12ef-451e-b830-f89c75a33158)

假设有两个 threads，S 和 T，S yield 之后，dispatcher 将 cpu 控制权交给 T，整个过程如下所示：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_V23MY973_86_Qpym4%2F-L_V2RR_CPzhpSLf85B5%2FScreen%20Shot%202019-03-09%20at%209.25.01%20AM.jpg?alt=media\&token=9a963414-b234-4d6e-8ef7-9a515e7818d9)

有趣的是，当 dispatcher 在 S 的 stack 中执行 switch 之后，返回到了 T 的 stack 中的 switch。

*blocking on I/O*

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_UqOJXufoRqMkuyVWh%2F-L_UudPvLi5drgAn7JXg%2FScreen%20Shot%202019-03-09%20at%208.46.35%20AM.jpg?alt=media\&token=aeca0520-1e22-4a37-b0c4-0b6ca6c7806b)

thread 请求一块数据的过程：

* user code invokes a system call
* read operation is initiated
* run new thread/switch

*与 switch 有关的统计值*

* 每个 10\~100ms 之间就会有一次 switch
* thread switching 操作的时间大约为 3-4 μs，比 process switching 快约 100 ns
* 跨核 switching 大约花费核内 switching 两倍的时间
* context-switching 的时间随着 working set 的大小增大而增大，甚至可以花费原来 100x 以上的时间（这里 working set 指的是 process 一段时间中使用的 memory 大小）

#### External Events

thread 不可能永久占用 CPU 资源，OS 通过外部事件（interrupts）来剥夺 thread 的 CPU 资源。

*Network Interrupt*

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_V23MY973_86_Qpym4%2F-L_V6W2vzf6jXIiGoS9U%2FScreen%20Shot%202019-03-09%20at%209.42.49%20AM.jpg?alt=media\&token=098cff2d-b2bf-439e-9d2b-25ce265e5eb9)

*Timer Interrupt*

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_V23MY973_86_Qpym4%2F-L_V6dNBrVIhz_GXUD1J%2FScreen%20Shot%202019-03-09%20at%209.43.23%20AM.jpg?alt=media\&token=e6393d23-672f-4473-9430-5249a95517f5)

一些 interrupts 的工作逻辑可以概括为：

```c
TimerInterrupt() {
    DoPeriodHouseKeeping();
    run_new_thread();
}

IOInterrupt() {
    ServiceIO();
    run_new_thread();
}

// ...
```

#### How does Thread get started?

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_V23MY973_86_Qpym4%2F-L_V8MTiFt3EkaqmaqgI%2FScreen%20Shot%202019-03-09%20at%209.50.54%20AM.jpg?alt=media\&token=2d28cd6d-0f80-480f-a3c8-395659e8f3b6)

run\_new\_thread 后 dispatcher switch 到 ThreadRoot 中，后者是 thread 执行的起点：

```c
ThreadRoot() {
    DoStartupHousekeeping();
    UserModeSwitch();
    Call fcnPtr(fcnArgPtr);
    ThreadFinish();
}
```

注意：本节插图中的 stack，蓝色表示 user stack，红色表示 kernel stack，二者逻辑上是两个不同的被保护的区域，请勿认为二者是连续的。

### Thread Abstraction

在 thread 看来：

*计算机中有无限个 CPU*

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_UqOJXufoRqMkuyVWh%2F-L_Ux3PK2_VP8C6N5xrS%2FScreen%20Shot%202019-03-09%20at%208.57.10%20AM.jpg?alt=media\&token=90c629d8-ffe3-4843-8e10-a3d9013d4f31)

*threads 的执行速度不能保证，因此程序的设计不应该依赖于 scheduler 调度的方式*

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_UqOJXufoRqMkuyVWh%2F-L_UxLauRKD4L-bMHJ3q%2FScreen%20Shot%202019-03-09%20at%208.58.22%20AM.jpg?alt=media\&token=e3f2d973-478f-4fd6-b38e-c78d7672727a)

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_UqOJXufoRqMkuyVWh%2F-L_UxRCACzco6Qx8YRY2%2FScreen%20Shot%202019-03-09%20at%208.58.46%20AM.jpg?alt=media\&token=575216e0-2dc3-4ad4-853e-75e7cee772e2)

### Thread Lifecycle

与 Process Lifecycle 非常类似：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_UqOJXufoRqMkuyVWh%2F-L_Uxcb2mgHCD2DiKtTN%2FScreen%20Shot%202019-03-09%20at%208.59.38%20AM.jpg?alt=media\&token=1956fa8c-c4d8-4e9f-88af-22bce03a1597)

### Shared vs. Per-Thread State

如下图所示：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_UqOJXufoRqMkuyVWh%2F-L_UxuES29fnlsMrK-Zc%2FScreen%20Shot%202019-03-09%20at%209.00.51%20AM.jpg?alt=media\&token=c7369c31-bf33-4069-a7af-392f047e4bc3)

OS 为每个 thread 建立一个 TCB，里面包含：

* Execution State：CPU registers, program counter (PC), pointer to stack (SP)
* Scheduling Info：state, priority, CPU time
* Various Pointers for implementing scheduling queues
* Pointer to enclosing process (PCB)
* etc

#### Multithreaded Processes

一个 Process 总有一个或多个 threads，对应到 PCB 与 TCB，就是一个 PCB 指向多个 TCBs：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_Wqepi8iylQfiPZctM%2F-L_WrXJBZED6F1bgeHPb%2FScreen%20Shot%202019-03-09%20at%205.52.13%20PM.jpg?alt=media\&token=93885031-b732-4de3-9179-a480a023da0e)

* 在同一个 process 中的 threads 之间做 context switch 开销小
* 在不同 processes 中的 threads 之间做 context switch 则同时需要改变 memory 和 I/O address tables

典型的 multithreaded 程序举例如下：

* Embedded systems
  * Elevators, Planes, Medical systems, Wristwatches
  * Single Program, concurrent operations
* Most modern OS kernels
  * Internally concurrent because have to deal with concurrent requests by multiple users
  * But no protection needed within kernel
* Database Servers
  * Access to shared data by many concurrent users
  * Also background utility processing must be done
* Network Servers
  * Concurrent requests from network
  * Again, single program, multiple concurrent operations
  * File server, Web server, and airline reservation systems
* Parallel Programming/Multiprocessing
  * Split program into multiple threads for parallelism

以 Client/Server 为例：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_Wqepi8iylQfiPZctM%2F-L_WuJgOdUee0HF04T6A%2FScreen%20Shot%202019-03-09%20at%206.04.17%20PM.jpg?alt=media\&token=7367e60f-c75c-4a1a-b1e3-c9482979e3ac)

client/browser：

* 可以同时用多个线程在多个 tabs 中访问同一个网站
* 可以同时利用多个线程下载同一个页面的多个文件，最后渲染结果

web server：

* 为每个 connection 创建 (fork) 一个 process
* 每个 process 利用一个 thread 获取 request，处理并返回 response
* 如果需要其他 I/O 操作，则 fork threads 完成相关工作，join 结果后返回

现实中，许多 processes 都是  multi-threaded 的，因此 thread context switches 即可能发生在 process 内部，也可能发生在 processes 之间：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_Wqepi8iylQfiPZctM%2F-L_Wwctt7E9sdrtTDN29%2FScreen%20Shot%202019-03-09%20at%206.14.28%20PM.jpg?alt=media\&token=dd010f46-2d48-42b5-bae5-e9d37668a9b7)

如图中 Google Chrome process 内部就有 13 个线程。

## Putting it together: Process

### 演变过程

传统的 Unix Process 如下图所示：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_XTi6nLt55I8jUWbgw%2F-L_XLXAXNab-ycRc77ZA%2FScreen%20Shot%202019-03-09%20at%208.07.40%20PM.jpg?alt=media\&token=06a774bc-f068-4ffb-9a8f-88f1b738d6fc)

多个 Processes 并发如下图所示：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_XTi6nLt55I8jUWbgw%2F-L_XLjPnsvp5mkdA6pQ5%2FScreen%20Shot%202019-03-09%20at%208.08.34%20PM.jpg?alt=media\&token=20ab6dbf-65dc-403c-9926-20c08d99b230)

每个 Process 可以有一个到多个 Threads，如下图所示：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_XTi6nLt55I8jUWbgw%2F-L_XM-KxAsDvNqe9k9Lz%2FScreen%20Shot%202019-03-09%20at%208.09.43%20PM.jpg?alt=media\&token=d02fbaa5-784e-4efe-b676-895794544613)

multi-cores

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_XTi6nLt55I8jUWbgw%2F-L_XUvdwQuH9Bqv59O_5%2FScreen%20Shot%202019-03-09%20at%208.48.43%20PM.jpg?alt=media\&token=8955701b-5227-4dab-a300-8535fd01c781)

hyper-threading

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_XTi6nLt55I8jUWbgw%2F-L_XV1iFR3aeE7KQnuOG%2FScreen%20Shot%202019-03-09%20at%208.49.12%20PM.jpg?alt=media\&token=202df152-c401-427e-a09e-72db186b102a)

### Kernel/User Mode Threads

上文中介绍的都是 kernel threads：

* kernel 原生支持的 threads
* 每个 thread 之间相互独立地运行或者暂停
* 一个 process 可能同时包含多个等待不同资源的 threads

kernel threads 的缺点在于，一切与它相关的操作都需要进入到 kernel mode 中，等待 kernel 调度。为了克服这个缺点，又诞生一种更轻量级的 thread，即 user threads：

* 由用户程序提供 threads 的 scheduler 和 package
* 可能存在多个 user threads 对应单个 kernel thread 的情况
* user threads 可以只在 yield 的时候 switch，控制权自定义
* 开销更小

但世上没有免费的午餐，由于多个 user threads 对应单个 kernel thread，一旦 kernel thread 被剥夺 CPU 资源，所有 user threads 就都无法继续运行。当然，对于这一问题也有折衷方案，即 scheduler activations，让 kernel 在 thread blocks 的时候提醒 user level threads 事情即将发生，用户进程可以使用其它 kernel threads 继续运行，此时多个 user threads 对应多个 kernel threads，如下图所示：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_XTi6nLt55I8jUWbgw%2F-L_XQ2XgmV05xDlaToUt%2FScreen%20Shot%202019-03-09%20at%208.27.25%20PM.jpg?alt=media\&token=c346ed90-9551-4821-891d-32612a3a39b2)

* user-level library, single-threaded process：early Java
  * library does thread context switch
  * kernel time slices between processes
* green threads：SunOS, Unix variants
  * user-level library does thread multiplexing
* scheduler activations：Windows
  * kernel allocates processors to user-level library
  * thread library implements context switch
  * system call I/O that blocks triggers up-call
* Linux, MacOS, Windows：use kernel threads
  * system calls for thread fork, join, exit (and lock, unlock ...)
  * kernel does context switching
  * simple, but a lot of transitions between user and kernel mode

### High-level Example：Web Server

没有 thread 的版本：

```c
serverLoop() {
    con = AcceptCon();
    ProcessFork(ServiceWebPage(), con);
}
```

有 thread 的版本：

```c
serverLoop() {
    con = AcceptCon();
    ThreadFork(ServiceWebPage(), connection);
}
```

虽然看起来一样，但有本质的区别：

* 使用 ThreadFork 可以在不同连接之间共享文件、CGI scripts、以及其它信息
* Threads 很便宜，因此降低了 overhead/request

#### Thread Pools

上一个 thread-based web server 仍然存在问题，如果连接太多，threads 的增加没有被限制，容易由于频繁地为短时任务创建、删除 threads 出现性能下降、延迟增加的问题，导致 throughput 下降，因此使用一个有界的 thread pool，来表示最大并发的限制，如下图所示：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_XTi6nLt55I8jUWbgw%2F-L_XYXQN3K6Tn_L7t30e%2FScreen%20Shot%202019-03-09%20at%209.04.29%20PM.jpg?alt=media\&token=3c8113a5-6e8a-4eb0-abb1-983471e4174b)

{% code title="master.c" %}

```c
master() {
    allocThreads(worker, queue);
    while(True) {
        con = AcceptCon();
        Enqueue(queue, con);
        wakeUp(queue);
    }
}
```

{% endcode %}

{% code title="worker.c" %}

```c
worker(queue) {
    while(TRUE) {
        con = Dequeue(queue);
        if (con == null)
            sleepOn(queue);
        else
            ServiceWebPage(con);
    }
}
```

{% endcode %}

## 小结

* Processes have two parts
  * Threads (Concurrency)
  * Address Spaces (Protection)
* Concurrency accomplished by multiplexing CPU Time:
  * Unloading current thread (PC, registers)
  * Loading new thread (PC, registers)
  * Such context switching may be voluntary through yield(), I/O operations, or involuntary from timer and other interrupts
* Protection accomplished restricting access
  * Memory mapping isolates processes from each other
  * dual-mode for isolating I/O, other resources

## 参考

[slides](https://inst.eecs.berkeley.edu/~cs162/sp15/static/lectures/5.pdf), [wikipedia page of thread pool](https://en.wikipedia.org/wiki/Thread_pool), video