简介
Treiber Stack在 R. Kent Treiber在1986年的论文Systems Programming: Coping with Parallelism中首次出现。它是一种无锁并发栈,其无锁的特性是基于CAS原子操作实现的。
实现
下面给出的Java语言实现为《Java并发编程实战》一书的15.4.1小结中的实现。Treiber Stack的实现套路很简单,就是CAS+重试,不需要任何注释就能轻松的看懂代码。
@ThreadSafe
public class ConcurrentStack <E> {
AtomicReference<Node<E>> top = new AtomicReference<Node<E>>();
public void push(E item) {
Node<E> newHead = new Node<E>(item);
Node<E> oldHead;
do {
oldHead = top.get();
newHead.next = oldHead;
} while (!top.compareAndSet(oldHead, newHead));
}
public E pop() {
Node<E> oldHead;
Node<E> newHead;
do {
oldHead = top.get();
if (oldHead == null)
return null;
newHead = oldHead.next;
} while (!top.compareAndSet(oldHead, newHead));
return oldHead.item;
}
private static class Node <E> {
public final E item;
public Node<E> next;
public Node(E item) {
this.item = item;
}
}
}
JDK中的使用
JDK中的FutureTask使用了Treiber Stack。关于FutureTask的源码解读,可以参考我的博文FutureTask源码解读。FutureTask用了Treiber Stack来维护等待任务完成的线程,在FutureTask的任务完成/取消/异常后在finishCompletion钩子方法中会唤醒栈中等待的线程。
参考
《Java并发编程实战》
Treiber Stack
Treiber Stack介绍的更多相关文章
-
理解与使用Treiber Stack
目录 背景 名称由来 CompletableFuture源码实现 FutureTask实现 Treiber Stack抽象实现 入栈 出栈 示例 参考 背景 最近在很多JDK源码中都看到了Treibe ...
-
ELK Stack 介绍 &; Logstash 日志收集
ELK Stack 组成 Software Description Function E:Elasticsearch Java 程序 存储,查询日志 L:Logstash Java 程序 收集.过滤日 ...
-
java集合系列——List集合之Stack介绍(五)
1.Stack的简介 Stack 类表示后进先出(LIFO)的对象堆栈.它通过五个操作对类 Vector 进行了扩展 ,允许将向量视为堆栈.它提供了通常的 push 和 pop 操作,以及取堆栈顶点的 ...
-
堆栈Stack介绍
堆栈(Stack)代表了一个后进先出的对象集合.当您需要对各项进行后进先出的访问时,则使用堆栈.当您在列表中添加一项,称为推入元素,当您从列表中移除一项时,称为弹出元素. Stack 类的方法和属性 ...
-
JUC源码分析-线程池篇(二)FutureTask
JUC源码分析-线程池篇(二)FutureTask JDK5 之后提供了 Callable 和 Future 接口,通过它们就可以在任务执行完毕之后得到任务的执行结果.本文从源代码角度分析下具体的实现 ...
-
Java 集合系列07之 Stack详细介绍(源码解析)和使用示例
概要 学完Vector了之后,接下来我们开始学习Stack.Stack很简单,它继承于Vector.学习方式还是和之前一样,先对Stack有个整体认识,然后再学习它的源码:最后再通过实例来学会使用它. ...
-
Java 集合系列 06 Stack详细介绍(源码解析)和使用示例
java 集合系列目录: Java 集合系列 01 总体框架 Java 集合系列 02 Collection架构 Java 集合系列 03 ArrayList详细介绍(源码解析)和使用示例 Java ...
-
java之Stack详细介绍
1 Stack介绍 Stack简介 Stack是栈.它的特性是:先进后出(FILO, First In Last Out). java工具包中的Stack是继承于Vector(矢量队列)的,由于Ve ...
-
【转】 Java 集合系列07之 Stack详细介绍(源码解析)和使用示例
概要 学完Vector了之后,接下来我们开始学习Stack.Stack很简单,它继承于Vector.学习方式还是和之前一样,先对Stack有个整体认识,然后再学习它的源码:最后再通过实例来学会使用它. ...
随机推荐
-
Yii2.0数据库查询的一些简单的操作
User::find()->all(); 此方法返回所有数据: User::findOne($id); 此方法返回 主键 id=1 的一条数据(举个例子): User::find()->w ...
-
Match:Cyclic Nacklace(KMP的next数组的高级应用)(HDU 3746)
串珠子 题目大意:给定一个字串,要你找到如果要使之成为循环串,在末尾需要的最小的字数(只能添加字符,不能删减字符) 首先联动一下之前做过的动态规划问题POJ 3280,当然了3280这一题是用的LD, ...
-
ci为什么必须得写构造函数
构造函数 如果要在你的任意控制器中使用构造函数的话,那么必须在里面加入下面这行代码: parent::__construct(); 这行代码的必要性在于,你此处的构造函数会覆盖掉这个父控制器类中的构造 ...
-
苹果系统直接读写 ntfs 磁盘
苹果系统对 ntfs 能读,但不能写. 方案1:修改 fstab 法 ======================================== 读写支持.在使用本教学文章之前,请先确定你没有安 ...
-
SpringMVC3.2+JPA使用注解的方式环境搭建
==============================entity=========================================================package ...
-
VJ1061迎春舞会之三人组舞
题目链接 推了半个下午..写的三重超时了 加了点单调队列的思想 优化了下过了 dp[i][j] 第二组的最右边的人选第J个人 那最左边肯定选第j-1个人 肯定是选相邻的 dp[i][j] = min ...
-
c# 6.0 学习笔记
refer : http://www.cnblogs.com/yinrq/p/5600530.html http://www.cnblogs.com/wolf-sun/p/5168217.html h ...
-
struts2讲义----建立一个struts2工程
建立一个Struts2 工程 Ø 1在MyEclipse中新建web工程 Ø 2在struts-2.2.1.1-all\struts-2.2.1.1解压struts2-blank.war( 最基础的示 ...
-
使用git进行版本控制
一.git基本介绍 Git是一个开源的分布式版本控制系统,用于敏捷高效地处理任何或小或大的项目.Git是目前世界上最先进的分布式版本控制系统. 与常用的版本控制工具 CVS, Subversion 等 ...
-
Unity3D-RayMarch-几何图元-3添加阴影
效果图: 在RayMarch渲染算法中计算阴影非常简单,当射线碰撞到物体,从碰撞点逆着光源方向再次执行射线步进算法,如果这一过程中碰撞到了其他物体,则碰撞点被其他物体遮挡,该处具有阴影. shader ...