找回密码
 立即注册

QQ登录

只需一步,快速开始

搜索

[ JAVA开发技术 ] 【守望者 j2se】锁无关栈和链表结构实现

2014-10-12 10:16| 发布者: zhouy | 查看: 1167 | 收藏

摘要: 通常在一个多线程环境下,我们需要共享某些数据,但为了避免竞争条件引致数据出现不一致的情况,某些代码段需要变成原子操作去执行。这时,我们便需要利用各种同步机制如互斥(Mutex)去为这些代码段加锁,让某一线 ...

通常在一个多线程环境下,我们需要共享某些数据,但为了避免竞争条件引致数据出现不一致的情况,某些代码段需要变成原子操作去执行。这时,我们便需要利用各种同步机制如互斥(Mutex)去为这些代码段加锁,让某一线程可以独占共享数据,避免竞争条件,确保数据一致性。但可惜的是,这属于阻塞性同步,所有其他线程唯一可以做的就是等待。基于锁(Lock based)的多线程设计更可能引发死锁、优先级倒置、饥饿等情况,令到一些线程无法继续其进度。
锁无关(Lock free)算法,顾名思义,即不牵涉锁的使用。这类算法可以在不使用锁的情况下同步各个线程。对比基于锁的多线程设计,锁无关算法有以下优势:


1.对死锁、优先级倒置等问题免疫:它属于非阻塞性同步,因为它不使用锁来协调各个线程,所以对死锁、优先级倒置等由锁引起的问题免疫;
2.保证程序的整体进度:由于锁无关算法避免了死锁等情况出现,所以它能确保线程是在运行当中,从而确保程序的整体进度;
3.性能理想:因为不涉及使用锁,所以在普遍的负载环境下,使用锁无关算法可以得到理想的性能提升。


自 JDK 1.5 推出之后,当中的 java.util.concurrent.atomic 的一组类为实现锁无关算法提供了重要的基础。本文介绍如何将锁无关算法应用到基本的数据结构中,去避免竞争条件,允许多个线程同时存取和使用集合中的共享数据。如果一个数据结构本身并非是线程安全的,一旦在多线程环境下使用这个数据结构,必须施加某种同步机制,否则很可能会出现竞争条件。我们即将设计的锁无关数据结构是线程安全的,所以使用时无需再编写额外代码去确保竞争条件不会出现。


 我们常用的stack,链表。会存在一些线程不安全的问题,这些问题主要是哪些呢?
     
1.stack
       
1)这里存在线程安全隐患的主要是push方法,我们可以这样模拟调用 push 时,它首先建立一个新的节点,并将 value 数据成员设定为传入
参数,而 next 数据成员则被赋值为当前的栈顶。然后它把 top 数据成员设定成新建立的节点。假设有两个线程 A 和 B 同时调用 push 方
法,线程 A 获取当前栈顶的节点去建立新的节点( push 方法代码第一行),但由于时间片用完,线程 A 暂时挂起。此时,线程 B 获取当
前栈顶的节点去建立新的节点,并把 top 设定成新建立的节点( push 方法代码第二行)。然后,线程 A 恢复执行,更新栈顶。当线程 B 对
push 的调用完成后,线程 A 原本获得的栈顶已经「过期」,因为线程 B 用新的节点取代了原本的栈顶。
   
2) pop 方法,它把栈顶的元素弹出。 pop 方法把栈顶暂存在一个本地变量 node ,然后用下一个节点去更新栈顶,最后返回变量 node 的
value 数据成员。如果两个线程同时调用这个方法,可能会引起竞争条件。当一个线程将当前栈顶赋值到变量 node ,并准备用下一个节点更新
栈 顶时,这个线程挂起。另一个线程亦调用 pop 方法,完成并返回结果。刚刚被挂起的线程恢复执行,但由于栈顶被另一个线程变更了,所以
继续执行的话会引起同步问题。


