classic readers-writers algorithm - anything wrong with using a single lock?

1
votes

I'm asking about the classic readers-writers problem: wiki link

I was studying this recently, and I wrote a solution using just a single lock: 

class ReadWrite {
    private Object lock = new Object();
    private boolean isWriting = false;
    private int readerCount = 0;

    public void read() throws InterruptedException {
        synchronized(lock) {
            while (isWriting) {
                lock.wait();
            }
            readerCount++;
        }
        doRead(); // takes some time to read it...
        synchronized(lock) {
            readerCount--;
            lock.notifyAll();
        }
    }

    public void write(int value) throws InterruptedException {
        synchronized(lock) {
            while (readerCount > 0 || isWriting) {
                lock.wait();
            }
            isWriting = true;
        }
        doWrite(value); // takes some time to write it
        synchronized(lock) {
            isWriting = false;
            lock.notifyAll();
        }
    }

    private void doRead() { // omitted }
    private void doWrite(int value) { // omitted }
}

.. then I would create a bunch of threads each calling either read() or write() repeatedly.

That solves the 1st readers/writers problem that favors readers.

...then I see all the references online/books always use two/multiple locks; so I'm not sure if I'm missing anything

I tested it w/ multiple thread configurations, and it actually works fine as in: 1) multiple reads simultaneously 2) only one writer writes at any time while no reading is going on

I solved it up to 3rd readers/writers problem (fairness between readers/writers) augmenting the above solution only slightly and you can see /* edited */ below)

Other than possible efficiency differences, do you see anything wrong algorithm-wise w/ using a single lock for readers/writers problem (at least for 1st readers/writers problem that favor readers)?

edit:

there was a discussion around whether i can solve 3rd readers/writers problem by modifying the original... and get it bounded below 2000ms (100ms read/write * 20 threads) so here it is; you can uncomment all sysouts to see whether exclusive writes still happen, as well as simultaneous reads. i also copy-pasted time-run outputs below.

import java.util.LinkedList;
import java.util.Queue;
import java.util.concurrent.locks.LockSupport;
import java.util.stream.IntStream;

class ReadWrite {
   private Object lock = new Object();
   private boolean isWriting = false;
   private int readerCount = 0;

   Queue<Thread> order = new LinkedList<Thread>();

   public void read(Reader r) throws InterruptedException {
      long start = System.currentTimeMillis();

      synchronized (lock) {
         while (isWriting || (!order.isEmpty() && order.peek() != r)) {

            if (!order.contains(r)) {
               order.add(r);
            }

            lock.wait();
         }

         order.remove(r);
         readerCount++;
         lock.notifyAll();
         // System.out.println("Reader " + r.id + " started reading; readerCount: " + readerCount);
      }

      doRead(r.id); // takes however many seconds to read it...

      synchronized (lock) {
         readerCount--;
         // System.out.println("Reader " + r.id + " finished reading; readerCount: " + readerCount);
         lock.notifyAll();
      }

      long delta = System.currentTimeMillis() - start;
      System.out.println("Reader " + r.id + " delta: " + delta + "");
   }

   public void write(Writer w, int value) throws InterruptedException {
      // System.out.println("Writer " + w.id + " entered write");
      long start = System.currentTimeMillis();

      synchronized (lock) {
         while (readerCount > 0 || isWriting ||  (!order.isEmpty() && order.peek() != w)) {

            if (!order.contains(w)) {
               order.add(w);
            }

            lock.wait();
         }

         order.remove(w);
         isWriting = true;
         // System.out.println("Writer " + w.id + " started writing-----------");
      }

      doWrite(w.id, value);

      synchronized (lock) {
         isWriting = false;

         // System.out.println("Writer " + w.id + " finished writing----------");
         lock.notifyAll();
      }

      long delta = System.currentTimeMillis() - start;
      System.out.println("Writer " + w.id + " delta: " + delta);

      if (delta - 2000 > 10) {
         System.out.println("!!!attention above!!!");
      }
   }

   private void doRead(int readerId) {
      LockSupport.parkNanos(100_000_000L);
   }

   private void doWrite(int writerId, int value) {
      LockSupport.parkNanos(100_000_000L);
   }
}

