標題: Bounded-Bypass Mutual Exclusion with Minimum Number of Registers
作者: Chen, Sheng-Hsiung
Huang, Ting-Lu
資訊工程學系
Department of Computer Science
關鍵字: Mutual exclusion;shared memory systems;space complexity;fetch&store;swap;bounded bypassing;FIFO
公開日期: 1-十二月-2009
摘要: 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
http://hdl.handle.net/11536/6397
ISSN: 1045-9219
DOI: 10.1109/TPDS.2009.28
期刊: IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS
Volume: 20
Issue: 12
起始頁: 1726
結束頁: 1737
顯示於類別:期刊論文


文件中的檔案:

  1. 000271464900003.pdf