2. 线程安全的实现方式

       class Node<T> { 
           Node<T> next; 
           T value; 
    
          public Node(T value, Node<T> next) { 
             this.next = next; 
             this.value = value; 
          } 
     } 

    public class Stack<T> { 
         AtomicReference<Node<T>> top = new AtomicReference<Node<T>>(); 
    
         public void push(T value) { 
              boolean sucessful = false; 
              while (!sucessful) { 
                   Node<T> oldTop = top.get(); 
                   Node<T> newTop = new Node<T>(value, oldTop); 
                  sucessful = top.compareAndSet(oldTop, newTop); 
         }; 
    } 
    
    public T peek() { 
         return top.get().value; 
    } 
    
    public T pop() { 
        boolean sucessful = false; 
        Node<T> newTop = null; 
        Node<T> oldTop = null; 
        while (!sucessful) { 
            oldTop = top.get(); 
            newTop = oldTop.next; 
            sucessful = top.compareAndSet(oldTop, newTop); 
        } 
        return oldTop.value; 
    } 
}


3 linkedList


栈是一个相当简单的数据结构,要解决的同步问题亦比较直接和容易。但很多环境下,栈并不能满足我们的需求。我们将介绍链表,它有更广泛的应用 范围。链表存在的线程不安全的地方更多.

1)先考虑一下 add方法,这个方法把一个新元素加入到集合内指定元素之后的位置,并返回一个 boolean 值指示元素有没有被加入到集合   中,元素没有被加入的原因是因为集合内没有所指定的元素。它首先在一个 for 循环中寻找指定元素的节点,成功发现指定的节点后,便建立一个新节点。这个新节点的 next 数据成员连接到指定节点原本的 next ,指定节点的 next 则连到新节点上。另一方面, remove 方法寻找指定元素并从集合中移除,并且返回一个 boolean 值指示元素有没有被移除,返回 false 代表集合中没有指定的元素。这个方法在一个循环寻找要移除的元素,并且将左右两边的元素重新连接。在多线程环境下,如果两个线程同时调用 add 或 remove 方法,或者一个线程调用 add 方法而同一时间另一个线程调用 remove 方法均有机会引发竞争条件。试想像现在链表内有三个元素,分别是 A、B 和 C 。如果一个线程准备把一个元素加到 A 之后,它首先确定 A 节点的位置,然后新建一个节点 A1,这个节点的 value 数据成员储存着新加入的元素,而 next 数据成员则储存着 B 节点的引用。当这个线程准备把 A 和 A1 通过 next 成员连接起来时,此时线程因为时间片用完而被挂起。另一个线程亦准备在 A 之后加入一个新元素,它建立 A2 节点,并解除 A 和 B 原本的连结,然后依着 A-A2-B 的次序重新连接三个节点,操作完成。现在,刚刚被挂起的线程恢复执行,并依着 A-A1-B 的次序去重新连接三个节点。这时问题出现,刚刚新加入的 A2 节点遗失了。解决方法是,每一次准备把 A 元素和新建立的节点连接时,检查 A 节的 next 有否被其他线程改动过,没有改动过才进行连接,这是通过 CAS 操作原子地进行的。


2)同时间执行 add 和 remove 亦有可能引起竞争条件。同样地,现在一个链表内有三个元素 A、B 和 C 。当一个线程准备调用 remove 方法从这个集合中移除 B 元素,它首先获得 A 节点,然后准备通过改变 A 节点的 next 成员,把 A 和 C 互相连接时,这个线程突然被挂起。此时另一个线程调用 add 方法在 B 节点后插入一个新的元素 B2 。插入操作完成后,刚才被挂起的线程恢复执行,并且通过改变 next 成员把 A 和 C 互相连接,完成移除操作。可是,刚刚被加入的 B2 元素则遗失了,因为 A 节点跳过了 B 节点,直接连接着 C 节点。故此,我们要有一个解决方案。 Timothy L. Harris 提供了一个方法,他把整个移除过程分成两个步骤,逻辑删除和物理删除。逻辑删除并非真正地移除一个节点,而是把要移除的节点标记为已删除。另一方面,物理删除则真实从集合左移除一个节点。每次要加入新元素到指定节点之后,都必先检查该节点有没有被标记为删除,没有的话才把新的节点连接到集合中。这是通过 AtomicMarkableReference<V> 类中的 compareAndSet 方法原子地进行的。


