Shared-Memory Synchronization

MICHAEL L. SCOTT is the Arthur Gould Yates Professor of Engineering and Chair of the Department of Computer Science at the University of Rochester. He received his Ph.D. from the University of Wisconsin-Madison in 1985. His research interests span operating systems, languages, architecture, and tools, with a particular emphasis on parallel and distributed systems. He is best known for work in synchronization algorithms and concurrent data structures, in recognition of which he shared the 2006 SIGACT/SIGOPS Edsger W. Dijkstra Prize. His textbook on programming language design and implementation (Programming Language Pragmatics, fourth edition, Morgan Kaufmann, Dec. 2015) is a standard in the field. He served as General Chair of SOSP in 2003 and as Program Chair of TRANSACT'07, PPoPP '08, and ASPLOS '12. He was named a Fellow of the ACM in 2006, of the IEEE in 2010, and of the AAAS in 2021. At the University of Rochester, he received the Robert and Pamela Goergen Award for Distinguished Achievement and Artistry in Undergraduate Teaching in 2001, the Edmund A. Hajim School of Engineering Lifetime Achievement Award in 2018, and the William H. Riker University Award for Graduate Teaching in 2020.

Trevor Brown is an Assistant Professor in the Cheriton School of Computer Science at the University of Waterloo. He completed his Ph.D. under the supervision of Faith Ellen at the University of Toronto in 2017, and conducted postdoctoral studies at the Institute of Science and Technology, Austria, and the Technion, Israel. His research straddles theory and practice, and focuses on the question of how large scale multicore systems can be programmed easily, efficiently and correctly. His specific research interests include concurrent data structures, lock-free synchronization, memory management, transactional memory, and non-volatile memory. At the University of Toronto, he won the Award for Excellence in Teaching Assistance in 2014. He has served multiple times on the Program Committees of ICDCS, PODC, PPoPP, SIROCCO, and SPAA, and was Publication Chair for PPoPP'19. He received the Best Paper Award at PPoPP'20, Best Artifact Awards at PPoPP'21 and PPoPP'22, and Finalist status in the Best Paper competitions at PPoPP'21 and SPAA'22.

1.Introduction.- 2.Architectural Background.- 3.Essential Theory.- 4.Practical Spin Locks.- 5.Busy-wait Synchronization with Conditions.- 6.Read-mostly Atomicity.- 7.Synchronization and Scheduling.- 8.Nonblocking Algorithms.- 9.Transactional Memory.