어떤 procedure, function, 그리고 기타 각종 object들이 thread-safety하다는 이야기를 종종 듣는다. 여러 스레드가 이 자원에 동시에 접근하더라도 프로그램의 무결성이 보장된다. 이를 위해, Mutex나 semaphore로 공유 자원을 보호할 수도 있고, thread local storage라는 TLS를 이용해서 각자 스레드에 한정적인 데이터 사본을 쓰도록 해도 된다.

여담으로 mutex, semaphore로 보호하는 전통적인 lock-unlock 방식은 '최악'의 상황을 항상 가정하고 있다. 다른 스레드가 쓸 가능성이 단 0.01%라도 있으면 이렇게 해야 한다. 물론 이 공유자원이 그렇게 중요하지 않다면 무시할 수도 있다. 그리고 또 하나 어려운 점은 스레드 사이에서 공유가 되는 특정 자원을 mutex로 보호했다고 해도 이 자원이 안전하다고 100% 확신할 수 없다는 점이다. 다른 코드에서 이 공유 자원을 lock하지 않고 그대로 접근하면 오류가 생길 수 있기 때문이다. 이러한 어려움을 풀기 위해 제안되고 있는 방법이 transactional memory이며, 요즘은 하드웨어에서 이를 효율적으로 지원하는 방법이 한창 연구 중이다. 상당히 흥미로운 분야인데 이 이야기는 나중에 시간이 되면… (사실 아는 것이 별로 없어서)

다시 thread-safety 이야기로 돌아가서, C-runtime 함수 중 많은 수는 static variable에 의존하는 경우가 많다. 대표적으로 토큰을 잘라주는 strtok 함수 군이 있을 것이다. 또, 난수 발생 함수인 srand와 rand 역시 static 변수를 사용한다. 대략적인 난수 seed를 설정하는 srand 함수의 구현은 다음과 같다.

보다시피 전역 변수를 사용하고 있다. 이런 경우 여러 스레드가 접근하면 문제가 발생할 수 밖에 없다. 그래서 이러한 경우 static variable대신, 스레드마다 주어진 별도의 공간, 즉 TLS로부터 얻어와야 한다. TLS는 Win32 API로 지원이 되고 다른 환경에서는 compiler extension으로도 지원이 된다. CRT 내부 구현에서는 _getptd() 라는 함수로부터 _ptiddata라는 스레드 마다 존재하는 자료구조를 이용한다. 다음 코드는 Visual Studio 2003 버전에서 가져온 rand 함수 구현 부분이다.

Multithread 환경일 때는 전역 변수 holdrand가 아닌 ptd 라는 TLS에 있는 holdrand에 값을 가져와서 사용함을 알 수 있다. 그리고 VS 2005의 rand 구현은 이 보다 더욱 간단해졌는데, 싱글스레드인 경우를 없애버렸다.

그래서 그런지 컴파일러 옵션 중 runtime library 항목 중에 이제 single thread 관련 항목은 빠졌다.

그럼, 본격 잡담으로 rand 함수 구조를 보면 퍽이나 간단하다. 이러한 방법은 Linear congruental generators라는 아주 오래 되고 또한 가장 많이 쓰이는 방법 중 하나이다.

보다시피 이러한 난수는 단순 수식에 의존하는, 말 그대로 유사-난수에 불과하다.

그렇다면 좋은 난수 생성기가 가져야 할 조건은 무엇일까? 대략 정리하면:

1. 가장 먼저, uniformly distributed 되어야 한다 (적당한 한글 표현이 잘). 그러니까 각각의 숫자를 얻을 확률이 균등해야 한다.
   
2. 이 숫자들은 서로 uncorrelated 되어야 한다. 예를 들어, 난수로 얻은 숫자를 (x, y)로 표현해서 그래프로 그리는데 직선 모양이라든지 어떠한 모양이라도 나오면 안 된다.
   
3. 순환 해서는 안 된다. 즉, 얻어지는 난수들을 쭉 늘어 놓았을 때 주기가 발견 되면 안 된다.
   
4. 재현이 가능해야 한다. 이것은 디버깅을 위해서 필수적인 기능이다. 흔히 이것은 "seed" 로 구현이 된다.
   
5. 빠른 시간에 계산 되어야 하고 메모리도 한정된 양만 사용해야 한다.
   

이 정도로 요약할 수 있다. 물론 이 조건을 다 만족하는 이상적인 난수 생성기를 컴퓨터에서 만들 수 없다. 특히 3번 조건을 만족하기는 쉽지 않다.

위에 예로 든 난수 함수 (linear congruential generator) 도 아주 오랫동안 돌려 보면 주기를 찾을 수 있다. 고등학교 때 이런 사실도 모르고 무식하게 rand 함수를 QBasic에서 하루 종일 돌려보니 한 10시간 정도 지난 뒤 같은 순열이 나오는 것을 발견 하기도 했었는데 그 때의 삽질이 떠오른다. 수식에서도 보듯이 M으로 mod 연산을 하고 있으므로 주기를 가짐을 쉽게 확인할 수 있다. 다만 이 주기를 아주 길게 해서 짧은 시간 동안에는 발견할 수 없도록 한 것이다. 그 밖에도 correlation 등의 문제가 있지만 대략 48비트 까지는 잘 작동한다고 한다.

다른 많은 방법 또한 많이 제시되어있는데 Lagged Fibonacci 방법이 있다. 이건 주기가 아주 길기 때문에 좀 더 좋은 품질의 난수를 얻을 수 있다. 이 방법은 하나의 seed가 아닌 다수의 seed를 요구하는 특징을 가지고 있다. 또, 병렬 컴퓨팅 환경에서는 추가적인 조건이 요구 된다. Scalability가 있어야 하며, 다른 machine에서 발생되는 난수와 관계 또한 없도록 해야 한다.

이렇게 난수 생성기를 만들고 나면 통계적인 방법으로 검증을 해야 한다. 예전 채널을 돌리다가 우연히 방송통신대에서 난수의 품질을 통계적인 방법으로 검증하는 강좌를 볼 수 있었다. 카이제곱으로 검정했던 것으로 기억하는데, 그 당시는 보면서 고개 끄덕이며 그렇지.. 했는데 지금은 기억나는 바가 전혀 없다(…)

Thread-safety를 하다가 난수 이야기로 빠져버렸는데 우리가 사용하는 rand 함수가 어떠한 단점을 가지고 있는지 아는 것도 좋을 것이다.

참고: 위 내용은 예전 병렬 프로그래밍 수업에서 배웠던 내용을 기반으로 작성 했음. 참고 교재는 "Parallel Programming in C with MPI and Open MP by Michael J. Quinn".

ps. 어떻게 하면 소스 코드를 예쁘게 붙여 넣을 수 있을까요? 그냥 캡쳐하는 것이 훨씬 편하네요.