FIFO queue synchronization

Question

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

Answer 1

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

Answer 2

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

Answer 3

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.)

Answer 4

I don't see your point, why that should be done if they access different memory, one in the beginning and another int the end?

Answer 5

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 6

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;
}

}