User level Locking Approach With synchronizedMap & ReentrantLock

I want to achieve user based locking as shown in below code.

If on user "1234" (java.lang.String.class identifier) some process is happening, or user is being used by some process, other processes should wait for that process to complete. Simple as that it sounds, I tried making it work using ReenterrentLock but I get stuck in perpetual waiting state and deadlock, though I was about to make it work using synchronised block, I wanted to achieve this with ReenterrentLock.

Below is my code & logs.

Let me know what I am doing wrong.

//Research.java file
  public static final int PERIOD = 10;
  public static final int END_INCLUSIVE = 23;
  public static final int N_THREADS = 8;

  public static void main(String[] args) {
    final ExecutorService executorService = Executors.newFixedThreadPool(N_THREADS);
    IntStream.rangeClosed(1, END_INCLUSIVE).forEach(value -> executorService.submit(() -> {
      final String user = value % 2 == 0 ? "1234" : "5678";
      process(value + "process", user);
    }));
    executorService.shutdown();
  }

  private static void process(String tag, String user) {
    System.out.println("waiting tag=" + tag + ",user=" + user + ",TH=" + Thread.currentThread().getName());
    AccountLock.getInstance().lock(user);
    System.out.println("in tag=" + tag + ",user=" + user + ",TH=" + Thread.currentThread().getName());
    sleep(tag, PERIOD);
    AccountLock.getInstance().unlock(user);
    System.out.println("out tag=" + tag + ",user=" + user + ",TH=" + Thread.currentThread().getName());
  }

  private static void sleep(String tag, long s) {
    boolean interrupt = false;
    try {
      TimeUnit.SECONDS.sleep(s);
    } catch (InterruptedException e) {
      interrupt = true;
      e.printStackTrace();
    } finally {
      if (interrupt) {
        Thread.currentThread().interrupt();
      }
    }
  }

/**
 * AccountLock
 */
final class AccountLock {
  private static final Map<String, Lock> LOCK_MAP = Collections.synchronizedMap(new HashMap<>());
  private static volatile AccountLock INSTANCE;

  private AccountLock() {
  }

  public static AccountLock getInstance() {
    if (INSTANCE == null) {
      synchronized (AccountLock.class) {
        if (INSTANCE == null) {
          INSTANCE = new AccountLock();
        }
      }
    }
    return INSTANCE;
  }

  public void lock(String user) {
    LOCK_MAP.computeIfPresent(user, (s, lock) -> {
      lock.lock();
      return lock;
    });
    LOCK_MAP.computeIfAbsent(user, s -> {
      final ReentrantLock lock = new ReentrantLock(true);
      lock.lock();
      return lock;
    });
  }

  public void unlock(String user) {
    LOCK_MAP.computeIfPresent(user, (s, lock) -> {
      lock.unlock();
      return null;
    });
  }
}

//logs
//waiting tag=2process,user=1234,TH=pool-1-thread-2
//waiting tag=3process,user=5678,TH=pool-1-thread-3
//waiting tag=1process,user=5678,TH=pool-1-thread-1
//waiting tag=4process,user=1234,TH=pool-1-thread-4
//waiting tag=5process,user=5678,TH=pool-1-thread-5
//in tag=3process,user=5678,TH=pool-1-thread-3
//in tag=4process,user=1234,TH=pool-1-thread-4
//in tag=5process,user=5678,TH=pool-1-thread-5
//waiting tag=6process,user=1234,TH=pool-1-thread-6
//waiting tag=7process,user=5678,TH=pool-1-thread-7
//waiting tag=8process,user=1234,TH=pool-1-thread-8

Let me know if you need thread dumps for the same.

I am using java8 on mac

Solution

The deadlock spawns from the interaction of your map, and the locks.

More precisely : you use a Collections.syncrhonized map, which in effect, puts a mutual exclusion on every (or so) method of the orignal map instance.

That means, for example, that as long as someone is inside a computeIfAbsent (or computeIfPresent) call, then no other method can be called on the map instance.

Up to this point no problem.

Except that, inside the computeIfxx calls, you do another locking operation, by acquiring lock instances.

Having two different locks AND not maintaining a strict lock acquisition order is the perfect recipe to deadlock, which you demonstrate here.

A sample chronology :

Thread T1 enters the Map (acquires the lock M), creates a Lock L1 and acquires it. T1 holds M and L1.
Thread T1 exists the map.computeXX, releasing M. T1 holds L1 (only).
Thread T2 enters the map (acquires M). T1 holds L1, T2 holds M.
Thread T2 tries to acquire L1 (the same one as T1), is blocked by T1. T1 holds L1, T2 holds M and waits for L1. Do you see it coming ?
Thread T1 is done. It wants to release L1, so tries to enter the map, which means trying to acquire M, which is held by T2. T1 holds L1, waits for M. T2 holds M, waits for L1. Game over.

The solution : it is tempting to not try to create the lock and take it at the same time, e.g. do not acquire the lock when inside a locked method. Let's try (just to make a point, you'll see how hard it gets).

If you break this embedded lock pattern, you'll never have lock/unlock calls when your threads already have another lock, preventing any deadlock pattern (deadlocks can not occur with a single reentrant lock).

Which means : change your AccountLock class from a locking instance to a lock factory instance. Or if you want to integrate stuff, do it differently.

lock(String user) {
    LOCKS.computeIfAbsent(user, u -> new ReentrantLock()).lock();
}

by moving the lock acquisition outside the map's method call, i've removed it from the map's mutex, and I eliminated the deadlock possibility.

With that corrected, I created another bug.

On the unlock side, you use computeIfPresent which returns null. That means that once done with a lock, you intend to remove it from the map. This is all well, but it creates a race condition in the unlock case.

T1 creates lock L1 for user 1, puts it in the map and locks it.
T2 wants the same L1, gets it from the map, and waits for its availability
T1 finishes, releases L1 (T2 does not yet know about it), and removes it from the map
T3 comes in and wants a lock for user 1, but L1 is gone from the map, so it creates L2 and acquires it.
T2 sees that L1 is free, acquires it and works
At this point, both T2 and T3 have concurrent access to user 1, which is bad
T2 finished first, goes to the map instance and frees the lock for user 1 which is L2, a lock it never acquired in the first place. IllegalMonitorStateException.

There is no easy way out of this one. You have to make sure that concurrent threads wanting to access a user have a consistant lock instance (here the problem is that T1 releases a lock while T2 has a hold on it, but has not locked it yet). This could not happen with your original code - because of the map's mutex, but that mutex created deadlocks.

So what to do ? You could never remove keys from the map.

public void unlock(String user) {
    LOCK_MAP.computeIfPresent(user, (s, lock) -> {
        lock.unlock();
        return lock;
});

But then nobody ever releases keys from the map, which grows indefinitely - one could add a thread-safe counter to check that locks are not "being acquired" before releasing them. Will that create in turn another bug ?

So that being said, there are still a few things to strengthen here :

Lock release should be performed in finally blocks
The number of lock instances you create is unbounded. You might want to avoid that (this is the real difficult part)
Having a mutex at the map's level is kind of a waste. A ConcurrentHashMap would provide much finer grained lock mechanism
Who knows what bug is left here.

Conclusion

Try and see if any solution provided in this other question helps you achieve your goal. It might be safer to use a respected library's implementation.

Concurrent programming is hard. Others have done it for you.