프로그래밍 언어 입문서가 아닌 프로그래밍 기초 개념 입문서
문과생, 비전공자를 위한 프로그래밍 입문책입니다.
jobGuid 꽃미남 프로그래머 "Pope Kim"님의 이론이나 수학에 치우치지 않고 실무에 곧바로 쓸 수 있는 실용적인 셰이더 프로그래밍 입문서 #겁나친절 jobGuid "1판의내용"에 "새로바뀐북미게임업계분위기"와 "비자관련정보", "1판을 기반으로 북미취업에 성공하신 분들의 생생한 경험담"을 담았습니다.
Posted by cagetu

나... 나도 병렬 프로그래밍 할래!! - #2

친절한 티스님이 연재하고 계시는 병맛.... 아니 병렬 프로그래밍에 대해서, 저도 관심이 많아서, 숟가락만 올리려고 합니다. ^^

시대가 병렬 프로그래밍을 원하는 시대이지만, 서버플머가 아닌 입장에서 거의 초보적인 지식만을 가지고 있는 상태입니다. 
따라서, 
이제 막 병렬 프로그래밍을 본격적으로 공부해보려고 하는 입장에서 과연 무엇을 먼저 공부해야 하나? 라는 생각이 들었습니다. 그래서, 차근 차근 밟아나가자를 생각에 만만한(?) "동기화 관련 내용부터 정리해보자!" 라고 결정했습니다. 
 


이미 많은 분들이 사용하시고 계시고, 아시는 내용이지만, 저 같이 잘 모르는 사람들도 있으니, 기초를 다지는 마음으로 정리하도록 해보겠습니다. (꼬꼬마들만 봅시다... ^^)



동기화(Synchronization)이란 무엇인가?

병렬 처리에서 동기화라는 것은 서로 다른 쓰레드 간의 실행 순서를 보장하기 위해서, 구속조건을 강제로 거는 것입니다.
동시에 여러개의 쓰레드가 동일한 자료를 접근하여 조작하고, 그 실행 결과를 접근하는 특정 순서에 의존하는 상황을 "경쟁 상황(race condition)"이라고 부릅니다. 
즉, 동기화란 쓰레드의 실행 순서를 구성하고 공유하는 데이터를 관리하는 것을 말합니다. 

동기화를 처리하는 유형은 일반적으로 상호배제(mutual exclusion)와 상태 동기화(condition synchronization)을 많이 사용하게 됩니다.
- 상호배제(mutual exclusion)
: 쓰레드가 공유 데이터를 사용하는 부분을 동기화 객체(critical section 등)로 블록시키는 방식입니다. 
상태 동기화(condition synchronization) 
: 시스템이 특정 상태로 도달하기 전까지는 쓰레드를 완전히 블록(block)시키는 방식입니다. 
 
동기화객체

- Critical Section
커널 객체를 사용하지 않으며, 그 내부 구조가 단순하기 때문에 동기화 처리를 하는데 있어서 속도가 빠르다는 장점이 있습니다. 하지만, 동일한 프로세스에서만 사용이 가능하다는 제약이 있습니다.
동일한 프로세스에서 다른 쓰레드의 방해를 받지 말아야 하는 작업을 할 때, 이 영역을 크리티컬 섹션으로 둘러싸면, 전역 자원의 독점권을 획득하게 됩니다.
 

커널 객체를 사용하는 동기화의 경우에는 신호 상태(Signaled)와 비신호 상태(Non-Signaled)의 두 가지 상태 중 하나로 존재를 하게 되며, 동기화 객체가 신호 상태(Signaled)가 될 때까지 이 커널 객체를 사용하려는 쓰레드는 대기하게 됩니다.
이런 경우, 대기 함수와 함께 사용하게 되는데, 대기 함수는 일정한 조건에 따라 스레드의 실행을 블록하거나 실행을 허가하 함수를 말합니다. 가장 대표적인 함수가 바로, "WaitForSingleObject" 입니다.

