Thread blocked forever when waits on lock operation

Question

I'm writing a java implementation for two-phase locking. So, I'm using Reentrant lock (ReadWrite lock). The problem is that when a thread executes the lock.readLock.lock() or lock.writeLock().lock() and the lock is already locked it stuck their forever even when the lock unlocked by using lock.readLock().unlock() or lock.writeLock().unlock(). So, it looks like the unlock doesn't wakeup the waiters!!! here is the code that causes the problem:

class LockTable
{
//    /*******************************************************************************
//     * This class is used to represent an individual lock.
//     * @param tid     the id of the transaction holding the lock
//     * @param shared  whether the lock is shared (true) or exclusive (false)
//     */
//    void Lock (int tid, boolean shared)
//    {
//        Semaphore sem = new Semaphore (0);
//    } // Lock class

    /** Associative map of locks held by transactions of the form (key = oid, value = lock)
     */
    private HashMap<Integer,MyLock> locks;

    public LockTable(){
        locks= new HashMap<Integer,MyLock>();

    }

    /*******************************************************************************
     * Acquire a shared/read lock on data object oid.
     * @param tid  the transaction id
     * @param oid  the data object id
     */
    void rl (int tid, int oid) throws InterruptedException
    {

        MyLock lock=null;
        boolean wait = false;
        synchronized(this) {
            try {
                lock = locks.get(oid);             // find the lock

                if((lock != null) && (lock.lock.isWriteLocked())){

                   wait = true;

                  // System.out.println(locks.get(oid).shared);
                }

                if(lock == null){
                 lock = new MyLock(tid, true);
                 lock.lock.readLock().lock();
                 lock.readers.add(tid);
                 locks.put(oid, lock);
              }

            } catch(Exception e) {
                System.out.println(e.getStackTrace());        // lock not found, so oid is not locked;
            } // try
        }//synch


        if (wait){

            System.out.println("Transaction " + tid + " is waiting..");
            Main.g.addEdge(tid, lock.tid);
                    if(Main.g.hasCycle())
                        restart(tid);

            //to exclude the restarted thread
            if(!Main.trans[tid].terminate){

                lock.lock.readLock().lock();
                Main.g.removeEdge(tid, lock.tid);
                synchronized(this){
                lock.readers.add(tid);
                }//synchronized
            }//if isInturrupted
            else
                return;
        }
       else
        synchronized(this) {
              lock.lock.readLock().lock();
              lock.readers.add(tid);
      } // synchronized

    } // rl

    /*******************************************************************************
     * Acquire an exclusive/write lock on data object oid.
     * @param tid  the transaction id
     * @param oid  the data object id
     */
    void wl (int tid, int oid) throws InterruptedException
    {
         //type to determine the last lock type in order
         //to be able to remove the edges from waitfor graph
        int type = 0;
        MyLock lock = null;
        boolean wait = false;

        synchronized(this) {
            try {
                lock = locks.get(oid);             // find the lock
                if(lock != null && (lock.lock.isWriteLocked() || lock.readers.size() > 0))
                {
                    wait = true;
                }
                if(lock == null){
                    lock = new MyLock(tid);
                    lock.lock.writeLock().lock();
                    locks.put(oid,lock);
                }
            } catch(Exception e) {
                System.out.println(e.getStackTrace());        // lock not found, so oid is not locked;
            } // try
      }
         if (wait){
                System.out.println("Transaction " + tid + " is waiting..");
                if(lock.lock.isWriteLocked())
                    Main.g.addEdge(tid, lock.tid);
                else{
                    type = 1;
                    for(int reader : lock.readers)
                         Main.g.addEdge(tid, reader);
                    }//else

                            if(Main.g.hasCycle())
                            {
                                restart(tid);
                            }//if
           if(!Main.trans[tid].terminate){
                System.out.println("I'm waiting here in wl");
                lock.lock.writeLock().lock();
                System.out.println("Wakeup..");
                if(type == 0)
                    Main.g.removeEdge(tid, lock.tid);
                else
                    for(int reader : lock.readers)
                        Main.g.removeEdge(tid, reader);
                lock.tid = tid;
             }
            else
                return;

        }// if(wait) ==> for the lock to be released
        else 
            lock.lock.writeLock().lock();

    } // wl

