Make a blocking thread for message queue

Question

I'm making a simple server-client application. I'm handling the message queue this way (class MessageQueue):

private Vector<String> messages;
//Runs from any thread
public void add(String message) {
    synchronized(messages) {
      messages.add(message);
      //This is only way to unstuck messages.wait()
      messages.notifyAll();
    }
}
//Runs from special thread
private void readQueue() {
    Log.debug("Waiting for messages to send.");
    while(run) {
        synchronized(messages) {
          //STUCK HERE!
          try {messages.wait();}catch(InterruptedException e) {}
          //send messages
          ...
        }
    }
}

I designed the code using this answer, but it's wrong or I haven't interpreted it correctly. Here's what happens:

1. Thread readQueue starts.
2. Thread readQueue blocks messages by synchronized block.
3. Thread readQueue blocks itself on messages.wait().
4. Another thread calls add("...") method.
5. Another thread gets stuck on synchronized block.

The messages.notifyAll() can never be called. Of course, originally, before searching, I was trying to do this:

//Runs from special thread
private void readQueue() {
    Log.debug("Waiting for messages to send.");
    while(run) {
        //Wait before getting noticed of new message
        try {messages.wait();}catch(InterruptedException e) {}
        //Block messages, read them, clear them
        synchronized(messages) {
          //send messages
          ...
        }
    }
}

This throws illegal monitor exception, which forces me to put wait into synchronized - and we're just where we begun - stuck.

Answer 1

A thread can't be stuck on the add method, since messages.wait() releases the object monitor. That way when your special thread is wait()ing, other threads are free to enter the synchronized block in add() (but one at a time only).

To prevent your "evil" example, you need a guarding while loop. If the consumer thread is notified, but messages is emptied, it will notice that in the while loop and wait() again.

while(running) {
    synchronized(messages) {
        while(messages.isEmpty())  // Guard against evilness
           try { messages.wait() } catch(InterruptedException e) {}
        // If we get here, messages can't be empty ever
        sendMessage();
    }
}

Edit: The timeline is as follows, Thread1 is producer, Thread2 is consumer.

Thread1 enters synchronized block.
Thread1 adds an item to messages.
Thread1 calls notify.
Thread1 exits synchronized block.
Thread2 enters synchronized block.
Thread2 checks to see if there are messages, and there are.
Thread2 proceeds to send message.
Thread2 exits synchronized block.

OR

Thread2 enters synchronized block.
Thread2 checks to see if there are messages, but there aren't any.
Thread2 waits() and releases the monitor.
Thread1 enters synchronized block.
Thread1 adds an item to messages.
Thread1 calls notify. (Thread2 is released from wait(), but can't run yet since it needs to acquire the monitor.
Thread1 exits synchronized block.
Thread2 acquires the monitor.
Thread2 checks the loop and notices there is a message.
Thread2 sends the message.
Thread2 exits the synchronized block.

Answer 2

So, while noone has given me a solution I've been testing and thinking. As Kayaman has pointed out, wait call releases the variable in current synchronized block. But there is more to it.
Java is smart enough to prevent conflicts and will not release the synchronised of other operations are performed on the variable in the block.

All I had to do was putting the wait and the while that sends messages into different synchronized blocks.
This is correct code that works:

private void readQueue() {
    Log.debug("Waiting for messages to send.");
    while(run) {
        //Calling isEmpty here is a little unsafe but I decided that I don't care
        if(messages.isEmpty()) {
          synchronized(messages) {
            Log.debug("Getting STUCK!");
            //After calling wait, the messages is released, just as expected
            try {messages.wait();}catch(InterruptedException e) {}
          }
        }
        //The sending
        synchronized(messages) {
          //send messages
        }
    }
}

It looks a little silly, but it makes sense. Consider the old, wrong code and a scenario:

//Runs from special thread
private void readQueue() {
    while(run) {
        synchronized(messages) {
          //STUCK HERE!
          try {messages.wait();}catch(InterruptedException e) {}
          //send messages
          ...
        }
    }
}
private void evil() {
    synchronized(messages) {
       messages.notify();
       messages.clear(); 
    }
}

1. readQueue thread enters synchronized block
2. readQueue thread calls messages.wait() and releases messages
3. Another thread runs evil()
4. Evil calls notify and allows readQueue to continue
5. At this moment, two synchronized blocks are operating on messages

I wonder how exactly is the checking implemented and what actions are allowed. I have no proof (e.g. I have found nothing about this in docs) for this but the fact that the first code works for me and the second does not.