1 of 261

Linked Lists: Locking, Lock-Free, and Beyond …

Companion slides for

The Art of Multiprocessor Programming

by Maurice Herlihy & Nir Shavit

2 of 261

Art of Multiprocessor Programming

2

Last Lecture: Spin-Locks

CS

Resets lock

upon exit

spin

lock

critical

section

.

3 of 261

Art of Multiprocessor Programming

3

Today: Concurrent Objects

Adding threads should not lower throughput

Contention effects
Mostly fixed by Queue locks

4 of 261

Art of Multiprocessor Programming

4

Today: Concurrent Objects

Adding threads should not lower throughput

Contention effects
Mostly fixed by Queue locks

Should increase throughput

Not possible if inherently sequential
Surprising things are parallelizable

5 of 261

Art of Multiprocessor Programming

5

Coarse-Grained Synchronization

Each method locks the object

Avoid contention using queue locks

6 of 261

Art of Multiprocessor Programming

6

Coarse-Grained Synchronization

Each method locks the object

Avoid contention using queue locks
Easy to reason about

In simple cases

7 of 261

Art of Multiprocessor Programming

7

Coarse-Grained Synchronization

Each method locks the object

Avoid contention using queue locks
Easy to reason about

In simple cases

So, are we done?

8 of 261

Art of Multiprocessor Programming

8

Coarse-Grained Synchronization

Sequential bottleneck

Threads “stand in line”

9 of 261

Art of Multiprocessor Programming

9

Coarse-Grained Synchronization

Sequential bottleneck

Threads “stand in line”

Adding more threads

Does not improve throughput
Struggle to keep it from getting worse

10 of 261

Art of Multiprocessor Programming

10

Coarse-Grained Synchronization

Sequential bottleneck

Threads “stand in line”

Adding more threads

Does not improve throughput
Struggle to keep it from getting worse

So why even use a multiprocessor?

Well, some apps inherently parallel …

11 of 261

Art of Multiprocessor Programming

11

This Lecture

Introduce four “patterns”

Bag of tricks …
Methods that work more than once …

12 of 261

Art of Multiprocessor Programming

12

This Lecture

Introduce four “patterns”

Bag of tricks …
Methods that work more than once …

For highly-concurrent objects

Concurrent access
More threads, more throughput

13 of 261

Art of Multiprocessor Programming

13

First:�Fine-Grained Synchronization

Instead of using a single lock …
Split object into

Independently-synchronized components

Methods conflict when they access

The same component …
At the same time

14 of 261

Art of Multiprocessor Programming

14

Second:�Optimistic Synchronization

Search without locking …
If you find it, lock and check …

OK: we are done
Oops: start over

Evaluation

Usually cheaper than locking, but
Mistakes are expensive

15 of 261

Art of Multiprocessor Programming

15

Third:�Lazy Synchronization

Postpone hard work
Removing components is tricky

Logical removal

Mark component to be deleted

Physical removal

Do what needs to be done

16 of 261

Art of Multiprocessor Programming

16

Fourth:�Lock-Free Synchronization

Don’t use locks at all

Use compareAndSet() & relatives …

Advantages

No Scheduler Assumptions/Support

Disadvantages

Complex
Sometimes high overhead

17 of 261

Art of Multiprocessor Programming

17

Linked List

Illustrate these patterns …
Using a list-based Set

Common application
Building block for other apps

18 of 261

Art of Multiprocessor Programming

18

Set Interface

Unordered collection of items
No duplicates
Methods

add(x) put x in set
remove(x) take x out of set
contains(x) tests if x in set

19 of 261

Art of Multiprocessor Programming

19

List-Based Sets

public interface Set<T> {

public boolean add(T x);

public boolean remove(T x);

public boolean contains(T x);

}

20 of 261

Art of Multiprocessor Programming

20

List-Based Sets

public interface Set<T> {

public boolean add(T x);

public boolean remove(T x);

public boolean contains(T x);

}

Add item to set

21 of 261

Art of Multiprocessor Programming

21

List-Based Sets

public interface Set<T> {

public boolean add(T x);

public boolean remove(T x);

public boolean contains(Tt x);

}

Remove item from set

22 of 261

Art of Multiprocessor Programming

22

List-Based Sets

public interface Set<T> {

public boolean add(T x);

public boolean remove(T x);

public boolean contains(T x);

}

Is item in set?

23 of 261

Art of Multiprocessor Programming

23

List Node

public class Node {

public T item;

public int key;

public Node next;

}

24 of 261

Art of Multiprocessor Programming

24

List Node

public class Node {

public T item;

public int key;

public Node next;

}

item of interest

25 of 261

Art of Multiprocessor Programming

25

List Node

public class Node {

public T item;

public int key;

public Node next;

}

Usually hash code

26 of 261

Art of Multiprocessor Programming

26

List Node

public class Node {

public T item;

public int key;

public Node next;

}

Reference to next node

27 of 261

Art of Multiprocessor Programming

27

The List-Based Set

a

b

c

Sorted with Sentinel nodes

(min & max possible keys)

-∞

+∞

28 of 261

Art of Multiprocessor Programming

28

Reasoning about Concurrent Objects

Invariant

Property that always holds

Established because

True when object is created
Truth preserved by each method

Each step of each method

29 of 261

Art of Multiprocessor Programming

29

Specifically …

Invariants preserved by

add()
remove()
contains()

Most steps are trivial

Usually one step tricky
Often linearization point

30 of 261

Art of Multiprocessor Programming

30

Interference

Invariants make sense only if

methods considered
are the only modifiers

Language encapsulation helps

List nodes not visible outside class

31 of 261

Art of Multiprocessor Programming

31

Interference

Freedom from interference needed even for removed nodes

Some algorithms traverse removed nodes
Careful with malloc() & free()!

Garbage collection helps here

32 of 261

Art of Multiprocessor Programming

32

Abstract Data Types

Concrete representation:

Abstract Type:

{a, b}

a

b

33 of 261

Art of Multiprocessor Programming

33

Abstract Data Types

Meaning of rep given by abstraction map

S( ) = {a,b}

a

b

34 of 261

Art of Multiprocessor Programming

34

Rep Invariant (partly)

Sentinel nodes

tail reachable from head

Sorted
No duplicates

35 of 261

Art of Multiprocessor Programming

35

Abstraction Map

S(head) =

{ x | there exists a such that

a reachable from head and
a.item = x

}

36 of 261

Art of Multiprocessor Programming

36

Sequential List Based Set

a

c

d

a

b

c

Add()

Remove()

37 of 261

Art of Multiprocessor Programming

37

Sequential List Based Set

a

c

d

b

a

b

c

Add()

Remove()

38 of 261

Art of Multiprocessor Programming

38

Coarse-Grained Locking

a

b

d

39 of 261

Art of Multiprocessor Programming

39

Coarse-Grained Locking