    void restart(int tid){
     synchronized(this) {
        MyLock lock;
        List<Integer> toRemove = new ArrayList();
        for(int i : locks.keySet()){
           lock = locks.get(i);

               //lock.sem.release();
               if(lock.lock.isWriteLockedByCurrentThread()){

                   System.out.println("Transaction"+tid+" unlock object "+ i +" in order to restart");
                   lock.lock.writeLock().unlock();
                    System.out.println("number of write holders: " + lock.lock.writeLock().getHoldCount());
                    System.out.println("number of read holders: " + lock.lock.getReadHoldCount());
                    System.out.println("number of waiters: " + lock.lock.getQueueLength());
                   toRemove.add(i);

               }
           if(!lock.lock.isWriteLocked())
               if(lock.readers.contains(tid)){
                   // lock.numberOfReaders --;

                      System.out.println("Transaction"+tid+" unlock object "+ i +" in order to restart");
                      lock.readers.remove(lock.readers.indexOf(tid));
                      lock.lock.readLock().unlock();
                      System.out.println("number of write holders: " + lock.lock.getWriteHoldCount());
                      System.out.println("number of read holders: " + lock.lock.getReadHoldCount());
                      System.out.println("number of waiters: " + lock.lock.getQueueLength());
                      toRemove.add(i);  

                  }//if
        }//for
        for(int i = 0; i < toRemove.size() ; i ++)
            locks.remove(toRemove.get(i));
        Main.g.removeEdges(tid);

       // Thread.currentThread().interrupt();
        Main.trans[tid].terminate = true;

        System.out.println("Transaction" + tid + " restarted");

        }//sync
    }

    /*******************************************************************************
     * Unlock/release the lock on data object oid.
     * @param tid  the transaction id
     * @param oid  the data object id
     */
    void ul (int tid, int oid)
    {
       MyLock lock = null;
        boolean error = false;
        synchronized(this) {
            try {
                lock = locks.get(oid);                    // find the lock
                if( lock == null)
                    System.out.println("println: lock not found");

            } catch(Exception e) {
                System.out.println("lock not found");   // lock not found
            } // try
        }//sync
            if((lock != null) && (lock.lock.isWriteLockedByCurrentThread())){

                      System.out.println("tid: " + tid + " unlock object: " + oid);
                      lock.lock.writeLock().unlock();
                      System.out.println("done with unlock");
                      System.out.println("number of write holders: " + lock.lock.writeLock().getHoldCount());
                      System.out.println("number of read holders: " + lock.lock.getReadHoldCount());
                      System.out.println("number of waiters: " + lock.lock.getQueueLength());
          }// if lock != null
            else
              if((lock != null) && (lock.readers.size()>0)){
                  if(lock.readers.contains(tid)){
                    lock.readers.remove(lock.readers.indexOf(tid));
                    lock.lock.readLock().unlock();
                    System.out.println("Transaction"+tid+" unlocked shared lock on object "+oid);
                    //System.out.println("number of write holders: " + lock.lock.readLock().);
                    System.out.println("number of read holders: " + lock.lock.getReadHoldCount());
                    System.out.println("number of waiters: " + lock.lock.getQueueLength());

                  }//if lock.readers
              }//if


        if (error) 
            System.out.println ("Error: ul: no lock for oid = " + oid + " found/owned");
    } // ul

Answer 1

Method A:
...snip...
synchronized(this) {
    ...snip...
    lock.lock.readLock().lock();
    ...snip...
}

Method B:
...snip...
synchronized(this) {
    ...snip...
    lock.lock.readLock().unlock();
    ...snip...
}

The problem you are having is a deadlock from basically blocking on one synchronizer while holding another. When you call Lock.lock() inside of a synchronized(this) code block, the Thread will enter a BLOCKING state while continuing to hold the intrinsic lock on this. Since the Thread which actually holds the Lock as to obtain the intrinsic-lock on this and the intrinsic -lock will never be released, you have a deadlock.

For example:
Thread1 enters Method A, obtains a lock on this
Thread2 enters Method A, can't obtain this so blocks
Thread1 obtains Readlock
Thread1 releases this
Thread2 obtains this
Thread2 blocks waiting for Readlock
Thread1 enters Method B, can't obtain this so blocks
deadlocked

Answer 2

also, don't forget about the non-happy path. make sure to put your unlock() inside of a finally, otherwise if an exception gets thrown, unlock() is never called and you end up in deadlock.