大家好,又见面了,我是你们的朋友全栈君。
//
同步问题:
对共享数据的访问,需要同步,互斥。
在中断,抢占,多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/
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/161727.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...