Lock-free programming và CAS là gì? Giải thích vấn đề ABA và khi nào nên dùng.

Lock-free programming phối hợp các thread mà không dùng mutex, dùng vòng lặp atomic compare-and-swap (CAS) sao cho luôn có ít nhất một thread tiến triển ngay cả khi những thread khác đình trệ. Không thread nào bị chặn bởi một thread khác đang giữ lock.

CAS

Compare-and-swap đặt một vị trí sang giá trị mới một cách atomic chỉ khi nó vẫn giữ giá trị cũ như kỳ vọng; nếu không thì thất bại và bạn thử lại. Đây là primitive nền tảng cho stack, queue và counter lock-free.

CAS(addr, expected, new):
  if *addr == expected: *addr = new; return true   # atomic, bất khả phân
  else: return false

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