- Mutex
뮤텍스는 오직 한 쓰레드에 의해서만 소유될 수 있으며 일단 어떤 쓰레드에서 소유되면 비신호 상태가 됩니다. 반대로 어떤 쓰레드에서도 소유되어 있지 않는다면, 신호 상태가 됩니다. 기본적으로 크리티컬 섹션과 유사하게 사용이 가능합니다. 이름을 기반으로 프로세스 사이에서의 동기화에서도 사용이 가능하기는 합니다만, 그만큼 속도가 느립니다.
뮤텍스는 쓰레드가 여러 개 있더라도 자신이 소유한 쓰레드를 기억하고 있으며, 같은 쓰레드가 같은 뮤텍스를 중복 호출하더라도 데드락이 발생하지 않게 하고 있습니다. (내부적으로 카운트 체크를 해서, 카운트가 0이 되었을 때 신호 상태로 돌려줌)

- Semaphore
기본적으로 뮤텍스와 비슷하게 처리가 됩니다만, 세마포어는 사용자가 지정한 개수만큼 보호되는 자원에 대해서 접근할 수 있도록 합니다. 유효자원의 카운트가 0이 되면 세마포어는 비신호 상태가 되고, 카운트가 1 이상이면 신호 상태가 됩니다. 다른 쓰레드가 자원을 풀 때까지 대기하게 되고 세마포어가 1 이상이면 유효자원의 개수를 1 감소 시키고 곧바로 리턴합니다. 
 
- Event 

특정 사건의 발생을 다른 쓰레드에 알리는 경우에 사용합니다. 이벤트를 사용한 동기화는 다음과 같은 형태가 됩니다.
"이벤트 E를 비신호 상태로 생성. A 쓰레드가 작업을 진행하고 B 쓰레드는 E가 신호 상태가 될 때까지 대기한다. A 쓰레드가 작업을 완료하면, 이벤트 E를 신호 상태로 변경한다. B 쓰레드가 작업을 시작함"   

deadlock

절대 가용되지 않을 다른 쓰레드의 리소스를 기다리는 때 발생합니다. 

Deadlock이 발생하는 시나리오는 다음과 같습니다.
- self-deadlock
쓰레드가 임의의 타이밍에서 걸었던 lock이 풀리기 전 특정 타이밍에 그것을 사용하려고 할 때 발생. 한 쓰레드에서 일어나게 됨.

recursive deadlock
A 쓰레드를 깨우는 작업을 B에서 할 때

lock-ordering deadlock
2개 이상의 프로세스(쓰레드)들이 자원을 점유한 상태에서 각각 다른 프로세스(쓰레드)들이 점유한 자원을 요청하여, 서로 상대방의 작업이 끝나기를 무한정 기다리는 상태


Lock-Free

Volatile
volatile은 해당 객체(변수)가 OS나 하드웨어 또는 다른 쓰레드에 의해 변경될 수 있다고 알려 주는 키워드 입니다. 즉, 이는 컴파일러에게 해당 객체의 값이 언제든지 변경될 수 있으니, 최적화를 통해서 값을 미리 예상하지 말고, 항상 해당 객체를 참조하는 시점에서 값을 매번 다시 읽도록 하라고 알려주는 것입니다.

일반적으로 컴파일러는 소스 코드를 분석하여, 해당 변수에 대한 값이 변경되지 않을 것으로 예측되면, 이 값을 미리 저장해 두었다가 사용하는 방식으로 최적화를 수행합니다. 

하지만, 멀티 쓰레드 환경에서는 현재 실행되는 쓰레드에 의해서 값이 변경될수가 있습니다. 이를 때 volatile 키워드를 이용할 수 있습니다. volatile 로 선언된 변수는 실제 사용할 시점에서의 값을 참조하기 때문에, 동기화를 처리한 것과 같은 결과를 얻을 수 있습니다.

- Spinlock
"조금만 기다리면 바로 쓸 수 있는데 굳이 컨텍스트 스위칭으로 부하를 줄 필요가 있나?"

[출처] Spin-Lock/Mutex/Semaphore|작성자 즐겁게

 라는 컨셉으로 개발된 것으로 크리티컬 섹션에 진입이 불가능할 때 컨텍스트 스위칭을 하지 않고, 잠시 루프를 돌면서 재시도 하는 것을 말합니다. 

