CPU并发编程学习小结

在之前接触 C++ Coroutine 的时候,看到了开源代码中关于内存序(memory order)的使用,于是想要了解一下这个内存序到底是个什么东西。结果发现相关的知识体系非常庞大,想要真正搞懂内存序是怎么来的、有什么用和什么时候用,需要搞清楚的东西根本不是一两天能学会的。本来只是想了解下内存序是什么,结果一不小心从《计算机体系结构》、《操作系统导论》一路学到了并发编程……

这篇文章梳理一下我在探索“内存序是个什么东西”时,学到的与 CPU 并发编程相关的知识,把我以前粗略了解的很多概念全部串起来了。

并发与并行的区别

并发与并行这两个概念很相似,但其实是有区别的。并行的两个任务在某个时间点同时运行,而并发则是在某一段时间内同时运行,在这段时间里两个任务可能是交替进行的。

结合一些例子说明会更好理解:一边打游戏一边喝可乐,如果暂停游戏拿起可乐喝一口再继续游戏,这就是并发;如果打游戏的同时用吸管喝可乐,这就是并行。

并发在一段时间内造成了同时进行多项任务的假象,而并行是真正的同时进行多项任务。

CPU 的并行技术

通常在讨论并发和并行的时候,都是在讨论多线程编程。其实在 CPU 内部也有一些并行技术,它们旨在提高 CPU 性能。在 CPU 设计里,提升 CPU 并行性的方法有两类:一类是允许 CPU 同时执行多条指令的指令级并行技术;另一类是运行 CPU 同时执行多个任务的线程级并行技术。

指令级并行

指令流水线技术可以让 CPU 同时执行多条指令,实现指令级并行。下面简单地说明他的原理,要详细地了解它可以参考《计算机组成与设计:硬件/软件接口》这本书。

对于 MIPS 指令集的 CPU 来说,一条指令的执行可以分为五个步骤:读取指令、指令解码与读取寄存器、执行指令、存储器访问和写回寄存器;

MIPS 指令的格式使得它可以同时进行指令解码与读取寄存器的值。对于其他指令集的处理器,可能不止五个步骤。

在没有流水线的处理器上,上一条指令的这五个步骤要全部执行完,才可以执行下一条指令。在处理器进行指令解码和读取寄存器这个步骤时,读取指令等其他部分的电路是闲置着的。流水线技术就是让其他部分的电路也运转起来,用来执行其他的指令。

用《计算机组成与设计:硬件/软件接口》里的例子来说明,这本书用洗衣服的过程来类比 CPU 的运行过程。洗衣店的工作流程可以分为:洗衣服、烘干衣服、叠衣服和收衣服四个步骤。在烘干衣服的时候,洗衣机、叠衣服的桌子和收衣服的人都是空闲的。如果采用流水线技术,此时可以让洗衣机去洗下一批衣服,等烘干机的工作结束,把衣服放到桌子上去叠衣服,而下一批的衣服也洗好了,正好可以放到烘干机里……

下面这张图展示了指令流水线的工作情况,在同一个 CPU 时钟周期里有多条指令同时执行。

指令流水线示意图

流水线可能会遇到在下一个时钟周期里下一条指令不能执行的情况,这种情况称为冒险(hazard)。流水线冒险有很多种情况,比如跳转指令会导致控制冒险。因为在跳转的条件计算出来之前,CPU 无法确定要继续执行哪里的指令,通常的解决方法是分支预测,让 CPU 猜一个分支继续执行。如何解决流水线冒险不是本文的主题因此不继续展开。

另一种指令级并行的技术是多发射(multi-issue),意思是按顺序地一次获取多条指令并同时执行。实现了这种指令级并行的处理器称为超标量处理器(superscalar processor),标量处理器每个时钟周期最多可以完成一条指令,而超标量处理器一个时钟周期可以完成多条指令(IPC > 1)。

执行单元(Execution units, EUs)是 CPU 中用于执行算数逻辑计算、分支和其他操作的独立模块。执行单元一般包括:算术逻辑单元(ALU)、浮点单元(FPU)、地址生成单元(AGU)等。

多发射是通过让 CPU 拥有多个执行单元实现的,将多条指令分配到不同的执行单元,这样指令就可以被同时执行。

这个技术的实现细节是很复杂的,因为并行执行的多条指令之间不可以有数据依赖。编译器在编译阶段可以分析指令间的数据依赖,通过调整指令的顺序以解决数据依赖问题,而且不会影响程序的执行结果。CPU 在运行阶段也可以检查指令间的数据依赖,通过动态调整指令的执行顺序来解决数据依赖问题,这让 CPU 拥有了乱序执行(out-of-order execution)的特性。

线程级并行

同时多线程(Simultaneous multithreading, SMT)技术可以在单个 CPU 内核上运行多个任务。SMT 名字里的“线程”不一定是同一个进程的线程,可以是两个不同进程的线程。在 Intel CPU 里,它被称为超线程技术(Hyper-Threading, HT),就是那个让一个处理器核心变两个处理器核心的技术。

同时多线程的原理是把闲置的执行单元利用起来,只需要增加一些寄存器和其他部件来保存机器状态,就可以提升 CPU 的并行性能。

操作系统的多任务

计算机的资源(CPU 资源、内存资源或硬盘资源等)由操作系统进行管理,现代操作系统将计算机的物理资源虚拟化处理,比如 CPU 虚拟化和内存虚拟化,让每个程序都以为自己拥有完整的 CPU 和完整的内存。

