Java ReadWriteLock

http://tutorials.jenkov.com/java-util-concurrent/readwritelock.html

The rules by which a thread is allowed to lock the ReadWriteLock either for reading or writing the guarded resource, are as follows:

Read Lock	If no threads have locked the ReadWriteLock for writing,  and no thread have requested a write lock (but not yet obtained it).  Thus, multiple threads can lock the lock for reading.
Write Lock	If no threads are reading or writing.  Thus, only one thread at a time can lock the lock for writing.

https://www.javaspecialists.eu/archive/Issue165.html


http://jsr166-concurrency.10961.n7.nabble.com/ReentrantReadWriteLock-starvation-td2086.html
Fair RRWLs do what you want by disabling barging completely, but at a very high performance cost

https://stackoverflow.com/questions/8775292/will-readlock-and-writelock-cause-starvation-for-writer


JavaMadeSoEasy.com: Implementation of custom/own ReadWriteLock and 
http://www.careercup.com/question?id=8504437

Implement: read_lock()/read_unlock() and write_lock()/write_unlock()
Given: Mutex.lock & Mutex.unlock

ReentrantReadWriteLock in java - Detailed explanation with full program

custom ReadWriteLock is a  interface, it provides methods  >

• which allows multiple threads to read shared resource at same time, but
• only one thread can write to shared resource at same time.

Problem in the code: use while with wait - check condition again. - best practice.

/** Copyright (c), AnkitMittal JavaMadeSoEasy.com */

interface ReadWriteLock {

   public ReentrantReadWriteLock.WriteLock writeLock();

   public ReentrantReadWriteLock.ReadLock  readLock();

}

class ReentrantReadWriteLock implements ReadWriteLock{

   //Variables to maintain read and write lock count.

   private int readLockCount;

   private int writeLockCount;

   /* Inner class providing readlock */

   private final ReentrantReadWriteLock.ReadLock readerLock;

  

   /* Inner class providing writelock */

   private final ReentrantReadWriteLock.WriteLock writerLock;

   public ReentrantReadWriteLock.WriteLock writeLock() {

      return writerLock;

   }

   public ReentrantReadWriteLock.ReadLock  readLock()  {

      return readerLock;

   }

  

   /**

    * Constructor

    */

   public ReentrantReadWriteLock() {

       readerLock = new ReadLock();

       writerLock = new WriteLock();

   }

  

   /**

    * More than one threads can acquire readLock at a time, provided

    * no other thread is acquiring writeLock at same time.

    */

   public class ReadLock{

          public synchronized void lock() {

                 /*

                 * More than one threads can acquire readLock at a time, provided

                 * no other thread is acquiring writeLock at same time.

                 */

                 if(writeLockCount==0){

                       readLockCount++;

                 }

                 /*

                 * if some other thread is

                 * acquiring write lock at that time,

                 * than current thread waits.

                 */

                 else{

                       try {

                              wait();

                       } catch (InterruptedException e) {

                              e.printStackTrace();

                       }

                 }

          }

          public synchronized void unlock() {

                 readLockCount--; //decrement readLockCount.

                

                 /*

                 * If readLockCount has become 0,

                 * all threads waiting to write will be notified

                 * and can acquire lock.

                 */

                 if(readLockCount==0)

                       notifyAll();

          }

     

   }

  

  

   /**

    * Only one threads can acquire writeLock at a time. Means writeLock

    * can only be obtained if no other thread is acquiring read or

    * write lock at that time.

    */

   public class WriteLock{

          public synchronized void lock() {

                 /*

             * writeLock can only be obtained if no other thread is

                 * acquiring read or write lock at that time.

                 */

                 if(writeLockCount==0 &&

                              readLockCount==0){

                       writeLockCount++;

                 }

                 /*

                 * if some other thread is

                 * acquiring read or write lock at that time,

                 * than current thread waits.

                 */

                 else{

                       try {

                              wait();

                       } catch (InterruptedException e) {

                              e.printStackTrace();

                       }

                 }

          }

