Is there a way to synchronize using two lock objects in Java?

Question

I'm wondering if there's a way in Java to synchronize using two lock objects. I don't mean locking on either object, I mean locking only on both.

e.g. if I have 4 threads:

• Thread A requests a lock using Object1 and Object2
• Thread B requests a lock using Object1 and Object3
• Thread C requests a lock using Object4 and Object2
• Thread D requests a lock using Object1 and Object2

In the above scenario, Thread A and Thread D would share a lock, but Thread B and Thread C would have their own locks. Even though they overlap with one of the two objects, the same lock only applies if it overlaps on both.

So I have a method called by many threads which is going to perform a specific activity type based on a specific database. I have identifier objects for both the database and the activity, and I can guarantee that the action will be thread safe as long as it is not the same activity based on the same database as another thread.

My ideal code would look something like:

public void doActivity(DatabaseIdentifier dbID, ActivityIdentifier actID) {    
    synchronized( dbID, actID ) { // <--- Not real Java
       // Do an action that can be guaranteed thread-safe per unique
       // combination of dbIT and actID, but needs to share a 
       // lock if they are both the same.
    }
}

I could create a hashmap of lock objects that are keyed by both the DatabaseIdentifier and the ActivityIdentifier, but I'm going to run into the same synchronization issue when I need to create/access those locks in a thread-safe way.

