必威体育Betway必威体育官网
当前位置:首页 > IT技术

lock-free介绍

时间:2019-10-10 12:14:29来源:IT技术作者:seo实验室小编阅读:53次「手机版」
 

lock free

无锁编程 / lock-free / 非阻塞同步

无锁编程,即不使用锁的情况下实现多线程之间的变量同步,也就是在没有线程被阻塞的情况下实现变量的同步,所以也叫非阻塞同步(Non-blocking Synchronization)。

实现非阻塞同步的方案称为“无锁编程算法”( Non-blocking algorithm)。

lock-free是目前最常见的无锁编程的实现级别(一共三种级别)。

为什么要 Non-blocking sync ?

使用lock实现线程同步有很多缺点:

* 产生竞争时,线程被阻塞等待,无法做到线程实时响应。

* dead lock。

* live lock。

* 优先级翻转。

* 使用不当,造成性能下降。

如果在不使用 lock 的情况下,实现变量同步,那就会避免很多问题。虽然目前来看,无锁编程并不能替代 lock。

实现级别

非同步阻塞的实现可以分成三个级别:wait-free/lock-free/obstruction-free。

wait-free

是最理想的模式,整个操作保证每个线程在有限步骤下完成。

保证系统级吞吐(system-wide throughput)以及无线程饥饿。

截止2011年,没有多少具体的实现。即使实现了,也需要依赖于具体cpu

lock-free

允许个别线程饥饿,但保证系统级吞吐。

确保至少有一个线程能够继续执行。

wait-free的算法必定也是lock-free的。

obstruction-free

在任何时间点,一个线程被隔离为一个事务进行执行(其他线程suspended),并且在有限步骤内完成。在执行过程中,一旦发现数据被修改(采用时间戳版本号),则回滚。

也叫做乐观锁,即乐观并发控制(OOC)。事务的过程是:1读取,并写时间戳;2准备写入,版本校验;3校验通过则写入,校验不通过,则回滚。

lock-free必定是obstruction-free的。

CAS原语

LL/SC, atom read-modify-write

如果CPU提供了Load-Link/Store-conditional(LL/SC)这对指令,则就可以轻松实现变量的CPU级别无锁同步。

LL [addr],dst:从内存[addr]处读取值到dst。

SC value,[addr]:对于当前线程,自从上次的LL动作后内存值没有改变,就更新成新值。

上述过程就是实现lock-free的 read-modify-write 的原子操作。

CAS (Compare-And-Swap)

LL/SC这对CPU指令没有实现,那么就需要寻找其他算法,比如CAS。

CAS是一组原语指令,用来实现多线程下的变量同步。

在 x86 下的指令CMPXCHG实现了CAS,前置LOCK既可以达到原子性操作。截止2013,大部分多核处理器均支持CAS。

CAS原语有三个参数,内存地址,期望值,新值。如果内存地址的值==期望值,表示该值未修改,此时可以修改成新值。否则表示修改失败,返回false,由用户决定后续操作。

Bool CAS(T* addr, T expected, T newValue) 
 { 
      if( *addr == expected ) 
     { 
          *addr =  newValue; 
           return true; 
     } 
     else 
           return false; 
 }

ABA 问题

thread1意图对val=1进行操作变成2,cas(*val,1,2)。

thread1先读取val=1;thread1被抢占(preempted),让thread2运行。

thread2 修改val=3,又修改回1。

thread1继续执行,发现期望值与“原值”(其实被修改过了)相同,完成CAS操作。

使用CAS会造成ABA问题,特别是在使用指针操作一些并发数据结构时。

解决方案

ABAʹ:添加额外的标记用来指示是否被修改。

语言实现

java demo

Atomicinteger atom = new AtomicInteger(1);

boolean r = atom.compareAndSet(1, 2);

C# demo

int i=1;

Interlocked.Increment(ref i);

内存模型(Memory Model)对细粒度锁的影响

