Lock-free, cas

참조 : http://www.gamedevforever.com/83

---

- Lockfree algorithm
Lockfree 알고리즘을 이해하기 위해서는 먼저 Atomic Operation에 대해서 알아볼 필요가 있습니다.

atomic operation의 정의
1. 일련의 모든 연산이 끝날 때까지 다른 프로세스는 그 연산에 대한 어떠한 변화도 할 수 없다.
2. 전체 연산 중 어느 하나라도 실패할 경우, 모든 연산은 실패하여, 시스템은 전체 연산이 시작하기 전의 상태로 복구된다.

32비트 인텔 CPU (IA-32)에서 지원되는 Atomic Operation에 관해 알아보자. 다음과 같은 인텔의 CPU 연산들 앞에 LOCK을 붙여 해당 연산을 Atomic하게 만들 수 있다. 즉, 스레드간의 동기화를 신경쓰지 않아도 된다. 자세한 것은 인텔사 웹싸이트에서 제공되는 개발자 매뉴얼을 참고하기 바란다.

ADD, ADC, AND, BTC, BTR, BTS, CMPXCHG, CMPXCH8B, DEC, INC, NEG, NOT, OR, SBB, SUB, XOR, XA

 
Win32의 Atomic Operation은 Interlockedxxx() 함수로 제공된다. 


간단하게, 차이를 살펴보면 다음과 같다.
  // atomic하다.
  GlobalCounter = 0;   


  // 이것은 atomic하지 않기 때문에, 멀티 쓰레드에서는 결과를 예측할 수 없다.
  ++GlobalCounter;      


  // atomic incremenet
  InterlockedIncrement(&GlobalCounter);

Lock-free는 Spinlock과 유사하게 작업을 완료하는 내부적으로 루프를 돌면서 재시도를 하는 방식입니다.
Lock-free 알고리즘에서는 비교 후 교환(Compare-And-Swap)이 가장 중요합니다. 그 이유는 Lock-free 에서는 Lock을 사용하지 않기 때문에, 다른 쓰레드가 이미 그 변수의 값을 변경했을 수가 있습니다. 물론, 발생 확률은 대체로 낮으므로, 변경되지 않았을 것이라고 가정하는 낙관적인(Optimistic) 방법이 Lock-free에 사용됩니다. 따라서, CAS(Compare-And-Swap: InterlockedCompareExchange)을 이용해서, 공유변수가 가정하는 값과 같으면 다음 단계로 넘어가고, 만약 변경되었다면, 재시도하는 방법으로 Lock 없이 동기화가 가능하도록 프로그래밍을 할 수 있습니다.
(즉, InterlockedCompareExchange(&v, b, a) 라는 함수를 보면, v의 값이 a와 같다면, v에 b를 대입하라는 의미입니다. 리턴값은 v가 값이 바뀌기 전의 v의 값을 나타냅니다.)

간단하게, Stack Push에 대한 예제를 보도록 하겠습니다.

1. void Push(Node* pNewNode)  
2. {  
3.  do {  
4.    Node* t = pTopNode;  
5.    pNewNode->pNext = t;  
6.  } while( !CAS(&pTopNode, t, pNewNode) );  
7. }  

코드에 대한 설명을 추가하자면...

pTopNode 는 다른 프로세스에 의해서 계속해서 변경될 수 있다.

pTopNode 와 t 를 연결시키고, new node 의 next 를 t 에 연결시키므로,

new node -(next)-> pTopNode 가 되도록 한 후에,

CAS 로 pTopNode 가 여전히 t인지 검사한다.

동일하다면, pNewNode 가 topNode 가 되고,

다른 프로세스에 의해 바뀌었다면 이 과정을 다시 수행해 준다.

CAS 의 예제는 다음과 같다.

int compare_and_swap(int* reg, int oldval, int newval)

{
    int old_reg_val = *reg;
    if (old_reg_val == oldval)
        *reg = newval;
    return old_reg_val
}

[출처] Compare and Swap(CAS)|작성자 fastbird

출처 : http://blog.naver.com/jungwan82?Redirect=Log&logNo=20179129211

cas ( compare and swap )

