大家好，又见面了，我是你们的朋友全栈君。
//
同步问题：
对共享数据的访问，需要同步，互斥。
在中断，抢占，多CPU，多线程 环境下尤其重要。
同步分为: 阻塞同步，非阻塞同步
阻塞同步有许多实现方式了：mutex, semaphore. 阻塞同步使用不当就可能造成死锁，活锁，优先级反转。
非阻塞同步：（现在流行三种）
wait free 很难实现，思想是本线程有限步就完成，完全不用理其余线程。
lock free 确保多个线程中，总有一个线程是运行着的。在全局上看就是这个模块一直运行中。
obstruction free 线程持续运行，当发现共享数据被改，回滚。
不难得出 Obstruction-free 是 Non-blocking synchronization 中性能最差的，而 Wait-free 性能是最好的，但实现难度也是最大的，因此 Lock-free 算法开始被重视，并广泛运用于当今正在运行的程序中，比如 linux 内核。
linux内核中就主要是实现了lock free
一般采用原子级的 read-modify-write 原语来实现 Lock-Free 算法，根据此理论，业界在原子操作的基础上提出了著名的 CAS（Compare – And – Swap）操作来实现 Lock-Free 算法，Intel 实现了一条类似该操作的指令：cmpxchg8。
//原语
CAS 原语负责将某处内存地址的值（1 个字节）与一个期望值进行比较，如果相等，则将该内存地址处的值替换为新值，CAS 操作伪码描述如下：
清单 1. CAS 伪码
Bool CAS(T* addr, T expected, T newValue)
{
if( *addr == expected )
{
*addr = newValue;
return true;
}
else
return false;
}
在实际开发过程中，利用 CAS 进行同步，代码如下所示：
清单 2. CAS 实际操作
do{
备份旧数据；
基于旧数据构造新数据；
}while(!CAS( 内存地址，备份的旧数据，新数据 ))
就是指当两者进行比较时，如果相等，则证明共享数据没有被修改，替换成新值，然后继续往下运行；如果不相等，说明共享数据已经被修改，放弃已经所做的操作，然后重新执行刚才的操作。容易看出 CAS 操作是基于共享数据不会被修改的假设，采用了类似于数据库的 commit-retry 的模式。当同步冲突出现的机会很少时，这种假设能带来较大的性能提升
修改前总是判断是否已经被修改过了，若无，则可完成本次修改
//内核无锁
1: double-checking lock. 即双重检测。
if( X )
{
aa;
if( X )
doit;
}
2: 原子锁。
内核中的原子锁是主要针对 整数与位操作的。 通常用内联实现，同时是实现为 汇编代码
3：非阻塞锁，lock free
1: spin lock, 自旋， 如果同步操作总是能在数条指令内完成，那么使用 Spin Lock 会比传统的 mutex lock 快一个数量级。
由于获得自旋锁后，是不能睡的，关中断的，所以在单核中，spin lock只是一个关中断的操作，而在多核中才是互斥的作用。
2： seq lock， 顺序锁，针对 写操作是小概率事件，而读操作是经常发生的行为。
所以写优先，即写的时候要进行互斥操作，但只与写操作互斥，而读操作则是每次读的前后都 要查看对象状态，若不同，则说明对象已被改了，要重新读，所以读操作可能会读很多次才成功。
linux中 seq lock 的实现原理依赖于一个序列计数器。
写者获得锁后， 要进行写前，会增加计数器 +1
而读者在读数据的前后，要读取序列的值，当前后不同，则要重新读。
缺点，seq lock 不能用于指针的数据，因读写同时发生时，可能出现无效的指针。
3: RCU, read-copy-update
同样针对 多读少写的情况，但是只对指针型的数据有效。即只能保护指针。
linux内核 的实现，当写者要写时，会先申请新内存，复制数据，然后在这个副本上改，最后更新原来的指针。这样整个写操作就只有一个指针赋值要互斥。
4：免锁， 单读单写的循环数组。
http://www.ibm.com/developerworks/cn/linux/l-cn-lockfree/
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/161727.html原文链接：https://javaforall.net
