“The Art of Multiprocessor Programming” 을 다시 읽기 시작하면서, 낙관적 동기화(Optimistic synchronization) 혹은 lock-free에 대한 재미있는 비유를 발견하였습니다. 아래 원문과 제가 이것을 번역한 것을 복사하여 놓았습니다. 어딘가 잡지에서 나왔을 법한 유머지만, 멀티프로세서에서 lock-free 프로그래밍을 하는 것에 대한 적절한 비유가 아닐까 생각합니다.
A tourist takes a taxi in a foreign town. The taxi driver speeds through a red light. The tourist, frightened, asks “what are you are doing?” The driver answers: “Do not worry, I am an expert.” He speeds through more red lights, and the tourist, on the verge of hysteria, complains again, more urgently. The driver replies. “Relax. relax. you are in the hands of an expert.” Suddenly, the light turns green, the driver slams on the brakes, and the taxi skids to a halt. The tourist picks himself off the floor of the taxi and asks “For crying out loud, why stop now that the light is finally green?” The driver answers “Too dangerous. could be another expert crossing.”
한 여행자가 외국 도시에서 택시를 탔다. 택시기사는 빨간 신호등을 무시하고 속도를 내며 지나갔다. 여행자가 불안해하며 "뭐하시는 겁니까?"라고 물었다. 택시기사는 "걱정 마세요. 저는 전문가입니다." 라고 대답했다. 택시기사는 몇 개의 빨간 신호를 더 지나갔고 여행자는 겁에 질려, 보다 다급히 불평했다. 택시기사는 "당신은 전문가의 손 안에 있으니, 편하게 있으세요"라고 대답했다. 갑자기 신호가 녹색으로 바뀌자 택시기사는 급제동했고 택시는 미끄러지며 정차했다. 여행자는 택시 바닥에서 몸을 일으키며 큰 소리로 물었다. "이제 마침내 녹색불이 켜졌는데 왜 정차합니까?" 택시기사는 "너무 위험하오. 다른 전문가가 지나갈수 있습니다."라고 답했다.
학창시절 운영체제(OS) 시간에 쓰레드 퀀텀 (quantum) 혹은 시분할 (time slice)에 관해 배운 적이 있습니다. 최근 우연히 팀 프로그래머 중 한 명이 윈도우즈 서버에서 퀀텀의 크기가 상당히 크다는 것을 다시 상기시켜 주었습니다.
Windows Internals 책에 따르면 윈도우즈 XP의 경우는 6, 윈도우즈 서버의 경우는 36의 퀀텀 값을 갖는다고 합니다. (3 퀀텀이 1 클럭에 해당함)
보통 인텔의 멀티프로세서 시스템은 1 클럭 간격이 15ms 이므로, XP는 30ms, 서버는 180ms의 시간이 (한 번의 쓰레드 스케줄링으로) 하나의 쓰레드에 할당되는 것 입니다.
물론 쓰레드가 대기(wait)상태로 들어간다면, 이 퀀텀을 다 사용하지 못하고 context switch가 일어 날 수 있습니다.
이러한 퀀텀 값은 또한 윈도우즈의 Performance Option 에서 변경 가능 합니다. (Application = 6 퀀텀 혹은 Background Service = 36 퀀텀 둘 중 선택 가능)
원도우즈 서버가 180 ms라는 상당히 큰 퀀텀 값을 가지는 이유는 서비스 어플리케이션 쓰레드에게 작업을 수행할 충분한 시간을 주기 위함입니다. 또 잦은 context switch는 전체 성능을 저하시킬 수 있기 때문입니다. 하지만 XP와 같은 Client OS의 경우 사용자에게 빠른 응답을 하는 것이 중요하므로 (예를 들면 UI 쓰레드) 작은 퀀텀 값을 갖는 것입니다.
최근에 구글은 Chrome 웹브라우저를 발표하였습니다. 그런데 흥미로운 점은 Chrome의 장점을 만화로 설명하는 온라인 책을 만들었는데, 그 내용은 전산학 OS강의를 방불케 합니다. 메모리 단편화(fragmentation)과 스레딩에 대해 설명하고 있으며 Chrome이 성능향상과 안정성을 위해 각각의 탭이 독립적인 프로세스에서 돌아간다고 합니다.
오랜동안 실행 중인 서버 프로그램이 갑자기 아무 이유없이 크래시를 일으키는 경우를 가끔 볼 수 있습니다. 그 이유 중 하나가 마찬가지로 메모리 단편화일 것입니다. 충분한 물리 메모리가 있음에도 불구하고 가상메모리가 단편화 되어 더 이상 메모리 할당이 불가능해질 수 있다는 것이지요.
그런데, 최근에 저는 또 한가지 이유를 발견하였는데 바로 스택 보호 페이지가 리셋되는 경우입니다. "단순히 정상인 메모리를 읽기만 함"으로써도 프로그램을 크래시 시킬 수 있다는 약간은 놀라운 사실입니다.
윈도우즈의 각각의 스레드 스택은 기본으로 1MB가 예약되어 있습니다. 하지만, 1MB전부가 commit (물리메모리로 매핑)된
것은 아니며, 스택 보호 페이지라는 것을 만들어 스택 크기가 커져 이 보호페이지를 액세스하게되면 예외(exception)가
발생하며, 이 때 OS 커널은 해당페이지를 Commit하고 새로운 보호페이지를 설정합니다. 아래 그림을 참고하시기 바랍니다.
이러한 방법으로 처음부터 모든 스레드에 1MB의 물리메모리를 스택으로 할당하지 않아도 되기 때문에 메모리 낭비를 상당히 줄일 수 있습니다.
문제는 어떤 특정 스레드의 스택 보호 페이지를 다른 스레드나 프로세스에서 읽기를 시도하는 것만으로도 보호 페이지가 리셋되어 사라지게 되며 이 경우 재설정이 되지 않고 스택크기도 늘어나지 않습니다.
보호 페이지가 사라진 상태에서 당장 문제가 나타나지는 않으나, 나중에 스택 보호 페이지가 없는 스레드가 스택을 많이 사용하게 되어 보호 페이지와 그 위의 commit되지 않은 페이지를 액세스하게 되면 Access Violation나며 어플리케이션이 종료될 가능성이 높습니다. 어플리케이션의 예외처리기 (unhandled exception handler)를 사용하여 오류 분석을 해봐도 원인을 찾기는 쉽지 않습니다.
이 문제를 실제로 보여주는 예제가 아래에 있습니다. 아래 코드를 복사하여 BrokenGuardPage.cpp라는 이름으로 저장한 다음, "cl BrokenGuardPage.cpp"와 같이 컴파일하면 예제 실행파일을 만들 수 있습니다.
AccessStackGuardFromOtherThread 함수는 새로운 스레드 하나를 생성하고 있으며 지역변수의 포인터를 새로운 스레드에 전달합니다. 새로 생성된 스레드는 전달된 지역변수 메모리값에 -0x2000을 하여 스택보호 페이지에 대해 읽기 만을 시도합니다.
이 프로그램을 실행하면 프로그램 STATUS_GUARD_PAGE_VIOLATION 예외가 먼저 발생합니다. 이 때 Unhandled exception handler가 설정되어 있어 프로그램은 종료하지 않고 계속실행이 됩니다. 다음으로 Crash 함수가 main 스레드로 부터 호출되는데, Crash는 단순히 큰 지역변수를 가지고 이를 초기화하려고 시도하고 있습니다. Crash 함수에 잘못된 코드는 전혀 없습니다만, Access Violation을 발생하며 프로그램이 종료되어 마지막의 "printf("End of Program.\n")"는 실행되지 않습니다.
//////////////////////////////////////////////////////////////// // // BrokenGuardPage.cpp // // Just use following commands for compile: // cl BrokenGuardPage.cpp // // www.devnote.net (9/26/2008) // ////////////////////////////////////////////////////////////////
같은 프로세스에서 뿐만 아니라, 읽기 메모리 권한(PROCESS_VM_READ)을 다른 프로세스에 부여하는 것만으로도 똑같이 프로그램 크래시를 유발할 수 있습니다. 또한 예외처리 핸들러에서 가끔 사용되는 IsBadxxxPtr API들도 똑같은 문제를 유발시킵니다. 아래 블로그를 참고하시기 바랍니다.
위 페이지의 첫번째 예제같이 보통 단순한 전역 bool 값을 사용하는 경우는 쉽게 문제를 알아낼 수 있지만, static object를 함수 안에 사용하는 경우 컴파일러가 내부 최적화하는 과정에서 전역변수 (두번째 예제의 "constructed")를 만들어 내기 때문에, 모르고 지나칠 가능성이 많습니다.
그러니까, 특히 C++를 사용한 멀티스레드 프로그램에서는 local static 변수를 사용을 자제하는 것이 좋겠습니다.
인텔, AMD, nVidia와 같은 칩메이커들은 멀티코어 CPU 개발과 함께 GPGPU (General-Purpose computation on GPUs) 연구 개발에 많은 노력을 하고 있습니다. 가장 큰이유는 멀티코어 CPU보다 가격이 훨씬 싸다는 점에 있습니다. GPGPU는 General-Purpose라는 이름에서와 같이 그래픽스에 관련된 연산뿐만 아니라 멀티스레드로 동시 실행가능한 어떠한 연산도 수행할 수 있다는 점이 매우 흥미롭습니다. 아래 몇가지 링크를 복사해 놓았습니다.
그런데, 이 Parallel FX Library가 어떻게 구현되었을까하는 궁금증을 가지고 있던 차에, .NET 바이너리를 디컴파일하여 소스를 보여주는 .NET Reflector 덕분에 내부를 들여다 볼 수 있었습니다.
간단히 말해 기본 구조는 MIT 대학에서 개발되었던 Cilk 에서 많은 부분을 빌어 왔다는 것을 알 수 있었습니다. Cilk는 1990년대 중반부터 개발되어 온 것이며 Work Stealing이라는 작업 스케줄링 개념을 만들어 내었습니다. .NET PFX도 Work Stealing을 그대로 적용시키고 있습니다.
PFX에서 핵심적으로 사용되는 자료구조 중에 "ConcurrentStack", "ConcurrentDeque (TakeQueue)", "ConcurrentListBag" 가 사용되고 있는데 이들은 대부분의 경우 Lock-free로 동작하도록 되어있습니다. .NET Reflector를 이용하면 소스를 살펴 볼 수 있습니다. 이들도 MS가 새로운 알고리즘을 개발한 것은 아니고, 모두 기존에 발표되었던 논문에 바탕하여 .NET에 적용한 것입니다.
하지만, NET의 Garbage Collector의 도움으로 이러한 Lock-Free 자료구조 제작이 C/C++에 비해 손쉽게 되었습니다. 다시 말해 Lock-Free의 난제들 중의 ABA문제와 메모리 액세스 문제(다른 스레드가 해제한 메모리를 참조하려고할 때 메모리 액세스 오류의 가능성이 있음)가 Garbage Collector로 인해 자동으로 제거되었다는 것입니다.
좀 극단적으로 말하면 PFX는 Cilk의 .NET 버전이라고 할 수 있습니다. 그만큼 Cilk에서 많은 부분을 빌어왔지만, 그다지 혁신적인 내용이 추가되지는 않았다는 것 입니다.
Java를 이용한 JCilk가 이미 발표된 지금, 늦은 감이 있으나 MS는 PFX 라이브러리로 .NET에서 병렬프로그래밍을 손쉽게 제공하려고 노력하고 있음을 알 수 있습니다. 하지만, 이것이 성공할지는 조금 더 지켜봐야 할 것 같습니다.
윈도우즈에서 제공되는 동기화 오브젝트 중에 가장 많이 사용되는 것이 CRITICAL_SECTION이다. 언젠가 Spinlock을 만들어 윈도우즈의 CRITICAL_SECTION과 비교한 적이 있는데, 놀랍게도 10배정도 빠르게 나타났다. 물론, 테스트 프로그램은 모든 스레드가 계속해서 lock을 얻으려고 쉬지 않고 경쟁하기 때문에, 일반적으로 일어날 수 있는 상황은 아니지만 10배 빠른 것은 좀 의외였다.
그런데, 윈도우즈 비스타에서 CRITICAL_SECTION은 XP보다 상당히 빠른 것으로 나타났다. 하지만, 역시 내가 만든 Spinlock보다는 느리게 나온다. 아래 XP와 Vista의 EnterCriticalSection API의 어셈블리 코드를 보면, XP에서는 SpinCount를 우선 확인한 후 LockCount를 Atomic Operation을 사용하여 1만큼 증가를 시도하지만, Vista에서는 비트 연산인 "Lock btr"을 사용하여 최하위 비트의 유무를 검사하는 것으로 단순화 되었다. 이 코드는 EnterCriticalSection API의 일부분으로 더 많은 변화가 있음을 짐작할 수 있다. Bit연산 Atomic Operation을 사용한 최적화라고 짐작된다.
그런데, Spinlock 보다 여전히 효율이 떨어지는 이유는, lock contention이 발생했을 경우 이벤트 대기 상태로 바로 바뀌고 컨택스트 스위치가 일어나기 때문일 것으로 생각된다. 나의 Spin lock은 lock을 얻지 못해도 어느 정도 재시도를 거듭한다. 테스트 프로그램은 다른 작업은 거의 하지 않고 Lock을 얻기위해 일정 시간을 실행하므로 Spinlock의 재시도 루틴이 큰 효과를 발휘하는 것이다. 따라서, 테스트 프로그램의 결과를 일반화 시키키는 좀 무리가 있다.
