Linked Lists

Goal of highly-concurrent objects:

  • concurrent access
  • more threads, more throughput

Four patterns for highly-concurrent objects:

  • fine-grained synchronization
    • split object into independently-synchronized components
    • methods conflict when they access the same component at the same time
  • optimistic synchronization
  • lazy synchronization
    • postpone hard work like removing components
  • lock-free synchronization
    • don't use locks at all
    • use CAS and its relatives

In this section, we will use a linked-list based set to illustrate four patterns.

public interface Set<T> {
    public boolean add(T x);
    public boolean remove(T x);
    public boolean contains(T x);
}

public class Node<T> {
    public T item;
    public int key; // hash code
    public Node next;
}

Reasoning about concurrent objects:

  • invariants (property that always holds)
  • true when object is created
  • preserved by each method and each step of each method
    • most steps are trivial
    • usually one step tricky, often linearization point

E.g. representation invariant of set:

  • sentinel nodes
    • tail reachable from head
  • sorted
  • no duplicates

Remove Method in Normal Lists

public boolean remove(Item item) {
    int key = item.hashCode();
    Node pred, curr; // predecessor and current nodes
    try {
        pred = this.head;
        pred.lock();
        curr = pred.next;
        curr.lock();
        // traversing list
        while (curr.key <= key) {
            // invariant: pred and curr locked
            if (item == curr.item) {
                pred.next = curr.next; // linearization point A
                return true;           // item removed
            }
            // find and lock next element
            pred.unlock();
            pred = curr;
            curr = curr.nect;
            curr.lock(); // linearization point B
        }
        return false;
    } finally { // make sure locks released
        curr.unlock();
        pred.unlock();
    }
}

To remove node \( e \), must lock \( e \) and its predecessor.

  • \( e \) cannot be removed by anyone else
  • \( e \)'s successor cannot be removed
  • \( e \)'s predecessor cannot be removed

Linearization of remove:

  • If item exists: point A
  • If item not exist: poin# Linked Lists

Drawbacks: long chain of acquire/release, inefficient

Optimistic List

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

public boolean remove(Item item) {
    int key = item.hashCode();
    while (true) {
        Node pred = this.pred;
        Node curr = pred.next;
        while (curr.key <= key) {
            if (item == curr.item) {
                break;
            }
            pred = curr;
            curr = curr.next;
        }
        try {
            pred.lock();
            curr.lock();
            // check for synchronization conflicts
            if (validate(pred, curr)) {
                pred.next = curr.next;
                return true;
            } else {
                return false;
            }
        } finally {
            pred.unlock();
            curr.unlock();
        }
    }
}

Benefits: much less lock acquire/release

Drawbacks: need to traverse list twice, contains() requries acquiring locks

Evaluation: optimistic method is effective if cost of scanning twice without locks is less than cost of scanning once with locks

Lazy List

Like optimistic, except:

  • scan once,
  • contains() never locks

Key insight: removing nodes causes trouble, so we do it lazily

  • logical remove: mark a node
  • physical remove: remove node from list

Invariant:

  • if not marked, then item in the set
  • and reachable from head
  • and if not yet traversed, it is reachable from pred
private boolean validate(Node pred, Node curr) {
    return !pred.marked && !curr.marked && pred.next == curr;
}

public boolean remove(Item item) {
    ...
    try {
        pred.lock();
        curr.lock();
        if (validate(pred, curr)) {
            if (curr.key == key) {
                curr.marked = true;    // logical remove
                pred.next = curr.next; // physical remove
                return true;
            } else {
                return false;
            }
        }
    } finally {
        pred.unlock();
        curr.unlock();
    }
    // inside while true, loop again
}

public boolean contains(Item item) { // wait-free!
    int key = item.hashCode();
    Node curr = this.head;
    while (curr.key < key) {
        curr = curr.next; // no lock, nodes may be removed
    }
    return curr.key == key && !curr.marked;
}

Benefits: wait-free contains()

Drawbacks:

  • contended add() and remove() calls do re-traverse
  • traffic jam if one thread delays

Traffic jam: if one thread enters critical section, and delays (cache miss, page fault, etc.), everyone else using that lock is stuck.

Lock-free Lists

Problem of eliminating locks: must prevent manipulation of removed node's pointer (当被逻辑删除,但还没有物理删除时,要防止该节点的指针被别人操作)

Solution: combine bit and pointer, make bit and pointer CASed together (AtomicMarkableReference)

What to do when you find a logically deleted node in path?

  • CAS the predecessor's next field
  • proceed (repeat)
  • 也就是,首先帮助别人把前驱的next进行CAS操作(别人可能还没做完这一步),然后重试
class Window {
    public Node pred;
    public Node curr;
    Window(Node pred, Node curr) {...}
}

public boolean remove(Item item) {
    boolean snip;
    while (true) {
        Window window = find(head, key);
        Node pred = window.pred, curr = window.curr; // neighbors
        if (curr.key != key) {
            return false; // not in list, not removed
        } else {
            Node succ = curr.next.getReference();
            snip = curr.next.attemptMark(succ, true); // try to mark deleted
            if (!snip) {
                continue; // logical delete failed, retry
            }
            pred.next.compareAndSet(curr, succ, false, false); // update next
            return true; // if we failed last CAS, someone else will succeed
        }
    }
}

public boolean add(Item item) {
    boolean splice;
    while (true) {
        Window window = find(head, key);
        Node pred = window.pred, curr = window.curr; // neighbors
        if (curr.key == key) {
            return false; // already here, not added
        } else {
            Node node = new Node(item);
            node.next = new AtomicMarkableReference(curr, false);
            if (pred.next.compareAndSet(curr, node, false, false)) {
                return true; // insert new node, else retry
            }
        }
    }
}

public boolean contains(Item item) {
    boolean marked;
    int key = item.hashCode();
    Node curr = this.head;
    while (curr.key < key) {
        curr = curr.next;
    }
    Node succ = curr.next.get(marked);
    return (curr.key == key && !marked[0]);
}