Concurrent Queues and Stacks
Concurrent Queues and Stacks Companion slides for The Art of Multiprocessor Programming by Maurice Herlihy & Nir Shavit
The Five-Fold Path
Art of Multiprocessor Programming 2 2 The Five-Fold Path Coarse-grained locking Fine-grained locking Optimistic synchronization Lazy synchronization Lock-free synchronization
Another Fundamental Problem
Art of Multiprocessor Programming 3 3 Another Fundamental Problem We told you about Sets implemented by linked lists Next: queues Next: stacks
Queues & Stacks
Art of Multiprocessor Programming 4 4 Queues & Stacks pool of items
Queues
Art of Multiprocessor Programming 5 5 Queues deq()/ enq( ) Total order First in First out
Stacks
Art of Multiprocessor Programming 6 6 Stacks pop()/ push( ) Total order Last in First out
Bounded
Art of Multiprocessor Programming 7 7 Bounded Fixed capacity Good when resources an issue
Unbounded
Art of Multiprocessor Programming 8 8 Unbounded Unlimited capacity Often more convenient
Blocking
Art of Multiprocessor Programming 9 Blocking zzz … Block on attempt to remove from empty stack or queue
Blocking
Art of Multiprocessor Programming 10 Blocking zzz … Block on attempt to add to full bounded stack or queue
Non-Blocking
Art of Multiprocessor Programming 11 Non-Blocking Ouch! Throw exception on attempt to remove from empty stack or queue
This Lecture
Art of Multiprocessor Programming 12 12 This Lecture Queue Bounded, blocking, lock-based Unbounded, non-blocking, lock-free Stack Unbounded, non-blocking lock-free Elimination-backoff algorithm
Queue: Concurrency
Art of Multiprocessor Programming 13 13 Queue: Concurrency enq(x) y=deq() enq() and deq() work at different ends of the object tail head
Concurrency
Art of Multiprocessor Programming 14 14 Concurrency enq(x) Challenge: what if the queue is empty or full? y=deq() tail head
Bounded Queue
Art of Multiprocessor Programming 15 15 Bounded Queue Sentinel head tail
Bounded Queue
Art of Multiprocessor Programming 16 16 Bounded Queue head tail First actual item
Bounded Queue
Art of Multiprocessor Programming 17 17 Bounded Queue head tail Lock out other deq() calls deqLock
Bounded Queue
Art of Multiprocessor Programming 18 18 Bounded Queue head tail Lock out other enq() calls deqLock enqLock
Not Done Yet
Art of Multiprocessor Programming 19 19 Not Done Yet head tail deqLock enqLock Need to tell whether queue is full or empty
Not Done Yet
Art of Multiprocessor Programming 20 20 Not Done Yet head tail deqLock enqLock Max size is 8 items size 1
Not Done Yet
Art of Multiprocessor Programming 21 21 Not Done Yet head tail deqLock enqLock Incremented by enq() Decremented by deq() size 1
Enqueuer
Art of Multiprocessor Programming 22 22 Enqueuer head tail deqLock enqLock size 1 Lock enqLock
Enqueuer
Art of Multiprocessor Programming 23 23 Enqueuer head tail deqLock enqLock size 1 Read size OK
Enqueuer
Art of Multiprocessor Programming 24 24 Enqueuer head tail deqLock enqLock size 1 No need to lock tail
Enqueuer
Art of Multiprocessor Programming 25 25 Enqueuer head tail deqLock enqLock size 1 Enqueue Node
Enqueuer
Art of Multiprocessor Programming 26 26 Enqueuer head tail deqLock enqLock size 1 2 getAndincrement()
Enqueuer
Art of Multiprocessor Programming 27 27 Enqueuer head tail deqLock enqLock size 8 Release lock 2
Enqueuer
Art of Multiprocessor Programming 28 28 Enqueuer head tail deqLock enqLock size 2 If queue was empty, notify waiting dequeuers
Unsuccesful Enqueuer
Art of Multiprocessor Programming 29 29 Unsuccesful Enqueuer head tail deqLock enqLock size 8 Uh-oh Read size
Dequeuer
Art of Multiprocessor Programming 30 30 Dequeuer head tail deqLock enqLock size 2 Lock deqLock
Dequeuer
Art of Multiprocessor Programming 31 31 Dequeuer head tail deqLock enqLock size 2 Read sentinel’s next field OK
Dequeuer
Art of Multiprocessor Programming 32 32 Dequeuer head tail deqLock enqLock size 2 Read value
Dequeuer
Art of Multiprocessor Programming 33 33 Dequeuer head tail deqLock enqLock size 2 Make first Node new sentinel
Dequeuer
Art of Multiprocessor Programming 34 34 Dequeuer head tail deqLock enqLock size 1 Decrement size
Dequeuer
Art of Multiprocessor Programming 35 35 Dequeuer head tail deqLock enqLock size 1 Release deqLock
Unsuccesful Dequeuer
Art of Multiprocessor Programming 36 36 Unsuccesful Dequeuer head tail deqLock enqLock size 0 Read sentinel’s next field uh-oh
Bounded Queue
Art of Multiprocessor Programming 37 37 Bounded Queue public class BoundedQueue<T> { ReentrantLock enqLock, deqLock; Condition notEmptyCondition, notFullCondition; AtomicInteger size; Node head; Node tail; int capacity; enqLock = new ReentrantLock(); notFullCondition = enqLock.newCondition(); deqLock = new ReentrantLock(); notEmptyCondition = deqLock.newCondition(); }
Bounded Queue
Art of Multiprocessor Programming 38 38 Bounded Queue public class BoundedQueue<T> { ReentrantLock enqLock, deqLock; Condition notEmptyCondition, notFullCondition; AtomicInteger size; Node head; Node tail; int capacity; enqLock = new ReentrantLock(); notFullCondition = enqLock.newCondition(); deqLock = new ReentrantLock(); notEmptyCondition = deqLock.newCondition(); } enq & deq locks
Digression: Monitor Locks
Art of Multiprocessor Programming 39 39 Digression: Monitor Locks Java synchronized objects and ReentrantLocks are monitors Allow blocking on a condition rather than spinning Threads: acquire and release lock wait on a condition
The Java Lock Interface
Art of Multiprocessor Programming 40 40 public interface Lock { void lock(); void lockInterruptibly() throws InterruptedException; boolean tryLock(); boolean tryLock(long time, TimeUnit unit); Condition newCondition(); void unlock; } The Java Lock Interface Acquire lock
The Java Lock Interface
Art of Multiprocessor Programming 41 41 public interface Lock { void lock(); void lockInterruptibly() throws InterruptedException; boolean tryLock(); boolean tryLock(long time, TimeUnit unit); Condition newCondition(); void unlock; } The Java Lock Interface Release lock
The Java Lock Interface
Art of Multiprocessor Programming 42 42 public interface Lock { void lock(); void lockInterruptibly() throws InterruptedException; boolean tryLock(); boolean tryLock( long time, TimeUnit unit); Condition newCondition(); void unlock; } The Java Lock Interface Try for lock, but not too hard
The Java Lock Interface
Art of Multiprocessor Programming 43 43 public interface Lock { void lock(); void lockInterruptibly() throws InterruptedException; boolean tryLock(); boolean tryLock(long time, TimeUnit unit); Condition newCondition(); void unlock; } The Java Lock Interface Create condition to wait on
The Java Lock Interface
Art of Multiprocessor Programming 44 44 The Java Lock Interface public interface Lock { void lock(); void lockInterruptibly() throws InterruptedException; boolean tryLock(); boolean tryLock(long time, TimeUnit unit); Condition newCondition(); void unlock; } Never mind what this method does
Lock Conditions
Art of Multiprocessor Programming 45 45 Lock Conditions public interface Condition { void await(); boolean await( long time, TimeUnit unit); void signal(); void signalAll(); }
Lock Conditions
Art of Multiprocessor Programming 46 46 public interface Condition { void await(); boolean await( long time, TimeUnit unit); void signal(); void signalAll(); } Lock Conditions Release lock and wait on condition
Lock Conditions
Art of Multiprocessor Programming 47 47 public interface Condition { void await(); boolean await(long time, TimeUnit unit); void signal(); void signalAll(); } Lock Conditions Wake up one waiting thread
Lock Conditions
Art of Multiprocessor Programming 48 48 public interface Condition { void await(); boolean await(long time, TimeUnit unit); void signal(); void signalAll(); } Lock Conditions Wake up all waiting threads
Await
Art of Multiprocessor Programming 49 49 Await Releases lock associated with q Sleeps (gives up processor) Awakens (resumes running) Reacquires lock & returns q.await()
Signal
Art of Multiprocessor Programming 50 50 Signal Awakens one waiting thread Which will reacquire lock q.signal();
Signal All
Art of Multiprocessor Programming 51 51 Signal All Awakens all waiting threads Which will each reacquire lock q.signalAll();
A Monitor Lock
Art of Multiprocessor Programming 52 52 A Monitor Lock Critical Section waiting room lock () unlock ()
Unsuccessful Deq
Art of Multiprocessor Programming 53 53 Unsuccessful Deq Critical Section waiting room lock () await() deq () Oh no, empty !
Another One
Art of Multiprocessor Programming 54 54 Another One Critical Section waiting room lock () await() deq () Oh no, empty !
Enqueuer to the Rescue
Art of Multiprocessor Programming 55 55 Enqueuer to the Rescue Critical Section waiting room lock () signalAll () enq ( ) unlock () Yawn! Yawn!
Monitor Signalling
Art of Multiprocessor Programming 56 56 Yawn! Monitor Signalling Critical Section waiting room Yawn! Awakened thread might still lose lock to outside contender…
Dequeuers Signalled
Art of Multiprocessor Programming 57 57 Dequeuers Signalled Critical Section waiting room Found it Yawn!
Dequeuers Signaled
Art of Multiprocessor Programming 58 58 Yawn! Dequeuers Signaled Critical Section waiting room Still empty!
Dollar Short + Day Late
Art of Multiprocessor Programming 59 59 Dollar Short + Day Late Critical Section waiting room
Java Synchronized Methods
Art of Multiprocessor Programming 60 60 public class Queue<T> { int head = 0, tail = 0; T[QSIZE] items; public synchronized T deq() { while (tail – head == 0) wait(); T result = items[head % QSIZE]; head++; notifyAll(); return result; } }} Java Synchronized Methods
Java Synchronized Methods
Art of Multiprocessor Programming 61 61 public class Queue<T> { int head = 0, tail = 0; T[QSIZE] items; public synchronized T deq() { while (tail – head == 0) wait(); T result = items[head % QSIZE]; head++; notifyAll(); return result; } }} Java Synchronized Methods Each object has an implicit lock with an implicit condition
Java Synchronized Methods
Art of Multiprocessor Programming 62 62 public class Queue<T> { int head = 0, tail = 0; T[QSIZE] items; public synchronized T deq() { while (tail – head == 0) wait(); T result = items[head % QSIZE]; head++; notifyAll(); return result; } }} Java Synchronized Methods Lock on entry, unlock on return
Java Synchronized Methods
Art of Multiprocessor Programming 63 63 public class Queue<T> { int head = 0, tail = 0; T[QSIZE] items; public synchronized T deq() { while (tail – head == 0) wait(); T result = items[head % QSIZE]; head++; this.notifyAll(); return result; } }} Java Synchronized Methods Wait on implicit condition
Java Synchronized Methods
Art of Multiprocessor Programming 64 64 public class Queue<T> { int head = 0, tail = 0; T[QSIZE] items; public synchronized T deq() { while (tail – head == 0) this.wait(); T result = items[head % QSIZE]; head++; notifyAll(); return result; } }} Java Synchronized Methods Signal all threads waiting on condition
(Pop!) The Bounded Queue
Art of Multiprocessor Programming 65 65 (Pop!) The Bounded Queue public class BoundedQueue<T> { ReentrantLock enqLock, deqLock; Condition notEmptyCondition, notFullCondition; AtomicInteger size; Node head; Node tail; int capacity; enqLock = new ReentrantLock(); notFullCondition = enqLock.newCondition(); deqLock = new ReentrantLock(); notEmptyCondition = deqLock.newCondition(); }
Bounded Queue Fields
Art of Multiprocessor Programming 66 66 Bounded Queue Fields public class BoundedQueue<T> { ReentrantLock enqLock, deqLock; Condition notEmptyCondition, notFullCondition; AtomicInteger size; Node head; Node tail; int capacity; enqLock = new ReentrantLock(); notFullCondition = enqLock.newCondition(); deqLock = new ReentrantLock(); notEmptyCondition = deqLock.newCondition(); } Enq & deq locks
Bounded Queue Fields
Art of Multiprocessor Programming 67 67 Bounded Queue Fields public class BoundedQueue<T> { ReentrantLock enqLock, deqLock; Condition notEmptyCondition, notFullCondition; AtomicInteger size; Node head; Node tail; int capacity; enqLock = new ReentrantLock(); notFullCondition = enqLock.newCondition(); deqLock = new ReentrantLock(); notEmptyCondition = deqLock.newCondition(); } Enq lock’s associated condition
Bounded Queue Fields
Art of Multiprocessor Programming 68 68 Bounded Queue Fields public class BoundedQueue<T> { ReentrantLock enqLock, deqLock; Condition notEmptyCondition, notFullCondition; AtomicInteger size; Node head; Node tail; int capacity; enqLock = new ReentrantLock(); notFullCondition = enqLock.newCondition(); deqLock = new ReentrantLock(); notEmptyCondition = deqLock.newCondition(); } size : 0 to capacity
Bounded Queue Fields
Art of Multiprocessor Programming 69 69 Bounded Queue Fields public class BoundedQueue<T> { ReentrantLock enqLock, deqLock; Condition notEmptyCondition, notFullCondition; AtomicInteger size; Node head; Node tail; int capacity; enqLock = new ReentrantLock(); notFullCondition = enqLock.newCondition(); deqLock = new ReentrantLock(); notEmptyCondition = deqLock.newCondition(); } Head and Tail
Enq Method Part One
Art of Multiprocessor Programming 70 70 Enq Method Part One public void enq(T x) { boolean mustWakeDequeuers = false ; enqLock.lock(); try { while (size.get() == Capacity) notFullCondition.await(); Node e = new Node(x); tail.next = e; tail = tail.next; if (size.getAndIncrement() == 0) mustWakeDequeuers = true ; } finally { enqLock.unlock(); } }
Enq Method Part One
Art of Multiprocessor Programming 71 71 public void enq(T x) { boolean mustWakeDequeuers = false; enqLock.lock(); try { while (size.get() == capacity) notFullCondition.await(); Node e = new Node(x); tail.next = e; tail = tail.next; if (size.getAndIncrement() == 0) mustWakeDequeuers = true; } finally { enqLock.unlock(); } } Enq Method Part One Lock and unlock enq lock
Enq Method Part One
Art of Multiprocessor Programming 72 72 public void enq(T x) { boolean mustWakeDequeuers = false; enqLock.lock(); try { while (size.get() == capacity) notFullCondition.await(); Node e = new Node(x); tail.next = e; tail = tail.next; if (size.getAndIncrement() == 0) mustWakeDequeuers = true; } finally { enqLock.unlock(); } } Enq Method Part One Wait while queue is full
Enq Method Part One
Art of Multiprocessor Programming 73 73 public void enq(T x) { boolean mustWakeDequeuers = false; enqLock.lock(); try { while (size.get() == capacity) notFullCondition.await(); Node e = new Node(x); tail.next = e; tail = tail.next; if (size.getAndIncrement() == 0) mustWakeDequeuers = true; } finally { enqLock.unlock(); } } Enq Method Part One when await() returns, you might still fail the test !
Be Afraid
Art of Multiprocessor Programming 74 74 public void enq(T x) { boolean mustWakeDequeuers = false; enqLock.lock(); try { while (size.get() == capacity) notFullCondition.await(); Node e = new Node(x); tail.next = e; tail = tail.next; if (size.getAndIncrement() == 0) mustWakeDequeuers = true; } finally { enqLock.unlock(); } } Be Afraid After the loop: how do we know the queue won’t become full again?
Enq Method Part One
Art of Multiprocessor Programming 75 75 public void enq(T x) { boolean mustWakeDequeuers = false; enqLock.lock(); try { while (size.get() == capacity) notFullCondition.await(); Node e = new Node(x); tail.next = e; tail = tail.next; if (size.getAndIncrement() == 0) mustWakeDequeuers = true; } finally { enqLock.unlock(); } } Enq Method Part One Add new node
Enq Method Part One
Art of Multiprocessor Programming 76 76 public void enq(T x) { boolean mustWakeDequeuers = false; enqLock.lock(); try { while (size.get() == capacity) notFullCondition.await(); Node e = new Node(x); tail.next = e; tail = tail.next; if (size.getAndIncrement() == 0) mustWakeDequeuers = true ; } finally { enqLock.unlock(); } } Enq Method Part One If queue was empty, wake frustrated dequeuers
Beware Lost Wake-Ups
Art of Multiprocessor Programming 77 77 Beware Lost Wake-Ups Critical Section waiting room lock () Queue empty so signal () enq ( ) unlock () Yawn!
Lost Wake-Up
Art of Multiprocessor Programming 78 78 Lost Wake-Up Critical Section waiting room lock () enq ( ) unlock () Yawn! Queue not empty so no need to signal
Lost Wake-Up
Art of Multiprocessor Programming 79 79 Lost Wake-Up Critical Section waiting room Yawn!
Lost Wake-Up
Art of Multiprocessor Programming 80 80 Lost Wake-Up Critical Section waiting room Found it
What’s Wrong Here?
Art of Multiprocessor Programming 81 81 What’s Wrong Here? Critical Section waiting room Still waiting ….!
Solution to Lost Wakeup
Art of Multiprocessor Programming 82 Solution to Lost Wakeup Always use signalAll() and notifyAll() Not signal() and notify() 82
Enq Method Part Deux
Art of Multiprocessor Programming 83 83 Enq Method Part Deux public void enq(T x) { if (mustWakeDequeuers) { deqLock.lock(); try { notEmptyCondition.signalAll(); } finally { deqLock.unlock(); } } }
Enq Method Part Deux
Art of Multiprocessor Programming 84 84 Enq Method Part Deux public void enq(T x) { if (mustWakeDequeuers) { deqLock.lock(); try { notEmptyCondition.signalAll(); } finally { deqLock.unlock(); } } } Are there dequeuers to be signaled?
Enq Method Part Deux
Art of Multiprocessor Programming 85 85 public void enq(T x) { if (mustWakeDequeuers) { deqLock.lock(); try { notEmptyCondition.signalAll(); } finally { deqLock.unlock(); } } } Enq Method Part Deux Lock and unlock deq lock
Enq Method Part Deux
Art of Multiprocessor Programming 86 86 public void enq(T x) { if (mustWakeDequeuers) { deqLock.lock(); try { notEmptyCondition.signalAll(); } finally { deqLock.unlock(); } } } Enq Method Part Deux Signal dequeuers that queue is no longer empty
The Enq() & Deq() Methods
Art of Multiprocessor Programming 87 87 The Enq() & Deq() Methods Share no locks That’s good But do share an atomic counter Accessed on every method call That’s not so good Can we alleviate this bottleneck?
Split the Counter
Art of Multiprocessor Programming 88 88 Split the Counter The enq() method Increments only Cares only if value is capacity The deq() method Decrements only Cares only if value is zero
Split Counter
Art of Multiprocessor Programming 89 89 Split Counter Enqueuer increments enqSize Dequeuer decrements deqSize When enqueuer runs out Locks deqLock computes size = enqSize - DeqSize Intermittent synchronization Not with each method call Need both locks! (careful …)
A Lock-Free Queue
Art of Multiprocessor Programming 90 90 A Lock-Free Queue Sentinel head tail
Compare and Set
Art of Multiprocessor Programming 91 91 Compare and Set CAS
Enqueue
Art of Multiprocessor Programming 92 92 Enqueue head tail enq ( )
Enqueue
Art of Multiprocessor Programming 93 93 Enqueue head tail
Logical Enqueue
Art of Multiprocessor Programming 94 94 Logical Enqueue head tail CAS
Physical Enqueue
Art of Multiprocessor Programming 95 95 Physical Enqueue head tail CAS
Enqueue
Art of Multiprocessor Programming 96 96 Enqueue These two steps are not atomic The tail field refers to either Actual last Node (good) Penultimate Node (not so good) Be prepared!
Enqueue
Art of Multiprocessor Programming 97 97 Enqueue What do you do if you find A trailing tail ? Stop and help fix it If tail node has non- null next field CAS the queue’s tail field to tail.next As in the universal construction
When CASs Fail
Art of Multiprocessor Programming 98 98 When CASs Fail During logical enqueue Abandon hope, restart Still lock-free (why?) During physical enqueue Ignore it (why?)
Dequeuer
Art of Multiprocessor Programming 99 99 Dequeuer head tail Read value