[24.03.15] Lock Free 자료구조 Issue

[Lock Free 자료구조 구현 Intro]

락-프리 자료구조의 성능이 다른 동기화 객체 더불어 활용되는 자료구조보다 더 우월한가 아닌가는 프로그램의 경향성을 파악해야 하며, 성능 분석을 통해 결정할 수 있는 선택 사항이다.

락-프리 자료구조 구현의 이유는 설계와 구현의 과정에서 발생하는 동기화 이슈들을 맞닥뜨리며, 여러 디버깅 기법을 통해 해결해 나가고자 하는 것에 의의를 두었다.

• 락-프리 구조를 어떻게 만들어야 thread-safe 할 수 있는지 파악. 이러한 경험을 바탕으로 일반적인 멀티-스레딩 프로그래밍 작성 시 임계 영역 설정과 동기화 객체 활용에 수월하기를 기대한다.
• 구현 및 테스트 과정에서 발생되는 동기화 오류 등을 맞닥뜨리고, 메모리 분석, 로그 기록 등 다양한 디버깅 기법을 적용하여 문제를 해결해나가는 능력 수립

 

[Lock Free 자료구조 의의]

락-프리 스택이나 큐에 대한 동기화 작업은 'push', 'pop' 작업의 모든 과정에서 필요한 것이 아니고, 일련의 과정 중 스레드 간 경합이 발생할 지점만을 파악하고, 원자적 연산과 더불어 스레드 경쟁을 제어하는 것과 같다.

즉, 스레드 개별적으로 동작할 수 있는 부분은 동기화 없이 처리하되, 실제 동기화가 필요한 '커밋(commit)' 단계에서만 동기화를 수행하여, 전체적으로 보면 자료구조의 접근 및 활용에 있어 thread-safe를 보장하는 것이다.

 

['Spin Lock' vs 'Lock Free']

• Spin Lock
  
  • 커밋 전 단계인 사전 단계까지 포함하여 임계 영역으로 설정하여 spin loop를 도는 것
  • 임계 영역에 대한 접근 제어는 InterlockedExchage 동기화 함수와 더불어 락 변수 역할을 하는 일종의 플래그 변수와 함께 구현할 수 있다.
• Lock Free
  • 스레드 간 공유 자원에 대한 경합이 존재하지 않는 단계에서는 각자 스레드가 알아서 로직을 수행한다.
  • 커밋 단계에서만 동기화를 수행한다.
  • 동기화 객체를 직접적으로 사용하진 않고, Interlocked 계열 함수와 함께 자료구조 내부 멤버에 대한 원자적 연산을 통해 스레드 경합을 회피한다.

[Lock Free 장단점 견해]

• 장점
  • 커밋 이전의 공유 자원과 관련이 없는 로직을 먼저 수행한다. 그리고 이 단계의 수행 후 곧바로 공유 자원 접근 및 갱신이 이루어질 수 있다. 스핀-락의 경우 커밋 단계 전후에 대한 분리 없이 전체의 로직을 임계 영역으로 두어 Fing-grained한 락을 작는다. 결국 상황에 따라 다르겠지만, 동일 스레드, 동일 삽입 작업 워크로드로 둘 때 락-프리 자료구조에 대한 작업의 결과 반영이 더 많아지지 않을 까이다.
  • 공유 자료구조에 대한 삽입/삭제를 단순히 동기화 객체로 제어를 한다하면, 락 획득 불가 시 블록 상태가 될 것이다. 이 경우 자신 스레드의 타임 슬라이스를 포기하고, 이 후 다시 ready 상태로 돌아와 락 획득 시도하는 등 락 획득 시도의 기회자체가 단위 시간동안 떨어진다고 본다.
• 단점
  • 다른 동기화 객체와 비교할 때 스핀-락에 더 가깝다. 구태여 락을 오랫동안 획득할 수 없는 상황이라면 블록 상태가 되어 코어 자원을 낭비하지 않는 것이 좋을 것이다. 

