xylz,imxylz

关注后端架构、中间件、分布式和并发编程

   :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  111 随笔 :: 10 文章 :: 2680 评论 :: 0 Trackbacks

在JDK 5之前Java语言是靠synchronized关键字保证同步的,这会导致有锁(后面的章节还会谈到锁)。

锁机制存在以下问题:

(1)在多线程竞争下,加锁、释放锁会导致比较多的上下文切换和调度延时,引起性能问题。

(2)一个线程持有锁会导致其它所有需要此锁的线程挂起。

(3)如果一个优先级高的线程等待一个优先级低的线程释放锁会导致优先级倒置,引起性能风险。

volatile是不错的机制,但是volatile不能保证原子性。因此对于同步最终还是要回到锁机制上来。

独占锁是一种悲观锁,synchronized就是一种独占锁,会导致其它所有需要锁的线程挂起,等待持有锁的线程释放锁。而另一个更加有效的锁就是乐观锁。所谓乐观锁就是,每次不加锁而是假设没有冲突而去完成某项操作,如果因为冲突失败就重试,直到成功为止。

CAS 操作

上面的乐观锁用到的机制就是CAS,Compare and Swap。

CAS有3个操作数,内存值V,旧的预期值A,要修改的新值B。当且仅当预期值A和内存值V相同时,将内存值V修改为B,否则什么都不做。

非阻塞算法 (nonblocking algorithms)

一个线程的失败或者挂起不应该影响其他线程的失败或挂起的算法。

现代的CPU提供了特殊的指令,可以自动更新共享数据,而且能够检测到其他线程的干扰,而 compareAndSet() 就用这些代替了锁定。

拿出AtomicInteger来研究在没有锁的情况下是如何做到数据正确性的。

private volatile int value;

首先毫无以为,在没有锁的机制下可能需要借助volatile原语,保证线程间的数据是可见的(共享的)。

这样才获取变量的值的时候才能直接读取。

public final int get() {
        return value;
    }

然后来看看++i是怎么做到的。

public final int incrementAndGet() {
    for (;;) {
        int current = get();
        int next = current + 1;
        if (compareAndSet(current, next))
            return next;
    }
}

在这里采用了CAS操作,每次从内存中读取数据然后将此数据和+1后的结果进行CAS操作,如果成功就返回结果,否则重试直到成功为止。

而compareAndSet利用JNI来完成CPU指令的操作。

public final boolean compareAndSet(int expect, int update) {  
    return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
    }

整体的过程就是这样子的,利用CPU的CAS指令,同时借助JNI来完成Java的非阻塞算法。其它原子操作都是利用类似的特性完成的。

而整个J.U.C都是建立在CAS之上的,因此对于synchronized阻塞算法,J.U.C在性能上有了很大的提升。参考资料的文章中介绍了如果利用CAS构建非阻塞计数器、队列等数据结构。

CAS看起来很爽,但是会导致“ABA问题”。

CAS算法实现一个重要前提需要取出内存中某时刻的数据,而在下时刻比较并替换,那么在这个时间差类会导致数据的变化。

比如说一个线程one从内存位置V中取出A,这时候另一个线程two也从内存中取出A,并且two进行了一些操作变成了B,然后two又将V位置的数据变成A,这时候线程one进行CAS操作发现内存中仍然是A,然后one操作成功。尽管线程one的CAS操作成功,但是不代表这个过程就是没有问题的。如果链表的头在变化了两次后恢复了原值,但是不代表链表就没有变化。因此前面提到的原子操作AtomicStampedReference/AtomicMarkableReference就很有用了。这允许一对变化的元素进行原子操作。

 

 

参考资料:

(1)非阻塞算法简介

(2)流行的原子

 



©2009-2014 IMXYLZ |求贤若渴
posted on 2010-07-04 18:03 imxylz 阅读(47962) 评论(19)  编辑  收藏 所属分类: J2EE

评论

# re: 深入浅出 Java Concurrency (5): 原子操作 part 4[未登录] 2010-07-05 15:24 nick
繼續繼續  回复  更多评论
  

