Art of Multiprocessor Programming

1 The Art of Multiprocessor ProgrammingThis page intentionally left blankThe Art of MultiprocessorProgrammingMaurice HerlihyNir ShavitAMSTERDAM BOSTON HEIDELBERG LONDONNEW YORK OXFORD PARIS SAN DIEGOSAN FRANCISCO SINGAPORE SYDNEY TOKYOM organ Kaufmann Publishers is an imprint of ElsevierAcquisitions EditorTiffany GasbarriniPublishing Services ManagerGeorge MorrisonSenior Production EditorPaul GottehrerCover DesignAlisa AndreolaCompositiondiacriTechInterior printerSheridan BooksCover printerPhoenix Color Kaufmann Publishers is an imprint of Corporate Drive, Suite 400, Burlington, MA 01803, USAThis book is printed on acid-free paper. Copyright 2008 by Elsevier Inc. All rights used by companies to distinguish their products are often claimed as trademarks or registeredtrademarks. In all instances in which Morgan Kaufmann Publishers is aware of a claim, the product namesappear in initial capital or all capital letters.

2 Readers, however, should contact the appropriate companiesfor more complete information regarding trademarks and part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form orby any means electronic, mechanical, photocopying, scanning, or otherwise without prior writtenpermission of the may be sought directly from Elsevier s Science & Technology Rights Department in Oxford,UK: phone: (+44) 1865 843830, fax: (+44) 1865 853333, E-mail: You may alsocomplete your request online via the Elsevier homepage ( ), by selecting Support & Contact then Copyright and Permission and then Obtaining Permissions. Library of Congress Cataloging-in-Publication DataApplication submittedISBN: 978-0-12-370591-4 For information on all Morgan Kaufmann publications,visit our Web site and bound in the United States of America0910111213 54321 For my parents, David and Patricia Herlihy, and for Liuba, David, and my parents, Noun and Aliza, my beautiful wife Shafi, and my kids,Yonadav and Lior, for their love and their patience, their incredible,unbelievable, and unwavering patience.

3 Throughout the writing of this page intentionally left blankContentsAcknowledgmentsxviiPrefacex ix1 Shared Objects and A Properties of Mutual The The Producer Consumer The Readers Writers The Harsh Realities of Parallel Chapter Exercises16 IPRINCIPLES192 Mutual Critical 2-Thread The Peterson The Filter Lamport s Bakery Bounded Lower Bounds on the Number of Chapter Exercises413 Concurrent Concurrency and Sequential Quiescent Sequential Linearization Formal Compositional The Nonblocking Progress Dependent Progress The Java memory Locks and Synchronized Volatile Final Chapter Exercises664 Foundations of Shared The Space of Register MRSW Safe A Regular Boolean MRSW A RegularM-Valued MRSW An Atomic SRSW An Atomic MRSW An Atomic MRMW Atomic An Obstruction-Free A Wait-Free Correctness Chapter Exercises945 The Relative Power of PrimitiveSynchronization Consensus States and Atomic Consensus FIFO Multiple Assignment Read Modify Write Common2 RMW ThecompareAndSet()

4 Chapter Exercises118xContents6 Universality of A Lock-Free Universal A Wait-Free Universal Chapter Exercises137 IIPRACTICE1397 Spin Locks and Welcome to the Real Test-And-Set TAS-Based Spin Locks Exponential Queue Array-Based The CLH Queue The MCS Queue A Queue Lock with A Composite A Fast-Path Composite Hierarchical A Hierarchical Backoff A Hierarchical CLH Queue One Lock To Rule Them Chapter Exercises1748 Monitors and Blocking Monitor Locks and The Lost-Wakeup Readers Writers Simple Readers Writers Fair Readers Writers Our Own Reentrant Chapter Exercises1909 Linked Lists: The Role of List-Based Concurrent Coarse-Grained Fine-Grained Optimistic Lazy Non-Blocking Chapter Exercises21910 Concurrent Queues and the ABA A Bounded Partial An Unbounded Total An Unbounded Lock-Free memory Reclamation and the ABA A Na ve Synchronous Dual Data Chapter Exercises24111 Concurrent Stacks and An Unbounded Lock-Free The Elimination Backoff A Lock-Free The Elimination Chapter Exercises25512 Counting, Sorting.

5 And Shared Software An Extended Performance and Quiescently Consistent Pools and Counting Networks That The Bitonic Counting Performance and Diffracting Parallel Sorting Designing a Sorting Sample Distributed Chapter Exercises29313 Concurrent Hashing and Closed-Address Hash A Coarse-Grained Hash A Striped Hash A Refinable Hash A Lock-Free Hash Recursive TheLockFreeHashSet<T> An Open-Addressed Hash Cuckoo Concurrent Cuckoo Striped Concurrent Cuckoo A Refinable Concurrent Cuckoo Hash Chapter Exercises32614 Skiplists and Balanced Sequential A Lock-Based Concurrent A Bird s-Eye The A Lock-Free Concurrent A Bird s-Eye The Algorithm in Concurrent Chapter Exercises349xivContents15 Priority Concurrent Priority An Array-Based Bounded Priority A Tree-Based Bounded Priority An Unbounded Heap-Based Priority A Sequential A Concurrent A Skiplist-Based Unbounded Priority Chapter Exercises36616 Futures, Scheduling, and Work Analyzing Realistic Multiprocessor Work Work Yielding and Work-Stealing A Bounded Work-Stealing An Unbounded Work-Stealing Work Chapter Exercises39217 Barrier Sense-Reversing Combining Tree Static Tree Termination Detecting Chapter Exercises40918 Transactional What is Wrong with Locking?

