Multiple readers and multiple writers(i mean multiple) synchronization

Question

I am developing a feature that needs a variant of read/write lock that can allow concurrent multiple writers.

Standard read/write lock allows either multiple readers or single writer to run concurrently. I need a variant that can allow multiple readers or multiple writers concurrently. So, it should never allow a reader and a writer concurrently. But, its okay to allow multiple writers at the same time or multiple readers at the same time.

I hope I was clear. I couldn't find any existing algorithm so far. I can think of couple of ways to do this using some queues and etc. But, I dont want to take a risk of doing it myself unless none exists.

Do you guys know of any existing scheme?

Thanks,

Answer 1

The concept you are looking for is a Reentrant lock. You need to be able to try to acquire the lock and not get blocked if the lock is already taken (this is known as reentrant lock). There is a native implementation of a reentrant lock in java so I will illustrate this example in Java. (http://docs.oracle.com/javase/1.5.0/docs/api/java/util/concurrent/locks/ReentrantLock.html).

Because when using tryLock() you don't get blocked if the lock is not available your writer/reader can proceed. However, you only want to release the lock when you're sure that no one is reading/writing anymore, so you will need to keep the count of readers and writers. You will either need to synchronize this counter or use a native atomicInteger that allows atomic increment/decrement. For this example I used atomic integer.

Class ReadAndWrite {
 private ReentrantLock readLock;
 private ReentrantLock writeLock;
 private AtomicInteger readers;
 private AtomicInteger writers;
 private File file;

 public void write() {
   if (!writeLock.isLocked()) {
    readLock.tryLock();
    writers.incrementAndGet(); // Increment the number of current writers
    // ***** Write your stuff *****
    writers.decrementAndGet(); // Decrement the number of current writers
    if (readLock.isHeldByCurrentThread()) {
     while(writers != 0); // Wait until all writers are finished to release the lock
     readLock.unlock();
    }
   } else {
     writeLock.lock();
     write();
   }
  }

 public void read() {
   if (!readLock.isLocked()) {
    writeLock.tryLock();
    readers.incrementAndGet(); 
    // ***** read your stuff *****
    readers.decrementAndGet(); // Decrement the number of current read
    if (writeLock.isHeldByCurrentThread()) {
     while(readers != 0); // Wait until all writers are finished to release the lock
     writeLock.unlock();
    }
   } else {
     readLock.lock();
     read();
   }
  }

What's happening here: First you check if your lock is locked to know if you can perform the action you're going to perform. If it's locked it means you can't read or write so you use lock to put yourself in wait state and re-call the same action when the lock is freed again.

If it's not locked, then you lock the other action (if you're going to read you lock writes and vice-versa) using tryLock. tryLock doesn't block if it's already locked, so several writers can write at the same time and several readers can read at the same time. When the number of threads doing the same thing as you reaches 0 it means that whoever held the lock in the first place can now release it. The only inconvenience with this solution is that the thread that holds the lock will have to stay alive until everyone is finished to be able to release it.

Answer 2

If you are using pthreads, take a look at the synchronization approach in this question.

You could use a similar approach with two variables readerCount and writerCount and a mutex. In a reader thread you would lock the mutex and wait for writerCount == 0. If this is condition is met, you increment the readerCount by 1 and release the lock. Then you do the reading. When you are done, you lock the mutex again, decrement the readerCount, signal the condition change and release the lock.

The writer thread follows the same logic but waits for the condition readerCount == 0 and increments/decrements writerCount instead.

Answer 3

I did have a solution along the lines of nifs comment. I have posted my solution below. The problem is with fairness policy. Starvation can easily happen. In my approach, one kind of thread is less likely than other. So I am just getting away with giving priority to girls. Ideally we want this to be with some decent fairness policy.

/**
 * RestRoomLock:
 *
 * This lock tries to simulate a gender based access to common rest room.
 * It is okay to have multiple boys or multiple girls inside the room. But,
 * we can't have boys and girls at the same time inside the room.
 *
 * This implementation doesn't really have proper fairness policy. For now,
 * girls are being treated with priority as long as boys are being gentle,
 * boyEntryBeGentle();
 *
 * @author bmuppana
 */
public class RestRoomLock {
    int boysInside;
    int girlsInside;
    int girlsWaiting;


    RestRoomLock() {
        boysInside = girlsInside = girlsWaiting = 0;
    }

    public synchronized void boyEntry() {
        while (girlsInside > 0) {
            try {
                wait();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
        boysInside++;
    }

    public synchronized void boyEntryBeGentle() {
        while (girlsInside + girlsWaiting > 0) {
            try {
                wait();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
        boysInside++;
    }

    public synchronized void boyExit() {
        boysInside--;
        assert boysInside >= 0;

        notifyAll();
    }

    public synchronized void girlEntry() {
        girlsWaiting++;
        while (boysInside > 0) {
            try {
                wait();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
        girlsWaiting--;

        girlsInside++;
    }

    public synchronized void girlExit() {
        girlsInside--;
        assert girlsInside >= 0;

        notifyAll();
    }
}