race condition question

Discussion in 'Java' started by jimjim, Nov 1, 2003.

  1. jimjim

    jimjim Guest

    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;
    }
    }
    }
     
    jimjim, Nov 1, 2003
    #1
    1. Advertising

  2. "jimjim" <> wrote in message
    news:ZHWob.3275$...
    > 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.iviz.com/
     
    Matt Humphrey, Nov 2, 2003
    #2
    1. Advertising

  3. jimjim

    Filip Larsen Guest

    "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
     
    Filip Larsen, Nov 2, 2003
    #3
  4. jimjim

    jimjim Guest

    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
     
    jimjim, Nov 2, 2003
    #4
  5. jimjim

    Filip Larsen Guest

    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
     
    Filip Larsen, Nov 2, 2003
    #5
  6. jimjim

    jimjim Guest

    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, Nov 2, 2003
    #6
  7. jimjim

    jimjim Guest

    PS: this was not part of a coursework. It was just my wish to learn in depth
     
    jimjim, Nov 2, 2003
    #7
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    1
    Views:
    356
    Kevin Spencer
    Aug 7, 2006
  2. Replies:
    3
    Views:
    749
  3. fran
    Replies:
    2
    Views:
    520
  4. techi_C
    Replies:
    2
    Views:
    1,446
    Richard Bos
    Aug 10, 2006
  5. Replies:
    2
    Views:
    555
Loading...

Share This Page