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.
Type de document :
[Research Report] PI-1969, 2011, pp.10
Liste complète des métadonnées

Littérature citée [26 références]  Voir  Masquer  Télécharger

Contributeur : Ist Rennes <>
Soumis le : mardi 15 mars 2011 - 12:32:05
Dernière modification le : jeudi 15 novembre 2018 - 11:57:36
Document(s) archivé(s) le : jeudi 16 juin 2011 - 02:50:12


Fichiers produits par l'(les) auteur(s)


  • HAL Id : inria-00576742, version 1


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



Consultations de la notice


Téléchargements de fichiers