logo资料库

The Art of Multiprocessor Programming.pdf

发布时间：2022-05-31 发布人：admin 分类：说明书 资料大小：4.44M 资料格式：pdf 举报 版权申诉
第1页 / 共529页
第2页 / 共529页
第3页 / 共529页
第4页 / 共529页
第5页 / 共529页
第6页 / 共529页
第7页 / 共529页
第8页 / 共529页
资料共529页，剩余部分请下载后查看
    The Art of Multiprocessor Programming
    Copyright Page
    Table of Contents
    Acknowledgments
    Preface
    Chapter 1. Introduction
    1.1 Shared Objects and Synchronization
    1.2 A Fable
    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
    Part I: Principles
    Chapter 2. Mutual Exclusion
    2.1 Time
    2.2 Critical Sections
    2.3 2-Thread Solutions
    2.4 The Filter Lock
    2.5 Fairness
    2.6 Lamport’s Bakery Algorithm
    2.7 Bounded Timestamps
    2.8 Lower Bounds on the Number of Locations
    2.9 Chapter Notes
    2.10 Exercises
    Chapter 3. Concurrent Objects
    3.1 Concurrency and Correctness
    3.2 Sequential Objects
    3.3 Quiescent Consistency
    3.4 Sequential Consistency
    3.5 Linearizability
    3.6 Formal Definitions
    3.7 Progress Conditions
    3.8 The Java Memory Model
    3.9 Remarks
    3.10 Chapter Notes
    3.11 Exercises
    Chapter 4. Foundations of Shared Memory
    4.1 The Space of Registers
    4.2 Register Constructions
    4.3 Atomic Snapshots
    4.4 Chapter Notes
    4.5 Exercises
    Chapter 5. The Relative Power of Primitive Synchronization Operations
    5.1 Consensus Numbers
    5.2 Atomic Registers
    5.3 Consensus Protocols
    5.4 FIFO Queues
    5.5 Multiple Assignment Objects
    5.6 Read–Modify–Write Operations
    5.7 Common2 RMW Operations
    5.8 The compareAndSet() Operation
    5.9 Chapter Notes
    5.10 Exercises
    Chapter 6. Universality of Consensus
    6.1 Introduction
    6.2 Universality
    6.3 A Lock-Free Universal Construction
    6.4 A Wait-Free Universal Construction
    6.5 Chapter Notes
    6.6 Exercises
    Part II: Practice
    Chapter 7. Spin Locks and Contention
    7.1 Welcome to the Real World
    7.2 Test-And-Set Locks
    7.3 TAS-Based Spin Locks Revisited
    7.4 Exponential Backoff
    7.5 Queue Locks
    7.6 A Queue Lock with Timeouts
    7.7 A Composite Lock
    7.8 Hierarchical Locks
    7.9 One Lock To Rule Them All
    7.10 Chapter Notes
    7.11 Exercises
    Chapter 8. Monitors and Blocking Synchronization
    8.1 Introduction
    8.2 Monitor Locks and Conditions
    8.3 Readers–Writers Locks
    8.4 Our Own Reentrant Lock
    8.5 Semaphores
    8.6 Chapter Notes
    8.7 Exercises
    Chapter 9. Linked Lists: The Role of Locking
    9.1 Introduction
    9.2 List-Based Sets
    9.3 Concurrent Reasoning
    9.4 Coarse-Grained Synchronization
    9.5 Fine-Grained Synchronization
    9.6 Optimistic Synchronization
    9.7 Lazy Synchronization
    9.8 Non-Blocking Synchronization
    9.9 Discussion
    9.10 Chapter Notes
    9.11 Exercises
    Chapter 10. Concurrent Queues and the ABA Problem
    10.1 Introduction
    10.2 Queues
    10.3 A Bounded Partial Queue
    10.4 An Unbounded Total Queue
    10.5 An Unbounded Lock-Free Queue
    10.6 Memory Reclamation and the ABA Problem
    10.7 Dual Data Structures
    10.8 Chapter Notes
    10.9 Exercises
    Chapter 11. Concurrent Stacks and Elimination
    11.1 Introduction
    11.2 An Unbounded Lock-Free Stack
    11.3 Elimination
    11.4 The Elimination Backoff Stack
    11.5 Chapter Notes
    11.6 Exercises
    Chapter 12. Counting, Sorting, and Distributed Coordination
    12.1 Introduction
    12.2 Shared Counting
    12.3 Software Combining
    12.4 Quiescently Consistent Pools and Counters
    12.5 Counting Networks
    12.6 Diffracting Trees
    12.7 Parallel Sorting
    12.8 Sorting Networks
    12.9 Sample Sorting
    12.10 Distributed Coordination
    12.11 Chapter Notes
    12.12 Exercises
    Chapter 13. Concurrent Hashing and Natural Parallelism
    13.1 Introduction
    13.2 Closed-Address Hash Sets
    13.3 A Lock-Free Hash Set
    13.4 An Open-Addressed Hash Set
    13.5 Chapter Notes
    13.6 Exercises
    Chapter 14. Skiplists and Balanced Search
    14.1 Introduction
    14.2 Sequential Skiplists
    14.3 A Lock-Based Concurrent Skiplist
    14.4 A Lock-Free Concurrent Skiplist
    14.5 Concurrent Skiplists
    14.6 Chapter Notes
    14.7 Exercises
    Chapter 15. Priority Queues
    15.1 Introduction
    15.2 An Array-Based Bounded Priority Queue
    15.3 A Tree-Based Bounded Priority Queue
    15.4 An Unbounded Heap-Based Priority Queue
    15.5 A Skiplist-Based Unbounded Priority Queue
    15.6 Chapter Notes
    15.7 Exercises
    Chapter 16. Futures, Scheduling, and Work Distribution
    16.1 Introduction
    16.2 Analyzing Parallelism
    16.3 Realistic Multiprocessor Scheduling
    16.4 Work Distribution
    16.5 Work-Stealing Dequeues
    16.6 Chapter Notes
    16.7 Exercises
    Chapter 17. Barriers
    17.1 Introduction
    17.2 Barrier Implementations
    17.3 Sense-Reversing Barrier
    17.4 Combining Tree Barrier
    17.5 Static Tree Barrier
    17.6 Termination Detecting Barriers
    17.7 Chapter Notes
    17.8 Exercises
    Chapter 18. Transactional Memory
    18.1 Introduction
    18.2 Transactions and Atomicity
    18.3 Software Transactional Memory
    18.4 Hardware Transactional Memory
    18.5 Chapter Notes
    18.6 Exercises
    Part III: Appendix
    Appendix A. Software Basics
    A.1 Introduction
    A.2 Java
    A.3 C#
    A.4 Pthreads
    A.5 Chapter Notes
    Appendix B. Hardware Basics
    B.1 Introduction (and a Puzzle)
    B.2 Processors and Threads
    B.3 Interconnect
    B.4 Memory
    B.5 Caches
    B.6 Cache-Conscious Programming, or the Puzzle Solved
    B.7 Multi-Core and Multi-Threaded Architectures
    B.8 Hardware Synchronization Instructions
    B.9 Chapter Notes
    B.10 Exercises
    Bibliography
    Index
    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
    分享到：
    赞 收藏

    相关推荐

    资料库

    开发技术

    共收录19306份资料，累计14个分类，关注成员有19位，主要包括：Actionscript,Javascript,PHP,VB,Perl,Delphi,Python,C#,C,Java,C++,Web开发,硬件开发,其它

    热门标签

    Actionscript Javascript PHP VB Perl Delphi Python C# C Java C++ Web开发 硬件开发 其它

    最新资料