a

b

d

c

40 of 261

Art of Multiprocessor Programming

40

honk!

Coarse-Grained Locking

a

b

d

c

Simple but hotspot + bottleneck

honk!

41 of 261

Art of Multiprocessor Programming

41

Coarse-Grained Locking

Easy, same as synchronized methods

“One lock to rule them all …”

Simple, clearly correct

Deserves respect!

Works poorly with contention

Queue locks help
But bottleneck still an issue

42 of 261

Art of Multiprocessor Programming

42

Fine-grained Locking

Requires careful thought

“Do not meddle in the affairs of wizards, for they are subtle and quick to anger”

Split object into pieces

Each piece has own lock
Methods that work on disjoint pieces need not exclude each other

43 of 261

Art of Multiprocessor Programming

43

Hand-over-Hand locking

a

b

c

44 of 261

Art of Multiprocessor Programming

44

Hand-over-Hand locking

a

b

c

45 of 261

Art of Multiprocessor Programming

45

Hand-over-Hand locking

a

b

c

46 of 261

Art of Multiprocessor Programming

46

Hand-over-Hand locking

a

b

c

47 of 261

Art of Multiprocessor Programming

47

Hand-over-Hand locking

a

b

c

48 of 261

Art of Multiprocessor Programming

48

Removing a Node

a

b

c

d

remove(b)

49 of 261

Art of Multiprocessor Programming

49

Removing a Node

a

b

c

d

remove(b)

50 of 261

Art of Multiprocessor Programming

50

Removing a Node

a

b

c

d

remove(b)

51 of 261

Art of Multiprocessor Programming

51

Removing a Node

a

b

c

d

remove(b)

52 of 261

Art of Multiprocessor Programming

52

Removing a Node

a

b

c

d

remove(b)

53 of 261

Art of Multiprocessor Programming

53

Removing a Node

a

c

d

remove(b)

Why hold 2 locks?

54 of 261

Art of Multiprocessor Programming

54

Concurrent Removes

a

b

c

d

remove(c)

remove(b)

55 of 261

Art of Multiprocessor Programming

55

Concurrent Removes

a

b

c

d

remove(b)

remove(c)

56 of 261

Art of Multiprocessor Programming

56

Concurrent Removes

a

b

c

d

remove(b)

remove(c)

57 of 261

Art of Multiprocessor Programming

57

Concurrent Removes

a

b

c

d

remove(b)

remove(c)

58 of 261

Art of Multiprocessor Programming

58

Concurrent Removes

a

b

c

d

remove(b)

remove(c)

59 of 261

Art of Multiprocessor Programming

59

Concurrent Removes

a

b

c

d

remove(b)

remove(c)

60 of 261

Art of Multiprocessor Programming

60

Concurrent Removes

a

b

c

d

remove(b)

remove(c)

61 of 261

Art of Multiprocessor Programming

61

Concurrent Removes

a

b

c

d

remove(b)

remove(c)

62 of 261

Art of Multiprocessor Programming

62

Concurrent Removes

a

b

c

d

remove(b)

remove(c)

63 of 261

Art of Multiprocessor Programming

63

Concurrent Removes

a

b

c

d

remove(b)

remove(c)

64 of 261

Art of Multiprocessor Programming

64

Uh, Oh

a

c

d

remove(b)

remove(c)

65 of 261

Art of Multiprocessor Programming

65

Uh, Oh

a

c

d

Bad news, c not removed

remove(b)

remove(c)

66 of 261

Art of Multiprocessor Programming

66

Problem

To delete node c

Swing node b’s next field to d

Problem is,

Someone deleting b concurrently could

direct a pointer

to c

b

a

c

b

a

c

67 of 261

Art of Multiprocessor Programming

67

Insight

If a node is locked

No one can delete node’s successor

If a thread locks

Node to be deleted
And its predecessor
Then it works

68 of 261

Art of Multiprocessor Programming

68

Hand-Over-Hand Again

a

b

c

d

remove(b)

69 of 261

Art of Multiprocessor Programming

69

Hand-Over-Hand Again

a

b

c

d

remove(b)

70 of 261

Art of Multiprocessor Programming

70

Hand-Over-Hand Again

a

b

c

d

remove(b)

71 of 261

Art of Multiprocessor Programming

71

Hand-Over-Hand Again

a

b

c

d

remove(b)

Found it!

72 of 261

Art of Multiprocessor Programming

72

Hand-Over-Hand Again

a

b

c

d

remove(b)

Found it!

73 of 261

Art of Multiprocessor Programming

73

Hand-Over-Hand Again

a

c

d

remove(b)

74 of 261

Art of Multiprocessor Programming

74

Removing a Node

a

b

c

d

remove(b)

remove(c)

75 of 261

Art of Multiprocessor Programming

75

Removing a Node

a

b

c

d

remove(b)

remove(c)

76 of 261

Art of Multiprocessor Programming

76

Removing a Node

a

b

c

d

remove(b)

remove(c)

77 of 261

Art of Multiprocessor Programming

77

Removing a Node

a

b

c

d

remove(b)

remove(c)

78 of 261

Art of Multiprocessor Programming

78

Removing a Node

a

b

c

d

remove(b)

remove(c)

79 of 261

Art of Multiprocessor Programming

79

Removing a Node

a

b

c

d

remove(b)

remove(c)

80 of 261

Art of Multiprocessor Programming

80

Removing a Node

a

b

c

d

remove(b)

remove(c)

81 of 261

Art of Multiprocessor Programming

81

Removing a Node

a

b

c

d

remove(b)

remove(c)

82 of 261

Art of Multiprocessor Programming

82

Removing a Node

a

b

c

d

Must acquire

Lock for b

remove(c)

83 of 261

Art of Multiprocessor Programming

83

Removing a Node

a

b

c

d

Cannot acquire lock for b

remove(c)

84 of 261

Art of Multiprocessor Programming

84

Removing a Node

a

b

c

d

Wait!

remove(c)

85 of 261

Art of Multiprocessor Programming

85

Removing a Node

a

b

d

Proceed to remove(b)

86 of 261

Art of Multiprocessor Programming

86

Removing a Node

a

b

d

remove(b)

87 of 261

Art of Multiprocessor Programming

87

Removing a Node

a

b

d

remove(b)

88 of 261

Art of Multiprocessor Programming

88

Removing a Node

a

d

remove(b)

89 of 261

Art of Multiprocessor Programming

89

Removing a Node

a

d

90 of 261

Art of Multiprocessor Programming

90

Remove method

public boolean remove(Item item) {

int key = item.hashCode();

Node pred, curr;

try {

…

} finally {

curr.unlock();

pred.unlock();

}}

91 of 261

Art of Multiprocessor Programming

91

Remove method

public boolean remove(Item item) {

int key = item.hashCode();

Node pred, curr;

try {

…

} finally {

curr.unlock();

pred.unlock();

}}

