Synchronization Algorithms and Concurrent Programming

by Taubenfeld, Gadi

Edition: 1st

ISBN13: 9780131972599

ISBN10: 0131972596

Format: Paperback

Pub. Date: 2006-07-20

Publisher(s): Prentice Hall

Other versions by this Author

List Price: ~~$165.60~~

Rent Textbook

Select for Price

Add to Cart

There was a problem. Please try again later.

New Textbook

We're Sorry
Sold Out

Used Textbook

We're Sorry
Sold Out

eTextbook

We're Sorry
Not Available

Buy from our Marketplace starting at $120.10

Summary

Synchronization Algorithms and Concurrent Programming Gadi Taubenfeld Synchronization is a fundamental challenge in computer science. It is fast becoming a major performance and design issue for concurrent programming on modern architectures, and for the design of distributed systems. This is the first text to give a complete and coherent view of all aspects of synchronization algorithms. Computer science students, programmers, system designers and researchers will be able to solve problems and master techniques that go beyond the treatment provided in introductory texts on operating systems, distributed computing and concurrency. Dozens of algorithms are presented and their performance is analyzed according to precise complexity measures. Highlights of the book include Oslash; A wide variety of synchronization problems, algorithms and key concepts covered in detail. Oslash; Self-review questions with solutions to check your understanding. Oslash; A wealth of END-of-chapter exercises and bibliographic notes. Oslash; Over 300 annotated references guiding you through the contemporary research literature. Oslash; A companion website provides PowerPoint slides and other teaching and learning aids for students and instructors at www.pearsoned.co.uk/taubenfeld. About the AUTHOR Gadi Taubenfeld is an Associate Professor of Computer Science at the Interdisciplinary Center in Herzliya, Israel. He is an established AUTHORity in the area of concurrent and distributed computing and has published widely in leading journals and conferences. He was the head of the computer science division at Israel's Open University; member of technical staff at AT&T Bell Laboratories; consultant to AT&T Labs - Research; and a research scientist and lecturer at Yale University. He holds a PhD in Computer Science from the Technion Israel Institute of Technology.

Author Biography

Gadi Taubenfeld is an Associate Professor of Computer Science at the Interdisciplinary Center in Herzliya, Israel

