List synchronization, from coarse-grained to non blocking wait-free

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
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.

// 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


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


  • 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?)
private boolean validate(Node pred, Node curr){
    Node node = head;
        if(node == pred) return;
    node =
    //  in this case the predecessor not reachable
    return false;

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

        // try to remove node
            // acquire lock, validate again.
            // 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


  • 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).


  • 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);


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()


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