race condition question

[jimjim]

Hi there,

Considering multiple concurent threads producing - consuming Objects
from the Vector by calling the send() and receive() functions of the
MessageQueue (see below), is a race condition possible? (as there are no
shared data/variables) That is, what may happen if a thread invokes send( )
and be switched with another thread that starts consuming with receive( ) ?
Is there a possibility that sth will break?

Responsible answers please. Do be verbose.
Thank you in advance.
jimijm

public class MessageQueue {
private Vector queue;

public MessageQueue() {
queue = new Vector();
}
public void send(Object item) {
queue.addElement(item);
}
public Object receive() {
Object item;
if (queue.size() == 0)
return null;
else {
item = queue.firstElement();
queue.removeElementAt(0);
return item;
}
}
}

 

[Matt Humphrey]

Hi there,

Considering multiple concurent threads producing - consuming Objects
from the Vector by calling the send() and receive() functions of the
MessageQueue (see below), is a race condition possible? (as there are no
shared data/variables) That is, what may happen if a thread invokes send( )
and be switched with another thread that starts consuming with receive( ) ?
Is there a possibility that sth will break?

Responsible answers please. Do be verbose.
Thank you in advance.
jimijm

public class MessageQueue {
private Vector queue;

public MessageQueue() {
queue = new Vector();
}
public void send(Object item) {
queue.addElement(item);
}
public Object receive() {
Object item;
if (queue.size() == 0)
return null;
else {
item = queue.firstElement();
queue.removeElementAt(0);
return item;
}
}
}

The wording of your question looks suspiciously like a homework assignment.

There are several race conditions possible here, all resulting from the
concurrent execution of a receive and one or more threads doing either a
receive or send. If you think there are no shared variables because the
queue is private, you need to recall that all threads share the data
context. If two or more threads are executing these methods on the same
object they are implicitly sharing data. Now ask yourself what two threads
using the same object will do as they step through the receive method with
the most deliberately inconvenient and mischievious timing possible.

Cheers,
Matt Humphrey (e-mail address removed) http://www.iviz.com/

 

[Filip Larsen]

Considering multiple concurent threads producing - consuming Objects
from the Vector by calling the send() and receive() functions of the
MessageQueue (see below), is a race condition possible? (as there are no
shared data/variables) That is, what may happen if a thread invokes send( )
and be switched with another thread that starts consuming with receive( ) ?
Is there a possibility that sth will break?

public class MessageQueue {
private Vector queue;

public MessageQueue() {
queue = new Vector();
}
public void send(Object item) {
queue.addElement(item);
}
public Object receive() {
Object item;
if (queue.size() == 0)
return null;
else {
item = queue.firstElement();
queue.removeElementAt(0);
return item;
}
}
}

The send method is ok, but the receive method has a race conditionwith
the three queue access and update invokations if there are multiple
consumers. If you only have one consumer the receive method should work,
but I would still recommend that you change it to be safe for multiple
consumers.

A simple approach could be to mark the send and recieve methods as
synchronized. Since Vector already are synchronized, you could also
place a synchronized(queue) block around the 3 queue access invokations
in recive.

Also, you should be aware that removing the first element of a Vector in
general is very inefficient since it has to move all remaining elements
one position over. There are several ways to make an efficient queue,
the simplest being to use LinkedList if you have access to the Java
Collection Framework (part of Java since 1.2). Using LinkedList your
class could look like

public class MessageQueue {

private LinkedList queue = new LinkedList();

public synchronized void send(Object item) {
queue.addLast(item);
}

public synchronized Object receive() {
if (queue.isEmpty()) {
return null;
} else {
return queue.removeFirst();
}
}
}


Finally, note that a consumer is not able to wait for a message with the
above MessageQueue class, it can only poll. If you want to be able to
let a consumer wait for a message, the normal approach is to include a
wait invokation in recieve and a notify invokation in send, like

public class MessageQueue {

private LinkedList queue = new LinkedList();

public synchronized void send(Object item) {
queue.addLast(item);
notifyAll();
}

public synchronized Object receive() throws InterruptedException {
while (queue.isEmpty()) {
wait();
}
return queue.removeFirst();
}
}



Regards,

 

[jimjim]

Filip,

Thank you very much for your reply and the time you have spent.

Your explanation was very clear and has "opened" my eyes! As a test of
whether I understood, I post the following question:
If the Vector's methods were not synchronized, wouldn't there have been a
race condition when two threads were invoking send( ) and receive( )
simultaneously? That is, when each of the threads was executing the
queue.addElement(item) and the queue.removeElementAt(0) methods concurrently
(I assume that the counter of the array storing the elements of the Vector
is shared...if not the counter, there may be other variable shared).
In this case placing a synchronized(queue) block around the 3 queue access
invocations in receive( ) won't deal with the race condition efficiently,
will it?

Thanks again

Regards,
jimjim

 

[Filip Larsen]

jimjim wrote

If the Vector's methods were not synchronized, wouldn't there have been a
race condition when two threads were invoking send( ) and receive( )
simultaneously?

Yes, that is correct. Only very simple methods can be thread-safe
without being synchronized, typically query methods like isEmpty or
size, but even then the methods are often marked synchronized anyway so
that there is no doubt they are meant to be thread-safe.

The containers in the Collections framework, for instance, are not
thread-safe when used directly (no methods on them are synchronized), so
access to them either have to be controlled from another instance, like
with the MessageQueue, or it can be wrapped with a call to one of the
Collections.synchronized<Type> methods. I find that I almost always use
the first approach because I need additional synchronization anyway in
order to avoid race conditions in the use of the container (just like
with the MessageQueue example I gave).

That is, when each of the threads was executing the
queue.addElement(item) and the queue.removeElementAt(0) methods concurrently
(I assume that the counter of the array storing the elements of the Vector
is shared...if not the counter, there may be other variable shared).

Yes, Vector has several member variables that potentially can become out
of sync if the access methods weren't synchronized. You can see the
exact detail for yourself if you browse the code of Vector as found in
the src.zip archive that is part of the J2SDK release. You can get a lot
of insight into the Java API by browsing that code.

In this case placing a synchronized(queue) block around the 3 queue access
invocations in receive( ) won't deal with the race condition efficiently,
will it?

Correct, not unless you place a synchronized(queue) block around the
queue.addElement(item) statement too.


Regards,

 

[jimjim]

Thank you Filip,

and also thank you for your time. We enlightened me well

Kind Regards,
jimjim

P.S: the problem is that I ve got nobody to help me and most of the people
on newsgroups give either wrong/inaccurate or cryptic (i.e look at the other
thread of this discussion) answers. The latter is because they either dont
want to share their knowledge with you, which is egoistic but can be
forgiven as they have spent a lot of time to attain it, or stimulate your
thought just like my professor in my university.

 

[jimjim]

PS: this was not part of a coursework. It was just my wish to learn in depth