浅谈Java中ABA问题及避免

本文主要研究的是关于Java中ABA问题及避免的相关内容,具体如下。

在《Java并发实战》一书的第15章中有一个用原子变量实现的并发栈,代码如下:

public class Node {
	public final String item;
	public Node next;
	public Node(String item){
		this.item = item;
	}
}
public class ConcurrentStack {
	AtomicReference<Node> top = new AtomicReference<Node>();
	public void push(String item){
		Node newTop = new Node(item);
		Node oldTop;
		do{
			oldTop = top.get();
			newTop.next = oldTop;
		}
		while(!top.compareAndSet(oldTop, newTop));
	}
	public String pop(){
		Node newTop;
		Node oldTop;
		do{
			oldTop = top.get();
			if(oldTop == null){
				return null;
			}
			newTop = oldTop.next;
		}
		while(!top.compareAndSet(oldTop, newTop));
		return oldTop.item;
	}
}

这个例子并不会引发ABA问题,至于为什么不会,后面再讲解,下面先讲一下ABA问题

什么是ABA?

引用原书的话:如果在算法中的节点可以被循环使用,那么在使用“比较并交换”指令就可能出现这种问题,在CAS操作中将判断“V的值是否仍然为A?”,并且如果是的话就继续执行更新操作,在某些算法中,如果V的值首先由A变为B,再由B变为A,那么CAS将会操作成功

ABA的例子

有时候,ABA造成的后果很严重,下面将并发栈的例子修改一下,看看ABA会造成什么问题:

public class Node {
	public final String item;
	public Node next;
	public Node(String item){
		this.item = item;
	}
}
public class ConcurrentStack {
	AtomicReference<Node> top = new AtomicReference<Node>();
	public void push(Node node){
		Node oldTop;
		do{
			oldTop = top.get();
			node.next = oldTop;
		}
		while(!top.compareAndSet(oldTop, node));
	}
	public Node pop(int time){
		Node newTop;
		Node oldTop;
		do{
			oldTop = top.get();
			if(oldTop == null){
				return null;
			}
			newTop = oldTop.next;
			TimeUnit.SECONDS.sleep(time);
		}
		while(!top.compareAndSet(oldTop, newTop));
		return oldTop;
	}
}

注意这里的变化,Node基本没有变化

重点关注ConcurrentStack的变化

1、push方法:原来是使用内容构造Node,现在直接传入Node,这样就符合了“在算法中的节点可以被循环使用”这个要求

2、pop方法的sleep,这是模拟线程的执行情况,以便观察结果

我们先往stack中压入两个Node:

ConcurrentStack stack = new ConcurrentStack();
stack.push(new Node("A"));
stack.push(new Node("B")); 

然后创建两个线程来执行出入栈的操作

线程A先执行出栈:让NodeA出栈

stack.pop(3); 

因为某些原因,线程A执行出栈比较久,用了3s

线程B执行出栈之后再入栈:先然NodeA和NodeB出栈,然后让NodeD,NodeC,NodeA入栈(NodeA在栈顶)

Node A = stack.pop(0);
stack.pop(0);
stack.push(new Node("D"));
stack.push(new Node("C"));
stack.push(A); 

注意:线程B实现了节点的循环利用,它先将栈里面的内容全部出栈,然后入栈,最后栈顶的内容是之前出栈的Node

线程B执行完这些动作之后,线程A才执行CAS,此时CAS是可以执行成功的

按照原来的想法,线程A和B执行之后,stack的内容应该是:C和D,C在栈顶,但这里的执行结果却是Stack中什么都没有,这就是ABA问题

如何避免ABA问题

Java中提供了AtomicStampedReference和AtomicMarkableReference来解决ABA问题

AtomicStampedReference可以原子更新两个值:引用和版本号,通过版本号来区别节点的循环使用,下面看AtomicStampedReference的例子:

