[multiprocessor programming] types of synchronization.

Coarse-grained synchronization: 
Lock the whole object while accessing each it's methods.

• Not scalable
• Ok for levels of concurrency are low.
• interface:
• add , lock whole list
• remove, lock whole list

    
Fine-grained synchronization: 
Provide each data member it's own lock.

• interface:
• add: lock couple nodes. 
• Use lock coupling. i.e during add between a, b. First we need to
  lock a, then b.
  All methods MUST acquire locks in the same order.
  Each lock must be 'hand-over-hand' style, must lock in couple.
• Reasoning is simple. Multi-thread adding nodes between a, b could
  cause problem.
• remove: lock couple nodes.

Optimistic synchronization: 

• Search without requiring any lock.
• While find the data member, lock it, and check if the data member not being modified
  since previous search. If every time during the lock data member has changed, it's
  not good for this method. This method is good for less change during the lock of
  data member.
• interface:
• add: search the list without lock.
  find the place valid for add, then lock pred, curr nodes.
  Check the locked nodes are still the same value during the previous search.
  Actually, just make sure the curr is larger than the input node is enough if don't care
  about sorting.
  Or do the sorting later.
• remove: same as add.
• contains: search the key without lock. While locating the key, lock pred, curr nodes, make sure the nodes contain the value with previous search. If not, re-searching again.

     
Lazy synchronization:

•  Postponing the efforts. Make into 2 phase commit.
  First, logically remove the data member by setting a tag bit.
  Secondly, physically remove it from the data structure, this time, we give a
  lock.
• interface:
• contain: a wait-free traversal. Only check if the node exists and not marked.
  In order to have contain wait-free, add/remove MUST to have the 'mark' variable assign as atomic.
  Node.next assign as atomic.
• add: introducing a 'mark' variable into the Node struct. During the first search,
  either can not find the node or finding the node is 'marked', consider the node
  does not exist in the list.
  While found  the node, lock pred, curr nodes, validates it, if pass the validation, insert the node.
• remove: 4 steps: 
• search for the node to remove, no lock needed.
  (all belowing steps are under pred, curr lock)
• while found, validate the finding.
• mark the removing node. This logically removes the node.
• redirect pred's next field. This physically removes the node.
• validation:  Does not traverse the whole list as previous methods.
  Just test if the node is marked or not and the value remains the same as previous (before lock) search.

     
Nonblocking synchronization:

• Most hard to implement. Not necessarily better than locking, since
  a RMW still forming a loop. Beware of ABA issue.
  Reference:
  Load-link/store-conditional
• interface:
• Base on Lazy synchronization, we tend to make add/remove lock-free by using RMW.
  BUT it won't work!
  Why? Because while applying RMW on pred's next field for removing curr,
  another thread  could apply RMW on curr's next field, it turns out that the second thread's adding won't work.
  We should group next and mark fields together as a atomic change.
  Introduce "find" member function.
  This function will use RMW to physically remove the node.
  Then continue finding the key. Return a position object which includes pred, curr, and
  the insertion key is in between.
• add: will call 'find' in the while loop. Continuously testing the finding to insert the key.
  That is to say, although there's no lock, however, if RMW fails, it will loop again and again
  till the condition satisfies.
• remove: same as add. Calling 'find' in the while loop. Mark the to be removed key.
  Let the 'find' to physically removes it.
• contain: same as Lazy synchronization.

     
Concurrent Reasoning:

• Finding the invariant. Properties that always hold.

1. Property holds when the object is created.
2. Once the property holds, then no thread can take a
   step that makes the property false.

• there are

1. insert
2. remove
3. contain
4. validation

 member functions that could modify the object's data member state.


Look out steps:   

• define data members.     e.g Sentinels nodes.
• Beware of dead-lock and starvation.

Definition:
A method is wait-free if it guarantees  that every call finishes in a finite number
    of steps. (Strong)
A method is lock-free if it guarantees that some call always finishes in a finite number
    of steps. (Weak)