[concurrency-interest] Design of Thread Safe Iterator Proxy

Yuval Shavit yankee.sierra at gmail.com
Sun Jun 16 17:51:23 EDT 2013


Hi Piyush,

This is a bit of a lengthy reply, apologies for that. The short of it is
that (a) this iterator still isn't thread-safe and (b) it's not needed to
fix a ConcurrentModificationException.

Firstly, note that the ConcurrentModificationException doesn't necessarily
have to do with concurrency. You can easily trigger it with a single
thread, as it just means that the collection was modified between an
iterator being created and next() being invoked on it. For instance, this
will trigger a CME:

    List<Integer> list = new ArrayList<Integer>();
    list.add(1);
    for (Integer i : list) {
        list.add(2); // modify the list, and then the implicit Iterator
will invoke next() for the next iteration
    }

    Exception in thread "main" java.util.ConcurrentModificationException
at java.util.AbstractList$Itr.checkForComodification(AbstractList.java:372)
 at java.util.AbstractList$Itr.next(AbstractList.java:343)
at Cme.main(Cme.java:6)

That said, in your SafeIterator.hasNext() method, you only unlock the
ReentrantLock when the delegate iterator throws an exception. You probably
meant to put the unlock within a finally block, not a catch block. This bug
means that invoking hasNext() will never unlock the lock if there's no
exception thrown (which there usually isn't), which is what's causing
things to stick.

This error illustrates the importance of using the simplest mechanism that
works. In this case, I would make the lock object just a new Object() --
not a ReentrantLock -- and use synchronized blocks with it. That takes care
of the lock-try-finally-unlock pattern for you, eliminating the possibility
of this error.

  final Object lock = new Object();
 public boolean hasNext() { synchronized (lock) { return
iterator.hasNext(); } }
  ...

It's important to note that this iterator will still not be thread-safe if
the delegate iterator isn't thread-safe, which usually means that the
collection that originally created the iterator is itself thread-safe. One
obvious way to break the thread safety is to (a) create an ArrayList (which
is not thread-safe), (b) create an iterator from it (which is also not
thread safe), call this iterator-u (c) create a SafeIterator from
iterator-1, call it iterator-s, (d) publish iterator-s to some thread, then
(e) modify iterator-u (by calling next, remove() or possibly even hasNext()
on it) *or* modify the original ArrayList somehow. Those actions won't be
synchronized on the SafeIterator's "lock" object, breaking thread safety.

In fact, because the Iterator interface inherently uses a check-then-act
pattern (first you check if there's a next element using hasNext(), then
you get that element using next()), it's pretty tricky to create a
thread-safe Iterator. For instance, if an iterator has one element left in
it, you could have two threads invoke hasNext() on it and see that there's
a next element; then both invoke next() on it, and the second one of those
will trigger a NoSuchElementException because the first one had already
"taken" the last element. That's just a classic race condition, nothing
tricky as far as data races or such. It's best to just have each Iterator
be thread-local. If you need something like a thread-safe queue that
various threads can take from, try one of the interfaces/classes
in java.util.concurrent, such as BlockingQueue.

-Yuval


On Mon, Jun 10, 2013 at 2:37 AM, piyush katariya <corporate.piyush at gmail.com
> wrote:

> Hi,
>
>        so i was in the need of ThreadSafe iterator, so that multiple
> threads can access over it concurrently without  throwing
> "ConcurrentModificationException".
>
> i came with solution attached herewith, but for some reason..multiple
> threads from thread pool after iterating over, stucks...
>
> can somebody help me with it..
>
>
> Regards,
> Piyush Katariya
>
> _______________________________________________
> Concurrency-interest mailing list
> Concurrency-interest at cs.oswego.edu
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20130616/98ae3c6c/attachment.html>


More information about the Concurrency-interest mailing list