[concurrency-interest] Problem with using an unbounded map of Mutex lock objects

Tim Peierls tim at peierls.net
Sat Jun 3 12:32:14 EDT 2006


On 6/3/06, Tim Peierls <tim at peierls.net> wrote:
>
> I was expecting Joe Bowbeer to have chimed in by now, but I'll have to do
> it for him. :-)
>

Joe pointed out (offline) some weaknesses in my posted code. Here is an
improved version that adds a remove method: waiting gets return null if the
key they are waiting for is removed. Benign races are possible, e.g.,
simultaneous puts from different threads, simultaneous put and remove.

The two part message is "Design with the standard library interfaces; use
the standard library implementations where conveniently possible". Future
makes the waiting and interrupt handling logic easy and consistent.
ConcurrentMap provides a thread-safe map with atomic put-if-absent and
remove-only-given-value. FutureTask and ConcurrentHashMap are performant and
well-tested implementations.

I believe the approach will scale very well. For ehcache, you have
serialization concerns that are not addressed in the code below, but this
should be independent of the blocking get issue.

public class BlockingCache<K, V> {

    public V get(K key) throws InterruptedException {
        try {
            return futureFor(key).get();
        } catch (CancellationException e) {
            return null;
        } catch (ExecutionException e) {
            throw new IllegalStateException(e.getCause()); // shouldn't
happen
        }
    }

    public V get(K key, long timeout, TimeUnit unit) throws
InterruptedException {
        try {
            return futureFor(key).get(timeout, unit);
        } catch (TimeoutException e) {
            return null;
        } catch (CancellationException e) {
            return null;
        } catch (ExecutionException e) {
            throw new IllegalStateException(e.getCause()); // shouldn't
happen
        }
    }

    public void put(K key, V value) {
        while (true) {
            FutureResult<V> f = futureFor(key);
            if (!f.isDone() || !cache.remove(key, f)) {
                f.set(value); // first set succeeds, subsequent calls
ignored
                break;
            }
        }
    }

    public void remove(K key) {
        if (cache.containsKey(key)) { // try to avoid creating future
unnecessarily
            FutureResult<V> f = futureFor(key);
            f.cancel(false);
            cache.remove(key, f);
        }
    }


    private FutureResult<V> futureFor(K key) {
        FutureResult<V> f = cache.get(key);
        if (f == null) {
            FutureResult<V> newf = new FutureResult<V>();
            f = cache.putIfAbsent(key, newf);
            if (f == null) return newf;
        }
        return f;
    }

    private final ConcurrentMap<K, FutureResult<V>> cache =
        new ConcurrentHashMap<K, FutureResult<V>>();


    private static class FutureResult<V> extends FutureTask<V> {
        FutureResult() { super(UNUSED, null); }
        public void set(V value) { super.set(value); }
    }

    private static final Runnable UNUSED = new Runnable() { public void
run() {} };
}


--tim
-------------- next part --------------
An HTML attachment was scrubbed...
URL: /pipermail/attachments/20060603/de3be3c4/attachment.html 


More information about the Concurrency-interest mailing list