Key used to order node

92 of 261

Art of Multiprocessor Programming

92

Remove method

public boolean remove(Item item) {

int key = item.hashCode();

Node pred, curr;

try {

…

} finally {

currNode.unlock();

predNode.unlock();

}}

Predecessor and current nodes

93 of 261

Art of Multiprocessor Programming

93

Remove method

public boolean remove(Item item) {

int key = item.hashCode();

Node pred, curr;

try {

…

} finally {

curr.unlock();

pred.unlock();

}}

Make sure locks released

94 of 261

Art of Multiprocessor Programming

94

Remove method

public boolean remove(Item item) {

int key = item.hashCode();

Node pred, curr;

try {

…

} finally {

curr.unlock();

pred.unlock();

}}

Everything else

95 of 261

Art of Multiprocessor Programming

95

Remove method

try {

pred = this.head;

pred.lock();

curr = pred.next;

curr.lock();

…

} finally { … }

96 of 261

Art of Multiprocessor Programming

96

Remove method

try {

pred = this.head;

pred.lock();

curr = pred.next;

curr.lock();

…

} finally { … }

lock pred == head

97 of 261

Art of Multiprocessor Programming

97

Remove method

try {

pred = this.head;

pred.lock();

curr = pred.next;

curr.lock();

…

} finally { … }

Lock current

98 of 261

Art of Multiprocessor Programming

98

Remove method

try {

pred = this.head;

pred.lock();

curr = pred.next;

curr.lock();

…

} finally { … }

Traversing list

99 of 261

Art of Multiprocessor Programming

99

Remove: searching

while (curr.key <= key) {

if (item == curr.item) {

pred.next = curr.next;

return true;

}

pred.unlock();

pred = curr;

curr = curr.next;

curr.lock();

}

return false;

100 of 261

Art of Multiprocessor Programming

100

Remove: searching

while (curr.key <= key) {

if (item == curr.item) {

pred.next = curr.next;

return true;

}

pred.unlock();

pred = curr;

curr = curr.next;

curr.lock();

}

return false;

Search key range

101 of 261

Art of Multiprocessor Programming

101

Remove: searching

while (curr.key <= key) {

if (item == curr.item) {

pred.next = curr.next;

return true;

}

pred.unlock();

pred = curr;

curr = curr.next;

curr.lock();

}

return false;

At start of each loop: curr and pred locked

102 of 261

Art of Multiprocessor Programming

102

Remove: searching

while (curr.key <= key) {

if (item == curr.item) {

pred.next = curr.next;

return true;

}

pred.unlock();

pred = curr;

curr = curr.next;

curr.lock();

}

return false;

If item found, remove node

103 of 261

Art of Multiprocessor Programming

103

Remove: searching

while (curr.key <= key) {

if (item == curr.item) {

pred.next = curr.next;

return true;

}

pred.unlock();

pred = curr;

curr = curr.next;

curr.lock();

}

return false;

If node found, remove it

104 of 261

Art of Multiprocessor Programming

104

Remove: searching

while (curr.key <= key) {

if (item == curr.item) {

pred.next = curr.next;

return true;

}

pred.unlock();

pred = curr;

curr = curr.next;

curr.lock();

}

return false;

Unlock predecessor

105 of 261

Art of Multiprocessor Programming

105

Remove: searching

while (curr.key <= key) {

if (item == curr.item) {

pred.next = curr.next;

return true;

}

pred.unlock();

pred = curr;

curr = curr.next;

curr.lock();

}

return false;

Only one node locked!

106 of 261

Art of Multiprocessor Programming

106

Remove: searching

while (curr.key <= key) {

if (item == curr.item) {

pred.next = curr.next;

return true;

}

pred.unlock();

pred = curr;

curr = curr.next;

curr.lock();

}

return false;

demote current

107 of 261

Art of Multiprocessor Programming

107

Remove: searching

while (curr.key <= key) {

if (item == curr.item) {

pred.next = curr.next;

return true;

}

pred.unlock();

pred = currNode;

curr = curr.next;

curr.lock();

}

return false;

Find and lock new current

108 of 261

Art of Multiprocessor Programming

108

Remove: searching

while (curr.key <= key) {

if (item == curr.item) {

pred.next = curr.next;

return true;

}

pred.unlock();

pred = currNode;

curr = curr.next;

curr.lock();

}

return false;

Lock invariant restored

109 of 261

Art of Multiprocessor Programming

109

Remove: searching

while (curr.key <= key) {

if (item == curr.item) {

pred.next = curr.next;

return true;

}

pred.unlock();

pred = curr;

curr = curr.next;

curr.lock();

}

return false;

Otherwise, not present

110 of 261

Art of Multiprocessor Programming

110

Why does this work?

To remove node e

Must lock e
Must lock e’s predecessor

Therefore, if you lock a node

It can’t be removed
And neither can its successor

111 of 261

Art of Multiprocessor Programming

111

Adding Nodes

To add node e

Must lock predecessor
Must lock successor

Neither can be deleted

(Is successor lock actually required?)

112 of 261

Art of Multiprocessor Programming

112

Rep Invariant

Easy to check that

tail always reachable from head
Nodes sorted, no duplicates

113 of 261

Art of Multiprocessor Programming

113

Drawbacks

Better than coarse-grained lock

Threads can traverse in parallel

Still not ideal

Long chain of acquire/release
Inefficient

114 of 261

Art of Multiprocessor Programming

114

Optimistic Synchronization

Find nodes without locking
Lock nodes
Check that everything is OK

115 of 261

Art of Multiprocessor Programming

115

Optimistic: Traverse without Locking

b

d

e

a

add(c)

Aha!

116 of 261

Art of Multiprocessor Programming

116

Optimistic: Lock and Load

b

d

e

a

add(c)

117 of 261

Art of Multiprocessor Programming

117

Optimistic: Lock and Load

b

d

e

a

add(c)

c

118 of 261

Art of Multiprocessor Programming

118

What could go wrong?

b

d

e

a

add(c)

Aha!

119 of 261

Art of Multiprocessor Programming

119

What could go wrong?

b

d

e

a

add(c)

120 of 261

Art of Multiprocessor Programming

120

What could go wrong?

b

d

e

a

remove(b)

121 of 261

Art of Multiprocessor Programming

121

What could go wrong?

b

d

e

a

remove(b)

122 of 261

Art of Multiprocessor Programming

122

What could go wrong?

b

d

e

a

add(c)

123 of 261

Art of Multiprocessor Programming

123

What could go wrong?

b

d

e

a

add(c)

c

124 of 261

Art of Multiprocessor Programming

124

What could go wrong?

d

e

a

add(c)

Uh-oh

125 of 261

Art of Multiprocessor Programming

125

Validate – Part 1

b

d

e

a

add(c)

Yes, b still reachable from head

