Multi Thread 공부 6일차 (List - Non-Blocking(비멈춤 동기화))

14 Jun 2021

Reading time ~4 minutes

List

지금까지 여러 동기화 방법을 알아봤다. 하지만 가장 좋은것은 lock을 하지 않고 만드는게 가장 빠르지만 가장 손실이 많이 났다.

그럼 현실에서 사용되고 있는 멀티스레드 방법을 알아보자

현실의 멀티스레드 프로그램은?
- 여러 스레드가 동시에 멀티코어에서 실행된다.
- 스레드간의 데이터 공유 및 도익화는 안전한 lock free 자료구조를 통해서 이루어진다
  - 언리얼 3 : 디스플레이 리스트 queue
  - 각종 게임 서버 : job queue 외 다수

현실에서 멀티스레드 프로그램은 스레드 간에 데이터 공유 및 동기화는 안전한 lock free 자료구조로 해야 한다. 언리얼 3,4같은 경우는 멀티스레드로 만든 엔진인데 스레드끼리 서로 queue로 주고 받는다. 로직 스레드에서 actor들을 최신으로 만들면 렌더링 스레드에서 업데이트 한다.

그리고 게임서버 회사에서 구현한 서버들은 락프리 자료구조를 사용한다. 랃프리 자료구조를 사용하지 않으면 성능이 안나온다.

그래서 락프리가 뭐냐

Lock Free

여러개의 스레드에서 동시에 호출했을 때에도 정해진 단위 시간마다 적어도 한 개의 호출이 완료되는 알고리즘
자료구조 및 그것에 대한 접근 방법
- queue : enqueue, dequeue
- stack : push, pop
- 이진트리 : insert, delete, search
멀티스레드에서 동시에 호출해도 정확한 결과를 만들어주는 알고리즘
- stl 탈락
Non-Blocking 알고리즘
- 다른 스레드가 어떤 상태에 있건 상관없이 호출이 완료된다.
호출이 다른 스레드와 충돌하였을 경우 적어도 하나의 승자에 있어서, 승자는 delay없이 완료된다.

여기서 략프리는 볼드체의 3개자 조건을 만족시키는 알고리즘이다.

따라서 stl에서 사용하고 있는 자료구조 큐, 벡터, 맵은 전부 사용하지 못한다. atomic하지 않기 때문에 멀티스레드에서 제대로 돌아가지 못한다.(직접 만들어야 한다.)

그 다음엔 Non-Blocking 해야 한다. 어떤 뜻이냐면, 여러 스레드가 동시에 호출해야 하는데 다른 스레드에서 메소드를 실행하면서 어떤 상태에 처해있건 상관없이 호출이 완료되는 알고리즘이다. 옆에 스레드가 어떤 상황이든 내걸 건들이든 말든 호출이 완료 되어야 한다.

만약 충돌했으면 어떻게 되냐? 그냥 끝내면 된다. lock free는 충돌하면 둘중 하나는 딜레이가 생기지만 하나는 그냥 완료 해야 한다.

Wait Free 알고리즘은?
- 호출이 다른 스레드와 충돌해도 모드 delay없이 완료 된다.
추가상식
- lock을 사용하지 않는다고 lock free 알고리즘이 아니다.
  - 계속해서 while문이 돌면 lock free 알고리즘이 아니게된다.
- lock을 사용하면 무조건 lock free 알고리즘이 아니다.
  - lock을 사용했으니까

BLK_QUEUE::push(int x)
{
	Node* e = New_Node(x); 
	qlock.lock(); 
	tail->next = e; 
	tail = e; 
	glock.unlock(); 
}

위의 자료구조를 논 블로킹으로 구현하면

LF_QUEUE::push(int x) 
{ 
	Node* e = New_Node(x);
	while (true) 
	{ 
		Node* last = tail; 
		Node* next = last->next; 
		if (last != tail) continue; 
		if (NULL == next) 
		{ 
			if (CAS(&(last->next), NULL, e)) 
			{
				CAS(&tail, last, e); 
				return; 
			} 
		} 
		else 
			CAS(&tail, last, next); 
	}
}

