TIL) CAS는 대체 머야

CAS 알고리즘은 매번 학습을 해도 다시 잊게 됩니다.

잊어서 다시 공부하려고 복습을 했습니다.

머리속 끄집어내기

CAS 알고리즘을 정리해보겠습니다.

What

CAS 알고리즘은 임계 영역을 사용할 때 동기화 문제를 해결하는 방식입니다.

Why

Lock 방식의 오버헤드와 성능 저하를 줄이면서 동시성 문제를 해결하기 위해서입니다.

When

많은 스레드가 임계영역에 동시에 접근하려고 할 때입니다.

Where

운영체제 커널이나 애플리케이션 또는 프로그래밍 수준에서 사용합니다.

Who

하드웨어 CPU의 저수준 연산자

How

메모리 위치와 예측한 값으로 일치하는 경우 변경할 값으로 수정하며 수정결과를 반환합니다.

한줄 정리하기

CAS 알고리즘은 임계 영역을 사용할 때 발생할 수 있는 동시성 문제를 해결하는 방법 중 하나로 Lock 방식의 오버헤드와 성능 저하를 줄일 수 있습니다. 많은 스레드가 동시에 접근할 때 사용하며 운영 체제 커널이나 애플리케이션에서 사용하며 하드웨어 CPU의 저수준 연산자를 통해 메모리 위치와 예측한 값이 일치하는 경우 예상한 값으로 변환되기 때문입니다.

CAS 알고리즘의 문제

• ABA 문제
• 스핀락 문제
• 단일 변수에만 적용 가능

ABA 문제

What

CAS 알고리즘과 같이 수정하려는 데이터의 현재 값과 변경할 값만 가지고 비교하게 되면 발생하는 문제를 말합니다.

CAS 알고리즘처럼 값의 동일성만을 기준으로 원자성을 판단하는 연산에서 값이 A → B → A 로 바뀌었음에도 불구하고 변화가 없다고 판단되는 동기화 오류를 말합니다.

Why

CAS 알고리즘은 현재 값과 변경할 값만 비교하므로 자료 구조나 그외 상황에서 다른 객체의 값이 수정될 수 있기 때문입니다.

CAS는 메모리의 중간 변경 이력은 감지하지 못하고, 오직 현재 값을 기대한 값과 같은지만 비교하기 때문에, 값이 바뀌었다가 다시 돌아오는 경우에도 성공 처리될 수 있습니다.

When

스레드가 CAS 연산을 하기 전에 다른 스레드가 해당 메모리를 변경 후 다시 원래 값으로 되돌리는 상황에서 발생합니다.

Where

멀티스레드 환경에서 CAS 오브젝트를 공유하는 경우 발생합니다.

멀티스레드 환경에서 공유 자원에 대한 락프리 구조(예: Concurrent Stack, Queue)**를 구현할 때 주로 발생합니다.

Who

다른 스레드가 발생 시킵니다.

CAS를 실행하는 스레드 자신은 ABA를 감지할 수 없고, 다른 스레드가 값을 바꿨다가 다시 되돌림으로써 ABA 문제를 유발합니다.

How

CAS 알고리즘으로 동시성 제어를 하고 연결리스트로 구현된 큐 자료구조를 사용한다고 할 때 발생할 수 있습니다.

큐 : [head] > [A] > [B] > [null]

스레드1:

1. front.next 는 [A] 로 확인합니다.
2. [A].next는 [B]로 확인합니다.
3. [A]를 poll() 하기 위해 front.compareAndSet([A],[B])

3번이 실행되기 전에 컨택스트 스위칭이 발생합니다

스레드 2:

1. 큐.poll()로 [A]를 꺼냅니다.
2. front.next는 [B]이며 또 poll()을 하고 [A]를 넣고 [C]를 넣습니다.

스레드 1의 3번이 실행되면서 큐 자체에 순서가 엉망이 됩니다.

정리

ABA는 CAS 알고리즘처럼 메모리 위치와 예측한 값이 일치하면 연산이 가능하도록 하여 그 사이 데이터가 오염되어도 변화가 없다고 판단하는 동기화 오류 문제가 있습니다. 멀티스레드 환경에서 임계 영역에 접근하여 CAS 알고리즘을 수행하기전 데이터가 수정되고 예측한 값으로만 변경된다면 변경 기록은 확인하지 않는 문제가 있습니다.

정리

CAS 알고리즘을 언제 사용할지 유사 CAS 알고리즘은 실무에서 어떻게 사용하는지, 그리고 CAS 알고리즘의 ABA 문제는 어떤 구조로 해결했는지 간단하게 정리하려고 합니다.

ABA를 해결하는 방법은 버전 추가와 마킹 방법입니다.

데이터를 읽을 때 버전을 읽고 수정할 때 버전을 올리게 됩니다.

CAS알고리즘의 한계는 데이터를 수정하는 동안 발생한 변경 이력이 무시된채 현재 값만 일치하면 되는 문제를 버전이나 마킹 처리로 해결할 수 있습니다.

또는 이벤트 루프처럼 변경하는 작업을 단일 스레드에서 처리한다고 한다면

Lock과 CAS 알고리즘은 어떤 차이가 있을까 생각해보면

프로그래밍 언어 수준의 Lock은 낮은 동시성과 복잡한 로직, 그리고 동시성 제어를 프로그래밍 레벨에서 알아서 해준다는 장점이 있습니다.

높은 동시성이 발생하고 임계구역의 지연시간이 길다면 오히려 Lock이 CAS보다 유리할 수 있습니다.

이유는 Lock이 걸리면 컨택스트 스위칭과 스레드를 깨우는 작업의 연산이 필요하지만 한번 대기 된 이후로는 CPU 자원을 사용하는 동기 I/O와 유사한데

CAS 알고리즘은 비동기 I/O와 유사합니다. 한번 시도해보고 실패하면 재시도를 하는 과정이 발생하게 됩니다.

이런 과정의 속도를 제어하거나 별도의 락을 사용하여 리트라이는 다른 스레드가 알람으로 깨워주면 시도하게 하는 방법도 있습니다.

CAS 알고리즘은 분산 서버에서도 활용할 수 있습니다.

이중화된 서버나 MSA 환경에서도 해당 CAS 알고리즘의 원리와 ABA 문제를 해결하기 위한 버전 관리를 통해 동기화 문제를 해결할 수 있습니다.

레디스나 별도의 서버를 활용하여 현재 값과 변경하려는 값을 확인하고 버전을 통해 ABA 문제를 해결할 수 있습니다.