Skip to content
Branch: master
Find file History
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
..
Failed to load latest commit information.
并发 IO chore: update May 16, 2019
并发单元
并发控制
并发模型
README.md
meta.json

README.md

并发编程

随着硬件性能的迅猛发展与大数据时代的来临,并发编程日益成为编程中不可忽略的重要组成部分。简单定义来看,如果执行单元的逻辑控制流在时间上重叠,那它们就是并发(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)多件事情的能力。

image.png

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

具体而言,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 集成到一个集成电路芯片上:

image

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

指令级并发

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

单指令、多数据

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

并发的应用场景

从计算机系统本身而言,并发被看做是操作系统内核用来运行多个应用程序的机制。很久很久以前是没有并发这个概念的,因为那个时候操作系统并不支持多任务。现在的操作系统今非昔比,支持抢占式任务、多线程、分页、TCP/IP 等现代操作系统特性,能满足用户各种各样的需求同时响应用户的不同操作,靠的是多任务系统的支持。在 Unix 时代一个进程(执行中的程序)只有一个线程,现代操作系统允许一个进程有多条线程。每个线程有独立栈空间、寄存器、程序计数器(存放下一条执行指令)。操作系统调度程序调度的是线程(在本文中提到线程的地方都指的是操作系统级的线程),并非进程,也就是说线程才是调度的基本单位。

在单处理器系统中,一个处于运行状态的 IO 消耗型程序,例如一个网络读取阻塞或用户输入阻塞导致处理器出现空闲,在视处理器为昂贵资源的情形下,这是巨大的浪费。然后,在对称处理器中(SMP),因为只有一个线程,那它只能在其中一个处理器上运行,也就是说剩余的处理器被白白浪费。如果使用多线程,不仅能充分利用多处理器,还能通过线程并发解决上述 IO 消耗程序中处理器空闲问题。并发编程能够解决的典型问题如下所示:

while (true){
     request = next_http_request()
     request_work(request)
}

当 request_work 发起 IO 之后 CPU 是完全空闲下来的,而可怜的新请求(next_http_request)必须等待 IO 完成之后才可以获取 CPU 的控制权。所以 CPU 的利用率非常低,并发要解决的问题就是提高 CPU 的利用率。明白这一点我们也就清楚了,并发只对非 CPU 密集型程序管用,如果 CPU 利用率非常高,更多的并发只会让情况更加糟糕。并发虽好,也不能滥用啊,典型的并发编程的适用场景包括:

  • 在多处理器上进行并行计算:在只有一个 CPU 的单处理器上, 井发流是交替的。在任何时间点上, 都只有一个流在 CPU 上实际执行。 然而, 那些有多个 CPU 的机器, 称为多处理器, 可以真正地同时执行多个流。被分成并发流的并发应用 在这样的机器上能够运行得快很多,这对大规模数据库和科学应用尤为重要。

  • 访问慢速 IO 设备:当一个应用正在等待来自慢速 IO 设备 (例如磁盘) 的数据到达时,内核会运行其他进程使 CPU 保持繁忙。 每个应用都可以以类似的方式,通过交替执行 IO,请求和其他有用的工作来使用并发性。

  • 与人交互:和计算机交互的人要求计算机同时执行多个任务的能力。 例如, 他们在打印个文档时, 可能想要调整一个窗口的大伽 现代视窗系统利用并发性来提供这种能九 每次用户请求某种操作 忧匕如说通过单击鼠标) 时, 一个独立的并发逻辑流被创建来执行这个操作。

  • 通过推迟工作以减少执行时延:有时, 应用程序能够通过推迟其他操作井同时执行它们,利用并发性来降低某些操作的延遮 比如, ˉ 一个动态存储分配器可以通过椎迟与酬个运行在较低优先级上的并发 “合井” 流的合并 (coalescing), 使用空闲时的 CPU 周期, 来降低单个 free 操作的延迟。

  • 服务多个网络客户端:一个慢速的客户端可能会导致服务器拒绝为所有其他客户端服务。 对于闻个真正的服务器来说 可能期望它每秒为成百上千的客户端提供服务, 某些个慢速客户端寻致拒绝为其他客户端服务, 这是不能接受峋 一个更好的方法是创建一个并发服务糕 它为每个客户端创建各自独立的逻辑流 这就允许服务器同时为多个客户端服务, 并且这也避免了慢速客户端独占服务器。

值得一提的是,并发也绝非银弹,在多核的前提下,性能和线程是紧密联系在一起的。线程间的跳转对高频 IO 操作的性能有决定性作用: 一次跳转意味着至少 3-20 微秒的延时,由于每个核心的 L1/L2 Cache 独,随之而来是大量的 cache miss,一些变量的读取、写入延时会从纳秒级上升几百倍至微秒级: 等待 CPU 把对应的缓存行同步过来。有时这带来了一个出乎意料的结果,当每次的处理都很简短时,一个多线程程序未必比一个单线程程序更快。因为前者可能在每次付出了大的切换代价后只做了一点点“正事”,而后者在不停地做“正事”。不过单线程也是有代价的,它工作良好的前提是“正事”都很快,否则一旦某次变慢就使后续的所有“正事”都被延迟了。在一些处理时间普遍较短的程序中,使用(多个不相交的)单线程能最大程度地”做正事“,由于每个请求的处理时间确定,延时表现也很稳定,各种 HTTP 服务器正是这样。但我们的检索服务要做的事情可就复杂多了,有大量的后端服务需要访问,广泛存在的长尾请求使每次处理的时间无法确定,排序策略也越来越复杂。如果还是使用(多个不相交的)单线程的话,一次难以预计的性能抖动,或是一个大请求可能导致后续一堆请求被延迟。

Amdahl 定律

Amdahl 定律可以用来计算处理器平行运算之后效率提升的能力,其由 Gene Amdal 在 1967 年提出;它描述了在一个系统中,基于可并行化和串行化的组件各自所占的比重,程序通过获得额外的计算资源,理论上能够加速多少。任何程序或算法可以按照是否可以被并行化分为可以被并行化的部分 1 - B 与不可以被并行化的部分 B,那么根据 Amdahl 定律,不同的并行因子的情况下程序的总执行时间的变化如下所示:

如果 F 是必须串行化执行的比重,那么 Amdahl 定律告诉我们,在一个 N 处理器的机器中,我们最多可以加速:

当 N 无限增大趋近无穷时,speedup 的最大值无限趋近 1/F,这意味着一个程序中如果 50% 的处理都需要串行进行的话,speedup 只能提升 2 倍(不考虑事实上有多少线程可用);如果程序的 10% 需要串行进行,speedup 最多能够提高近 10 倍。

Amdahl 定律同样量化了串行化的效率开销。在拥有 10 个处理器的系统中,程序如果有 10% 是串行化的,那么最多可以加速 5.3 倍(53 %的使用率),在拥有 100 个处理器的系统中,这个数字可以达到 9.2(9 %的使用率)。这使得无效的 CPU 利用永远不可能到达 10 倍。下图展示了随着串行执行和处理器数量变化,处理器最大限度的利用率的曲线。随着处理器数量的增加,我们很明显地看到,即使串行化执行的程度发 生细微的百分比变化,都会大大限制吞吐量随计算资源增加。

Amdahl 定律旨在说明,多核 CPU 对系统进行优化时,优化的效果取决于 CPU 的数量以及系统中的串行化程序的比重;如果仅关注于提高 CPU 数量而不降低程序的串行化比重,也无法提高系统性能。

链接

You can’t perform that action at this time.