blocked in sending to unbounded LinkedBlockingQueue unless there is no receiver?

Question

I have a simple program to generate inputs to CRC32 which output a number ending with 123456 (in hex). It does bruteforce in a worker thread (the next step would be to make multiple worker threads). The worker thread sends results to the queue q.

import java.util.*;
import java.util.concurrent.*;
import java.util.zip.*;

class A {
    static final BlockingQueue<List<Byte>> q =
        new LinkedBlockingQueue<List<Byte>>();

    static {
        new Thread() {
            public void run() {
                System.out.println("worker thread starting");
                int len = 1;
                byte[] a = new byte[32];
                for (int i =0; i < 32; i++) a[i]=-128;
                while (true) {
                    CRC32 crc = new CRC32();
                    crc.update(a, 0, len);
                    long x = crc.getValue();
                    if ((x & 0xffffff) == 0x123456) {
                        System.out.println("HA " + Arrays.toString(a) + "; " + x);
                        List<Byte> l = new LinkedList<Byte>();
                        for (int i = 0; i < a.length; i++) l.add(a[i]);
                        System.out.println("A");
                        q.add(l);
                        System.out.println("B"); // never reaches here
                    }
                    // generate next guess
                    boolean c = true;
                    for (int i = 0; i < len && c; i++) {
                        c = ++a[i] == -128;
                        if (c) if (i + 2 > len) len = i + 2;
                    }
                }
            }
        }.start();
    }

    // for stats: amount of inputs found per interval
    static long amount = 3;
    static long interval;
    static {
        // record an initial value for interval, so any code using
        // it doesn't have to have a special case to check whether
        // it's initialized
        long start = System.currentTimeMillis();
        while (q.size() != amount);
        interval = System.currentTimeMillis() - start;
    }

    public static void main(String[] args) {
        System.out.println("main");
    }
}

For some reason, it gets stuck:

$ javac A.java && java A
worker thread starting
HA [-49, 72, 73, -128, -128, -128, -128, -128, -128, -128, -128, -128, -128, -128, -128, -128, -128, -128, -128, -128, -128, -128, -128, -128, -128, -128, -128, -128, -128, -128, -128, -128]; 1376924758
A

The worker thread is clearly blocked in sending to the queue (q.add(l)), otherwise, "B" would be printed to the console. If I comment out the line reading from the queue (while (q.size() != amount)), it no longer gets stuck. I thought this behavior is impossible for an unbounded queue (assuming there aren't already 2147483647 elements in it). This is not a SynchronousQueue, so sending to the queue should work regardless of whether any thread is receiving from it. In fact, this behavior seems opposite to SynchronousQueue: sending only works if there is no receiver.

Why is the worker thread being blocked when it tries to send to the queue?

How many cores does your computer have? It's possible that calling `q.add` is waking up the receiver which then enters an infinite loop, which could mean that control would never return to your producer thread if e.g. you're only able to run one thread at a time — Zim-Zam O'Pootertoot, Jul 01 '13 at 15:34
`while (q.size() != amount);` inside a static initializer? Smells like deadlock to me... — Jim Garrison, Jul 01 '13 at 16:56
@JimGarrison: If you take that line out, you will see the worker thread indeed puts over 3 items in the queue. It's the reading of the queue that causes the worker to get blocked when putting the first item, but that shouldn't happen since this is an unbounded non blocking queue. — Dog, Jul 01 '13 at 21:25
You started a thread during class initialization that refers to the potentially incomplete class. This is a major no-no -- you have "leaked" a reference to a not-yet-completely-constructed object. See http://stackoverflow.com/questions/8445966/this-reference-escaping-during-construction — Jim Garrison, Jul 01 '13 at 21:30

John Vint · Accepted Answer · 2013-07-01T16:19:32.667

It's blocked on the synchronized(A.class) not the queue.

When the main thread starts it loads class A. In order to do that it synchronizes on the class itself to effectively load the class. When you start a new thread and try to access the queue, it will try to load the class (since the class hasn't completed loading because of the busy spin in the second static block). Now that the first thread owns the synchronized lock the class, the second thread will sit on the class monitor until the first thread exists the second static (busy spin).

Run the program and kill 3 it to see the thread-dump. You will notice the monitor is on the class and not the queue.

I will try to illustrate this.

Thread-1
 Load Class A
  synchronized(A.class){
    static: create new Thread (call it Thread-2)
    static: busy spin while (q.size() != amount); 

  }

Thread-2 (after first static)
  run(){
     A.q 
      Load Class A
      synchronized(A.class){ //block until Thread-1 releases the lock
           A.q.add(..);
      }
  }

blocked in sending to unbounded LinkedBlockingQueue unless there is no receiver?

1 Answers1