I'm reading the source code of ConcurrentHashMap
in JDK8, notice that TreeBin
uses a 'read-write' lock to prevent concurrent read and write.
Read threads will go through TreeNodes if there's no concurrent write thread trying to modify the tree structure. When the 'find' operation is done, read thread may:
(1)'CAS' the lockState
and 'unpark' the waiter(writer) thread if it exists.
Following is the 'find()' method in source code.
final Node<K,V> find(int h, Object k) {
if (k != null) {
for (Node<K,V> e = first; e != null; ) {
int s; K ek;
if (((s = lockState) & (WAITER|WRITER)) != 0) {
if (e.hash == h &&
((ek = e.key) == k || (ek != null && k.equals(ek))))
return e;
e = e.next;
}
else if (U.compareAndSwapInt(this, LOCKSTATE, s,
s + READER)) {
TreeNode<K,V> r, p;
try {
p = ((r = root) == null ? null :
r.findTreeNode(h, k, null));
} finally {
Thread w;
// (1)if no more readers, try to unpark the waiter if it exists
if (U.getAndAddInt(this, LOCKSTATE, -READER) ==
(READER|WAITER) && (w = waiter) != null)
LockSupport.unpark(w);
}
return p;
}
}
}
return null;
}
on the other hand, writer thread may:
(2) adding the WAITER
state to lockState
with 'CAS' operation.
(3) set itself to waiter
variable.
(4) 'park' itself.
here's the writer's code:
private final void contendedLock() {
boolean waiting = false;
for (int s;;) {
if (((s = lockState) & ~WAITER) == 0) {
if (U.compareAndSwapInt(this, LOCKSTATE, s, WRITER)) {
if (waiting)
waiter = null;
return;
}
}
else if ((s & WAITER) == 0) {
if (U.compareAndSwapInt(this, LOCKSTATE, s, s | WAITER)) {
waiting = true;
waiter = Thread.currentThread();
}
}
else if (waiting)
LockSupport.park(this);
}
}
HERE IS MY CONFUSION:
If the four operation above run in this order (2) (1) (3) (4), the operation (1) won't unpark anything because 'waiter' was null at that moment.
Then the waiter will park forever without anyone who can unpark it.
The subsequent writes will be all blocked on the intrinsic lock held by the 'parked' thread.
IS THIS A CHANCE OF DEADLOCK ?
I'm really confused about this. I think perhaps I've missed something in the source code. Need your help if you are familiar with it.
In ConcurrentHashMap, at a time any number of threads can perform retrieval operation but for updated in the object, the thread must lock the particular segment in which the thread wants to operate. This type of locking mechanism is known as Segment locking or bucket locking.
Yes, ConcurrentHashMap uses a multitude of locks (by default, 16 of them), each lock controls one segment of the hash. When setting data in a particular segment, the lock for that segment is obtained. When getting data, a volatile read is used.
The ConcurrentHashMap class is similar to HashMap, except that it's thread-safe and allows modification while iteration. It's clear from the output that ConcurrentHashMap takes care of the new entry in the map while iteration whereas HashMap throws ConcurrentModificationException .
There can't be two threads changing things at the same time. The whole point of using such data structures is that they prevent more than one thread updating that "core internal data" at the same time. Having two threads that change the map at the very same point time is not possible.
The question is more than one year old. But it's such a nice puzzle. Here's the answer:
After (2) (1) (3) execution in contendedLock() continues as follows:
if (((s = lockState) & ~WAITER) == 0)
is true because (1) was executed
if (U.compareAndSwapInt(this, LOCKSTATE, s, WRITER))
is also true, because (3) was executed before (s = lockState)
and not after it
Since waiting
was set to true before the execution of (3) the third if statements is also true. Therefore waiter
is set to null and we exit the loop. (4) is never executed.
To sum it up: After (2) (1) (3) operation (4) will never be executed. So there is no chance of deadlock and we can all continue to use ConcurrentHashMap without qualms ;-)
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With