Concurrent libraries with foresight

Linearizable libraries provide operations that appear to execute
atomically. Clients, however, may need to execute a sequence of operations
(a composite operation) atomically. We consider the problem
of extending a linearizable library to support arbitrary atomic
composite operations by clients. We introduce a novel approach in
which the concurrent library ensures atomicity of composite operations
by exploiting information (foresight) provided by its clients.
We use a correctness condition, based on a notion of dynamic rightmovers,
that guarantees that composite operations execute atomically
without deadlocks, and without using rollbacks.
We present a static analysis to infer the foresight information
required by our approach, allowing a compiler to automatically
insert the foresight information into the client. This relieves the
client programmer of this burden and simplifies writing client code.
We present a generic technique for extending the library implementation
to realize foresight-based synchronization. This technique
is used to implement a general-purpose Java library for Map
data structures — the library permits composite operations to simultaneously
work with multiple instances of Map data structures.
We use the Maps library and the static analysis to enforce atomicity
of a wide selection of real-life Java composite operations. Our
experiments indicate that our approach enables realizing efficient
and scalable synchronization for real-life composite operations.