转载

Android 并发编程起因

如需转载请联系听云College团队成员小尹邮箱：yinhy#tingyun.com

大多数的Android设备是多处理器的，Android3.0和以后的版本开始支持多处理器核心架构。多处理器对称Symmetric Multi-Processor缩写为SMP，定义了针对多核CPU如何共享内存的设计。SMP使得软件开发变得更加复杂，而且SMP工作在ARM类型处理器上比x86处理器上更具有挑战，x86测试运行正常的代码可能在ARM上可能会执行失败。

一、多处理器并发问题的理论知识

1. 内存一致模型：

内存一致模型描述了由硬件结构对于内存访问所作的保证，如你将先写一个值到内存地址A处，又写一个值到内存地址B处，模型会保证每一个处理器都会按照前面的顺序收到前面的变化。这样程序员感知到的会是这样：

所有的内存操作看起来是一个一个执行的

单独看任何一个处理器，指令都是按照程序定义的顺序执行的

实际上处理器很可能会对指令进行重排序或者延迟执行读写操作，请看下面一个例子：

线程1和线程2可能执行在不同的处理器上，在你编写多线程代码时要时刻考虑这个。当每个线程执行完成后，结果可能有如下多种：

单处理器的x86或者ARM是顺序一致的，但是大多数的SMP系统都不是。

2. 处理器一致性

X86的SMP处理器提供了处理器一致性的设计，相比顺序执行稍微若一些，它保证了：两次读不会重排序、两次写不会重排序，但是写后读操作不保证顺序。如下面的例子：

线程1期望使用A来标识它是否繁忙，线程2使用B来标识繁忙。两个线程通过简称对方是否繁忙来决定是否执行关键逻辑。在顺序执行的机器上这是对的，但是在SMP类型的x86或者ARM上，线程1里的写：A=true和读：reg1=B在线程2里可能观察到的是相反的顺序，着站在线程2角度观察到的情况可能变为：

这种不确定顺序问题的产生主要是由于处理器缓存造成的。

3. 处理器缓存行为

现代的处理器会有一个或者多个缓存来存储内存和处理器之间使用的数据，通常被标记为L1和L2之类的，数字越高离处理器越远。缓存内存会增加大小、耗费硬件硬件、更加耗电，因此Android上使用的ARM处理器通常只有一个小的L1缓存，很少或者没有L2/L3缓存。

从L1缓存里读取数据或者向其写入数据都是非常快的，大致是从内存读写速度的10到100倍速度执行，因此处理器会优先使用缓存执行更多的操作。缓存的写策略决定了什么时候将缓存的值写入主存，写贯穿的缓存会立即将结果写入内存，回写缓存会等到执行超过了空间范围且需要移除一些实例时执行。无论哪种方式，处理器会持续执行指令，可能在写会主存前执行了很多的指令（写贯穿方式不会等待写执行完才执行其他指令）。

每个处理器有自己的缓存导致了并发问题的产生。最简单的模型里，每个缓存不与其他缓存有关联不与其他缓存共享，只能通过写回内存后得到变更。读写内存耗费较长的时间会导致内部的多个线程交互变得极其缓慢，所以需要一个方式来实现缓存的数据共享，这通常叫做缓存一致性设计，是由处理器的缓存一致性模型决定的。

由于上述设计的存在，处理器1线程1执行写：A=1后处理器2线程2读取A，可能会从主存中得到A也可能从线程2自己的缓存中读到，这都会导致读取错误的值。此时为了保证内存访问的一致性，处理器1可以等到其他处理器都收到A的变更通知后再执行其他指令，但是这会带来严重的性能问题，放松对读写内存一致性的限制又会增加程序员的开发负担。

处理器缓存不是操作独立的字节，数据是按照缓存行读写的。对于很多的ARM处理器是32个字节。如果你从本地的主存读取数据，你可能会读取临近的一些值。写数据的时候需要从主存读取并更新，这样会导致可能会读取相近的数据并更改。

4. ARM在指令排序的薄弱

ARM提供了薄弱的内存一致性保障，它不保证读和写相互之间的顺序。如：

在x86上，这不会出问题，reg会得到41。线程2会观察到线程1存储的值的变化，并且按线程1的程序顺序。但是在ARM的多处理并发场景下，读和写可能被重排序，reg可能得到0也可能得到41，除非你精确的定义顺序，否则你不知道结果是什么。

5. 内存数据屏障

内存屏障提供了一种告知处理器内存操作的顺序的方式。屏障指令本身是无用的，容易造成高消耗。通常包括如下几种常见的指令：

读后读/写后写：

回到前面的例子：

线程1需要保证存储值到A要发生在存储值到B之前，这就是一个写后写的场景。线程2需要保证读取B发生在读取A之前，这就是个读后读的场景。如前面介绍的，读和写在ARM里会被观察到不同的执行顺序。我们可以这样解决：

写后写屏障保证了所有的观察者能够观测到线程1写A先发生写B后发生，同理线程2也可也保证读取顺序的可见一致性。

