A mutual exclusion algorithm with optimally bounded bypasses |
| |
Authors: | K. Alagarsamy |
| |
Affiliation: | Department of Computer Science, University of Northern British Columbia, Prince George, BC, Canada V2N 4Z9 |
| |
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. |
| |
Keywords: | Mutual exclusion Critical section Read/write atomicity Bypasses Synchronization Concurrency |
本文献已被 ScienceDirect 等数据库收录! |
|