Lecture 4:
Concurrent Queues and Stacks
Companion slides for
The Art of Multiprocessor Programming
by Maurice Herlihy & Nir Shavit With modifications by Lamont Samuels
pool
• Data Structure similar to Set
– Does not necessarily provide contains() method – Allows the same item to appear more than once – get() and set()
public interface Pool
void put(T item);
T get();
}
Art of Multiprocessor Programming© 2 Herlihy-Shavit 2007
Queues & Stacks
• Both: pool of items
• Queue
– enq() & deq()
– First-in-first-out (FIFO) order
• Stack
– push() & pop()
– Last-in-first-out (LIFO) order
Art of Multiprocessor Programming© 3 Herlihy-Shavit 2007
Bounded vs Unbounded
• Bounded
– Fixed capacity
– Good when resources an issue
• Unbounded
– Holds any number of objects
Art of Multiprocessor Programming© 4 Herlihy-Shavit 2007
Blocking vs Non-Blocking
• Problem cases:
– Removing from empty pool
– Adding to full (bounded) pool
• Blocking
– Caller waits until state changes
• Non-Blocking
– Method throws exception
Art of Multiprocessor Programming© 5 Herlihy-Shavit 2007
enq(x)
Queue: Concurrency
y=deq()
tail head
enq() and deq() work at different ends of the object
Art of Multiprocessor Programming© 6 Herlihy-Shavit 2007
enq(x)
Concurrency
y=deq()
Challenge: what if the queue is empty or full?
Art of Multiprocessor Programming© 7 Herlihy-Shavit 2007
head
tail
lock
• enqLock/deqLock
– Atmostoneenqueuer/dequeueratatimecanmanipulate the queue’s fields
• Two locks
– Enqueuerdoesnotlockoutdequeuer – viceversa
• Association
– enqLockassociatedwithnotFullCondition
– deqLockassociatedwithnotEmptyCondition
Art of Multiprocessor Programming© 8 Herlihy-Shavit 2007
enqueue
2. Reads the size field
3. If full, enqueuer must wait until dequeuer makes room
4. enqueuer waits on notFullCondition field, releasing enqLock temporarily, and blocking until that condition is signaled.
5. Each time the thread awakens, it checks whether there is a room, and if not, goes back to sleep
6. Insert new item into tail
7. Release enqLock
8. If queue was empty, notify/signal waiting dequeuers
Art of Multiprocessor Programming© 9 Herlihy-Shavit 2007
1. Acquires enqLock
dequeue
3. If empty, dequeuer must wait until item is enqueued
4. dequeuer waits on notEmptyCondition field, releasing deqLock temporarily, and blocking until that condition is signaled.
5. Each time the thread awakens, it checks whether item was enqueued, and if not, goes back to sleep
6. Assigne the value of head’s next node to “result” and reset head to head’s next node
7. Release deqLock
8. If queue was full, notify/signal waiting enqueuers
9. Return “result”
Art of Multiprocessor Programming© 10 Herlihy-Shavit 2007
1. Acquires deqLock
2. Reads the size field
Bounded Queue
head
tail
Art of Multiprocessor Programming 113
Sentinel
Bounded Queue
head
tail
First actual item
Art of Multiprocessor Programming 142
Bounded Queue
head
tail
deqLock
Lock out other deq() calls
Art of Multiprocessor Programming 135
Bounded Queue
head tail deqLock
enqLock
Lock out other enq() calls
Art of Multiprocessor Programming 146
Not Done Yet
head tail deqLock
enqLock
Art of Multiprocessor Programming 157
Need to tell whether queue is full or empty
Not Done Yet
head tail deqLock
enqLock size
1
Max size is 8 items Art of Multiprocessor Programming 168
Not Done Yet
head tail deqLock
enqLock size
1
Incremented by enq() Decremented by deq()
Art of Multiprocessor Programming 179
Enqueuer
head tail deqLock
enqLock size
1
Lock enqLock
Art of Multiprocessor Programming 1280
Enqueuer
head tail deqLock
enqLock size
1
Read size
OK Art of Multiprocessor Programming 1291
Enqueuer
head tail deqLock
enqLock size
No need to lock tail
1
Art of Multiprocessor Programming 202
Enqueuer
head tail deqLock
enqLock size
1
Enqueue Node
Art of Multiprocessor Programming 213
Enqueuer
head tail deqLock
enqLock size
21
getAndincrement()
Art of Multiprocessor Programming 224
Enqueuer
head tail deqLock
enqLock
size
Release lock
8
2
Art of Multiprocessor Programming 235
Enqueuer
head tail deqLock
enqLock
size
2
If queue was empty, notify waiting dequeuers
Art of Multiprocessor Programming 246
Unsuccesful Enqueuer
head tail deqLock
enqLock
size
8
…
Read size
Uh-oh
Art of Multiprocessor Programming 257
Dequeuer
head tail deqLock
enqLock size
2
Lock deqLock
Art of Multiprocessor Programming 268
Dequeuer
head tail deqLock
enqLock size
2
Read sentinel’s next field
OK
Art of Multiprocessor Programming 279
Dequeuer
head tail deqLock
enqLock size
Read value
2
Art of Multiprocessor Programming 3208
Dequeuer
Make first Node
new sentinel
head tail deqLock
enqLock size
2
Art of Multiprocessor Programming 3219
Dequeuer
head tail deqLock
enqLock size
1
Decrement size
Art of Multiprocessor Programming 302
Dequeuer
head tail deqLock
enqLock size
1
Release deqLock
Art of Multiprocessor Programming 313
Unbounded Lock-Free Queue (Nonblocking)
• Unbounded
– No need to count the number of items
• Lock-free
– Use AtomicReference
• An object reference that may be updated atomically.
– boolean compareAndSet(V expect, V update)
• Atomically sets the value to the given updated value if the current value == the expected value.
• Nonblocking
– No need to provide conditions on which to wait 32
A Lock-Free Queue
head
tail
Art of Multiprocessor Programming 4334
Sentinel
Enqueue
head tail
Enq( )
Art of Multiprocessor Programming 4354
Enqueue
head tail
Art of Multiprocessor Programming 4356
Logical Enqueue
head tail
CAS
Art of Multiprocessor Programming 4367
Physical Enqueue
head tail
CAS
Art of Multiprocessor Programming 4378
Enqueue
• These two steps are not atomic
• The tail field refers to either – Actual last Node (good)
– Penultimate Node (not so good)
• Be prepared!
• (For you to think about) How could you fix that?
Art of Multiprocessor Programming 4389
When CASs Fail
• During logical enqueue – Abandon hope, restart – Still lock-free (why?)
• During physical enqueue – Ignore it (why?)
Art of Multiprocessor Programming 5319
Dequeuer
head tail
Read value
Art of Multiprocessor Programming 5402
Dequeuer
Make first Node
new sentinel
CAS
head tail
Art of Multiprocessor Programming 5413
Concurrent Stack
• Methods
– push(x) – pop()
• Last-in, First-out (LIFO) order • Lock-Free!
Art of Multiprocessor Programming 5426
Empty Stack
Top
Art of Multiprocessor Programming 4573
Push
Top
Art of Multiprocessor Programming 5484
Push
CAS
Top
Art of Multiprocessor Programming 5459
Push
Top
Art of Multiprocessor Programming 6406
Push
Top
Art of Multiprocessor Programming 6417
Push
Top
Art of Multiprocessor Programming 6428
Push
CAS
Top
Art of Multiprocessor Programming 6493
Push
Top
Art of Multiprocessor Programming 6540
Pop
Top
Art of Multiprocessor Programming 6515
Pop
CAS
Top
Art of Multiprocessor Programming 6526
Pop
CAS
Top
mine!
Art of Multiprocessor Programming 6537
Pop
CAS
Top
Art of Multiprocessor Programming 6548
Pop
Top
Art of Multiprocessor Programming 6595
Lock-free Stack
public class LockFreeStack { private AtomicReference top =
new AtomicReference(null); public boolean tryPush(Node node){
Node oldTop = top.get();
node.next = oldTop; return(top.compareAndSet(oldTop, node))
}
public void push(T value) { Node node = new Node(value);
while (true) {
if (tryPush(node)) {
return;
} else backoffA.rbtaofcMkoulftifpr(o)c;essor Programming 7506
}}
Lock-free Stack
public class LockFreeStack {
private AtomicReference top = new
AtomicReference(null);
public Boolean tryPush(Node node){
Node oldTop = top.get();
node.next = oldTop; return(top.compareAndSet(oldTop, node))
}
public void push(T value) {
Node node = new Node(value); while (true) {
}}
tryPush attempts to push a node
if (tryPush(node)) {
return;
} else backoffA.rbtaofcMkoulftifpr(o)cessor Programming 7517
Lock-free Stack
public class LockFreeStack {
private AtomicReference top = new
AtomicReference(null);
public boolean tryPush(Node node){
Node oldTop = top.get();
node.next = oldTop; return(top.compareAndSet(oldTop, node))
}
public void push(T value) {
Node node = new Node(value);
}}
while (true) {
if (tryPush(node)) {
Read top value
return;
} else backoffA.rbtaofcMkoulftifpr(o)cessor Programming 7528
Lock-free Stack
public class LockFreeStack {
private AtomicReference top = new
AtomicReference(null);
public boolean tryPush(Node node){
Node oldTop = top.get();
node.next = oldTop;
return(top.compareAndSet(oldTop, node)) }
public void push(T value) {
Node node = new Node(value); while (true) {
}}
current top will be new node’s successor
if (tryPush(node)) {
return;
} else backoffA.rbtaofcMkoulftifpr(o)cessor Programming 7539
Lock-free Stack
public class LockFreeStack {
private AtomicReference top = new
AtomicReference(null);
public boolean tryPush(Node node){
Node oldTop = top.get();
node.next = oldTop;
return(top.compareAndSet(oldTop, node))
}
public void push(T value) {
Node node = new Node(value); while (true) {
}}
if (tryPush(node)) {
Try to swing top, return success or failure
return;
} else backoffA.rbtaofcMkoulftifpr(o)cessor Programming 6740
Lock-free Stack
public class LockFreeStack {
private AtomicReference top = new
AtomicReference(null);
public boolean tryPush(Node node){
Node oldTop = top.get();
node.next = oldTop; return(top.compareAndSet(oldTop, node))
}
public void push(T value) {
Node node = new Node(value); while (true) {
if (tryPush(node)) { Push calls tryPush return;
} else backoffA.rbtaofcMkoulftifpr(o)cessor Programming 6715 }}
Lock-free Stack
public class LockFreeStack {
private AtomicReference top = new
AtomicReference(null);
public boolean tryPush(Node node){
Node oldTop = top.get();
node.next = oldTop; return(top.compareAndSet(oldTop, node))
}
public void push(T value) {
Node node = new Node(value);
}}
while (true) {
if (tryPush(node)) {
return; Create new node
} else backoffA.rbtaofcMkoulftifpr(o)cessor Programming 7662
Lock-free Stack
public class LockFreeStack {
private AtomicReference top = new
AtomicReference(null);
public boolean tryPush(Node node){
Node oldTop = top.get(); node.next = oldTop;
If tryPush() fails,
back off before retrying
return(top.compareAndSet(oldTop, node)) }
public void push(T value) {
Node node = new Node(value); while (true) {
if (tryPush(node)) { return;
} else backoffA.rbtaofcMkoulftifpr(o)cessor Programming 7637 }}
Unbounded Lock-Free Stack
protected boolean tryPush(Node node)
{
Node oldTop = top.get();
node.next = oldTop;
return (top.compareAndSet(oldTop, node));
}
public void push( T value )
{
Node node = new Node( value );
while (true) {
if (tryPush(node)) { return; }
else { backoff.backoff( ); }
}
}
protected Node tryPop( ) throws EmptyException
{
Node oldTop = top.get();
if ( oldTop == null ) {
throw new EmptyException( );
}
Node newTop = oldTop.next;
if ( top.compareAndSet( oldTop, newTop ) ) {
return oldTop;
} else { return null; }
}
public T pop() throws EmptyException {
while (true) {
Node returnNode = tryPop( );
if ( returnNode != null ) {
return returnNode.value;
} else { backoff.backoff( ); }
} }
64
Lock-free Stack
• Good
– No locking
• Bad
– Without GC, fear ABA
– Without backoff, huge contention at top – In any case, no parallelism
Art of Multiprocessor Programming 7659
Question
• Are stacks inherently sequential?
• Reasons why
– Every pop() call fights for top item
• Reasons why not – Think about it!
Art of Multiprocessor Programming 8660