Reader-writers problem using semaphores in Java

Question

I have written my own solution to the Reader-Writers problems using semaphores based on the psuedocode from Wikipedia. I would like to gauge the correctness and quality of the code.

import java.util.concurrent.Semaphore;

class ReaderWritersProblem {

    static Semaphore readLock = new Semaphore(1);
    static Semaphore writeLock = new Semaphore(1);
    static int readCount = 0;

    static class Read implements Runnable {
        @Override
        public void run() {
            try {
                //Acquire Section
                readLock.acquire();
                readCount++;
                if (readCount == 1) {
                    writeLock.acquire();
                }
                readLock.release();

                //Reading section
                System.out.println("Thread "+Thread.currentThread().getName() + " is READING");
                Thread.sleep(1500);
                System.out.println("Thread "+Thread.currentThread().getName() + " has FINISHED READING");

                //Releasing section
                readLock.acquire();
                readCount--;
                if(readCount == 0) {
                    writeLock.release();
                }
                readLock.release();
            } catch (InterruptedException e) {
                System.out.println(e.getMessage());
            }
        }
    }

    static class Write implements Runnable {
        @Override
        public void run() {
            try {
                writeLock.acquire();
                System.out.println("Thread "+Thread.currentThread().getName() + " is WRITING");
                Thread.sleep(2500);
                System.out.println("Thread "+Thread.currentThread().getName() + " has finished WRITING");
                writeLock.release();
            } catch (InterruptedException e) {
                System.out.println(e.getMessage());
            }
        }
    }

    public static void main(String[] args) throws Exception {
        Read read = new Read();
        Write write = new Write();
        Thread t1 = new Thread(read);
        t1.setName("thread1");
        Thread t2 = new Thread(read);
        t2.setName("thread2");
        Thread t3 = new Thread(write);
        t3.setName("thread3");
        Thread t4 = new Thread(read);
        t4.setName("thread4");
        t1.start();
        t3.start();
        t2.start();
        t4.start();
    }
}

Answer 1

The logic looks good in this program, but I am observing that there is a problem with readCount. Suppose if two threads (say t1 and t2) reach readCount++ at the same time. Initially, both will read the readCount value to be 0, and after being incremented by both, the value will be corrupted i.e., it may be 2 and the same will happen with readCount--.

The problem is that, according to the Java memory model, if this read and write for readCount are not atomic, we can declare the readCount as volatile:

volatile static int readCount = 0;

Will volatile resolve the problem:

Again, by declaring the readCount as volatile, it now makes the read and write operations atomic, meaning that every thread will read the updated value of readCount as there will be no optimizations by the compiler (as volatile declared). There will be only one copy of the variable and that will be in main memory, so every thread will read/write the value in main memory only. Now there will no variable copies in thread caches.

But still, this is not the full-proof solution, because increment/decrement operations on any variable are not atomic operations. readCount++ (or readCount--) is not a single operation and consists of these three operations:

1. Read readCount
2. Add one to readCount, i.e. readCount + 1, (readCount - 1, in case of readCount--)
3. Write the value (from step 2) again in readCount

Note: There are lots of links on Google about volatile, such as this one.

In order to solve this problem, I can think of two approaches:

1. synchronized block

   We can write both increment (readCount++) and decrement (readCount--) operations in a synchronized block, because readCount is static. Will use a ReaderWritersProblem.class object for the synchronized block. Now, any thread that wants to enter the block first has to acquire the lock on the ReaderWritersProblem.class object. Then only it can proceed, otherwise it will wait. This way, we can make the increment/decrement operations atomic (which is actually composed of three operations, explained as above):

   Replace readCount++:

   synchronized(ReaderWritersProblem.class) {
       readCount++;
   }
   

   Replace readCount--:

   synchronized(ReaderWritersProblem.class) {
       readCount--;
   }
   

2. AtomicInteger class

   We can use Java in-built atomic concurrent APIs i.e. classes in package java.util.concurrent.atomic. As readCount is of type Integer, we can go for an AtomicInteger class. This class provides methods for increment and decrement operations and guarantees the atomicity of these operations.

   We can modify the code as such:

   Replace the readCount declaration:

   static AtomicInteger readCount = new AtomicInteger(0);
   

   Replace readCount++:

   readCount.getAndIncrement();
   

   Replace readCount--:

   readCount.getAndDecrement();
   

   You can check here for more APIs in the AtomicInteger class.

Answer 2

The readLock semaphore protects the readCount variable, so the original code is fine. No need for additional mechanisms to make it atomic in this case.

Answer 3

There's no need to use synchronize for readers, as you are acquiring the lock for readCount++ and readCount--.

One drawback in your code is the starvation for writers. The first reader has acquired writeLock, and so subsequent readers will keep on coming and will not let readCount become 0. So any waiting writers will always wait for writeLock to be released and will eventually starve.

Answer 4

I would suggest declaring your semaphores as fair:

static Semaphore readLock = new Semaphore(1, true);
static Semaphore writeLock = new Semaphore(1, true);

With that, the threads are placed into a FIFO queue when blocked, so any starvation problems are solved.

BTW, I've added a new version in this post