Time complexity bounds for shared-memory mutual exclusion.

摘要

Mutual exclusion algorithms are used to resolve conflicting accesses to shared resources by concurrent processes. The problem of designing such an algorithm is widely regarded as one of the "classic" problems in concurrent programming.; Recent work on scalable shared-memory mutual exclusion algorithms has shown that the most crucial factor in determining an algorithm's performance is the amount of traffic it generates on the processors-to-memory interconnect [23, 38, 61, 84]. In light of this, the RMR (remote-memory-reference) time complexity measure was proposed [84). Under this measure, an algorithm's time complexity is defined to be the worst-case number of remote memory references required by one process in order to enter and then exit its critical section.; In the study of shared-memory mutual exclusion algorithms, the following fundamental question arises: for a given system model, what is the most efficient mutual exclusion algorithm that can be designed under the RMR measure? This question is important because its answer enables us to compare the cost of synchronization in different systems with greater accuracy. With some primitives, constant-time algorithms are known, so the answer to this question is trivial. However, with other primitives (e.g. , under read/write atomicity), there are still gaps between the best known algorithms and lower bounds.; In this dissertation, we address this question. The main thesis to be supported by this dissertation can be summarized as follows. The mutual exclusion problem exhibits different time-complexity bounds as a function of both the number of processes (N) and the number of simultaneously active processes (contention, k), depending on the available synchronization primitives and the underlying system model. Moreover, these time-complexity bounds are nontrivial, in that constant-time algorithms are impossible in many cases .; In support of this thesis, we present a time-complexity lower bound of O(log N/log log N) for systems using atomic reads, writes, and comparison primitives, such as compare-and-swap. This bound is within a factor of theta(log log N) of being optimal. Given that constant-time algorithms based on fetch-and-&phis; primitives exist, this lower bound points to an unexpected weakness of compare-and-swap, which is widely regarded as being the most useful of all primitives to provide in hardware.; We also present an adaptive algorithm with theta(min(k, log N)) RMR time complexity under read/write atomicity, where k is contention. In addition, we present another lower bound that precludes the possibility of an o(k) algorithm for such systems, even if comparison primitives are allowed.; Regarding nonatomic systems, we present a theta(log N) nonatomic algorithm, and show that adaptive mutual exclusion is impossible in such systems by proving that any nonatomic algorithm must have a single-process execution that accesses O(log N/log log N) distinct variables.; Finally, we present a generic fetch-and-&phis;-based local-spin mutual exclusion algorithm with theta(logr N) RMR time complexity. This algorithm is "generic" in the sense that it can be implemented using any fetch-and-&phis; primitive of rank r, where 2 ≤ r N. The rank of a fetch-and-&phis; primitive expresses the extent to which processes may "order themselves" using that primitive. For primitives that meet a certain additional condition, we present a O(log N/log log N) algorithm, which is time-optimal for certain primitives of constant rank.