비교하고 같으면 둘이 바꾼다.

cas( a,b c ) -> a랑 b랑 같으면? a를 c로 바꾼다.

 

* cas는 원자성이 보장된다. ( 단순한 if a==b { a=c } 가 아님 ), ( x86에서 cmpxchg 인스트럭션으로 구현 )

 

 

락프리는 마법이 아니다. -> 단순히 될 때 까지 계속 시도하는것.

 

while( true ){ node *ptr = top_ptr; node *next_ptr = ptr->next; if( cas(top_ptr, ptr, next_ptr) ) break; }

( 간단한 락프리 스택에서 top 포인터를 바꾸는 코드 )

 

5번째줄의 cas에서 top_ptr과 ptr이 다르다는것은 2,3번째줄을 실행하는 도중에 스위칭이 일어나서 다른 스레드가 top_ptr을 바꾸고 갓다는 것,

따라서 top_ptr을 변경하지 않고 루프 안의 코드를 한번 더 실행한다. ( 아무한테도 방해받지 않고 작업이 완료될 때 까지 계속 반복 )

[출처] 락프리 (lockfree)|작성자 Anz

출처 : http://pjc0247.blog.me/80209850983

ABA 문제
CAS를 사용한 어떤 알고리듬은 false positive match 혹은 ABA 문제라고 불리는 문제에 영향을 받기 때문에 적절한 핸들링이 필요하다. 이것은 old value가 읽히는 시간과 CAS가 시도되는 시간 사이의 차이 때문에 발생한다. 어떤 프로세서나 스레드들은 그 메모리 위치를 2번 혹은 그 이상 변경하는데 그렇게 함으로써 old value와 일치하는 bit pattern이 만들어지는 경우가 있다. 문제는 이 new bit pattern이 old value와 같은 bit pattern을 가지지만 다른 뜻을 포함하고 있을 때이다. 예를 들어 재 사용된 주소이거나 포장된 버전 카운터일 수 있다.

이 문제에 대한 일반적인 해결책은 두배 길이의 CAS를 사용하는 것이다. 예를 들어 32 bit system에서는 64bit CAS를 사용. second half는 카운터를 저장한다. 연산에서 비교되는 파트는 이미 읽혀진 값과 카운터를 현재 포인터와 카운터이다. 그들이 일치한다면 swap이 발생하고 new value가 써진다. 그리고 new value의 카운터는 증가한다. 이렇게 하면 ABA문제가 발생하더라고 카운터가 다르기 때문에 다른 값임을 판별 할 수 있다.

다른 대안으로는 DCAS를 지원하지 않는 CPU들에서 유용한데 freelist로의 index를 사용하는 것이다. fullpointer로의 index 대신에. 예를 들어 32 bit CAS는 16bit index와 16bit counter를 사용한다. 하지만 줄어든 counter 길이 때문에 ABA 문제가 발생할 확률이 증가한다.

다른 테크닉으로는 하나의 ABA 카운터를 전체 데이터 구조에 사용하는 대신에 각 데이터 구조체 마다 별도의 ABA Counter를 저장하는 것이다.

더 복잡하지만 더 효율적인 방법으로는 SMR, Safe Memory Reclamation 알고리듬을 구현하는 것이다. 이것은 일종의 lock-free garbage collection이다. SMR을 사용할 때 얻는 이점은 주어진 포인터 주소가 오직 한번만 존재하게 된다는 것이다. 그러므로 ABA 문제가 완전히 해결된다. SMR 이 없다면 freelist가 사용되어야 하는데 이것은 데이터 엘레멘트가 존재하지 않더라도(해제되어도) 안전하게 데이터 요소에 접근하기 위해서이다. SMR이 있다면 이것이 필요없다.

[출처] Compare and Swap(CAS)|작성자 fastbird

lockfree stack 의 구현

void push(int t) {

Node* node = new Node(t);

do {

node->next = head;

} while (!cas(&head, node, node->next));

}

bool pop(int& t) {

Node* current = head;

while(current) {

if(cas(&head, current->next, current)) {

t = current->data; // problem? 

return true;

}

current = head;

}

return false;

}