W12 Mittwoch

OPTIMISTIC implementation of ADD() method. Are bad interleavings possible?

• No, code is correct.

• Yes, because curr and pred are being unlocked in wrong order.

• Yes, because of an error in the code logic.

• Yes, because pred.next is set before entry.next.

• Yes, because list is traversed without locks.

What are advantages of lazy vs. optimistic synchronization?

• Lazy sync. requires no lock acquisitions.

• add()/remove() require less lock acquisitions

• add()/remove() require less list traversals

• remove() is in O(1)

A stack with these push() and pop() operations is non-blocking.

• True

• False

Wait-Free implies Starvation-Free

• True

• False

Lock-Free implies starvation-free.

• True

• False

Wait-Free implies Lock-Free

• True

• False

Lock-free implies deadlock-free.

• True

• False

The algorithm is lock-free.

• True

• False

The code is... (select all that apply)

• Deadlock-Free

• Lock-Free

• Starvation-Free

• Wait-Free

A lock-free method always finishes in a bounded number of steps, indepen-

dent of other threads.

• True.

• False.