class Reader extends Thread{
   public int id = 0;
   private ReadWrite rw = null;
   public Reader(int id, ReadWrite rw) {
      this.id = id;
      this.rw = rw;
   }

   @Override
   public void run() {
      while (true) {
         try {
            rw.read(this);
         } catch (InterruptedException e) {
         }
      }
   }
}

class Writer extends Thread {
   public int id = 0;
   private ReadWrite rw = null;

   public Writer(int id, ReadWrite rw) {
      this.id = id;
      this.rw = rw;
   }

   @Override
   public void run() {
      while (true) {
         try {
            rw.write(this, 0);
         } catch (InterruptedException e) {
         }  
      }
   }
}

public class RW {
   public static void main(String[] args) throws InterruptedException {
      ReadWrite rw = new ReadWrite();

      for (int i : IntStream.range(0, 10).toArray()) {
         new Reader(i, rw).start();
      }

      for (int i : IntStream.range(0, 10).toArray()) {
         new Writer(i, rw).start();
      }
   }
}

output from extended run:

Reader 7 delta: 100
Reader 8 delta: 100
Reader 9 delta: 100
Reader 3 delta: 101
Reader 2 delta: 100
Reader 5 delta: 100
Reader 1 delta: 101
Reader 0 delta: 101
Reader 6 delta: 100
Reader 4 delta: 100
Writer 0 delta: 200
Writer 1 delta: 302
Writer 3 delta: 402
Writer 5 delta: 502
Writer 2 delta: 603
Writer 4 delta: 704
Writer 6 delta: 805
Writer 7 delta: 906
Writer 8 delta: 1006
Writer 9 delta: 1106
Reader 8 delta: 1106
Reader 9 delta: 1106
Reader 7 delta: 1106
Reader 5 delta: 1105
Reader 6 delta: 1105
Reader 3 delta: 1106
Reader 2 delta: 1105
Reader 1 delta: 1105
Reader 0 delta: 1105
Reader 4 delta: 1105
Writer 0 delta: 1108
Writer 1 delta: 1107
Writer 3 delta: 1106
Writer 5 delta: 1106
Writer 2 delta: 1105
Writer 4 delta: 1105
Writer 6 delta: 1104
Writer 7 delta: 1104
Writer 8 delta: 1104
Writer 9 delta: 1105
Reader 8 delta: 1105
Reader 7 delta: 1106
Reader 9 delta: 1106
Reader 3 delta: 1107
Reader 5 delta: 1107
Reader 6 delta: 1107
Reader 2 delta: 1107
Reader 4 delta: 1107
Reader 1 delta: 1108
Reader 0 delta: 1108
Writer 0 delta: 1108
Writer 1 delta: 1107
Writer 3 delta: 1108
Writer 5 delta: 1108
Writer 2 delta: 1108
Writer 4 delta: 1109
Writer 6 delta: 1109
Writer 7 delta: 1109
Writer 8 delta: 1109
Writer 9 delta: 1109
Reader 8 delta: 1110
Reader 9 delta: 1109
Reader 7 delta: 1110
Reader 3 delta: 1110
Reader 5 delta: 1111
Reader 4 delta: 1110
Reader 2 delta: 1110
Reader 6 delta: 1110
Reader 0 delta: 1110
Reader 1 delta: 1111
Writer 0 delta: 1111
Writer 1 delta: 1112
Writer 3 delta: 1111
Writer 5 delta: 1112
Writer 2 delta: 1113
Writer 4 delta: 1111
Writer 6 delta: 1112
Writer 7 delta: 1111
Writer 8 delta: 1112
Writer 9 delta: 1112
Reader 8 delta: 1111
Reader 9 delta: 1111
Reader 7 delta: 1111
Reader 5 delta: 1110
Reader 3 delta: 1111
Reader 6 delta: 1110
Reader 4 delta: 1110
Reader 2 delta: 1110
Reader 1 delta: 1110
Reader 0 delta: 1110
Writer 0 delta: 1109
Writer 1 delta: 1109
Writer 3 delta: 1109
Writer 5 delta: 1109
Writer 2 delta: 1109
Writer 4 delta: 1110
Writer 6 delta: 1109
Writer 7 delta: 1109
Writer 8 delta: 1108
Writer 9 delta: 1107
Reader 3 delta: 1105
Reader 7 delta: 1106
Reader 4 delta: 1105
Reader 6 delta: 1105
Reader 8 delta: 1107
Reader 9 delta: 1106
Reader 2 delta: 1105
Reader 1 delta: 1105
Reader 0 delta: 1105
Reader 5 delta: 1107
Writer 0 delta: 1106
Writer 1 delta: 1105
Writer 3 delta: 1106
Writer 5 delta: 1105
Writer 2 delta: 1104
Writer 4 delta: 1103
Writer 6 delta: 1103
Writer 7 delta: 1103
Writer 8 delta: 1103
Writer 9 delta: 1104
Reader 3 delta: 1104
Reader 7 delta: 1105
Reader 8 delta: 1106
Reader 1 delta: 1105
Reader 4 delta: 1106
Reader 6 delta: 1106
Reader 0 delta: 1105
Reader 2 delta: 1105
Reader 9 delta: 1106
Reader 5 delta: 1105
Writer 0 delta: 1105
Writer 1 delta: 1105
Writer 3 delta: 1104
Writer 5 delta: 1105
Writer 2 delta: 1106
Writer 4 delta: 1107
Writer 6 delta: 1109
Writer 7 delta: 1109
Writer 8 delta: 1110
Writer 9 delta: 1110
Reader 7 delta: 1110
Reader 3 delta: 1111
Reader 8 delta: 1110
Reader 1 delta: 1111
Reader 4 delta: 1111
Reader 6 delta: 1112
Reader 0 delta: 1112
Reader 5 delta: 1112
Reader 2 delta: 1112
Reader 9 delta: 1112
Writer 0 delta: 1113
Writer 1 delta: 1113
Writer 3 delta: 1113
Writer 5 delta: 1113
Writer 2 delta: 1113
Writer 4 delta: 1112
Writer 6 delta: 1110
Writer 7 delta: 1111
Writer 8 delta: 1110
Writer 9 delta: 1111
Reader 7 delta: 1110
Reader 3 delta: 1111
Reader 8 delta: 1110
Reader 1 delta: 1110
Reader 4 delta: 1110
Reader 6 delta: 1109
Reader 0 delta: 1110
Reader 5 delta: 1109
Reader 9 delta: 1109
Reader 2 delta: 1109
Writer 0 delta: 1109
Writer 1 delta: 1111
Writer 3 delta: 1112
Writer 5 delta: 1111
Writer 2 delta: 1111
Writer 4 delta: 1111
Writer 6 delta: 1112
Writer 7 delta: 1112
Writer 8 delta: 1112
Writer 9 delta: 1111
Reader 7 delta: 1111
Reader 3 delta: 1110
Reader 8 delta: 1111
Reader 4 delta: 1112
Reader 1 delta: 1112
Reader 5 delta: 1112
Reader 6 delta: 1113
Reader 0 delta: 1112
Reader 2 delta: 1113
Reader 9 delta: 1113
Writer 0 delta: 1112
Writer 1 delta: 1111
Writer 3 delta: 1110
Writer 5 delta: 1110
Writer 2 delta: 1109
Writer 4 delta: 1109
Writer 6 delta: 1108
Writer 7 delta: 1108
Writer 8 delta: 1109
Writer 9 delta: 1109
Reader 7 delta: 1109
Reader 3 delta: 1109
Reader 1 delta: 1107
Reader 4 delta: 1107
Reader 8 delta: 1109
Reader 9 delta: 1106
Reader 0 delta: 1107
Reader 2 delta: 1106
Reader 6 delta: 1107
Reader 5 delta: 1107
Writer 0 delta: 1107
Writer 1 delta: 1106
Writer 3 delta: 1107
Writer 5 delta: 1109
Writer 2 delta: 1110
Writer 4 delta: 1110
Writer 6 delta: 1111
Writer 7 delta: 1110
Writer 8 delta: 1109
Writer 9 delta: 1109
Reader 7 delta: 1109
Reader 1 delta: 1109
Reader 3 delta: 1110
Reader 4 delta: 1109
Reader 8 delta: 1110
Reader 0 delta: 1109
Reader 9 delta: 1109
Reader 6 delta: 1109
Reader 2 delta: 1109
Reader 5 delta: 1109
Writer 0 delta: 1109
Writer 1 delta: 1110
Writer 3 delta: 1110
Writer 5 delta: 1109
Writer 2 delta: 1108
Writer 4 delta: 1109
Writer 6 delta: 1108
Writer 7 delta: 1109
Writer 8 delta: 1111
Writer 9 delta: 1111
Reader 1 delta: 1111
Reader 7 delta: 1112
Reader 3 delta: 1111
Reader 4 delta: 1111
Reader 8 delta: 1111
Reader 9 delta: 1111
Reader 6 delta: 1111
Reader 0 delta: 1111
Reader 2 delta: 1112
Reader 5 delta: 1112
Writer 0 delta: 1111
Writer 1 delta: 1111
Writer 3 delta: 1110
Writer 5 delta: 1109
Writer 2 delta: 1109
Writer 4 delta: 1110
Writer 6 delta: 1110
Writer 7 delta: 1110
Writer 8 delta: 1108
Writer 9 delta: 1107
Reader 1 delta: 1107
Reader 7 delta: 1108
Reader 3 delta: 1108
Reader 4 delta: 1109
Reader 8 delta: 1108
Reader 0 delta: 1109
Reader 6 delta: 1109
Reader 9 delta: 1109
Reader 2 delta: 1109
Reader 5 delta: 1109
Writer 0 delta: 1108
Writer 1 delta: 1108
Writer 3 delta: 1108
Writer 5 delta: 1108
Writer 2 delta: 1109
Writer 4 delta: 1107
Writer 6 delta: 1107
Writer 7 delta: 1107
Writer 8 delta: 1107
Writer 9 delta: 1108
Reader 1 delta: 1108
Reader 4 delta: 1107
Reader 7 delta: 1108
Reader 3 delta: 1108
Reader 8 delta: 1108
Reader 6 delta: 1107
Reader 0 delta: 1107
Reader 5 delta: 1107
Reader 9 delta: 1108
Reader 2 delta: 1107
Writer 0 delta: 1107
Writer 1 delta: 1107
Writer 3 delta: 1108
Writer 5 delta: 1109
Writer 2 delta: 1109
Writer 4 delta: 1109
Writer 6 delta: 1110
Writer 7 delta: 1109
Writer 8 delta: 1110
Writer 9 delta: 1110
Reader 1 delta: 1109
Reader 3 delta: 1109
Reader 4 delta: 1109
Reader 7 delta: 1109
Reader 0 delta: 1109
Reader 5 delta: 1108
Reader 8 delta: 1109
Reader 6 delta: 1109
Reader 9 delta: 1109
Reader 2 delta: 1109
Writer 0 delta: 1110
Writer 1 delta: 1111
Writer 3 delta: 1111
Writer 5 delta: 1110
Writer 2 delta: 1110
Writer 4 delta: 1111
Writer 6 delta: 1111
Writer 7 delta: 1112
Writer 8 delta: 1111
Writer 9 delta: 1110
Reader 1 delta: 1111
Reader 3 delta: 1110
Reader 4 delta: 1111
Reader 0 delta: 1111
Reader 5 delta: 1111
Reader 7 delta: 1112
Reader 8 delta: 1112
Reader 6 delta: 1112
Reader 2 delta: 1112
Reader 9 delta: 1112
Writer 0 delta: 1111
Writer 1 delta: 1110
Writer 3 delta: 1109
Writer 5 delta: 1110
Writer 2 delta: 1109
Writer 4 delta: 1110
Writer 6 delta: 1110
Writer 7 delta: 1109
Writer 8 delta: 1110
Writer 9 delta: 1111
Reader 1 delta: 1111
Reader 3 delta: 1112
Reader 4 delta: 1111
Reader 5 delta: 1110
Reader 0 delta: 1110
Reader 7 delta: 1112
Reader 8 delta: 1111
Reader 6 delta: 1111
Reader 9 delta: 1110
Reader 2 delta: 1110
Writer 0 delta: 1111
Writer 1 delta: 1111
Writer 3 delta: 1112
Writer 5 delta: 1112
Writer 2 delta: 1112
Writer 4 delta: 1110
Writer 6 delta: 1110
Writer 7 delta: 1111
Writer 8 delta: 1110
Writer 9 delta: 1110
Reader 1 delta: 1109
Reader 3 delta: 1109
Reader 5 delta: 1109
Reader 4 delta: 1109
Reader 7 delta: 1108
Reader 8 delta: 1108
Reader 0 delta: 1110
Reader 6 delta: 1108
Reader 9 delta: 1108
Reader 2 delta: 1108
Writer 0 delta: 1107
Writer 1 delta: 1108
Writer 3 delta: 1107
Writer 5 delta: 1107
Writer 2 delta: 1107
Writer 4 delta: 1107
Writer 6 delta: 1107
Writer 7 delta: 1106
Writer 8 delta: 1106
Writer 9 delta: 1105
Reader 1 delta: 1105
Reader 3 delta: 1105
Reader 5 delta: 1106
Reader 4 delta: 1106
Reader 7 delta: 1105
Reader 0 delta: 1106
Reader 8 delta: 1106
Reader 6 delta: 1106
Reader 9 delta: 1106
Reader 2 delta: 1106
Writer 0 delta: 1107
Writer 1 delta: 1106
Writer 3 delta: 1106
Writer 5 delta: 1106
Writer 2 delta: 1107
Writer 4 delta: 1107
Writer 6 delta: 1107
Writer 7 delta: 1107
Writer 8 delta: 1108
Writer 9 delta: 1108
Reader 1 delta: 1109
Reader 3 delta: 1108
Reader 5 delta: 1108
Reader 7 delta: 1109
Reader 4 delta: 1109
Reader 8 delta: 1108
Reader 0 delta: 1108
Reader 9 delta: 1109
Reader 2 delta: 1109
Reader 6 delta: 1109
Writer 0 delta: 1108
Writer 1 delta: 1108
Writer 3 delta: 1109
Writer 5 delta: 1108
Writer 2 delta: 1108
Writer 4 delta: 1108
Writer 6 delta: 1107
Writer 7 delta: 1108
Writer 8 delta: 1107
Writer 9 delta: 1107
Reader 1 delta: 1106
Reader 3 delta: 1107
Reader 5 delta: 1107
Reader 7 delta: 1106
Reader 0 delta: 1108
Reader 8 delta: 1108
Reader 4 delta: 1108
Reader 9 delta: 1108
Reader 2 delta: 1108
Reader 6 delta: 1108
Writer 0 delta: 1109
Writer 1 delta: 1111
Writer 3 delta: 1111
Writer 5 delta: 1111
Writer 2 delta: 1110
Writer 4 delta: 1110
Writer 6 delta: 1111
Writer 7 delta: 1111
Writer 8 delta: 1112
Writer 9 delta: 1112
Reader 1 delta: 1113
Reader 3 delta: 1112
Reader 5 delta: 1112
Reader 0 delta: 1110
Reader 7 delta: 1112
Reader 8 delta: 1111
Reader 9 delta: 1110
Reader 4 delta: 1111
Reader 6 delta: 1110
Reader 2 delta: 1110
Writer 0 delta: 1110
Writer 1 delta: 1108
Writer 3 delta: 1107
Writer 5 delta: 1108
Writer 2 delta: 1108
Writer 4 delta: 1108
Writer 6 delta: 1108
Writer 7 delta: 1107
Writer 8 delta: 1106
Writer 9 delta: 1107
Reader 1 delta: 1106
Reader 3 delta: 1106
Reader 5 delta: 1105
Reader 0 delta: 1106
Reader 7 delta: 1106
Reader 8 delta: 1106
Reader 4 delta: 1106
Reader 9 delta: 1106
Reader 6 delta: 1106
Reader 2 delta: 1107
Writer 0 delta: 1106
Writer 1 delta: 1107
Writer 3 delta: 1108
Writer 5 delta: 1108
Writer 2 delta: 1109
Writer 4 delta: 1110
Writer 6 delta: 1109
Writer 7 delta: 1110
Writer 8 delta: 1111
Writer 9 delta: 1110
Reader 3 delta: 1110
Reader 5 delta: 1110
Reader 1 delta: 1110
Reader 7 delta: 1110
Reader 0 delta: 1110
Reader 4 delta: 1110
Reader 8 delta: 1110
Reader 9 delta: 1110
Reader 2 delta: 1110
Reader 6 delta: 1111
Writer 0 delta: 1110
Writer 1 delta: 1110
Writer 3 delta: 1109
Writer 5 delta: 1109
Writer 2 delta: 1109
Writer 4 delta: 1110
Writer 6 delta: 1110
Writer 7 delta: 1110
Writer 8 delta: 1110
Writer 9 delta: 1110
Reader 3 delta: 1111
Reader 0 delta: 1111
Reader 5 delta: 1112
Reader 7 delta: 1111
Reader 1 delta: 1112
Reader 9 delta: 1110
Reader 8 delta: 1110
Reader 4 delta: 1110
Reader 2 delta: 1110
Reader 6 delta: 1110
Writer 0 delta: 1110
Writer 1 delta: 1110
Writer 3 delta: 1110
Writer 5 delta: 1109
Writer 2 delta: 1109
Writer 4 delta: 1107
Writer 6 delta: 1108
Writer 7 delta: 1107
Writer 8 delta: 1107
Writer 9 delta: 1108
Reader 3 delta: 1107
Reader 1 delta: 1107
Reader 9 delta: 1107
Reader 0 delta: 1107
Reader 7 delta: 1107
Reader 5 delta: 1107
Reader 6 delta: 1107
Reader 2 delta: 1107
Reader 4 delta: 1108
Reader 8 delta: 1108
Writer 0 delta: 1108
Writer 1 delta: 1107
Writer 3 delta: 1108
Writer 5 delta: 1108
Writer 2 delta: 1107
Writer 4 delta: 1108
Writer 6 delta: 1107
Writer 7 delta: 1109
Writer 8 delta: 1109
Writer 9 delta: 1108
Reader 3 delta: 1108
Reader 1 delta: 1108
Reader 9 delta: 1108
Reader 7 delta: 1109
Reader 0 delta: 1109
Reader 5 delta: 1109
Reader 8 delta: 1109
Reader 2 delta: 1109
Reader 6 delta: 1109
Reader 4 delta: 1109
Writer 0 delta: 1108
Writer 1 delta: 1110
Writer 3 delta: 1109
Writer 5 delta: 1109
Writer 2 delta: 1109
Writer 4 delta: 1108
Writer 6 delta: 1108
Writer 7 delta: 1106
Writer 8 delta: 1107
Writer 9 delta: 1107
Reader 1 delta: 1107
Reader 3 delta: 1108
Reader 9 delta: 1107
Reader 0 delta: 1107
Reader 5 delta: 1107
Reader 7 delta: 1107
Reader 8 delta: 1107
Reader 6 delta: 1107
Reader 2 delta: 1107
Reader 4 delta: 1107
Writer 0 delta: 1108
Writer 1 delta: 1107
Writer 3 delta: 1107
Writer 5 delta: 1108
Writer 2 delta: 1109
Writer 4 delta: 1110
Writer 6 delta: 1111
Writer 7 delta: 1112
Writer 8 delta: 1110
Writer 9 delta: 1111
Reader 3 delta: 1111
Reader 1 delta: 1111
Reader 5 delta: 1111
Reader 9 delta: 1112
Reader 0 delta: 1111
Reader 7 delta: 1112
Reader 6 delta: 1112
Reader 2 delta: 1112
Reader 4 delta: 1112
Reader 8 delta: 1112
Writer 0 delta: 1111
Writer 1 delta: 1111
Writer 3 delta: 1113
Writer 5 delta: 1112
Writer 2 delta: 1112
Writer 4 delta: 1111
Writer 6 delta: 1110
Writer 7 delta: 1109
Writer 8 delta: 1109
Writer 9 delta: 1109
Reader 3 delta: 1108
Reader 1 delta: 1108
Reader 9 delta: 1108
Reader 0 delta: 1108
Reader 5 delta: 1108
Reader 2 delta: 1108
Reader 7 delta: 1109
Reader 4 delta: 1108
Reader 6 delta: 1108
Reader 8 delta: 1108
Writer 0 delta: 1110
Writer 1 delta: 1109
Writer 3 delta: 1107
Writer 5 delta: 1107
Writer 2 delta: 1107
Writer 4 delta: 1107
Writer 6 delta: 1107
Writer 7 delta: 1108
Writer 8 delta: 1108
Writer 9 delta: 1108
Reader 3 delta: 1109
Reader 9 delta: 1109
Reader 1 delta: 1110
Reader 7 delta: 1108
Reader 4 delta: 1108
Reader 2 delta: 1108
Reader 0 delta: 1110
Reader 8 delta: 1108
Reader 5 delta: 1110
Reader 6 delta: 1108
Writer 0 delta: 1106
Writer 1 delta: 1106
Writer 3 delta: 1106
Writer 5 delta: 1107
Writer 2 delta: 1106
Writer 4 delta: 1106
Writer 6 delta: 1106
Writer 7 delta: 1106
Writer 8 delta: 1106
Writer 9 delta: 1106
Reader 3 delta: 1105
Reader 9 delta: 1105
Reader 1 delta: 1105
Reader 4 delta: 1105
Reader 7 delta: 1105
Reader 2 delta: 1105
Reader 8 delta: 1105
Reader 0 delta: 1105
Reader 5 delta: 1105
Reader 6 delta: 1105
Writer 0 delta: 1106
Writer 1 delta: 1107
Writer 3 delta: 1108
Writer 5 delta: 1107
Writer 2 delta: 1108

