大家好,又见面了,我是你们的朋友全栈君。
一、非阻塞同步(Non-blocking Synchronization)
1. 无锁编程 / lock-free / 非阻塞同步
无锁编程,即不使用锁的情况下实现多线程之间的变量同步,也就是在没有线程被阻塞的情况下实现变量的同步,所以也叫非阻塞同步(Non-blocking Synchronization)。
实现非阻塞同步的方案称为“无锁编程算法”( Non-blocking algorithm)。
lock-free是目前最常见的无锁编程的实现级别(一共三种级别):
- wait-free
- lock-free
- obstruction-free
2. 为什么要 Non-blocking sync ?
使用lock实现线程同步有很多缺点:
* 产生竞争时,线程被阻塞等待,无法做到线程实时响应。
* dead lock。
* live lock。
* 优先级翻转。
* 使用不当,造成性能下降。
3. wait-free
是最理想的模式,整个操作保证每个线程在有限步骤下完成。
保证系统级吞吐(system-wide throughput)以及无线程饥饿。
截止2011年,没有多少具体的实现。即使实现了,也需要依赖于具体CPU。
4. lock-free
允许个别线程饥饿,但保证系统级吞吐。
确保至少有一个线程能够继续执行。
wait-free的算法必定也是lock-free的。
5. obstruction-free
在任何时间点,一个线程被隔离为一个事务进行执行(其他线程suspended),并且在有限步骤内完成。
在执行过程中,一旦发现数据被修改(采用时间戳、版本号),则回滚。
也叫做乐观锁,即乐观并发控制(OOC)。
事务的过程是:1读取,并写时间戳;2准备写入,版本校验;3校验通过则写入,校验不通过,则回滚。
二、CAS
CAS( compare and swap) 原子操作,用来实现多线程下的变量同步。
保证了如果需要更新的地址没有被其他进程(线程)改动过,那么它可以安全的写入。
而这也是我们对于某个数据或者数据结构加锁要保护的内容,保证读写的一致性,不出现dirty data。
CAS原语有三个参数:
- 内存地址,
- 期望值,
- 新值。
算法逻辑:
- 如果内存地址的值==期望值,表示该值未修改,此时可以修改成新值。
- 否则表示修改失败,返回false,由用户决定后续操作。
int compare_and_swap (int* reg, int oldval, int newval) {
ATOMIC();
int old_reg_val = *reg;
if (old_reg_val == oldval)
*reg = newval;
END_ATOMIC();
return old_reg_val;
}
可在循环中不断执行CAS,如果共享变量没有改变,那么swap,在当前环境中写入,否则继续do-while的Retry-Loop。
三、ABA问题
ABA问题最容易发生在lock free算法中的,地址被重用的情况。
无锁相当于“锁”的粒度变小了,主要是“锁”HEAD和TAIL这两个关键资源。而不是整个数据结构。
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);
https://www.cnblogs.com/demian/p/11141733.html
https://blog.csdn.net/nawenqiang/article/details/83027222
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/161699.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...