          public synchronized void unlock() {

                 writeLockCount--; //decrement writeLockCount.

                 notifyAll(); //notify all waiting threads.

          }

     

   }

}

Read / Write Locks in Java

Read Access	If no threads are writing, and no threads have requested write access.
Write Access	If no threads are reading or writing.

By up-prioritizing write-access requests we assume that write requests are more important than read-requests. Besides, if reads are what happens most often, and we did not up-prioritize writes, starvation could occur. Threads requesting write access would be blocked until all readers had unlocked the ReadWriteLock.  
Therefore a thread can only be granted read access if no thread has currently locked the ReadWriteLock for writing, or requested it locked for writing.

public class ReadWriteLock{

  private int readers       = 0;
  private int writers       = 0;
  private int writeRequests = 0; // Use AtomicInteger

  public synchronized void lockRead() throws InterruptedException{
    while(writers > 0 || writeRequests > 0){
      wait();
    }
    readers++;
  }

  public synchronized void unlockRead(){
    readers--;
    notifyAll();
  }

  public synchronized void lockWrite() throws InterruptedException{
    writeRequests++;

    while(readers > 0 || writers > 0){
      wait();
    }
    writeRequests--;
    writers++;
  }

  public synchronized void unlockWrite() throws InterruptedException{
    writers--;
    notifyAll();
  }
}

The rules for read access are implemented in the lockRead() method. All threads get read access unless there is a thread with write access, or one or more threads have requested write access.

The rules for write access are implemented in the lockWrite() method. A thread that wants write access starts out by requesting write access (writeRequests++). Then it will check if it can actually get write access. A thread can get write access if there are no threads with read access to the resource, and no threads with write access to the resource. How many threads have requested write access doesn't matter.

It is worth noting that both unlockRead() and unlockWrite() calls notifyAll() rather than notify(). To explain why that is, imagine the following situation:

Inside the ReadWriteLock there are threads waiting for read access, and threads waiting for write access. If a thread awakened by notify() was a read access thread, it would be put back to waiting because there are threads waiting for write access. However, none of the threads awaiting write access are awakened, so nothing more happens. No threads gain neither read nor write access. By calling noftifyAll() all waiting threads are awakened and check if they can get the desired access.

Calling notifyAll() also has another advantage. If multiple threads are waiting for read access and none for write access, and unlockWrite() is called, all threads waiting for read access are granted read access at once - not one by one.

Read / Write Lock Reentrance

The ReadWriteLock class shown earlier is not reentrant. If a thread that has write access requests it again, it will block because there is already one writer - itself. Furthermore, consider this case:

1. Thread 1 gets read access.
2. Thread 2 requests write access but is blocked because there is one reader.
3. Thread 1 re-requests read access (re-enters the lock), but is blocked because there is a write request

In this situation the previous ReadWriteLock would lock up - a situation similar to deadlock. No threads requesting neither read nor write access would be granted so.

To make the ReadWriteLock reentrant it is necessary to make a few changes. Reentrance for readers and writers will be dealt with separately.

Read Reentrance

To make the ReadWriteLock reentrant for readers we will first establish the rules for read reentrance:

• A thread is granted read reentrance if it can get read access (no writers or write requests), or if it already has read access (regardless of write requests).

To determine if a thread has read access already a reference to each thread granted read access is kept in a Map along with how many times it has acquired read lock. When determing if read access can be granted this Map will be checked for a reference to the calling thread.

public class ReadWriteLock{

  private Map<Thread, Integer> readingThreads =
      new HashMap<Thread, Integer>();

  private int writers        = 0;
  private int writeRequests  = 0;

  public synchronized void lockRead() throws InterruptedException{
    Thread callingThread = Thread.currentThread();
    while(! canGrantReadAccess(callingThread)){
      wait();                                                                   
    }

    readingThreads.put(callingThread,
       (getAccessCount(callingThread) + 1));
  }


