Theartofmultiprocessorprogramming

The art of multiprocessor programming 是讲述多处理器编程的经典。This page intentionally left blankThe Art of MultiprocessorProgrammingMaurice HerlihyNir shavitAMSTERDAM● BOSTON· HEIDELBERG· LONDONNEW YORK· OXFORD● PARIS· SAN DIEGOSAN FRANCISCO· SINGAPORE· SYDNEY· TOKYOELSEVIERMorgan Kaufmann Publishers is an imprint of ElsevierMORGAN KAUFMANN PUBLISHERSAcquisitions editorTiffany gasbarriniPublishing Services Manager George MorrisonSenior production editorPaul gottehrerCover designAlisa andreolaCompositiondiacritechInterior printeSheridan booksCover prrinterPhoenix Color CorpMorgan Kaufmann Publishers is an imprint of elsevier30 Corporate Drive, Suite 400, Burlington, MA 01803, USAThis book is printed on acid-free paperCopyright@ 2008 by Elsevier Inc. All rights reservedDesignations 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. Readers, however, should contact the appropriate companiesfor more complete information regarding trademarks and registrationNo part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form ory any means--electronic, mechanical, photocopying, scanning, or otherwise--without prior writtenpermission of the publisher.Permissions may be sought directly from Elsevier's Science Technology Rights Department in Oxford,UK:phone:(+44)1865843830,fax:(+44)1865853333,E-mail:permissions@elsevier.com.YoumayalsocompleteyourrequestonlineviatheElsevierhomepage(http://elsevier.com),byselectingsupport&Contactthen“ Copyright and Permission" and then“ Obtaining Permissions.”Library of Congress Cataloging-in-Publication DataApplication submittedISBN:978-0-12-370591-4For information on all Morgan Kaufmann publications,visitourWebsiteatwww.mkp.comorwww.books.elsevier.comPrinted and bound in the United States of america091011121354321Working together to groworaries in developing countrieswww.elsevier.comwww.bookaid.orgwww.sabre.orgelsevier bookAId Sabre FoundationFor my parents, David and Patricia Herlihy, and for Liuba, David, and annaFor 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, throughout the writing of this bookThis page intentionally left blankContentsAcknowledgmentsXVIIPrefaceXIXIntroductionI Shared Objects and synchronizationL2 A Fable2.1 Properties of Mutual Exclusion2.2 The moral93 The Producer-Consumer problem4 The readers-Writers Problem5 The harsh realities of parallelization6 Parallel ProgrammingI 7 Chapter notes58 Exercises16PRINCIPLES2 Mutual exclusion2.|Ti2.2 Critical sectionsVIlContents2.3 2-Thread solutions242,3. The lockon class252.3.2 The Lock Two class262.3.3 The Peterson lock272.4 The filter lock2.5 Fairness832.6 Lamport's bakery Algorithm2.7 Bounded Timestamps332 8 Lower bounds on the number of locations372.9 Chapter Notes402.0 Exercises43 Concurrent Objects453.1 Concurrency and Correctness453.2 Sequential Objects483.3 Quiescent Consistency493.3 Remarks3.4 SequentialConsistency553.4 Remarks523.5 Linearizability543.5. Linearization points553.5.2 Remarks553.6 Formal definitions553.6 Linearizability573.6.2 Compositional Linearizability573.6.3 The Nonblocking Property583.7 Progress Conditions593.7. Dependent Progress Conditions03. 8 The java Memory Model6663. 8. Locks and synchronized blocks38.2∨ olatile fields633.8.3 Final Fields63Contents3 9 Remarks643.10 Chapter notes653.|E× raises4 Foundations of Shared Memory4. The Space of Registers724.2 Register Constructions774.2.I MRSW Safe registers784.2.2 A Regular boolean mrs register784.2.3 A Regular m-valued MrS register794.2.4 An AtomIC SRSW Register84. 2.5 An Atomic MRSW register824.2.6 An Atomic MRMW register854.3 Atomic Snapshe874.3.1 An Obstruction-Free Snapshot874.3.2 A Wait-Free Snapshot4.3.3 Correctness Arguments4.4 Chapter notes4.5E× excises945 The relative power of primitiveSynchronization Operations995. Consensus numbers1005.. States and valence5.2 Atomic Registers035.3 Consensus Protocols1065.4 FIFO Queues1065.5 Multiple Assignment Objects5.6 Read-Modify-Write Operations125.7 Common2 RMW Operations5. 8 The compareAndSet()Operation5.9 Chapter Notes