并行编程技术是谁的核心技术体系

并行编程技术是谁的核心技术体系

在摩尔定律失效之前，提升处理器性能通过主频提升、硬件超线程等技术就能满足应用需要。随着主频提升慢慢接近撞上光速这道墙，摩尔定律开始逐渐失效，多核集成为处理器性能提升的主流手段。现在市面上已经很难看到单核的处理器，就是这一发展趋势的佐证。要充分发挥多核丰富的计算资源优势，多核下的并行编程就不可避免，Linux kernel就是一典型的多核并行编程场景。但多核下的并行编程却挑战多多。

多核并行编程的挑战

目前主流的计算机都是冯诺依曼架构，即共享内存的计算模型，这种过程计算模型对并行计算并不友好。下图是一种典型的计算机硬件体系架构。

这种架构中，有如下设计特点：

多个CPU核改善处理器的计算处理能力；

多级cache改善CPU访问主存的效率；

各个CPU都有本地内存（NUMA（非一致性内存访问）），进一步改善CPU访问主存的效率；

store buffer模块改善cache write由于应答延迟而造成的写停顿问题；

invalidate queue模块改善使无效应答的时延，把使无效命令放入queue后就立即发送应答；

外设DMA支持直接访问主存，改善CPU使用效率；

这些硬件体系设计特点也引入很多问题，最大的问题就是cache一致性问题和乱序执行问题。

cache一致性问题由cache一致性协议MESI解决，MESI由硬件保证，对软件来说是透明的。MESI协议保证所有CPU对单个cache line中单个变量修改的顺序保持一致，但不保证不同变量的修改在所有CPU上看到的是相同顺序。这就造成了乱序。不仅如此，乱序的原因还有很多：

store buffer引起的延迟处理，会造成乱序；

invalidate queue引起的延迟处理，会造成乱序；

编译优化，会造成乱序；

分支预测、多流水线等CPU硬件优化技术，会造成乱序；

外设DMA，会造成数据乱序；

这种情况造成，就连简单的++运算 *** 作的原子性都无法保证。这些问题必须采用多核并行编程新的技术手段来解决。

多核并行编程关键技术

锁技术

Linux kernel提供了多种锁机制，如自旋锁、信号量、互斥量、读写锁、顺序锁等。各种锁的简单比较如下，具体实现和使用细节这里就不展开了，可以参考《Linux内核设计与实现》等书的相关章节。

自旋锁，不休眠，无进程上下文切换开销，可以用在中断上下文和临界区小的场合；

信号量，会休眠，支持同时多个并发体进入临界区，可以用在可能休眠或者长的临界区的场合；

互斥量，类似与信号量，但只支持同时只有一个并发体进入临界区；

读写锁，支持读并发，写写/读写间互斥，读会延迟写，对读友好，适用读侧重场合；

顺序锁，支持读并发，写写/读写间互斥，写会延迟读，对写友好，适用写侧重场合；

锁技术虽然能有效地提供并行执行下的竞态保护，但锁的并行可扩展性很差，无法充分发挥多核的性能优势。锁的粒度太粗会限制扩展性，粒度太细会导致巨大的系统开销，而且设计难度大，容易造成死锁。除了并发可扩展性差和死锁外，锁还会引入很多其他问题，如锁惊群、活锁、饥饿、不公平锁、优先级反转等。不过也有一些技术手段或指导原则能解决或减轻这些问题的风险。

按统一的顺序使用锁（锁的层次），解决死锁问题；

指数后退，解决活锁/饥饿问题；

范围锁（树状锁），解决锁惊群问题；

优先级继承，解决优先级反转问题 ；

原子技术

原子技术主要是解决cache和内存不一致性和乱序执行对原子访问的破坏问题。Linux kernel中主要的原子原语有：

ACCESS_ONCE()、READ_ONCE() and WRITE_ONCE()：禁止编译器对数据访问的优化，强制从内存而不是缓存中获取数据；

barrier()：乱序访问内存屏障，限制编译器的乱序优化；

smb_wmb()：写内存屏障，刷新store buffer，同时限制编译器和CPU的乱序优化；

smb_rmb()：读内存屏障，刷新invalidate queue，同时限制编译器和CPU的乱序优化；

smb_mb()：读写内存屏障，同时刷新store buffer和invalidate queue，同时限制编译器和CPU的乱序优化；

atomic_inc()/atomic_read()等：整型原子 *** 作；

严格来说，Linux kernel作为系统软件，实现受硬件影响很大，不同硬件有不同的内存模型，因此，不同于高级语言，Linux kernel的原子原语语义并没有一个统一模型。比如在SMP的ARM64 CPU上，barrier、smb_wmb、smb_rmb的实现与smb_mb都是一样的，都是volatile ("" ::: "memory")。

另外，再多提一句的是，atomic_inc()原语为了保证原子性，需要对cache进行刷新，而缓存行在多核体系下传播相当耗时，其多核下的并行可扩展性差。

无锁技术

上一小节中所提到的原子技术，是无锁技术中的一种，除此之外，无锁技术还包括RCU、Hazard pointer等。值得一提的是，这些无锁技术都基于内存屏障实现的。

Hazard pointer主要用于对象的生命周期管理，类似引用计数，但比引用计数有更好的并行可扩展性；

RCU适用的场景很多，其可以替代：读写锁、引用计数、垃圾回收器、等待事物结束等，而且有更好的并行扩展性。但RCU也有一些不适用的场景，如写侧重；临界区长；临界区内休眠等场景。

不过，所有的无锁原语也只能解决读端的并行可扩展性问题，写端的并行可扩展性只能通过数据分割技术来解决。