3)链表有可能发生的冲突比较多,另一个问题便是两个线程同时间执行 remove 方法。这个问题和同时间执行 add 有点类同。现在假设一个集合内有四个元素 A、B、C 和 D,一个线程调用 remove 方法去移除元素 B 。它首先确定了 A 和 C 的位置,然后准备解除 A 和 B 的连结,再将 A 和 C 连接起来,实际的移除还未实行,这时这个线程被挂起了。另一个线程亦调用 remove 方法移除 C 元素,它解除 B 和 C 的连结,并把 B 和 D 连接起来,移除操作完成。之后刚才的线程恢复运行,继续执行余下的操作,把 A 和 C 连接起来,这样之前的移除 C 的操作便受到了破坏。最终链表中的元素变成 A-C-D,C 元素没有被移除。所以,我们 remove 方法需要确定要移除的元素的 next 有没有被改变。例如移除 B 的时候,检查 A 的 next 有没有被其他线程更动,以及有没有被标记为已经逻辑地删除。这亦是透过 CAS 操作去完成的。

3.线程安全的实现方式

class Node<T> { 
    AtomicMarkableReference<Node<T>> next; 
    T value; 
    
    public Node(T value, Node<T> next) { 
        this.next = new AtomicMarkableReference<Node<T>>(next, false); 
        this.value = value; 
    } 
    
class LinkedList<T> { 
    AtomicMarkableReference<Node<T>> head; 

    public LinkedList() { 
        Node<T> headNode = new Node<T>(null, null); 
        head = new AtomicMarkableReference<Node<T>>(headNode, false); 
    } 
    
    public void addFirst(T value) { 
        addAfter(head.getReference().value, value); 
    } 
    
    public boolean add(T after, T value) { 
        boolean sucessful = false; 
        while (!sucessful) { 
            boolean found = false; 
            for (Node<T> node = head.getReference(); node != null && !isRemoved(node); 
            node = node.next.getReference()) { 
                if (isEqual(node.value, after) && !node.next.isMarked()) { 
                    found = true; 
                    Node<T> nextNode = node.next.getReference(); 
                    Node<T> newNode = new Node<T>(value, nextNode); 
                    sucessful = node.next.compareAndSet(nextNode, newNode, false, false); 
                    break; 
                } 
            } 
            if (!found) { 
                return false; 
            } 
        } 
        return true; 
    } 
    
    public boolean remove(T value) { 
        boolean sucessful = false; 
        while (!sucessful) { 
            boolean found = false; 
            for (Node<T> node = head.getReference(), nextNode = node.next.getReference(); 
            nextNode != null; node = nextNode, nextNode = nextNode.next.getReference()) { 
                if (!isRemoved(nextNode) && isEqual(nextNode.value, value)) { 
                    found = true; 
                    logicallyRemove(nextNode); 
                    sucessful = physicallyRemove(node, nextNode); 
                    break; 
                } 
            } 
            if (!found) { 
                return false; 
            } 
        } 
        return true; 
    } 
    
    void logicallyRemove(Node<T> node) { 
        while (!node.next.attemptMark(node.next.getReference(), true)) { } 
    } 
    
    boolean physicallyRemove(Node<T> leftNode, Node<T> node) { 
        Node<T> rightNode = node; 
        do { 
            rightNode = rightNode.next.getReference(); 
        } while (rightNode != null && isRemoved(rightNode)); 
        return leftNode.next.compareAndSet(node, rightNode, false, false); 
    } 
    
    boolean isRemoved(Node<T> node) { 
        return node.next.isMarked(); 
    } 
    