6 What is Wrong withcompareAndSet()? What is Wrong with Compositionality? What can We Do about It? Transactions and Software Transactional Transactions and Transactional Zombies and Atomic Dependent or Independent Progress? Contention Implementing Atomic An Obstruction-Free Atomic A Lock-Based Atomic Hardware Transactional Cache Transactional Cache Chapter Exercises449 IIIAPPENDIX451A Software Yielding and Thread-Local C# Thread-Local Thread-Local Chapter Notes466B Hardware Introduction (and a Puzzle) Processors and Cache-Conscious Programming , or the Multi-Core and Multi-Threaded Relaxed memory Hardware Synchronization Chapter Exercises481 Bibliography483 Index495 AcknowledgmentsWe would like to thank Doug Lea, Michael Scott, Ron Rivest, Tom Corman,Michael Sipser, Radia Pearlman, George Varghese and Michael Sipser for theirhelp in finding the right publication venue for our thank all the students, colleagues, and friends who read our draft chap-ters and sent us endless lists of comments and ideas.

7 Yehuda Afek, Shai Ber,Martin Buchholz, Vladimir Budovsky, Christian Cachin, Cliff Click, Yoav Cohen,Dave Dice, Alexandra Fedorova, Pascal Felber, Christof Fetzer, Shafi Goldwasser,Rachid Guerraoui, Tim Harris, Danny Hendler, Maor Hizkiev, Eric Koskinen,Christos Kozyrakis, Edya Ladan, Doug Lea, Oren Lederman, Pierre Leone, YossiLev, Wei Lu, Victor Luchangco, Virendra Marathe, John Mellor-Crummey, MarkMoir, Dan Nussbaum, Kiran Pamnany, Ben Pere, Torvald Riegel, Vijay Saraswat,Bill Scherer, Warren Schudy, Michael Scott, Ori Shalev, Marc Shapiro, YotamSoen, Ralf Suckow, Seth Syberg, Alex Weiss, and Zhenyuan Zhao. We apologizefor any names inadvertently thank Mark Moir, Steve Heller, and our colleagues in the Scalable Syn-chronization group at Sun Microsystems for their incredible support during thewriting of the book offers complete code for all the examples, as well asslides, updates, and other useful tools on its companion web pageat: book is intended to serve both as a textbook for a senior-level undergraduatecourse, and as a reference for should know enough discrete mathematics to understand big-O notation, and what it means for a problem to be NP-complete.

8 It is helpful tobe familiar with elementary systems constructs such as processors, threads, andcaches. A basic understanding of Java is needed to follow the examples. (Weexplain advanced language features before using them.) Two appendixes summa-rize what the reader needs to know: Appendix A covers Programming languageconstructs, and Appendix B covers Multiprocessor hardware first third covers theprinciplesof concurrent Programming , showing howtothinklike a concurrent programmer. Like many other skills such as driving a car,cooking a meal, or appreciating caviar, thinking concurrently requires cultivation,but it can be learned with moderate effort. Readers who want to start program-ming right away may skip most of this section, but should still read Chapters 2and 3 which cover the basic ideas necessary to understand the rest of the first look at the classicmutual exclusionproblem (Chapter 2).

9 This chap-ter is essential for understanding why concurrent Programming is a challenge. Itcovers basic concepts such as fairness and deadlock. We then ask what it meansfor a concurrent program to be correct (Chapter 3). We consider several alter-native conditions, and the circumstances one might want to use each one. Weexamine the properties ofshared memoryessential to concurrent computation(Chapter 4), and we look at the kinds of synchronization primitives needed toimplement highly concurrent data structures (Chapters 5 and 6).We think it is essential that anyone who wants to become truly skilled in theart of Multiprocessor Programming spend time solving the problems presentedin the first part of this book. Although these problems are idealized, they distillthe kind of thinking necessary to write effective Multiprocessor programs.

10 MostxixxxPrefaceimportant, they distill the style of thinking necessary to avoid the commonmistakes committed by nearly all novice programmers when they first next two-thirds describe thepracticeof concurrent Programming . Eachchapter has a secondary theme, illustrating either a particular Programming pat-tern or algorithmic technique. At the level of systems and languages, Chapter 7covers spin locks and contention. This chapter introduces the importance ofthe underlying architecture, since spin lock performance cannot be understoodwithout understanding the Multiprocessor memory hierarchy. Chapter 8 coversmonitor locks and waiting, a common synchronization idiom, especially in 16 covers work-stealing and parallelism, and Chapter 17 describes bar-riers, all of which are useful for structure concurrent chapters cover concurrent data structures.