截取原文:
交替锁(hand-over-hand locking)
设想我们要在链表中插入一个节点。一种做法是用锁保护整个链表,但链表加锁时其他使用者无法访问链表。而交替锁可以只锁住链表的一部分,允许不涉及被锁部分的其他线程自由访问链表,。。。
插入新的链表节点时,需要将待插入位置两边的节点加锁。首先锁住链表的前两个节点。如果这两节点之间不是待插入位置,那么就解锁第一个节点,并锁住第三个节点。如果被锁住的两个节点之间仍不是待插入
位置,就解锁第二个节点,并锁住第四个节点。以此类推,直到找到待插入位置并插入新的节点,最后解锁两边的节点。
这种交替式的加锁和解锁顺序是无法用内置锁实现的,但使用ReentrantLock就可以在需要的地方抵用lock()和unlock()。我们用下面的类来实现使用交替锁的有序链表。
class ConcurrentSortedList {
private class Node {
int value;
Node prev;
Node next;
ReentrantLock lock = new ReentrantLock();
Node() {}
Node(int value, Node prev, Node next) {
this.value = value; this.prev = prev; this.next = next;
}
}
private final Node head;
private final Node tail;
public ConcurrentSortedList() {
head = new Node(); tail = new Node();
head.next = tail; tail.prev = head;
}
public void insert(int value) {
Node current = head;
current.lock.lock();
try {
while(true) {
next.lock.lock();
try {
if(next == tail || next.value < value) {
Node node = new Node(value, current, next);
next.prev = node;
current.next = node;
return;
}
} finally { current.lock.unlock(); }
current = next;
next = current.next;
}
} finally { next.lock.unlock(); }
}
}
这种方案不仅可以让多个线程并发地进行链表插入操作,还能让其他的链表操作安全地并发。比如计算链表节点个数,只需倒序遍历链表即可。
public int size() {
Node current = tail;
int count = 0;
while(current.prev != head) {
ReentrantLock lock = current.lock();
lock.lock();
try {
++count;
current = current.prev;
} finally { lock.unlock(); }
}
return count;
}
=======================分隔线========================
分析:
文中利用ReentrantLock实现了一对交替锁,对待插入位置的前后两个节点进行锁定同步,从而提供了对有序链表并发插入操作的支持。
作者说:“这种方案不仅可以让多个线程并发地进行链表插入操作,还能让其他的链表操作安全地并发。比如计算链表节点个数,只需倒序遍历链表即可”
随后作者给出一段代码示例,从链表的尾向前依次遍历,遍历过程中对遍历节点加锁,然后++count,然后解锁,从而统计出链表的节点个数。
以下是我的几点疑问:
问题一:为何作者选择倒序遍历?顺序不可以吗?
我估计作者是考虑锁的争用问题,如果倒序,将是相向而行,锁争用最多发生一次(锁相遇的地方),而如果顺序,将是同向而行,锁争用次数会增多。
不知是否是这个原因,有请大神指点。
问题二:这样真的如作者所说,size()方法可以支持并发吗?
我觉得这样支持不了并发,作者好像忽略了这样一种情况:插入发生在锁相遇之后,就是size()从后向前加锁,insert()从前向后加锁,当发生锁相遇之后insert()才找到插入位置,执行插入操作,这样size()方法统计的是插入之前的链表节点数。
。。。
我表述得不是很清楚,如果有哪位大神看过此书这部分,求教此块内容。
线程与锁一章中“交替锁”的并发有疑问
|
最新讨论 · · · · · · (全部)
我还是很想知道黄炎兄在本书2.2节(15页)开始使用...(aphasiac)
> 我来回应