Synchronize Java methods by the arguments

Question

Assume that we have a method doSomething(String input) and we want to run it synchronized by different inputs.

It means that running doSomething(A) should block any consecutive calls of doSomething(A) until the first one is completed BUT should not block doSomething(B) or doSomething(C).

So i've created a wrapper method to achieve this goal. It creates objects based on input value and places locks on them and keeps a reference to them in a list.

private static final ArrayList<String> runningTasks  = new ArrayList<>();


public void doSomethingSyncedByInput(String input) {

    // Create a lock or load an already created lock from the list.
    // (Yeah, it's a race condition but forget about it. It's just an example.)
    String lock = new String(input);
    if(runningTasks.contains(input)){
        // get currently available lock object
        lock = runningTasks.get(runningTasks.indexOf(input));
    }else {
        // add a reference on tasks list
        runningTasks.add(lock);
    }

    synchronized (lock) {
        doSomething(input);
    }
}

It actually works; but it's not a totally thread-safe solution as ArrayList is not thread-safe. The contents of ArrayList is not volatile and according to documentation, adding and removing items on the list is not reflected on other threads instantly.

Note that this implementation is not synchronized. If multiple threads access an ArrayList instance concurrently, and at least one of the threads modifies the list structurally, it must be synchronized externally.

A well known thread safe variant of ArrayList is CopyOnWriteArrayList (which makes a copy of the elements and re-sets the inner volatile field holding elements to be sure to have latest version of the list on all other threads instantly). As the name yields, it COPIES each one of the list items on adding a new item to the list and it means the references to the actual objects that got the lock on, would be lost and the code will be broken.

So I need a datatype which holds a list of objects and doesn't copy or change objects in favor of concurrency support. I could use String.intern() functionality but it brings a lot of potential problems especially on mobile platforms.

Any ideas?

Or, do you know any bulletproof implementations available to use?

I'm on Android platform by the way.

UPDATE:

I've reached a solution by myself. Check out my own answer. Comments are welcomed.

Answer 1

You don't need a data type. You need a semaphore dedicated to the locking code. Take a semaphore before you check contains. Figure out if you're in the list. Add yourself to the list if needed. Release it after. You now have a synchronous way of obtaining any lock.

(This is also basically what any synchronized type will do- except by doing the semaphore yourself you can synchronize multiple operations at a time, such as checking contains then adding to the list. Its a frequent bug to use a synchronized data type, expect it will fix your problems, only to find that you needed to synchronize at a higher level around multiple functions).

Of course your code has other weaknesses. You're never removing old keys from the list as they finish, so you could have unbounded size there. Also contains on a list is an N operation, a hashmap is better if you care more about speed than memory.

Answer 2

Unless I misunderstand your question, this is a trivial thing to do:

<T, R> R doSomethingSynchronizedByInput(T input, Function<T, R> fn) {
    synchronized(input) { return fn.apply(input); }
}

Amended to note lack of specificity in question and to add two solutions:

To do the same thing, on the class/type of the input, you need only slightly modify the code above:

<T, R> R doSomethingSynchronizedByInput(T input, Function<T, R> fn) {
    synchronized(input.getClass()) { return fn.apply(input); }
}

Finally, doing something similar for values that are .equals (this is, apparently, what you mean by "value") is slightly more complex. Something along these lines should work:

// Note: I have not tested this: it is just a sketch.
// It requires that type T have an "equals" method that divides
// it into "values"
// Don't try to use a Comparator, because the HashMap doesn't.
public class DoSomethingSynchedByInput<T, R> {
    public interface Listener<V> { void accept(V val); }

    private final Map<T, LinkedList<T>> waiting = new HashMap<>();

    void doSomething(final T input, Function<T, R> fn, Listener<R> listener)
        throws InterruptedException {
        synchronized (waiting) {
            LinkedList<T> waitList = waiting.get(input);
            if (waitList == null) { waitList = new LinkedList<>(); }
            waitList.addLast(input);
            waiting.put(input, waitList);
            while (true) {
                if (waitList.peekFirst() == input) { break; }
                waiting.wait();
            }
        }
        try { listener.accept(fn.apply(input)); }
        finally {
            synchronized (waiting) {
                LinkedList<T> waitList = waiting.get(input);
                waitList.getFirst();
                if (waitList.size() > 0) { waiting.notifyAll(); }
                else { waiting.remove(input); } 
            }
        }
    }
}

Note that there are all kinds of issues, here, that you are not specifying. Several people have brought up the issue that it may be dangerous to lock on a public object (because someone else might). That might be problem, or it might be a design goal. Of much more concern, to me, is that this solution is blocking threads instead of queuing tasks. A blocked thread is a pretty expensive way to represent queued work.

My suggestion is that you take the solutions above and rethink your problem. But, hey, that's not what you asked.

Answer 3

NOTE: For the solution, skip to the UPDATE part below.

