[NDC 2014] 멀티쓰레드 프로그래밍이 왜이리 힘드나요?

---

멀티쓰레드 프로그래밍의 어려움

- Data Race: 2를 5천만번 더했는데 1억이 안나옴 -> lock을 사용해 해결

- 성능: 싱글 쓰레드보다 느려짐 -> lock을 쓰지 말자

- 컴파일러: 변수를 참조했는데 무시 -> volatile 키워드 또는 atomic으로 해결

- CPU: 프로그램 실행 순서를 자기 마음대로 변조 -> asm mfence 또는 atomic으로 해결

 

 

Lock-Free 알고리즘이란?

여러 개의 쓰레드에서 동시에 호출했을 때에도 정해진 단위 시간마다 적어도 한 개의 호출이 완료되는 알고리즘

호출이 다른 쓰레드와 충돌했을 경우 적어도 하나의 승자가 있어서, 승자는 delay 없이 완료 된다.

LOCK을 사용하지 않는다고 해서 모두가 lock-free 알고리즘은 아니며, LOCK을 사용하면 무조건 lock-free 알고리즘이 아니다.

장점: 성능과 높은 부하에도 안정적

단점: 복잡한 알고리즘, 정확성 증명의 어려움, 새로운 메소드를 추가하기 어려움, 메모리 재사용의 어려움(ABA)

 

 

CAS?

lock-free 알고리즘의 핵심

CAS(&A, old, new) => A 메모리를 다른 쓰레드가 먼저 업데이트하면 false, 아니면 new로 갱신

하지만 2개의 변수를 동시에 atomic하게 변경할 순 없다.

 

 

멀티쓰레드 프로그래밍 도우미

Intel TBB: 좋은 성능과 유용한 라이브러리, Concurrent 자료 구조

Visual Studio PPL: Intel TBB와 유사

OpenMP: 컴파일러 레벨에서 병렬 프로그램 API를 제공

 

 

Transactional Memory

CAS의 개념을 그대로 구현한 것

CAS와 다른점은 생산성. 싱글 쓰레드 프로그램을 그대로 쓸 수 있고 멀티쓰레드에선 Lock-Free하게 실행됨

다른 쓰레드와 충돌이 일어날 수 있는 구간을 transaction으로 선언한다.

 

How?

1. transaction 구간에서 읽고 쓴 메모리를 다른 쓰레드에서 접근했는지 검사한다. (write는 실제 메모리에 쓰지 않음)

2. 다른 쓰레드에서의 접근이 있었으면 모든 업데이트를 무효화 한 후 다시 시도

3. 다른 쓰레드에서의 접근이 없었다면 transaction 구간에서의 update를 실제 메모리에 update

이 방법을 Software적으로 관리하거나(STM), Hardware적으로 관리함(HTM)

 

장점: 기존 프로그램을 그대로 사용 가능해 생산성이 높음

단점: STM은 오버헤드로 인한 속도 저하, HTM은 HW가 필요

 

출처: http://ndcreplay.nexon.com/NDC2014/sessions/NDC2014_0048.html

---