Paper-> Exposing Non-Atomic Methods of Concurrent Objects

classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view

Paper-> Exposing Non-Atomic Methods of Concurrent Objects

Kimo Crossman

Exposing Non-Atomic Methods of Concurrent Objects

(Submitted on 28 Jun 2017)
In particular, we identify 10 classes in the
java.util.concurrent package which implement queues, deques, sets, and key-value maps. For each class we
select a small set of core methods which are believed to behave atomically. These core methods represent the
most basic operations, e.g., a key-value map’s put, get, remove, and containsKey methods. 

Multithreaded software is typically built with specialized concurrent objects like atomic integers, queues, and maps. These objects' methods are designed to behave according to certain consistency criteria like atomicity, despite being optimized to avoid blocking and exploit parallelism, e.g., by using atomic machine instructions like compare and exchange (cmpxchg). Exposing atomicity violations is important since they generally lead to elusive bugs that are difficult to identify, reproduce, and ultimately repair. 
In this work we expose atomicity violations in concurrent object implementations from the most widely-used software development kit: The Java Development Kit (JDK). We witness atomicity violations via simple test harnesses containing few concurrent method invocations. While stress testing is effective at exposing violations given catalytic test harnesses and lightweight means of falsifying atomicity, divining effectual catalysts can be difficult, and atomicity checks are generally cumbersome. We overcome these problems by automating test-harness search, and establishing atomicity via membership in precomputed sets of acceptable return-value outcomes. Our approach enables testing millions of executions of each harness each second (per processor core). This scale is important since atomicity violations are observed in very few executions (tens to hundreds out of millions) of very few harnesses (one out of hundreds to thousands). Our implementation is open source and publicly available

Concurrency-interest mailing list
[hidden email]
Reply | Threaded
Open this post in threaded view

Re: Paper-> Exposing Non-Atomic Methods of Concurrent Objects

Doug Lea
On 07/06/2017 09:37 AM, Kimo Crossman wrote:
>   Exposing Non-Atomic Methods of Concurrent Objects
> Michael Emmi,  Constantin Enea

This tool seems useful (running it before release would have
picked up a fixed bug). The other non-atomicities reported
are expected, but show that people either don't read our
package-level documentation, or don't always bear it in mind.
Here's what it currently says. We should probably improve it, and/or
replicate some of it in particular classes. Suggestions welcome.

Pasting from ...

Concurrent Collections
Besides Queues, this package supplies Collection implementations
designed for use in multithreaded contexts: ConcurrentHashMap,
ConcurrentSkipListMap, ConcurrentSkipListSet, CopyOnWriteArrayList, and
CopyOnWriteArraySet. When many threads are expected to access a given
collection, a ConcurrentHashMap is normally preferable to a synchronized
HashMap, and a ConcurrentSkipListMap is normally preferable to a
synchronized TreeMap. A CopyOnWriteArrayList is preferable to a
synchronized ArrayList when the expected number of reads and traversals
greatly outnumber the number of updates to a list.

The "Concurrent" prefix used with some classes in this package is a
shorthand indicating several differences from similar "synchronized"
classes. For example java.util.Hashtable and
Collections.synchronizedMap(new HashMap()) are synchronized. But
ConcurrentHashMap is "concurrent". A concurrent collection is
thread-safe, but not governed by a single exclusion lock. In the
particular case of ConcurrentHashMap, it safely permits any number of
concurrent reads as well as a large number of concurrent writes.
"Synchronized" classes can be useful when you need to prevent all access
to a collection via a single lock, at the expense of poorer scalability.
In other cases in which multiple threads are expected to access a common
collection, "concurrent" versions are normally preferable. And
unsynchronized collections are preferable when either collections are
unshared, or are accessible only when holding other locks.

Most concurrent Collection implementations (including most Queues) also
differ from the usual java.util conventions in that their Iterators and
Spliterators provide weakly consistent rather than fast-fail traversal:

    they may proceed concurrently with other operations
    they will never throw ConcurrentModificationException
    they are guaranteed to traverse elements as they existed upon
construction exactly once, and may (but are not guaranteed to) reflect
any modifications subsequent to construction.
Concurrency-interest mailing list
[hidden email]