乐趣区

并发编程导论

并发编程导论是对于分布式计算 - 并发编程 https://url.wx-coder.cn/Yagu8 系列的总结与归纳。欢迎关注公众号:某熊的技术之路。

并发编程导论

随着硬件性能的迅猛发展与大数据时代的来临,并发编程日益成为编程中不可忽略的重要组成部分。简单定义来看,如果执行单元的逻辑控制流在时间上重叠,那它们就是并发(Concurrent)的。并发编程复兴的主要驱动力来自于所谓的“多核危机”。正如摩尔定律所预言的那样,芯片性能仍在不断提高,但相比加快 CPU 的速度,计算机正在向多核化方向发展。正如 Herb Sutter 所说,“免费午餐的时代已然终结”。为了让代码运行得更快,单纯依靠更快的硬件已无法满足要求,并行和分布式计算是现代应用程序的主要内容,我们需要利用多个核心或多台机器来加速应用程序或大规模运行它们。

并发编程是非常广泛的概念,其向下依赖于操作系统、存储等,与分布式系统、微服务等,而又会具体落地于 Java 并发编程、Go 并发编程、JavaScript 异步编程等领域。云计算承诺在所有维度上(内存、计算、存储等)实现无限的可扩展性,并发编程及其相关理论也是我们构建大规模分布式应用的基础。

