Java deadlock when synchronizing on local resources?

I see the problem of multiple thread deadlock in the same line of code

I can't understand why the thread is blocked on the synchronization line below, because there is no other synchronization on the object in the call stack or any other thread Does anyone know what happened or how I can reproduce this problem (currently, 15 threads hit trim () in the loop and process 2000 tasks through my queue - but can't reproduce it)

In the following thread dump, I think multiple threads with "locked" status may be Java bugs: http://bugs.java.com/view_bug.do?bug_id=8047816 In which jstack reports that the thread is in an error state (I use JDK version: 1.7.0_51)

Cheers!

This is the thread view in a thread dump

"xxx>Job Read-3" daemon prio=10 tid=0x00002aca001a6800 nid=0x6a3b waiting for monitor entry [0x0000000052ec4000]
   java.lang.Thread.State: BLOCKED (on object monitor)
    at com.mycompany.collections.CustomQueue.remove(CustomQueue.java:101)
    - locked <0x00002aae6465a650> (a java.util.ArrayDeque)
    at com.mycompany.collections.CustomQueue.trim(CustomQueue.java:318)
    at com.mycompany.collections.CustomQueue.itemProcessed(CustomQueue.java:302)
    at com.mycompany.collections.CustomQueue.trackCompleted(CustomQueue.java:147)
    at java.util.concurrent.ThreadPoolExecutor.afterExecute(UnkNown Source)
    at java.util.concurrent.ThreadPoolExecutor.runWorker(UnkNown Source)
    at java.util.concurrent.ThreadPoolExecutor$Worker.run(UnkNown Source)
    at java.lang.Thread.run(UnkNown Source)

   Locked ownable synchronizers:
    - <0x00002aaf5f9c2680> (a java.util.concurrent.ThreadPoolExecutor$Worker)

"xxx>Job Read-2" daemon prio=10 tid=0x00002aca001a5000 nid=0x6a3a waiting for monitor entry [0x0000000052d83000]
   java.lang.Thread.State: BLOCKED (on object monitor)
    at com.mycompany.collections.CustomQueue.remove(CustomQueue.java:101)
    -  locked <0x00002aae6465a650> (a java.util.ArrayDeque)
    at com.mycompany.collections.CustomQueue.trim(CustomQueue.java:318)
    at com.mycompany.collections.CustomQueue.itemProcessed(CustomQueue.java:302)
    at com.mycompany.collections.CustomQueue.trackCompleted(CustomQueue.java:147)
    at java.util.concurrent.ThreadPoolExecutor.afterExecute(UnkNown Source)
    at java.util.concurrent.ThreadPoolExecutor.runWorker(UnkNown Source)
    at java.util.concurrent.ThreadPoolExecutor$Worker.run(UnkNown Source)
    at java.lang.Thread.run(UnkNown Source)

   Locked ownable synchronizers:
    - <0x00002aaf5f9ed518> (a java.util.concurrent.ThreadPoolExecutor$Worker)

"xxx>Job Read-1" daemon prio=10 tid=0x00002aca00183000 nid=0x6a39 waiting for monitor entry [0x0000000052c42000]
   java.lang.Thread.State: BLOCKED (on object monitor)
    at com.mycompany.collections.CustomQueue.remove(CustomQueue.java:101)
    - waiting to lock <0x00002aae6465a650> (a java.util.ArrayDeque)
    at com.mycompany.collections.CustomQueue.trim(CustomQueue.java:318)
    at com.mycompany.collections.CustomQueue.itemProcessed(CustomQueue.java:302)
    at com.mycompany.collections.CustomQueue.trackCompleted(CustomQueue.java:147)
    at java.util.concurrent.ThreadPoolExecutor.afterExecute(UnkNown Source)
    at java.util.concurrent.ThreadPoolExecutor.runWorker(UnkNown Source)
    at java.util.concurrent.ThreadPoolExecutor$Worker.run(UnkNown Source)
    at java.lang.Thread.run(UnkNown Source)

   Locked ownable synchronizers:
    - <0x00002aaf5f9ecde8> (a java.util.concurrent.ThreadPoolExecutor$Worker)


"xxx>Job Read-0" daemon prio=10 tid=0x0000000006a83000 nid=0x6a36 waiting for monitor entry [0x000000005287f000]
   java.lang.Thread.State: BLOCKED (on object monitor)
        at com.mycompany.collections.CustomQueue.remove(CustomQueue.java:101)
    - waiting to lock <0x00002aae6465a650> (a java.util.ArrayDeque)
    at com.mycompany.collections.CustomQueue.trim(CustomQueue.java:318)
    at com.mycompany.collections.CustomQueue.itemProcessed(CustomQueue.java:302)
    at com.mycompany.collections.CustomQueue.trackCompleted(CustomQueue.java:147)
    at java.util.concurrent.ThreadPoolExecutor.afterExecute(UnkNown Source)
    at java.util.concurrent.ThreadPoolExecutor.runWorker(UnkNown Source)
    at java.util.concurrent.ThreadPoolExecutor$Worker.run(UnkNown Source)
    at java.lang.Thread.run(UnkNown Source)

This is the extracted java code, which shows the location of the error

public class Deadlock {
        final Deque<Object> delegate  = new ArrayDeque<>();
        final long maxSize = Long.MAX_VALUE;

        private final AtomicLong totalExec = new AtomicLong();
        private final Map<Object,AtomicLong> totals = new HashMap<>();
        private final Map<Object,Deque<Long>> execTimes = new HashMap<>();

        public void trim() {
            //Possible optimization is evicting in chunks,segmenting by arrival time
            while (this.totalExec.longValue() > this.maxSize) {
                final Object t = this.delegate.peek();
                final Deque<Long> execTime = this.execTimes.get(t);
                final Long exec = execTime.peek();
                if (exec != null && this.totalExec.longValue() - exec > this.maxSize) {
                    //If Job Started Inside of Window,remove and re-loop
                    remove();
                }
                else {
                    //Otherwise exit the loop
                    break;
                }
            }
        }

        public Object remove() {
            Object removed;
            synchronized (this.delegate) { //4 Threads deadlocking on this line !
                removed = this.delegate.pollFirst();
            }
            if (removed != null) {
                itemRemoved(removed);
            }
            return removed;
        }

        public void itemRemoved(final Object t) {
            //Decrement Total & Queue
            final AtomicLong catTotal = this.totals.get(t);
            if (catTotal != null) {
                if (!this.execTimes.get(t).isEmpty()) {
                    final Long exec = this.execTimes.get(t).pollFirst();
                    if (exec != null) {
                        catTotal.addAndGet(-exec);
                        this.totalExec.addAndGet(-exec);
                    }
                }
            }
        }
    }

Solution

From documentation for HashMap

(emphasize their)

You are reading and writing maps out of sync

I see no reason to think your code is thread safe

I suggest that you cause infinite loops due to lack of thread safety

Input synchronization blocks are relatively slow, so thread dumps may always show at least a few threads waiting to acquire locks