1 of 19

9.6-9.7: Optimistic and Lazy Synchronization

Jesper Pedersen Notander

Herlihy

Ch 9. Linked Lists: The Role of Locking

2 of 19

Optimistic Synchronization

head

tail

a

b

c

d

Node {

T value;

volatile Node next;

}

Absence from interference ⇒

  • A removed node’s next field is never changed
  • Requires that the GC does not remove a node that is traversed.

b

3 of 19

Optimistic Synchronization

head

tail

a

b

c

d

e

predA

currA

#currA < #e

4 of 19

Optimistic Synchronization

head

tail

a

b

c

d

e

predA

currA

#currA < #e

5 of 19

Optimistic Synchronization

head

tail

a

b

c

d

e

predA

currA

#currA < #e

6 of 19

Optimistic Synchronization

head

tail

a

b

c

d

e

predA

currA

#currA < #e

7 of 19

Optimistic Synchronization

head

tail

a

b

d

e

predA

currA

c

Interference

8 of 19

Optimistic Synchronization

head

tail

a

b

d

e

predA

currA

c

Validation

predA .next == currA

9 of 19

Optimistic Synchronization

head

tail

a

b

d

predA

Validation

e

currA

c

CONFLICT ⇒ RESTART

predA .next == currA

10 of 19

Optimistic Synchronization

head

tail

a

b

d

predA

currA

c

head

tail

a

b

d

predA

currA

c

add(e)

remove(e)

e

11 of 19

Optimistic Synchronization

head

tail

a

b

d

predA

currA

c

head

tail

a

b

d

predA

currA

c

e

add(e)

remove(e)

12 of 19

Optimistic Summary

  • Not starvation free in theory but in practice
  • $(traversing*2) << $(traversing + locks)
  • Contains acquires locks ⇒ performance--

​

13 of 19

Lazy Synchronization

head

tail

a

b

c

d

Node {

boolean marked;

T value;

volatile Node next;

}

Every unmarked node is reachable!

14 of 19

Lazy Synchronization

a

b

e

c

d

!predA.marked &&

!currA.marked &&

predA.next == currA

​

Validation

head

tail

predA

currA

15 of 19

Lazy Synchronization

head

tail

a

b

e

predA

currA

c

d

CONFLICT ⇒ RESTART

!predA.marked &&

!currA.marked &&

predA.next == currA

​

Validation

16 of 19

Optimistic Synchronization

currA

c

head

tail

a

b

d

predA

Physical removal

Logical removal (mark)

remove(e)

17 of 19

Lazy Synchronization

  • add() and remove() is not starvation-free
  • contains() is wait-free
  • Separation of logical steps from physical
  • add() and remove() are blocking

​

18 of 19

Thank

You

​

19 of 19

Exercises

Ex 1) Show that the add() method in the optimistic algorithm only need to lock either pred or curr?

​

Ex 2) Would the lazy algorithm work if we set the next field to null, instead of using a boolean flag?