Java: lock functions which work on the same element

Question

There are many threads which work on elements on the same map, each with a code, for example:

THREAD_1 works on an element with code "1234"
THREAD_2 works on an element with code "1234"
THREAD_3 works on an element with code "9876"
etc...

Elements are not permanent, i.e. THREAD_1 might remove the element "1234" and then insert it again. What I want is that, while THREAD_1 is working on the element "1234" (also removing it) THREAD_2 must wait.

Is there a way for doing it?

A possible solution might be to insert a fake element in a HashMap and then enforce the synchronization with a "synchronized" clause on that element. What do you think about? (Obviously that fake element would remain in the map also if a thread removed the element with the associated code)...

Answer 1

Given your particular problem, none of the java standard object can solve all your problems. Here's a solution that I believe is correct and does not keep any unnecessary keys or values in your lock map:

// we don't use a ConcurrentHashMap, because we have some other operations 
// that need to be performed in atomically with map.put and map.remove.
// ConcurrentHashMap would of course also work, but it doesn't remove the 
// need for external synchronization in in our case.
Map<String, CountingLock> locksMap = new HashMap<String, CountingLock>();
...

HttpResponse myFunction(String key) {

    CountingLock lock;
    synchronized(locksMap){
        lock = locksMap.get(key);
        if(lock == null){
            lock = new CountingLock();
            locksMap.put(key, lock);
        }
        lock.prepare(); // has to be done while holding the lock of locksMap.
                        // basically tells other threads that the current 
                        // thread intends to acquire the lock soon. This way,
                        // the other threads know not to remove this lock 
                        // from locksMap as long as another one has indicated
                        // that he is going to need it soon.
    }

    lock.lock(); // has to be done while NOT holding the lock of locksMap,
                 // or we risk deadlock situations.

    try {
        // ...
        // work
        // ...
    } finally {
        synchronized(locksMap) {
            if(lock.unlock() == 0){
                // no other thread is intending to use this lock any more. 
                // It is safe to remove it from the map. The next thread 
                // will just have to recreate a new lock for the same key.
                locksMap.remove(key);
            }
        }
    }

    return SOMETHING;    
}

private static class CountingLock {
    // The number of threads that are trying to access the protected Key
    private AtomicInteger interestedThreads = new AtomicInteger(0);

    private Lock lock = new ReentrantLock();

    public void prepare(){
        interestedThreads.incrementAndGet();
    }

    public void lock(){
        lock.lock();
    }

    public int unlock(){
        lock.unlock();
        return interestedThreads.decrementAndGet();              
    }
}

This code should work as expected in all cases. That was a fun problem to solve :-)

Answer 2

We use a thing we call a LockMap.

A LockMap is essentially:

Map<Object, ReadWriteLock>

We have a synchronized method to fetch the lock for a specific Object.

Since Maps rely on equivalence, rather than identity, two objects that are equal() give you the same lock.

So:

lock1 = map.get(new Thing(1));
lock2 = map.get(new Thing(1));

lock1 == lock2 = true

Which is handy.

Once you get the lock, you can lock it as you wish to control access to the Object.

The other thing we do is use a LRU map (using a LinkedHashMap -- see this), so that old object keys can fall off the end when they're unused.

Answer 3

You should use ConcurrentHashMap

A hash table supporting full concurrency of retrievals and adjustable expected concurrency for updates.

Retrieval operations (including get) generally do not block, so may overlap with update operations (including put and remove).

The allowed concurrency among update operations is guided by the optional concurrencyLevel constructor argument (default 16), which is used as a hint for internal sizing. The table is internally partitioned to try to permit the indicated number of concurrent updates without contention. Because placement in hash tables is essentially random, the actual concurrency will vary