Fast Mutual Exclusion, Even with Contention
Fast Mutual Exclusion, Even with Contention
复制标题
即使存在争用，也能快速互斥
DOI：
--
复制
发表时间：
1993
期刊：
影响因子：
--
通讯作者：
M. Scott
中科院分区：
文献类型：
--
作者：
Maged M. Michael;M. Scott
我们提出了一种互斥算法，在除了读和写之外没有原子指令的机器上，在有争用和无争用的情况下都能很好地执行。该算法利用了存储系统以全字和半字两种粒度进行读写的能力。它依赖于可预测的处理器执行速度，但对临界区的长度没有限制，在冲突请求之间进行仲裁时仅执行O(N)个对共享内存的引用(而不是在Lamport的快速互斥算法的通用版本中为O(n^2))，并且在没有争用的情况下仅执行2次读取和4次写入(新的下限)。我们提供了一个正确的证明。.pp我们还研究了指数退避在快速互斥中的效用，并在Silicon Graphics Iris多处理器和更大的模拟机器上进行了实验。有了Backoff，我们发现Lamport的算法、我们的新算法以及由于Alur和Taubenfeld而产生的最近的算法都工作得非常好，即使在激烈的争用中也超过了Silicon Graphics机器的本地硬件锁。
We present a mutual exclusion algorithm that performs well both with and without contention, on machines with no atomic instructions other than read and write. The algorithm capitalizes on the ability of memory systems to read and write at both full- and half-word granularities. It depends on predictable processor execution rates, but requires no bound on the length of critical sections, performs only O(n) total references to shared memory when arbitrating among conflicting requests (rather than O(n^2) in the general version of Lamport's fast mutual exclusion algorithm), and performs only 2 reads and 4 writes (a new lower bound) in the absence of contention. We provide a correctness proof. .pp We also investigate the utility of exponential backoff in fast mutual exclusion, with experimental results on the Silicon Graphics Iris multiprocessor and on a larger, simulated machine. With backoff in place, we find that Lamport's algorithm, our new algorithm, and a recent algorithm due to Alur and Taubenfeld all work extremely well, outperforming the native hardware locks of the Silicon Graphics machine, even with heavy contention.