Skip to Main content Skip to Navigation
Journal articles

Iterative Computations with Ordered Read-Write Locks

Pierre-Nicolas Clauss 1 Jens Gustedt 1, *
* Corresponding author
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.
Complete list of metadatas

Cited literature [14 references]  Display  Hide  Download

https://hal.inria.fr/inria-00330024
Contributor : Jens Gustedt <>
Submitted on : Monday, October 13, 2008 - 10:08:53 PM
Last modification on : Monday, May 4, 2020 - 11:39:10 AM
Document(s) archivé(s) le : Tuesday, October 9, 2012 - 12:05:08 PM

File

RR-6685.pdf
Files produced by the author(s)

Identifiers

Collections

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⟩

Share

Metrics

Record views

773

Files downloads

393