spinlock은 lock을 얻을 수 없다면, 계속 lock을 확인하며 얻을 때 까지 기다립니다. 즉, 무한루프를 돌면서 최대한 다른 스레드에서 CPU를 양보하지 않는 것입니다. lock이 바로 사용이 가능해질 경우에는 컨텍스트 스위칭의 비용을 줄여 CPU의 부담을 줄여줄 수 있지만, 반대로 다른 쓰레드가 lock을 오래 동안 유지하게 된다면, 오히려 CPU 시간을 너무 많이 소모하게 됩니다. 

따라서, Lock/Unlock 시간이 아주 짧아서 락을 하는 경우가 드믄 경우에 유용하게 사용해야 합니다.
 
- Lockfree algorithm
Lockfree 알고리즘을 이해하기 위해서는 먼저 Atomic Operation에 대해서 알아볼 필요가 있습니다.

atomic operation의 정의
1. 일련의 모든 연산이 끝날 때까지 다른 프로세스는 그 연산에 대한 어떠한 변화도 할 수 없다.
2. 전체 연산 중 어느 하나라도 실패할 경우, 모든 연산은 실패하여, 시스템은 전체 연산이 시작하기 전의 상태로 복구된다.

32비트 인텔 CPU (IA-32)에서 지원되는 Atomic Operation에 관해 알아보자. 다음과 같은 인텔의 CPU 연산들 앞에 LOCK을 붙여 해당 연산을 Atomic하게 만들 수 있다. 즉, 스레드간의 동기화를 신경쓰지 않아도 된다. 자세한 것은 인텔사 웹싸이트에서 제공되는
 개발자 매뉴얼을 참고하기 바란다.

ADD, ADC, AND, BTC, BTR, BTS, CMPXCHG, CMPXCH8B, DEC, INC, NEG, NOT, OR, SBB, SUB, XOR, XA
 
Win32의 Atomic Operation은 Interlockedxxx() 함수로 제공된다. 
간단하게, 차이를 살펴보면 다음과 같다.
  // atomic하다.
  GlobalCounter = 0;   
 
// 이것은 atomic하지 않기 때문에, 멀티 쓰레드에서는 결과를 예측할 수 없다.   ++GlobalCounter;
// atomic incremenet  
 InterlockedIncrement(&GlobalCounter);


Lock-free는 Spinlock과 유사하게 작업을 완료하는 내부적으로 루프를 돌면서 재시도를 하는 방식입니다.
Lock-free 알고리즘에서는 비교 후 교환(Compare-And-Swap)이 가장 중요합니다. 그 이유는 Lock-free 에서는 Lock을 사용하지 않기 때문에, 다른 쓰레드가 이미 그 변수의 값을 변경했을 수가 있습니다. 물론, 발생 확률은 대체로 낮으므로, 변경되지 않았을 것이라고 가정하는 낙관적인(Optimistic) 방법이 Lock-free에 사용됩니다. 따라서, CAS(Compare-And-Swap: InterlockedCompareExchange)을 이용해서, 공유변수가 가정하는 값과 같으면 다음 단계로 넘어가고, 만약 변경되었다면, 재시도하는 방법으로 Lock 없이 동기화가 가능하도록 프로그래밍을 할 수 있습니다.
(즉, InterlockedCompareExchange(&v, b, a) 라는 함수를 보면, v의 값이 a와 같다면, v에 b를 대입하라는 의미입니다. 리턴값은 v가 값이 바뀌기 전의 v의 값을 나타냅니다.)

간단하게, Stack Push에 대한 예제를 보도록 하겠습니다.
void Push(Node* pNewNode)
{
 do {
   Node* t = pTopNode;
   pNewNode->pNext = t;
 } while( !CAS(&pTopNode, t, pNewNode) );
}

