A Tight Bound on Time Complexity of Mutual Exclusion

摘要: In distributed shared memory multiprocessors, remote accesses generate processor-tomemory trac which may result in a bottleneck. It is therefore important to design algorithms that minimize the number of accesses. We establish lower bound 3 on access time complexity for mutual exclusion model where processes communicate by means general read-modify-write primitive. Since primitive generalization all atomic primitives at most one variable, our holds any set such primitives. Furthermore, this tight because it matches upper Huang’s algorithm proposed 1999.