estudy 한국어/English

CAS와 ABA 문제

1,865 단어·4 분·원문(.md)

뮤텍스나 세마포어는 누군가 lock을 쥐고있으면 다른 스레드들은 대기열에서 잠들어야한다. (context switching 발생 -> 엄청난 오버헤드)

이를 해결하기 위해 등장한 것이 lock-free 즉 락 없이 동기화를 맞추는 CAS 이다.

CAS는 cpu가 제공하는 원자적 명령어로 작동 논리는 다음과 같다.

  1. 메모리 위치 V 의 값을 읽어온다. (내가 기대하는 기존값 E)
  2. 내가 계산한 새로운 값 N으로 업데이트 시도한다.
  3. 이때 현재 메모리 V 값이 내가 아까 읽었던 기대값 E와 여전히 같은가를 비교한다.
  4. 만약 같다면, 아무것도 건드리지 않았다는 뜻이므로 새로운 값으로 교체한다.
  5. 만약 다르다면, 내가 계산하는 동안 다른 스레드가 값을 가로채서 바꾼 것이므로 업데이트를 포기한다. (실패 후 보통 처음부터 다시 시도함.)

이 과정이 중간에 끊기지 않고 cpu 단에서 한 큐에 실행됨을 보장한다.

// CAS 명령어의 논리적 동작을 C 코드로 표현한 의사코드 (실제론 하나의 CPU 명령어로 동작)
bool CAS(int *memory_location, int expected_value, int new_value) {
    if (*memory_location == expected_value) {
        *memory_location = new_value;
        return true;  // 성공
    }
    return false; // 누군가 중간에 값을 바꿨음! 실패!
}

ABA 문제 #

CAS 는 값이 예전이랑 똑같다고 판단하면 아무것도 건드리지 않았으니 업데이트를 한다로 동작하는데, 이 전제는 완벽하게 틀릴 수 있다.

값이 똑같다고 해서 아무것도 건드리지 않은 것은 아니기 때문이다.

  1. 스레드 1이 공유 변수에서 값 A를 읽어오고 이걸 C로 바꾸려한다.
  2. 갑자기 os 스케줄러에 의해 스레드 1이 멈춘다. premmeted
  3. 스레드 2가 난입해서 공유 변수값을 A에서 B로 바꾼다.
  4. 스레드 2가 다시 변수값을 B에서 A로 원상복구 해놓는다.
  5. 스레드 1이 깨어나서 CAS를 실행한다 현재값이 내가 아까 읽은 A가 맞는지 확인하고 지금 기준으론 맞으니 C로 바꾼다.

단순히 숫자 카운터라면 값이 같으니 넘어가도 무방하지만, 포인터 메모리 주소를 다루는 자료구조 List, Stack 같은게 이런 문제가 있었다면?

주소값 A가 가리키는 메모리가 중간 해제되어 다른 주소로 재할당된 문제가 생긴다면? 껍데기 이름표 A만 같지 내용은 완전히 망가진 쓰레기 값이 되버린다면 CAS는 이걸 통과시켜버리는 것이다.

이 문제를 막기위한 가장 대표적인 해결책은 값에 시퀀셜한 버저닝이나 타임스탬프를 꼬리표로 붙이는 것이다.

단순히 A인지만 확인하는 것이 아니라 A와 버전 1인지를 확인한다. 이를 Double-word CAS라고 부른다.

  • 스레드 1이 A v1을 읽고
  • 스레드 2가 B v2로 바꿨다가 A v3로 바꾼다.
  • 깨어난 스레드1이 CAS를 시도했다가 현재값이 A v1이 아니라 A v3것을 보고 CAS가 실패하게 된다.

CAS의 한계 #

cas는 락을 사용하지 않고도 동시성 제어를 할 수 있는 강력한 메커니즘이지만 만능은 아니다.

특히 스레드간 경합 contention이 심해질 때 치명적인 단점들이 존재한다.

ABA 이외에도 더 알아보면

cpu 자원 낭비 busy waiting #

CAS 명령어 자체는 한 번 성공하거나 실패하거나 끝난다.

따라서 원하는 값을 업데이트 하려면 성공할 때까지 계속 재시도하는 while 루프 안에서 cas를 호출해야하는데 이를 스핀락이라고 부른다.

문제점은 스레드 100개가 동시에 하나의 변수를 수정하려고한다면? 1개만 성공하고 99개는 실패한다. 이 99개의 스레드들은 대기 상태로 들어가는것은 아니지만 cpu 100을 점유한채 계속해서 while 루프를 돌며 cas를 재시도한다. 엄청난 cpu 사이클 낭비가될 수 있다.

멀티 코어 환경에서 캐시 일관성 트래픽 폭주 cache ping-pong #

현대의 멀티 코어 cpu는 각 코어마다 고속의 L1/L2 캐시를 가지고 있다. CAS 명령어가 실패하든 성공하던 메모리 값을 비교하여 수정하려는 시도 자체가 cpu 내부 버스에 막대한 트래픽을 유발한다.

문제점은 여러 코어가 동일한 메모리 주소에 CAS를 시도하면 하드웨어는 데이터의 일관성을 맞추기 위해 특정 코어의 캐시 데이터를 강제로 무효화하고 다른 코어로 데이터를 전송한다. 이 과정이 코어들 사이에서 탁구공처럼 왔다 갔다 한다고해서 캐시 핑퐁이라 부르며 심할 경우 메모리 대역폭이 꽉차 시스템 전체가 느려진다.

Starvation 및 불공정성 #

기아 상태인데 os가 관리하는 뮤텍스나 세마포어는 보통 대기열 큐를 만들어 순서대로 락을 할당해주는 공정성을 어느정도 보장할 수 있다.

문제는 CAS 루프에는 순서가 없고 그저 타이밍 좋게 cas 명령어를 수행 시점 값이 일치하는 스레드가 먹게되는건데, 운이 나쁜 특정 스레드는 다른 스레드들이 계속 값을 바꿔버리는 바람에 무한정 cas에 실패하여 영원히 업데이트를 하지 못하는 기아 상태에 빠질 수 있다.

단일 변수(주소) 조작의 한계 #

가장 구조적인 한계고, 하드웨어가 제공하는 CAS 명령어는 한 번에 단 하나의 메모리 주소 일반적으로 32, 64비트 크기에 대해서만 원자성을 보장한다.

문제점은 만약 은행 계좌 이체처럼 a계좌에서 출금하고 b계좌로 입금 하는 두 가지 분리된 메모리 영역을 동시에 업데이트한다면 일반적인 cas 명령 하나로만은 원자성 보장이 힘들다.

이를 해결하기위해 굉장히 복잡한 락프리 자료구조를 설계하거나 소프트웨어 트랜잭셔널 메모리같은 고급 기법을 도입해야하므로 구현 난이도가 급격히 상승한다.

Operating-System/casaba.md