Coping with Contention (Extended Abstract)
作者： Manhoi Choy , Ambuj K. Singh
DOI: 10.1007/BFB0020426
关键词:
摘要: Contention in multiprocessor systems is considered. A randomized algorithm for mutual exclusion presented that achieves a constant average response time under varying degrees of contention. The use randomization does not affect the safety or progress conditions, only performance algorithm.
springer.com
sci-hub.se 参考文章(20)
James Aspnes, Maurice Herlihy, Fast randomized consensus using shared memory Journal of Algorithms. ,vol. 11, pp. 441- 461 ,(1990) , 10.1016/0196-6774(90)90021-6
Karl Abrahamson, On achieving consensus using a shared memory principles of distributed computing. pp. 291- 302 ,(1988) , 10.1145/62546.62594
Jae-Heon Yang, James H. Anderson, Fast, scalable synchronization with minimal hardware support Proceedings of the twelfth annual ACM symposium on Principles of distributed computing - PODC '93. pp. 171- 182 ,(1993) , 10.1145/164051.164072
Daniel Lehmann, Michael O. Rabin, On the advantages of free choice: a symmetric and fully distributed solution to the dining philosophers problem symposium on principles of programming languages. pp. 133- 138 ,(1981) , 10.1145/567532.567547
Phillip B. Gibbons, Yossi Matias, Vijaya Ramachandran, Efficient low-contention parallel algorithms Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures - SPAA '94. ,vol. 53, pp. 236- 247 ,(1994) , 10.1145/181014.181382
Maurice Herlihy, Beng-Hong Lim, Nir Shavit, Low contention load balancing on large-scale multiprocessors Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures - SPAA '92. pp. 219- 227 ,(1992) , 10.1145/140901.140924
T.E. Anderson, The performance of spin lock alternatives for shared-money multiprocessors IEEE Transactions on Parallel and Distributed Systems. ,vol. 1, pp. 6- 16 ,(1990) , 10.1109/71.80120
Michael O. Rabin, The choice coordination problem Acta Informatica. ,vol. 17, pp. 121- 134 ,(1982) , 10.1007/BF00288965
Maurice Herlihy, Wait-free synchronization ACM Transactions on Programming Languages and Systems. ,vol. 13, pp. 124- 149 ,(1991) , 10.1145/114005.102808
Jae-Heon Yang, James H. Anderson, Time bounds for mutual exclusion and related problems Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94. pp. 224- 233 ,(1994) , 10.1145/195058.195139