由于处理器架构处理内存模型的不同，上面的屏障在x86是不需要的，在ARM上是必须的。

读后写/写后读：

类似的，读后写或者写后读也可以加入对应的屏障指令保证顺序的一致和可见。不过要注意，x86只有“写后读”场景需要加入屏障保证内存一致性可见性，ARM所有场景都需要。

屏障指令：

不同的处理器提供了不同的屏障指令，如Sparc V8提供了上面的全部4种指令。X86的SSE2提供了一个全屏障指令，ARMv7提供了写后写和全屏障指令。全屏障指令即代表支持上面的4中场景。

需要注意的是，屏障指令只保证了指令执行的顺序，并不会对缓存一致性和同步做出保证，ARM的屏障指令对其他内核的缓存是没影响的。

内存屏障总结：

不同场景需要需要使用不同的内存屏障指令，如果准确的使用会是有益处的，但是代码的维护风险会变得很高。正因为如此，ARM处理器不提供不同种类的内存屏障指令，很多需要使用屏蔽指定时的原子语义是通过全量屏蔽指令完成的。

内存屏障最核心的设计是定义顺序，不是一个执行一堆刷新的指令，可以把它看做当前处理器核心执行指令的时间分割线。

6. 原子操作

原子操作可以保证一系列的执行步骤会像单一的一条指令一样。在ARM上，读写32字节这个最进本的操作时原子执行的。如果数据部是对其的，原子性会因此而丢失，不对齐的数据会跨两个缓存行，其他的处理器核心可以独立的看到一半的变更。因此，ARMv7文档声明它提供了“单独拷贝原子性”来应对全字节访问、“半字对齐”应对半字对齐场景、全字访问应对全字对齐场景。但是两个字（64-bit）访问就不是原子的了，除非位置是双字对齐且使用特殊的读写指令。

对内存执行更复杂的操作通常是读-改-写指令，需要读取数据、更改数据然后写回数据。处理器有多种不同的处理时限，ARM使用了叫做“Load Linked/Store Conditional”的技术实现：读-改-写操作执行处理旧的过期数据就会变得没有意义，如果两个核心对同一个地址执行原子增加操作，因为各自缓存的存在，任何一个都无法看到其他的变更，这种操作不是实际原子的。处理器的缓存一致性规则需要保证读改写RMW能够在多处理器内核环境下正常工作。

原子读改写不可以被理解为通过内存屏障实现，ARM的原子实现是没有内存屏障的。针对同一地址的一系列的原子读改写操作可以被其他的内核安装程序顺序观察到，但是原子和非原子操作混合是不能保证顺序的。

7. 原子性和屏障技术结合

可以通过自旋锁的技术实现了解二者的结合，核心思想是一个内存地址初始化锁值为0，如果一个线程需要访问一个关键区域，它会设置锁值为1，当关键区域代码执行完成，锁值被恢复为0。如果其他一个线程已经将锁值设置为1，那么当前线程会停下来自旋直到锁值恢复为0。

为了确保上述算法的实现，我们可以使用一个叫做比较交互的原子性读改写技术。这个功能需要三个参数：内存地址、期望值、新值。如果内存地址的值时期望值，则写入新值返回旧值。否则不作修改。一个小的变化可以产生另一个功能：比较设置，返回值变为boolean标识是否变更而不是返回旧值。两个功能类似，可以简称为CAS。结合屏障技术，一个自旋锁可以类似如下实现：

在对称多处理场景SMP，一个自旋锁是保护关键区域代码执行非常有效的手段。如果我们知道另一个线程正在关键指令并占有锁，我们会浪费一些循环来等到我们得到执行机会。然而，如果其他占用锁的线程和当前线程碰巧在同一个处理器核心执行，我们的自旋会是一种浪费，因为其他线程不会有进展除非操作系统非配给它执行的机会（通过迁移其他线程到另一个核心或者抢占当前线程来执行）。一个更合理的优化方式是自旋几次后将线程交给操作系统的原始实现：让线程进程睡眠状态知道执行线程执行完成。

内存屏障是必须的，用来保证其他线程观察到锁值的变化优先于关键区域的内存操作的变化。同样，我们需要保证对关键内存的操作变化的要先于锁释放执行和被观察到，因此完整的实现如下：

如前面提到的，最后执行的原子写操作时ARM和x86都提供的实现，不同于原子的读改写操作，原子写不保证其他线程能够立刻观测到这个值的变更，但这不是问题，我们只是需要保证其他线程不进入关键代码区。

申请一个自旋锁时，需要先执行CAS然后执行内存屏障，通常叫做acquiring操作。释放一个自旋锁时，需要先执行内存屏障然后执行有原子写，通常叫做releasing操作。

对于不同的处理器架构，实现上会做出相应的优化。如x86上只有写后读的屏障才需要，因此释放场景的屏障操作在x86上是不需要的。将一些操作移到关键代码区里会是安全的（但反之就不一定），这样通过将一些关联的操作代码放到一起执行可以提升效率，因为从内存加载是很慢的操作，但处理器可以继续执行不依赖前面加载内存数据结果的指令。