FIFO queue synchronization

Question

Should FIFO queue be synchronized if there is only one reader and one writer?

Answer 1

What do you mean by "synchronized"? If your reader & writer are in separate threads, you want the FIFO to handle the concurrency "correctly", including such details as:

• proper use of FIFO API should never cause data structures to be corrupted
• proper use of FIFO API should not cause deadlock (although there should be a mechanism for a reader to wait until there is something to read)
• the objects read from the FIFO should be the same objects, in the same order, written to the FIFO (there shouldn't be missing objects or rearranged order)
• there should be a bounded time (one would hope!) between when the writer puts something into the FIFO, and when it is available to the reader.

In the Java world there's a good book on this, Java Concurrency In Practice. There are multiple ways to implement a FIFO that handles concurrency correctly. The simplest implementations are blocking, more complex ones use non-blocking algorithms based on compare-and-swap instructions found on most processors these days.

Answer 2

Yes, if the reader and writer interact with the FIFO queue from different threads.

Answer 3

Try this code for concurrent fifo usage:

public class MyObjectQueue {

private static final ReentrantReadWriteLock lock = new ReentrantReadWriteLock();

private static final ReadLock readLock;

private static final WriteLock writeLock;

private static final LinkedList<MyObject> objects;

static {
    readLock = lock.readLock();
    writeLock = lock.writeLock();
    objects = new LinkedList<MyObject>();
}

public static boolean put(MyObject p) {
    writeLock.lock();
    try {
        objects.push(p);            
        return objects.contains(p);
    } finally {
        writeLock.unlock();
    }
}

public static boolean remove(MyObject p) {
    writeLock.lock();
    try {
        return objects.remove(p);           
    } finally {
        writeLock.unlock();
    }
}

public static boolean contains(MyObject p) {
    readLock.lock();
    try {
        return objects.contains(p);         
    } finally {
        readLock.unlock();
    }
}   

public MyObject get() {
    MyObject o = null;
    writeLock.lock();
    try {
        o = objects.getLast();
    } catch (NoSuchElementException nse) {
        //list is empty
    } finally {
        writeLock.unlock();
    }
    return o;
}

}

Answer 4

Depending on implementation, but most likely. You don't want reader to read partially written data.

Answer 5

Yes, unless its documentation explicitly says otherwise.

(It is possible to implement a specialized FIFO that doesn't need synchronization if there is only one reader and one writer thread, e.g. on Windows using InterlockedXXX functions.)