Concepts: Wait-free and Lock-free

An object impl. is wait-free if every thread completes a method in a finite number of steps:

• NO mutual exclusion (thread should not halt in critical section)
• NO while loop (that may keep spining..)

An object impl. if lock-free if in an infinite execution infinitely often some method call finishes(in a finite number of steps)

List synchronization patterns, an overview

0.Coarse grained locking: one lock rules all.
bottlenecking! adding more threads doesn’t speed up

1.Fine-grained synchronization:
have more locks! Split object into independently-synchronized-components. Kindda complex, locking overhead

2.Optimistic synchronization
For linked set of components. Search without locking, only locks when need to change a certain component. Cheaper than locking, but mistakes are expensive.

3.Lazy synchronization
postpone hard work.(like removing components)

• logical removal(easy to synchronize), mark delete, not actually deleting it.
• physical removal(difficult)

4. Lock-Free Synchronization
DO NOT USE LOCK.
use hardware support(atomic operations). e.g.compareAndSet(),Robust against asynchrony: (e.g. some threads are slow or stuck,since the slower ones don’t hold lock, others won’t get dragged). Disadv. comples, sometimes high overhead

Basic Setup.

1
2
3
4
5
6

// set interface
public interface Set{
    public boolean add(Object x);
    public boolean remove(Object x);
    public boolean contains(Object x);
}

public class Node {
    Object object;
    int key;   // usually hash code, e.g. for ordering
    Node next;
}

reasoning about concurrent data structures: Identify invariants, properties that always holds, use invariants to find out who is responsible for a fault.

set some invariants:

• Sentinel nodes(tail reachable from head)
• Sorted
• no duplicate

Synchronizations

coarse-grained: one lock rule them all

fine grained locking:
hand over hand locking, lock for each node. each thread only acquire locks on the nodes that they are opearating/watching e.g.

• delete node X, need to hold lock for both X and its predecessor.
• add node: lock predecessor, lock successor

Reviews:

• better chan coarse grained, can traverse in paralle
• not ideal: long chain of acquire/release, inefficient.
• bottle neck: allows concurrency but everyone always delayed by the front guy.
• Lock acquisition overhead.

optimistic list:

• find nodes without locking (traverse need no locks)
• lock nodes
• traverse again to make sure every ok.

e.g. remove node c: optimistically traverse list to find c, lock c.pred then lock c.curr. Re-Traverse list to find c and verity c.pred (still) precedes c.curr(otherwise try again or return false). Perform removal and release locks.

• wait-free traversal
• must have non-interference (natural in languages with GC like java)
• limited hotspots only at locked add(), remove(), contains() destination locations, not traversals
• drawback:
  • two traversals.(yet they are wait-free)
  • contains() acquires locks, but this method is the most commonly used one.
• scanning twice without vs. scanning once with locks(it depends, how fast is your lock?)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

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
    }
    //  in this case the predecessor not reachable
    return false;
}

public boolean remove(Object object){
    int key = object.hashCOde();
    while(true){
        // retry on conflict.
        Node pred = this.head;
        Node curr = pred.next;
        while(curr.key <= key){
            // optimistically traverse
            if(object == curr.object) break
            pred = curr;
            curr = curr.next;
        }

        // try to remove node
        try{
            // acquire lock, validate again.
        }finally{
            // release locks
        }
    }
}

Lazy List: split logical removal and physical removal
like optimistic except: scan once, contains() never locks

removing nodes causes trouble, do it lazily:

• Scan list (as before), no locks needed
• lock pred & curr (as before)
• each node has “removed” flag.
• logical delete: marks curr node as removed
• physical delete: redirects pred’s next (as before)

e.g. to remove c: optimistically traverse list to find c.
lock c.pred then lock c.curr
verify flag and that c.pred precedes c.curr
set flag (logical removal)
perform physical removal and release locks

Review:

• no need to rescan (check pred is not marked, curr is not marked, pred points to curr)
• wait-free traversal: in the set(no marked), not in the set(marked or missing)
• if the check failed, release all the locks and re-traverse the list.
• contains() need no lock
• do not need a second traverse(as in optimistic).

problem:

• still need to lock pred and curr node
• if lock holder stops/stuck, others using the lock suffer.

Lock-free List, using RMW(read modify write) operations java.util.concurrent.atomic

getAndSet: set new value and return old value compareAndSet(CAS): set new value and return true if old value matches expected value, return faluse otherwise

boolean compareAndSet(int expValue, int newValue);

AtomicMarkbableReference

public class AtomicMarkableReference<T>{
    public T get(boolean[] marked);
    public boolean compareAndSet(
                    T expectedRef,
                    T updateRef,
                    boolean expectedMark,
                    boolean updateMark);
    // if object matches expected and Mark matches 
    // expected mark, then update obj to updateRef 
    // and mark to updateMark

    public boolean attemptMark()

}

impl. use AtomicMarkableReference as the next field of node. . Therefore a mark bit is stored in the node’s next field. (But logically, this mark bit marks whether THIS NODE is deleted)

AtomicMarkableReference: atomically updates mark and reference: prevents manipulation of logically-removed next pointer

Lock-free Lists:

• eliminate locking entirely
• contains() wait-free, add() and remove() lock-free
• lock-free add() and remove()
• lock-free find()

REF

1. “the art of multicore programming”
2. FCDS Lecture, by Prof.Fetzer, TU Dresden.