The Art of Multiprocessor Programming
This page intentionally left blank
The Art of Multiprocessor
Programming
Maurice Herlihy
Nir Shavit
AMSTERDAM • BOSTON • HEIDELBERG • LONDON
SAN FRANCISCO • SINGAPORE • SYDNEY • TOKYO
NEW YORK • OXFORD • PARIS • SAN DIEGO
Morgan Kaufmann Publishers is an imprint of Elsevier
Acquisitions Editor
Tiffany Gasbarrini
Publishing Services Manager George Morrison
Senior Production Editor
Cover Design
Composition
Interior printer
Cover printer
Paul Gottehrer
Alisa Andreola
diacriTech
Sheridan Books
Phoenix Color Corp.
Morgan Kaufmann Publishers is an imprint of Elsevier.
30 Corporate Drive, Suite 400, Burlington, MA 01803, USA
This book is printed on acid-free paper. ∞
Copyright © 2008 by Elsevier Inc. All rights reserved.
Designations used by companies to distinguish their products are often claimed as trademarks or registered
trademarks. In all instances in which Morgan Kaufmann Publishers is aware of a claim, the product names
appear in initial capital or all capital letters. Readers, however, should contact the appropriate companies
for more complete information regarding trademarks and registration.
No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or
by any means—electronic, mechanical, photocopying, scanning, or otherwise—without prior written
permission of the publisher.
Permissions may be sought directly from Elsevier’s Science & Technology Rights Department in Oxford,
UK: phone: (+44) 1865 843830, fax: (+44) 1865 853333, E-mail: permissions@elsevier.com. You may also
complete your request online via the Elsevier homepage (http://elsevier.com), by selecting “Support & Contact”
then “Copyright and Permission” and then “Obtaining Permissions.”
Library of Congress Cataloging-in-Publication Data
Application submitted
ISBN: 978-0-12-370591-4
For information on all Morgan Kaufmann publications,
visit our Web site at www.mkp.com or www.books.elsevier.com
Printed and bound in the United States of America
09 10 11 12 13
5 4 3 2 1
For my parents, David and Patricia Herlihy, and for Liuba, David, and Anna.
For 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 book.
This page intentionally left blank
Contents
xvii
xix
1
3
6
8
9
10
12
13
15
15
16
19
21
21
22
vii
Acknowledgments
Preface
1 Introduction
1.1 Shared Objects and Synchronization
1.2 A Fable
1.2.1 Properties of Mutual Exclusion
1.2.2 The Moral
1.3 The Producer–Consumer Problem
1.4 The Readers–Writers Problem
1.5 The Harsh Realities of Parallelization
1.6 Parallel Programming
1.7 Chapter Notes
1.8 Exercises
I PRINCIPLES
2 Mutual Exclusion
2.1 Time
2.2 Critical Sections