Adaptive mutual exclusion with local spinning |
| |
Authors: | Yong-Jik Kim James H. Anderson |
| |
Affiliation: | (1) Tmax Soft Research Center, 272-6 Seohyeon-dong, Seongnam-si, Gyeonggi-do, 463-824, South Korea;(2) Department of Computer Science, University of North Carolina at Chapel Hill, Chapel Hill, NC 27599-3175, USA |
| |
Abstract: | We present an adaptive algorithm for N-process mutual exclusion under read/write atomicity in which all busy waiting is by local spinning. In our algorithm, each process p performs O(k) remote memory references to enter and exit its critical section, where k is the maximum “point contention” experienced by p. The space complexity of our algorithm is Θ(N), which is clearly optimal. Our algorithm is the first mutual exclusion algorithm under read/write atomicity that is adaptive when time complexity is measured by counting remote memory references.A preliminary version of this paper was presented at the 14th International Symposium on Distributed Computing [6]. |
| |
Keywords: | Adaptive mutual exclusion Local spinning Read/write atomicity Shared-memory systems Time complexity |
本文献已被 SpringerLink 等数据库收录! |
|