modern-multithreading-c-java
.pdf
MODERN MULTITHREADING
Implementing, Testing, and
Debugging Multithreaded Java and
C++/Pthreads/Win32 Programs
RICHARD H. CARVER
KUO-CHUNG TAI
A JOHN WILEY & SONS, INC., PUBLICATION
MODERN MULTITHREADING
MODERN MULTITHREADING
Implementing, Testing, and
Debugging Multithreaded Java and
C++/Pthreads/Win32 Programs
RICHARD H. CARVER
KUO-CHUNG TAI
A JOHN WILEY & SONS, INC., PUBLICATION
Copyright 2006 by John Wiley & Sons, Inc. All rights reserved.
Published by John Wiley & Sons, Inc., Hoboken, New Jersey.
Published simultaneously in Canada.
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, recording, scanning, or otherwise, except as permitted under Section 107 or 108 of the 1976 United States Copyright Act, without either the prior written permission of the Publisher, or authorization through payment of the appropriate per-copy fee to the Copyright Clearance Center, Inc., 222 Rosewood Drive, Danvers, MA 01923, (978) 750-8400, fax (978) 750-4470, or on the web at www.copyright.com. Requests to the Publisher for permission should be addressed to the Permissions Department, John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030, (201) 748-6011, fax (201) 748-6008, or online at http://www.wiley.com/go/permission.
Limit of Liability/Disclaimer of Warranty: While the publisher and author have used their best efforts in preparing this book, they make no representations or warranties with respect to the accuracy or completeness of the contents of this book and specifically disclaim any implied warranties of merchantability or fitness for a particular purpose. No warranty may be created or extended by sales representatives or written sales materials. The advice and strategies contained herein may not be suitable for your situation. You should consult with a professional where appropriate. Neither the publisher nor author shall be liable for any loss of profit or any other commercial damages, including but not limited to special, incidental, consequential, or other damages.
For general information on our other products and services or for technical support, please contact our Customer Care Department within the United States at (800) 762-2974, outside the United States at (317) 572-3993 or fax (317) 572-4002.
Wiley also publishes its books in a variety of electronic formats. Some content that appears in print may not be available in electronic formats. For more information about Wiley products, visit our web site at www.wiley.com.
Library of Congress Cataloging-in-Publication Data:
Carver, Richard H., 1960–
Modern multithreading: implementing, testing, and debugging multithreaded Java and C++/Pthreads/Win32 programs / by Richard H. Carver and Kuo-Chung Tai.
p. cm.
Includes bibliographical references and index. ISBN-13 978-0-471-72504-6 (paper) ISBN-10 0-471-72504-8 (paper)
1. Parallel programming (Computer science) 2. Threads (Computer programs) I. Tai, Kuo-Chung. II. Title.
QA76.642.C38 2006 005.1 1–dc22
2005045775
Printed in the United States of America.
10 9 8 7 6 5 4 3 2 1
CONTENTS
Preface |
xi |
1 Introduction to Concurrent Programming |
1 |
1.1Processes and Threads: An Operating System’s View, 1
1.2Advantages of Multithreading, 3
1.3Threads in Java, 4
1.4Threads in Win32, 6
1.5Pthreads, 9
1.6C++ Thread Class, 14
1.6.1C++ Class Thread for Win32, 14
1.6.2C++ Class Thread for Pthreads, 19
1.7Thread Communication, 19
1.7.1Nondeterministic Execution Behavior, 23
1.7.2Atomic Actions, 25
1.8Testing and Debugging Multithreaded Programs, 29
1.8.1Problems and Issues, 30
1.8.2Class TDThread for Testing and Debugging, 34
1.8.3Tracing and Replaying Executions with Class Template sharedVariable<>, 37
1.9Thread Synchronization, 38
Further Reading, 38
References, 39
Exercises, 41
v
vi |
CONTENTS |
2 The Critical Section Problem |
46 |
2.1Software Solutions to the Two-Thread Critical Section Problem, 47
2.1.1Incorrect Solution 1, 48
2.1.2Incorrect Solution 2, 49
2.1.3Incorrect Solution 3, 50
2.1.4Peterson’s Algorithm, 52
2.1.5Using the volatile Modifier, 53
2.2Ticket-Based Solutions to the n-Thread Critical Section Problem, 54
2.2.1Ticket Algorithm, 54
2.2.2Bakery Algorithm, 56
2.3Hardware Solutions to the n-Thread Critical Section Problem, 58
2.3.1Partial Solution, 59
2.3.2Complete Solution, 59
2.3.3Note on Busy-Waiting, 60
2.4Deadlock, Livelock, and Starvation, 62
2.4.1Deadlock, 62
2.4.2Livelock, 62
2.4.3Starvation, 63
2.5Tracing and Replay for Shared Variables, 64
2.5.1ReadWrite-Sequences, 65
2.5.2Alternative Definition of ReadWrite-Sequences, 67
2.5.3Tracing and Replaying ReadWrite-Sequences, 68
2.5.4Class Template sharedVariable<>, 70
2.5.5Putting It All Together, 71
2.5.6Note on Shared Memory Consistency, 74
Further Reading, 77
References, 78
Exercises, 79
3 Semaphores and Locks |
84 |
3.1Counting Semaphores, 84
3.2Using Semaphores, 86
3.2.1Resource Allocation, 86
3.2.2More Semaphore Patterns, 87
3.3Binary Semaphores and Locks, 90
3.4Implementing Semaphores, 92
3.4.1Implementing P() and V(), 92
3.4.2VP() Operation, 94
3.5Semaphore-Based Solutions to Concurrent Programming Problems, 96
3.5.1Event Ordering, 96
CONTENTS |
vii |
3.5.2Bounded Buffer, 96
3.5.3Dining Philosophers, 98
3.5.4Readers and Writers, 101
3.5.5Simulating Counting Semaphores, 108
3.6Semaphores and Locks in Java, 111
3.6.1Class countingSemaphore, 111
3.6.2Class mutexLock, 113
3.6.3Class Semaphore, 115
3.6.4Class ReentrantLock, 116
3.6.5Example: Java Bounded Buffer, 116
3.7Semaphores and Locks in Win32, 119
3.7.1CRITICAL SECTION, 119
3.7.2Mutex, 122
3.7.3Semaphore, 124
3.7.4Events, 132
3.7.5Other Synchronization Functions, 134
3.7.6Example: C++/Win32 Bounded Buffer, 134
3.8Semaphores and Locks in Pthreads, 134
3.8.1Mutex, 136
3.8.2Semaphore, 137
3.9Another Note on Shared Memory Consistency, 141
3.10Tracing, Testing, and Replay for Semaphores and Locks, 143
3.10.1Nondeterministic Testing with the Lockset Algorithm, 143
3.10.2Simple SYN-Sequences for Semaphores and Locks, 146
3.10.3Tracing and Replaying Simple PV-Sequences and LockUnlock-Sequences, 150
3.10.4Deadlock Detection, 154
3.10.5Reachability Testing for Semaphores and Locks, 157
3.10.6Putting It All Together, 160
Further Reading, 163
References, 164
Exercises, 166
4 Monitors |
177 |
4.1Definition of Monitors, 178
4.1.1Mutual Exclusion, 178
4.1.2Condition Variables and SC Signaling, 178
4.2Monitor-Based Solutions to Concurrent Programming Problems, 182
4.2.1Simulating Counting Semaphores, 182
4.2.2Simulating Binary Semaphores, 183
4.2.3Dining Philosophers, 183
4.2.4Readers and Writers, 187
viii |
CONTENTS |
4.3Monitors in Java, 187
4.3.1Better countingSemaphore, 190
4.3.2notify vs. notifyAll, 191
4.3.3Simulating Multiple Condition Variables, 194
4.4Monitors in Pthreads, 194
4.4.1Pthreads Condition Variables, 196
4.4.2Condition Variables in J2SE 5.0, 196
4.5Signaling Disciplines, 199
4.5.1Signal-and-Urgent-Wait, 199
4.5.2Signal-and-Exit, 202
4.5.3Urgent-Signal-and-Continue, 204
4.5.4Comparing SU and SC Signals, 204
4.6Using Semaphores to Implement Monitors, 206
4.6.1SC Signaling, 206
4.6.2SU Signaling, 207
4.7Monitor Toolbox for Java, 209
4.7.1Toolbox for SC Signaling in Java, 210
4.7.2Toolbox for SU Signaling in Java, 210
4.8Monitor Toolbox for Win32/C++/Pthreads, 211
4.8.1Toolbox for SC Signaling in C++/Win32/Pthreads, 213
4.8.2Toolbox for SU Signaling in C++/Win32/Pthreads, 213
4.9Nested Monitor Calls, 213
4.10Tracing and Replay for Monitors, 217
4.10.1Simple M-Sequences, 217
4.10.2Tracing and Replaying Simple M-Sequences, 219
4.10.3Other Approaches to Program Replay, 220
4.11Testing Monitor-Based Programs, 222
4.11.1M-Sequences, 222
4.11.2Determining the Feasibility of an M-Sequence, 227
4.11.3Determining the Feasibility of a Communication-Sequence, 233
4.11.4Reachability Testing for Monitors, 233
4.11.5Putting It All Together, 235
Further Reading, 243
References, 243
Exercises, 245
5 Message Passing |
258 |
5.1Channel Objects, 258
5.1.1Channel Objects in Java, 259
5.1.2Channel Objects in C++/Win32, 263
5.2Rendezvous, 266
5.3Selective Wait, 272