本节主要讨论并发编程理论相关的内容,可以参阅 [Java 并发编程 https://url.wx-coder.cn/72vCj、Go 并发编程 https://url.wx-coder.cn/FO9EX 等了解具体编程语言中并发编程的实践,可以参阅微服务实战 https://url.wx-coder.cn/7KZ2i 或者关系型数据库理论 https://url.wx-coder.cn/DJNQn 了解并发编程在实际系统中的应用。

并发与并行

并发就是可同时发起执行的程序,指程序的逻辑结构;并行就是可以在支持并行的硬件上执行的并发程序,指程序的运⾏状态。换句话说,并发程序代表了所有可以实现并发行为的程序,这是一个比较宽泛的概念,并行程序也只是他的一个子集。并发是并⾏的必要条件;但并发不是并⾏的充分条件。并发只是更符合现实问题本质的表达,目的是简化代码逻辑,⽽不是使程序运⾏更快。要是程序运⾏更快必是并发程序加多核并⾏。

简言之,并发是同一时间应对(dealing with)多件事情的能力;并行是同一时间动手做(doing)多件事情的能力。

并发是问题域中的概念——程序需要被设计成能够处理多个同时 (或者几乎同时) 发生的事件;一个并发程序含有多个逻辑上的独立执行块,它们可以独立地并行执行,也可以串行执行。而并行则是方法域中的概念——通过将问题中的多个部分并行执行,来加速解决问题。一个并行程序解决问题的速度往往比一个串行程序快得多,因为其可以同时执行整个任务的多个部分。并行程序可能有多个独立执行块,也可能仅有一个。

具体而言,Redis 会是一个很好地区分并发和并行的例子。Redis 本身是一个单线程的数据库,但是可以通过多路复用与事件循环的方式来提供并发地 IO 服务。这是因为多核并行本质上会有很大的一个同步的代价,特别是在锁或者信号量的情况下。因此,Redis 利用了单线程的事件循环来保证一系列的原子操作,从而保证了即使在高并发的情况下也能达到几乎零消耗的同步。再引用下 Rob Pike 的描述:

A single-threaded program can definitely provides concurrency at the IO level by using an IO (de)multiplexing mechanism and an event loop (which is what Redis does).

线程级并发

从 20 世纪 60 年代初期出现时间共享以来,计算机系统中就开始有了对并发执行的支持;传统意义上,这种并发执行只是模拟出来的,是通过使一台计算机在它正在执行的进程间快速切换的方式实现的,这种配置称为单处理器系统。从 20 世纪 80 年代开始,多处理器系统,即由单操作系统内核控制的多处理器组成的系统采用了多核处理器与超线程(HyperThreading)等技术允许我们实现真正的并行。多核处理器是将多个 CPU 集成到一个集成电路芯片上:

超线程,有时称为同时多线程(simultaneous multi-threading),是一项允许一个 CPU 执行多个控制流的技术。它涉及 CPU 某些硬件有多个备份,比如程序计数器和寄存器文件;而其他的硬件部分只有一份,比如执行浮点算术运算的单元。常规的处理器需要大约 20 000 个时钟周期做不同线程间的转换,而超线程的处理器可以在单个周期的基础上决定要执行哪一个线程。这使得 CPU 能够更好地利用它的处理资源。例如,假设一个线程必须等到某些数据被装载到高速缓存中,那 CPU 就可以继续去执行另一个线程。

指令级并发

在较低的抽象层次上,现代处理器可以同时执行多条指令的属性称为指令级并行。实每条指令从开始到结束需要长得多的时间,大约 20 个或者更多的周期,但是处理器使用了非常多的聪明技巧来同时处理多达 100 条的指令。在流水线中,将执行一条指令所需要的活动划分成不同的步骤,将处理器的硬件组织成一系列的阶段,每个阶段执行一个步骤。这些阶段可以并行地操作,用来处理不同指令的不同部分。我们会看到一个相当简单的硬件设计,它能够达到接近于一个时钟周期一条指令的执行速率。如果处理器可以达到比一个周期一条指令更快的执行速率,就称之为超标量(Super Scalar)处理器。

单指令、多数据

在最低层次上,许多现代处理器拥有特殊的硬件,允许一条指令产生多个可以并行执行的操作,这种方式称为单指令、多数据,即 SIMD 并行。例如,较新的 Intel 和 AMD 处理器都具有并行地对 4 对单精度浮点数(C 数据类型 float)做加法的指令。


内存模型

如前文所述,现代计算机通常有两个或者更多的 CPU,一些 CPU 还有多个核;其允许多个线程同时运行,每个 CPU 在某个时间片内运行其中的一个线程。在存储管理 https://parg.co/Z47 一节中我们介绍了计算机系统中的不同的存储类别:

每个 CPU 包含多个寄存器,这些寄存器本质上就是 CPU 内存;CPU 在寄存器中执行操作的速度会比在主内存中操作快非常多。每个 CPU 可能还拥有 CPU 缓存层,CPU 访问缓存层的速度比访问主内存块很多,但是却比访问寄存器要慢。计算机还包括主内存(RAM),所有的 CPU 都可以访问这个主内存,主内存一般都比 CPU 缓存大很多,但速度要比 CPU 缓存慢。当一个 CPU 需要访问主内存的时候,会把主内存中的部分数据读取到 CPU 缓存,甚至进一步把缓存中的部分数据读取到内部的寄存器,然后对其进行操作。当 CPU 需要向主内存写数据的时候,会将寄存器中的数据写入缓存,某些时候会将数据从缓存刷入主内存。无论从缓存读还是写数据,都没有必要一次性全部读出或者写入,而是仅对部分数据进行操作。

并发编程中的问题,往往源于缓存导致的可见性问题、线程切换导致的原子性问题以及编译优化带来的有序性问题。以 Java 虚拟机为例,每个线程都拥有一个属于自己的线程栈(调用栈),随着线程代码的执行,调用栈会随之改变。线程栈中包含每个正在执行的方法的局部变量。每个线程只能访问属于自己的栈。调用栈中的局部变量,只有创建这个栈的线程才可以访问,其他线程都不能访问。即使两个线程在执行一段相同的代码,这两个线程也会在属于各自的线程栈中创建局部变量。因此,每个线程拥有属于自己的局部变量。所有基本类型的局部变量全部存放在线程栈中,对其他线程不可见。一个线程可以把基本类型拷贝到其他线程,但是不能共享给其他线程,而无论哪个线程创建的对象都存放在堆中。

可见性

所谓的可见性,即是一个线程对共享变量的修改,另外一个线程能够立刻看到。单核时代,所有的线程都是直接操作单个 CPU 的数据,某个线程对缓存的写对另外一个线程来说一定是可见的;譬如下图中,如果线程 B 在线程 A 更新了变量值之后进行访问,那么获得的肯定是变量 V 的最新值。多核时代,每颗 CPU 都有自己的缓存,共享变量存储在主内存。运行在某个 CPU 中的线程将共享变量读取到自己的 CPU 缓存。在 CPU 缓存中,修改了共享对象的值,由于 CPU 并未将缓存中的数据刷回主内存,导致对共享变量的修改对于在另一个 CPU 中运行的线程而言是不可见的。这样每个线程都会拥有一份属于自己的共享变量的拷贝,分别存于各自对应的 CPU 缓存中。

可见性问题最经典的案例即是并发加操作,如下两个线程同时在更新变量 test 的 count 属性域的值,第一次都会将 count=0 读到各自的 CPU 缓存里,执行完 count+=1 之后,各自 CPU 缓存里的值都是 1,同时写入内存后,我们会发现内存中是 1,而不是我们期望的 2。之后由于各自的 CPU 缓存里都有了 count 的值,两个线程都是基于 CPU 缓存里的 count 值来计算,所以导致最终 count 的值都是小于 20000 的。

Thread th1 = new Thread(()->{test.add10K();
});

Thread th2 = new Thread(()->{test.add10K();
});

// 每个线程中对相同对象执行加操作
count += 1;

在 Java 中,如果多个线程共享一个对象,并且没有合理的使用 volatile 声明和线程同步,一个线程更新共享对象后,另一个线程可能无法取到对象的最新值。当一个共享变量被 volatile 修饰时,它会保证修改的值会立即被更新到主存,当有其他线程需要读取时,它会去内存中读取新值。通过 synchronized 和 Lock 也能够保证可见性,synchronized 和 Lock 能保证同一时刻只有一个线程获取锁然后执行同步代码,并且在释放锁之前会将对变量的修改刷新到主存当中。因此可以保证可见性。

原子性

所谓的原子性,就是一个或者多个操作在 CPU 执行的过程中不被中断的特性,CPU 能保证的原子操作是 CPU 指令级别的,而不是高级语言的操作符。我们在编程语言中部分看似原子操作的指令,在被编译到汇编之后往往会变成多个操作:

i++

# 编译成汇编之后就是:# 读取当前变量 i 并把它赋值给一个临时寄存器;
movl i(%rip), %eax
# 给临时寄存器 +1;
addl $1, %eax
# 把 eax 的新值写回内存
movl %eax, i(%rip)

我们可以清楚看到 C 代码只需要一句,但编译成汇编却需要三步 (这里不考虑编译器优化,实际上通过编译器优化可以将这三条汇编指令合并成一条)。也就是说,只有简单的读取、赋值(而且必须是将数字赋值给某个变量,变量之间的相互赋值不是原子操作) 才是原子操作。按照原子操作解决同步问题方式:依靠处理器原语支持把上述三条指令合三为一,当做一条指令来执行,保证在执行过程中不会被打断并且多线程并发也不会受到干扰。这样同步问题迎刃而解,这也就是所谓的原子操作。但处理器没有义务为任意代码片段提供原子性操作,尤其是我们的临界区资源十分庞大甚至大小不确定,处理器没有必要或是很难提供原子性支持,此时往往需要依赖于锁来保证原子性。

对应原子操作 / 事务在 Java 中,对基本数据类型的变量的读取和赋值操作是原子性操作,即这些操作是不可被中断的,要么执行,要么不执行。Java 内存模型只保证了基本读取和赋值是原子性操作,如果要实现更大范围操作的原子性,可以通过 synchronized 和 Lock 来实现。由于 synchronized 和 Lock 能够保证任一时刻只有一个线程执行该代码块,那么自然就不存在原子性问题了,从而保证了原子性。

有序性

顾名思义,有序性指的是程序按照代码的先后顺序执行。代码重排是指编译器对用户代码进行优化以提高代码的执行效率,优化前提是不改变代码的结果,即优化前后代码执行结果必须相同。

譬如:

int a = 1, b = 2, c = 3;
void test() {
    a = b + 1;
    b = c + 1;
    c = a + b;
}

在 gcc 下的汇编代码 test 函数体代码如下,其中编译参数: -O0

movl b(%rip), %eax
addl $1, %eax
movl %eax, a(%rip)
movl c(%rip), %eax
addl $1, %eax
movl %eax, b(%rip)
movl a(%rip), %edx
movl b(%rip), %eax
addl %edx, %eax
movl %eax, c(%rip)

编译参数:-O3

movl b(%rip), %eax                  ; 将 b 读入 eax 寄存器
leal 1(%rax), %edx                  ; 将 b + 1 写入 edx 寄存器
movl c(%rip), %eax                  ; 将 c 读入 eax
movl %edx, a(%rip)                  ; 将 edx 写入 a
addl $1, %eax                       ; 将 eax+1
movl %eax, b(%rip)                  ; 将 eax 写入 b
addl %edx, %eax                     ; 将 eax+edx
movl %eax, c(%rip)                  ; 将 eax 写入 c 

在 Java 中与有序性相关的经典问题就是单例模式,譬如我们会采用静态函数来获取某个对象的实例,并且使用 synchronized 加锁来保证只有单线程能够触发创建,其他线程则是直接获取到实例对象。

if (instance == null) {synchronized(Singleton.class) {if (instance == null)
        instance = new Singleton();}
}

不过虽然我们期望的对象创建的过程是:内存分配、初始化对象、将对象引用赋值给成员变量,但是实际情况下经过优化的代码往往会首先进行变量赋值,而后进行对象初始化。假设线程 A 先执行 getInstance() 方法,当执行完指令 2 时恰好发生了线程切换,切换到了线程 B 上;如果此时线程 B 也执行 getInstance() 方法,那么线程 B 在执行第一个判断时会发现 instance != null,所以直接返回 instance,而此时的 instance 是没有初始化过的,如果我们这个时候访问 instance 的成员变量就可能触发空指针异常。

内存屏障

多处理器同时访问共享主存,每个处理器都要对读写进行重新排序,一旦数据更新,就需要同步更新到主存上 (这里并不要求处理器缓存更新之后立刻更新主存)。在这种情况下,代码和指令重排,再加上缓存延迟指令结果输出导致共享变量被修改的顺序发生了变化,使得程序的行为变得无法预测。为了解决这种不可预测的行为,处理器提供一组机器指令来确保指令的顺序要求,它告诉处理器在继续执行前提交所有尚未处理的载入和存储指令。同样的也可以要求编译器不要对给定点以及周围指令序列进行重排。这些确保顺序的指令称为内存屏障。具体的确保措施在程序语言级别的体现就是内存模型的定义。

POSIX、C++、Java 都有各自的共享内存模型,实现上并没有什么差异,只是在一些细节上稍有不同。这里所说的内存模型并非是指内存布 局,特指内存、Cache、CPU、写缓冲区、寄存器以及其他的硬件和编译器优化的交互时对读写指令操作提供保护手段以确保读写序。将这些繁杂因素可以笼 统的归纳为两个方面:重排和缓存,即上文所说的代码重排、指令重排和 CPU Cache。简单的说内存屏障做了两件事情:拒绝重排,更新缓存

C++11 提供一组用户 API std::memory_order 来指导处理器读写顺序。Java 使用 happens-before 规则来屏蔽具体细节保证,指导 JVM 在指令生成的过程中穿插屏障指令。内存屏障也可以在编译期间指示对指令或者包括周围指令序列不进行优化,称之为编译器屏障,相当于轻量级内存屏障,它的工作同样重要,因为它在编译期指导编译器优化。屏障的实现稍微复杂一些,我们使用一组抽象的假想指令来描述内存屏障的工作原理。使用 MB_R、MB_W、MB 来抽象处理器指令为宏:

  • MB_R 代表读内存屏障,它保证读取操作不会重排到该指令调用之后。
  • MB_W 代表写内存屏障,它保证写入操作不会重排到该指令调用之后。
  • MB 代表读写内存屏障,可保证之前的指令不会重排到该指令调用之后。

这些屏障指令在单核处理器上同样有效,因为单处理器虽不涉及多处理器间数据同步问题,但指令重排和缓存仍然影响数据的正确同步。指令重排是非常底层的且实 现效果差异非常大,尤其是不同体系架构对内存屏障的支持程度,甚至在不支持指令重排的体系架构中根本不必使用屏障指令。具体如何使用这些屏障指令是支持的 平台、编译器或虚拟机要实现的,我们只需要使用这些实现的 API(指的是各种并发关键字、锁、以及重入性等,下节详细介绍)。这里的目的只是为了帮助更好 的理解内存屏障的工作原理。

内存屏障的意义重大,是确保正确并发的关键。通过正确的设置内存屏障可以确保指令按照我们期望的顺序执行。这里需要注意的是内存屏蔽只应该作用于需要同步的指令或者还可以包含周围指令的片段。如果用来同步所有指令,目前绝大多数处理器架构的设计就会毫无意义。

Java 内存模型(Java Memory Model, JMM)

Java 内存模型着眼于描述 Java 中的线程是如何与内存进行交互,以及单线程中代码执行的顺序等,并提供了一系列基础的并发语义原则;最早的 Java 内存模型于 1995 年提出,致力于解决不同处理器 / 操作系统中线程交互 / 同步的问题,规定和指引 Java 程序在不同的内存架构、CPU 和操作系统间有确定性地行为。在 Java 5 版本之前,JMM 并不完善,彼时多线程往往会在共享内存中读取到很多奇怪的数据;譬如,某个线程无法看到其他线程对共享变量写入的值,或者因为指令重排序的问题,某个线程可能看到其他线程奇怪的操作步骤。

Java 内存模型具备一些先天的“有序性”,即不需要通过任何手段就能够得到保证的有序性,这个通常也称为 happens-before 原则。如果两个操作的执行次序无法从 happens-before 原则推导出来,那么它们就不能保证它们的有序性,虚拟机可以随意地对它们进行重排序。

Java 内存模型对一个线程所做的变动能被其它线程可见提供了保证,它们之间是先行发生关系。

  • 线程内的代码能够按先后顺序执行,这被称为 程序次序规则
  • 对于同一个锁,一个解锁操作一定要发生在时间上后发生的另一个锁定操作之前,也叫做 管程锁定规则
  • 前一个对 volatile 的写操作在后一个 volatile 的读操作之前,也叫 volatile 变量规则
  • 一个线程内的任何操作必需在这个线程的 start()调用之后,也叫作 线程启动规则
  • 一个线程的所有操作都会在线程终止之前,线程终止规则
  • 一个对象的终结操作必需在这个对象构造完成之后,也叫 对象终结规则

对于程序次序规则来说,就是一段程序代码的执行在单个线程中看起来是有序的。注意,虽然这条规则中提到“书写在前面的操作先行发生于书写在后面的操作”,这个应该是程序看起来执行的顺序是按照代码顺序执行的,因为虚拟机可能会对程序代码进行指令重排序。虽然进行重排序,但是最终执行的结果是与程序顺序执行的结果一致的,它只会对不存在数据依赖性的指令进行重排序。因此,在单个线程中,程序执行看起来是有序执行的,这一点要注意理解。事实上,这个规则是用来保证程序在单线程中执行结果的正确性,但无法保证程序在多线程中执行的正确性。


进程,线程与协程

在未配置 OS 的系统中,程序的执行方式是顺序执行,即必须在一个程序执行完后,才允许另一个程序执行;在多道程序环境下,则允许多个程序并发执行。程序的这两种执行方式间有着显著的不同。也正是程序并发执行时的这种特征,才导致了在操作系统中引入进程的概念。进程是资源分配的基本单位,线程是资源调度的基本单位

早期的操作系统基于进程来调度 CPU,不同进程间是不共享内存空间的,所以进程要做任务切换就要切换内存映射地址,而一个进程创建的所有线程,都是共享一个内存空间的,所以线程做任务切换成本就很低了。现代的操作系统都基于更轻量的线程来调度,现在我们提到的“任务切换”都是指“线程切换”。

Process | 进程

进程是操作系统对一个正在运行的程序的一种抽象,在一个系统上可以同时运行多个进程,而每个进程都好像在独占地使用硬件。所谓的并发运行,则是说一个进程的指令和另一个进程的指令是交错执行的。无论是在单核还是多核系统中,可以通过处理器在进程间切换,来实现单个 CPU 看上去像是在并发地执行多个进程。操作系统实现这种交错执行的机制称为上下文切换。

操作系统保持跟踪进程运行所需的所有状态信息。这种状态,也就是上下文,它包括许多信息,例如 PC 和寄存器文件的当前值,以及主存的内容。在任何一个时刻,单处理器系统都只能执行一个进程的代码。当操作系统决定要把控制权从当前进程转移到某个新进程时,就会进行上下文切换,即保存当前进程的上下文、恢复新进程的上下文,然后将控制权传递到新进程。新进程就会从上次停止的地方开始。

在虚拟存储管理 https://url.wx-coder.cn/PeNqS 一节中,我们介绍过它为每个进程提供了一个假象,即每个进程都在独占地使用主存。每个进程看到的是一致的存储器,称为虚拟地址空间。其虚拟地址空间最上面的区域是为操作系统中的代码和数据保留的,这对所有进程来说都是一样的;地址空间的底部区域存放用户进程定义的代码和数据。

  • 程序代码和数据,对于所有的进程来说,代码是从同一固定地址开始,直接按照可执行目标文件的内容初始化。
  • 堆,代码和数据区后紧随着的是运行时堆。代码和数据区是在进程一开始运行时就被规定了大小,与此不同,当调用如 malloc 和 free 这样的 C 标准库函数时,堆可以在运行时动态地扩展和收缩。
  • 共享库:大约在地址空间的中间部分是一块用来存放像 C 标准库和数学库这样共享库的代码和数据的区域。
  • 栈,位于用户虚拟地址空间顶部的是用户栈,编译器用它来实现函数调用。和堆一样,用户栈在程序执行期间可以动态地扩展和收缩。
  • 内核虚拟存储器:内核总是驻留在内存中,是操作系统的一部分。地址空间顶部的区域是为内核保留的,不允许应用程序读写这个区域的内容或者直接调用内核代码定义的函数。

Thread | 线程

在现代系统中,一个进程实际上可以由多个称为线程的执行单元组成,每个线程都运行在进程的上下文中,并共享同样的代码和全局数据。进程的个体间是完全独立的,而线程间是彼此依存的。多进程环境中,任何一个进程的终止,不会影响到其他进程。而多线程环境中,父线程终止,全部子线程被迫终止(没有了资源)。而任何一个子线程终止一般不会影响其他线程,除非子线程执行了 exit() 系统调用。任何一个子线程执行 exit(),全部线程同时灭亡。多线程程序中至少有一个主线程,而这个主线程其实就是有 main 函数的进程。它是整个程序的进程,所有线程都是它的子线程。我们通常把具有多线程的主进程称之为主线程。

线程共享的环境包括:进程代码段、进程的公有数据、进程打开的文件描述符、信号的处理器、进程的当前目录、进程用户 ID 与进程组 ID 等,利用这些共享的数据,线程很容易的实现相互之间的通讯。进程拥有这许多共性的同时,还拥有自己的个性,并以此实现并发性:

  • 线程 ID:每个线程都有自己的线程 ID,这个 ID 在本进程中是唯一的。进程用此来标识线程。
  • 寄存器组的值:由于线程间是并发运行的,每个线程有自己不同的运行线索,当从一个线程切换到另一个线程上时,必须将原有的线程的寄存器集合的状态保存,以便 将来该线程在被重新切换到时能得以恢复。
  • 线程的堆栈:堆栈是保证线程独立运行所必须的。线程函数可以调用函数,而被调用函数中又是可以层层嵌套的,所以线程必须拥有自己的函数堆栈,使得函数调用可以正常执行,不受其他线程的影响。
  • 错误返回码:由于同一个进程中有很多个线程在同时运行,可能某个线程进行系统调用后设置了 errno 值,而在该 线程还没有处理这个错误,另外一个线程就在此时 被调度器投入运行,这样错误值就有可能被修改。所以,不同的线程应该拥有自己的错误返回码变量。
  • 线程的信号屏蔽码:由于每个线程所感兴趣的信号不同,所以线程的信号屏蔽码应该由线程自己管理。但所有的线程都共享同样的信号处理器。
  • 线程的优先级:由于线程需要像进程那样能够被调度,那么就必须要有可供调度使用的参数,这个参数就是线程的优先级。

Linux 中的线程

在 Linux 2.4 版以前,线程的实现和管理方式就是完全按照进程方式实现的;在 Linux 2.6 之前,内核并不支持线程的概念,仅通过轻量级进程(lightweight process)模拟线程,一个用户线程对应一个内核线程(内核轻量级进程),这种模型最大的特点是线程调度由内核完成了,而其他线程操作(同步、取消)等都是核外的线程库(LinuxThread)函数完成的。为了完全兼容 Posix 标准,Linux 2.6 首先对内核进行了改进,引入了线程组的概念(仍然用轻量级进程表示线程),有了这个概念就可以将一组线程组织称为一个进程,不过内核并没有准备特别的调度算法或是定义特别的数据结构来表征线程;相反,线程仅仅被视为一个与其他进程(概念上应该是线程)共享某些资源的进程(概念上应该是线程)。在实现上主要的改变就是在 task_struct 中加入 tgid 字段,这个字段就是用于表示线程组 id 的字段。在用户线程库方面,也使用 NPTL 代替 LinuxThread。不同调度模型上仍然采用 1 对 1 模型。

进程的实现是调用 fork 系统调用:pid_t fork(void);,线程的实现是调用 clone 系统调用:int clone(int (*fn)(void *), void *child_stack, int flags, void *arg, ...)。与标准 fork() 相比,线程带来的开销非常小,内核无需单独复制进程的内存空间或文件描写叙述符等等。这就节省了大量的 CPU 时间,使得线程创建比新进程创建快上十到一百倍,能够大量使用线程而无需太过于操心带来的 CPU 或内存不足。无论是 fork、vfork、kthread_create 最后都是要调用 do_fork,而 do_fork 就是根据不同的函数参数,对一个进程所需的资源进行分配。

线程池

线程池的大小依赖于所执行任务的特性以及程序运行的环境,线程池的大小应该应采取可配置的方式(写入配置文件)或者根据可用的 CPU 数量 Runtime.availableProcessors() 来进行设置,其中 Ncpu 表示可用 CPU 数量,Nthreads 表示线程池工作线程数量,Ucpu 表示 CPU 的利用率 0≤ Ucpu ≤1;W 表示资源等待时间,C 表示任务计算时间;Rtotal 表示有限资源的总量,Rper 表示每个任务需要的资源数量。

  • 对于对于纯 CPU 计算的任务 - 即不依赖阻塞资源(外部接口调用)以及有限资源(线程池)的 CPU 密集型(compute-intensive)任务线程池的大小可以设置为:Nthreads = Ncpu+1
  • 如果执行的任务除了 cpu 计算还包括一些外部接口调用或其他会阻塞的计算,那么线程池的大小可以设置为 Nthreads = Ncpu - Ucpu -(1 + W / C)。可以看出对于 IO 等待时间长于任务计算时间的情况,W/C 大于 1,假设 cpu 利用率是 100%,那么 W/C 结果越大,需要的工作线程也越多,因为如果没有足够的线程则会造成任务队列迅速膨胀。
  • 如果任务依赖于一些有限的资源比如内存,文件句柄,数据库连接等等,那么线程池最大可以设置为 Nthreads ≤ Rtotal/Rper

Coroutine | 协程

协程是用户模式下的轻量级线程,最准确的名字应该叫用户空间线程(User Space Thread),在不同的领域中也有不同的叫法,譬如纤程 (Fiber)、绿色线程(Green Thread) 等等。操作系统内核对协程一无所知,协程的调度完全有应用程序来控制,操作系统不管这部分的调度;一个线程可以包含一个或多个协程,协程拥有自己的寄存器上下文和栈,协程调度切换时,将寄存器上细纹和栈保存起来,在切换回来时恢复先前保运的寄存上下文和栈。

比如 Golang 里的 go 关键字其实就是负责开启一个 Fiber,让 func 逻辑跑在上面。而这一切都是发生的用户态上,没有发生在内核态上,也就是说没有 ContextSwitch 上的开销。协程的实现库中笔者较为常用的譬如 Go Routine、node-fibers、Java-Quasar 等。

Go 的栈是动态分配大小的,随着存储数据的数量而增长和收缩。每个新建的 Goroutine 只有大约 4KB 的栈。每个栈只有 4KB,那么在一个 1GB 的 RAM 上,我们就可以有 256 万个 Goroutine 了,相对于 Java 中每个线程的 1MB,这是巨大的提升。Golang 实现了自己的调度器,允许众多的 Goroutines 运行在相同的 OS 线程上。就算 Go 会运行与内核相同的上下文切换,但是它能够避免切换至 ring-0 以运行内核,然后再切换回来,这样就会节省大量的时间。但是,这只是纸面上的分析。为了支持上百万的 Goroutines,Go 需要完成更复杂的事情。

要支持真正的大并发需要另外一项优化:当你知道线程能够做有用的工作时,才去调度它。如果你运行大量线程的话,其实只有少量的线程会执行有用的工作。Go 通过集成通道(channel)和调度器(scheduler)来实现这一点。如果某个 Goroutine 在一个空的通道上等待,那么调度器会看到这一点并且不会运行该 Goroutine。Go 更近一步,将大多数空闲的线程都放到它的操作系统线程上。通过这种方式,活跃的 Goroutine(预期数量会少得多)会在同一个线程上调度执行,而数以百万计的大多数休眠的 Goroutine 会单独处理。这样有助于降低延迟。

除非 Java 增加语言特性,允许调度器进行观察,否则的话,是不可能支持智能调度的。但是,你可以在“用户空间”中构建运行时调度器,它能够感知线程何时能够执行工作。这构成了像 Akka 这种类型的框架的基础,它能够支持上百万的 Actor。


并发控制

涉及多线程程序涉及的时候经常会出现一些令人难以思议的事情,用堆和栈分配一个变量可能在以后的执行中产生意想不到的结果,而这个结果的表现就是内存的非法被访问,导致内存的内容被更改。在一个进程的线程共享堆区,而进程中的线程各自维持自己堆栈。在 Windows 等平台上,不同线程缺省使用同一个堆,所以用 C 的 malloc (或者 windows 的 GlobalAlloc)分配内存的时候是使用了同步保护的。如果没有同步保护,在两个线程同时执行内存操作的时候会产生竞争条件,可能导致堆内内存管理混乱。比如两个线程分配了统一块内存地址,空闲链表指针错误等。

最常见的进程 / 线程的同步方法有互斥锁 (或称互斥量 Mutex),读写锁(rdlock),条件变量(cond),信号量(Semophore) 等;在 Windows 系统中,临界区 (Critical Section) 和事件对象 (Event) 也是常用的同步方法。总结而言,同步问题基本的就是解决原子性与可见性 / 一致性这两个问题,其基本手段就是基于锁,因此又可以分为三个方面:指令串行化 / 临界资源管理 / 锁、数据一致性 / 数据可见性、事务 / 原子操作。在并发控制中我们会考虑线程协作、互斥与锁、并发容器等方面。

线程通信

并发控制中主要考虑线程之间的通信 (线程之间以何种机制来交换信息) 与同步 (读写等待,竞态条件等) 模型,在命令式编程中,线程之间的通信机制有两种:共享内存和消息传递。Java 就是典型的共享内存模式的通信机制;而 Go 则是提倡以消息传递方式实现内存共享,而非通过共享来实现通信。

在共享内存的并发模型里,线程之间共享程序的公共状态,线程之间通过写 - 读内存中的公共状态来隐式进行通信。在消息传递的并发模型里,线程之间没有公共状态,线程之间必须通过明确的发送消息来显式进行通信。同步是指程序用于控制不同线程之间操作发生相对顺序的机制。在共享内存并发模型里,同步是显式进行的。程序员必须显式指定某个方法或某段代码需要在线程之间互斥执行。在消息传递的并发模型里,由于消息的发送必须在消息的接收之前,因此同步是隐式进行的。

常见的线程通信方式有以下几种:

  • 管道(Pipe):管道是一种半双工的通信方式,数据只能单向流动,而且只能在具有亲缘关系的进程间使用,其中进程的亲缘关系通常是指父子进程关系。
  • 消息队列(Message Queue):消息队列是由消息的链表,存放在内核中并由消息队列标识符标识。消息队列克服了信号传递信息少、管道只能承载无格式字节流以及缓冲区大小受限等缺点。
  • 信号量(Semophore):信号量是一个计数器,可以用来控制多个进程对共享资源的访问。它常作为一种锁机制,防止某进程正在访问共享资源时,其他进程也访问该资源。因此,主要作为进程间以及同一进程内不同线程之间的同步手段。
  • 共享内存(Shared Memory):共享内存就是映射一段能被其他进程所访问的内存,这段共享内存由一个进程创建,但多个进程都可以访问。共享内存是最快的 IPC 方式,它是针对其他进程间通信方式运行效率低而专门设计的。它往往与其他通信机制,如信号量配合使用,来实现进程间的同步和通信。
  • 套接字(Socket):套接字也是一种进程间通信机制,与其他通信机制不同的是,它可用于不同主机间的进程通信。

锁与互斥

互斥是指某一资源同时只允许一个访问者对其进行访问,具有唯一性和排它性;但互斥无法限制访问者对资源的访问顺序,即访问是无序的。同步:是指在互斥的基础上(大多数情况),通过其它机制实现访问者对资源的有序访问。在大多数情况下,同步已经实现了互斥,特别是所有写入资源的情况必定是互斥的;少数情况是指可以允许多个访问者同时访问资源。

临界资源

所谓的临界资源,即一次只允许一个进程访问的资源,多个进程只能互斥访问的资源。临界资源的访问需要同步操作,比如信号量就是一种方便有效的进程同步机制。但信号量的方式要求每个访问临界资源的进程都具有 wait 和 signal 操作。这样使大量的同步操作分散在各个进程中,不仅给系统管理带来了麻烦,而且会因同步操作的使用不当导致死锁。管程就是为了解决这样的问题而产生的。

操作系统中管理的各种软件和硬件资源,均可用数据结构抽象地描述其资源特性,即用少量信息和对该资源所执行的操作来表征该资源,而忽略它们的内部结构和实现细节。利用共享数据结构抽象地表示系统中的共享资源。而把对该共享数据结构实施的操作定义为一组过程,如资源的请求和释放过程 request 和 release。进程对共享资源的申请、释放和其他操作,都是通过这组过程对共享数据结构的操作来实现的,这组过程还可以根据资源的情况接受或阻塞进程的访问,确保每次仅有一个进程使用该共享资源,这样就可以统一管理对共享资源的所有访问,实现临界资源互斥访问。

管程就是代表共享资源的数据结构以及由对该共享数据结构实施操作的一组过程所组成的资源管理程序共同构成的一个操作系统的资源管理模块。管程被请求和释放临界资源的进程所调用。管程定义了一个数据结构和能为并发进程所执行 (在该数据结构上) 的一组操作,这组操作能同步进程和改变管程中的数据。

悲观锁(Pessimistic Locking)

悲观并发控制,又名悲观锁 (Pessimistic Concurrency Control,PCC) 是一种并发控制的方法。它可以阻止一个事务以影响其他用户的方式来修改数据。如果一个事务执行的操作都某行数据应用了锁,那只有当这个事务把锁释放,其他事务才能够执行与该锁冲突的操作。悲观并发控制主要用于数据争用激烈的环境,以及发生并发冲突时使用锁保护数据的成本要低于回滚事务的成本的环境中。

在编程语言中,悲观锁可能存在以下缺陷:

  • 在多线程竞争下,加锁、释放锁会导致比较多的上下文切换和调度延时,引起性能问题。
  • 一个线程持有锁会导致其它所有需要此锁的线程挂起。
  • 如果一个优先级高的线程等待一个优先级低的线程释放锁会导致优先级倒置,引起性能风险。

数据库中悲观锁主要由以下问题:悲观锁大多数情况下依靠数据库的锁机制实现,以保证操作最大程度的独占性。如果加锁的时间过长,其他用户长时间无法访问,影响了程序的并发访问性,同时这样对数据库性能开销影响也很大,特别是对长事务而言,这样的开销往往无法承受,特别是对长事务而言。如一个金融系统,当某个操作员读取用户的数据,并在读出的用户数据的基础上进行修改时(如更改用户帐户余额),如果采用悲观锁机制,也就意味着整个操作过程中(从操作员读出数据、开始修改直至提交修改结果的全过程,甚至还包括操作员中途去煮咖啡的时间),数据库记录始终处于加锁状态,可以想见,如果面对几百上千个并发,这样的情况将导致怎样的后果。

互斥锁 / 排他锁

互斥锁即对互斥量进行分加锁,和自旋锁类似,唯一不同的是竞争不到锁的线程会回去睡会觉,等到锁可用再来竞争,第一个切入的线程加锁后,其他竞争失败者继续回去睡觉直到再次接到通知、竞争。

互斥锁算是目前并发系统中最常用的一种锁,POSIX、C++11、Java 等均支持。处理 POSIX 的加锁比较普通外,C++ 和 Java 的加锁方式很有意思。C++ 中可以使用一种 AutoLock(常见于 chromium 等开源项目中)工作方式类似 auto_ptr 智 能指针,在 C++11 中官方将其标准化为 std::lock_guard 和 std::unique_lock。Java 中使用 synchronized 紧跟同步代码块 (也可修饰方法) 的方式同步代码,非常灵活。这两种实现都巧妙的利用各自语言特性实现了非常优雅的加锁方式。当然除此之外他们也支持传统的类 似于 POSIX 的加锁模式。

可重入锁

也叫做锁递归,就是获取一个已经获取的锁。不支持线程获取它已经获取且尚未解锁的方式叫做不可递归或不支持重入。带重入特性的锁在重入时会判断是否同一个线程,如果是,则使持锁计数器 +1(0 代表没有被线程获取,又或者是锁被释放)。C++11 中同时支持两种锁,递归锁 std::recursive_mutex 和非递归 std::mutex。Java 的两种互斥锁实现以及读写锁实现均支持重入。POSIX 使用一种叫做重入函数的方法保证函数的线程安全,锁粒度是调用而非线程。

读写锁

支持两种模式的锁,当采用写模式上锁时与互斥锁相同,是独占模式。但读模式上锁可以被多个读线程读取。即写时使用互斥锁,读时采用共享锁,故又叫共享 - 独 占锁。一种常见的错误认为数据只有在写入时才需要锁,事实是即使是读操作也需要锁保护,如果不这么做的话,读写锁的读模式便毫无意义。

乐观锁(Optimistic Locking)

相对悲观锁而言,乐观锁(Optimistic Locking)机制采取了更加宽松的加锁机制。相对悲观锁而言,乐观锁假设认为数据一般情况下不会造成冲突,所以在数据进行提交更新的时候,才会正式对数据的冲突与否进行检测,如果发现冲突了,则让返回用户错误的信息,让用户决定如何去做。上面提到的乐观锁的概念中其实已经阐述了他的具体实现细节:主要就是两个步骤:冲突检测和数据更新。其实现方式有一种比较典型的就是 Compare and Swap。

CAS 与 ABA

CAS 是项乐观锁技术,当多个线程尝试使用 CAS 同时更新同一个变量时,只有其中一个线程能更新变量的值,而其它线程都失败,失败的线程并不会被挂起,而是被告知这次竞争中失败,并可以再次尝试。CAS 操作包含三个操作数 —— 内存位置 (V)、预期原值(A) 和新值(B)。如果内存位置的值与预期原值相匹配,那么处理器会自动将该位置值更新为新值。否则,处理器不做任何操作。无论哪种情况,它都会在 CAS 指令之前返回该位置的值。CAS 有效地说明了我认为位置 V 应该包含值 A;如果包含该值,则将 B 放到这个位置;否则,不要更改该位置,只告诉我这个位置现在的值即可。这其实和乐观锁的冲突检查 + 数据更新的原理是一样的。

乐观锁也不是万能的,乐观并发控制相信事务之间的数据竞争 (Data Race) 的概率是比较小的,因此尽可能直接做下去,直到提交的时候才去锁定,所以不会产生任何锁和死锁。但如果直接简单这么做,还是有可能会遇到不可预期的结果,例如两个事务都读取了数据库的某一行,经过修改以后写回数据库,这时就遇到了问题。

  • 乐观锁只能保证一个共享变量的原子操作。如上例子,自旋过程中只能保证 value 变量的原子性,这时如果多一个或几个变量,乐观锁将变得力不从心,但互斥锁能轻易解决,不管对象数量多少及对象颗粒度大小。
  • 长时间自旋可能导致开销大。假如 CAS 长时间不成功而一直自旋,会给 CPU 带来很大的开销。
  • ABA 问题。

CAS 的核心思想是通过比对内存值与预期值是否一样而判断内存值是否被改过,但这个判断逻辑不严谨,假如内存值原来是 A,后来被 一条线程改为 B,最后又被改成了 A,则 CAS 认为此内存值并没有发生改变,但实际上是有被其他线程改过的,这种情况对依赖过程值的情景的运算结果影响很大。解决的思路是引入版本号,每次变量更新都把版本号加一。部分乐观锁的实现是通过版本号 (version) 的方式来解决 ABA 问题,乐观锁每次在执行数据的修改操作时,都会带上一个版本号,一旦版本号和数据的版本号一致就可以执行修改操作并对版本号执行 +1 操作,否则就执行失败。因为每次操作的版本号都会随之增加,所以不会出现 ABA 问题,因为版本号只会增加不会减少。

自旋锁

Linux 内核中最常见的锁,作用是在多核处理器间同步数据。这里的自旋是忙等待的意思。如果一个线程 (这里指的是内核线程) 已经持有了一个自旋锁,而另一条线程也想要获取该锁,它就不停地循环等待,或者叫做自旋等待直到锁可用。可以想象这种锁不能被某个线程长时间持有,这会导致其他线程一直自旋,消耗处理器。所以,自旋锁使用范围很窄,只允许短期内加锁。

其实还有一种方式就是让等待线程睡眠直到锁可用,这样就可以消除忙等待。很明显后者优于前者的实现,但是却不适用于此,如果我们使用第二种方式,我们要做几步操作:把该等待线程换出、等到锁可用在换入,有两次上下文切换的代价。这个代价和短时间内自旋 (实现起来也简单) 相比,后者更能适应实际情况的需要。还有一点需要注意,试图获取一个已经持有自旋锁的线程再去获取这个自旋锁或导致死锁,但其他操作系统并非如此。

自旋锁与互斥锁有点类似,只是自旋锁不会引起调用者睡眠,如果自旋锁已经被别的执行单元保持,调用者就一直循环在那里看是 否该自旋锁的保持者已经释放了锁,” 自旋 ” 一词就是因此而得名。其作用是为了解决某项资源的互斥使用。因为自旋锁不会引起调用者睡眠,所以自旋锁的效率远 高于互斥锁。虽然它的效率比互斥锁高,但是它也有些不足之处:

  • 自旋锁一直占用 CPU,他在未获得锁的情况下,一直运行--自旋,所以占用着 CPU,如果不能在很短的时 间内获得锁,这无疑会使 CPU 效率降低。
  • 在用自旋锁时有可能造成死锁,当递归调用时有可能造成死锁,调用有些其他函数也可能造成死锁,如 copy_to_user()、copy_from_user()、kmalloc()等。

自旋锁比较适用于锁使用者保持锁时间比较短的情况。正是由于自旋锁使用者一般保持锁时间非常短,因此选择自旋而不是睡眠是非常必要的,自旋锁的效率远高于互斥锁。信号量和读写信号量适合于保持时间较长的情况,它们会导致调用者睡眠,因此只能在进程上下文使用,而自旋锁适合于保持时间非常短的情况,它可以在任何上下文使用。如果被保护的共享资源只在进程上下文访问,使用信号量保护该共享资源非常合适,如果对共享资源的访问时间非常短,自旋锁也可以。但是如果被保护的共享资源需要在中断上下文访问 (包括底半部即中断处理句柄和顶半部即软中断),就必须使用自旋锁。自旋锁保持期间是抢占失效的,而信号量和读写信号量保持期间是可以被抢占的。自旋锁只有在内核可抢占或 SMP(多处理器) 的情况下才真正需要,在单 CPU 且不可抢占的内核下,自旋锁的所有操作都是空操作。另外格外注意一点:自旋锁不能递归使用。

MVCC

为了实现可串行化,同时避免锁机制存在的各种问题,我们可以采用基于多版本并发控制(Multiversion concurrency control,MVCC)思想的无锁事务机制。人们一般把基于锁的并发控制机制称成为悲观机制,而把 MVCC 机制称为乐观机制。这是因为锁机制是一种预防性的,读会阻塞写,写也会阻塞读,当锁定粒度较大,时间较长时并发性能就不会太好;而 MVCC 是一种后验性的,读不阻塞写,写也不阻塞读,等到提交的时候才检验是否有冲突,由于没有锁,所以读写不会相互阻塞,从而大大提升了并发性能。我们可以借用源代码版本控制来理解 MVCC,每个人都可以自由地阅读和修改本地的代码,相互之间不会阻塞,只在提交的时候版本控制器会检查冲突,并提示 merge。目前,Oracle、PostgreSQL 和 MySQL 都已支持基于 MVCC 的并发机制,但具体实现各有不同。

MVCC 的一种简单实现是基于 CAS(Compare-and-swap)思想的有条件更新(Conditional Update)。普通的 update 参数只包含了一个 keyValueSet’,Conditional Update 在此基础上加上了一组更新条件 conditionSet {… data[keyx]=valuex, … },即只有在 D 满足更新条件的情况下才将数据更新为 keyValueSet’;否则,返回错误信息。这样,L 就形成了如下图所示的 Try/Conditional Update/(Try again) 的处理模式:

对于常见的修改用户帐户信息的例子而言,假设数据库中帐户信息表中有一个 version 字段,当前值为 1;而当前帐户余额字段 (balance) 为 100。

  • 操作员 A 此时将其读出(version=1),并从其帐户余额中扣除 50 (100-50)。
  • 在操作员 A 操作的过程中,操作员 B 也读入此用户信息(version=1),并从其帐户余额中扣除 20(100-20)。
  • 操作员 A 完成了修改工作,将数据版本号加一(version=2),连同帐户扣除后余额(balance=50),提交至数据库更新,此时由于提交数据版本大于数据库记录当前版本,数据被更新,数据库记录 version 更新为 2。
  • 操作员 B 完成了操作,也将版本号加一(version=2)试图向数据库提交数据(balance=80),但此时比对数据库记录版本时发现,操作员 B 提交的数据版本号为 2,数据库记录当前版本也为 2,不满足提交版本必须大于记录当前版本才能执行更新的乐观锁策略,因此,操作员 B 的提交被驳回。这样,就避免了操作员 B 用基于 version=1 的旧数据修改的结果覆盖操作员 A 的操作结果的可能。

从上面的例子可以看出,乐观锁机制避免了长事务中的数据库加锁开销(操作员 A 和操作员 B 操作过程中,都没有对数据库数据加锁),大大提升了大并发量下的系统整体性能表现。需要注意的是,乐观锁机制往往基于系统中的数据存储逻辑,因此也具备一定的局限性,如在上例中,由于乐观锁机制是在我们的系统中实现,来自外部系统的用户余额更新操作不受我们系统的控制,因此可能会造成脏数据被更新到数据库中。


并发 IO

IO 的概念,从字义来理解就是输入输出。操作系统从上层到底层,各个层次之间均存在 IO。比如,CPU 有 IO,内存有 IO, VMM 有 IO, 底层磁盘上也有 IO,这是广义上的 IO。通常来讲,一个上层的 IO 可能会产生针对磁盘的多个 IO,也就是说,上层的 IO 是稀疏的,下层的 IO 是密集的。磁盘的 IO,顾名思义就是磁盘的输入输出。输入指的是对磁盘写入数据,输出指的是从磁盘读出数据。

所谓的并发 IO,即在一个时间片内,如果一个进程进行一个 IO 操作,例如读个文件,这个时候该进程可以把自己标记为“休眠状态”并出让 CPU 的使用权,待文件读进内存,操作系统会把这个休眠的进程唤醒,唤醒后的进程就有机会重新获得 CPU 的使用权了。这里的进程在等待 IO 时之所以会释放 CPU 使用权,是为了让 CPU 在这段等待时间里可以做别的事情,这样一来 CPU 的使用率就上来了;此外,如果这时有另外一个进程也读文件,读文件的操作就会排队,磁盘驱动在完成一个进程的读操作后,发现有排队的任务,就会立即启动下一个读操作,这样 IO 的使用率也上来了。

IO 类型

Unix 中内置了 5 种 IO 模型,阻塞式 IO, 非阻塞式 IO,IO 复用模型,信号驱动式 IO 和异步 IO。而从应用的角度来看,IO 的类型可以分为:

  • 大 / 小块 IO:这个数值指的是控制器指令中给出的连续读出扇区数目的多少。如果数目较多,如 64,128 等,我们可以认为是大块 IO;反之,如果很小,比如 4,8,我们就会认为是小块 IO,实际上,在大块和小块 IO 之间,没有明确的界限。
  • 连续 / 随机 IO:连续 IO 指的是本次 IO 给出的初始扇区地址和上一次 IO 的结束扇区地址是完全连续或者相隔不多的。反之,如果相差很大,则算作一次随机 IO。连续 IO 比随机 IO 效率高的原因是:在做连续 IO 的时候,磁头几乎不用换道,或者换道的时间很短;而对于随机 IO,如果这个 IO 很多的话,会导致磁头不停地换道,造成效率的极大降低。
  • 顺序 / 并发 IO:从概念上讲,并发 IO 就是指向一块磁盘发出一条 IO 指令后,不必等待它回应,接着向另外一块磁盘发 IO 指令。对于具有条带性的 RAID(LUN),对其进行的 IO 操作是并发的,例如:raid 0+1(1+0),raid5 等。反之则为顺序 IO。

在传统的网络服务器的构建中,IO 模式会按照 Blocking/Non-Blocking、Synchronous/Asynchronous 这两个标准进行分类,其中 Blocking 与 Synchronous 大同小异,而 NIO 与 Async 的区别在于 NIO 强调的是 轮询(Polling),而 Async 强调的是通知(Notification)。譬如在一个典型的单进程单线程 Socket 接口中,阻塞型的接口必须在上一个 Socket 连接关闭之后才能接入下一个 Socket 连接。而对于 NIO 的 Socket 而言,服务端应用会从内核获取到一个特殊的 “Would Block” 错误信息,但是并不会阻塞到等待发起请求的 Socket 客户端停止。

一般来说,在 Linux 系统中可以通过调用独立的 select 或者 epoll 方法来遍历所有读取好的数据,并且进行写操作。而对于异步 Socket 而言(譬如 Windows 中的 Sockets 或者 .Net 中实现的 Sockets 模型),服务端应用会告诉 IO Framework 去读取某个 Socket 数据,在数据读取完毕之后 IO Framework 会自动地调用你的回调(也就是通知应用程序本身数据已经准备好了)。以 IO 多路复用中的 Reactor 与 Proactor 模型为例,非阻塞的模型是需要应用程序本身处理 IO 的,而异步模型则是由 Kernel 或者 Framework 将数据准备好读入缓冲区中,应用程序直接从缓冲区读取数据。

  • 同步阻塞:在此种方式下,用户进程在发起一个 IO 操作以后,必须等待 IO 操作的完成,只有当真正完成了 IO 操作以后,用户进程才能运行。
  • 同步非阻塞:在此种方式下,用户进程发起一个 IO 操作以后边可返回做其它事情,但是用户进程需要时不时的询问 IO 操作是否就绪,这就要求用户进程不停的去询问,从而引入不必要的 CPU 资源浪费。
  • 异步非阻塞:在此种模式下,用户进程只需要发起一个 IO 操作然后立即返回,等 IO 操作真正的完成以后,应用程序会得到 IO 操作完成的通知,此时用户进程只需要对数据进行处理就好了,不需要进行实际的 IO 读写操作,因为真正的 IO 读取或者写入操作已经由内核完成了。

而在并发 IO 的问题中,较常见的就是所谓的 C10K 问题,即有 10000 个客户端需要连上一个服务器并保持 TCP 连接,客户端会不定时的发送请求给服务器,服务器收到请求后需及时处理并返回结果。

IO 多路复用

IO 多路复用就通过一种机制,可以监视多个描述符,一旦某个描述符就绪(一般是读就绪或者写就绪),能够通知程序进行相应的读写操作。select,poll,epoll 都是 IO 多路复用的机制。值得一提的是,epoll 仅对于 Pipe 或者 Socket 这样的读写阻塞型 IO 起作用,正常的文件描述符则是会立刻返回文件的内容,因此 epoll 等函数对普通的文件读写并无作用。

首先来看下可读事件与可写事件:当如下任一情况发生时,会产生套接字的可读事件:

  • 该套接字的接收缓冲区中的数据字节数大于等于套接字接收缓冲区低水位标记的大小;
  • 该套接字的读半部关闭(也就是收到了 FIN),对这样的套接字的读操作将返回 0(也就是返回 EOF);
  • 该套接字是一个监听套接字且已完成的连接数不为 0;
  • 该套接字有错误待处理,对这样的套接字的读操作将返回 -1。

当如下任一情况发生时,会产生套接字的可写事件:

  • 该套接字的发送缓冲区中的可用空间字节数大于等于套接字发送缓冲区低水位标记的大小;
  • 该套接字的写半部关闭,继续写会产生 SIGPIPE 信号;
  • 非阻塞模式下,connect 返回之后,该套接字连接成功或失败;
  • 该套接字有错误待处理,对这样的套接字的写操作将返回 -1。

select,poll,epoll 本质上都是同步 IO,因为他们都需要在读写事件就绪后自己负责进行读写,也就是说这个读写过程是阻塞的,而异步 IO 则无需自己负责进行读写,异步 IO 的实现会负责把数据从内核拷贝到用户空间。select 本身是轮询式、无状态的,每次调用都需要把 fd 集合从用户态拷贝到内核态,这个开销在 fd 很多时会很大。epoll 则是触发式处理连接,维护的描述符数目不受到限制,而且性能不会随着描述符数目的增加而下降。

方法 数量限制 连接处理 内存操作
select 描述符个数由内核中的 FD_SETSIZE 限制,仅为 1024;重新编译内核改变 FD_SETSIZE 的值,但是无法优化性能 每次调用 select 都会线性扫描所有描述符的状态,在 select 结束后,用户也要线性扫描 fd_set 数组才知道哪些描述符准备就绪(O(n)) 每次调用 select 都要在用户空间和内核空间里进行内存复制 fd 描述符等信息
poll 使用 pollfd 结构来存储 fd,突破了 select 中描述符数目的限制 类似于 select 扫描方式 需要将 pollfd 数组拷贝到内核空间,之后依次扫描 fd 的状态,整体复杂度依然是 O(n)的,在并发量大的情况下服务器性能会快速下降
epoll 该模式下的 Socket 对应的 fd 列表由一个数组来保存,大小不限制(默认 4k) 基于内核提供的反射模式,有活跃 Socket 时,内核访问该 Socket 的 callback,不需要遍历轮询 epoll 在传递内核与用户空间的消息时使用了内存共享,而不是内存拷贝,这也使得 epoll 的效率比 poll 和 select 更高
退出移动版