  public synchronized void unlockRead(){
    Thread callingThread = Thread.currentThread();
    int accessCount = getAccessCount(callingThread);
    if(accessCount == 1){ readingThreads.remove(callingThread); }
    else { readingThreads.put(callingThread, (accessCount -1)); }
    notifyAll();
  }


  private boolean canGrantReadAccess(Thread callingThread){
    if(writers > 0)            return false;
    if(isReader(callingThread) return true;
    if(writeRequests > 0)      return false;
    return true;
  }

  private int getReadAccessCount(Thread callingThread){
    Integer accessCount = readingThreads.get(callingThread);
    if(accessCount == null) return 0;
    return accessCount.intValue();
  }

  private boolean isReader(Thread callingThread){
    return readingThreads.get(callingThread) != null;
  }

}

Write reentrance is granted only if the thread has already write access.

public class ReadWriteLock{

    private Map<Thread, Integer> readingThreads =
        new HashMap<Thread, Integer>();

    private int writeAccesses    = 0;
    private int writeRequests    = 0;
    private Thread writingThread = null;

  public synchronized void lockWrite() throws InterruptedException{
    writeRequests++;
    Thread callingThread = Thread.currentThread();
    while(! canGrantWriteAccess(callingThread)){
      wait();
    }
    writeRequests--;
    writeAccesses++;
    writingThread = callingThread;
  }

  public synchronized void unlockWrite() throws InterruptedException{
    writeAccesses--;
    if(writeAccesses == 0){
      writingThread = null;
    }
    notifyAll();
  }

  private boolean canGrantWriteAccess(Thread callingThread){
    if(hasReaders())             return false;
    if(writingThread == null)    return true;
    if(!isWriter(callingThread)) return false;
    return true;
  }

  private boolean hasReaders(){
    return readingThreads.size() > 0;
  }

  private boolean isWriter(Thread callingThread){
    return writingThread == callingThread;
  }
}

Read to Write ReentranceSometimes it is necessary for a thread that have read access to also obtain write access. For this to be allowed the thread must be the only reader.
Write to Read Reentrance

Sometimes a thread that has write access needs read access too. A writer should always be granted read access if requested. If a thread has write access no other threads can have read nor write access, so it is not dangerous. 

Fully Reentrant ReadWriteLock

public class ReadWriteLock{

  private Map<Thread, Integer> readingThreads =
       new HashMap<Thread, Integer>();

   private int writeAccesses    = 0;
   private int writeRequests    = 0;
   private Thread writingThread = null;


  public synchronized void lockRead() throws InterruptedException{
    Thread callingThread = Thread.currentThread();
    while(! canGrantReadAccess(callingThread)){
      wait();
    }

    readingThreads.put(callingThread,
     (getReadAccessCount(callingThread) + 1));
  }

  private boolean canGrantReadAccess(Thread callingThread){
    if( isWriter(callingThread) ) return true;
    if( hasWriter()             ) return false;
    if( isReader(callingThread) ) return true;
    if( hasWriteRequests()      ) return false;
    return true;
  }


  public synchronized void unlockRead(){
    Thread callingThread = Thread.currentThread();
    if(!isReader(callingThread)){
      throw new IllegalMonitorStateException("Calling Thread does not" +
        " hold a read lock on this ReadWriteLock");
    }
    int accessCount = getReadAccessCount(callingThread);
    if(accessCount == 1){ readingThreads.remove(callingThread); }
    else { readingThreads.put(callingThread, (accessCount -1)); }
    notifyAll();
  }

  public synchronized void lockWrite() throws InterruptedException{
    writeRequests++;
    Thread callingThread = Thread.currentThread();
    while(! canGrantWriteAccess(callingThread)){
      wait();
    }
    writeRequests--;
    writeAccesses++;
    writingThread = callingThread;
  }

