CAS

CAS(Compare-And-Swap)는 multithreading programming에서 사용하는 atominc instruction이다. 이 연산은 특정 메모리위치의 값이 주어진 값과 동일하다면 해당 메모리 주소를 새로운 값으로 대체한다. 이 연산은 atomic이기 때문에 새로운 값이 최신의 정보임을 보장한다. 만약 값 비교 와중에 다른 스레드에서 그 값이 업데이트 되어 버리면 쓰기는 실패한다. 간단히 bool을 리턴하기도 하고(compare-and-set), 메모리 위치에서 읽은 값(쓰인 값이 아님)을 리턴하기도 한다.

function cas(p: pointer to int, old: int, new: int) is
    if *p ≠ old
        return false

    *p ← new

    return true

CAS 연산의 원자성은 하드웨어 수준에서 보장된다. 이는 메모리에 대한 접근이 하나의 불가분의 단위로 처리되어, 연산의 일관성과 정확성을 유지하며, 다른 스레드에 의한 간섭을 방지한다. 이러한 특성은 멀티스레딩 환경에서 데이터 무결성을 보장한다.

헷갈리는 부분 CAS (Compare-And-Swap) 연산은 원자적으로 실행되는데, 이는 연산이 중간에 중단되거나 다른 연산에 의해 방해받지 않는다는 것을 의미한다. 그러나 이것이 CPU 제어권이 CAS 연산 동안 다른 스레드나 프로세스로 전환되지 않는다는 것을 직접적으로 의미하지는 않는다.(상관이 없는 것임)

Usage

CAS는 semaphore와 mutex를 구현하는데 사용되기도 하고 정교한 lock-free and wait free algorithm을 위해서도 사용된다. Maurice Herlihy(1991)은 CAS가 atomic read, write, fetch-and-add를 큰 메모리에 대해서도 수행될 수 있음을 증명했다. CAS를 이용해서 구현된 알고리듬은 전형적으로 key memory location을 읽고 old value를 기억한다. 이 old value에 기반하여 어떤 new value를 계산한다. 그리고서는 이 new value를 CAS를 사용하여 스왑을 시도한다. 스왑시에 비교되는 위치는 여전히 old value와 같을 것이다. 만일 CAS가 실패했다면 처음부터 다시 시도해야한다.

ABA problem

동시, 병렬 프로그래밍을 공부 하다가 보면 ABA Problem 이라는 현상이 등장한다. 간단히 이야기 하면, CAS(compare and swap) 연산과 관련하여 공유 객체(Shared Object)의 변경을 감지하지 못하는 현상을 말한다. 이것은 CAS 연산에 메모리 주소 혹은 레퍼런스를 사용하는 가운데, 메모리가 재사용되는 경우에 발생한다. 특히 메모리의 재사용 이라는 것은 현대의 대부분의 메모리 관리자가 사용하는 상당히 자연스러운 최적화 방법이기 때문에 동시, 병렬 프로그래밍 과 Lock-Free 알고리즘을 구현할 때는 꼭 고려해야 하는 사항이다.

간단히 말하자면 CAS(Compare And Swap)를 사용해서 자료구조의 아이템을 변경할 때, 포인터가 시스템에 의해 재사용되면서 생기는 문제다. 일단 CAS를 비교할 때 포인터 변수를 가지고 작업을 수행하기 때문에 결국 주소값을 비교하게 된다.

ABA problem 해결

1. DCAS(Double Compare And Swap)

2. Hazard Pointer

해제하면 안되는 위험한 포인터를 Hazard Pointer라하며, 주 내용은 다른 스레드가 해당 변수를 사용하고 있다면 메모리를 해제하지 않는것이다. 이렇게되면 MemoryManager는 메모리를 반환받지 못할것이고 메모리 재활용을 통한 ABA Problem은 발생하지 않을것이다.

CAS 명령어

1. x86 아키텍처

  • 명령어: CMPXCHG (Compare and Exchange)
  • 사용 예시: 
    CMPXCHG destination, source

    이 명령어는 목적지(메모리 또는 레지스터)의 값을 비교하여, 그 값이 누산기(accumulator, 보통 AX, EAX, RAX 레지스터)의 값과 같으면 소스(레지스터)의 값을 목적지에 저장합니다.

2. ARM 아키텍처

  • 명령어: LDREX (Load Register Exclusive) / STREX (Store Register Exclusive)
  • 사용 예시: 
    LDREX R1, [R2] CMP R1, R3 STREX R4, R0, [R2]

    여기서 LDREX는 메모리에서 값을 읽고, STREX는 조건이 충족될 때만 메모리에 값을 저장합니다.

번외) Lock과 CAS

Lock (락)

  • 목적: 여러 스레드 또는 프로세스가 동시에 공유 자원에 접근하는 것을 제어하기 위해 사용된다.
  • 작동 방식: 락을 사용하면 한 시점에 하나의 스레드만 특정 자원을 사용할 수 있다. 다른 스레드들은 락이 해제될 때까지 대기해야 한다.
  • 종류: 뮤텍스, 세마포어, 모니터 등 다양한 형태의 락이 존재한다.
  • 문제점: 데드락, 스타베이션, 우선순위 역전 등의 문제가 발생할 수 있다.

    Compare And Swap (CAS)

  • 목적: 낮은 수준에서의 원자적 연산을 제공하여 동시성 제어를 가능하게 한다.
  • 작동 방식: 세 가지 주요 요소(메모리 위치, 예상되는 원래 값, 새로운 값)를 사용하여, 메모리 위치의 값이 예상 값과 일치하는 경우에만 새로운 값으로 업데이트한다. 그렇지 않으면, 업데이트를 수행하지 않는다.
  • 특징: 락을 사용하지 않고도 동시성 제어가 가능하며, 데드락의 위험이 없다.
  • 문제점: ABA 문제, 루프 내에서의 성능 문제 등이 발생할 수 있다.

    차이점

    1. 동작 수준: 락은 보다 고수준의 동기화 메커니즘이며, CAS는 낮은 수준의 원자적 연산을 제공한다.
    2. 문제점: 락은 데드락과 같은 복잡한 문제들을 가지고 있으나, CAS는 ABA 문제나 루프 성능 문제 등 다른 유형의 문제를 가지고 있다.
    3. 용도: CAS는 세밀한 제어가 필요한 경우나 락을 사용할 수 없는 환경에서 유용하다. 반면, 락은 보다 일반적인 동시성 제어에 사용된다.
    4. 복잡성: 락은 구현이 비교적 간단하다.

references

https://en.wikipedia.org/wiki/Compare-and-swap https://m.blog.naver.com/jungwan82/20179129211 https://velog.io/@choiish98/CAS ABA https://blog.naver.com/jjoommnn/130040068875 https://chfhrqnfrhc.tistory.com/entry/ABA-Problem-1