瓜田纳履之黄金满地

《深入理解并行编程》整理笔记

2016-07-23  本文已影响1954人  初级造轮师

目录

<a id="1."></a>1.并发编程的目标

相对于串行编程来说,并行编程有如下三个主要目标:

所以，并没有完美的环境，需要我们在性能、生产率、通用性之间进行权衡。

对于电脑或者手机的结构来讲：从底层硬件、固件、操作系统核心、系统库、中间软件到上层应用；越往上层，生产率越来越重要。越往下层，性能和通用性越来越重要。因为在上层需要进行大量开发工作，必须考虑通用性来降低成本，而下层性能的损失极难在上层恢复。

所以，性能和通用性是底层开发主要关心的地方

<a id="2."></a>2.并行访问控制 - 是什么使并行编程变得复杂?

（需要注意的是:并行计算的困难,有人为因素的原因与并行计算本身的技术 属性的原因,二者给并行计算带来的困难是差不多的。这是由于我们需要人为干 涉并行计算的过程,人和计算机间的双向交互需要人和机器都执行同等复杂的操 作。因此,采用抽象或者数学分析将极大的限制实用性。）

<a id="3."></a>3.关于硬件 - 对并行编程造成的障碍

（大多数人根据直觉就知道,在系统间传递消息要比在单个系统上执行简单计 算更加耗时。不过,在共享同一块内存的系统的线程间传递消息是不是也更加耗 时,这点可就不一定了。本章主要关注共享内存系统中的同步和通信的开销,只 涉及了一些共享内存并行硬件设计的皮毛）

单线程

  1. CUP流水线：

    • 过去微处理器在处理下一条指令之前，至少需要取址、解码和执行3个周期来完成本条指令；后来的CPU可以同时处理多条指令，通过一条很长的‘流水线’来控制CPU内部的指令流。
    • 带有长流水线的 CPU 想要达到最佳性能,需要程序给出高度可预测的控制流。在这种程序中,流水线可以一直保持在满状态,CPU 高速运行。
    • （如果程序中带有许多循环,且循环计数都比较小;或者面向对象 的程序中带有许多虚对象,每个虚对象都可以引用不同的实对象,而这些实对象 都有频繁被调用的成员函数的不同实现,此时 CPU 很难或者完全不可能预测某 个分支的走向。这样 CPU 要么等待控制流进行到足以知道分支走向的方向时, 要么干脆猜测——由于此时程序的控制流不可预测——CPU 常常猜错。在这两 种情况中,流水线都是空的,CPU 需要等待流水线被新指令填充,这将大幅降 低 CPU 的性能）

  2. 内存引用：

    • 过去，微处理器从内存读取一个值的时间比执行一条指令的时间短。现在它可以在这段时间执行上百 条甚至上千条指令
    • 虽然现代微型计算机上的大型缓存极大地减少了内存访问延迟,但是只有高 度可预测的数据访问模式才能让缓存发挥最大效用。不幸的是,一般像遍历链表 这样的操作的内存访问模式非常难以预测——毕竟如果这些模式是可预测的,我 们也就不会被指针所困扰了,是吧?内存引用常常是影响现代 CPU 性能的重要因素。

多线程

  1. 原子操作

    • 原子操作的概念在某种意义上与CPU流水线上的一次执行一条的汇编操作冲突了。现代CPU为了提高性能让CPU能够乱序执行原子操作。
    • 原子操作通常只用于数据的单个元素。由于许多并行算法都需要在更新多个数据元素时，保证正确的执行顺序，大多数CPU都提供了内存屏障。它也是影响性能的因素之一。

  2. 内存屏障

    • 下面是一个简单的基于锁的 临界区。
    1 spin_lock(&mylock);
