스레드, 데이터 경쟁, 교차 잠금, 라이브 잠금
Common problems in multi-core programming, Part 1: Threads, data races, deadlocks, live locks 중 핵심만 발췌 번역한 글이다.
지나치게 많은 스레드
스레드가 너무 많으면 프로그램의 성능이 심각하게 떨어진다. 그 영향은 두 가지 방식으로 이뤄진다. 첫째, 정해진 분량의 일을 여러 스레드에 분배하면 스레드 하나하나는 할 일이 별로 없게 된다. 그래서 스레드를 시작하고 종료하는 비용이 실제로 하는 일의 양을 압도하게 된다. 둘째, 소프트웨어 스레드가 너무 많으면 한정된 하드웨어 자원을 공유하는데 드는 비용이 커진다.
하드웨어 스레드보다 소프트웨어 스레드가 많을 때 운영체제는 보통 라운드 로빈 스케줄링을 이용한다. 스케줄러는 소프트웨어 스레드마다 타임 슬라이스(time slice)를 부여하여 하드웨어 스레드 중 하나에서 실행될 수 있게 한다.
소프트웨어 스레드의 타임 슬라이스가 떨어지면 스케줄러는 그 스레드를 멈추고(suspend) 해당 하드웨어 스레드에 다른 소프트웨어 스레드를 돌린다. 소프트웨어 스레드는 다음 타임 슬라이스를 얻을 때까진 잠시 동결된다.
타임 슬라이스 덕분에 모든 소프트웨어 스레드에게 기회가 주어진다. 타임 슬라이스가 없다면, 일부 소프트웨어 스레드가 하드웨어 스레드를 몽땅 독점해 다른 소프트웨어가 굶게 할 것이다. 하지만 이렇게 하드웨어 스레드를 공정하게 분배하려면 오버헤드가 걸린다. 소프트웨어 스레드가 너무 많으면 오버헤드 때문에 성능이 심각하게 저하될 수 있다. 여기서 말하는 오버헤드는 종류가 다양한데, 이를 알아두면 나중에 문제가 발생했을 때 범인을 찾는데 도움이 된다.
스레드 레지스터 상태
가장 명백한 오베헤드는 스레드의 레지스터 상태를 저장하고 복구하는 과정이다. 소프트웨어 스레드를 일시 중단(suspend)하려면 하드웨어 스레드의 레지스터 상태를 저장해야 한다. 그래야 다음 타임 슬라이스 때 소프트웨어 스레드가 값을 복구할 수 있기 때문이다. 일반적으로, 스레드 스케줄러는 타임 슬라이스를 상당히 크게 잡기 때문에 레지스터를 저장하고 복구하는 오버헤드는 미미하다. 그러니 이 경우는 그리 걱정할 필요 없다.
스레드 캐시 상태
이보다 미묘한 문제는 스레드의 캐시 상태를 저장하고 복구하는 오버헤드이다. 현대 프로세서는 캐시 메모리에 상당히 의존한다. 캐시 메모리는 주 메모리보다 10배에서 100배 빠르다. 캐시에 적중하는 경우는 접근이 빠를 뿐더라 메모리 버스의 대역폭도 소모하지 않는다. 하지만 캐시는 빠르긴 해도 유한한 자원이다.
캐시가 꽉 찼을 땐, 프로세서가 새 데이터가 들어갈 자리를 마련하기 위해 캐시에서 데이터를 제거해야 한다. 보통 제거할 데이터를 고를 때 최근에 사용되지 않은 데이터(Least Recently Used, LRU)를 고른다. 이렇게 하면 대개 이전 타임 슬라이스의 데이터가 선택된다. 그렇기 때문에 스레드는 서로 상대방의 데이터를 제거하곤 한다. 정리하자면 스레드가 너무 많으면 서로 캐시를 차지하려고 다투기 때문에 성능이 저하된다.
가상 메모리 스레싱
비슷하긴 하지만 그 수준은 다른 오버헤드가 바로 가상 메로리 스레싱이다. 대부분의 시스템은 가상 메모리를 사용하는데, 프로세서는 실제 사용가능한 주소보다 큰 주소 공간을 가진다. 가상 메모리는 디스크에 위치하며, 자주 사용되는 부분은 실제 메모리에 있다. 캐시와 비슷하게 공간이 필요할 때는 최근에 사용되지 않은 데이터가 메모리에서 제거된다.
소프트웨어 스레드 각각은 스택과 데이터 구조를 유지하려고 가상 메모리를 사용한다. 캐시와 마찬가지로 타임 슬라이스는 실제 메모리를 두고 소프트웨어 스레드끼리 경쟁하게 만들며 이는 성능을 떨어뜨린다. 극단적인 경우엔, 스레드가 너무 많아서 프로그램이 가상 메모리를 고갈시키기도 한다.
Convoying
여태 설명한 캐시와 가상 메모리 이슈는 너무 많은 소프트웨어 스레드가 제한된 자원을 공유하기 때문에 발생한다. 이와는 다르고, 이보다 심각할 때가 많은 문제도 있는데 convoying이라고 한다. Convoying은 잠금 하나를 두고 여러 소프트웨어 스레드가 산더미처럼 쌓이는 현상이다.
스레드가 잠금을 쥔 상태에서 해당 스레드의 타임 슬라이스가 만료되었다고 해보자. 그 잠금을 기다리던 스레드 모두는 그 스레드가 일어나 잠금을 풀기만을 기다려야 한다. 잠금 구현이 공정하다면, 그러니까 먼저 잠금을 획득한 순서대로 처리하는 구현이라면 문제는 심각해진다. 대기 중인 스레드가 잠시 중단되면 그 뒤를 이어 기다리는 스레드는 어느 것도 잠금을 획득하지 못하게 된다.
해결책
보통 가장 좋은 해결책은 \’실행 가능한\'(Runnable) 스레드의 개수를 하드웨어 스레드의 개수에, 가능하다면 외부 캐시(Outer-level cache)의 개수에 맞추어 제한하는 것이다.
예를 들어, 듀얼 코어 인텔 펜티엄 프로세서 익스트림 에디션은 물리 코어가 둘이며, 각각은 하이퍼 스레딩 기술과 캐시를 탑재한다. 이러한 구성은 네 개의 하드웨어 스레드와 두 개의 외부 캐시를 지원한다.
실행 가능한 스레드 네 개를 모두 사용하는 게 최선일 것이다. 스레드에 캐시가 너무 많이 필요해서 캐시를 두고 서로 싸우는 일이 벌어지지 않는다면 말이다. 그런 경우라면 스레드를 둘만 두는 편이 최선일지 모른다. 확실하게 하려면 실험하는 수밖에 없다. 스레드 개수를 하드코딩하지 말고 튜닝 매개변수로 남겨두자.
실행 가능한 스레드, 그러니까 차단되지 않은 스레드는 타임 슬라이스 오버헤드를 유발한다. 스레드가 외부 이벤트, 이를테면 마우스 클릭이나 디스크 입출력 요구 등을 기다리느라 차단되면, 운영체제는 라운드 로빈 스케줄링을 취한다. 그러므로 차단된 스레드 때문에 타임 슬라이스 오버헤드를 일으키진 않는다. 대부분의 운영체제 스레드가 차단되었다면, 하드웨어 스레드보다 소프트웨어 스레드가 많더라도 효율적으로 실행될 수도 있다.
도움이 될만한 조직화 원칙을 말하자면, 입출력 스레드와 계산 스레드를 분리하라는 것이다. 계산 스레드는 대부분의 시간에 실행 가능한 스레드여야 한다. 이상적으론 계산 스레드는 외부 이벤트 때문에 차단되는 일이 없어야 하고, 작업 큐에서 일거리를 받아 계속 뭔가를 해야 한다. 계산 스레드의 개수는 프로세스 자원에 맞춰야 한다. I/O 스레드는 대부분의 시간을 외부 이벤트 때문에 대기하는 스레드이다. 그러므로 이런 스레드는 많아도 문제되지 않는다.
유용한 프로그래밍 기법
효율적인 작업 큐를 구축하려면 상당한 전문지식이 필요하다. 일반적으로 제일 좋은 방법은 기존 소프트웨어를 활용하는 것이다. 흔히 사용하는 기법은 다음과 같다.
- OpenMP를 사용한다. OpenMP 는 스레드를 대신 루프 순회만 명시해도 되게 해준다. OpenMP는 알아서 스레드를 관리한다. 프로그래머가 스레드 개수를 특별히 지정하지 않는 한, OpenMP가 알아서 최적의 소프트웨어 스레드 개수를 찾아낸다.
- 스레드 풀을 이용한다. 불행하게도 POSIX 스레드에는 표준 스레드 풀에 대한 지원이 빠졌다. 프로그래밍 환경마다 스레드 풀의 구현과 사용법이 다르다.
- 전문가라면 스스로 작업 스케줄러를 작성하고 싶을지 모른다. 이럴 때 사용하는 방법이 작업 훔치기(Work stealing)이다. 스레드마다 자신만의 작업 목록을 가진다. 스레드 하나가 작업을 다 처리하고 나면, 그 스레드가 다른 스레드의 작업 목록에서 작업을 훔쳐 온다. 작업 훔치기는 캐시 사용률을 높이고 부하를 분산시킨다. 스레드가 자기 목록을 처리하는 동안엔 캐시에 든 데이터를 재활용할 가능성이 높다. 작업 목록이 고갈되어 다른 스레드의 작업을 훔치면 부하가 분산된다. 작업 훔치기를 효율적으로 구현하려면, 할 일이 떨어진 스레드가 큰 작업을 훔쳐서 한동안 바빠지도록 만들면 된다. 초기 Cilk 스케줄러가 이러한 구현을 보여주는 좋은 사례이다.
데이터 경쟁, 교차 잠금, 라이브 잠금
공유된 메모리에 대한 동기화되지 않은 접근은 경합 상태를 유발할 수 있다. 이런 상태에선 프로그램의 결과가 여러 스레드의 상대적인 타이밍에 따라 비결정적이게 된다.
파악하기 쉬운 경합만 있다면 병렬 프로그래밍은 한결 쉬워질 것이다. 하지만 똑같은 경합일지라도 프로그래밍 문법에 따라 다양한 방식으로 가리곤 한다. 스레드가 데이터를 인출하고 갱신하는데 하나의 명령어만 쓰더라도, 하드웨어가 그 명령어를 분해해 여러 번의 읽기와 쓰기로 엮을지도 모를 일이다.
불일치 (misaligned) 적재와 저장도 (만약 이런 게 지원된다면) 보통 원자적이지 않다. 이런 경우에 프로세서는 두 개의 연속된 캐시 라인에 대해 따로따로 접근한다.
데이터 경쟁은 공유된 메모리에 동기화되지 않은 접근을 할 때만 발생하진 않는다. 동기화된 접근일지라도 지나치게 저수준에서 동기화를 한다면 문제가 된다.
예를 들어 잠금을 이용해 리스트의 메서드를 동기화한다고 해보자. 동일한 키가 리스트에 있는지 확인하는 Has 메서드 내부에 동기화 코드가 있다. 그리고 새 요소를 삽입하는 Insert 메서드 내부에도 동기화 코드가 있다. 이때 동일한 키가 있는지 확인하고, 그런 키가 없을 때만 삽입하는 새로운 메서드 InsertUniqueItem 을 추가한다고 하자. Has와 Insert 는 각각 동기화를 보장한다. 하지만 한 스레드가 Has 로 확인하고 Insert를 미처 실행하기 전에 또 다른 스레드가 Has 로 값이 있는지 확인한다면 InsertUniqueItem 의 동기화는 깨진다. 그러므로 InsertUniqueItem에 Has와 Insert 를 묶는 잠금을 또 추가해야 한다.
이렇게 잠금을 하나 더 추가하니 그만큼 성능을 손해본다. 저수준의 컴포넌트에 잠금을 두는 것은 시간 낭비일 때가 많다. 어차피 그 컴포넌트를 사용하는 고수준의 컴포넌트에 잠금을 두어야 할 것이기 때문이다. 그보다 낮은 수준의 잠금은 의미없는 오버헤드에 불과하게 된다.
다행히 이러한 시나리오에서 고수준의 잠금이 있으면 저수준의 잠금은 경합을 벌이지 않으며, 대부분의 잠금 구현은 경합이 없는 경우를 최적화하였다. 그렇기에 성능에 미치는 영향이 다소 완화된다. 하지만 쓸데 없는 잠금을 제거하는 게 제일 좋긴 하다. 물론 컴포넌트 자체적으로 내부 잠금을 제공해야 할 때도 있다.
교차잠금 다루기
경쟁 조건은 인터리브(Interleaved) 연산 때문에 망가질만한 곳에 잠금을 추가하면 보통 해결된다. 불행하게도 잠금은 나름의 해악이 있고 그 중에서도 교차잠금(Deadlock)이 악명 높다.
교차잠금이 보통 잠금 때문에 발생하긴 해도 스레드가 둘 이상의 공유 자원에 대해 배타적인 접근을 획득하는 경우라면 언제나 발생 가능하다. 잠금이 아닌 파일에 접근하는 경우를 떠올리면 이해하기 쉬울 것이다. 교차차잠금은 다음의 네 가지 조건이 모두 만족될 때만 발생한다.
- 각 자원에 대한 접근이 배탁적이다.
- 스레드가 어떤 자원을 든 채로 다른 자원을 요청할 수 있게 허용한다.
- 어떤 스레드도 자신이 획득한 자원을 양도하려 하지 않는다.
- 자원들을 획득하려 하는 스레드끼리 순환 구조를 이룬다. 한 스레드가 자원 하나씩을 든 상태에서 다른 스레드가 상대의 자원을 요청한다.
교차잠금은 이러한 조건 중 하나만 깨뜨려도 풀린다
교차잠금을 방지하는 가장 좋은 방법은 배타적인 접근이 필요한 자원을 복사하여 스레드마다 자신의 복사본을 갖는 것이다. 각 스레드는 잠금 없이 자원에 접근할 수 있다. 필요하다면 막판에 복사본을 한데 모아 단일 복사본으로 병합하면 된다.
복제를 하여 잠금을 없애면 교차 잠금을 방지하고 더 나아가 성능 확장성(Scailability)가 향상될 여지가 있다. 제거된 잠금이 경합의 근원이었다면 말이다.
복제를 하지 못하는 경우엔, 그러니까 정말로 자원의 복사본을 하나만 두어야 할 때는, 동일한 순서로 자원(잠금)을 확득하는 게 현명하다. 일관성 있게 순서를 정해 자원을 획득하면 교차 잠금을 방지할 수 있다.
어떤 순서가 편하냐는 상황에 따라 다르다. 만약 잠금마다 연관된 이름이 있다면 단순히 알파벳 순서에 따라도 괜찮다. 바보 같이 보일지 몰라도 적어도 대규모 프로젝트 한 곳에선 성공적이었다.
데이터 구조 하나에 잠금이 여럿 있다면 해당 데이터 구조의 토폴로지에 따라 순서를 정하면 된다. 연결 리스트라면 리스트에 등장하는 순서대로 아이템을 잠그면 될 것이다.
트리 구조라면 전위 순회(Pre-order traversal)에 따르면 된다. 이와 유사하게, 중첩된 구조를 취하는 컴포넌트라면, 그러니까 작은 컴포넌트가 모여 큰 컴포넌트를 이루는 경우라면, 보통 밖에서부터 안쪽으로 들어가는 순서를 따른다.
잠그는 순서가 명확하지 않을 때는 주소에 따라 잠금을 나열하면 된다. 이 접근 방식은 스레드가 모든 잠금의 주소를 안다는 가정이 필요하다. 잠금을 획득하기 전에 어떤 잠금이 필요한지 알아야 하지만 말이다.
// 잠금의 주소에 따라 순서대로 잠금 걸기
void AcquireTwoLocksViaOrdering(Lock& x, Lock& y)
{
assert(&X != &y);
if(&x < &y)
{
acquire x
acquire y
}
else
{
acquire y
acquire x
}
교차 잠금의 세 번째 조건은 어느 스레드도 자원을 양도하려 하지 않는다는 것이다. 스레드가 다른 자원을 획득하지 못할 때 자신이 가진 자원을 양도한다면 교차 잠금은 벌어지지 않는다. 이런 이유로 뮤텍스에는 \’try lock\’ 같은 루틴이 있다.
이런 방식은 잠금을 정렬하는 게 현실적이지 않을 때 유용하다. 스레드가 두 개의 잠금을 모두 얻으려다 실패하면 잠금을 모두 풀고 다시 시도하면 된다.
라이브 잠금은 스레드끼리 부딪히고 물러나기를 반복할 때 벌어진다. 아래 코드는 자원 획득에 실패하여 스레드가 물러날 때마다 기다리는 시간을 늘리는 방식으로 라이브 잠금을 풀려 시도한다.
// \'시도했다 물러나기\' 방식
void AcquireTwoLocksViaBackoff(Loack& x, Lock& y)
{
for(int t = 1; ; t *= 2)
{
acquire x
try to acquire y
if( y was acquired )
break;
release x
wait for random amount of time between 0 and t
}
}
언젠가는 충돌에 관여한 스레드 중 하나는 다음 작업으로 넘어가기에 충분할만큼 물러나게 될 것이다. 물러나기의 단점은 공정하지 않다는 것이다. 특정 스레드가 진전을 본다는 보장이 없다. 공정성이 중요한 이슈라면, 순서대로 잠그는 게 아마도 교차 잠금을 방지하는 최선의 방법일 것이다.