public class ConcurrentStack {
	AtomicStampedReference<Node> top = new AtomicStampedReference<Node>(null,0);
	public void push(Node node){
		Node oldTop;
		int v;
		do{
			v=top.getStamp();
			oldTop = top.getReference();
			node.next = oldTop;
		}
		while(!top.compareAndSet(oldTop, node,v,v+1));
		//   }while(!top.compareAndSet(oldTop, node,top.getStamp(),top.getStamp()+1));
	}
	public Node pop(int time){
		Node newTop;
		Node oldTop;
		int v;
		do{
			v=top.getStamp();
			oldTop = top.getReference();
			if(oldTop == null){
				return null;
			}
			newTop = oldTop.next;
			try {
				TimeUnit.SECONDS.sleep(time);
			}
			catch (InterruptedException e) {
				e.printStackTrace();
			}
		}
		while(!top.compareAndSet(oldTop, newTop,v,v+1));
		//   }while(!top.compareAndSet(oldTop, newTop,top.getStamp(),top.getStamp()));
		return oldTop;
	}
	public void get(){
		Node node = top.getReference();
		while(node!=null){
			System.out.println(node.getItem());
			node = node.getNode();
		}
	}
}

注意:不能使用注释中的方式,否则就和单纯使用原子变量没有区别了

AtomicMarkableReference可以原子更新一个布尔类型的标记位和引用类型,看下面的例子:

AtomicMarkableReference<Node> top = new AtomicMarkableReference<Node>(null,true);
public void push(Node node){
	Node oldTop;
	Boolean v;
	do{
		v=top.isMarked();
		oldTop = top.getReference();
		node.next = oldTop;
	}
	while(!top.compareAndSet(oldTop, node,v,!v));
}

总结

以上就是本文关于浅谈Java中ABA问题及避免的全部内容,希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题,如有不足之处,欢迎留言指出。感谢朋友们对本站的支持!

您可能感兴趣的文章:

  • java并发编程之cas详解
  • 全面了解Java中的CAS机制
  • Java编程cas操作全面解析
  • Java语言中cas指令的无锁编程实现实例
  • java中switch case语句需要加入break的原因解析
  • java实现cassandra高级操作之分页实例(有项目具体需求)
  • 解决cannot be cast to javax.servlet.Filter 报错的问题
  • Java并发编程总结——慎用CAS详解
(0)

