Lazy synchronization, Optimistic synchronization

Question 1

What is the main idea behind lazy synchronization?

Answer 1

Postpone hard work
split 2 removal phases:
logical removal (mark component to be deleted)
physical removal(Do what needs to be done)

Question 2

what call are most likely to be made in Lazy:

Answer 2

contains()

Question 3

how does lazy refine optimistic sync

Answer 3

contains() are wait-free and add + remove traverse list only once in absence of contention

Question 4

What does each node have extra in lazy?

Answer 4

boolean field called marked which indicates whether the node is reachable. Every unmarked node is reachable

Question 5

Does the contains() every lock in lazy?

Answer 5

No

Question 6

Does validation require to traverse through the list to determine if a node is reachable?

Answer 6

No

Question 7

How does the validate function look in lazy()

Answer 7

private boolean
validate(Node pred, Node curr) {
return
!pred.marked &&
!curr.marked &&
pred.next == curr);
}

Question 8

How does the contains method look for lazy?

Answer 8

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;
}

Question 9

how does the add method look for lazy?

Answer 9

same as optimistic
public boolean add(T item) {
int key = item.hashCode();
while (true) {
Node pred = head;
Node curr = pred.next;
while (curr.key < key) {
pred = curr; curr = curr.next;
}
pred.lock(); curr.lock();
try {
if (validate(pred, curr)) {
if (curr.key == key) {
return false;
} else {
Node node = new Node(item);
node.next = curr;
pred.next = node;
return true;
}}} finally {
pred.unlock(); curr.unlock();
}}}

Question 10

How does remove look for Lazy?

Answer 10

public boolean remove(T item) {
int key = item.hashCode();
Node pred = head;
Node curr = pred.next;
while (curr.key < key) {
pred = curr;
curr = curr.next;
}
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();
}}}

Question 11

how does the contains method look for optimistic sync?

Answer 11

public boolean contains(T item) {
int key = item.hashCode();
Node pred = head;
Node curr = pred.next;
while (curr.key < key) {
pred = curr; curr = curr.next;
}
try {
pred.lock(); curr.lock();
if (validate(pred, curr))
return (curr.key == key)
} finally {
pred.unlock(); curr.unlock();
}

Question 12

Good + bad about Optimistic sync:

Answer 12

Good: less lock get/release = better performance + concurrency
bad: need to traverse list twice + contains still acquires locks