[ 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);