CS (Computer Science) - Compare And Swap (CAS)

멀티 스레드 환경에선 동기화를 달성하기 위해, lock을 보통 사용하곤 한다.

하지만, lock을 사용하는 경우 오버헤드가 발생하기도 하고 데드락의 문제도 발생할 수 있다.

 

성능상 이점을 보기 위해 사용하는 것이 멀티 스레딩인데, 오히려 성능을 저하시킨다면 상당히 잘못된 설계라고 할 수 있을 것이다. 이 때문에, lock을 사용하지 않고 프로그램을 설계하고자 하는 것을 lock_free라고 한다.

 

lock_free를 달성하기 위해 사용되는 알고리즘 중 하나가 CAS이다.

 

CAS

어떠한 변수의 값을 읽고 쓰는 연산을 할 때, 스레드는 자신의 스택 영역에 해당 변수를 저장하게 된다.

그리고, 스택 영역의 데이터를 기반으로 연산을 진행항 뒤 메인 메모리에 쓰기 작업을 함으로써 작업을 마치게 된다.

 

하지만, 멀티 스레딩 환경에선 문제가 발생할 수 있다. 스레드의 스택 영역에 저장된 값을 기반으로 연산을 하는 동안 다른 스레드가 메인 메모리의 값을 바꿔버렸다면 결과값이 기대값과 달라질 수 있기 때문이다.

 

CAS는 이를 탐지한다. 스레드의 스택영역에 저장되어 있는 변수의 값이 메인 메모리에 저장되어 있는 값과 동일한지를 판단한 후, 동일하다면 그 때 쓰기 연산을 실행하는 것이다.

 

ABA 문제

CAS는 lock_Free를 달성하기 위해 자주 사용되는 방식이지만, ABA 문제를 일으킬 수 있어서 주의가 필요한 알고리즘이라고 한다.

 

ABA 문제는 그림을 보며 이해해보자.

 

 

이런 스택이 있다고 해보자. A,B,C,D 총 4개의 데이터를 가지고 있는 스택이며 top은 A이고 next는 B이다.

 

이 때, 2개의 스레드가 있다고 해보자.

1번 스레드는 pop() 연산을 1회 진행할 것이며, 2번 스레드는 2번의 pop()과 1번의 push()작업을 진행할 것이다.

2번 스레드가 1번 스레드보다 훨씬 빠른 상황이라고 가정할 것이다.

 

스레드 1이 pop을 하기 전에, 스레드 2가 모든 작업을 마친다고 한다면, 아래와 같은 순서로 스레드 2는 작업을 할 것이다.

 

A, B를 pop하였고, 다시 A를 push하여 스택의 원소는 3개이며 top은 그대로 A인 상황이다.

 

이 때, 1번 스레드에서 작업을 하려고 한다면?

 

스레드의 스택 영역에 저장되어 있는 top과 메인 메모리의 top이 동일하기 때문에, CAS결과 문제가 없다고 판단하여 pop연산을 진행할 것이다. 하지만, 실제로는 스택 내부의 값이 달라져있다.

 

스레드 1에선 top()인 A를 pop()하면서 next()인 B를 top()으로 설정할 것이다.

하지만, 메인 메모리에는 B가 존재하지 않는다. 해당 작업이 끝난 뒤, 메인 메모리에서 스택의 top()에 접근하면? 치명적인 오류가 발생할 것이다.

 

이 것이 ABA 문제이다. 단순히 값이 같냐 다르냐 이것만으로 판단하기엔 위와 같은 문제가 발생할 여지가 있다는 것이다.

 

ABA 문제를 해결하기 위해, Doble CAS나 Hazard Pointer와 같은 기법을 사용한다고 한다.

해당 기법은 다른 게시물에서 별도로 정리해보아야 할 듯 하다.