通常在一个多线程环境下,我们需要共享某些数据,但为了避免竞争条件引致数据出现不一致的情况,某些代码段需要变成原子操作去执行。这时,我们便需要利用各种同步机制如互斥(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); } } } |
行业聚焦 面试交流 职位推荐 开发视频 技术交流 腾讯微博 新浪微博
友情链接:课课家教育 阿里云 鲜果 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