Skip to Main content Skip to Navigation
Reports

Looking for Efficient Implementations of Concurrent Objects

Achour Mostefaoui 1 Michel Raynal 1 
1 ASAP - As Scalable As Possible: foundations of large scale dynamic distributed systems
Inria Rennes – Bretagne Atlantique , IRISA-D1 - SYSTÈMES LARGE ÉCHELLE
Abstract : As introduced by Taubenfeld, a contention-sensitive implementation of a concurrent object is an implementation such that the overhead introduced by locking is eliminated in the common cases, i.e., when there is no contention or when the operations accessing concurrently the object are non-interfering. This paper, that can be considered as an introductory paper to this topic, presents a methodological construction of a contention-sensitive implementation of a concurrent stack. In a contention-free context a push or pop operation does not rest on a lock mechanism and needs only six accesses to the shared memory. In case of concurrency a single lock is required. Moreover, the implementation is starvation-free (any operation is eventually executed). The paper, that presents the algorithms in an incremental way, visits also a family of liveness conditions and important concurrency-related concepts such as the notion of an abortable object.
Document type :
Reports
Complete list of metadata

Cited literature [26 references]  Display  Hide  Download

https://hal.inria.fr/inria-00576742
Contributor : Ist Rennes Connect in order to contact the contributor
Submitted on : Tuesday, March 15, 2011 - 12:32:05 PM
Last modification on : Thursday, January 20, 2022 - 4:20:17 PM
Long-term archiving on: : Thursday, June 16, 2011 - 2:50:12 AM

File

PI-1969.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00576742, version 1

Citation

Achour Mostefaoui, Michel Raynal. Looking for Efficient Implementations of Concurrent Objects. [Research Report] PI-1969, 2011, pp.10. ⟨inria-00576742⟩

Share

Metrics

Record views

177

Files downloads

176