For now I'm just synchronizing on the DatabaseIdentifier. It's much less likely that there will be multiple activities going on at the same time for one DBIdentifier, so I will only rarely be over-locking. (Can't say the same for the opposite direction though.)

Anyone have a good way to handle this that doesn't involve forcing unnecessary threads to wait?

Thanks!

Answer 1

I can't think of a way to do this that really captures your idea of locking a pair of objects. Some low-level concurrency boffin might be able to invent one, but i have my doubts about whether we would have the necessary primitives to implement it in Java.

I think the idea of using the pairs as keys to identify lock objects is a good one. If you want to avoid locking, then arrange the lookup so that it doesn't do any.

I would suggest a two-level map, vaguely like:

Map<DatabaseIdentifier, Map<ActivityIdentifier, Lock>> locks;

Used vaguely thus:

synchronized (locks.get(databaseIdentifier).get(activityIdentifier)) {
    performSpecificActivityOnDatabase();
}

If you know what all the databases and activities are upfront, then just create a perfectly normal map containing all the combinations when your application starts up, and use it exactly as above. The only locking is on the lock objects, and there is no contention.

If you don't know what the databases and activities will be, or there are too many combinations to create a complete map upfront, then you will need to create the map incrementally. This is where Concurrency Fun Times begin.

The straightforward solution is to lazily create the inner maps and the locks, and to protect these actions with normal locks:

Map<ActivityIdentifier, Object> locksForDatabase;
synchronized (locks) {
    locksForDatabase = locks.get(databaseIdentifier);
    if (locksForDatabase == null) {
        locksForDatabase = new HashMap<ActivityIdentifier, Object>();
        locks.put(databaseIdentifier, locksForDatabase);
    }
}
Object lock;
synchronized (locksForDatabase) {
    lock = locksForDatabase.get(locksForDatabase);
    if (lock == null) {
        lock = new Object();
        locksForDatabase.put(locksForDatabase, lock);
    }
}
synchronized (lock) {
    performSpecificActivityOnDatabase();
}

As you are evidently aware, this will lead to too much contention. I mention it only for didactic completeness.

You can improve it by making the outer map concurrent:

ConcurrentMap<DatabaseIdentifier, Map<ActivityIdentifier, Object>> locks;

And:

Map<ActivityIdentifier, Object> newHashMap = new HashMap<ActivityIdentifier, Object>();
Map<ActivityIdentifier, Object> locksForDatabase = locks.putIfAbsent(databaseIdentifier, newHashMap);
if (locksForDatabase == null) locksForDatabase = newHashMap;
Object lock;
synchronized (locksForDatabase) {
    lock = locksForDatabase.get(locksForDatabase);
    if (lock == null) {
        lock = new Object();
        locksForDatabase.put(locksForDatabase, lock);
    }
}
synchronized (lock) {
    performSpecificActivityOnDatabase();
}

Your only lock contention there will be on the per-database maps, for the duration of a put and a get, and according to your report, there won't be much of that. You could convert the inner map to a ConcurrentMap to avoid that, but that sounds like overkill.

There will, however, be a steady stream of HashMap instances being created to be fed to putIfAbsent and then being thrown away. You can avoid that with a sort of postmodern atomic remix of double-checked locking; replace the first three lines with:

Map<ActivityIdentifier, Object> locksForDatabase = locks.get(databaseIdentifier);
if (locksForDatabase == null) {
    Map<ActivityIdentifier, Object> newHashMap = new HashMap<ActivityIdentifier, Object>();
    locksForDatabase = locks.putIfAbsent(databaseIdentifier, newHashMap);
    if (locksForDatabase == null) locksForDatabase = newHashMap;
}

In the common case that the per-database map already exists, this will do a single concurrent get. In the uncommon case that it does not, it will do an additional but necessary new HashMap() and putIfAbsent. In the very rare case that it does not, but another thread has also discovered that, one of the threads will be doing a redundant new HashMap() and putIfAbsent. That should not be expensive.

Actually, it occurs to me that this is all a terrible idea, and that you should just stick the two identifiers together to make one double-size key, and use that to make lookups in a single ConcurrentHashMap. Sadly, i am too lazy and vain to delete the above. Consider this advice a special prize for reading this far.

PS It always mildly annoys me to see an instance of Object used as nothing but a lock. I propose calling them LockGuffins.

Answer 2

have each DatabaseIdentifier keep a set of locks keyed to ActivityIdentifiers that it owns

so you can call

public void doActivity(DatabaseIdentifier dbID, ActivityIdentifier actID) {    
    synchronized( dbID.getLock(actID) ) { 
       // Do an action that can be guaranteed thread-safe per unique
       // combination of dbIT and actID, but needs to share a 
       // lock if they are both the same.
    }
}

then you only need a (short) lock on the underlying collection (use a ConcurrentHashMap) in dbID

in other words

ConcurrentHashMap<ActivityIdentifier ,Object> locks = new...
public Object getLock(ActivityIdentifier actID){
    Object res = locks.get(actID); //avoid unnecessary allocations of Object

    if(res==null) {
        Object newLock = new Object();
        res = locks.puIfAbsent(actID,newLock );
        return res!=null?res:newLock;
    } else return res;
}

this is better than locking the full action on dbID (especially when its a long action) but still worse than your ideal scenario

update in responce to comments about EnumMap

private final EnumMap<ActivityIdentifier ,Object> locks;

/**
  initializer ensuring all values are initialized 
*/
{
    EnumMap<ActivityIdentifier ,Object> tmp = new EnumMap<ActivityIdentifier ,Object>(ActivityIdentifier.class)
    for(ActivityIdentifier e;ActivityIdentifier.values()){
        tmp.put(e,new Object());
    }
    locks = Collections.unmodifiableMap(tmp);//read-only view ensures no modifications will happen after it is initialized making this thread-safe
}


public Object getLock(ActivityIdentifier actID){
    return locks.get(actID);
}

Answer 3

Your hashmap suggestion is what I've done in the past. The only change I'd make is using a ConcurrentHashMap, to minimize the synchronization.

The other issue is how to cleanup the map if the possible keys are going to change.

Answer 4

I think you should go the way of the hashmap, but encapsulate that in a flyweight factory. Ie, you call:

FlyweightAllObjectsLock lockObj = FlyweightAllObjectsLock.newInstance(dbID, actID);

Then lock on that object. The flyweight factory can get a read lock on the map to see if the key is in there, and only do a write lock if it is not. It should reduce the concurrency factor.

You might also want to look into using weak references on that map as well, to avoid keeping memory from garbage collection.