大家好，又见面了，我是你们的朋友全栈君。

简单的笔记，未完待续

一道题：

无锁化编程有哪些常见方法？

• 针对计数器，可以使用原子加
• 只有一个生产者和一个消费者，那么就可以做到免锁访问环形缓冲区（Ring Buffer）
• RCU（Read-Copy-Update），新旧副本切换机制，对于旧副本可以采用延迟释放的做法 
• CAS（Compare-and-Swap），如无锁栈，无锁队列等待

解析：

一、RCU

        RCU是Linux 2.6内核系统新的锁机制 RCU(Read-Copy Update)。参考：http://www.ibm.com/developerworks/cn/linux/l-rcu/

        众所周知，为了保护共享数据,需要一些同步机制,如自旋锁(spinlock)，读写锁(rwlock)，它们使用起来非常简单,而且是一种很有效的同步机制，在UNIX系统和Linux系统中得到了广泛的使用。但是随着计算机硬件的快速发展，获得这种锁的开销相对于CPU的速度在成倍地增加，原因很简单，CPU的速度与访问内存的速度差距越来越大，而这种锁使用了原子操作指令，它需要原子地访问内存，也就说获得锁的开销与访存速度相关。会导致处理器流水线停滞或刷新，因此它的开销相对于CPU速度而言就越来越大。

        RCU并不是新的锁机制，它只是对Linux内核而言是新的。早在二十世纪八十年代就有了这种机制，而且在生产系统中使用了这种机制，但这种早期的实现并不太好，在二十世纪九十年代出现了一个比较高效的实现，而在linux中是在开发内核2.5.43中引入该技术的并正式包含在2.6内核中。

        RCU(Read-Copy Update)，顾名思义就是
读-拷贝修改，它是基于其原理命名的。
对于被RCU保护的共享数据结构，读者不需要获得任何锁就可以访问它，但写者在访问它时首先拷贝一个副本，然后对副本进行修改，最后使用一个回调（callback）机制在适当的时机把指向原来数据的指针重新指向新的被修改的数据。这个时机就是所有引用该数据的CPU都退出对共享数据的操作。写者在访问被RCU保护的共享数据时不需要和读者竞争任何锁，只有在有多于一个写者的情况下需要获得某种锁以与其他写者同步。允许多个读者和写者并发执行。
RCU 技术的核心是写操作分为写和更新两步，允许读操作在任何时候无阻碍的运行，换句话说，就是通过
延迟写来提高同步性能。

         因此RCU实际上是一种改进的rwlock，读者几乎没有什么同步开销，它不需要锁，不使用原子指令。

二、CAS

参考：透过 Linux 内核看无锁编程

非阻塞型同步的三种方案：

1. Wait-free

   Wait-free 是指任意线程的任何操作都可以在有限步之内结束，而不用关心其它线程的执行速度。 Wait-free 是基于 per-thread 的，可以认为是 starvation-free 的。非常遗憾的是实际情况并非如此，采用 Wait-free 的程序并不能保证 starvation-free，同时内存消耗也随线程数量而线性增长。目前只有极少数的非阻塞算法实现了这一点。

2. Lock-free

   Lock-Free 是指能够确保执行它的所有线程中至少有一个能够继续往下执行。由于每个线程不是 starvation-free 的，即有些线程可能会被任意地延迟，然而在每一步都至少有一个线程能够往下执行，因此系统作为一个整体是在持续执行的，可以认为是 system-wide 的。所有 Wait-free 的算法都是 Lock-Free 的。

3. Obstruction-free

   Obstruction-free 是指在任何时间点，一个孤立运行线程的每一个操作可以在有限步之内结束。只要没有竞争，线程就可以持续运行。一旦共享数据被修改，Obstruction-free 要求中止已经完成的部分操作，并进行回滚。 所有 Lock-Free 的算法都是 Obstruction-free 的。

        CAS（Compare – And – Swap）操作业界在原子操作的基础上提出的，用来实现Lock-Free算法。CAS 原语负责将某处内存地址的值（1 个字节）与一个期望值进行比较，如果相等，则将该内存地址处的值替换为新值，CAS 操作伪码描述如下：

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