相关推荐

  • java并发编程之cas详解

    CAS(Compare and swap)比较和替换是设计并发算法时用到的一种技术.简单来说,比较和替换是使用一个期望值和一个变量的当前值进行比较,如果当前变量的值与我们期望的值相等,就使用一个新值替换当前变量的值.这听起来可能有一点复杂但是实际上你理解之后发现很简单,接下来,让我们跟深入的了解一下这项技术. CAS的使用场景 在程序和算法中一个经常出现的模式就是"check and act"模式.先检查后操作模式发生在代码中首先检查一个变量的值,然后再基于这个值做一些操作.下面是一个

  • 解决cannot be cast to javax.servlet.Filter 报错的问题

    cannot be cast to javax.servlet.Filter 报错, 原因servlet-api.jar冲突 使用maven开发web应用程序, 启动的时候报错: jar not loaded. See Servlet Spec 2.3, section 9.7.2. Offending class: javax/servlet/Servlet.class 然后输出错误: 严重: Exception starting filter encodingFilter java.lang

  • Java语言中cas指令的无锁编程实现实例

    最开始接触到相关的内容应该是从volatile关键字开始的吧,知道它可以保证变量的可见性,而且利用它可以实现读与写的原子操作...但是要实现一些复合的操作volatile就无能为力了...最典型的代表是递增和递减的操作.... 我们知道,在并发的环境下,要实现数据的一致性,最简单的方式就是加锁,保证同一时刻只有一个线程可以对数据进行操作....例如一个计数器,我们可以用如下的方式来实现: public class Counter { private volatile int a = 0; pub

  • java中switch case语句需要加入break的原因解析

    java中switch case语句需要加入break的原因解析            java 中使用switch case语句需要加入break 做了具体的实例分析,及编译源码,在源码中分析应该如何使用,大家可以参考下: 假设我们有如下这样一个switch语句: public static void test(int index) { switch (index) { case 1: System.out.println(1); case 2: System.out.println(2);

  • Java并发编程总结——慎用CAS详解

    一.CAS和synchronized适用场景 1.对于资源竞争较少的情况,使用synchronized同步锁进行线程阻塞和唤醒切换以及用户态内核态间的切换操作额外浪费消耗cpu资源:而CAS基于硬件实现,不需要进入内核,不需要切换线程,操作自旋几率较少,因此可以获得更高的性能. 2.对于资源竞争严重的情况,CAS自旋的概率会比较大,从而浪费更多的CPU资源,效率低于synchronized.以java.util.concurrent.atomic包中AtomicInteger类为例,其getAn

  • 全面了解Java中的CAS机制

    前言 在看到Java锁机制的时候,无意中看到了CAS这个词,然后在百度查找CAS看了很多文章始终没有看的太懂,今天又在Google上查找了一些资料,才算是真正弄清楚了CAS机制. 什么是CAS 在jdk 1.5中增加的一个最主要的支持是Atomic类,比如说AtomicInteger, AtomicLong,这些类可帮助最大限度地减少在多线程中对于一些基本操作(例如,增加或减少多个线程之间共享的值)的复杂性.而这些类的实现都依赖于CAS(compare and swap)的算法. 乐观锁和悲观锁

  • java实现cassandra高级操作之分页实例(有项目具体需求)

    上篇博客讲到了cassandra的分页,相信大家会有所注意:下一次的查询依赖上一次的查询(上一次查询的最后一条记录的全部主键),不像mysql那样灵活,所以只能实现上一页.下一页这样的功能,不能实现第多少页那样的功能(硬要实现的话性能就太低了). 我们先看看驱动官方给的分页做法 如果一个查询得到的记录数太大,一次性返回回来,那么效率非常低,并且很有可能造成内存溢出,使得整个应用都奔溃.所以了,驱动对结果集进行了分页,并返回适当的某一页的数据. 一.设置抓取大小(Setting the fetch

  • Java编程cas操作全面解析

    CAS 指的是现代 CPU 广泛支持的一种对内存中的共享数据进行操作的一种特殊指令.这个指令会对内存中的共享数据做原子的读写操作. 简单介绍一下这个指令的操作过程:首先,CPU 会将内存中将要被更改的数据与期望的值做比较.然后,当这两个值相等时,CPU 才会将内存中的数值替换为新的值.否则便不做操作.最后,CPU 会将旧的数值返回.这一系列的操作是原子的.它们虽然看似复杂,但却是 Java 5 并发机制优于原有锁机制的根本.简单来说,CAS 的含义是"我认为原有的值应该是什么,如果是,则将原有的

  • 浅谈Java中ABA问题及避免

    本文主要研究的是关于Java中ABA问题及避免的相关内容,具体如下. 在<Java并发实战>一书的第15章中有一个用原子变量实现的并发栈,代码如下: public class Node { public final String item; public Node next; public Node(String item){ this.item = item; } } public class ConcurrentStack { AtomicReference<Node> top

  • 浅谈Java中的atomic包实现原理及应用

    1.同步问题的提出 假设我们使用一个双核处理器执行A和B两个线程,核1执行A线程,而核2执行B线程,这两个线程现在都要对名为obj的对象的成员变量i进行加1操作,假设i的初始值为0,理论上两个线程运行后i的值应该变成2,但实际上很有可能结果为1. 我们现在来分析原因,这里为了分析的简单,我们不考虑缓存的情况,实际上有缓存会使结果为1的可能性增大.A线程将内存中的变量i读取到核1算数运算单元中,然后进行加1操作,再将这个计算结果写回到内存中,因为上述操作不是原子操作,只要B线程在A线程将i增加1的

  • 浅谈Java中Unicode的编码和实现

    Unicode的编码和实现 大概来说,Unicode编码系统可分为编码方式和实现方式两个层次. 编码方式 字符是抽象的最小文本单位.它没有固定的形状(可能是一个字形),而且没有值."A"是一个字符,"€"也是一个字符.字符集是字符的集合.编码字符集是一个字符集,它为每一个字符分配一个唯一数字. Unicode 最初设计是作为一种固定宽度的 16 位字符编码.也就是每个字符占用2个字节.这样理论上一共最多可以表示216(即65536)个字符.上述16位统一码字符构成基

  • 浅谈java中null是什么,以及使用中要注意的事项

    1.null既不是对象也不是一种类型,它仅是一种特殊的值,你可以将其赋予任何引用类型,你也可以将null转化成任何类型,例如: Integer i=null; Float f=null; String s=null; 但是不能把null赋值给基本类型,如int ,float,double等 int k=null ----------编译器会报错cannot convert from null to int 2.null是关键字,像public.static.final.它是大小写敏感的,你不能将

  • 浅谈java中math类中三种取整函数的区别

    math类中三大取整函数 1.ceil 2.floor 3.round 其实三种取整函数挺简单的.只要记住三个函数名翻译过来的汉语便能轻松理解三大函数,下面一一介绍 1.ceil,意思是天花板,java中叫做向上取整,大于等于该数字的最接近的整数 例: math.ceil(13.2)=14 math.ceil(-13.2)=-13 2.floor,意思是地板,java中叫做向下取整,小于等于该数字的最接近的整数 例: math.floor(13.2)=13 math.floor(-13.2)=-

  • 浅谈Java中Collection和Collections的区别

    1.java.util.Collection 是一个集合接口.它提供了对集合对象进行基本操作的通用接口方法.Collection接口在Java 类库中有很多具体的实现.Collection接口的意义是为各种具体的集合提供了最大化的统一操作方式. Collection ├List │├LinkedList │├ArrayList │└Vector │ └Stack └Set 2.java.util.Collections 是一个包装类.它包含有各种有关集合操作的静态多态方法.此类不能实例化,就像一

  • 浅谈Java中注解Annotation的定义、使用、解析

    此例子,用于说明如何在Java中对"注解 Annotation"的定义.使用和解析的操作.注解一般用于自定义开发框架中,至于为什么使用,此处不作过多说明,这里只说明如何使用,以作备记.下面例子已测试,可以正常运行通过. 1.注解自定义. 这里定义两个注解,分别用来注解类和注解属性. package cc.rulian.ann; import java.lang.annotation.ElementType; import java.lang.annotation.Retention;

  • 浅谈java中的TreeMap 排序与TreeSet 排序

    TreeMap: package com; import java.util.Comparator; import java.util.TreeMap; public class Test5 { /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub TreeMap<String, String> tree = new TreeMap<String,

  • 浅谈java中对集合对象list的几种循环访问

    java中对集合对象list的几种循环访问的总结如下  1 经典的for循环 public static void main(String[] args) { List<String> list = new ArrayList(); list.add("123"); list.add("java"); list.add("j2ee"); System.out.println("=========经典的for循环=======

  • 浅谈java中的一维数组、二维数组、三维数组、多维数组

    这个数组可以看做新手学习,从一维数组 到 多维 数组 循环渐进,其实看起也很简单,一看便知,众所周知,一维.二维或许经常用到,用到二维以上应该就很少了. public class test { public static void main(String[] args) { /*一维数组*/ int num[] = {0,1,2}; /*下面输出 3 行数据,0 ~ 2*/ for (int i = 0; i < num.length; i++) { System.out.println("

随机推荐