并发链表中锁的使用及优化
【概念】
如果存在一系列的节点，以head节点为开始节点，以b为结束节点，且这个节点序列中，每个节点都指向其successor节点，则称节点b是可达的。
一个对象在集合中当且仅当这个对象从head节点触发时可达的。
【案例1】 一个并发list的简单实现
package com.reign.gcmob.concurrency;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;
public class CoarseList<T> {
private class Node {
T item;
int key;
Node next;
public Node(int key) {
this.key = key;
}
public Node(T item) {
this.item = item;
}
}
private Node head;
private Lock lock = new ReentrantLock();
public CoarseList() {
head = new Node(Integer.MIN_VALUE);
head.next = new Node(Integer.MAX_VALUE);
}
public boolean add(T item) {
Node pred, curr;
int key = item.hashCode();
lock.lock();
try {
pred = head;
curr = pred.next;
while (curr.key < key) {
pred = curr;
curr = curr.next;
}
if (key == curr.key) {
return false;
} else {
Node node = new Node(item);
node.next = curr;
pred.next = node;
return true;
}
} finally {
lock.unlock();
}
}
public boolean remove(T item) {
Node pred, curr;
int key = item.hashCode();
lock.lock();
try {
pred = head;
curr = pred.next;
while (curr.key < key) {
pred = curr;
curr = curr.next;
}
if (key == curr.key) {
pred.next = curr.next;
return true;
} else {
return false;
}
} finally {
lock.unlock();
}
}
}
上述实现的优缺点分析：
如果并发量很低时，这个
CoarseList是一种非常好的list的实现。
如果并发量很大时，即使锁的性能很好，则总存在线程出现超时等待的问题。
【案例2】 一种对案例1的CoarseList的FineList实现
public class FineList<T> {
private class Node {
T item;
int key;
Node next;
private Lock lock = new ReentrantLock();
public Node(int key) {
this.key = key;
}
public Node(T item) {
this.item = item;
}
public void lock() {
lock.lock();
}
public void unlock() {
lock.unlock();
}
}
private Node head;
public FineList() {
head = new Node(Integer.MIN_VALUE);
head.next = new Node(Integer.MAX_VALUE);
}
public boolean add(T item) {
int key = item.hashCode();
head.lock();
Node pred = head;
try {
Node curr = pred.next;
curr.lock();
try {
while (curr.key < key) {
pred.unlock();
pred = curr;
curr = curr.next;
curr.lock();
}
if (curr.key == key) {
return false;
}
Node newNode = new Node(item);
newNode.next = curr;
pred.next = newNode;
return true;
} finally {
curr.unlock();
}
} finally {
pred.unlock();
}
}
public boolean remove(T item) {
Node pred = null, curr = null;
int key = item.hashCode();
head.lock();
try {
pred = head;
curr = pred.next;
curr.lock();
try {
while (curr.key < key) {
pred.unlock();
pred = curr;
curr = curr.next;
pred.lock();
curr.lock();
}
if (curr.key == key) {
pred.next = curr.next;
return true;
}
return false;
} finally {
curr.unlock();
}
} finally {
pred.unlock();
}
}
}
分析：
- 为什么
FineList的remove方法需要两把锁？
反证法： 假设只使用一把锁来实现FineList的remove方法，比如下面的实现
public boolean remove(T item) {
Node pred = null, curr = null;
int key = item.hashCode();
head.lock();
try {
pred = head;
curr = pred.next;
while (curr.key < key) {
pred.unlock();
pred = curr;
curr = curr.next;
pred.lock();
}
if (curr.key == key) {
pred.next = curr.next;
return true;
}
return false;
} finally {
pred.unlock();
}
}
此时，假设有两个线程A和B来操作FineList，线程A打算删除key=a的节点，线程B打算删除key=b的节点，其中节点a的next指向节点b。
假设线程B先调用remove方法，根据上述代码依次获取head节点的锁->释放head节点的锁->获得a节点的锁->释放a节点的锁；线程A后调用remove方法，获取head节点的锁。此时，由于head节点的锁跟a节点的锁是不一样的，则线程B删除节点b的代码和线程A删除节点a的代码是可以并发执行的，就会导致如下现象，最终结果是只删除了节点a。
介绍完只用一把锁来实现remove方法存在的问题，下面来分析为什么两把锁是成功的？
假设线程B先调用remove方法，则锁的获取顺序为获取head节点的锁->释放head节点的锁->获得a节点的锁->获得b节点的锁->释放b节点的锁->释放a节点的锁；线程A后调用remove方法，则锁的获取顺序为获取head节点的锁->获得a节点的锁->释放a节点的锁->释放head节点的锁。注意两个线程此时会竞争获取节点a的锁，就不会出现一把锁的引起的问题。
- 不论是
add方法还是remove方法，锁的获取顺序必须是从head节点开始，然后next引用，直到tail节点。如果add方法和remove获取锁的顺序不一样，就有可能造成死锁，比如下图所示：线程A打算添加a节点，获取锁的顺序是已经获得b节点的锁-->尝试着再获取head节点的锁；线程B打算删除节点b，获取锁的顺序是已经获得head节点的锁-->尝试着再获取b节点的锁，即
