Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10331294 | Information Processing Letters | 2005 | 5 Pages |
Abstract
Peterson's algorithm [G.L. Peterson, Myths about the mutual exclusion problem, Inform. Process. Lett. 12 (3) (1981) 115-116] for mutual exclusion has been widely studied for its elegance and simplicity. In Peterson's algorithm, each process has to cross nâ1 stages to access the shared resource irrespective of the contention for the shared resource at that time, and allows unbounded bypasses. In [K. Block, T.-K. Woo, A more efficient generalization of Peterson's mutual exclusion algorithm, Inform. Process. Lett. 35 (1990) 219-222], Block and Woo proposed a modified algorithm that transforms the number stages to be crossed from fixed nâ1 to t, where 1⩽t⩽n, and bounds the number of possible bypasses by n(nâ1)/2. This paper proposes a simple modification that reduces the bound on the number of possible bypasses to optimal nâ1.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
K. Alagarsamy,