在多线程系统中,当多个线程同时访问共享的内存时,就需要一个规范来约束不同的线程该如何与内存交互,这个规范就称之为内存模型(Memory Model)。

顺序一致性内存模型(Sequential Consistency Memory Model)则是内存模型规范中的一种。在这个模型中,内存与访问它的线程保持独立,通过一个控制器(Memory controller)来保持与线程的联系,以进行读写操作。在同一个线程内的,读写操作的顺序也就是代码指定的顺序。但多个线程时,读写操作就会与其他线程中的读写操作发生交错。

如上图中所示,Thread 1 中在写入 Value 和 Inited 的值,而 Thread 2 中在读取 Inited 和 Value 的值到 Ri 和 Rv 中。由于在内存控制器中发生重排(Memory Reordering),最终的结果可能有很多种情况,如下表所示。

顺序一致性内存模型非常的直观,也易于理解。但实际上,由于该模型在内存硬件实现效率上的限制,导致商用的 CPU 架构基本都没有遵循该模型。一个更贴近实际的多处理器内存模型更类似于下图中的效果。

也就是说,每个 CPU 核都会有其自己的缓存模型,例如上图中的 Level 1 cache 和 Level 2 Cache,用以缓存最近使用的数据,以提升存取效率。同时,所有的写入数据都被缓冲到了 Write Buffer 缓冲区中,在数据在被刷新至缓存前,处理器可以继续处理其他指令。这种架构提升了处理器的效率,但同时也意味着我们不仅要关注 Memory,同时也要关注 Buffer 和 Cache,增加了复杂性。

上图所示为缓存不一致问题(Incoherent Caches),当主存(Main Memory)中存储着 Value=5,Inited=0 时,Processor 1 就存在着新写入 Cache 的值没有被及时刷新至 Memory 的问题,而 Processor 2 则存在着读取了 Cache 中旧值的问题。

显然,上面介绍着内存重排和缓存机制会导致混乱,所以实际的内存模型中会引入锁机制(Locking Protocol)。通常内存模型会遵循以下三个规则:

  • Rule 1:当线程在隔离状态运行时,其行为不会改变;
  • Rule 2:读操作不能被移动到获取锁操作之前;
  • Rule 3:写操作不能被移动到释放锁操作之后;

Rule 3 保证了在释放锁之前,所有写入操作已经完成。Rule 2 保证要读取内存就必须先获取锁,不会再有其他线程修改内存。Rule 1 则保证了获得锁之后的操作行为是顺序的。

在体现锁机制(Locking Protocol)的价值的同时,我们也会意识到它所带来的限制,也就是限制了编译器和 CPU 对程序优化的自由。

我们知道,.NET Framework 遵循 ECMA 标准,而 ECMA 标准中则定义了较为宽松的内存访问模型,将内存访问分为两类:

  • 常规内存访问(Ordinary Memory Access)
  • 易变内存访问(Volatile Memory Access)

其中,易变内存访问是特意为 "volatile" 设计,它包含如下两个规则:

  1. 读和写操作不能被移动到 volatile-read 之前;
  2. 读和写操作不能被移动到 volatile-write 之后;

对于那些没有使用 "lock" 和 "volatile" 的程序片段,编译器和硬件可以对常规内存访问做任何合理的优化。反过来讲,内存系统仅需在应对 "lock" 和 "volatile" 时采取缓存失效和刷新缓冲区等措施,这极大地提高了性能。

顺序一致性(Sequential Consistency)的要求描述了程序代码描述的顺序与内存操作执行的顺序间的关系。多数编程语言都提供顺序一致性的支持,例如在 C# 中可以将变量标记为 volatile。

A volatile read has "acquire semantics" meaning that the read is guaranteed to occur prior to any references to memory that occur after the read instruction in the CIL instruction sequence

A volatile write has "release semantics" meaning that the write is guaranteed to hAPPen after any memory references prior to the write instruction in the CIL instruction sequence.

相关阅读

分享到:

栏目导航

推荐阅读

热门阅读