并發(fā)鏈表中鎖的使用及優(yōu)化
【概念】
如果存在一系列的節(jié)點(diǎn)，以head節(jié)點(diǎn)為開(kāi)始節(jié)點(diǎn)，以b為結(jié)束節(jié)點(diǎn)，且這個(gè)節(jié)點(diǎn)序列中，每個(gè)節(jié)點(diǎn)都指向其successor節(jié)點(diǎn)，則稱節(jié)點(diǎn)b是可達(dá)的。
一個(gè)對(duì)象在集合中當(dāng)且僅當(dāng)這個(gè)對(duì)象從head節(jié)點(diǎn)觸發(fā)時(shí)可達(dá)的。
【案例1】 一個(gè)并發(fā)list的簡(jiǎn)單實(shí)現(xiàn)
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();
}
}
}
上述實(shí)現(xiàn)的優(yōu)缺點(diǎn)分析：
如果并發(fā)量很低時(shí)，這個(gè)
CoarseList是一種非常好的list的實(shí)現(xiàn)。
如果并發(fā)量很大時(shí)，即使鎖的性能很好，則總存在線程出現(xiàn)超時(shí)等待的問(wèn)題。
【案例2】 一種對(duì)案例1的CoarseList的FineList實(shí)現(xiàn)
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方法需要兩把鎖？
反證法： 假設(shè)只使用一把鎖來(lái)實(shí)現(xiàn)FineList的remove方法，比如下面的實(shí)現(xiàn)
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();
}
}
此時(shí)，假設(shè)有兩個(gè)線程A和B來(lái)操作FineList，線程A打算刪除key=a的節(jié)點(diǎn)，線程B打算刪除key=b的節(jié)點(diǎn)，其中節(jié)點(diǎn)a的next指向節(jié)點(diǎn)b。
假設(shè)線程B先調(diào)用remove方法，根據(jù)上述代碼依次獲取head節(jié)點(diǎn)的鎖->釋放head節(jié)點(diǎn)的鎖->獲得a節(jié)點(diǎn)的鎖->釋放a節(jié)點(diǎn)的鎖；線程A后調(diào)用remove方法，獲取head節(jié)點(diǎn)的鎖。此時(shí)，由于head節(jié)點(diǎn)的鎖跟a節(jié)點(diǎn)的鎖是不一樣的，則線程B刪除節(jié)點(diǎn)b的代碼和線程A刪除節(jié)點(diǎn)a的代碼是可以并發(fā)執(zhí)行的，就會(huì)導(dǎo)致如下現(xiàn)象，最終結(jié)果是只刪除了節(jié)點(diǎn)a。
介紹完只用一把鎖來(lái)實(shí)現(xiàn)remove方法存在的問(wèn)題，下面來(lái)分析為什么兩把鎖是成功的？
假設(shè)線程B先調(diào)用remove方法，則鎖的獲取順序?yàn)楂@取head節(jié)點(diǎn)的鎖->釋放head節(jié)點(diǎn)的鎖->獲得a節(jié)點(diǎn)的鎖->獲得b節(jié)點(diǎn)的鎖->釋放b節(jié)點(diǎn)的鎖->釋放a節(jié)點(diǎn)的鎖；線程A后調(diào)用remove方法，則鎖的獲取順序?yàn)楂@取head節(jié)點(diǎn)的鎖->獲得a節(jié)點(diǎn)的鎖->釋放a節(jié)點(diǎn)的鎖->釋放head節(jié)點(diǎn)的鎖。注意兩個(gè)線程此時(shí)會(huì)競(jìng)爭(zhēng)獲取節(jié)點(diǎn)a的鎖，就不會(huì)出現(xiàn)一把鎖的引起的問(wèn)題。
- 不論是
add方法還是remove方法，鎖的獲取順序必須是從head節(jié)點(diǎn)開(kāi)始，然后next引用，直到tail節(jié)點(diǎn)。如果add方法和remove獲取鎖的順序不一樣，就有可能造成死鎖，比如下圖所示：線程A打算添加a節(jié)點(diǎn)，獲取鎖的順序是已經(jīng)獲得b節(jié)點(diǎn)的鎖-->嘗試著再獲取head節(jié)點(diǎn)的鎖；線程B打算刪除節(jié)點(diǎn)b，獲取鎖的順序是已經(jīng)獲得head節(jié)點(diǎn)的鎖-->嘗試著再獲取b節(jié)點(diǎn)的鎖，即
