On the Consistency Conditions of Transactional Memories

Abstract : The aim of a Software Transactional Memory (STM) is to discharge the programmers from the management of synchronization in multiprocess programs that access concurrent objects. To that end, a STM system provides the programmer with the concept of a transaction: each sequential process is decomposed into transactions, where a transaction encapsulates a piece of sequential code accessing concurrent objects. A transaction contains no explicit synchronization statement and appears as if it has been executed atomically. Due to the underlying concurrency management, a transaction commits or aborts. Up to now, few papers focused on the definition of consistency conditions suited to STM systems. One of them has recently proposed the opacity consistency condition. Opacity involves all the transactions (i.e., the committed plus the aborted transactions). It requires that (1) until it aborts (if ever it does) a transaction sees a consistent global state of the concurrent objects, and (2) the execution is linearizable (i.e., it could have been produced by a sequential execution -of the same transactions- that respects the real time order on the non-concurrent transactions). This paper is on consistency conditions for transactional memories. It first presents a framework that allows defining a space of consistency conditions whose extreme endpoints are serializability and opacity. It then extracts from this framework a new consistency condition that we call virtual world consistency. This condition ensures that (1) each transaction (committed or aborted) reads values from a consistent global state, (2) the consistent global states read by committed transactions are mutually consistent, but (3) the consistent global states read by aborted transactions are not required to be mutually consistent. Interestingly enough, this consistency condition can benefit lots of STM applications as, from its local point of view, a transaction cannot differentiate it from opacity. Finally, the paper presents and proves correct a STM algorithm that implements the virtual world consistency condition. Interestingly, this algorithm distinguishes the serialization date of a transaction from its commit date (thereby allowing more transactions to commit).
Type de document :
Rapport
[Research Report] PI 1917, 2008, pp.23
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00350131
Contributeur : Anne Jaigu <>
Soumis le : mardi 6 janvier 2009 - 09:08:15
Dernière modification le : mercredi 11 avril 2018 - 01:57:23
Document(s) archivé(s) le : mardi 8 juin 2010 - 18:35:47

Fichiers

PI-1917.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00350131, version 1

Citation

Damien Imbs, José Ramón González De Mendivil Moreno, Michel Raynal. On the Consistency Conditions of Transactional Memories. [Research Report] PI 1917, 2008, pp.23. 〈inria-00350131〉

Partager

Métriques

Consultations de la notice

952

Téléchargements de fichiers

170