# re: 深入浅出 Java Concurrency (5): 原子操作 part 4 2010-11-13 18:41 HyviTan
Hi

文章结尾的两个参考文献链接失效了。  回复  更多评论
  

# re: 深入浅出 Java Concurrency (5): 原子操作 part 4 2011-03-07 20:51 caihj
“上面的乐观锁用到的机制就是CAS,Compare and Swap”
是Swap?不是Set?
  回复  更多评论
  

# re: 深入浅出 Java Concurrency (5): 原子操作 part 4 2011-05-04 13:00 kick
请教博主,从网上找了一段模拟CAS的代码,能够实现i++功能,改了一下。开了10000个线程运行,结果是错误的,达不到10000. 为什么?
public class CasCounter {
private SimulatedCAS simulatedCAS = null;
public int getValue(){
return simulatedCAS.getValue();
}

public int increment(){
int oldValue = simulatedCAS.getValue();
while(simulatedCAS.compareAndSwap(oldValue, oldValue+1) != oldValue)
oldValue = simulatedCAS.getValue();
return oldValue;
}

public CasCounter(SimulatedCAS cas){
this.simulatedCAS = cas;
}

public static void main(String[] args) throws InterruptedException {
CasCounter counter = new CasCounter(new SimulatedCAS());
Thread[] ts = new Thread[10000];
for(int i = 0; i <10000; i++){
ts[i] = new CounterThread(counter);

}
for(Thread t : ts){
t.start();
}

for(Thread t : ts){
t.join();
}

System.out.println("counter: "+ counter.getValue());
}
}

public class CounterThread extends Thread {
CasCounter counter = null;

public CounterThread(CasCounter counter) {

this.counter = counter;
}

@Override
public void run() {
counter.increment();
}
}

public class SimulatedCAS {

private volatile int value = 0;
public synchronized int getValue(){
return value;

}
public synchronized int compareAndSwap(int expectedValue, int newValue){
if(value == expectedValue)
value = newValue;
return expectedValue;
}
}
  回复  更多评论
  

# re: 深入浅出 Java Concurrency (5): 原子操作 part 4[未登录] 2011-08-09 20:07 xxx
@kick
问题可能出在CasCounter.increment()函数中。
多个线程可能取到相同的 oldValue,会导致线程修改失效。
如果给这个函数加上 synchronized差不多就可以了。

不过郁闷的是,加上synchronized以后,也会出现达不到10000的情况。
不过比不加synchronized的情况好的多。不知道是为什么了  回复  更多评论
  

# re: 深入浅出 Java Concurrency (5): 原子操作 part 4 2011-08-09 21:29 xylz
@xxx
@kick

出错的地方在于CAS操作,稍微改动一下:
public synchronized int compareAndSwap(int expectedValue, int newValue) {
if (value == expectedValue) {
value = newValue;
return expectedValue;
}
return - expectedValue;
}
就可以得到正确结果的。通常CAS操作可以返回true/false,如果操作成功返回true,否则返回false。原来的代码是不管操作是否成功都返回了期待值,所以就改变了操作逻辑。
  回复  更多评论
  

# re: 深入浅出 Java Concurrency (5): 原子操作 part 4 2011-08-11 15:49 zhangxl
@xylz
这里的模拟都使用了synchronized(内在锁)关键字,模拟CAS还有什么意义呢?引入CAS的目的不就是为了较少锁的竞争,提高多线程并发的吞吐率吗?
我觉得要模拟也应该像AQS那样,比如,这是AQS的源码中状态变量的原子操作:

A.Q.S里面包含了一个存储同步状态的变量,它的声明如下:

private volatile int state;

这里采用了volatile修饰符的原因是为了保证对state变量的写对所有的线程都是可见的。但是大家都知道,volatile只能保证变量的可见性,不能保证对变量操作的原子性,所以A.Q.S里面就采用了CAS(Compare And Swap)操作来更新state变量的值,代码如下:

protected final boolean compareAndSetState(int expect, int update)
{ // See below for intrinsics setup to support this
return unsafe.compareAndSwapInt(this, stateOffset, expect, update); }


