An Optimistic Approach to Lock-Free FIFO Queues
作者： Edya Ladan-Mozes , Nir Shavit
DOI: 10.1007/978-3-540-30186-8_9
关键词: Parallel computing 、 Concurrency 、 Data structure 、 Compare-and-swap 、 Double-ended queue 、 Concurrent data structure 、 Queue management system 、 Computer science 、 FIFO (computing and electronics) 、 Non-blocking algorithm 、 Queue
摘要: First-in-first-out (FIFO) queues are among the most fundamental and highly studied concurrent data structures. The effective practical dynamic-memory queue implementation in literature is lock-free FIFO algorithm of Michael Scott, included standard Java TM Concurrency Package.
springer.com
core.ac.uk
sci-hub.se 参考文章(30)
Maurice Herlihy, Victor Luchangco, Mark Moir, The repeat offender problem: a mechanism for supporting dynamic-sized lock-free data structures international symposium on distributed computing. pp. 339- 353 ,(2002) , 10.1007/3-540-36108-1_23
John M Mellor-Crummey, Concurrent Queues: Practical Fetch-and-Phi Algorithms. ,(1987)
William N. Scherer, Michael L. Scott, Nonblocking Concurrent Data Structures with Condition Synchronization international symposium on distributed computing. pp. 174- 187 ,(2004) , 10.1007/978-3-540-30186-8_13
Faye A. Briggs, Kai Hwang, Computer Architecture and Parallel Processing ,(1984)
Victor Luchangco, Mark Moir, Nir Shavit, On the Uncontended Complexity of Consensus Lecture Notes in Computer Science. pp. 45- 59 ,(2003) , 10.1007/978-3-540-39989-6_4
Philippas Tsigas, Yi Zhang, A simple, fast and scalable non-blocking concurrent FIFO queue for shared memory multiprocessor systems Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures - SPAA '01. pp. 134- 143 ,(2001) , 10.1145/378580.378611
Maurice Herlihy, Victor Luchangco, Paul Martin, Mark Moir, Dynamic-sized lock-free data structures principles of distributed computing. pp. 131- 131 ,(2002) , 10.1145/571825.571847
Maged M. Michael, Michael L. Scott, Simple, fast, and practical non-blocking and blocking concurrent queue algorithms principles of distributed computing. pp. 267- 275 ,(1996) , 10.1145/248052.248106
Maged M. Michael, Michael L. Scott, Nonblocking Algorithms and Preemption-Safe Locking on Multiprogrammed Shared Memory Multiprocessors Journal of Parallel and Distributed Computing. ,vol. 51, pp. 1- 26 ,(1998) , 10.1006/JPDC.1998.1446
Danny Dolev, Eli Gafni, Michael Merritt, Nir Shavit, Yehuda Afek, Hagit Attiya, Atomic snapshots of shared memory Journal of the ACM. ,vol. 40, pp. 873- 890 ,(1993) , 10.1145/153724.153741