이렇게 된다.

마지막에 CAS 는 뭐냐!?

CAS(Compare And Swap)

현재 스레드에 저장된 값과 메인 메모리에 저장된 값을 비교하여 일치하는 경우 새로운 값으로 교체하고 일치하지 않는다면, 실패하고 재시도를 하는 알고리즘이다.

 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;
}

이런 식으로 구현이 된다.

하지만! ABA Problem 이라는 문제가 등장한다.

ABA Problem

CAS 연산에서 공유 객체에 대한 변화를 감지하지 못할 때 발생하는 현상을 ABA현상이라고 한다.

출처 : (https://ozt88.tistory.com/38)

맨 위에 노드는 A라고 할때 스레드1은 top을 A로 저장하고 next를 b로 저장한다. 그런데 중간에 스레드2가 끼어들어서 A와 B 둘다 Pop을 했다. 그런데 다시 그레드3이 중간에 A의 주소를 Push해버렸다. 그래서 CAS 체크를 하면 Fail이 뜨지 않는다. CAS는 주소가 맞다고 감지하고 그럼 이미 Pop해서 B가 스택의 top이 된다. CAS만으로 주소값을 비교하다보니 일관성을 보장하기 힘들다.

이런 문제를 해결하기 위해 double check CAS라는 것이 있다.

pop의 count를 포함한 double check를 통해서 주소값을 CAS 해주고, pop한 count 또한 CAS 해주면서 일관성을 보장해준다.

다시 CAS로 돌아오자

CAS
- CAS가 없이는 대부분의 non blicking 알고리즘을 구현할 수 없다.
  - queue stack list
- CAS 를 사용하면 모든 싱글 스레드 알고리즘을 lock free 알고리즘으로 변환할 수 있다
- lock free 알고리즘의 핵심
- cas(&a, old, new);
  - 의미 : a값이 old이면 new 로 바꾸고 true 리턴
  - 다른 버전의 의미 : a메모리를 다른 스레드가 먼저 업데이트해서 false가 나왔다. 포기해라.

자 그럼 lock free를 구현해야 한다.

첫번째 방법은 만약 실패했을 시 실패하기 전 과거로 돌아간다….??

우리에겐 시간을 돌리는 힘은 없다… ㅠㅠ

두번째 방법 자료구조의 변경을 시도하고 만약 다른 스레드가 먼저 변경했으면 시도를 취소한다.

두번째 방법이 가장 현실적인 방법이다.

while(true)
{
	int old_sum = sum;
	if(CAS(&sum, old_sum, old_sum + 2))
	{
		break;
	}
}

이렇게 작성을 하는게 간단한 lock free 알고리즘이다. 조금만 생각해도 lock이 한번도 없이 잘 돌아간다.

대신 장점이 이렇게 쨩쨩한데 단점도 그만큼 쨩쨩하다

단점
- 알고리즘이 많이 복잡하다.(렌더링을 하면 코드가 2~3배 길어진다고 어디서 주워들었다.)
- 복잡하기 때문에 실수하기 쉽다.
  - 그런데 실수를 적발하기가 어렵다.(와… 노답)
- 제대로 동작하는 것이 증명된 알고리즘을 사용해야 한다.
결론
- 믿을 수 있는 non blocking container들을 사용하라
  - Intel TBB, Visual Studio PPL
- 자신을 포함한 출처가 의심스러운 알고리즘은 정확성을 증명하고 사용하라
  - 정확성이 증명된 논문에 있는 알고리즘은 사용해도 좋다.

C++20 에서 드디어 non blocking 알고리즘이 몇개 추가될거같다.(로드맵에서 그렇게 써있었다. 끼얏호우)

Multi Thread