Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Is it possible to get a deadlock with ConcurrentHashMap in this circumstance?

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.

like image 771
Kyne Xiao Avatar asked Mar 23 '19 14:03

Kyne Xiao


People also ask

How does locking happen in ConcurrentHashMap?

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.

Does ConcurrentHashMap use locks?

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.

Is ConcurrentHashMap values thread-safe?

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 .

Can multiple threads write in ConcurrentHashMap at the same time?

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.


1 Answers

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

like image 101
rmunge Avatar answered Oct 11 '22 20:10

rmunge