126 of 261

Art of Multiprocessor Programming

126

What Else Could Go Wrong?

b

d

e

a

add(c)

Aha!

127 of 261

Art of Multiprocessor Programming

127

What Else Coould Go Wrong?

b

d

e

a

add(c)

add(b’)

128 of 261

Art of Multiprocessor Programming

128

What Else Coould Go Wrong?

b

d

e

a

add(c)

add(b’)

b’

129 of 261

Art of Multiprocessor Programming

129

What Else Could Go Wrong?

b

d

e

a

add(c)

b’

130 of 261

Art of Multiprocessor Programming

130

What Else Could Go Wrong?

b

d

e

a

add(c)

c

131 of 261

Art of Multiprocessor Programming

131

Validate Part 2�(while holding locks)

b

d

e

a

add(c)

Yes, b still points to d

132 of 261

Art of Multiprocessor Programming

132

Optimistic: Linearization Point

b

d

e

a

add(c)

c

133 of 261

Art of Multiprocessor Programming

133

Invariants

Careful: we may traverse deleted nodes
But we establish properties by

Validation
After we lock target nodes

134 of 261

Art of Multiprocessor Programming

134

Correctness

If

Nodes b and c both locked
Node b still accessible
Node c still successor to b

Then

Neither will be deleted
OK to delete and return true

135 of 261

Art of Multiprocessor Programming

135

Unsuccessful Remove

a

b

d

e

remove(c)

Aha!

136 of 261

Art of Multiprocessor Programming

136

Validate (1)

a

b

d

e

Yes, b still reachable from head

remove(c)

137 of 261

Art of Multiprocessor Programming

137

Validate (2)

a

b

d

e

remove(c)

Yes, b still points to d

138 of 261

Art of Multiprocessor Programming

138

OK Computer

a

b

d

e

remove(c)

return false

139 of 261

Art of Multiprocessor Programming

139

Correctness

If

Nodes b and d both locked
Node b still accessible
Node d still successor to b

Then

Neither will be deleted
No thread can add c after b
OK to return false

140 of 261

Art of Multiprocessor Programming

140

Validation

private boolean

validate(Node pred,

Node curr) {

Node node = head;

while (node.key <= pred.key) {

if (node == pred)

return pred.next == curr;

node = node.next;

}

return false;

}

141 of 261

Art of Multiprocessor Programming

141

private boolean

validate(Node pred,

Node curr) {

Node node = head;

while (node.key <= pred.key) {

if (node == pred)

return pred.next == curr;

node = node.next;

}

return false;

}

Validation

Predecessor & current nodes

142 of 261

Art of Multiprocessor Programming

142

private boolean

validate(Node pred,

Node curr) {

Node node = head;

while (node.key <= pred.key) {

if (node == pred)

return pred.next == curr;

node = node.next;

}

return false;

}

Validation

Begin at the beginning

143 of 261

Art of Multiprocessor Programming

143

private boolean

validate(Node pred,

Node curr) {

Node node = head;

while (node.key <= pred.key) {

if (node == pred)

return pred.next == curr;

node = node.next;

}

return false;

}

Validation

Search range of keys

144 of 261

Art of Multiprocessor Programming

144

private boolean

validate(Node pred,

Node curr) {

Node node = head;

while (node.key <= pred.key) {

if (node == pred)

return pred.next == curr;

node = node.next;

}

return false;

}

Validation

Predecessor reachable

145 of 261

Art of Multiprocessor Programming

145

private boolean

validate(Node pred,

Node curr) {

Node node = head;

while (node.key <= pred.key) {

if (node == pred)

return pred.next == curr;

node = node.next;

}

return false;

}

Validation

Is current node next?

146 of 261

Art of Multiprocessor Programming

146

private boolean

validate(Node pred,

Node curr) {

Node node = head;

while (node.key <= pred.key) {

if (node == pred)

return pred.next == curr;

node = node.next;

}

return false;

}

Validation

Otherwise move on

147 of 261

Art of Multiprocessor Programming

147

private boolean

validate(Node pred,

Node curr) {

Node node = head;

while (node.key <= pred.key) {

if (node == pred)

return pred.next == curr;

node = node.next;

}

return false;

}

Validation

Predecessor not reachable

148 of 261

Art of Multiprocessor Programming

148

Remove: searching