    boolean isEqual(T arg0, T arg1) { 
        if (arg0 == null) { 
            return arg0 == arg1; 
        } else { 
            return arg0.equals(arg1); 
        } 
    } 
}

推荐阅读

【守望者  j2se】ConcurrentHashMap原理分析
【守望者 j2se】ConcurrentHashMap原
集合是编程中最常用的数据结构。而谈到并发,几乎总是离不开集合这类高级数据
【守望者  j2se】双向链表模拟
【守望者 j2se】双向链表模拟
我们熟悉了java单向链表的模拟,现在我就必须开始双向链表的模拟的.1.基础结构
【守望者 高并发】现有高并发WEB服务器 lighttpd Apache Nginx比较
【守望者 高并发】现有高并发WEB服务器
lighttpd网络服务器基于的Lighttpd的网络服务器具有这样的特点:占用内存资源
【守望者 高并发】C10K/C500K与I/O框架
【守望者 高并发】C10K/C500K与I/O框架
C10K、C/500K问题C10K 的意思是10000并发请求,C500K意思是500 000并发请求,
【守望者  j2se】虚拟机各部分内存溢出情况
【守望者 j2se】虚拟机各部分内存溢出
通过简单的小例子程序,演示java虚拟机各部分内存溢出情况:(1).java堆溢出:
【守望者  JMM】理解volatile内存语义
【守望者 JMM】理解volatile内存语义
理解volatile变量对写多线程程序还是很有帮助的,这样就会避免一上来就是syn这
【守望者 高并发】使用CAS实现高效并发处理
【守望者 高并发】使用CAS实现高效并发
守望者:在并发处理应用中,一般使用锁的方式来解决竞争问题,但锁的效率比较
【守望者  j2se】吃透 java I/O 工作机制-1
【守望者 j2se】吃透 java I/O 工作机
I/O 问题可以说是当今互联网 Web 应用中所面临的主要问题之一,因为当前在这
【守望者 大数据】Mahout学习路线图
【守望者 大数据】Mahout学习路线图
Hadoop家族产品,常用的项目包括Hadoop, Hive, Pig, HBase, Sqoop, Mahout, Z
【守望者 j2se】ConcurrentMap之putIfAbsent(key,value)用法讨论
【守望者 j2se】ConcurrentMap之putIfA
先看一段代码:public class Locale { private final static MapString, Lo
【守望者  javascript】判断IE浏览器世界上最短的代码
【守望者 javascript】判断IE浏览器世
最短的IE判定var ie=!-分析以前最短的IE判定借助于IE不支持垂直制表符的特性
【守望者 大数据】机器学习已成为大数据的基石
【守望者 大数据】机器学习已成为大数
机器学习(Machine Learning, ML)是一门多领域交叉学科,涉及概率论、统计学、
【守望者  j2se】多线程与并发知识点总结
【守望者 j2se】多线程与并发知识点总
对于多线程和并发编程这个比较大的技术模块,我们会整理一些帖子方便知识点的
【守望者  j2se】二叉树模拟
【守望者 j2se】二叉树模拟
接着我们就要写一个比较复杂的数据结构的,但是这个数据结构是很重要的,假如
【守望者 SRS  】SRS 源代码分析笔记(0.9.194)-分析服务器对端口的监听 ...
【守望者 SRS 】SRS 源代码分析笔记(
第一部分 分析服务器对端口的监听 端口监听与初始化(一)全局变量_srs_confi

行业聚焦  面试交流  职位推荐  开发视频   技术交流  腾讯微博  新浪微博

友情链接:课课家教育  阿里云  鲜果  W3Cfuns前端网  中国企业家  环球企业家  投资界  传媒梦工场  MSN中文网  Android开发者社区  cnbeta  投资中国网  又拍云存储  美通说传播  IT茶馆  网商在线  商业评论网  TechOrange  IT时代周刊  3W创新传媒  开源中国社区  二维工坊  Iconfans  推酷  智能电视网  FreeBuf黑客与极客  财经网  DoNews  凤凰财经  新财富  eoe移动开发者社区  i黑马  网易科技  新浪科技  搜狐IT  创业家  创业邦  腾讯财经  福布斯中文网  天下网商  TechWeb  雷锋网  新浪创业  和讯科技  品途O2O  极客公园  艾瑞网  抽屉新热榜  卖家网  人民网通信频道  拉勾网  创新派  简单云主机  

手机版|黑名单|守望者在线 在线教育 linux 高级程序设计 C/C++ 大数据 ( 蜀ICP备14029946号

成都守望者科技有限公司 © 2013-2016 All Rights Reserved