이러한 장점과 단점은 상황에 따라 다르게 발현될 것이고, 결국 프로그램 경향성의 파악 그리고 성능 분석을 통한 적절한 동기화 기법 선택이 필요한 것이다.

(스핀-락과 일반적인 동기화 객체를 통한 동기화의 중간 타협점 느낌...?)

 

[Stack 자료구조와 Lock Free 적용 가능성]

https://lumian2015.github.io/lockFreeProgramming/lock-free-stack.html

위 그림을 기반하여 스택의 Enqueue 함수는 간단하게 아래와 같은 형태일 것이다.

Enqueue(X) {
    // 새로운 노드 생성
    Node* newNode = new Node();
    newNode.Value = X;
    newNode.Next = NULL;
    
    // 스택에 추가 
    // (실질적으로 공유 자원인 스택에 접근하여 영향을 주는 코드)
    newNode.Next = Head;
    Head = newNode;
}

 

이 코드에서 새로운 노드가 자료구조에 추가되는 코드는 임계 영역이다. 별도의 동기화가 없다면 thread-safe하지 못하다. 

락 프리 스택은 이 임계 영역에 해당하는 부분에만 '커밋' 단계를 두어 동기화를 수행한다.

 

커밋 단계의 '진입 시점'과 '판단 시점'에서 자료주고 상태와 변화를 파악한다. 여기서 변화는 다른 스레드의 수행 결과이다.

스택의 경우 자료구조를 변경한다는 것은 결국 'Head' 멤버를 갱신하는 것이다. '진입 시점'에는 현재 Head를 캡쳐한다고 표현하고, 커밋 단계의 '판단 시점'에서의 Head와 일치성을 확인한다. 만약 일치한다면 Head의 갱신을 자신 스레드가 준비한 새로운 노드를 기반으로 수행한다. 

 

중요한 것은 이 비교와 갱신을 수행하는 커밋 단계가 '원자적'으로 수행되어야 한다는 것이다. 흔히 'CAS(Compare And Exchange)'라 불리는 연산을 원자적으로 수행함을 의미하는데, 이는 InterlockedComapreAndExchange API를 활용하여 코어 연산 레벨에서 원자성을 보장하도록 요청한다. 

// PUSH 커밋 단계(비교와 갱신)
Node* oldHead;
do {
    oldHead  = Head;
    newNode->next = oldHead;
} while(oldHead != InterlockedCompareExchangePointer((PVOID*)&Head, (PVOID)newNode, (PVOID)oldHead));


// POP 커밋 단계
Node* oldHead;
Node* nextNode;
do {
    oldHead = Head;
    nextNode = oldHead->next;
} while(Head && Head != InterlockedCompareExchangePointer((PVOID*)&Head, (PVOID)nextNode, (PVOID)oldHead));

// POP 정리
if(oldHead != NULL) {
    data = oldHead->data;
    delete oldHead;
    return true;
}
else {
    return false;
}

 

 

[LockFree 구현 시 발생 이슈]

1.  ABA 문제

CRT에서 제공하는 new/delete 동적 할당에서 문제가 기인된다. new/delete는 내부적으로 malloc/free를 활용할 수 있다. 문제는 malloc/free 과정에서 주소가 재활용될 수 있다는 것이다. 주소가 재활용되는 것은 CRT 코드에서 성능 향상을 위해 수행하는 내부적 로직에서 기인한다.

 

스택을 기준으로 발생가능한 ABA 문제 예시는 아래와 같다.

 

(1) 스레드 A가 POP을 수행(head, nextNode를 지역변수에 들고 있음)

 

(2) 스레드 A의 커밋 단계 전 다른 스레드의 개입

(3) 스레드 A의 커밋 단계 수행

 

(ABA 문제로 인해 파생되는 문제)

(1) 자료구조의 무결성 파괴 (+ 메모리 누수)

이러한 상황에서 head ptr의 일치로 next(과거 데이터, 위치 상 뒤쪽에 있는)를 새로운  헤드로 설정 시 기존 push된 데이터들이 모두 날라가는 문제가 발생할 수 있다. 단순히 자료구조에서 날라간 것을 넘어 메모리 누수 문제이다.

 

