`
sixsun
  • 浏览: 9159 次
  • 性别: Icon_minigender_1
  • 来自: 深圳
最近访客 更多访客>>
文章分类
社区版块
存档分类
最新评论

CAS与ABA问题

 
阅读更多
  • 什么是ABA问题

        我们先来看一个多线程的运行场景:

 

时间点1 :线程1查询值是否为A

时间点2 :线程2查询值是否为A
时间点3 :线程2比较并更新值为B
时间点4 :线程2查询值是否为B
时间点5 :线程2比较并更新值为A

时间点6 :线程1比较并更新值为C 

 

        在这个线程执行场景中,2个线程交替执行。线程1在时间点6的时候依然能够正常的进行CAS操作,尽管在时间点2到时间点6期间已经发生一些意想不到的变化, 但是线程1对这些变化却一无所知,因为对线程1来说A的确还在。通常将这类现象称为ABA问题。

 

 

  • ABA发生了,但线程不知道

        我们再来看一个小例子进一步体会ABA的发生。从而思考该如何解决ABA问题。

/**
 * 无法检测到ABA是否发生
 * @author 
 */
public class DontCheckABADemo {

    /**
     * 把邮件内容“远方的问候”放到了一个普通信封envelope里
     * envelope = 邮件内容
     */
    static AtomicReference<String> envelope =
     new AtomicReference<String>( "远方的来信" );

    /**
     * @param args
     * @throws InterruptedException
     */
    public static void main(String[] args) throws InterruptedException {

        // 线程1
        Thread t1 = new Thread(new Runnable() {
            @Override
            public void run() {
               
                String mailContent = envelope.get();

                System.out.println("T1首先看到了信封里的邮件内容[ " + 
                mailContent + " ](A)。");
                                           
                try {
                    // T1被强制sleep一会,好让T2这个时候有机可乘
                    System.out.println("T1现在有事情暂时的离开了一小会。");   
                    Thread.sleep(2000);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
               
                boolean result = envelope.compareAndSet(
                   mailContent, "远方的回信");
                if( result ) {
                    System.out.println(
                    "\nT1在返回后重新检查了邮件,好像没人动过。" +
                    "现在可以写回信了[ "  + envelope.get() + " ]。");
                }
            }
        });

        // 线程2
        Thread t2 = new Thread(new Runnable() {
            @Override
            public void run() {

                try {
                    // T2先sleep一会,好让T1有机会先看到信封里面的邮件内容
                    Thread.sleep(1000);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }

                String mailContent = envelope.get();

                // T2第一次修改了信封里的邮件内容
                boolean firstOpt = envelope.compareAndSet(mailContent, "");
                if( firstOpt )
                    System.out.println(
                    "\nT2悄悄将信封里的邮件内容[ " + mailContent + " ]取走(B)。" +
                    "现在邮件内容已经不再信封里了。");

                // T2第二次修改了信封里的邮件内容
                boolean secondOpt = envelope.compareAndSet("", mailContent);

                if( secondOpt )
                    System.out.println(
                    "T2悄悄把信封里的邮件内容[ " + envelope.get() + " ]放回(A)。"    +
                    "现在邮件内容好像没被动过一样。");
            }
        });       

        t1.start();
        t2.start();
    }
}

 
        控制台信息

T1首先看到了信封里的邮件内容[ 远方的来信 ](A)。
T1现在有事情暂时的离开了一小会。

T2悄悄将信封里的邮件内容[ 远方的来信 ]取走(B)。现在邮件内容已经不再信封里了。
T2悄悄把信封里的邮件内容[ 远方的来信 ]放回(A)。现在邮件内容好像没被动过一样。

T1在返回后重新检查了邮件,好像没人动过。现在可以写回信了[ 远方的回信 ]。

 

 

  • 解决ABA问题的初步思路

        通过码示例我们思考一下ABA问题的根源是什么,当线程进行compareAndSet操作时是通过比较值的方式来判断能否更改当前的值。 但有些业务场景仅仅依靠比较值是不能满足整个逻辑的正确性的,可能还需要知道这个值是被谁更新了,更新了多少次,更新的时间等等。 基于这些需求我们可以给每个值再关联上一些扩展数据作为CAS操作时额外的比较机制,从而形成一个实际值与若干个标记值的复合原子数据。

 

  • 解决ABA问题的技术细节

        我们现在有了初步的解决思路,但还需要考虑一些实现上的细节。CAS操作由原先仅仅对一个值的比较,现在变成了对多个值的比较(实际值和一些标记值),而在多线程环境中同时操作多个值往往会比操作一个值更加需要小心谨慎,如果不能以原子的方式完成多个值的操作,在多线程环境中将会出现比ABA更加严重且意想不到问题。

 

  • ABA问题与Java并发包

        现在有了初步的解决思路和需要注意的技术细节,我们是否要开始编码实现一个更加健壮的代码来发现线程执行过程中的ABA问题。在动手之前不妨先看一看Java并发包,Java并发包提供两个原子类型:AtomicStampedReference和AtomicMarkableReference。这两个类型提供了解决ABA问题的机制,并且它们的解决办法与我们所思考的方式是完全一致的,如代码片段1所示。

    代码片段1

 

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

 
        AtomicStampedReference的compareAndSet操作不仅需要检查值(reference)是否发生了改变,同时还要检查与值相关联的标记值(stamp)是否也发生了改变。开发者可以根据具体的业务的需求,在每次通过compareAndSet修改AtomicStampedReference内容(值与标记)的时候,既要比较reference,还要比较stamp,这个整数标记通过具体的业务需求策略生成。现在在每次CAS操作的时候reference都会与一个整数标记对应,即使在引用没有被修改的时候,也依然知道引用可能被访问过。标记就好像是引用的一个访问操作记号。AtomicStampedReference的实现如代码片段2所示。

 

        代码片段2

 

public boolean compareAndSet(V expectedReference,V newReference,
     int expectedStamp,int newStamp) {

	// pair复制到局部变量current,current在当前方法中是线程安全的
     Pair<V> current = pair;

	return
	expectedReference == current.reference && // 当前引用与期待的引用相同
	expectedStamp == current.stamp && // 并且当前标记与期待的标记相同
	((newReference == current.reference && // 并且新引用与当前引用相同
	newStamp == current.stamp) || // 并且新标记与当前标记相同则无需更新
     
     // Pair.of方法将newReference和newStamp构建出一个Pair对象,同时更新
	casPair(current, Pair.of(newReference, newStamp))); // 否则更新内容
}

private boolean casPair(Pair<V> cmp, Pair<V> val) {
    return UNSAFE.compareAndSwapObject(this, pairOffset, cmp, val);
}

 

 

  • ABA发生了,线程检测到了

        现在我们可以改写之前的代码,检测ABA的发生:

 

/**
 * 可以检测到ABA是否发生了
 * @author 
 */
public final class CheckABADemo {

	/**
	 * 把邮件内容“远方的问候”放到了一个智能的能够记录操作标记的信封envelope中
	 * envelope = 邮件内容 + 操作标记
	 */
	static AtomicStampedReference<String> envelope = 
     new AtomicStampedReference<String>( "远方的来信", 0 );

	/**
	 * @param args
	 * @throws InterruptedException
	 */
	public static void main(String[] args) throws InterruptedException {

		// 线程1
		Thread t1 = new Thread(new Runnable() {
			
			@Override
			public void run() {
				
				String mailContent = envelope.getReference();
				int mailStamp = envelope.getStamp();
				
				System.out.println(
				"T1首先看到了信封里的邮件内容[ " + mailContent + " ](A)。" +
				"信封上还有一个操作标记:" + mailStamp);
				                            
				try {
					// T1实际上被强制sleep一会,好让T2这个时候有机可乘
					System.out.println("T1现在有事情暂时的离开了");						
					Thread.sleep(2000);  
				} catch (InterruptedException e) {
					e.printStackTrace();
				}
				
				// T1尝试给‘远方的来信’回信
				boolean result = envelope.compareAndSet(
				mailContent, "远方的回信", mailStamp, ++mailStamp);
				
				if( result ) {
					System.out.println(
					"\nT1在返回后检查邮件内容和信封上面的操作标记。" +
					"邮件内容还是一样。信封的操作标记也没人动过。" + 
					"现在可以写回信了[ "  + envelope.getReference() + "]");
					
				} else {
					System.out.println(
					"\nT1在返回后检查邮件内容和信封上面的操作标记。"   +
					"邮件内容还是一样,但信封的操作标记被动过了。\n" + 
					"T1:信件被别人偷看了,我该做点什么好呢。\n" +
					"或者\n " +
					"T1:信件被别人偷看了,这没什么大不了的。" );
					
				}
			}
		});

		// 线程2
		Thread t2 = new Thread(new Runnable() {
			@Override
			public void run() {

				try {
					// T2先sleep一会,好让T1有机会先看到信封里面的邮件内容
					Thread.sleep(1000); 
				} catch (InterruptedException e) {
					e.printStackTrace();
				}

				int[] mailStamp = new int[1];
				String mailContent = envelope.get(mailStamp);

				// T2第一次修改了信封里的邮件内容和信封上的操作标记
				boolean firstOpt = envelope.compareAndSet(
                   mailContent, "", mailStamp[0], ++mailStamp[0]);
				if( firstOpt ) 
					System.out.println(
					"\nT2悄悄将信封里的邮件内容[ " + mailContent + " ]取走(B)。" +
					"现在邮件内容已经不在信封里了。" +
					"信封上的操作标记首次被改动了:" + envelope.getStamp());

				// T2第二次修改了信封里的邮件内容和信封上的操作标记
				boolean secondOpt = envelope.compareAndSet(
                   "", mailContent, mailStamp[0], ++mailStamp[0]);
				if( secondOpt ) 
					System.out.println(
					"T2悄悄把信封里的邮件内容[ " + 
                                         envelope.getReference() + " ]放回(A)。" + 
					"现在邮件内容好像没被动过一样。" +
					"信封上的操作标记再次被改动了:" + envelope.getStamp());
			}
		});		

		t1.start();
		t2.start();
	}
}

 
        控制台信息

T1首先看到了信封里的邮件内容[ 远方的来信 ](A)。信封上还有一个操作标记:0
T1现在有事情暂时的离开了

T2悄悄将信封里的邮件内容[ 远方的来信 ]取走(B)。现在邮件内容已经不在信封里了。信封上的操作标记首次被改动了:1
T2悄悄把信封里的邮件内容[ 远方的来信 ]放回(A)。现在邮件内容好像没被动过一样。信封上的操作标记再次被改动了:2

T1在返回后检查邮件内容和信封上面的操作标记。邮件内容还是一样,但信封的操作标记被动过了。
T1:信件被别人偷看了,我该做点什么好呢。
或者
T1:信件被别人偷看了,这没什么大不了的。

 

 

  • ABA问题小结

        ABA并非是一个错误。而是多个线程在交替执行过程中可能发生的现象,并且这个现象仅仅通过基本的CAS操作是难以察觉的,而是否需要处理这个问题取决与你的业务场景。

 

        根据我们之前提及的“解决ABA问题的初步思路”以及JDK的并发包中的AtomicStampedReference和AtomicMarkableReference 类型的实现代码,我们还可以扩展出适合不同业务场景, 创建解决ABA问题的新的原子类型。比如以线程id作为标记,以当前时间作为标记等等。现在你是否觉得有了更多的思路。

分享到:
评论

相关推荐

    CAS下ABA问题及优化方案

    CAS下ABA问题及优化方案 CAS(Compare And Set)是一种常见的乐观锁机制,用于降低读写锁冲突,保证数据一致性。但是在极端情况下,CAS 乐观锁机制可能会出现 ABA 问题。本文将从ABA问题的定义、出现原因、优化方案...

    CAS底层原理与ABA问题.docx

    3. **ABA问题**:在某些情况下,一个线程读取到的值A,在其他线程中被修改为B,然后再变回A,CAS会认为值没有变化,从而可能导致错误的结果。为了解决这个问题,可以使用版本号或者“戳”来记录变量的状态,如Java中...

    技术分享-JAVA并发库解读

    #### CAS与ABA问题 Compare-and-Swap (CAS) 是一种常用的原子操作,用于实现无锁算法。它通过比较预期值与当前值是否一致来决定是否更新变量的值。然而,CAS存在ABA问题,即当一个值由A变为B然后再变回A时,CAS无法...

    Java并发的CAS原理与ABA问题的讲解

    总的来说,虽然CAS提供了一种高效的无锁同步机制,但需要开发者注意ABA问题可能带来的潜在风险,并根据具体应用场景选择合适的解决方案。在设计并发程序时,理解CAS的工作原理以及它可能引发的问题是至关重要的,...

    并行数据结构优化.pptx

    CAS与ABA问题 - **CAS操作**:解决了死锁问题,但存在ABA问题。 - **ABA问题**:一个值被修改后又恢复原状,CAS无法识别这种变化。 - **解决方案**:使用版本号或时间戳标记数据。 #### 2. 多版本并发控制(MVCC...

    CAS源码分析,以及ABA问题的解决

    CAS(比较并交换)一个小demo import java.util.concurrent.atomic.AtomicInteger; public class CasDemo { public static void main(String[] args) { //默认初始值为5,也就是主存中的值为5 AtomicInteger ...

    浅谈Java中ABA问题及避免

    Java中的ABA问题是指在使用Compare-And-Swap(CAS)操作时可能出现的一种问题。该问题的产生是由于CAS操作的原子性和并发环境中的线程执行顺序的不确定性。ABA问题的出现可能会导致程序的不正确执行和数据的不一致。...

    atomicReference 使用和AtomicStampedReference 解决ABA的问题.docx

    然而,CAS虽然解决了原子性问题,但并不能避免ABA问题。ABA问题是指在并发环境下,一个值从A变到B,然后再变回A,而CAS可能只检查值是否还是A,却忽略了它曾经变为B的过程。这个比喻中,你手中的手提箱虽然看起来...

    Java CAS 原理分析

    CAS操作可能会遇到ABA问题(即在两次比较之间,一个值可能被多次修改回到初始状态),这时可以考虑使用带有版本号的CAS或其他替代方案。 #### 七、结论 CAS作为多线程环境中不可或缺的一种同步机制,通过硬件层面...

    JAVA CAS实现原理与使用.docx

    但是,它也有一定的局限性,比如ABA问题(值从A变为B再变回A,但CAS仍然认为没有变化),以及可能导致循环等待(自旋锁)的高CPU占用。因此,在实际使用中,开发者需要根据场景选择合适的同步策略,如使用带有版本号...

    基于cas的无锁队列实现

    2. **避免ABA问题**:如果在CAS过程中,旧值A被修改为其他值,然后再变回A,CAS操作会成功,但可能隐藏了错误。解决方法可以引入版本号或者使用更高级的同步原语。 3. **队列扩容**:如果队列接近满,需要动态扩容...

    CAS学习手册-JAVA程序员必备

    1. **场景引入与问题** 在多线程环境下,简单的计数器自增操作如果不加以同步控制,可能会导致数据不一致。例如,两个线程各自独立地对同一个静态变量count进行累加,最终结果可能不会是200。为了解决这个问题,...

    Java 多线程与并发(8-26)-JUC原子类- CAS, Unsafe和原子类详解.pdf

    首先是ABA问题,即在CAS操作中,如果一个变量在被读取后、在被写入新值前,其值被修改为另一个值然后再改回原值,CAS操作可能会认为这个变量没有被修改过,导致数据不一致的问题。为了解决ABA问题,Java提供了...

    ABA信号转导家族基因鉴定与功能分析.docx

    本文主要研究了茶树ABA信号转导家族基因的鉴定与功能分析,包括CsPYLs/PP2CAs/SnRK2s三个基因家族的表达模式、在逆境胁迫中的表达模式、相互之间的互作关系等。 研究结果表明,茶树中存在15个CsPYLs基因,8个CsPP2...

    笔记-3、原子操作CAS1

    这种情况可能导致循环,也就是所谓的"ABA问题",即一个值被改变,然后又变回原值,但中间可能发生了其他操作,使得系统状态发生不可预知的变化。 为了解决ABA问题,Java提供了一些特殊的原子类,如`...

    CAS原理 java 并发

    **标题:“CAS原理与Java并发”** 在Java并发编程中,CAS(Compare and Swap,比较并交换)是一种无锁算法,广泛应用于多线程环境下的数据同步。它通过硬件指令来实现原子操作,提升了并发性能,同时避免了锁带来的...

    【并发编程】CAS到底是什么.pdf

    - **ABA问题**:在CAS操作过程中,如果某个值由A变为B再变回A,其他线程可能会误以为该值未被更改。 - **解决方案**: 1. **版本号**:为每个变量添加一个版本号,每次更新变量时都增加版本号,以此区分相同的值。 ...

    15 原子性轻量级实现—深入理解Atomic与CAS.pdf

    然而,过度依赖CAS可能导致ABA问题,即值从A变为B,再变回A,虽然比较成功,但实际上值已经发生了变化。Java中的`Atomic`类通常通过版本号来解决ABA问题。 除了`AtomicInteger`,还有`AtomicLongArray`、`...

Global site tag (gtag.js) - Google Analytics