Uploaded image for project: 'JDK'
  1. JDK
  2. JDK-8255753

"Writer preference" of ReentrantReadWriteLock is deadlock prone

    XMLWordPrintable

    Details

      Description

      ADDITIONAL SYSTEM INFORMATION :
      This is a pure JAVA problem.

      java version "1.8.0_131"
      Java(TM) SE Runtime Environment (build 1.8.0_131-b11)
      Java HotSpot(TM) Client VM (build 25.131-b11, mixed mode, sharing)

      I'm not sure if this problem is present in nowadays "long term support" version but You can easily check if the ReentrantReadWriteLock source was updated in between.

      A DESCRIPTION OF THE PROBLEM :
      The ReentrantReadWriteLock is "writer preffering", that is if there is a waiting reader and a waiting writer then the reader is NOT let in before the writer is let in.

      In certain conditions this leads to deadlock (see below example).

      The condition is quite tricky to reproduce, but happens in a real life:

      1.Have two read-write protected resources.
      2.Have two readers, which do need to access both at once. Make them to lock resources in different order. Notice, with "many readers-one writer" this out-of-order locking should NOT create any problems at all.
      3.Have two separate threads, each updating each of resources by grabbing a single write lock. Again it shouldn't be a deadlock-prone condition.

      In a very specific order of events (as in an example) a pending writer request will put on hold one of criss-crossed read requests. If there would be no criss-crossing everything would be solved. Due to criss crossing however the writer prefference blocks readers from entering and system freezes.

      STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
      Run below test in console. Observe a freeze.

      EXPECTED VERSUS ACTUAL BEHAVIOR :
      EXPECTED -
      1 - syncing
      3 - syncing
      2 - syncing
      4 - syncing
      1 - aquiring read lock on A
      1 - aquired read lock on A
      2 - aquiring read lock on B
      2 - aquired read lock on B
      3 - aquiring write lock on A
      4 - aquiring write lock on B
      2 - aquiring read lock on A
      2 - aquired read lock on A
      1 - aquiring read lock on B
      1 - aquired read lock on B
      2 - releasing read lock on A
      2 - releasing read lock on B
      2 - done
      1 - releasing read lock on B
      1 - releasing read lock on A
      1 - done
      4 - aquired write lock on B
      3 - aquired write lock on A
      4 - releasing write lock on B
      4 - B.done()
      3 - releasing write lock on A
      3 - A.done()

      Note: This output was produced with an alternative implementation which is a rip-off of Your code with removed fairness and writer prefference.
      ACTUAL -


      1 - syncing
      2 - syncing
      3 - syncing
      4 - syncing
      1 - aquiring read lock on A
      1 - aquired read lock on A
      2 - aquiring read lock on B
      2 - aquired read lock on B
      3 - aquiring write lock on A
      4 - aquiring write lock on B
      2 - aquiring read lock on A
      1 - aquiring read lock on B
      ... and freeze

      ---------- BEGIN SOURCE ----------
      import java.util.concurrent.locks.*;
      import java.util.concurrent.*;
      /**
      An example showing how standard read-write lock may deadlock.
      */
      public final class DeadlockingReadWriteLock
      {
      static ReadWriteLock A = new ReentrantReadWriteLock(false);
      static ReadWriteLock B = new ReentrantReadWriteLock(false);
      //static ReadWriteLock A = new sztejkat.utils.ipc.CReentrantReadWriteLock();
      //static ReadWriteLock B = new sztejkat.utils.ipc.CReentrantReadWriteLock();
      static CyclicBarrier synch = new CyclicBarrier(4);

      public static void main(String []a)throws Throwable
      {
      //Start readers
      new Thread()
      {
      public void run()
      {
      try{
      System.out.println("1 - syncing");
      synch.await();
      System.out.println("1 - aquiring read lock on A");
      A.readLock().lock();
      System.out.println("1 - aquired read lock on A");
      Thread.sleep(2000);
      System.out.println("1 - aquiring read lock on B");
      B.readLock().lock();
      System.out.println("1 - aquired read lock on B");
      Thread.sleep(1000);
      System.out.println("1 - releasing read lock on B");
      B.readLock().unlock();
      System.out.println("1 - releasing read lock on A");
      A.readLock().unlock();
      System.out.println("1 - done");
      }catch(Exception ex){ System.out.println(ex);};
      };
      }.start();
      new Thread()
      {
      public void run()
      {
      try{
      System.out.println("2 - syncing");
      synch.await();
      Thread.sleep(1000);
      System.out.println("2 - aquiring read lock on B");
      B.readLock().lock();
      System.out.println("2 - aquired read lock on B");
      Thread.sleep(1000);
      System.out.println("2 - aquiring read lock on A");
      A.readLock().lock();
      System.out.println("2 - aquired read lock on A");
      Thread.sleep(1000);
      System.out.println("2 - releasing read lock on A");
      A.readLock().unlock();
      System.out.println("2 - releasing read lock on B");
      B.readLock().unlock();
      System.out.println("2 - done");
      }catch(Exception ex){ System.out.println(ex);};
      };
      }.start();
      new Thread()
      {
      public void run()
      {
      try{
      System.out.println("3 - syncing");
      synch.await();
      Thread.sleep(1500);
      System.out.println("3 - aquiring write lock on A");
      A.writeLock().lock();
      System.out.println("3 - aquired write lock on A");
      Thread.sleep(1000);
      System.out.println("3 - releasing write lock on A");
      A.writeLock().unlock();
      System.out.println("3 - A.done()");
      }catch(Exception ex){ System.out.println(ex);};
      };
      }.start();
      new Thread()
      {
      public void run()
      {
      try{
      System.out.println("4 - syncing");
      synch.await();
      Thread.sleep(1500);
      System.out.println("4 - aquiring write lock on B");
      B.writeLock().lock();
      System.out.println("4 - aquired write lock on B");
      Thread.sleep(1000);
      System.out.println("4 - releasing write lock on B");
      B.writeLock().unlock();
      System.out.println("4 - B.done()");
      }catch(Exception ex){ System.out.println(ex);};
      };
      }.start();
      };
      };
      ---------- END SOURCE ----------

      CUSTOMER SUBMITTED WORKAROUND :
      None, except writing own read-write lock implementation.

      Notice, I'm aware that out-of-order locking in case of exclusive locks is deadlock prone, but I wouldn't ever expect it be also deadlock prone in case of "many readers - single writer" locking scheme. The whole idea of this scheme is to "not bother about read locking" across the entire system.

      I'm also aware, than in a plain single lock case this "writer prefference" prevents system starvation and many applications may depend on that so changing it to "reader prefference" is not an option.

      I would be glad to see in JDK a second, alternative ReadWriteLock implementation which will be "reader preffering" and will be deadlock-proof and unfair obviously at the cost of possible starvation.

      FREQUENCY : always


        Attachments

          Activity

            People

            Assignee:
            dl Doug Lea
            Reporter:
            webbuggrp Webbug Group
            Votes:
            0 Vote for this issue
            Watchers:
            4 Start watching this issue

              Dates

              Created:
              Updated: