LockFreeList
1. Locking Mechanism의 문제
우리가 멀티쓰레드 상황에서 쓰레드간 공유자원에 대하여 consistency를 위해 Locking Mechanism을 사용하곤 한다.
이러한 Lock의 경우 다음과 긑은 문제를 야기하게 된다.
- DeadLock : 당연하다.
- Priority Inversion : OS의 스케줄링에 따르면 우선순위가 낮은 프로세스가 먼저 Lock을 획득하게 되어 우선순위가 역전되는 현상이 발생한다.
- Convoying : Locking을 획득하고 이를 해제하기 까지 가장 속도가 느리게 걸리는 프로세스에 의해 다른 프로세스들의 속도 또한 지연되는 현상을 의미한다.
- Async-signal unsafety : function이 signal handler에서도 안전하게 호출될 수 있는 것을 의미한다.
다음 Async-singal safety하지 않는 대표적인 함수인 printf의 예시이다.
// Thread A : printf("Hello World, I'm A");
-> Hello Worl
// Singnal handler is Called to print "[DEBUG] Error Occured"
-> Hello Worl[DEBUG] Error Occuredd
이처럼 signal handler에서 안전하게 호출되지 않는 함수들을 async-signal safety하지 않는다고 이야기한다.
Lock을 사용하게 되면 async-signal safe하지 않는 함수가 되게 되는데 예를 들어 다음과 같은 상황이 발생하기 때문이다.
-> Thread A가 Lock1을 획득
-> Thread A가 signal을 받게 되어 signal handler가 호출되고 다시 Lock1을 획득하려고 한다.
-> 같은 쓰레드가 같은 Lock에 대해서 획득 요청을 하기 때문에 요청이 거절되고 DeadLock에 빠지게 된다.
- kill-tolerance : Thread가 lock을 가지고있기 때문에 바로 kill을 바로 수행하지 못하고 해당 lock을 반환하는 과정을 거치고 thread가 종료된다.
- Pre-emption tolerance : Thread가 lock을 가지고 있는데 pre-emption되려고 한다면 해당 lock을 반환하는 과정을 거치고 pre-emption이 되어야한다.
따라서 전체적인 성능은 Lock을 사용함으로써 떨어지게 된다.
하지만 그렇다고 Lock을 사용하지 않는 알고리즘을 만들기는 매우 어렵다. 한번이라도 멀티코어 관련 코딩을 해보신 분들은 동감할 것이다. 따라서 LockFree DataStructure를 사용하는 것이 대부분이고 다음과 같은 4가지 방식의 패턴을 사용하게 된다.
2. Pattern of Concurrent Data Structure
(1) Fine-grained Synchronization
특정 자료구조에 대하여 global lock을 사용하여 synchronization을 구현하는 것이 아닌 자료구조에서 부분을 나누어 lock을 분배하는 것을 의미한다.
Linked List에 대하여 전체적인 Lock을 처리하는 것이 아닌 Node별로 Lock을 부여하여 관리하는 방법을 예시로 들 수 있다.
ex)
void LinkedList::deleteNode(Node* prevNode) {
int succeed = 0;
while(succeed = 0){
while(pthread_mutex_trylock(&prevNode->Lock) !=0);
if(pthread_mutex_tryloc(&prevNode->Next->Lock) == 0){
Node *temp = prevNode->nextNode;
prevNode->nextNode = temp->nextNode;
delete temp;
succeed = 1;
}
else{
pthread_mutex_unlock(&prevNode->Lock);
}
}
}
(2) Optimistic Synchronization
자료구조에 대한 검색, 삭제, 추가 등의 operation을 수행하기 전에 validation이라는 과정을 거치게 되는 패턴을 의미한다.
validation이란 linked list를 전체 순회하면서 특정 노드에 대하여 lock을 획득할 수 있는지를 검사하고 해당 값이 내가 원하는 값인지를 검사하는 과정을 의미한다. 해당 과정에서 만약 실패를 하게 된다면 linked list를 처음부터 순회하게 된다.
locking을 지속적으로 시도하는 Fine-grained synchronization보다는 빠르지만 linked list를 순회하는 cost가 높다는 단점이 존재한다.
(3) Lazy Synchronization
Search에 대해서는 Lock을 걸지 않고 Insert와 remove에 대해서만 lock을 획득하는 방법이다.
단, delete에 대해서 바로 delete를 하지않고 Node에 Logically deleted라는 체크를 하기 때문에 delete가 다른 쓰레드의 속도를 늦추지 않는다.
이러한 Logically delete 때문에 search와 insert를 위해서는 다음과 같은 validation과정을 거치게 된다.
1. pred is not marked
2. curr is not marked
3. pred point to curr
(4) Lock Free Method
위의 과정들은 Lock에 대한 overhead를 줄이는 방법이지만 결국에는 lock을 사용하기 때문에 성능이 좋지 않다.
Lock Free Method는 Compare and swap방법을 사용하여 lock없이 concurrent하게 쓰레드들이 linked list를 검색, 수정, 삽입등의 operation을 수행할 수 있게 해주는 방법이다.
- Linked List
다음 예시는 Linked List에서 Insert를 어떻게 lockFree하게 진행하는지에 대한 예시이다.
다음 예시는 이해를 쉽게 하기 위한 pseudo code입니다.
void LinkedList::deleteNode(Node* prevNode) {
Node* NewNext = prevNode->Next->Next;
Node* OldNext = prevNode->Next;
CAS(&(prevNode->next), &OldNext, NewNext);
}하지만 다음과 같이 delete를 하게 된다면 OldNext에게 새롭게 추가된 Node가 누락될 수 있다.
이 때문에 Logical Remove를 먼저하고 Physical remove를 진행하게 된다.
여기서 Logical Remove란 Node에 대해서 markbit을 하는 것을 의미하는데 이러한 markbit가 되어있다면 cas가 이뤄지지 않는다.
따라서 logically Remove가 된 노드에 대해서는 새로운 노드와의 CAS가 이뤄지지 않게 된다.
- Queue
queue같은 경우 이러한 linked list에서의 LockFree방식을 적용하면 queue는 head와 tail모두 관리를 해야한다는 점 때문에 문제가 생기게 된다.
LinkedList의 LockFree방식은 tail의 상태를 다음 2가지 중 1가지로 존재하게 만들어준다.
1. Actual Last Node
2. Penultimate Node
2번 상황이라면 다른 쓰레드가 Insert를 수행하고 있는 상황을 의미한다.
따라서 CAS를 통해 Tail이 진짜 마지막을 가르키게 수정하는 작업이 필요하다.
이러한 LockFree queue의 경우 ABA Problem에 대하여 vulnerable하다.
Q) ABA Problem이란?
우리가 앞써 말한 Node에 대해서 관리하는 방법은 이러한 Node를 추후에 사용하기 위해 Free pool에 저장해두는 방식이 존재한다.
이러한 방식으로 Free Node를 관리하게 된다면 head가 Free pool에 존재하는 Node를 가르키게 되는 상황이 발생하게 되는데 이를 ABA problem이라고 한다.
ex)
현재 상황 : Head->A->B->C->tail
Thread 1 : A를 deque하고 싶다. -> A, B주소값 획득
Thread 1 Sleep
Thread 2 : A, B를 모두 deque하고 싶다 -> A, B deque성공
현재 상태 : Head->C->tail
buffer Pool : A->B
Thread 1 Wakeup
Thread 1 : Head의 next를 B로 설정하자
현재 상태 Head->[B in Buffer pool] -> ?
이를 방지하기 위해 주소값에 stamp라는 공간을 사용하여 이를 처리한다.
우리가 64비트 주소 공간을 사용할 때 64비트 전체를 사용하지 않는다. 이 중 남은 공간에 stamp를 사용하고 이 stamp가 특정 노드가 현재 buffer pool에 존재하는지에 대한 상태를 관리해준다. 따라서 이러한 stamp가 늘어있는 경우 cas에서 주소공간이 달라지게 되기 때문에 head가 buffer pool에 존재하는 node를 next로 설정할 일이 없게 된다.
성균관대 남범석 교수님의 SWE3032 강의를 듣고 정리한 글입니다.
긴 글 읽어주셔서 감사합니다.
틀린 부분이 있으면 댓글을 달아주시면 감사하겠습니다.
📧 : may3210@g.skku.edu