2 a = a + 1;
3 spin_unlock(&mylock);
    • 如果CPU没有顺序执行上诉语句，a会在没有锁的情况下加一，导致我们无法得到精确的值。为防止这种情况发生，锁操作原语必须包含显示或隐式的内存屏障。当然这样会降低CPU性能。

  3. Cache Miss - 缓存未命中

    • 现代CPU使用大容量的高速缓存来降低由于较低的内存访问速度带来的性能惩罚。但是，CPU高速缓存事实上对多CPU间频繁访问的变量起反效果。
    • 当某个CPU想去更改变量的值时，这个变量刚被其他CPU修改过而存在他的缓存中，这将导致代价高昂的Cache Miss

  4. I/O操作

    • 其实缓存未命中可以视为CPU之间的I/O操作，当然相比于其它的I/O操作，这个代价最低廉。
    • I/O操作设计网络、大容量存储器，或者（更糟的）人类本身，I/O操作对性能的影响远远大于以上提到的各种障碍。

<a id="4."></a>4.这种障碍的实际开销

硬件体系结构

如果 CPU0 在对一个变量执行“比较并交换”(CAS- Compare and Swap)操作,而该变量所在的缓存线在 CPU7 的高速缓存中,就会发生以下经过简化的事件序列:
1. CPU0 检查本地高速缓存,没有找到缓存线。
2. 请求被转发到 CPU0 和 CPU1 的互联模块,检查 CPU1 的本地高速缓存,
没有找到缓存线。
3. 请求被转发到系统互联模块,检查其他三个管芯,得知缓存线被 CPU6
和 CPU7 所在的管芯持有。
4. 请求被转发到 CPU6 和 CPU7 的互联模块,检查这两个 CPU 的高速缓存,
在 CPU7 的高速缓存中找到缓存线。
5. CPU7 将缓存线发送给所属的互联模块,并且刷新自己高速缓存中的缓
存线。
6. CPU6 和 CPU7 的互联模块将缓存线发送给系统互联模块。
7. 系统互联模块将缓存线发送给 CPU0 和 CPU1 的互联模块。
8. CPU0 和 CPU1 的互联模块将缓存线发送给 CPU0 的高速缓存。
9. CPU0 现在可以对高速缓存中的变量执行 CAS 操作了。
关于CAS

操作的开销

一些在并行程序中很重要的常见操作开销如下图所示。该系统的时钟周期为0.6ns。在表格的第三列,操作被标准化到了整个时钟周期,称作“比率”。

Operation Cost (ns) Ratio
Clock period 0. 1.0
Best-case CAS 37.9 63.2
Best-case lock 65.6 109.3
Single cache miss 139.5 232.5
CAS cache miss 306.0 510.0
Comms Fabric 3,000 5,000
Global Comms 130,000,000 216,000,000

（最好情况下的CAS操作消耗大概40纳秒,超过60个时钟周期。这里的“最 好情况”是指对某一个变量执行CAS操作的CPU正好是最后一个操作该变量的 CPU,所以对应的缓存线已经在 CPU 的高速缓存中了,类似地,最好情况下的 锁操作(一个“round trip 对”包括获取锁和随后的释放锁)消耗超过 60 纳秒, 超过 100 个时钟周期。这里的“最好情况”意味着用于表示锁的数据结构已经在 获取和释放锁的 CPU 所属的高速缓存中了。锁操作比 CAS 操作更加耗时,是因
深入理解并行编程
为锁操作的数据结构中需要两个原子操作。
缓存未命中消耗大概 140 纳秒,超过 200 个时钟周期。需要在存储新值时查
询变量的旧值的 CAS 操作,消耗大概 300 纳秒,超过 500 个时钟周期。想想这 个,在执行一次 CAS 操作的时间里,CPU 可以执行 500 条普通指令。这表明了 细粒度锁的局限性。）

<a id="5."></a>5.并行编程领域的基本工具

<a id="5.1"></a>5.1 脚本语言

Linux shell 脚本语言用一种简单而又有效的方法处理并行化。比如,假设你 有一个叫做 compute_it 的程序,你需要用不同的参数运行两次。那么只需要这样 写:

1 compute_it 1 > compute_it.1.out &
2 compute_it 2 > compute_it.2.out &
3 wait
4 cat compute_it.1.out
5 cat compute_it.2.out

小问题:可是这个愚蠢透顶的 shell 脚本并不是真正的并行程序!这些垃 圾有什么用??

<a id="5.2"></a> 5.2 POSIX API - 支持多进程虚拟化和POSIX线程

