Concurrent Stacks

1.

‫מרצה‪ :‬יהודה אפק‬
‫מגיש‪ :‬ערן שרגיאן‬

2.

Outline
Quick reminder of the Stack structure.
The Unbounded Lock-Free Stack.
The Elimination Backoff Stack.

3.

Concurrent Stack
The Stack<T> class is a collection of items (of type
T) that provides the following methods:
push(x)
pop()
Satisfying the Last-In-First-Out (LIFO) property:
The last item pushed is the first popped.

4.

Empty Stack
Top

5.

Push
Top

6.

Push
Top
CAS

7.

Push
Top

8.

Push
Top

9.

Push
Top

10.

Push
Top
CAS

11.

Push
Top

12.

Pop
Top

13.

Pop
Top
CAS

14.

Pop
Top
CAS
mine!

15.

Pop
Top
CAS

16.

Pop
Top

17.

The LockfreeStack class
The lock-free stack is a linked list, where the top
field points to the first node (or null if the stack is
empty).
A pop() call uses compareAndSet() to try to remove
the first node from the stack.
A push() call uses compareAndSet() to try to insert a
new node into the top of the stack.

18.

public class LockFreeStack {
private AtomicReference top = new AtomicReference(null);
static final int MIN_DELAY = …;
static final int MAX_DELAY = …;
Backoff backoff = new Backoff(MIN_DELAY, MAX_DELAY);
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 backoff.backoff();
}
}

19.

public boolean 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();
}

20.

Lock-free Stack
Good
No locking
Bad
huge contention at top
No parallelism

21.

Elimination-Backoff Stack
The LockFreeStack implementation scales poorly, not so
much because the stack’s top field is a source of contention,
but primarily because it is a sequential bottleneck.
Ways to solve it :
exponential backoff (reduces contention but does not solve the
bottleneck problem).
elimination backoff

22.

Observation
Push(
linearizable stack
)
Pop()
Yes!
After an equal number
of pushes and pops,
stack stays the same

23.

Idea: Elimination Array
Push(
)
Pick at
random
stack
Pop()
Pick at
random
Elimination
Array

24.

Push Collides With Pop
continue
Push(
stack
)
Pop()
continue
Yes!
No need to
access stack

25.

No Collision
Push( )
Pop()
stack
If pushes collide
no collision,
orIfpops
collide
accessstack
stack
access

26.

Elimination-Backoff Stack
A union of the LockFreeStack class with the
elimination array
Access Lock-free stack,
If uncontended, apply operation
if contended, back off to elimination array and attempt elimination

27.

Elimination-Backoff Stack
If CAS fails, back off
Push( )
Pop()
CAS
Top

28.

Dynamic Range and Delay
Push( )
Pick random range and
max time to wait for
collision based on level of
contention encountered

29.

Linearizability
The combined data structure, array, and shared
stack, is linearizable because the shared stack is
linearizable, and the eliminated calls can be ordered
as if they happened at the point in which they
exchanged values.
Un-eliminated calls
linearized as before
Eliminated calls:
linearize pop() immediately after matching push()
Combination is a linearizable stack

30.

Un-Eliminated Linearizability
pop(v1)
push(v1)
time
time

31.

Eliminated Linearizability
Collision
Point
pop(v1)
push(v1)
pop(v2)
push(v2)
time
time
Red calls are
eliminated

32.

Backoff Has Dual Effect
Elimination introduces parallelism
Backoff onto array cuts contention on lock-free
stack
Elimination in array cuts down total number of
threads ever accessing lock-free stack

33.

Elimination Array
public class EliminationArray {
private static final int duration = ...;
private static final int timeUnit = ...;
Exchanger<T>[] exchanger;
public EliminationArray(int capacity) {
exchanger = new Exchanger[capacity];
for (int i = 0; i < capacity; i++)
exchanger[i] = new Exchanger<T>();
…
}
…
}

34.

A Lock-Free Exchanger
public class Exchanger<T> {
AtomicStampedReference<T> slot
= new AtomicStampedReference<T>(null, 0);

35.

Atomic Stamped Reference
Reference
address
S
Stamp

36.

Exchanger Status
enum Status {EMPTY, WAITING, BUSY};

37.

Lock-free Exchanger
EMPTY

38.

Lock-free Exchanger
CAS
EMPTY

39.

Lock-free Exchanger
WAITING

40.

Lock-free Exchanger
In search of
partner …
WAITING

41.

Lock-free Exchanger
Try to
exchange item
and set state
to BUSY
Still waiting …
Slot
CAS
WAITING

42.

Lock-free Exchanger
Partner showed
up, take item and
reset to EMPTY
Slot
BUSY
item
stamp/state

43.

Lock-free Exchanger
Partner showed
up, take item and
reset to EMPTY
Slot
BUSY
EMPTY
item
stamp/state

44.

The Exchanger Slot
Exchanger is lock-free
Because the only way an exchange can fail is if
others repeatedly succeeded or no-one showed up

45.

Elimination Array
public class EliminationArray {
…
public T visit(T value, int Range) throws TimeoutException {
int slot = random.nextInt(Range);
int nanodur = convertToNanos(duration, timeUnit));
return (exchanger[slot].exchange(value, nanodur)
}}

46.

Elimination Stack Push
public void push(T value) {
...
while (true) {
if (tryPush(node)) {
return;
} else try {
T otherValue =
eliminationArray.visit(value,policy.Range);
if (otherValue == null) {
return;
}
}

47.

Elimination Stack Pop
public T pop() {
...
while (true) {
if (tryPop()) {
return returnNode.value;
} else
try {
T otherValue =
eliminationArray.visit(null,policy.Range);
if (otherValue != null) {
return otherValue;
}
}
}}

48.

Summary
Quick reminder of the Stack structure.
The Unbounded Lock-Free Stack.
The Elimination Backoff Stack.

49.

‫תודה רבה על ההקשבה‬