- Excessive helping in lock-free algorithm might actually do more harm e.g. increase memory contention
- Obstraction Free is a concept by Herlihy to not help in conflict but rather retry the operation through some sort of exponential backoff.
- more formally data structure is obstruction-free if it completes in a finite steps that do not involved contending with other operations for memory access.
Bridge gap betweeen formal definition and real performance.
A set of operations are disjoint-access parallel if and only if any pair of operation invocations which access disjoint sets of memory locations do not directly affect each others’ execution
Involved using a single shared lock which is known to the operating system, so contention will significantly affect performance under memory intensive workload.
- Multi-word Compare And Swap (MCAS)
- Software Transaction Memory (STM)
#Chapter 3
Data Structures especially concurrent ones increase performance / scalability but sacrifise reusability.
Multi-word CAS
- http://faculty.ycp.edu/~dhovemey/pubs/ecoop2002.pdf (Atmoic Instructions in Java)
- This papaer uses C/C++, refer to above for a java implementation