so it gets bounded under the max expected time;

1
javamultithreadingalgorithm
I'd say by checking readerCount and isWriting you're actually implementing additional locks. – Thomas

1 Answers

1
votes

Seems that your code still does not solve the third problem and gives a preference to the readers over writers. As wiki says:

Therefore, the third readers-writers problem is sometimes proposed, which adds the constraint that no thread shall be allowed to starve; that is, the operation of obtaining a lock on the shared data will always terminate in a bounded amount of time.

Let's create 10 reader and 10 writer threads:

public static void main(String[] args) throws InterruptedException {
    ReadWrite rw = new ReadWrite();
    for(int i : IntStream.range(0, 10).toArray()) {
        new Thread(() -> {
            while(true) {
                try {
                    rw.read(i);
                } catch (InterruptedException e) {}
            }
        }, "Reader #"+i).start();
    }
    for(int i : IntStream.range(0, 10).toArray()) {
        new Thread(() -> {
            while(true) {
                try {
                    rw.write(i, i);
                } catch (InterruptedException e) {}
            }
        }, "Writer #"+i).start();
    }
}

Let the doRead and doWrite just sleep 100 ms:

private void doRead(int readerId) { 
    LockSupport.parkNanos(100_000_000L);
}

private void doWrite(int writerId, int value) {
    LockSupport.parkNanos(100_000_000L);
}