  public synchronized void unlockWrite() throws InterruptedException{
    if(!isWriter(Thread.currentThread()){
      throw new IllegalMonitorStateException("Calling Thread does not" +
        " hold the write lock on this ReadWriteLock");
    }
    writeAccesses--;
    if(writeAccesses == 0){
      writingThread = null;
    }
    notifyAll();
  }

  private boolean canGrantWriteAccess(Thread callingThread){
    if(isOnlyReader(callingThread))    return true;
    if(hasReaders())                   return false;
    if(writingThread == null)          return true;
    if(!isWriter(callingThread))       return false;
    return true;
  }


  private int getReadAccessCount(Thread callingThread){
    Integer accessCount = readingThreads.get(callingThread);
    if(accessCount == null) return 0;
    return accessCount.intValue();
  }


  private boolean hasReaders(){
    return readingThreads.size() > 0;
  }

  private boolean isReader(Thread callingThread){
    return readingThreads.get(callingThread) != null;
  }

  private boolean isOnlyReader(Thread callingThread){
    return readingThreads.size() == 1 &&
           readingThreads.get(callingThread) != null;
  }

  private boolean hasWriter(){
    return writingThread != null;
  }

  private boolean isWriter(Thread callingThread){
    return writingThread == callingThread;
  }

  private boolean hasWriteRequests(){
      return this.writeRequests > 0;
  }

}

http://www.java2s.com/Code/Java/Threads/ReadWriteLock.htm

http://www.javapractices.com/topic/TopicAction.do?Id=118
http://www.javacodegeeks.com/2012/04/java-concurrency-with-readwritelock.html

Application
how to use ReadWriteLock for achieving ConcurrentHashMap functionality.

public class MyConcurrentHashMap<K,V> {

private Map<K,V> hashMap = new HashMap<>();

//non-fair read write lock

private final ReadWriteLock lock = new ReentrantReadWriteLock();

private final Lock readLock = lock.readLock();

private final Lock writeLock = lock.writeLock();

public MyConcurrentHashMap(){

}

public void put(K key, V value){

writeLock.lock();

try{

hashMap.put(key, value);

}finally{

writeLock.unlock();

}

}

public V get(K key){

readLock.lock();

try{

return hashMap.get(key);

}finally{

readLock.unlock();

}

}

public V remove(K key){

writeLock.lock();

try{

return hashMap.remove(key);

}finally{

writeLock.unlock();

}

}

public boolean containsKey(K key){

readLock.lock();

try{

return hashMap.containsKey(key);

}finally{

readLock.unlock();

}

}

}

http://www.chenguanghe.com/readwritelock/
http://tutorials.jenkov.com/java-concurrency/starvation-and-fairness.html

1. Threads with high priority swallow all CPU time from threads with lower priority.
2. Threads are blocked indefinately waiting to enter a synchronized block, because other threads are constantly allowed access before it.
3. Threads waiting on an object (called wait() on it) remain waiting indefinitely because other threads are constantly awakened instead of it.

Threads with high priority swallow all CPU time from threads with lower priority

You can set the thread priority of each thread individually. The higher the priority the more CPU time the thread is granted. You can set the priority of threads between 1 and 10. Exactly how this is interpreted depends on the operating system your application is running on. For most applications you are better off leaving the priority unchanged.

Threads are blocked indefinitely waiting to enter a synchronized block

Java's synchronized code blocks can be another cause of starvation. Java's synchronized code block makes no guarantee about the sequence in which threads waiting to enter the synchronized block are allowed to enter. This means that there is a theoretical risk that a thread remains blocked forever trying to enter the block, because other threads are constantly granted access before it. This problem is called "starvation", that a thread is "starved to death" by because other threads are allowed the CPU time instead of it.

Threads waiting on an object (called wait() on it) remain waiting indefinitely

A simple implementation of the Lock class could look like this:

public class Lock{
  private boolean isLocked      = false;
  private Thread  lockingThread = null;

  public synchronized void lock() throws InterruptedException{
    while(isLocked){
      wait();
    }
    isLocked      = true;
    lockingThread = Thread.currentThread();
  }

