[C] Lock-free 알고리즘

Lock-free 알고리즘은 멀티스레드 환경에서 동기화 메커니즘을 사용하지 않고 스레드 간 동기화를 달성하는 프로그램 기법을 말한다.

 

📌 핵심 개념

Lock-free 알고리즘은 CAS( Compare-And-Swap )이나 Load-Link/Store-Conditional 같은 원자적 연산을 사용한다.

이 연산들은 하드웨어 레벨에서 원자성을 보장하므로 락 없이도 데이터 일관성을 유지할 수 있다.

 

CAS 연산은 어떤 데이터를 비교하고, 해당 데이터가 같으면 값을 교환하고 true 또는 false를 반환하는 작업에 원자성을 보장한다.

if(memory_location == expected_value)
{
    memory_location = new_value;
    return true;
}
else
{
    return false;
}

 

📌 ABA Problem

CAS를 사용해 자료구조의 아이템을 변경할 때, 포인터가 시스템에 의해 재사용되면서 생기는 문제를 말한다.

예를 들어보자.

ThreadA, ThreadB, ThreadC가 있고,

{ 4, 3, 2, 1 } 순서로 네 개의 수를 삽입한 스택이 있다고 할때, ThreadA에서 pop을 해서 4를 빼고, 3을 top으로 지정하는 작업을 완료하기 전에, ThreadB에서 접근해서 pop을 2번 진행한후, ( { 2, 1 } ) ThreadC에서 push를 해서 4를 다시 넣은 후 ( { 4,2,1} ), ThreadA에서 CAS를 하면 ThreadA에서는 4가 맨위에 있기 때문에 아무런 문제가 발생하지 않은 것처럼 보인다. 따라서 3을 top으로 만들게 되는데, 3은 이미 제거된 데이터이기 때문에 3을 top으로 보면 안된다.

이와 같은 문제가 대표적인 ABA Problem이라고 할 수 있다.