(2) 디버그 힙 관리자 할당 메모리의 오버플로우 예외 발생

malloc의 동작을 먼저 살펴보자면, malloc은 내부적으로 HeapAlloc(윈도우)을 통해 동적 메모리를 할당받는다. 프로세스 힙 관리자는 프로세스 시작 시 OS로부터 미리 할당받아 놓은 가상 메모리 블록을 기본 힙으로 들어있는데, 이 중 일부 영역을 반환하는 것이다.

프로그램이 디버드 모드로 빌드되었다면, CRT 디버그 힙 관리자는 추가의 영역을 더해 동적 메모리를 할당받는다. 이 추가 영역에는 메모리 부가 정보를 담는 4바이트 버퍼가 있는데, 일련의 비트들로 셋팅된다. 이 일련이 비트들을 오버플로우 발생을 식별하는데 발생하며, 반환 시 오염이 확인되면 런타임 에러를 발생시킨다. 

만약 이미 반환된 주소에 대해 접근이 이루어진다면(자료구조 무결성이 파괴된 상태에서), 오버플로우 식별을 위한 비트를 건들일 수 있는 가능성이 발생한다. 이는 곧 런타임 에러로 이어진다.

 

(3) double-free 에러 유발

마찬가지로 자료구조의 무결성이 파괴된 상태인데, 이번엔 이미 반환된 주소에 대한 중복 해제(free)를 하게 된다면 여러 문제가 발생할 수 있다.

• 힙 구조 손상(Heap Corruption)
  • 동적 메모리 관리 시스템은 메모리 할당과 해제를 관리하기 위해 내부적으로 데이터 구조(ex, free-list, heap metadata emd)을 유지한다. 
  • double free 시 이미 해제된 메모리 블록을 다시 힙 관리 구조에 추가하면서, 힙 관리 데이터 무결성이 파괴된다. 이는 당장의 런타임 에러를 발생시키지는 않겠지만, 결국 후속 동적 할당/해제를 비정상적으로 만들게 될 것이다.
• 이중 해제 시 사용 후 해제(Use-After-Free) 가능성
  • 말 그대로 해제된 메모리를 다시 사용할 가능성이 생기는 것이다.
  • 메모리를 다른 코드에서 재할당 한 상황에서, 해당 메모리를 다시 해제한다면(표면상 double free 처럼 동작하는 경우), 해제된 영역을 참조하는 부작용이 발생할 수 있다.

 

2.  디커밋된 페이지 영역 참조 부작용 -> Read Access Error 발생!

헤더를 캡처한 스레드의 수행 재개하여 이전 캡쳐 주소에 접근한다. 만약 이 캡쳐된 주소 영역이 프로세스 힙 관리자 차원에서 디커밋(Decommit)한 영역이 되었다면, 허용되지 않은 주소로 접근한 것과 같아지기에 '읽기 액세스 오류'가 발생한다. 

 

 

∴ 결국, '1. ABA 문제'와 '2. 디커밋 페이지 참조 에러 문제'를 해결하기 위해 기본 동적 할당 시스템에 의존할 수 없음을 결론내릴 수 있다.

 

[락-프리 메모리 풀]

메모리 참조 오류를 피하기 위해, 메모리 풀로부터 할당받아야 한다. 그런데 메모리 풀에 동기화를 동기화 객체를 사용하게 된다면, 이는 락-프리 자체가 성립이 안된다. 따라서 락-프리 스택 구조와 비슷하게 수행하면서 대신에 메모리 풀의 메모리 접근을 원자적으로 제어하여 풀 내 메모리를 할당하는 방식을 수행한다.

참고로 락-프리 메모리 풀에도 ABA 문제가 발생할 수 있다. 앞서 설명한 ABA 문제 예방을 메모리 풀에도 적용해야 한다. (단 메모리 풀에는 메모리 참조 오류 염려가 없는 것이다)

 

락-프리 메모리 풀: https://alphamot.tistory.com/47

[Lock Free] Lock Free Memory Pool