在只有一个核心的 CPU 上,操作系统依然可以做到同时运行多个程序,其中的原理我相信绝大多数读者都了解过。CPU 资源在时间上被划分,让一个程序使用一段时间的 CPU,然后让下一个程序使用一段时间的 CPU,如此下来,CPU 就被几个程序共享了。

如果要深入了解,推荐阅读人民邮电出版社的《操作系统导论》,原著是《Operating Systems: Three Easy Pieces》,书和翻译都很好。

这种暂停当前程序的执行并切换到另一个程序继续执行的操作,称为上下文切换(Context switch)。上下文切换要保存当前程序的程序计数器(Program Counter, PC)、CPU 当前所有寄存器的值、和内存虚拟化相关的一些值,以及其他,然后恢复另一个程序的程序计数器、寄存器值、内存虚拟化相关的值等等。

虽然看起来上下文切换的开销很大,但是除非进程或者线程很多导致上下文切换很频繁,一般来说不用考虑上下文切换的开销。

多进程多线程都是实现并发的方法,在可靠性、资源占用、编程难易程度等方面各有优势与不足。

多进程方案在可靠性上有明显优势,多线程程序任意一条线程的异常都会导致整个程序崩溃。Chrome 浏览器和许多有限元分析软件都采用的多进程方案。

因为缺少并发编程的经验,这一块我就不乱说了。

多处理器调度的问题

现在的处理器基本都是多核心设计,这其实就意味着计算机实际上是有多个处理器的。对操作系统来说,多处理器的多任务调度(决定何时进行上下文切换的策略)会给程序员带来一些麻烦,下面来讨论这些问题。

缓存亲和性

CPU 寄存器的访问速度很快,与之相比内存的访问速度就慢多了。缓存(Cache)是介于 CPU 寄存器和内存之间的存储器,容量比内存小很多,访问速度比内存快得多。

现代处理器的缓存是多级的,一般分为 L1、L2、L3 三个级别,容量依次增加,访问速度依次降低。L1 级缓存又会被拆分成两块,一块专门用来存储指令,另一块专门用来存储数据。下图展示了三级缓存的结构(缓存大小的数值是随便填的)。

CPU 缓存架构

缓存之所以能够起作用,是因为程序的执行具有局部性特征,局部性有两种:时间局部性空间局部性

  • 时间局部性:当一个数据被访问后,它很快会被再次访问。比如循环变量 i 和循环体的指令本身。

  • 空间局部性:当一个数据被访问后,很可能紧接着访问它周围的数据。比如遍历数组和指令的顺序执行。

CPU 在获取数据时会先在 L1 级缓存中寻找,如果没找到,也就是缓存未命中,那么就会到下一级 L2 级缓存寻找,还找不到就从 L3 级缓存寻找,最后从内存中获取数据。

如果频繁遇到缓存未命中,会严重影响 CPU 的运行速度。在编写程序的时候,要考虑到缓存的影响。比如操作系统的多处理器调度策略,要尽可能地让同一个进程保持在同一个 CPU 上。这是因为一个进程运行一段时间后,缓存中维护着该进程的许多状态。当该进程恢复到上一次运行的 CPU 时,缓存就能起作用。

又比如遍历二维数组时,按行遍历和按列遍历的速度是不一样的,按行遍历的速度应该会更快些。

1
2
3
4
5
6
7
8
for(int row = 0; row < MAX_ROW; ++row)
{
for(int column = 0; column < MAX_COLUMN; ++column)
{
data[row * MAX_COLUMN + column] = 1; // 按行遍历,一行一行地遍历
data[column * MAX_ROW + row] = 1; // 按列遍历,一列一列地遍历
}
}

如果指针 data 所指向的内存区域足够大,无法全部装进 L1 缓存中,那么这两种遍历方式的差距将会很大。按列访问每次访问的内存区域跨度很大,很可能会遇到缓存未命中的情况,此时 CPU 不得不去下一级缓存甚至内存中寻找数据,这就降低了效率。用“局部性”的概念来理解,按列访问不符合“空间局部性”的特点,因此缓存无法起到加速作用。

下面的内容没写完……

缓存一致性问题

内存一致性问题

同步问题

一些基本概念

竞态条件、互斥区

原子操作

历史:不需要硬件帮助的原子算法

注意,在现代硬件上这种算法已经无法正确运行。

解决同步问题:互斥锁与条件变量

需要硬件帮忙才能正确实现锁。

自旋锁

优点与不足:在锁会被很快被释放的情况下,自旋锁效率很高,因为可能仅仅自旋了很短的时间。但是在其他情况,自旋锁会一直占用 CPU 使之空转。此外,由于谁能获得锁依赖于系统调度。这可能会导致某种极端情况:一条线程一直在自旋,而其他两条线程交替获得锁,导致这条线程被“饿死”。

Ticket锁

优点与不足:Ticket锁保证所有的线程都能获得锁。

解决自旋太多

  1. 让出时间片:yield
  2. 休眠代替自旋

二阶段锁

自选一段时间,然后休眠线程。

条件变量

使用互斥锁导致的问题

死锁

活锁

优先级反转

无阻塞算法

无阻塞算法(Non-blocking algorithm)常被称为“无锁编程”。无锁编程常被理解为“没有使用互斥锁的编程算法”,这个理解是正确的,因为只要使用了锁就不会是无阻塞算法,但没有反映出“无阻塞”的本质。

wait-free、lock-free 和 obstruction-free。

其中 lock-free 指的是不会导致总体任务进度锁住(lock up)的算法,而不是不用互斥锁的算法。

ABA 问题

总结

参考资料

作者

uint128.com

发布于

2022-08-22

更新于

2022-09-03

许可协议

评论