Iterative Computations with Ordered Read-Write Locks

Pierre-Nicolas Clauss 1 Jens Gustedt 1, *
* Auteur correspondant
1 ALGORILLE - Algorithms for the Grid
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : We introduce the framework of ordered read-write locks, ORWL, that are characterized by two main features: a strict FIFO policy for access and the attribution of access to lock-handles instead of processes or threads. These two properties allow applications to have a controlled pro-active access to resources and thereby to achieve a high degree of asynchronicity between different tasks of the same application. For the case of iterative computations with many parallel tasks which access their resources in a cyclic pattern we provide a generic technique to implement them by means of ORWL. We show that the possible execution patterns for such a system correspond to a combinatorial lattice structure and that this lattice is finite iff the configuration contains a potential deadlock. In addition, we provide efficient algorithms: one that allows for a deadlock-free initialization of such a system and another one for the detection of deadlocks in an already initialized system.
Type de document :
Article dans une revue
Journal of Parallel and Distributed Computing, Elsevier, 2010, 70 (5), pp.496­-504. 〈10.1016/j.jpdc.2009.09.002〉
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00330024
Contributeur : Jens Gustedt <>
Soumis le : lundi 13 octobre 2008 - 22:08:53
Dernière modification le : dimanche 20 mai 2018 - 20:20:10
Document(s) archivé(s) le : mardi 9 octobre 2012 - 12:05:08

Fichier

RR-6685.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Pierre-Nicolas Clauss, Jens Gustedt. Iterative Computations with Ordered Read-Write Locks. Journal of Parallel and Distributed Computing, Elsevier, 2010, 70 (5), pp.496­-504. 〈10.1016/j.jpdc.2009.09.002〉. 〈inria-00330024〉

Partager

Métriques

Consultations de la notice

707

Téléchargements de fichiers

252