Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Java > race condition question

Reply
Thread Tools

race condition question

 
 
jimjim
Guest
Posts: n/a
 
      11-01-2003
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;
}
}
}


 
Reply With Quote
 
 
 
 
Matt Humphrey
Guest
Posts: n/a
 
      11-02-2003

"jimjim" <(E-Mail Removed)> wrote in message
news:ZHWob.3275$(E-Mail Removed)...
> 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 http://www.velocityreviews.com/forums/(E-Mail Removed) http://www.iviz.com/


 
Reply With Quote
 
 
 
 
Filip Larsen
Guest
Posts: n/a
 
      11-02-2003
"jimjim" wrote

> 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,
--
Filip Larsen


 
Reply With Quote
 
jimjim
Guest
Posts: n/a
 
      11-02-2003
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


 
Reply With Quote
 
Filip Larsen
Guest
Posts: n/a
 
      11-02-2003
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,
--
Filip Larsen


 
Reply With Quote
 
jimjim
Guest
Posts: n/a
 
      11-02-2003
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.



 
Reply With Quote
 
jimjim
Guest
Posts: n/a
 
      11-02-2003
PS: this was not part of a coursework. It was just my wish to learn in depth


 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Example code from SwingWorker documentation could have race condition? lionelv@gmail.com Java 3 02-04-2007 07:27 AM
Help Needed : Race condition while removing semaphore(sysvsem semaphore) techi_C C Programming 2 08-10-2006 12:27 PM
Can static member cause a race condition? alexvodovoz@gmail.com ASP .Net 1 08-07-2006 12:17 PM
Race condition on accept() system call using pthread on Red Hat ES 2.1 (kernel 2.4.9) fran C Programming 2 08-10-2004 08:09 PM
Mega Pixel race is like the Mhz Race Hugo Drax Digital Photography 7 01-12-2004 11:07 AM



Advertisments