Treiber Stack介绍

时间:2022-12-17 16:33:36

简介

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介绍的更多相关文章

  1. 理解与使用Treiber Stack

    目录 背景 名称由来 CompletableFuture源码实现 FutureTask实现 Treiber Stack抽象实现 入栈 出栈 示例 参考 背景 最近在很多JDK源码中都看到了Treibe ...

  2. ELK Stack 介绍 &amp&semi; Logstash 日志收集

    ELK Stack 组成 Software Description Function E:Elasticsearch Java 程序 存储,查询日志 L:Logstash Java 程序 收集.过滤日 ...

  3. java集合系列——List集合之Stack介绍(五)

    1.Stack的简介 Stack 类表示后进先出(LIFO)的对象堆栈.它通过五个操作对类 Vector 进行了扩展 ,允许将向量视为堆栈.它提供了通常的 push 和 pop 操作,以及取堆栈顶点的 ...

  4. 堆栈Stack介绍

    堆栈(Stack)代表了一个后进先出的对象集合.当您需要对各项进行后进先出的访问时,则使用堆栈.当您在列表中添加一项,称为推入元素,当您从列表中移除一项时,称为弹出元素. Stack 类的方法和属性 ...

  5. JUC源码分析-线程池篇(二)FutureTask

    JUC源码分析-线程池篇(二)FutureTask JDK5 之后提供了 Callable 和 Future 接口,通过它们就可以在任务执行完毕之后得到任务的执行结果.本文从源代码角度分析下具体的实现 ...

  6. Java 集合系列07之 Stack详细介绍&lpar;源码解析&rpar;和使用示例

    概要 学完Vector了之后,接下来我们开始学习Stack.Stack很简单,它继承于Vector.学习方式还是和之前一样,先对Stack有个整体认识,然后再学习它的源码:最后再通过实例来学会使用它. ...

  7. Java 集合系列 06 Stack详细介绍&lpar;源码解析&rpar;和使用示例

    java 集合系列目录: Java 集合系列 01 总体框架 Java 集合系列 02 Collection架构 Java 集合系列 03 ArrayList详细介绍(源码解析)和使用示例 Java ...

  8. java之Stack详细介绍

    1  Stack介绍 Stack简介 Stack是栈.它的特性是:先进后出(FILO, First In Last Out). java工具包中的Stack是继承于Vector(矢量队列)的,由于Ve ...

  9. 【转】 Java 集合系列07之 Stack详细介绍&lpar;源码解析&rpar;和使用示例

    概要 学完Vector了之后,接下来我们开始学习Stack.Stack很简单,它继承于Vector.学习方式还是和之前一样,先对Stack有个整体认识,然后再学习它的源码:最后再通过实例来学会使用它. ...

随机推荐

  1. Yii2&period;0数据库查询的一些简单的操作

    User::find()->all(); 此方法返回所有数据: User::findOne($id); 此方法返回 主键 id=1 的一条数据(举个例子): User::find()->w ...

  2. Match&colon;Cyclic Nacklace&lpar;KMP的next数组的高级应用&rpar;&lpar;HDU 3746&rpar;

    串珠子 题目大意:给定一个字串,要你找到如果要使之成为循环串,在末尾需要的最小的字数(只能添加字符,不能删减字符) 首先联动一下之前做过的动态规划问题POJ 3280,当然了3280这一题是用的LD, ...

  3. ci为什么必须得写构造函数

    构造函数 如果要在你的任意控制器中使用构造函数的话,那么必须在里面加入下面这行代码: parent::__construct(); 这行代码的必要性在于,你此处的构造函数会覆盖掉这个父控制器类中的构造 ...

  4. 苹果系统直接读写 ntfs 磁盘

    苹果系统对 ntfs 能读,但不能写. 方案1:修改 fstab 法 ======================================== 读写支持.在使用本教学文章之前,请先确定你没有安 ...

  5. SpringMVC3&period;2&plus;JPA使用注解的方式环境搭建

    ==============================entity=========================================================package ...

  6. VJ1061迎春舞会之三人组舞

    题目链接 推了半个下午..写的三重超时了  加了点单调队列的思想 优化了下过了 dp[i][j] 第二组的最右边的人选第J个人 那最左边肯定选第j-1个人 肯定是选相邻的 dp[i][j] = min ...

  7. c&num; 6&period;0 学习笔记

    refer : http://www.cnblogs.com/yinrq/p/5600530.html http://www.cnblogs.com/wolf-sun/p/5168217.html h ...

  8. struts2讲义----建立一个struts2工程

    建立一个Struts2 工程 Ø 1在MyEclipse中新建web工程 Ø 2在struts-2.2.1.1-all\struts-2.2.1.1解压struts2-blank.war( 最基础的示 ...

  9. 使用git进行版本控制

    一.git基本介绍 Git是一个开源的分布式版本控制系统,用于敏捷高效地处理任何或小或大的项目.Git是目前世界上最先进的分布式版本控制系统. 与常用的版本控制工具 CVS, Subversion 等 ...

  10. Unity3D-RayMarch-几何图元-3添加阴影

    效果图: 在RayMarch渲染算法中计算阴影非常简单,当射线碰撞到物体,从碰撞点逆着光源方向再次执行射线步进算法,如果这一过程中碰撞到了其他物体,则碰撞点被其他物体遮挡,该处具有阴影. shader ...