4.锁--无锁编程以及CAS

时间:2021-09-15 12:08:51

无锁编程以及CAS

无锁编程 / 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,由用户决定兴许操作。
4.锁--无锁编程以及CAS
Bool CAS(T* addr, T expected, T newValue) 
 { 
      if( *addr == expected ) 
     { 
          *addr =  newValue; 
           return true; 
     } 
     else 
           return false; 
 }
4.锁--无锁编程以及CAS

 

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);
 

Refs