Universal constructions for large objects
James Horton Anderson, Mark Moir · IEEE Transactions on Parallel and Distributed Systems · 1999
We present lock-free and wait-free universal constructions for implementing large shared objects. Most previous universal constructions require processes to copy the entire object state, which is impractical for large objects. Previous attempts to address this problem require programmers to explicitly fragment large objects into smaller, more manageable pieces, paying particular attention to how such pieces are copied. In contrast, our constructions are designed to largely shield programmers from this fragmentation. Furthermore, for many objects, our constructions result in lower copying overhead than previous ones. Fragmentation is achieved in our constructions through the use of load-linked, store-conditional, and validate operations on a "large" multiword shared variable. Before presenting our constructions, we show how these operations can be efficiently implemented from similar one-word primitives.
Cited by 66 works. doi:10.1109/71.819952
Authors
References
- Linearizability: a correctness condition for concurrent objects
- Wait-free synchronization
- Software transactional memory
- A methodology for implementing highly concurrent data objects
- A method for implementing lock-free shared-data structures
- Disjoint-access-parallel implementations of strong shared memory primitives
- Software transactional memory
- Practical implementations of non-blocking synchronization primitives
- Transparent support for wait-free transactions
- Universal constructions for multi-object operations