Lock-free programming และ CAS คืออะไร? อธิบายปัญหา ABA และเมื่อไรควรใช้

Lock-free programming ประสานงานระหว่าง thread โดยไม่ใช้ mutex ด้วยการใช้ลูป compare-and-swap (CAS) แบบ atomic เพื่อให้อย่างน้อยหนึ่ง thread คืบหน้าเสมอแม้ตัวอื่นจะค้าง ไม่มี thread ใดถูกบล็อกเพราะอีก thread ถือ lock ไว้

CAS

Compare-and-swap ตั้งค่าตำแหน่งหน่วยความจำเป็นค่าใหม่แบบ atomic เฉพาะเมื่อมันยังคงเป็นค่าเดิมที่คาดไว้; มิฉะนั้นจะล้มเหลวและคุณต้องลองใหม่ มันเป็น primitive ที่อยู่เบื้องหลัง stack, queue และตัวนับแบบ lock-free

CAS(addr, expected, new):
  if *addr == expected: *addr = new; return true   # atomic, indivisible
  else: return false

 old, next;
 {
    old  = value.get();
    next = old + ;
}  (!value.compareAndSet(old, next));