And let's print how long it takes to perform the write:

public void write(int writerId, int value) throws InterruptedException {
   long start = System.currentTimeMillis();
   ... all your code ...
   long delta = System.currentTimeMillis()-start;
   System.out.println("Write delta: "+delta);
}

I removed other prints. Now I see the following output:

Write delta: 200
Write delta: 200
Write delta: 600
Write delta: 800
Write delta: 1000
Write delta: 1099
Write delta: 1300
Write delta: 1500
Write delta: 600
Write delta: 1899
...
Write delta: 2700
Write delta: 4399
Write delta: 2100
Write delta: 1900
...
Write delta: 2800
Write delta: 3400
Write delta: 6999
Write delta: 900
Write delta: 1300
Write delta: 2500
...
Write delta: 1800
Write delta: 2800
Write delta: 7802
Write delta: 2600
...

I expect the maximal delta around 2000 ms: we have 20 concurrent threads, each takes around 100 ms to run, so we should wait at most that all other threads finish the current operation. But we should not wait for some other thread several times. Actually I observe maximal delta 2000-2100 when I replace your implementation with standard JDK ReentrantReadWriteLock. In your case delays can be several times longer and seems that there's no guaranteed maximum (in longer run I observe higher delays as well). Thus I would not say that your code solves the 3rd problem.