The Cache Coherent (CC) and the Distributed Shared Memory (DSM) models are standard shared memory models, and the Remote Memory Reference (RMR) complexity is considered to accurately predict the actual performance of mutual exclusion algorithms in shared memory systems. In [12] we prove a tight lower bound for the RMR complexity of deadlock-free randomized mutual exclusion algorithms in both the CC and the DSM model with an adaptive adversary. Our lower bound establishes that an adaptive adversary can schedule n processes in such a way that each enters the critical section once, and the total number of RMRs is Ω(n log n/log log n) in expectation. This matches an upper bound of Hendler and Woelfel .
展开▼
机译：高速缓存相干（CC）和分布式共享存储器（DSM）模型是标准共享存储器模型，并且遥控存储器参考（RMR）复杂性被认为是准确地预测共享存储器系统中的相互排除算法的实际性能。在[12]中，我们证明了在CC和DSM模型中的无锁定随机互排除算法的RMR复杂性，具有自适应对手。我们的下限建立了自适应对手可以以这样的方式安排N个进程，每个方式进入一次关键部分，并且RMRS的总数是ω（n log n / log log n）期望。这与Hendler和Woelfel的上限相匹配。
展开▼