public boolean remove(Item item) {

int key = item.hashCode();

retry: while (true) {

Node pred = this.head;

Node curr = pred.next;

while (curr.key <= key) {

if (item == curr.item)

break;

pred = curr;

curr = curr.next;

} …

149 of 261

Art of Multiprocessor Programming

149

public boolean remove(Item item) {

int key = item.hashCode();

retry: while (true) {

Node pred = this.head;

Node curr = pred.next;

while (curr.key <= key) {

if (item == curr.item)

break;

pred = curr;

curr = curr.next;

} …

Remove: searching

Search key

150 of 261

Art of Multiprocessor Programming

150

public boolean remove(Item item) {

int key = item.hashCode();

retry: while (true) {

Node pred = this.head;

Node curr = pred.next;

while (curr.key <= key) {

if (item == curr.item)

break;

pred = curr;

curr = curr.next;

} …

Remove: searching

Retry on synchronization conflict

151 of 261

Art of Multiprocessor Programming

151

public boolean remove(Item item) {

int key = item.hashCode();

retry: while (true) {

Node pred = this.head;

Node curr = pred.next;

while (curr.key <= key) {

if (item == curr.item)

break;

pred = curr;

curr = curr.next;

} …

Remove: searching

Examine predecessor and current nodes

152 of 261

Art of Multiprocessor Programming

152

public boolean remove(Item item) {

int key = item.hashCode();

retry: while (true) {

Node pred = this.head;

Node curr = pred.next;

while (curr.key <= key) {

if (item == curr.item)

break;

pred = curr;

curr = curr.next;

} …

Remove: searching

Search by key

153 of 261

Art of Multiprocessor Programming

153

public boolean remove(Item item) {

int key = item.hashCode();

retry: while (true) {

Node pred = this.head;

Node curr = pred.next;

while (curr.key <= key) {

if (item == curr.item)

break;

pred = curr;

curr = curr.next;

} …

Remove: searching

Stop if we find item

154 of 261

Art of Multiprocessor Programming

154

public boolean remove(Item item) {

int key = item.hashCode();

retry: while (true) {

Node pred = this.head;

Node curr = pred.next;

while (curr.key <= key) {

if (item == curr.item)

break;

pred = curr;

curr = curr.next;

} …

Remove: searching

Move along

155 of 261

Art of Multiprocessor Programming

155

On Exit from Loop

If item is present

curr holds item
pred just before curr

If item is absent

curr has first higher key
pred just before curr

156 of 261

Art of Multiprocessor Programming

156

Remove Method

try {

pred.lock(); curr.lock();

if (validate(pred,curr) {

if (curr.item == item) {

pred.next = curr.next;

return true;

} else {

return false;

}}} finally {

pred.unlock();

curr.unlock();

}}}

157 of 261

Art of Multiprocessor Programming

157

try {

pred.lock(); curr.lock();

if (validate(pred,curr) {

if (curr.item == item) {

pred.next = curr.next;

return true;

} else {

return false;

}}} finally {

pred.unlock();

curr.unlock();

}}}

Remove Method

Always unlock

158 of 261

Art of Multiprocessor Programming

158

try {

pred.lock(); curr.lock();

if (validate(pred,curr) {

if (curr.item == item) {

pred.next = curr.next;

return true;

} else {

return false;

}}} finally {

pred.unlock();

curr.unlock();

}}}

Remove Method

Lock both nodes

159 of 261

Art of Multiprocessor Programming

159

try {

pred.lock(); curr.lock();

if (validate(pred,curr) {

if (curr.item == item) {

pred.next = curr.next;

return true;

} else {

return false;

}}} finally {

pred.unlock();

curr.unlock();

}}}

Remove Method

Check for synchronization conflicts

160 of 261

Art of Multiprocessor Programming

160

try {

pred.lock(); curr.lock();

if (validate(pred,curr) {

if (curr.item == item) {

pred.next = curr.next;

return true;

} else {

return false;

}}} finally {

pred.unlock();

curr.unlock();

}}}

Remove Method

target found, remove node

161 of 261

Art of Multiprocessor Programming

161

try {

pred.lock(); curr.lock();

if (validate(pred,curr) {

if (curr.item == item) {

pred.next = curr.next;

return true;

} else {

return false;

}}} finally {

pred.unlock();

curr.unlock();

}}}

Remove Method

target not found

162 of 261

Art of Multiprocessor Programming

162

Optimistic List

Limited hot-spots

Targets of add(), remove(), contains()
No contention on traversals

Moreover

Traversals are wait-free
Food for thought …

163 of 261

Art of Multiprocessor Programming

163

So Far, So Good

Much less lock acquisition/release

Performance
Concurrency

Problems

Need to traverse list twice
contains() method acquires locks

164 of 261

Art of Multiprocessor Programming

164

Evaluation

Optimistic is effective if

cost of scanning twice without locks

is less than

cost of scanning once with locks

Drawback

contains() acquires locks
90% of calls in many apps

165 of 261

Art of Multiprocessor Programming

165

Lazy List

Like optimistic, except

Scan once
contains(x) never locks …

Key insight

Removing nodes causes trouble
Do it “lazily”

166 of 261

Art of Multiprocessor Programming

166

Lazy List

remove()

Scans list (as before)
Locks predecessor & current (as before)

Logical delete

Marks current node as removed (new!)

Physical delete

Redirects predecessor’s next (as before)

167 of 261

Art of Multiprocessor Programming

167

Lazy Removal

a

b

c

d

168 of 261

c

Art of Multiprocessor Programming

168

Lazy Removal

a

b

d

Present in list

169 of 261

c

Art of Multiprocessor Programming

169

Lazy Removal

a

b

d

Logically deleted

170 of 261

Art of Multiprocessor Programming

170

Lazy Removal

a

b

c

d

Physically deleted

171 of 261

Art of Multiprocessor Programming

171

Lazy Removal

a

b

d

Physically deleted

172 of 261

Art of Multiprocessor Programming

172

Lazy List

All Methods

Scan through locked and marked nodes
Removing a node doesn’t slow down other method calls …

Must still lock pred and curr nodes.

173 of 261

Art of Multiprocessor Programming

173

Validation

No need to rescan list!
Check that pred is not marked
Check that curr is not marked
Check that pred points to curr

174 of 261

Art of Multiprocessor Programming

174

Business as Usual

a

b

c

175 of 261

Art of Multiprocessor Programming

175

Business as Usual

a

b

c

176 of 261

Art of Multiprocessor Programming

176

Business as Usual

a

b

c

177 of 261

Art of Multiprocessor Programming

177

Business as Usual

a

b

c

remove(b)

178 of 261

Art of Multiprocessor Programming

178

Business as Usual

a

b

c

a not marked

179 of 261

Art of Multiprocessor Programming

179

Business as Usual

a

b

c

a still points to b

180 of 261

Art of Multiprocessor Programming

180

Business as Usual

a

b

c

Logical delete

181 of 261

Art of Multiprocessor Programming

181

Business as Usual

a

b

c

physical delete

182 of 261

Art of Multiprocessor Programming

182

Business as Usual

a

b

c

183 of 261

Art of Multiprocessor Programming

183

Validation

private boolean

validate(Node pred, Node curr) {

return

!pred.marked &&

!curr.marked &&

pred.next == curr);

}

184 of 261

Art of Multiprocessor Programming

184

private boolean

validate(Node pred, Node curr) {

return

!pred.marked &&

!curr.marked &&

pred.next == curr);

}

List Validate Method

Predecessor not

Logically removed

185 of 261

Art of Multiprocessor Programming

185

private boolean

validate(Node pred, Node curr) {

return

!pred.marked &&

!curr.marked &&

pred.next == curr);

}

List Validate Method

Current not

Logically removed

186 of 261

Art of Multiprocessor Programming

186

private boolean

validate(Node pred, Node curr) {

return

!pred.marked &&

!curr.marked &&

pred.next == curr);

}

List Validate Method

Predecessor still

Points to current

187 of 261

Art of Multiprocessor Programming

187

Remove

try {

pred.lock(); curr.lock();

if (validate(pred,curr) {

if (curr.key == key) {

curr.marked = true;

pred.next = curr.next;

return true;

} else {

return false;

}}} finally {

pred.unlock();

curr.unlock();

}}}

188 of 261

Art of Multiprocessor Programming

188

Remove

try {

pred.lock(); curr.lock();

if (validate(pred,curr) {

if (curr.key == key) {

curr.marked = true;

pred.next = curr.next;

return true;

} else {

return false;

}}} finally {

pred.unlock();

curr.unlock();

}}}

Validate as before

189 of 261

Art of Multiprocessor Programming

189

Remove

try {

pred.lock(); curr.lock();

if (validate(pred,curr) {

if (curr.key == key) {

curr.marked = true;

pred.next = curr.next;

return true;

} else {

return false;

}}} finally {

pred.unlock();

curr.unlock();

}}}

Key found

190 of 261

Art of Multiprocessor Programming

190

Remove

try {

pred.lock(); curr.lock();

if (validate(pred,curr) {

if (curr.key == key) {

curr.marked = true;

pred.next = curr.next;

return true;

} else {

return false;

}}} finally {

pred.unlock();

curr.unlock();

}}}

Logical remove

191 of 261

Art of Multiprocessor Programming

191

Remove

