프로세스
프로세스 우선순위: 클래스 ProcessInitializer
스레드
성능 개선하기
암달의 법칙
성능은 프로세서의 개수에 비례하지 않는다
싱글프로세서에서 작업시간 1이 걸리는 일을 프로세서가 5개인 머신에서는 작업시간이 1/5로 줄어야 하지만, 현실적으로 불가능하다. 왜냐하면, 프로세서간의 통신과 조율(스케줄링 같은)이 필요하고, 이런 것들이 상황과 구현의 방법에 따라 성능에 적지 않은 영향을 주기 때문이다.
성능 측정하기
암달의 법칙을 이용하면 이와 같은 추가 비용이 성능에 미치는 영향을 쉽게 이해할 수 있다. 여기에서는 암달의 법칙을 이용해 이와 같은 요소가 성능에 얼마나 영향을 미치는지 확인해 보려고 한다.
암달의 법칙은 다음과 같다.
S = 1 / ((1 – p) + p / n)
- n : 프로세서의 수
- p : 동시에 처리 할 수 있는 작업의 비율 (예를 들어 5만큼의 작업 중에 4만큼의 작업을 동시에 처리할 수 있다면 p = 4 / 5)
- 1 – p : 동시에 처리할 수 없는 작업의 비율 (위의 예에서는 1 / 5)
- (1 – p) + p / n : n개의 프로세서가 절대 작업량 1인 작업을 동시에 처리할 경우에 걸리는 시간
- S : 속도 증가 배율
이 법칙에서 n과 S가 같아질 경우 가장 이상적이다. 예를 들어 프로세서가 5개일 경우 속도가 5배로 증가했다면, 이 로직은 가장 이상적이라고 할 수 있다. 하지만 앞에서 말한 것과 같이 현실에서는 이런 결과를 볼 수 없다.
더 쉬운 이해를 위해 다음의 예에서 속도 증가 비율을 계산해 보자.
어떤 작업을 동시에 처리할 수 있는 부분의 비율이 0.8 라고 가정하고, 이 작업을 프로세서가 4개인 머신에서 처리한다고 할 때, 속도 증가 배율(S)은 다음과 같다.
S = 1 / (0.2 + 0.8 / 4) = 2.5
이것은 이 작업을 처리하는데 프로세서가 4개인 머신이 싱글프로세서 머신보다 2.5배 빠르다는 것을 나타낸다. 그렇다면 프로세서가 8개인 머신에서는 얼마나 빨라질지 계산해보자.
S = 1 / (0.2 + 0.8 / 8) = 3.3333..
이처럼 약 3.3배 빨라진다. 게다가 프로세서를 계속 늘려 계산해 봐도 5배 이상 빨라지지 않는다. 즉, 20%의 동시에 처리할 수 없는 작업이 전체 성능을 심각하게 떨어뜨릴 수 있다는 얘기다. 물론 현실에서는 더 적을 수도 있다. 하지만 우리가 보는 비율의 크기에 비해 성능에 미치는 영향은 매우 크다.
어떻게 성능을 개선할 것인가?
앞에서 동시에 처리할 수 없는 작업의 양이 얼마나 성능에 영향을 미치는 지를 암달의 법칙을 통해 확인해 봤다. 적은 양의 작업이라도 성능에 큰 영향을 미친다. 그렇기 때문에 성능을 극대화하기 위해서는 이런 작업을 할 수 있는 한 줄여야 한다. 이번 단원에서는 성능에 미치는 요소들의 유형을 살펴보고, 성능을 개선할 수 있는 방법에 대해 살펴 보려고 한다.
CPU 바운드 게임 서버
일반적으로 게임서버의 성능은 CPU의 성능에 영향을 받는다. 게임 장르에 따라 다를 수 있지만. 이 책에서 다루고자 하는 다양한 로직이 구현된 대용량 게임 서버는 CPU 성능에 영향을 받는다고 보는 것이 옳다. 쉽게 말해 CPU 성능이 좋을 수록 더 빠른 응답 속도를 보여준다는 의미이다. 결국 좋은 CPU를 사용하는 서버는 게임 환경을 보다 더 쾌적하게 만들 수 있다.
물론, CPU 성능만 좋다고 해서 게임 환경이 쾌적해 지는 것은 아니다. 서버 프로그램이 CPU를 잘 활용하지 못하면 CPU 구입 비용만 날리고 CPU 벤더만 좋은일을 해 주게 된다.
성능에 영향을 미치는 것
입출력(I/O)
파일이나 소켓 같은 입출력은 꽤 느리다. 특히 동기 방식으로 입출력을 처리할 경우에는 병목현상이 발생한다. (이 부분은 프로액터 패턴에서 자세히 다룬다) 따라서 입출력을 어떻게 처리하냐가 프로그램의 성능을 좌우할 수 있다.
잠금(Exclusive Lock)
잠금은 암달의 범칙에서 동시에 처리할 수 없는 작업에 속한다. 잠금을 많이 사용할 수록 성능이 떨어지는 것은 당연하다. 이 책에서는 잠금을 사용하지 않는 것을 원칙으로 한다.
신청 초과와 신청 미달
우리가 만들 수 있는 스레드를 \’논리 스레드\’라 하고 하드웨어의 것을 \’실제 스레드\’라 한다. 외부 장치와의 입출력이 없다면 실제 스레드 하나 당 하나의 논리 스레드만 실행될 경우에 가장 효율적이다. 실제 스레드보다 논리 스레드가 더 적을 경우에 \’신청 미달\’이라고 하는데, 이럴 경우에는 CPU 자원을 제대로 활용을 못하게 된다. 반대로 논리 스레드가 더 많을 경우에는 \’신청 초과\’라고 하고, 이럴 경우에는 스케줄링에 대한 비용을 더 부담해야 한다.
\’신청 초과\’가 발생하면 스케줄러가 논리 스레드를 시간 분할해서 실행하게 된다. 이 작업은 선점형 스케줄링을 하는 운영체제가 하게 된다. 시간 분할은 공짜로 이루어지는 것이 아니기 때문에 그에 대한 비용을 지불해야 한다.
시간 분할이 되서 다른 스레드로 차례가 넘어갈 때 기존의 스레드에 대한 문맥을 저장하고 다음 차례인 스레드의 문맥을 복구해야 한다. 이런 작업을 컨텍스트 스위칭이라고 한다. 컨텍스트 스위칭이 일어날 때 스레드의 문맥에 포함되는 레지스터를 저장하고 복원한다.
그리고 캐시 쿨링이라는 비용이 발생할 수 있다. 프로세서는 최근에 접근한 데이터를 캐시 메모리에 보관한다. 이 메모리는 메인 메모리에 비해 상대적으로 작고 매우 빠르다. 프로세서가 캐시 메모리를 모두 사용해 버리면, 보통 가장 오래 전에 사용한 데이터를 캐시에서 퇴출시키고 메인 메모리에 쓴다. 스레드가 자기 차례가 돼서 데이터를 참조하면서 이 데이터가 캐시에 저장된다. 이 처리는 수 백 사이클이 소요된다. 하지만 그 데이터가 퇴출되지 않고 충분히 자주 참조된다면 단지 몇 사이클 만에 데이터에 접근할 수 있다. 이런 데이터를 캐시에서 따끈한 상태에 있다라고 한다. 1
시간 분할은 이것을 무효화 시킨다. 만약 스레드 A가 자신의 시간을 다 사용하면 같은 물리 스레드에서 스레드 B가 수행된다. 이렇게 되면 B는 A가 사용하던 따끈한 상태의 데이터를 캐시로부터 퇴출시킨다. 물론 A와 B 모두 그 데이터를 참조한다면 이런 일은 발생하지 않을 수도 있다. 캐시에서 추출되고 난 후 다시 A 차례가 되면 A는 캐시에서 퇴출된 데이터를 캐시로 다시 로딩하는 비용이 발생한다. 더 상황이 악화되서 스레드 A가 전과는 다른 물리 스레드에서 수행될 수 있다면, 두 스레드가 그 데이터를 공유하더라도 캐시 미스가 발생할 수 있다.
또 다른 비용은 잠금 선점이라는 것이다. 어떤 스레드가 잠금을 획득하고 풀기 전에 자신의 시간을 모두 사용해서 스케줄링이 된다면 다음 순서가 오기 전까지 불필요한 잠금 상태가 유지된다. 이렇게 되면 그 잠금에 대기하는 스레드들은 자신의 순서가 와도 아무 것도 하지 못한 체 넘어가게 된다. 이런 효과를 호송 효과라고 한다. 2
병렬프로그래밍에 유용한 패턴
멀티스레드 프로그래밍 라이브러리
인텔 스레드 빌딩 블록
Concurrency Runtime
# 비동기 에이전트 라이브러리
동시성 모델
Multiple Synchronous Threads
- 동시성이 있는 서버를 만들기에 가장 직관적인 방법이다.
- 비동기 처리가 없는 멀티스레드를 이용한다.
- 스레드 내에서는 데이터를 공유하지 않는다.
- 각 연결마다 하나의 스레드를 만들어 동기적으로 처리를 한다.
- 각 연결마다 데이터를 공유하지 않는 웹서버에 적합하다.
- 아무리 웹서버라도 로그파일 같은 것은 공유하게 되는데 이럴 경우 성능에 문제가 발생한다. \’단점\’ 항목에서 자세히 설명한다.
# 단점
- 동기화 복잡도가 올라간다.
- 캐시파일이나 로그파일 또는 웹페이지 접속 수 같은 서버의 공유자원에 접근할 경우 구현이 복잡해진다.
- 스레드 내에서 기본 로직은 동기적으로 처리되지만 서버의 공유자원에 접근하려면 결국 동기화에 신경 써야 한다. 단지 상대적으로 직관적인 방법일 뿐이다.
- 성능상 오버헤드가 올라간다.
- 스레드가 매우 많아지므로 컨텍스트 스위칭, 동기화, CPU 간의 데이터 이동 같은 오버헤드가 발생한다.
Reactor Pattern
- socket 의 select 함수를 이용한다.
- 하나의 스레드에서 입출력을 처리하므로 입출력이 동시에 이루러지지는 않는다. 입출력에 한해서는 동시성을 갖고 있지 않다.
- 처리 순서
- 클라이언트와 연결에 성공하면 Reactor 에 \’읽기대기모드\’로 등록한다. 이후에는 클라이언트의 데이터를 넌블럭으로 받을 수 있다.
- 클라이언트로 부터 데이터를 제대로 받을 때까지 읽기를 반복한 후, 데이터를 분석해 처리한다. (분석과 처리는 작업스레드에게 넘길 수 있다.)
# 단점
- 성능을 위해 데이터 처리를 할 때 다른 클라이언트의 입출력을 막아서는 안된다. 결국 처리가 복잡해진다.
- select 함수에서 사용하는 같은 descriptor 집합을 여러 스레드에서 사용할 수 없다. 이런 점은 고성능서버에 맞지 않다.
- 부하를 분산하기 위한 작업 예약방식(task scheduling)을 직접 구현해야 한다. 이것은 가장 어려운 작업이 될 수 있다.
Proactor Pattern
- OS 가 비동기 명령을 지원한다면 효과적인 고성능서버를 구현할 수 있다.
- Windows 는 IOCP 를 이용해 비동기 명령을 지원한다.
- 앞에서 설명한
Reactor와는 달리 완료된 입출력을 여러 스레드에서 처리할 수 있다. - 처리 순서
- 서버가 Send 나 Recv 같은 비동기 명령을 OS 에 등록하고 Completion Dispatcher 에 콜백함수를 등록한다. 이 콜백함수에는 데이터를 처리하는 코드가 들어있다.
- OS 가 서버 대신 비동기 명령을 처리한다.
- 비동기 명령이 완료되면 OS 가 그 결과를 큐에 넣는다.
- Completion Dispatcher 는 큐에서 결과 값을 꺼내 콜백함수를 호출한다.
# 단점
- 최소한
Reactor Pattern만큼 프로그래밍 로직이 복잡하다. 더 복잡해질 수 있다는 얘기다. - 비동기 명령이 순서대로 처리되지 않을 수도 있기 때문에 분석과 디버깅이 어렵다.
우리의 스레드 관리 전략
CPU 바운드 서버를 지향하는 얼그레이는 시간 분할의 비용을 최소화하기 위해3
실제 프로세서의 수만큼 스레드를 만든다. 그리고 각 프로세서 당 하나의 스레드에 선호도를 지정한다. 이 방식은 앞에서 설명한 TBB 의 예약 방식과 같다. 선점형 예약 방식을 사용하는 OS라 하더라도 캐시 무효화를 고려해 설계되기 때문에 논리 스레드가 수행되는 프로세서가 자주 바뀌지는 않는다. 하지만 사용하던 프로세서가 여유롭지 않다면 여유로운 프로세서에 스레드를 할당할 수 밖에 없다. 이와 같이 전에 수행되던 프로세서가 아닌 다른 프로세서에서 수행될 때 캐시가 무효화된다. 얼그레이의 예약 방식은 이러한 상황을 줄여 준다.
이런 예약 방식을 사용하기 위해서는 프로세서 자원을 최대한 사용해야 한다. 그렇지 않으면 신청 미달이 발생하게 되므로 효율적이지 않다. 결국 시간 분할의 비용과 신청 미달에 의한 비용을 저울질해 봐야 한다. 이것은 꽤 골치아픈 일이다. 4 이런 이유 때문에 데이터베이스 처리나 로깅 같은 I/O 바운드의 작업을 다른 하드웨어로 분리하는 것이 좋다.
태스크 기반 예약 방식
얼그레이는 예약 방식에 있어서 TBB와 PPL과 많이 닮아 있다. 이 두 라이브러리와 마찬가지로 얼그레이도 태스크 기반 예약 방식을 사용한다.
태스크큐 만들기
얼그레이는 무잠금을 원칙으로 한다. 그렇기 때문에 태스크큐도 무잠금 알고리즘을 기반해 만들어져 있다. 이번 단원에서는 많이 알려져 있는 무잠금 알고리즘의 원리과 구현 방법을 설명하고 이 알고리즘을 변형해서 태스크큐를 만들어 볼 것이다.
무잠금큐 만들어 보기
태스크큐는 무잠금 큐를 기반으로 하기 때문에 태스크큐를 만들기 전에 무잠금 큐를 구현해 보기로 하자. 간단히 무잠금 큐를 만들어 보고 몇 가지 문제점들을 보완해 나가면서 완성도를 높일 것이다.
CAS 이해하기
무잠금큐는 데이터를 동기화를 위해 Compare And Swap 이라는 원자적 함수를 사용한다. 주로 줄여서 CAS(카스)라 부른다. CAS는 검사와 데이터의 변경을 한 번에 수행한다. 이것을 C 코드로 만들어 보면 다음과 같다. 실제로는 원자적인 함수이므로 함수 내에 다른 스레드가 끼어들 수 없다는 것을 생각하며 살펴보자.
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;
}
http://en.wikipedia.org/wiki/Compare-and-swap 에서 발췌
코드를 보면 CAS는 세 개의 인자를 받는다. 첫 번째 인자인 reg와 두 번째 인자인 oldval를 비교해 값이 같으면 reg를 세 번째 인자인 newval 값으로 변경한다. 만약 reg와 oldval이 같지 않으면 아무 일도 일어나지 않는다. 그리고 reg의 변경되기 전 값을 리턴한다.
여기에서 우리는 CAS가 두 가지 역할을 하는 것을 알 수 있다. 그 중 하나는 여러 스레드에 의해 경쟁상태에 있는 메모리를 한 스레드만 변경할 수 있도록 하는 것이다. 그리고 다른 하나는 어떤 스레드가 그 메모리를 변경 중이라면 그 외 스레드는 변경할 수 없음을 알게된다. 자신이 변경할 수 없다는 것을 아는 방법은 단순하다. CAS가 리턴하는 값과 비교에 사용했던 oldval 값을 비교하면 된다. 만약 이 두 값이 같다면 reg가 newval로 변경됐다고 보면 된다.
윈도우의 API 중에 Interlocked- 로 시작하는 함수들이 모두 원자적 함수다. 이 중에 CAS 역할을 하는 함수는 InterlockedCompareExchange 함수인데 인자로 64비트 값을 사용한다면 InterlockedCompareExchange64 함수를 사용해야 한다. 이후로는 InterlockedCompareExchange 함수를 그냥 사용하지 않고 BOOL 값을 리턴하는 CAS함수로 래핑해 사용할 것이다. 그 함수의 구현은 다음과 같다. InterlockedCompareExchange 함수를 사용할 때 주의할 점은 인자들이 32비트 경계면으로 정렬돼 있어야 한다는 것이다. 정렬돼 있지 않으면 예상하지 못한 문제가 발생할 수 있다. 정렬된 메모리를 얻기 위해서는 _aligned_malloc 함수를 사용하면 된다.
inline BOOL CAS(volatile LONG *Dest, LONG Compare, LONG Exchange)
{
return InterlockedCompareExchange(Dest, Exchange, Compare) == Compare;
}
inline BOOL CAS64(volatile LONGLONG *Dest, LONGLONG Compare, LONGLONG Exchange)
{
return InterlockedCompareExchange64(Dest, Exchange, Compare) == Compare;
}
셀 구조체
무잠금큐의 자료구조는 링크드리스트로 구성돼 있다. C++로 표현한 셀의 구조는 다음과 같다. 지금은 타입 재정의가 무의미해 보이더라도 이후에 ABA 문제를 해결하면서 이부분이 확장될 것이므로 지금은 넘어가도록 하자. 템플릿은 무잠금큐를 일반화하기 위해 필요하다.
template<typename T>
struct Cell
{
typedef struct Cell<T> CellType;
typedef CellType* PointerType;
explicit Cell(CellType* next, T value)
{
this->next = next
this->value = value;
}
explicit Cell(T value)
{
this->next = NULL;
this->value = value;
}
explicit Cell() { this->next = NULL;}
PointerType next;
T value;
};
클래스 정의
이제 무잠금큐의 클래스를 정의해 보자. 범용적으로 사용하기 위해 템플릿으로 데이터타입과 메모리할당자를 선택할 수 있게 한다. 실제로 두 파라미터는 유용하게 사용된다. 특히 서버 개발에서 메모리 할당자는 원하는 것으로 변경할 수 있어야 한다. 무잠금큐 클래스를 정의하면 다음과 같다.
namespace Earlgrey {
namespace Algorithm {
template<typename T, class Allocator = std::allocator<T>>
class Queue : private Uncopyable
{
public:
typedef struct Cell<T> CellType;
typedef CellType::PointerType PointerType;
};
}}
여기에서 private 으로 선언된 Uncopyable 은 복사생성자와 대입연산자를 막아준다. 복사를 하기 위해서는 큐 안에있는 데이터들을 접근할 수 있어야 하는데 무잠금큐에서는 이런 작업의 안정성을 보장할 수 없다. 그렇기 때문에 Uncopyable 클래스를 private으로 상속해서 복사하려는 시도를 컴파일 시간에 미리 막아준다.
큐에 넣기
큐에 데이터를 넣는 Enqueue 함수는 다음과 같이 구현할 수 있다. 다음의 코드는 몇 가지 문제를 안고 있는 완성된 코드다. 문제에 대해서는 차차 해결하도록 하자.
void Enqueue(T value)
{
CellType* cell = _Allocator.allocate(1);
cell->value = value;
EARLGREY_VERIFY(cell != NULL);
for(;;)
{
PointerType tail = _tail;
PointerType next = tail->next;
// 다른 스레드가 _tail 을 변경했다면 대기한다.
if (tail != _tail)
continue;
// 아직 큐잉이 되지 않았다면 큐잉을 시도한다.
if (NULL ### next)
{
if (CAS64( (volatile LONGLONG*) &(_tail->next), next, cell ))
{
CAS64( (volatile LONGLONG*) &_tail, tail, cell);
break;
}
}
else
{
// 선점한 스레드가 큐잉하고 있는 중이므로 다른 스레드들은 이 블록에서 마무리 작업을 한다.
// 마무리 작업은 tail 을 새로 추가된 값으로 바꾸는 일이다.
// 이렇게 함으로써 convoying 을 피할 수 있다.
EARLGREY_ASSERT(next != NULL);
CAS64( (volatile LONGLONG*) &_tail, tail, next);
}
}
}
코드를 차근차근 이해하며 진행해 보자. 우선 for 루프 이전의 코드는 큐에 넣을 새로운 셀을 만드는 것이다. 이 메서드의 궁극적인 목적은 데이터를 담고 있는 셀을 큐의 맨 끝에 넣는 것이다.
for 루프 안으로 들어가서 지역변수를 두 개 선언하는데, 두 변수 모두 현재 상태를 복사해 두기 위한 임시변수다. 하나는 tail 을 담고, 다른 하나는 tail->next 멤버 값을 담는다. 이 두 임시변수는 CAS 로 값을 변경할 때 비교자로 사용된다. 임시 변수를 CAS 의 비교자로 사용하는 것은 관용구처럼 쓰이므로 CAS 를 사용하는 알고리즘에서 종종 볼 수 있을 것이다.
첫번째 CAS 문에서 경쟁이 발생하게 된다. 이 부분에 접근한 스레드 중 하나만 _tail->next 값을 새로운 셀로 변경하고 나머지는 링크드 리스트의 연결이 제대로 구성될 때까지 else 블록을 반복해서 수행하게 된다. 편의를 위해 변경에 성공한 스레드를 A라고 하고 나머지 스레드를 A\’ 라고 하자. A\’ 스레드가 루프에서 벗어나기 위해서는 _tail 이 새로 만들어진 셀로 변경돼야 한다. 그렇게 해야 링크드 리스트가 완성되기 때문이다.
if (CAS64( (volatile LONGLONG*) &(_tail->next), next, cell ))
{
CAS64( (volatile LONGLONG*) &_tail, tail, cell);
break;
}
변경에 성공한 스레드 A는 break 문이 있는 블록에서 _tail 을 새로운 셀로 변경하는 CAS 문을 수행한다. 직접 값을 변경하지 않고 CAS 를 사용하는 이유는 대기중인 스레드에게도 이 작업을 할 수 있는 기회를 주기 위해서이다. 이렇게 하면 대기중이 스레드들이 루프를 돌면서 _tail 을 _tail->next 로 변경하는 시도를 계속 하게된다. 스레드 A가 자신의 퀀텀을 모두 소비해서 컨텍스트 전환이 발생해도 다른 스레드가 이작업을 대신해주기 때문에 convoying 문제가 발생하지 않게된다.
코드를 보면 무한 루프를 위해 for(;;) 구문을 사용한다. 얼그레이는 경고레벨을 4로 지정해 컴파일하기 때문에 while(1) 과 같은 구문은 비교문에 상수를 사용했다는 경고를 발생시킨다. 이 경고를 피하기 위해서는 for(;;) 구문을 사용해야 한다. (참조: http://msdn.microsoft.com/en-us/library/6t66728h%28v=vs.80%29.aspx)
무잠금 알고리즘은 단순한 편이 아니라서 구현 중에 개발자들이 실수할 여지가 많다. 그러므로 적절한 곳에 어썰트 문을 아끼지 말고 사용하자.
큐에서 꺼내기
큐에서 꺼낸 데이터는 출력파라미터로 복사된다. 큐에 데이터가 쌓여 있어 성공적으로 꺼냈다면 true 를 리턴하고 큐가 비어있다면 false 를 리턴한다. 다음의 코드는 완성되지 않은 코드이다. 우선 아래에 있는 코드를 이해하고 어떤 문제가 있는지 살펴보자.
bool Dequeue(T& value)
{
for (;;)
{
// 비교를 위한 임시변수를 선언한다.
PointerType head = _head, tail = _tail;
PointerType next = head->next;
// head 를 다른 스레드에서 변경했다면 다시 시도한다.
if (head != _head)
continue;
if (head ### tail)
{
if (next ### NULL)
return false; // 큐가 비었다.
// Enqueue 중에 아직 tail 이 업데이트되지 않았다. 여기에서 업데이트한다.
CAS64( (volatile LONGLONG*) &_tail, tail, next );
continue;
}
// _head 의 next 의 값을 출력 파라미터로 복사한다.
value = next->value;
EARLGREY_ASSERT(head != next);
// head 를 next 값으로 바꾼다. 다른 스레드가 이미 head 를 변경했다면 처음부터 다시 시도한다.
if (!CAS64( (volatile LONGLONG*) &_head, head, next))
{
continue;
}
delete head;
return true;
}
}
Dequeue 메서드는 크게 세 가지 처리를 한다. 가장 먼저 큐가 비어있는지 검사한다. 이때 큐가 비어있다면 false를 리턴한다. 그런 다음 맨 앞에 있는 셀의 데이터를 출력 파라미터에 복사한다. 이 값은 마지막 처리까지 제대로 이루어진다면 변경되지 않는다. 마지막으로 맨 앞 셀을 제거한다. 이 때 경쟁이 발생해서 실패하게되면 루프를 다시 돌게 된다.
코드를 보면 head를 메모리에서 제거하기 전에 head->next 값으로 변경하는데, 이 때 어떤 스레드가 먼저 head 를 변경하면 head 를 변경하려던 다른 스레드들은 루프를 다시 돌아 Dequeue 작업을 재시도하게 된다. Dequeue 할 때 이 부분만 선점하면 데이터를 꺼낼 수 있다. 그리고 실패하더라도 다음 루프에서 다른 스레드가 변경한 가장 최신 값을 이용해 다시 처리할 수 있다. 그래서 CAS 를 선점한 스레드가 CAS 를 호출한 후에 컨텍스트 전환이 발생하더라도 convoying 이 발생하지는 않게 되는 것이다.
큐에 데이터가 두 개 이상일 경우에는 Enqueue 처리와 Dequeue 처리 중에 경쟁이 발생하지 않는다. 하지만 큐에 데이터가 빈 상태에서 새 데이터를 추가할 때는 경쟁이 발생하게된다. 왜냐하면 next 를 양쪽에서 참조를 하기 때문이다. Enqueue 안에서 head->next 가 null 에서 새 데이터로 바뀐 후 컨텍스트 전환이 발생하게 되면 Dequeue 를 호출한 스레드는 대기하게 된다. 즉, convoying 이 발생한다. 그렇기 때문에 Dequeue 에서도 tail 을 next 로 바꾸는 작업을 해줘야 이 문제를 피할 수 있다.
ABA 문제 해결하기
해저드 포인터
무잠금 큐의 변형
큐잠그기
태스크큐 사용하기
tr1 bind 를 이용한 멤버함수 시그니처 만들기
공유데이터와 태스크큐
언제 큐를 잠그는가
주의할 점
태스크큐로 해결하지 못하는 것
순서 맞추기
volatile
다중 스레드 코드에서는 컴파일러의 과도한 최적화 때문에 문제가 생기기도 한다. 무잠금 알고리즘은 루프를 돌리기 마련인데, 최적화 문제를 피하려면 공유 변수를 volatile로 선언해 둘 필요가 있다. 가능한 경우에는 읽기 및 쓰기 경계선을 직접 설정하는 게 더 나을 수도 있다.4
4: volatile에 대한 설명을 쓰려다 일단 Game Programming Gems 6에 적힌 글을 옮깁니다.
무엇이 어려운가
TLS(Thread Local Storage)
명시적인 TLS
- TLS API를 이용해 TLS를 관리한다.
- TLS 를 사용하는 포인터 정보는 스레드 정보를 담고 있는 TEB(Thread Environment Block) 구조체에 있다.
- 이 정보는 배열로 만들어진 단순한 접근자이다.
- 기본적으로 제공하는 TLS 저장 공간(슬롯)은 64개 뿐이다. 나중에 64개로는 부족하다는 것을 깨달은 M$는 1024개의 저장 공간(확장 슬롯)을 새롭게 추가한다. 그래서 현재는 최대 1088(64 + 1024)개의 저장 공간을 사용할 수 있다.
- TlsAlloc과 TlsFree는 사용할 수 있는 TLS 슬롯을 찾기 위해 락을 건다(acquire).
- 기본 슬롯을 다 사용한 경우에는 TlsAlloc이 0을 리턴하고 확장 슬롯을 할당한다.
- TerminateThread API를 이용해서 스레드를 종료하면 (배열인) 확장 슬롯의 메모리가 해제되지 않아 메모리 누수가 발생한다.
암시적인 TLS
__declspec(thread)변수- API를 이용하는 것과 효과는 비슷하지만 내부 구현은 꽤 다르다.
- 변수를 __declspec(thread)로 선언하면, 컴파일러와 링커는 실행가능한 이미지의 특정 위치에 이 변수가 사용할 수 있는 공간을 만든다.
- 이와 같은 변수는 모두 PE 이미지에 있는 .tls 섹션에 위치한다.
-
TLS on Windows 에 대한 아주 좋은 글 : http://www.nynaeve.net/?p=180
- http://msdn.microsoft.com/ko-kr/library/9w1sdazb.aspx
- http://msdn.microsoft.com/ko-kr/library/2s9wt68x.aspx
- 주의할 점 : http://rein.upnl.org/wordpress/archives/755
- .tls : http://kai127.springnote.com/pages/1775028 http://sweeper.egloos.com/1985738
TLS 클래스 만들기
TLS 타이머
TLS를 이용한 빠른 메모리 관리자
간단하게만.. 자세한 내용은 메모리 관리자 편에서