个人觉得这样才能模拟出CAS的本质,原子特性。
  回复  更多评论
  

# re: 深入浅出 Java Concurrency (5): 原子操作 part 4 2011-08-13 20:18 yintiefu
@kick
修改2个地方的代码

1.
public int increment() {

for(;;){
int oldValue = simulatedCAS.getValue();
if(simulatedCAS.compareAndSwap(oldValue,oldValue+1)){
oldValue = simulatedCAS.getValue();
return oldValue;
}
}
}

2.
public synchronized boolean compareAndSwap(int expectedValue, int newValue) {
if (value == expectedValue){
value = newValue;
return true;
}
return false;
}  回复  更多评论
  

# re: 深入浅出 Java Concurrency (5): 原子操作 part 4 2011-08-26 10:53 imtxt
@zhangxl
您讲的是上面的回复贴出的代码?本来那就是拿来做好玩用的吧。  回复  更多评论
  

# re: 深入浅出 Java Concurrency (5): 原子操作 part 4 2012-07-09 11:39 waitingfortime
@xylz
这个代码不做修改,也可以得到正确的数啊?怎么得不到呢  回复  更多评论
  

# re: 深入浅出 Java Concurrency (5): 原子操作 part 4[未登录] 2013-03-03 14:40 teasp
“独占锁是一种悲观锁”,这是错误的说法。  回复  更多评论
  

# re: 深入浅出 Java Concurrency (5): 原子操作 part 4 2013-03-06 21:44 asdf
@teasp
别话说一半,解释一下  回复  更多评论
  

# re: 深入浅出 Java Concurrency (5): 原子操作 part 4[未登录] 2013-03-07 12:54 teasp
@asdf
独占锁既可以是悲观的也可以是乐观的呀,用CAS实现的独占锁不就是乐观的?  回复  更多评论
  

# re: 深入浅出 Java Concurrency (5): 原子操作 part 4[未登录] 2013-06-16 13:24 flying
用博主的 int compareAndSwap方法返回- expectedValue,有时会出现9999,用boolean是对的,应该是expectedValue为零时,-0和0是相同的值,导致没有加成功。  回复  更多评论
  

# re: 深入浅出 Java Concurrency (5): 原子操作 part 4[未登录] 2013-06-16 13:31 flying
@xylz
SimulatedCAS 类的value 是volatile ,getValue的synchronized 关键字是不是可以去掉了?
  回复  更多评论
  

# re: 深入浅出 Java Concurrency (5): 原子操作 part 4 2014-08-06 21:04 vanjayzhou
借这里问个问题哈,java 当中的cas问题,java concurrent 包的实现是依赖 CAS准则实现的,对AtomicInteger 方法中的 compareAndSet方法有些疑惑。
public final boolean compareAndSet(int expect, int update) {
return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
}

unsafe.compareAndSwapInt方法是本地方法, 我考虑这么一种情况:
两个线程T1, T2 同时取了主内存中A, T1调用compareAndSet 方法成功,将A变成 A1, 因为A值是同时从内存中取出来的,那T2调用compareAndSet方法也会成功,将A变成A2. 那结果不是不正确了么。
帮我分析一下啊。
谢啦
  回复  更多评论
  

# re: 深入浅出 Java Concurrency (5): 原子操作 part 4 2014-08-08 10:13 imxylz
@vanjayzhou
CAS的CPU原语保证A修改时,T2修改会失败。所以T2才需要循环操作,直到成功。  回复  更多评论
  

# re: 深入浅出 Java Concurrency (5): 原子操作 part 4[未登录] 2014-10-31 16:58 JJZHK
@vanjayzhou
老版的CPU会进行锁总线,新版的CPU进行的是缓存锁定。所以T2修改的时候肯定会失败的,因为共享内存已经被CPU锁定了。  回复  更多评论
  

# re: 深入浅出 Java Concurrency (5): 原子操作 part 4[未登录] 2016-01-06 08:40 William Chen
没错是交换设置。  回复  更多评论
  


只有注册用户登录后才能发表评论。


网站导航:
 

©2009-2014 IMXYLZ