Title: Bounded-Bypass Mutual Exclusion with Minimum Number of Registers
Authors: Chen, Sheng-Hsiung
Huang, Ting-Lu
Department of Computer Science
Keywords: Mutual exclusion;shared memory systems;space complexity;fetch&store;swap;bounded bypassing;FIFO
Issue Date: 1-Dec-2009
Abstract: A mutual exclusion mechanism that is both fair and space efficient can be highly valuable for shared memory systems under time and memory constraints such as embedded real-time systems. Several algorithms that utilize only one shared variable and guarantee a certain level of fairness have been proposed. However, these use hypothetical read-modify-write operations that have never been implemented in any system. This paper presents two fair algorithms that do not use such operations, each of which uses a single additional shared variable. The proposed algorithms employ commonly available operations, fetch&store and read/write, on two shared variables. The first algorithm satisfies the bounded-bypass condition. The second is an improvement on the first that satisfies the FIFO condition, which is the most stringent fairness condition. Additionally, it is shown that achieving the bounded-bypass condition using the same set of operations requires two shared variables. Both of the algorithms are thus optimal with respect to the number of shared variables.
URI: http://dx.doi.org/10.1109/TPDS.2009.28
ISSN: 1045-9219
DOI: 10.1109/TPDS.2009.28
Volume: 20
Issue: 12
Begin Page: 1726
End Page: 1737
Appears in Collections:Articles

Files in This Item:

  1. 000271464900003.pdf