[c++] CAS 구현 및 ABA 문제 해결 :: ABA 해결_4. 그 외의 방법들

 

목차

1. 문제 정의
2. lock free 구현
3. ABA 해결
   1. int형 구현(+ Hazard pointer)
   2. Counter
   3. 그 외의 방법들
4. mutex lock(spin lock)과의 비교

그 외의 방법들

1. DCAS

   • _InterlockedCompareExchange128 사용

     위의 Counter 기법과 비슷하다. 64bit를 모두 이용하여 주소를 표현하는 CPU에서는 위의 Counter 기법을 사용할 수 없으므로 c++의 _InterlockedCompareExchange128 연산을 이용하여 이를 대신할 수 있다. 이 연산은 64bit 자료형 2개를 묶어서 128bit로 CAS 연산을 시행할 수 있다. 이 때 64bit 씩 분리하여 새로운 값으로 바꾸어줄 수 있다.

   • lock 변수 이용

     어셈블리어까지 보면 lock-free 기법도 결국 lock을 이용하지만, 코드 상에서 구현하기 위해 lock 변수를 사용하는 것은 lock기법과 다를 것이 없으므로 올바른 해결책이 아니다.

2. RCU

   데이터를 사용할 때 해당 데이터를 읽고(read) 복사해서(copy) 사용한다(use). 다른 쓰레드가 original data를 사용하고 있을 동안 기다리다가 original data를 사용하는 쓰레드가 없으면 복사한 데이터를 적용시킨다.

3. FreeList

   FreeList 2개를 이용하여 각각 push와 pop을 하는 용도로 사용한다.

=> 아무 스레드도 동작하지 않을 때, 두 List를 합해줘야한다.

4. LL, SC

   LL, CC 명령은 다른 스레드가 해당 자료형을 건드렸는지 안 건드렸는지를 가지고 연산의 성공 / 실패를 따지므로 해결 가능하다. 하지만 이 명령은 arm cpu에서 주로 가능하며 arm cpu를 쓰는 PC는 많지 않다.

적용 가능한 아키텍처

• ARM
• 68k
• Alpha
• ARM (ARMv6 ~ ARMv8)
• MIPS
• POWERPC

 

=> mutex와의 비교는 마지막 포스팅에