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
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.
May 8, 2022


[+] click to leave a comment [+]
the comment system on this blog works via email. The button
below will generate a mailto: link based on this page's url 
and invoke your email client - please edit the comment there!

[optional] even better, encrypt the email with my public key

- don't modify the subject field
- specify a nickname, otherwise your comment will be shown as   
  anonymous
- your email address will not be disclosed
- you agree that the comment is to be made public.
- to take down a comment, send the request via email.

>> SEND COMMENT <<




Fun with Image Maps and SVGs via benji February 20, 2024

Over the past few weeks I've been playing around with making some images on my website interactive. My "informatics" class in high school taught us some basic HTML. By basic I mean in notepad and writing everything by hand, saving to a...

Goblin Week 2024 via Helvetica Blanc January 26, 2024

It snuck up on me, but I managed to draw my little goblins to celebrate the week! I love my children - they're like awful Pikmin. I've uploaded the whole parade as a print, as well as individual prints for each goblin. There's something very fu…

How to trust gpg keys via Travis Shears Personal Site October 27, 2023

After moving some GPG keys to a new computer I kept getting these trust warnings. It is NOT certain that the key belongs to the person named in the user ID.If you * really * know what you are doing, you may answer the next question with yes. Use this key a…

Generated by openring from webring