(本节浅入浅出地介绍了 POSIX 环境,包括广泛应用的 pthreads[Ope97]。3.2.1 节介绍了 POSIX 的 fork()和相关原语,3.2.2 节介绍了线程创建和撤销,3.2.3 节 介绍了 POSIX locking 机制,最后的 3.4 节展示了 Linux 内核中的类似操作。)

1 int x = 0;
2 int pid;
3
4 pid = fork();
5 if (pid == 0) { /* child */
6 x = 1;
7 printf("Child process set x=1\n");
8 exit(0);
9}
10 if (pid < 0) { /* parent, upon error */ 11 perror("fork");
12 exit(-1);
13 }
14 waitall();
15 printf("Parent process sees x=%d\n", x);

for (;;) {
   pid = wait(&status);
if
} }
(pid == -1) {
if (errno == ECHILD)
break;
perror("wait");
exit(-1);

// pthread_create()的第一个参数是指向 pthread_t 类型
的指针,用于存放将要创建线程的线程 ID 号,第二个 NULL 参数是一个可选的 指向 pthread_attr_t 结构的指针,第三个参数是新线程将要调用的函数(在本例 中是 mythread()),最后一个 NULL 参数是传递给 mythread()的参数。

1 pthread_mutex_t lock_a = PTHREAD_MUTEX_INITIALIZER; 
2 pthread_mutex_t lock_b = PTHREAD_MUTEX_INITIALIZER; 
3 int x = 0;
4
5 void *lock_reader(void *arg)
6{
7   int i;
8   int newx = -1;
9   int oldx = -1;
10  pthread_mutex_t *pmlp = (pthread_mutex_t *)arg;
11
12  if (pthread_mutex_lock(pmlp) != 0) {
13      perror("lock_reader:pthread_mutex_lock");
14      exit(-1);
15  }
16  for (i = 0; i < 100; i++) {
17      newx = ACCESS_ONCE(x);
18      if (newx != oldx) {
19          printf("lock_reader(): x = %d\n", newx);
20      }
21      oldx = newx;
22      poll(NULL, 0, 1);
23  }
24  if (pthread_mutex_unlock(pmlp) != 0) {
25      perror("lock_reader:pthread_mutex_unlock");
26      exit(-1);
27  }
28  return NULL;
29}
30
31 void *lock_writer(void *arg)
32 {
33      int i;
34      pthread_mutex_t *pmlp = (pthread_mutex_t *)arg;
35
36      if (pthread_mutex_lock(pmlp) != 0) {
37          perror("lock_reader:pthread_mutex_lock");
38          exit(-1);
39      }
40      for (i = 0; i < 3; i++) {
41          ACCESS_ONCE(x)++;
42          poll(NULL, 0, 5);
43      }
44      if (pthread_mutex_unlock(pmlp) != 0) {
45          perror("lock_reader:pthread_mutex_unlock");
46          exit(-1);
47      }
48      return NULL;
49 }

<a id="5.3"></a> 5.3 原子操作

* 读写锁在临界区最小时开销最大,考虑到这一点,那么最好 能有其他手段来保护极其短小的临界区。
* gcc 编译器 供了许多附加的原子操作,包括__sync_fetch_and_sub()、 __sync_fetch_and_or()、__sync_fetch_and_and()、__sync_fetch_and_xor()和 __sync_fetch_and_nand()原语,这些操作都返回参数的原值。如果你一定需要变 量的新值,可以使用__sync_add_and_fetch()、__sync_sub_and_fetch()、 __sync_or_and_fetch()、__sync_and_and_fetch()、__sync_xor_and_fetch()和 __sync_nand_and_fetch()原语。
* 有一对原语 供了经典的“比较并交换”操作,__sync_bool_compare_and_swap()和__sync_val_compare_and_swap()。
* __sync_synchronize()原语是一个“内存屏障”,它限制编译器和 CPU 对指令 乱序执行的优化。在某些情况下,只限制编译器对指令 的优化就足够了,CPU 的优化可以保留,此时就需要使用 barrier()原语

<a id="5.4"></a>5.4 Linux 内核中类似 POSIX 的操作

(不幸的是,远在各种标准委员会出现之前,线程操作,加锁、解锁原语和原 子操作就已经存在了。因此,这些操作有很多种变体。用汇编语言实现这些操作 也十分常见,不仅因为历史原因,还因为可以在某些特定场合获得更好的性能。 比如,gcc 的_sync族原语都是 供 memory-ordering 的语义,这激励许多程序 员实现自己的函数,来满足许多不需要 memory ordering 语义的场景。)

POSIX 原语与 Linux 内核函数对应表

Category POSIX Linux Kernel
Thread Management pthread_t struct task_struct
pthread_create() kthread_create
pthread_exit() kthread_should_stop() (rough)
pthread_join() kthread_stop() (rough)
poll(NULL, 0, 5) schedule_timeout_interruptible()
POSIX Locking pthread_mutex_t spinlock_t (rough)
struct mutex
PTHREAD_MUTEX_INITIALIZER DEFINE_SPINLOCK()
DEFINE_MUTEX()
pthread_mutex_lock() spin_lock() (and friends)
mutex_lock() (and friends)
pthread_mutex_unlock() spin_unlock() (and friends)
mutex_unlock()
POSIX Reader-Writer pthread_rwlock_t rwlock_t (rough)
Locking struct rw_semaphore
PTHREAD_RWLOCK_INITIALIZER DEFINE_RWLOCK()
DECLARE_RWSEM()
pthread_rwlock_rdlock() read_lock() (and friends)
down_read() (and friends)
pthread_rwlock_unlock() read_unlock() (and friends)
up_read()
thread_rwlock_wrlock() write_lock() (and friends)
down_write() (and friends)
pthread_rwlock_unlock() write_unlock() (and friends)
up_write()
Atomic Operations C Scalar Types atomic_t
atomic64_t
__sync_fetch_and_add() atomic_add_return()
atomic64_add_return()
__sync_fetch_and_sub() atomic_sub_return()
atomic64_sub_return()
__sync_val_compare_and_swap() cmpxchg()
__sync_lock_test_and_set() xchg() (rough)
__sync_synchronize() smp_mb()

比较 POSIX、gcc 原语和 Linux 内核中使用的版本。精准的对应关系很难给出,因为 Linux 内核有各种各样的加 锁、解锁原语,gcc 则有很多 Linux 内核中不能直接使用的原子操作。当然,一 方面,用户态的代码不需要 Linux 内核中各种类型的加锁、解锁原语,同时另一 方面,gcc 的原子操作也可以直接用 cmpxchg()来模拟。

<a id="6."></a>6.计数

（计算机能做的事情里,计数也许是最简单也是最自然的了。不过在一台大型 的共享内存的多处理器系统上高效并且 scalably(可扩展性) 的计数,仍然具有相当的挑战性。 更进一步,计数背后隐含概念的简单性使得我们可以探索并发中的基本问题,而 无需被繁复的数据结构或者复杂的同步原语干扰。因此,计数是并行编程的极佳 切入对象。）

把一个数从1自增加到10亿(使用多线程来提高效率)

  1. 不加锁，非原子访问，最终可能只得到5亿左右。这与CUP读写原理有关，读的时候从主存复制一份到缓存，写入时更新主存
  2. 加锁-互斥锁，能够得到正确值，但性能太差。

    图 4.4 是另一种全局原子自增的视角。为了让每个 CPU 得到机会增加一个指定全局变量,包含变量的缓存线需要在所有 CPU 间传播,如图中红箭头所示。这种传播相当耗时,从而导致了糟糕性能。
  3. 统计计数器，给每个线程一个计数器，那么总的计数值就是所有线程计数器值的简单相加。

    这种做法不再需 要代价昂贵的跨越整个计算机系统的通信。但是这种在“更新”上扩展极佳的方 法,在存在大量线程时,会带来“读取”上的巨大代价。
    如何能在保留“更新”侧扩展性的同时,减少“读取”侧产生的代价？
  4. 结果一致的实现，之前每次读取前，都要更新所有线程的计数器以保证数据一致性。现在使用一种弱读取方式，只是在最终计算完成之后才更新得到正确的值。

近似上限计数器-另一种设计

可是对于由某一个线程创建，但由另一个线程释放就无法处理了。

那么。。。

<a id="7."></a>7.RCU(Read-Copy Update) 基础

<a id="7.1"></a>RCU概念

所以说,会有这样的 RCU 出现这样的情况吗?


<a id="7.2"></a>1.Linux中RCU机制的原理

  1. 效率问题。锁机制的实现需要对内存的原子化访问，这种访问操作会破坏流水线操作，降低了流水线效率。这是影响性能的一个因素。另外，在采用读写锁机制的情况下，写锁是排他锁，无法实现写锁与读锁的并发操作，在某些应用下回降低性能。

  2. 扩展性问题。当系统中CPU数量增多的时候，采用锁机制实现数据的同步访问效率偏低。并且随着CPU数量的增多，效率降低，由此可见锁机制实现的数据一致性访问扩展性差。

为了解决上述问题，Linux中引进了RCU机制。该机制在多CPU的平台上比较适用，对于读多写少的应用尤其适用。RCU的思路实际上很简单，下面对其进行描述：

  1. 对于读操作，可以直接对共享资源进行访问，但是前提是需要CPU支持访存操作的原子化，现代CPU对这一点都做了保证。但是RCU的读操作上下文是不可抢占的（这一点在下面解释），所以读访问共享资源时可以采用read_rcu_lock()，该函数的工作是停止抢占。

  2. 对于写操作，其需要将原来的老数据作一次备份（copy），然后对备份数据进行修改，修改完毕之后再用新数据更新老数据，更新老数据时采用了rcu_assign_pointer（）宏，在该函数中首先屏障一下memory，然后修改老数据。这个操作完成之后，需要进行老数据资源的回收。操作线程向系统注册回收方法，等待回收。采用数据备份的方法可以实现读者与写者之间的并发操作，但是不能解决多个写着之间的同步，所以当存在多个写者时，需要通过锁机制对其进行互斥，也就是在同一时刻只能存在一个写者。

  3. 在RCU机制中存在一个垃圾回收的daemon(后台驻留程序)，当共享资源被update之后，可以采用该daemon实现老数据资源的回收。回收时间点就是在update之前的所有的读者全部退出。由此可见写者在update之后是需要睡眠等待的，需要等待读者完成操作，如果在这个时刻读者被抢占或者睡眠，那么很可能会导致系统死锁。因为此时写者在等待读者，读者被抢占或者睡眠，如果正在运行的线程需要访问读者和写者已经占用的资源，那么死锁的条件就很有可能形成了。

<a id="7.3"></a>可睡眠 RCU 实现

从上述分析来看，RCU思想是比较简单的，其核心内容紧紧围绕“写时拷贝”，采用RCU机制，能够保证在读写操作共享资源时，基本不需要取锁操作，能够在一定程度上提升性能。但是该机制的应用是有条件的，对于读多写少的应用，机制的开销比较小，性能会大幅度提升，但是如果写操作较多时，开销将会增大，性能不一定会有所提升。总体来说，RCU机制是对rw_lock的一种优化。

<a id="smp"></a>SMP对称多处理结构：

<a id="why"></a>为何苹果双核性能比安卓4核要高

<a id="java"></a>Java

  1. Java是一门面向对象编程语言，不仅吸收了C++语言的各种优点，还摒弃了C++里难以理解的多继承、指针等概念，因此Java语言具有功能强大和简单易用两个特征。Java语言作为静态面向对象编程语言的代表，极好地实现了面向对象理论，允许程序员以优雅的思维方式进行复杂的编程。
  2. Java具有简单性、面向对象、分布式、健壮性、安全性、平台独立与可移植性、多线程、动态性等特点。
  3. Java可以编写桌面应用程序、Web应用程序、分布式系统和嵌入式系统应用程序等。
  4. 应用：
    • Android应用
    • 在金融业应用的服务器程序
    • 网站
    • 嵌入式领域
    • 大数据技术。。。

<a id="tpc"></a>数据库常用压测工具

Tpcc-mysql

TPC(Tracsactin Processing Performance Council)事务处理性能协会是一个评价大型数据库系统软硬件性能的非盈利的组织，TPC-C是TPC协会制定的，用来测试典型的复杂OLTP系统的性能

上一篇 下一篇

猜你喜欢

热点阅读