数据分割技术

分割数据结构，减少共享数据，是解决并行可扩展性的根本办法。对分割友好（即并行友好）的数据结构有：

数组

哈希表

基树（Radix Tree）/稀疏数组

跳跃列表（skip list）

使用这些便于分割的数据结构，有利于我们通过数据分割来改善并行可扩展性。

除了使用合适的数据结构外，合理的分割指导规则也很重要：

读写分割：以读为主的数据与以写为主的数据分开；

路径分割：按独立的代码执行路径来分割数据；

专项分割：把经常更新的数据绑定到指定的CPU/线程中；

所有权分割：按CPU/线程个数对数据结构进行分割，把数据分割到per-cpu/per-thread中；

4种分割规则中，所有权分割是分割最彻底的。

以上这些多核并行编程内容基本上涵盖了Linux kernel中所有的并发编程关键技术。当然并行编程还有很多其他技术没有应用到Linux kernel中的，如无副作用的并行函数式编程技术（Erlang/Go等）、消息传递、MapReduce等等。

openmp并行程序在多核linux上最大化使用cpu的方法如下：

#include <stdio.h>

#include <stdlib.h>

#include <omp.h>

#include <time.h>

int main()

{

    long long i

    long double sum = .0

    long double sec = .0

    // Multi-thread compute start

    clock_t t1 = clock()

    #pragma omp parallel for

    for (i = 0 i < 1000000000 i++)

    {

        sum += i/100

    }

    clock_t t2 = clock()

    sec = (t2 - t1)

    //sec = (t2 - t1)

    printf("Program costs %.2Lf clock tick.\n", sec)

    exit(EXIT_SUCCESS)

}

以上代码中，#pragma omp parallel for

这一行的作用即是调用openmp的功能，根据检测到的CPU核心数目，将for (i = 0i <1000000000i++)这个循环执行过程平均分配给每一个CPU核心。

去掉#pragma omp parallel for这行，则和普通的串行代码效果一致。

注意，要使用openmp功能，在编译的时候需要加上-fopenmp编译参数。

以下是两种编译搭配两种代码出现的4种结果，可以很直观地看到效果：

1、代码里含有#pragma omp parallel for，编译参数有-fopenmp

Endys-MacBook-Pro:Desktop endy$ vi test.c

Endys-MacBook-Pro:Desktop endy$ gcc-6 test.c -o test -fopenmp

Endys-MacBook-Pro:Desktop endy$ ./test

Program costs 50202611.00 clock tick.

2、代码里含有#pragma omp parallel for，编译参数没有-fopenmp

Endys-MacBook-Pro:Desktop endy$ gcc-6 test.c -o test

Endys-MacBook-Pro:Desktop endy$ ./test

Program costs 4068178.00 clock tick.

3、代码里没有#pragma omp parallel for，编译参数有-fopenmp

Endys-MacBook-Pro:Desktop endy$ vi test.c

Endys-MacBook-Pro:Desktop endy$ gcc-6 test.c -o test -fopenmp

Endys-MacBook-Pro:Desktop endy$ ./test

Program costs 4090744.00 clock tick.

4、代码里没有#pragma omp parallel for，编译参数没有-fopenmp

Endys-MacBook-Pro:Desktop endy$ vi test.c

Endys-MacBook-Pro:Desktop endy$ gcc-6 test.c -o test

Endys-MacBook-Pro:Desktop endy$ ./test

Program costs 4170093.00 clock tick.

可以看出，只有在情况1下，openmp生效，其他3种情况下，均为单核运行，2、3、4结果较为接近，而1的运行结果大约相差25%。

值得注意的是，使用多核心的case 1竟然比单核的其他3种case慢了25%，原因是在这种单一的循环运算中，并行分配CPU任务的指令比直接执行下一个循环指令的效率更低。所以并不是用并行运算就一定能够提高运算效率的，要根据实际情况来判断。

并发出现在计算机系统的不同层面上，硬件异常处理程序、进程和Linux信号处理程序，以及应用程序中。

当一个应用正在等待来自慢速I/O设备（如磁盘）的数据到达时，内核会运行其他进程，使CPU保持繁忙。每个应用都可以按照类似的方式，通过交替执行I/O请求和其他有用的工作来利用并发。

和计算机交互的人要求计算机有同时执行多个任务的能力。如在打印一个文档时，调整一个窗口的大小。现代视窗系统利用并发来提供这种能力。每次用户请求某种 *** 作（如单击鼠标）时，一个独立的并发逻辑流被创建来执行这个 *** 作。

应用程序能够通过推迟其他 *** 作和并发地执行他们，并用并发来降低某些 *** 作的延迟。如一个动态内存分配器可以通过推迟合并，把它放到一个运行在较低优先级上的并发合并流中，在有空闲的CPU周期时充分利用这些空闲周期，从而降低单个free *** 作的延迟。

一个慢速的客户端可能会导致服务器拒绝为所有其他客户端服务，对于一个真正的服务器来说，可能期望它每秒为成百上千的客户端提供服务，由于一个慢速客户端导致拒绝为其他客户端服务，这是不能接受的。一个更好的办法是创建一个并发服务器，它为每个客户端创建一个单独的逻辑流。这就允许服务器同时为多个客户端服务，避免单个慢速客户端独占服务器。

现代计算机系统都配备了多核处理器，多核处理器包含有多个CPU，被划分为并发流的应用程序通常在多核机器上比单核机器上运行得快，因为这些流会并行执行，而不是交错执行。

使用应用级并发的应用程序成为并发程序（concurrent program）。现代 *** 作系统提供了三种基本的构造并发程序的方法。

---