try {

pred.lock(); curr.lock();

if (validate(pred,curr) {

if (curr.key == key) {

curr.marked = true;

pred.next = curr.next;

return true;

} else {

return false;

}}} finally {

pred.unlock();

curr.unlock();

}}}

physical remove

192 of 261

Art of Multiprocessor Programming

192

Contains

public boolean contains(Item item) {

int key = item.hashCode();

Node curr = this.head;

while (curr.key < key) {

curr = curr.next;

}

return curr.key == key && !curr.marked;

}

193 of 261

Art of Multiprocessor Programming

193

Contains

public boolean contains(Item item) {

int key = item.hashCode();

Node curr = this.head;

while (curr.key < key) {

curr = curr.next;

}

return curr.key == key && !curr.marked;

}

Start at the head

194 of 261

Art of Multiprocessor Programming

194

Contains

public boolean contains(Item item) {

int key = item.hashCode();

Node curr = this.head;

while (curr.key < key) {

curr = curr.next;

}

return curr.key == key && !curr.marked;

}

Search key range

195 of 261

Art of Multiprocessor Programming

195

Contains

public boolean contains(Item item) {

int key = item.hashCode();

Node curr = this.head;

while (curr.key < key) {

curr = curr.next;

}

return curr.key == key && !curr.marked;

}

Traverse without locking

(nodes may have been removed)

196 of 261

Art of Multiprocessor Programming

196

Contains

public boolean contains(Item item) {

int key = item.hashCode();

Node curr = this.head;

while (curr.key < key) {

curr = curr.next;

}

return curr.key == key && !curr.marked;

}

Present and undeleted?

197 of 261

Art of Multiprocessor Programming

197

Summary: Wait-free Contains

a

0

a

b

c

0

e

1

d

Use Mark bit + list ordering

Not marked 🡪 in the set
Marked or missing 🡪 not in the set

198 of 261

Art of Multiprocessor Programming

198

Lazy List

a

0

a

b

c

0

e

1

d

Lazy add() and remove() + Wait-free contains()

199 of 261

Art of Multiprocessor Programming

199

Evaluation

Good:

contains() doesn’t lock
In fact, its wait-free!
Good because typically high % contains()
Uncontended calls don’t re-traverse

Bad

Contended add() and remove() calls do re-traverse
Traffic jam if one thread delays

200 of 261

Art of Multiprocessor Programming

200

Traffic Jam

Any concurrent data structure based on mutual exclusion has a weakness
If one thread

Enters critical section
And “eats the big muffin”

Cache miss, page fault, descheduled …

Everyone else using that lock is stuck!
Need to trust the scheduler….

201 of 261

Art of Multiprocessor Programming

201

Reminder: Lock-Free Data Structures

No matter what …

Guarantees minimal progress in any execution
i.e. Some thread will always complete a method call
Even if others halt at malicious times
Implies that implementation can’t use locks

202 of 261

Art of Multiprocessor Programming

202

Lock-free Lists

Next logical step

Wait-free contains()
lock-free add() and remove()

Use only compareAndSet()

What could go wrong?

203 of 261

Art of Multiprocessor Programming

203

a

0

a

b

c

0

e

1

c

Logical Removal

Physical Removal

Use CAS to verify pointer

is correct

Not enough!

Lock-free Lists

204 of 261

Art of Multiprocessor Programming

204

Problem…

a

0

a

b

c

0

e

1

c

Logical Removal

Physical Removal

0

d

Node added

205 of 261

Art of Multiprocessor Programming

205

The Solution: Combine Bit and Pointer

a

0

a

b

c

0

e

1

c

Logical Removal =

Set Mark Bit

Physical

Removal

CAS

0

d

Mark-Bit and Pointer

are CASed together

(AtomicMarkableReference)

Fail CAS: Node not

added after logical

Removal

206 of 261

Art of Multiprocessor Programming

206

Solution

Use AtomicMarkableReference
Atomically

Swing reference and
Update flag

Remove in two steps

Set mark bit in next field
Redirect predecessor’s pointer

207 of 261

Art of Multiprocessor Programming

207

Marking a Node

AtomicMarkableReference class

Java.util.concurrent.atomic package

address

F

mark bit

Reference

208 of 261

Art of Multiprocessor Programming

208

Extracting Reference & Mark

Public Object get(boolean[] marked);

209 of 261

Art of Multiprocessor Programming

209

Extracting Reference & Mark

Public Object get(boolean[] marked);

Returns reference

Returns mark at array index 0!

210 of 261

Art of Multiprocessor Programming

210

Extracting Reference Only

public boolean isMarked();

Value of mark

211 of 261

Art of Multiprocessor Programming

211

Changing State

Public boolean compareAndSet(

Object expectedRef,

Object updateRef,

boolean expectedMark,

boolean updateMark);

212 of 261

Art of Multiprocessor Programming

212

Changing State

Public boolean compareAndSet(

Object expectedRef,

Object updateRef,

boolean expectedMark,

boolean updateMark);

If this is the current reference …

And this is the current mark …

213 of 261

Art of Multiprocessor Programming

213

Changing State

Public boolean compareAndSet(

Object expectedRef,

Object updateRef,

boolean expectedMark,

boolean updateMark);

…then change to this new reference …

… and this new mark

214 of 261

Art of Multiprocessor Programming

214

Changing State

public boolean attemptMark(

Object expectedRef,

boolean updateMark);

215 of 261

Art of Multiprocessor Programming

215

Changing State

public boolean attemptMark(

Object expectedRef,

boolean updateMark);

If this is the current reference …

216 of 261

Art of Multiprocessor Programming

216

Changing State

public boolean attemptMark(

Object expectedRef,

boolean updateMark);

.. then change to this new mark.

217 of 261

b

CAS

Art of Multiprocessor Programming

217

Removing a Node

a

c

d

remove c

218 of 261

Art of Multiprocessor Programming

218

Removing a Node

a

b

d

remove b

remove c

c

failed

CAS

219 of 261

Art of Multiprocessor Programming

219

Removing a Node

a

b

d

remove b

remove c

c

220 of 261

Art of Multiprocessor Programming

220

Removing a Node

a

d

remove b

remove c

221 of 261

Art of Multiprocessor Programming

221

Traversing the List

Q: what do you do when you find a “logically” deleted node in your path?
A: finish the job.

CAS the predecessor’s next field
Proceed (repeat as needed)

222 of 261

Art of Multiprocessor Programming

222

Lock-Free Traversal�(only Add and Remove)

a

b

c

d

CAS

Uh-oh

pred

curr

pred

curr

223 of 261

Art of Multiprocessor Programming

223

The Window Class