Preface	p. xiii
Key Features	p. xv
Introduction	p. 1
Concurrent and Distributed Computing	p. 1
Data Communication and Synchronization	p. 2
Contention, Cooperation, and Resource Allocation	p. 2
Synchronization: Two Examples	p. 3
Why is Synchronization Difficult?	p. 3
Too Much Milk	p. 4
The Coordinated Attack Problem	p. 8
The Mutual Exclusion Problem	p. 10
The Problem	p. 11
Comments	p. 13
Complexity Measures	p. 14
Counting Steps	p. 14
Counting Time Units	p. 15
Counting Remote Memory Accesses	p. 16
Space Complexity	p. 17
Processes, Threads and Scheduling	p. 17
Processes	p. 17
Threads	p. 18
Scheduling	p. 19
Bibliographic Notes	p. 22
Problems	p. 23
Mutual Exclusion Using Atomic Registers: Basic Topics	p. 31
Algorithms for Two Processes	p. 31
Peterson's Algorithm	p. 32
Kessels' Single-writer Algorithm	p. 35
Tournament Algorithms	p. 37
A Solution Based on Peterson's Algorithm	p. 38
A Solution Based on Kessels' Algorithm	p. 40
A Fast Mutual Exclusion Algorithm	p. 42
Lamport's Fast Algorithm	p. 42
A Simple Observation	p. 46
Starvation-free Algorithms	p. 47
Basic Definitions	p. 48
The Bakery Algorithm	p. 49
The Black-White Bakery Algorithm	p. 55
Tight Space Bounds	p. 58
A Lower Bound	p. 59
An Upper Bound: The One-bit Algorithm	p. 63
Computing with Infinitely Many Processes	p. 66
Automatic Discovery of Algorithms	p. 68
Three Algorithms	p. 69
More Results	p. 70
Bibliographic Notes	p. 71
Problems	p. 74
Mutual Exclusion Using Atomic Registers: Advanced Topics	p. 97
Local Spinning Algorithms	p. 97
Local Spinning	p. 98
The Local Spinning Black-White Bakery Algorithm	p. 99
A Local Spinning Tournament Algorithm	p. 101
Adaptive Algorithms	p. 104
Basic Definitions	p. 104
A Simple Adaptive Algorithm	p. 105
An Adaptive Tournament Algorithm	p. 110
The Adaptive Black-White Bakery Algorithm	p. 116
An Impossibility Result	p. 119
Fault-tolerant Algorithms	p. 122
Defining Fault-tolerance	p. 123
A Fault-tolerant Algorithm	p. 124
Self-stabilization	p. 127
Symmetric Algorithms	p. 129
Symmetric Deadlock-free Algorithms	p. 130
Symmetric Starvation-free Algorithms	p. 132
Observations about Concurrency	p. 132
Bibliographic Notes	p. 133
Problems	p. 136
Blocking and Non-blocking Synchronization	p. 147
Synchronization Primitives	p. 147
Atomic Operations	p. 148
Objects	p. 150
Non-atomic Registers	p. 152
Collision Avoidance using Test-and-set Bits	p. 153
A Trivial Deadlock-free Algorithm	p. 153
Using a Test-and-test-and-set Bit	p. 154
Collision Avoidance Locks	p. 155
A Fast Starvation-free Algorithm	p. 156
The Ticket Algorithm using RMW Objects	p. 157
The Ticket Algorithm	p. 158
A Simple Lower Bound	p. 159
Local Spinning using Strong Primitives	p. 160
Anderson's Queue-based Algorithm	p. 160
Graunke and Thakkar Queue-based Algorithm	p. 163
The MCS Queue-based Algorithm	p. 165
Concurrent Data Structures	p. 169
Non-blocking and Wait-free Synchronization	p. 170
A Non-blocking Concurrent Queue Algorithm	p. 171
Semaphores	p. 176
Constant Space Starvation-free Algorithm	p. 178
Correctness Proof	p. 179
Monitors	p. 181
Fairness of Shared Objects	p. 183
Fairness Properties	p. 183
Basic Results	p. 184
Algorithms	p. 186
Bibliographic Notes	p. 189
Problems	p. 194
Barrier Synchronization	p. 203
Barriers	p. 203
Atomic Counter	p. 204
A Simple Counter Barrier	p. 204
A Local Spinning Counter Barrier	p. 206
A Barrier without Shared Memory Initialization	p. 206
Test-and-set Bits	p. 207
A Constant Space Barrier	p. 207
An Asymmetric Barrier without Memory Initialization	p. 208
Combining Tree Barriers	p. 210
A Tree-based Barrier	p. 212
The Dissemination Barrier	p. 213
The See-Saw Barrier	p. 215
The Algorithm	p. 215
Correctness Proof	p. 218
Semaphores	p. 219
Bibliographic Notes	p. 221
Problems	p. 222
The l-exclusion Problem	p. 227
The Problem	p. 227
Algorithms Using Atomic Registers	p. 229
An l-starvation-free Algorithm	p. 229
An Unbounded FIFO-enabling Algorithm	p. 231
Using a Single Read-modify-write Register	p. 234
The Counter Algorithm	p. 234
The Numbered Ticket Algorithm	p. 235
The Unbounded Colored Ticket Algorithm	p. 236
The Bounded Colored Ticket Algorithm	p. 238
The l-assignment Problem	p. 241
Bibliographic Notes	p. 243
Problems	p. 245
Multiple Resources	p. 249
Deadlocks	p. 249
Deadlock Prevention	p. 252
Two Phase Locking and Timestamping-ordering	p. 252
The Total Order Theorem	p. 253
Deadlock Avoidance: The Problem of Deadly Embrace	p. 255
The Problem	p. 255
The Banker's Algorithm	p. 256
The Dining Philosophers Problem	p. 259
The Problem	p. 259
Preliminaries	p. 260
Concurrency and Robustness	p. 262
Hold and Wait Strategy	p. 263
The LR Algorithm	p. 263
The LLR Algorithm	p. 265
A Lower Bound	p. 267
Relating Concurrency and Robustness	p. 268
Wait and Release Strategy	p. 269
Randomized Algorithms	p. 271
The Free Philosophers Algorithm	p. 272
The Courteous Philosophers Algorithm	p. 272
Bibliographic Notes	p. 274
Problems	p. 276
Classical Synchronization Problems	p. 281
The Producer-Consumer Problem	p. 281
Atomic Registers	p. 282
Atomic Counter	p. 283
General Semaphores	p. 284
Binary Semaphores	p. 284
Monitors	p. 286
Sleep and Wakeup	p. 287
Readers and Writers	p. 288
Semaphores	p. 289
Monitors	p. 290
The Sleeping Barber	p. 292
The Cigarette Smoker's Problem	p. 294
More Synchronization Problems	p. 297
Group Mutual Exclusion and Room Synchronization	p. 297
Concurrent Reading and Writing of Clocks	p. 298
The Choice Coordination Problem	p. 299
The H[subscript 2]O Problem	p. 300
The Roller Coaster Problem	p. 300
Bibliographic Notes	p. 301
Problems	p. 303
Consensus	p. 307
The Problem	p. 307
Three Simple Consensus Algorithms	p. 308
A Single 3-valued Read-modify-write Register	p. 308
Two Processes, Two Read-modify-write Bits	p. 309
Many Processes, Four Read-modify-write Bits	p. 310
Consensus without Memory Initialization	p. 311
The Algorithm	p. 312
Correctness Proof	p. 314
Reaching Consensus Using a Shared Queue	p. 316
Impossibility of Consensus with One Faulty Process	p. 318
A Formal Model	p. 318
Basic Observations	p. 320
The Impossibility Theorem	p. 321
The Relative Power of Synchronization Primitives	p. 325
The Universality of Consensus	p. 328
Basic Definitions	p. 328
A Universal Construction	p. 330
Bibliographic Notes	p. 334
Problems	p. 336
Timing-based Algorithms	p. 343
Timing-based Systems	p. 343
Mutual Exclusion with Known Delays	p. 345
Fast Mutual Exclusion with Known Delays	p. 347
The Algorithm	p. 347
Correctness Proof	p. 348
Consensus with Known Delays	p. 352
Fast Consensus with Known Delays	p. 353
The Algorithm	p. 353
Correctness Proof	p. 354
Fast Consensus with Unknown Delays	p. 355
The Algorithm	p. 355
Correctness Proof	p. 357
Fast Mutual Exclusion with Unknown Delays	p. 359
The Algorithm	p. 359
Correctness Proof	p. 361
Time Complexity	p. 363
Bibliographic Notes	p. 365
Problems	p. 366
Bibliography	p. 373
Index	p. 417
Table of Contents provided by Ingram. All Rights Reserved.

Kids

Men

Unisex

Women

For You

For Your Car

For Your Home

For Your Pet

Cards

Games

Holiday

Home Decor

Mascot

Graduation Gifts

Art Supplies

For Your Tech

Office Supplies

Clothing

Accessories

Supplies

Synchronization Algorithms and Concurrent Programming

Rent Textbook

New Textbook

Used Textbook

eTextbook

Summary

Author Biography

Table of Contents

Synchronization Algorithms and Concurrent Programming

Rent Textbook

New Textbook

Used Textbook

eTextbook

How Marketplace Works:

Summary

Author Biography

Table of Contents

Digital License