  public synchronized void unlock(){
    if(this.lockingThread != Thread.currentThread()){
      throw new IllegalMonitorStateException(
        "Calling thread has not locked this lock");
    }
    isLocked      = false;
    lockingThread = null;
    notify();
  }
}

A Fair Lock

public class FairLock {
    private boolean           isLocked       = false;
    private Thread            lockingThread  = null;
    private List<QueueObject> waitingThreads =
            new ArrayList<QueueObject>();

  public void lock() throws InterruptedException{
    QueueObject queueObject           = new QueueObject();
    boolean     isLockedForThisThread = true;
    synchronized(this){
        waitingThreads.add(queueObject);
    }

    while(isLockedForThisThread){
      synchronized(this){
        isLockedForThisThread =
            isLocked || waitingThreads.get(0) != queueObject;
        if(!isLockedForThisThread){
          isLocked = true;
           waitingThreads.remove(queueObject);
           lockingThread = Thread.currentThread();
           return;
         }
      }
      try{
        queueObject.doWait();
      }catch(InterruptedException e){
        synchronized(this) { waitingThreads.remove(queueObject); }
        throw e;
      }
    }
  }

  public synchronized void unlock(){
    if(this.lockingThread != Thread.currentThread()){
      throw new IllegalMonitorStateException(
        "Calling thread has not locked this lock");
    }
    isLocked      = false;
    lockingThread = null;
    if(waitingThreads.size() > 0){
      waitingThreads.get(0).doNotify();
    }
  }
}

public class QueueObject {

  private boolean isNotified = false;

  public synchronized void doWait() throws InterruptedException {
    while(!isNotified){
        this.wait();
    }
    this.isNotified = false;
  }

  public synchronized void doNotify() {
    this.isNotified = true;
    this.notify();
  }

  public boolean equals(Object o) {
    return this == o;
  }
}

FairLock creates a new instance of QueueObject and enqueue it for each thread calling lock(). The thread calling unlock() will take the top QueueObject in the queue and call doNotify() on it, to awaken the thread waiting on that object. This way only one waiting thread is awakened at a time, rather than all waiting threads. This part is what governs the fairness of the FairLock.

Also notice that the QueueObject is really a semaphore. The doWait() and doNotify() methods store the signal internally in the QueueObject. This is done to avoid missed signals caused by a thread being preempted just before calling queueObject.doWait(), by another thread which calls unlock() and thereby queueObject.doNotify(). The queueObject.doWait() call is placed outside the synchronized(this) block to avoid nested monitor lockout, so another thread can actually call unlock() when no thread is executing inside the synchronized(this) block in lock() method.

http://blog.guoyb.com/2018/02/11/rwlock
首先，一个常见的误区是，认为在读多写少的情况下，rwlock的性能一定要比mutex高。实际上，rwlock由于区分读锁和写锁，每次加锁时都要做额外的逻辑处理（如区分读锁和写锁、避免写锁“饥饿”等等），单纯从性能上来讲是要低于更为简单的mutex的；但是，rwlock由于读锁可重入，所以实际上是提升了并行性，在读多写少的情况下可以降低时延。

上面的几个例子其实是想说明，对于这种情况，最好的办法还是针对业务场景，做一次性能测试，以实测结果为准绳来选择具体使用哪一种锁。

但是，rwlock有一个非常大的隐患，这个隐患也是由于读锁可重入带来的：读锁的可重入性前提条件是在读锁控制的临界区内，对共享资源只有读操作而没有写操作。然而，对于程序的维护者（非开发者）来说，很容易就忽视了这一点（想想你自己在接手一份别人写的代码时，会特别关注某段代码是rwlock控制的还是mutex控制的吗？），从而在读锁的范围内引入写操作。我认为这是使用读写锁时需要考虑的最严重的一个问题。

Read full article from JavaMadeSoEasy.com: Implementation of custom/own ReadWriteLock and ReentrantReadWriteLock in java - Detailed explanation with full program