마무리
지금까지 병렬프로그래밍에서 기본적으로 알고 있어야 하는 동기화에 관련해서 정리를 해보았습니다. 당연한 이야기 이지만, 동기화에 대해서는 완벽하게 알고 있어야, 병렬 프로그래밍을 잘 할 수 있겠죠?! ㅎ. 특히, 최근에 주목을 받고 있는 Lock-Free와 같은 알고리즘은 그 효능(?)에 대해서 아직도 의견이 엇갈리고 있기도 합니다.
(기초적이고 많이 알려진 내용이라 자세하게 설명하는 것 보다는 간단하게 성격만을 정리하였습니다. (사실 저도 잘 알지 못합니다.. ^^;; 인터넷을 통해서, 관련된 내용의 샘플소스를 같이 보시면 더욱 좋을 것 같습니다.)

하지만, 동기화처리를 통해서 모든 것을 할 수 없기 때문에, 얼마난 논리적으로 전체적으로 설계를 잘 하느냐?가 중요할 것입니다.  단지, 동기화 처리에 대한 개념이 이제 시작일 뿐입니다. 


저의 입방에서는 궁극적으로는 "효율적인 Multithread 기반 게임 엔진을 만들 수 있을까?"혹은 "게임엔진에서 병렬프로그래밍을 최대한 활용할 수 있을까?"에 대한 답을 얻는 것이 목적입니다.

앞으로는 이와 관련해서, 데이터 처리, 멀티코어 엔진 아키텍쳐 등과 같은 내용들에 대해서 아마 지속적으로 볼 생각입니다.
(사실 이 주제는 "친절한 티스"님의 주제고 저는 그냥 숟가락만 올렸을 뿐입니다. ㅎㅎㅎ)

어설픈 내용을 봐주셔서, 감사합니다. ㅎㅎ
 

참고자료
-  Window 구조와 원리 그리고 Codes (정덕영)
-  Threading and Parallel Programming Constructs
-  Lockless Programming Considerations for Xbox360 and Microsoft Windows  
-  Non-blocking algorithm
http://choiwonwoo.egloos.com/1176220 : Atomic Operation
-  Kasa Study : Lock-Free (김성헌)
TAG

댓글을 달아 주세요

  1. Favicon of https://gamedevforever.com 끼로 2012.02.02 23:07 신고  댓글주소  수정/삭제  댓글쓰기

    우와!!! 전 그럼 두분만 따라가겠습니다!!! 우... 우리 병렬 프로그래밍 해요!!!

  2. Favicon of https://gamedevforever.com ozlael 2012.02.04 15:27 신고  댓글주소  수정/삭제  댓글쓰기

    우와 듀엣곡이당

  3. Favicon of https://gamedevforever.com 죠쉬 2012.02.07 13:36 신고  댓글주소  수정/삭제  댓글쓰기

    오오... 갑자기 막 불타오릅니다.
    PS3에 설치했던 옐로독이나 다시 부팅해 볼까

  4. Favicon of http://bluekms21.blog.me 크로스 2012.02.14 15:45  댓글주소  수정/삭제  댓글쓰기

    이..이건..
    정말 황금같은 정리네요!
    본문과 출처를 모두 제 개인 블로그에 스크랩 해두고 싶은데 괜찮으실런지요??

  5. Favicon of http://bluekms21.blog.me 크로스 2012.02.15 10:57  댓글주소  수정/삭제  댓글쓰기

    http://bluekms21.blog.me/10131877847

    감사합니다. 본문은 수정하지 않고 출처 표기하여 위와같이 포스팅 했습니다.
    정말 다시봐도 좋은 정리네요.. 음음.. 멋질 정도입니다

  6. 둔한이 2012.02.15 20:02  댓글주소  수정/삭제  댓글쓰기

    질문이있는데요 예제소스에서 CAS라는 펑션의 파라미터가 InterlockedCompareExchange와 같다면 t와 pNewNode의 순서는 바뀌어야하는게 아닌가요?

    • Favicon of https://gamedevforever.com cagetu 2012.02.16 08:20 신고  댓글주소  수정/삭제

      말씀하신게 맞아요.
      보통 논문등에서 표기할 때는 CAS(v, a, b); 로 표시하는데, Interlock 함수는 (v, b, a)로 사용합니다.

      내용에서 빠졌네요. ㄱㅅㄱㅅ. ㅎㅎ