멀티 스레드 프로그램 예제
From DevNote
Contents |
스레드 생성
윈도우즈에서 스레드를 생성하는 방법에 대해 알아 보자. C/C++를 사용할 경우 CreateThread API 함수를 사용할 수 있다. 아래와 같이 CreateThread를 호출하면 새로운 스레드를 생성한 후 그 스레드는 바로 ThreadProc을 호출하며 ThreadProc이 종료되거나 스레드를 생성한 프로세스가 종료될 때 까지 스레드는 계속 수행된다. 모든 스레드는 윈도우즈의 자체 스케줄러에 의해 자동 수행되며 멀티프로세서나 멀티코어 CPU를 가진 시스템일 경우 동시에 수행될 수 있다.
DWORD threadId;
HANDLE handle = (HANDLE) CreateThread(
(LPSECURITY_ATTRIBUTES) 0,
0, // stack size
ThreadProc,
(LPVOID)i, // argument
0,
&threadId
);
5개의 스레드를 생성시킨 후 각각의 스레드가 "Hello world!!!"를 출력하는 프로그램을 작성한다면 다음과 같다. ThreadProc은 "Hello world!!!"를 출력한 후 바로 return하여 스레드의 수행이 종료된다. WaitForMultipleObjects는 여러 개의 스레드가 모두 종료할 때 까지 기다리는 것이다. 이 프로그램이 처음 실행되면 main 함수에서 시작이 되는 데 이것도 역시 스레드이다. 다른점이라면 main 함수를 호출한 메인 스레드로서 이 메인 스레드가 종료되면 프로그램이 종료되므로 main스레드가 생성한 자식(child) 스레드들도 모두 같이 종료된다는 것이다.
CreateThread의 네번째 파라미터는 LPVOID 타입으로 임의의 값을 새로운 스레드에 넘겨 줄 수 있다. 아래 예제에서는 스레드의 일련번호를 정수(int)형으로 전달하였으며 생성된 스레드안에서 printf는 "Hello world!!! (%d)"와 같이 스레드 번호를 함께 출력한다.
//----------------------------------------------------------------------------
static DWORD WINAPI ThreadProc(LPVOID lpParameter) {
int threadNo = (int)lpParameter;
printf("Hello world!!! (%d)\n", threadNo);
return 0;
}
//----------------------------------------------------------------------------
void RunThreads (int maxThreads) {
HANDLE handles[MAX_NUM_THREADS];
for (int i = 0; i < maxThreads; i++) {
DWORD threadId;
handles[i] = (HANDLE) CreateThread(
(LPSECURITY_ATTRIBUTES) 0,
0, // stack size
ThreadProc,
(LPVOID)i, // argument
0,
&threadId
);
}
// Wait until all threads have terminated.
WaitForMultipleObjects(
maxThreads,
handles,
TRUE,
INFINITE
);
// Close thread handles
for (int i = 0; i < maxThreads; i++)
CloseHandle(handles[i]);
}
//----------------------------------------------------------------------------
void RunTests () {
RunThreads(5);
}
//----------------------------------------------------------------------------
int main(int argc, char * argv[]) {
RunTests();
return 0;
}
여기서 확실히 이해해야 할 점은 스레드들은 동시에 수행될 수 있으며 스레드들이 어떠한 순서로 실행될 것인지 또 언제 실행이 완료될 것인지에 대해 보장할 수 없다는 것이다.[1] 위의 예제는 간단하여 실행하면 대부분 스레드가 생성된 순서대로 1, 2, 3, 4, 5와 같은 값이 출력될 것이지만, 절대로 이러한 스레드 실행순서를 가정하고 프로그램을 제작해서는 안된다. 운영체제의 스케줄러는 보통 preemptive scheduler로서 스레드 수행 중간에 언제라도 다른 스레드로 컨텍스트 스위치될 수 있다. 이것이 시분할(time slice) 방식 멀티태스킹이다.
시스템에 별 문제가 없는 경우 보통은 모든 스레드들은 일정 시간이 지나면 다시 자신의 time slice를 받아 재실행된다. 하지만, 비정상적인 경우 자신의 time slice를 오랫동안 받지 못할 수 있다.
| 다른 알고리즘도 마찬가지지만 특히 멀티프로그래밍을 위한 병렬 알고리즘을 개발하는 데 있어 어려운 점은 100% 확실한 것이 아닌 것은 모두 0%로 생각해야 한다는 것이다. 나의 알고리즘이 99.9%의 경우 문제가 없다라고 한다해도, 일반적으로 사용될 수 있는 알고리즘으로 인정하기 쉽지 않다. 이러한 경우가 효율적인 병렬 알고리즘을 개발하는 경우 자주 발생되며 발견하기도 매우 어렵다. |
멀티스레드 프로그램으로 쉽게 제작하여 큰 성능향상을 볼 수 있는 프로그램은 주어진 문제가 1/N (N은 스레드 개수)로 분리되어 실행될 수 있는 경우이다. 이러한 방법을 작업량 분산(Load balancing)이라고 부른다. 이러한 경우가 실세계에서는 흔치 않다. 따라서 대부분 일부분만이 병렬수행 가능하다. 아래 병렬성이 매우 좋은 두가지 프로그램 예제를 살펴보자.
멀티스레드 예제 - Prime Number
1부터 5천만(50,000,000)까지 자연수 중에 소수(prime number)[2]를 구하는 프로그램을 멀티스레드로 제작해 보자. 가장 쉽게 생각할 수 있는 것은 각각의 스레드가 1/N (N은 총 스레드 개수)씩 나누어 소수를 구하는 것이다.
여기서 사용한 소수를 구하는 알고리즘[3]은 소수임을 테스트 하고자 하는 숫자 개수 만큼 50000000 배열을 가지고 자신의 배수가 되는 모든 수를 찾아 0로 셋팅하는 것이다. 이 알고리즘은 메모리는 상당히 많이 차지하지만 속도는 매우 빠르다. 이 방법의 단점은 작은 수의 경우는 자신의 배수가 많아 수행 시간이 오래 걸리고 큰 수는 시간이 적게 걸리므로 1/N한다면 각 스레드간의 수행시간이 매우 차이가 나게 될 것이다. 즉 스레드를 사람에 비유하면 N명의 사람이 작업을 1/N 씩 분담하여 처리하면 전체 처리시간을 한 사람이 할 때보다 최대 N배 향상 시킬 수 있다. 여기서 할당된 일의 양이 공평하지 못해 자신에게 할당된 양을 다했다고 놀고 있는 사람이 있다면, N배의 성능향상은 달성될 수 없다. 결국 CPU 혹은 코아의 개수가 많을수록 될 수 있는데로 작업을 골고루 분리하는 것이 성능을 높이는 방법이다.
아래 코드에서는 현재 소수 검사에 사용되고 있는 값을 스레드간에 공유되는 전역변수(global variable) s_curPrime에 저장하고 각각의 스레드는 이 값을 1 증가시켜 그 배수 값들을 제거한다. s_curPrime값이 최대 값인 50000000이 될 때까지 이것을 반복한다. 그러니까 어떠한 스레드도 자신이 해야할 몫을 다했다고 먼저 끝나버리는 일은 없다. 스레드간 공유변수를 Atomic하게 증가시키기 위해 InterlockedIncrement을 사용하였다. [4]
메모리 최적화를 위해 소수가 아닌 짝수는 배열에서 제외하기위해 약간의 트릭이 사용되었는데 이 트릭으로 전역 배열 s_prime의 크기를 절반으로 줄일 수 있었다. 메모리 사용을 줄이기 위해 비트 배열을 사용한 경우도 있으나 여기서는 멀티 스레드 예제를 보여주고자 함이니, 그러한 방법은 사용하지 않았다.
| 스레드간에 공유되는 변수는 적절한 동기화(synchronization) 방법으로 항상 보호되어야만 한다. 그렇지 않으면 하나의 스레드가 공유 변수의 값을 수정하는 동안 다른 스레드가 그 값을 다른 값으로 변경하거나 읽어 사용할 가능성이 있다. |
또, 아래 예제는 스레드 개수에 따른 수행 시간을 알아보기 위해 스레드의 개수를 1에서 20개까지 늘려가며 수행 시간을 출력하도록 하였다.
소수를 구하는 것은 별로 대단치 않은 것으로 보이지만, 구하는 수의 크기가 커질수록 점점 많은 시간과 메모리가 소요된다. 아래 웹싸이트들을 참고하기 바란다
멀티스레드 소수 예제 소스코드 다운로드
static unsigned char s_prime[MAX_PRIME_NUMBER/2 + 1];
static unsigned long volatile s_curPrime = 0;
//----------------------------------------------------------------------------
static DWORD WINAPI ThreadProc(LPVOID lpParameter) {
int threadNo = (int)lpParameter;
SetThreadPriority(GetCurrentThread(), THREAD_PRIORITY_HIGHEST);
const unsigned maxSqrt = sqrt((float)MAX_PRIME_NUMBER);
for (;;) {
unsigned n = InterlockedIncrement((LONG *)&s_curPrime);
if ((n & 1) == 0)
continue;
if (maxSqrt <= n)
break;
if (s_prime[n/2]) {
// eliminate multiples of each prime, starting with its square
for (unsigned i = n * n; i <= MAX_PRIME_NUMBER; i += n) {
if (i & 1)
s_prime[i/2] = false;
}
}
}
return 0;
}
//----------------------------------------------------------------------------
static void RunThreads (int maxThreads) {
HANDLE handles[MAX_NUM_THREADS];
for (int i = 0; i < maxThreads; i++) {
DWORD threadId;
handles[i] = (HANDLE) CreateThread(
(LPSECURITY_ATTRIBUTES) 0,
0, // stack size
ThreadProc,
(LPVOID)i, // argument
0,
&threadId
);
}
// Wait until all threads have terminated.
WaitForMultipleObjects(
maxThreads,
handles,
TRUE,
INFINITE
);
// Close thread handles
for (int i = 0; i < maxThreads; i++)
CloseHandle(handles[i]);
}
//----------------------------------------------------------------------------
static void RunTests () {
for (unsigned i = 1; i <= MAX_NUM_THREADS; i++) {
// Init prime array
s_prime[0] = 0;
for (unsigned j = 1; j < arrsize(s_prime); j++) {
//if (i & 1)
s_prime[j] = 1; // assume all odd numbers are prime at first
//else
// s_prime[i] = 0;
}
// let it start from 3
s_curPrime = 2;
__int64 startCounter = GetPerfCounters();
// Do the job
RunThreads(i);
float totalTime = (GetPerfCounters() - startCounter) / (float)GetPerfFreq();
printf("%3d\t%10.4f\n", i, totalTime);
#ifdef WRITE_RESULT
// Write result
printf("2 ");
for (unsigned n = 1; n < arrsize(s_prime); n++) {
if (s_prime[n])
printf("%d ", n * 2 + 1);
}
printf("\n");
#endif
}
}
인텔 Xeon 1 CPU에서의 수행 결과는 다음과 같다. 스레드의 개수가 늘어나도 수행시간은 줄어들지 않음을 알수 있다.
| 스레드수 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 수행시간 | 0.7722 | 0.7707 | 0.7680 | 0.7562 | 0.7689 | 0.7644 | 0.7698 | 0.7639 | 0.7487 | 0.7058 |
아래 그래프는 4개의 Xeon CPU를 가진 시스템에서의 결과이다. 전체 수행 시간은 예상과 같이 CPU가 늘어가면서 줄어든다. 하지만 그 감소율은 점차로 낮아지며, 전체 CPU 개수와 보다 많은 5개 이상의 스레드가 실행될 경우 더이상의 성능향상은 나타나지 않고 있다. 또, 주목할 점은 스래드가 1에서 4까지 늘어날 경우에도 수행시간이 스레드 개수의 배수인 2배, 3배, 4배로 비례하여 감소하지 않는다는 것인데. 이러한 이유는 위의 알고리즘이 완전히 전체 작업을 싱글스레드 프로그램에 비해 1/N로 감소시키지 못하는 단점을 가지고 있기 때문이다. 즉, 2에 대한 수행을 한 후 4를 할 필요가 없으나 이러한 경우를 처리하지 못하고 있다.
멀티스레드 예제 - Fractal
두 번째 멀티스레드 예제는 만델브롯 셋(Mandelbrot set)[5]을 이용한 프랙탈 생성 프로그램이다. 아래 사용된 만델브롯 셋 알고리즘은 y 좌표축을 따라 스캔라인을 하나씩 처리하며 각각의 스캔라인은 독립적으로 처리될 수 있으므로 병렬수행이 매우 쉽다.
| 당황스러울 정도로 병렬성을 가진 이라는 의미로 영어로 Embarrassingly parallel[6]이라는 말이 있다. 만델브롯 프랙탈은 그러한 예제 중의 하나이다. 당황스럽다라고 유머스럽게 표현한 이유는 병렬성이 아주 좋아 쉽게 병렬 프로그램으로 구현이 가능한 경우가 매우 드물기 때문이다. |
만델브롯의 수학식에 관한 자세한 설명은 위키[7]를 참고하기 바라며, 여기서는 멀티스레드를 이용한 병렬수행에 초점을 맞추도록 하겠다.
멀티스레드 프랙탈 예제 소스코드 다운로드
아래코드에서 s_curScanY 가 공유 변수이며, 각 스레드는 InterlockedIncrement를 사용하여 y값을 atomic하게 증가시킨다. (16번 라인)
각 스레드의 실행 함수인 ThreadProc은 이 Draw함수를 바로 호출한다. 17번 라인에서 InterlockedIncrement한 결과가 최대 y 값을 넘으면 for문을 빠져나오고 스레드의 수행이 종료된다.
다시 말해, 이 프로그램의 핵심은 전역(global) 변수인 s_curScanY을 사용하여 현재 처리해야할 y값을 정하는 것이며, 여러개의 스레드가 동시에 실행될 때 각각의 스레드는 다음 y값을 배정받게 된다. 여기서 InterlockedIncrement는 여러 스레드가 동시에 y값을 얻어내려고 할 때에도 모두 다른 값을 갖도록 보장해준다.
만약 s_curScanY의 초기값이 1이고 unsigned y = s_curScanY++;와 같이 Atomic 함수를 사용하지 않은 경우를 가정해 보자. 이 연산은 s_curScanY가 실제로 차지하는 메모리 영역의 값을 1만큼 증가시키는 단순한 것으로 보이나, CPU와 메모리 사이에서 일어나는 데이터 이동은 그리 단순하지 않다. 즉, 내부적으로 1. 메모리 읽어 오기, 2. 값을 변경하기(1만큼 증가), 3. 다시 메모리에 쓰기. 이렇게 2단계의 작업이 이루어지며 하나의 CPU가 이 작업을 진행하는 동안 다른 CPU가 s_curScanY메모리 값을 읽거나 쓰는 것을 막을 수 없다.
결과적으로, 이 때 스레드 A가 s_curScanY을 읽어 1을 더해 쓰기 직전 스레드 B도 같은 작업을 하고 있다면 s_curScanY는 2가 더해지고 스레드 A, B모두 y는 2가 되어 중복된 작업을 수행할 뿐만아니라 y=1인 경우는 실행되지도 못한다. 이러한 문제는 멀티코어가 아닌 일반 싱글프로세서에서도 나타날 가능성이 있다. 다만, 그 확률이 매우 낮을 뿐이다.
또, 어셈블리 레벨에서는 각각의 연산들은 Atomic할 것이라 생각하는 것 역시 잘못된 것이다. 아래 어셈블리는 "ADD" 연산을 수행하고 있으며, 이 연산을 수행 중 다른 CPU가 s_curScanY값을 변경하는 것을 막지 못한다. 멀티프로세서 시스템에서 스레드간 공유변수에 Atomic 연산을 쓰지 않으면, 결과는 확실히 예측할 수 없다.[8]
ADD s_curScanY, 1
1 //---------------------------------------------------------------------------
2 static void Draw (
3 unsigned width,
4 unsigned height,
5 unsigned char * buffer
6 ) {
7 const double MinRe = -2.0;
8 const double MaxRe = 1.0;
9 const double MinIm = -1.2;
10 const double MaxIm = MinIm + (MaxRe - MinRe) * height/width;
11 const double Re_factor = (MaxRe - MinRe)/(width - 1);
12 const double Im_factor = (MaxIm - MinIm)/(height - 1);
13 const unsigned MAX_ITERATIONS = 1024;
14
15 for (;;) {
16 unsigned y = InterlockedIncrement((LONG *)&s_curScanY);
17 if (height <= y)
18 break;
19 double c_im = MaxIm - y * Im_factor;
20 for (unsigned x = 0; x < width; x++)
21 {
22 double c_re = MinRe + x * Re_factor;
23 double Z_re = c_re, Z_im = c_im;
24 bool isInside = true;
25 unsigned n = 0;
26
27 for (; n < MAX_ITERATIONS; n++) {
28 double Z_re2 = Z_re * Z_re, Z_im2 = Z_im * Z_im;
29 if (Z_re2 + Z_im2 > 4) {
30 isInside = false;
31 break;
32 }
33 Z_im = 2 * Z_re * Z_im + c_im;
34 Z_re = Z_re2 - Z_im2 + c_re;
35 }
36
37 if (!isInside && n != 0) {
38 // coloring the outside pixels
39 unsigned char r, g, b;
40 if (n < 16) {
41 r = n * 16;
42 g = 0;
43 b = 0;
44 }
45 else if (n < 32) {
46 n -= 16;
47 r = 255;
48 g = 128 + n * 8;
49 b = 128 + n * 8;
50 }
51 else if (n < 128) {
52 n -= 128;
53 r = 255;
54 g = 220;
55 b = n * 2;
56 }
57 else {
58 r = min(n, (unsigned) 255);
59 g = min(n, (unsigned) 255);
60 b = min(n, (unsigned) 255);
61 }
62
63 unsigned char * ptr = buffer + y * width * IMAGE_STRIDE + x * IMAGE_STRIDE;
64 *ptr++ = b;
65 *ptr++ = g;
66 *ptr++ = r;
67 }
68 }
69 }
70 }
CreateMandelbrotBmpFile함수는 main 함수로 부터 바로 호출되며, RunThreads에서 threads 파라미터 개수 만큼의 스레드를 생성하여 프랙탈의 각 픽셀의 값을 rgbValues에 넣은 후 이것을 이미지 파일 포맷 중의 하나인 PNG 포맷으로 저장한다. 여기서 이미지 파일 저장을 간편하게 하기 위해 VC 8.0에서 제공되는 C++/CLI를 이용 .NET 함수를 직접 호출하는 방법을 사용하였다. 이러한 방법을 사용한 이유는 C++에서 이미지 파일을 일정 포맷으로 저장하려면 상당한 코딩이 필요하기 때문에 .NET의 클래스 라이브러리에 있는 이미지 관련 함수를 사용한 것이며 굳이 이러한 방법을 꼭 써야한다는 것은 아니다.
1 //---------------------------------------------------------------------------
2 static void CreateMandelbrotBmpFile (
3 unsigned width,
4 unsigned height,
5 unsigned threads
6 ) {
7 // Declare an array to hold the bytes of the bitmap.
8 array <Byte>^ rgbValues = gcnew array<Byte>(width * height * IMAGE_STRIDE);
9 pin_ptr<Byte> pRgbValues = &rgbValues[0];
10
11 __int64 startCounter = GetPerfCounters();
12
13 RunThreads(threads, width, height, pRgbValues);
14
15 float totalTime = (GetPerfCounters() - startCounter) / (float)GetPerfFreq();
16 System::Console::WriteLine("{0}\t{1}", threads, totalTime);
17
18 // pin no longer needed
19 pRgbValues = nullptr;
20
21 // create bmp file
22 Bitmap^ myBitmap = gcnew Bitmap(
23 width, height,
24 Imaging::PixelFormat::Format24bppRgb
25 );
26
27 // Lock the bitmap's bits.
28 System::Drawing::Rectangle rect = System::Drawing::Rectangle(
29 0, 0, myBitmap->Width, myBitmap->Height
30 );
31 System::Drawing::Imaging::BitmapData^ bmpData = myBitmap->LockBits(
32 rect,
33 System::Drawing::Imaging::ImageLockMode::ReadWrite,
34 myBitmap->PixelFormat
35 );
36
37 // Get the address of the first line.
38 IntPtr ptr = bmpData->Scan0;
39
40 // Copy the RGB values back to the bitmap
41 System::Runtime::InteropServices::Marshal::Copy(rgbValues, 0, ptr, rgbValues->Length);
42
43 // Unlock the bits.
44 myBitmap->UnlockBits(bmpData);
45
46 myBitmap->Save("mandelbrot.png", Imaging::ImageFormat::Png);
47 }
48
49 //---------------------------------------------------------------------------
50 int main(array<System::String ^> ^args)
51 {
52 if (args->Length < 3) {
53 System::Console::WriteLine("Usage: Mandelbrot [width] [height] [threads]");
54 return 1;
55 }
56
57 int width = System::Int32::Parse(args[0]);
58 int height = System::Int32::Parse(args[1]);
59 int threads = System::Int32::Parse(args[2]);
60
61 if (width == 0 || MAX_WIDTH < width ||
62 height == 0 || MAX_HEIGHT < height ) {
63 System::Console::WriteLine("Wrong width or height value");
64 return 1;
65 }
66
67 if (threads == 0 || MAX_THREADS < threads) {
68 System::Console::WriteLine("threads must be non zero and less than {0}", MAX_THREADS);
69 return 1;
70 }
71
72 CreateMandelbrotBmpFile(
73 width,
74 height,
75 threads
76 );
77 return 0;
78 }
결과
다음은 만델브롯 예제의 실행 결과 그래프이다. 하이퍼스레드를 지원하는 CPU일 경우 CPU 개수 * 2 만큼의 논리적 CPU가 존재하여 4 CPU의 경우는 8개 스레드까지 성능향상을 보였고, 1 CPU에서도 2개의 스레드 까지 성능향상을 보인다. 물론, 스레드 수가 증가함에 따라 하이퍼스레드는 물리적인 CPU나 코어보다는 낮은 성능 향상을 보인다.
만델브롯의 우수한 병렬성 덕분에 스레드 개수가 늘어날 때마다 성능향상의 폭은 거의 스레드 개수에 비례하여 늘어나고 있다. 하지만, 물리적인 코어나 CPU 개수 이상의 스레드는 별다는 성능향상을 보이지 않음을 알 수 있다.
이것은 가장 이상적인 스레드 개수는 하나의 CPU당 하나임을 암시한다. 하지만, 스레드가 대부분 어떠한 이벤트를 기다리는데 시간을 소요한다면(대부분의 I/O 스레드), 이러한 스레드들은 CPU 시간을 많이 사용하지 않으므로 CPU 개수보다 많아도 별 문제가 되지 않는다. 앞의 예제에서는 RunThreads 함수가 작업 스레드들을 생성한 뒤 모든 스레드가 종료할 때까지 WaitForMultipleObjects API를 이용하여 기다리고 있으며 전체 성능에 거의 영향을 끼치지 않는다.
아래 그래프에서 X축은 스레드 개수이며, Y축은 총 프로그램 수행시간(초) 이다.
참고 문서와 각주
- ↑ 정해진 시간 내에 어떤 작업이 완료되는 것을 보장하는 운영체제를 실시간 운영체제(Real-time OS)라고 한다. 윈도우즈는 이러한 실시간 운영체제가 아니다.
- ↑ wp:Prime Number
- ↑ wp:Prime Number
- ↑ wp:Atomic operation이란 그 연산을 방해하는 다른 연산이 일어날 수 없는 것을 의미한다. CPU와 Lock-free알고리즘에서 다시 자세하게 다루어 질 것 이다.
- ↑ wp:Mandelbrot Set
- ↑ wp:Embarrassingly parallel
- ↑ wp:Mandelbrot Set
- ↑ Atomic_Operations 참고.