As i dived deeper in CopyOnWriteArrayList class, i noticed that CopyOnWriteArrayList.add() uses Arrays.copyOf() which makes a shallow copy of the elements list. It means that it only copies the array itself, not the elements inside. They're just passed on to the new array. So, the lock objects stay intact and we can be sure that the object retrieved via

runningTasks.get(runningTasks.indexOf(input))

is exactly the same object we added on runningTasks and locked on, and the list is on it's latest version on all threads immediately after editing anhy of list items.

I ran the experiment with structural changes to the list, just to be sure:

CopyOnWriteArrayList<String> l = new CopyOnWriteArrayList<>();
String s1 = new String("foo");
String s2 = new String("bar"); 
String s3 = new String("bar"); // Different object, same value

l.add(s1);
Log.e("TEST", "Result: "+String.valueOf( s1 == l.get(0) ));

l.add(s2);
Log.e("TEST", "Result: "+String.valueOf( s1 == l.get(0) ));
Log.e("TEST", "Result: "+String.valueOf( s2 == l.get(1) ));

l.add(s3);
Log.e("TEST", "Result: "+String.valueOf( s1 == l.get(0) ));
Log.e("TEST", "Result: "+String.valueOf( s2 == l.get(1) ));
Log.e("TEST", "Result: "+String.valueOf( s3 == l.get(2) ));

l.remove(1); // the s2
Log.e("TEST", "Result: "+String.valueOf( s1 == l.get(0) ));
Log.e("TEST", "Result: "+String.valueOf( s2 == l.get(1) )); // should be false
Log.e("TEST", "Result: "+String.valueOf( s3 == l.get(1) )); // should be true 

And the results were:

E/TEST: Result: true
E/TEST: Result: true
E/TEST: Result: true
E/TEST: Result: true
E/TEST: Result: true
E/TEST: Result: true
E/TEST: Result: true
E/TEST: Result: false
E/TEST: Result: true

So the references to original objects would be kept. Thus the code can be modified to use CopyOnWriteArrayList. The final version would be:

private static final CopyOnWriteArrayList<String> runningTasks  = new CopyOnWriteArrayList<>();


public void doSomethingSyncedByInput(String input) {

    String lock;
    int index;

    synchronized (runningTasks) {
        index = runningTasks.indexOf(input);
        if (index >= 0) {
            // get currently available lock object
            lock = runningTasks.get(index);
        } else {
            // add a reference on tasks list
            lock = new String(input);
            runningTasks.add(lock);
        }
    }

    synchronized (lock) {
        if(!runningTasks.contains(lock)){
            runningTasks.add(lock);
        }

        doSomething(input);

        index = runningTasks.indexOf(lock);
        if(index >= 0)
            runningTasks.remove(index);
    }
}

It's not perfect though.

Feedbacks are welcomed.

UPDATE

I managed to implement a better one. This one is completely thread-safe, prevents race conditions and cleans up memory after usage.

public class ParameterSynchronizer <T> {

    private final CopyOnWriteArrayList<T> objects;
    private final ConcurrentHashMap<T, Integer> lockCounter;

    public ParameterSynchronizer(){
        objects = new CopyOnWriteArrayList<>();
        lockCounter = new ConcurrentHashMap<>();
    }

    public T getLockObject(T input){
        synchronized (objects) {
            T lock = input;
            int index = objects.indexOf(lock);
            if (index >= 0) {
                lock = objects.get(index);
                lockCounter.put(lock, lockCounter.get(lock)+1);
            } else {
                objects.add(lock);
                lockCounter.put(lock, 1);
            }
            return lock;
        }
    }

    public void cleanUpLockObject(T input){
        synchronized (objects) {
            T lock = input;
            int counter = lockCounter.get(lock);
            if(counter == 1) {
                objects.remove(objects.indexOf(lock));
                lockCounter.remove(lock);
            }else{
                lockCounter.put(lock, counter - 1);
            }
        }
    }

}

Usage:

You should create a final static field having an instance of this class. Use getLockObject() to get the object needed for synchronized block. In end of the synchronized block (last line, in finally, before return, etc.), run cleanUpLockObject() to clear memory. Both methods should be called just once per execution per thread, as calling them changes the thread counter.

It keeps a track of how many threads are locking on this object, and clears the object if no other threads are locking on it.

private static ParameterSynchronizer<String> ps = new ParameterSynchronizer<>();

public void doSomethingSyncedByInput(String input){
    String lockObject = ps.getLockObject(input);
    synchronized (lockObject) {
        doSomething(input);
        ps.cleanUpLockObject(lockObject);
    }
}

And just in case, if doSomething() throws, it could be catched like

private static ParameterSynchronizer<String> ps = new ParameterSynchronizer<>();

public void doSomethingSyncedByInput(String input) throws Exception {
    String lockObject = ps.getLockObject(input);
    synchronized (lockObject) {
        try {
            doSomething(input);
        } catch(Exception e) {
            throw e;
        } finally {
            ps.cleanUpLockObject(lockObject);
        }
    }
}