class Window {

public Node pred;

public Node curr;

Window(Node pred, Node curr) {

this.pred = pred; this.curr = curr;

}

224 of 261

Art of Multiprocessor Programming

224

The Window Class

class Window {

public Node pred;

public Node curr;

Window(Node pred, Node curr) {

this.pred = pred; this.curr = curr;

}

A container for pred and current values

225 of 261

Art of Multiprocessor Programming

225

Using the Find Method

Window window = find(head, key);

Node pred = window.pred;

curr = window.curr;

226 of 261

Art of Multiprocessor Programming

226

Using the Find Method

Window window = find(head, key);

Node pred = window.pred;

curr = window.curr;

Find returns window

227 of 261

Art of Multiprocessor Programming

227

Using the Find Method

Window window = find(head, key);

Node pred = window.pred;

curr = window.curr;

Extract pred and curr

228 of 261

228

The Find Method

Window window = find(item);

At some instant,

pred

curr

succ

item

or …

229 of 261

229

The Find Method

Window window = find(item);

At some instant,

pred

curr= null

succ

item

not in list

230 of 261

Art of Multiprocessor Programming

230

Remove

public boolean remove(T item) {

Boolean snip;

while (true) {

Window window = find(head, key);

Node pred = window.pred, curr = window.curr;

if (curr.key != key) {

return false;

} else {

Node succ = curr.next.getReference();

snip = curr.next.compareAndSet(succ, succ, false true);

if (!snip) continue;

pred.next.compareAndSet(curr, succ, false, false);

return true;

}}}

231 of 261

Art of Multiprocessor Programming

231

Remove

public boolean remove(T item) {

Boolean snip;

while (true) {

Window window = find(head, key);

Node pred = window.pred, curr = window.curr;

if (curr.key != key) {

return false;

} else {

Node succ = curr.next.getReference();

snip = curr.next.compareAndSet (succ, succ, false, true);

if (!snip) continue;

pred.next.compareAndSet(curr, succ, false, false);

return true;

}}}

Keep trying

232 of 261

Art of Multiprocessor Programming

232

Remove

public boolean remove(T item) {

Boolean snip;

while (true) {

Window window = find(head, key);

Node pred = window.pred, curr = window.curr;

if (curr.key != key) {

return false;

} else {

Node succ = curr.next.getReference();

snip = curr.next.compareAndSet (succ, succ, false, true);

if (!snip) continue;

pred.next.compareAndSet(curr, succ, false, false);

return true;

}}}

Find neighbors

233 of 261

Art of Multiprocessor Programming

233

Remove

public boolean remove(T item) {

Boolean snip;

while (true) {

Window window = find(head, key);

Node pred = window.pred, curr = window.curr;

if (curr.key != key) {

return false;

} else {

Node succ = curr.next.getReference();

snip = curr.next.compareAndSet(succ, succ, false, true);

if (!snip) continue;

pred.next.compareAndSet(curr, succ, false, false);

return true;

}}}

She’s not there …

234 of 261

Art of Multiprocessor Programming

234

Remove

public boolean remove(T item) {

Boolean snip;

while (true) {

Window window = find(head, key);

Node pred = window.pred, curr = window.curr;

if (curr.key != key) {

return false;

} else {

Node succ = curr.next.getReference();

snip = curr.next.compareAndSet(succ, succ, false, true);

if (!snip) continue;

pred.next.compareAndSet(curr, succ, false, false);

return true;

}}}

Try to mark node as deleted

235 of 261

Art of Multiprocessor Programming

235

Remove

public boolean remove(T item) {

Boolean snip;

while (true) {

Window window = find(head, key);

Node pred = window.pred, curr = window.curr;

if (curr.key != key) {

return false;

} else {

Node succ = curr.next.getReference();

snip = curr.next.compareAndSet(succ, succ, false, true);

if (!snip) continue;

pred.next.compareAndSet(curr, succ, false, false);

return true;

}}}

If it doesn’t work, just retry, if it does, job essentially done

236 of 261

Art of Multiprocessor Programming

236

Remove

public boolean remove(T item) {

Boolean snip;

while (true) {

Window window = find(head, key);

Node pred = window.pred, curr = window.curr;

if (curr.key != key) {

return false;

} else {

Node succ = curr.next.getReference();

snip = curr.next.compareAndSet(succ, succ, false, true);

if (!snip) continue;

pred.next.compareAndSet(curr, succ, false, false);

return true;

}}}

Try to advance reference

(if we don’t succeed, someone else did or will).

a

237 of 261

Art of Multiprocessor Programming

237

Add

public boolean add(T item) {

boolean splice;

while (true) {

Window window = find(head, key);

Node pred = window.pred, curr = window.curr;

if (curr.key == key) {

return false;

} else {

Node node = new Node(item);

node.next = new AtomicMarkableRef(curr, false);

if (pred.next.compareAndSet(curr, node, false, false)) {return true;}

}}}

238 of 261

Art of Multiprocessor Programming

238

Add

public boolean add(T item) {

boolean splice;

while (true) {

Window window = find(head, key);

Node pred = window.pred, curr = window.curr;

if (curr.key == key) {

return false;

} else {

Node node = new Node(item);

node.next = new AtomicMarkableRef(curr, false);

if (pred.next.compareAndSet(curr, node, false, false)) {return true;}

}}}

Item already there.

239 of 261

Art of Multiprocessor Programming

239

Add

public boolean add(T item) {

boolean splice;

while (true) {

Window window = find(head, key);

Node pred = window.pred, curr = window.curr;

if (curr.key == key) {

return false;

} else {

Node node = new Node(item);

node.next = new AtomicMarkableRef(curr, false);

if (pred.next.compareAndSet(curr, node, false, false)) {return true;}

}}}

create new node

240 of 261

Art of Multiprocessor Programming

240

Add

public boolean add(T item) {

boolean splice;

while (true) {

Window window = find(head, key);

Node pred = window.pred, curr = window.curr;

if (curr.key == key) {

return false;

} else {

Node node = new Node(item);

node.next = new AtomicMarkableRef(curr, false);

if (pred.next.compareAndSet(curr, node, false, false)) {return true;}

}}}

Install new node, else retry loop

241 of 261

Art of Multiprocessor Programming

241

Wait-free Contains

public boolean contains(T item) {

boolean marked;

int key = item.hashCode();

Node curr = this.head;

while (curr.key < key)

curr = curr.next;

Node succ = curr.next.get(marked);

return (curr.key == key && !marked[0])

}

242 of 261

Art of Multiprocessor Programming

242

Wait-free Contains

public boolean contains(T item) {

boolean marked;

int key = item.hashCode();

Node curr = this.head;

while (curr.key < key)

curr = curr.next;

Node succ = curr.next.get(marked);

return (curr.key == key && !marked[0])

}

Only diff is that we get and check marked

243 of 261

Art of Multiprocessor Programming

243

Lock-free Find

public Window find(Node head, int key) {

Node pred = null, curr = null, succ = null;

boolean[] marked = {false}; boolean snip;

retry: while (true) {

pred = head;

curr = pred.next.getReference();

while (true) {

succ = curr.next.get(marked);

while (marked[0]) {

…

}

if (curr.key >= key)

return new Window(pred, curr);

pred = curr;

curr = succ;

}

}}

244 of 261

Art of Multiprocessor Programming

244

Lock-free Find

public Window find(Node head, int key) {

Node pred = null, curr = null, succ = null;

boolean[] marked = {false}; boolean snip;

retry: while (true) {

pred = head;

curr = pred.next.getReference();

while (true) {

succ = curr.next.get(marked);

while (marked[0]) {

…

}

if (curr.key >= key)

return new Window(pred, curr);

pred = curr;

curr = succ;

}

}}

If list changes while traversed, start over

245 of 261

Art of Multiprocessor Programming

245

public Window find(Node head, int key) {

Node pred = null, curr = null, succ = null;

boolean[] marked = {false}; boolean snip;

retry: while (true) {

pred = head;

curr = pred.next.getReference();

while (true) {

succ = curr.next.get(marked);

while (marked[0]) {

…

}

if (curr.key >= key)

return new Window(pred, curr);

pred = curr;

curr = succ;

}

}}

Lock-free Find

Start looking from head

246 of 261

Art of Multiprocessor Programming

246

public Window find(Node head, int key) {

Node pred = null, curr = null, succ = null;

boolean[] marked = {false}; boolean snip;

retry: while (true) {

pred = head;

curr = pred.next.getReference();

while (true) {

succ = curr.next.get(marked);

while (marked[0]) {

…

}

if (curr.key >= key)

return new Window(pred, curr);

pred = curr;

curr = succ;

}

}}

Lock-free Find

Move down the list

247 of 261

Art of Multiprocessor Programming

247

public Window find(Node head, int key) {

Node pred = null, curr = null, succ = null;

boolean[] marked = {false}; boolean snip;

retry: while (true) {

pred = head;

curr = pred.next.getReference();

while (true) {

succ = curr.next.get(marked);

while (marked[0]) {

…

}

if (curr.key >= key)

return new Window(pred, curr);

pred = curr;

curr = succ;

}

}}

Lock-free Find

Get ref to successor and current deleted bit

248 of 261

Art of Multiprocessor Programming

248

public Window find(Node head, int key) {

Node pred = null, curr = null, succ = null;

boolean[] marked = {false}; boolean snip;

retry: while (true) {

pred = head;

curr = pred.next.getReference();

while (true) {

succ = curr.next.get(marked);

while (marked[0]) {

…

}

if (curr.key >= key)

return new Window(pred, curr);

pred = curr;

curr = succ;

}

}}

Lock-free Find

Try to remove deleted nodes in path…code details soon

249 of 261

Art of Multiprocessor Programming

249

public Window find(Node head, int key) {

Node pred = null, curr = null, succ = null;

boolean[] marked = {false}; boolean snip;

retry: while (true) {

pred = head;

curr = pred.next.getReference();

while (true) {

succ = curr.next.get(marked);

while (marked[0]) {

…

}

if (curr.key >= key)

return new Window(pred, curr);

pred = curr;

curr = succ;

}

}}

Lock-free Find

If curr key that is greater or equal, return pred and curr

250 of 261

Art of Multiprocessor Programming

250

public Window find(Node head, int key) {

Node pred = null, curr = null, succ = null;

boolean[] marked = {false}; boolean snip;

retry: while (true) {

pred = head;

curr = pred.next.getReference();

while (true) {

succ = curr.next.get(marked);

while (marked[0]) {

…

}

if (curr.key >= key)

return new Window(pred, curr);

pred = curr;

curr = succ;

}

}}

Lock-free Find

Otherwise advance window and loop again

251 of 261

Art of Multiprocessor Programming

251

Lock-free Find

retry: while (true) {

…

while (marked[0]) {

snip = pred.next.compareAndSet(curr,

succ, false, false);

if (!snip) continue retry;

curr = succ;

succ = curr.next.get(marked);

}

…

252 of 261

Art of Multiprocessor Programming

252

Lock-free Find

retry: while (true) {

…

while (marked[0]) {

snip = pred.next.compareAndSet(curr,

succ, false, false);

if (!snip) continue retry;

curr = succ;

succ = curr.next.get(marked);

}

…

Try to snip out node

253 of 261

Art of Multiprocessor Programming

253

Lock-free Find

retry: while (true) {

…

while (marked[0]) {

snip = pred.next.compareAndSet(curr, succ, false, false);

if (!snip) continue retry;

curr = succ;

succ = curr.next.get(marked);

}

…

if predecessor’s next field changed must retry whole traversal

254 of 261

Art of Multiprocessor Programming

254

Lock-free Find

retry: while (true) {

…

while (marked[0]) {

snip = pred.next.compareAndSet(curr,

succ, false, false);

if (!snip) continue retry;

curr = succ;

succ = curr.next.get(marked);

}

…

Otherwise move on to check if next node deleted

255 of 261

Art of Multiprocessor Programming

255

Performance

On 16 node shared memory machine

Benchmark throughput of Java List-based Set

algs. Vary % of Contains() method Calls.

256 of 261

Art of Multiprocessor Programming

256

High Contains Ratio

Lock-free

Lazy list

Coarse Grained

Fine Lock-coupling

257 of 261

Art of Multiprocessor Programming

257

Low Contains Ratio

Lock-free

Lazy list

Coarse Grained

Fine Lock-coupling

258 of 261

Art of Multiprocessor Programming

258

As Contains Ratio Increases

Lock-free

Lazy list

Coarse Grained

Fine Lock-coupling

% Contains()

259 of 261

Art of Multiprocessor Programming

259

Summary

Coarse-grained locking
Fine-grained locking
Optimistic synchronization
Lazy synchronization
Lock-free synchronization

260 of 261

Art of Multiprocessor Programming

260

“To Lock or Not to Lock”

Locking vs. Non-blocking: Extremist views on both sides
The answer: nobler to compromise, combine locking and non-blocking

Example: Lazy list combines blocking add() and remove() and a wait-free contains()
Remember: Blocking/non-blocking is a property of a method

261 of 261

Art of Multiprocessor Programming

261

�This work is licensed under a Creative Commons Attribution-ShareAlike 2.5 License.

You are free:

to Share — to copy, distribute and transmit the work
to Remix — to adapt the work

Under the following conditions:

Attribution. You must attribute the work to “The Art of Multiprocessor Programming” (but not in any way that suggests that the authors endorse you or your use of the work).
Share Alike. If you alter, transform, or build upon this work, you may distribute the resulting work only under the same, similar or a compatible license.

For any reuse or distribution, you must make clear to others the license terms of this work. The best way to do this is with a link to

http://creativecommons.org/licenses/by-sa/3.0/.

Any of the above conditions can be waived if you get permission from the copyright holder.
Nothing in this license impairs or restricts the author's moral rights.