inria-00330024, version 1
Iterative Computations with Ordered Read-Write Locks
Pierre-Nicolas Clauss
a, 1Jens Gustedt
b, 1
Journal of Parallel and Distributed Computing 70, 5 (2010) 496-504
Résumé : 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.
- a – Université Henri Poincaré - Nancy I
- b – INRIA
- 1 : ALGORILLE (INRIA Lorraine - LORIA)
- INRIA – CNRS : UMR7503 – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine (INPL)
- Collaboration : Grid'5000
- Domaine : Informatique/Algorithme et structure de données
Informatique/Calcul parallèle, distribué et partagé - Mots-clés : synchronization – iterative algorithms – read-write locks
- Référence interne : RR-6685
- inria-00330024, version 1
- http://hal.inria.fr/inria-00330024
- oai:hal.inria.fr:inria-00330024
- Contributeur : Jens Gustedt
- Soumis le : Lundi 13 Octobre 2008, 22:08:53
- Dernière modification le : Lundi 23 Avril 2012, 16:35:44






Documents associés
Exporter