Egloos | Log-in
F/OSS study
F/OSS study
Dekker's Algorithm (2)
이전 글 보기:


앞서 글에서 밝힌 대로 이번에는 컴파일러의 최적화에 의해 이전의 예제 프로그램이 어떠한 영향을 받는지 살펴볼 것이다.

우선 앞의 글에서 작성한 예제 프로그램을 최적화 옵션을 켠 후에 다시 컴파일 해 보자.

$ gcc -O2 -o dekker-opt main.c dekker.c -pthread
$
$ ./dekker-opt
^C

실행시켜보면 십중팔구 무한루프에 빠지게 될 것이다.
무한루프에 빠지는 부분은 (당연하게도) busy-wait를 수행하는 lock 루틴에서 발생한다.
다시 dekker_lock() 함수의 구현을 살펴보자.

void dekker_lock(struct dekker *d, int thid)
{
    d->flag[thid] = 1;
    barrier();

    while (d->flag[!thid]) {
        d->flag[thid] = 0;

        while (d->turn != thid)
            (void) 0; /* do nothing */

        d->flag[thid] = 1;
        barrier();
    }
}

여기에는 2개의 while loop가 존재하며 이 두 loop가 모두 무한히 실행될 가능성이 있다.
각 loop에서 검사하는 조건은 상대방의 flag 값과 turn 값인데
이 두 값은 모두 현재 실행되는 함수 내에서 변경되지 않으며 다른 스레드가 변경해 주어야 하는 것이다.

컴파일러의 최적화 옵션이 켜지지 않았다면 gcc는 우리가 프로그램을 작성한대로 각 변수의 값을 메모리에서 읽어올 것이다.
하지만 최적화를 수행하게 되면 컴파일러는 loop 내에서 불필요하게! 반복되는 연산을 loop 밖으로 꺼내어
loop 내부의 실행 속도를 향상시키려고 한다. (이를 LICM: Loop Invariant Code Motion 이라고 한다)
따라서 d->flag[!thid] 값과 d->turn != thid 의 결과는 loop 내에서 변경되지 않으므로
매번 메모리에서 읽어오지 않고 최초에 한 번만 읽은/계산한 후 임의의 레지스터 내에 저장해 둔 뒤 사용하므로
항상 같은 결과를 낼 것이며 따라서 무한루프에 빠지게 되는 것이다.

이를 해결하는 방법은 각 변수를 volatile로 선언하는 것이다.
C 언어의 volatile은 바로 이러한 경우를 위해 존재하는 것으로 자신이 해당 변수의 값을 변경하지 않아도
다른 존재 (스레드 혹은 인터럽트 등)로 인해 값이 변경될 수 있으므로 항상 확인해야 한다는 것을 알려주며
이로 인해 컴파일러가 수행할 수 있는 최적화에 많은 제약을 받게 된다.
(마찬가지로 diff -u 형식이다. -로 표시된 줄을 +로 표시된 줄로 바꾸면 된다.)

 struct dekker {
-    char flag[2];
-    int turn;
+    volatile char flag[2];
+    volatile int turn;
 };

또 한 가지 발생할 수 있는 최적화로 인한 문제는 lock/unlock이 inline되는 경우에 생겨나는데
앞의 예제에서는 main.c 파일과 dekker.c 파일로 나누어서 프로그램을 구현했으므로
thread_routine 내에서 lock/unlock의 구현을 볼 수 없고 따라서 inline이 불가능했다.
하지만 dekker.c 파일을 main.c 파일로 포함시켜서 함수를 static으로 선언한다면
컴파일러가 자유롭게 이를 inline 시켜 버릴 수도 있다.

그 경우 thread_routine은 lock/unlock의 구현을 모두 볼 수 있게 되며
DFA 결과 lock/unlock 내에서 result_sum 변수의 값을 변경하지 않는다는 것을 확신할 수 있으므로
마찬가지로 LICM에 의해 result_sum의 계산이 loop 밖으로 옮겨질 수 있다.

이러한 결과는 소스 코드를 직접 수정하는 대신
gcc에서 다음과 같이 컴파일을 수행해도 동일한 효과를 얻을 수 있다.

$ gcc -O2 -o dekker-inline -fwhole-program main.c --combine dekker.c -pthread
$
$ ./dekker-inline
result = 1000000

-fwhole-program은 주어진 파일 (정확히는 translation unit - 여기서는 main.c 및 #include된 파일들) 내의
공개된 심볼들을 (main 함수는 제외) 모두 static으로 선언된 것처럼 만들어 주며
--combine 옵션은 dekker.c 파일을 main.c 파일로 합쳐 준다.
이렇게 컴파일 된 후의 thread_routine() 함수는 마치 다음과 같은 함수처럼 동작할 것이다.

static void thread_routine(void *arg)
{
    int i;
    int thid = *(int *) arg;
    unsigned long tmp;

    tmp = result_sum;
    for (i = 0; i < 1000000; i++) {
        /* inline된 dekker_lock() */
        dlock.flag[thid] = 1;
        barrier();

        while (dlock.flag[!thid]) {
            dlock.flag[thid] = 0;
            while (dlock.turn != thid)
                (void) 0;
            dlock.flag[thid] = 1;
            barrier();
        }

        /* inline된 dekker_unlock() */
        dlock.flag[thid] = 0;
        dlock.turn = !thid;
    }
    /* loop invariant code motion */
    result_sum = tmp + 1000000;
    return NULL;
}

이 경우 각 스레드는 result_sum의 초기값 (0)을 읽은 후 loop가 끝날 때 값을 갱신하므로
두 스레드 모두 같은 값을 읽고 쓰게 되며 따라서 위와 같이 잘못된 결과가 나오게 된다.
이를 해결하는 방법도 마찬가지로 volatile 키워드를 이용하는 것이다.

-static unsigned long result_sum;
+static volatile unsigned long result_sum;

이제는 위와 같이 컴파일 하는 경우도 LICM 없이 loop 내에서 result_sum을 매번 계산할 것이므로
아래와 같이 정상적인 결과를 보여준다.

$ gcc -O2 -o dekker-inline -fwhole-program main.c --combine dekker.c -pthread
$
$ ./dekker-inline
result = 2000000

마지막으로 살펴볼 문제는 컴파일러 최적화라기 보다는 OS에 의한 스케줄링으로 인한 문제로 보이며
사실 다음 글에서 살펴볼 Dekker의 알고리즘을 3개의 이상의 스레드로 확장시키는 과정에서 발견한 것이다.
이는 알고리즘 자체의 문제가 아닌 초기에 thid를 넘기는 과정에서 생길 수 있는 race로 인한 문제이다.

앞의 main() 함수에서 pthread_create()를 통해 스레드를 새로 생성할 때
thid 값을 전달하기 위해 인덱스로 사용한 지역 변수 i의 값을 전달하는데
pthread_create() 함수의 인자는 void * 타입이므로 불필요한 cast를 없애기 위해
i의 주소를 전달하고 thread_routine() 내에서 이를 역참조하여 thid를 얻는 방식으로 구현하였다.

하지만 (내 경우는 주로 스레드 수가 시스템 내의 CPU 수 보다 많아진 경우) 서로 다른 스레드가
동일한 thid를 얻게되는 경우가 생기게 되어 최종 결과가 비정상적으로 나오는 경우가 있었다.
이는 main thread에서 i의 값을 증가시키는 시점과 생성된 스레드가 i 값을 참조하는 시점이
미묘하게 얽히면서 발생되는 문제이다.

예를 들어 main thread가 loop를 통해 pthread_create() 함수를 두 번 호출하는데
각 호출 시 지역 변수 i의 값은 각각 0과 1이다.
하지만 인자로는 이 값 (0 혹은 1)이 아닌 i의 주소가 전달되므로 스레드가 생성되어
thread_routine() 함수가 실행되어야 i의 주소를 통해 실제 값을 읽을 수 있는데
만약 i 값이 증가되기 전에 해당 스레드가 실행되지 못했다면 thid 값으로 1 혹은 2를 얻게될 수도 있다.
(실제 테스트 결과 대부분은 다음의 pthread_join() 루프로 인해 thid 0을 가지게 되었다.)

이를 해결하기 위해서는 포인터를 이용하여 역참조를 통해 thid 값을 전달하는 대신
값 자체를 (포인터로 cast하여) 인자로 넘기는 것이다.
하지만 x86_64에서 int를 바로 포인터 타입으로 변경하면 컴파일러가 경고를 보여주므로
다음과 같이 long 타입을 이용하여 이를 방지하도록 하였다.
(코드 수정을 최소화 하기 위해 lock/unlock 함수에 전달되는 thid 인자의 타입은 그대로 int로 남겨두었다.)

 static void *thread_routine(void *arg)
 {
     int i;
-    int thid = *(int *) arg;
+    int thid = (long) arg;

 ...

 int main(void)
 {
-    int i;
+    long i;
     pthread_t pth[NR_THREAD];

     for (i = 0; i < NR_THREAD; i++) {
-         pthread_create(&pth[i], NULL, thread_routine, &i);
+         pthread_create(&pth[i], NULL, thread_routine, (void *) i);

이제 thread_routine()은 (언제 바뀔지 모르는) main thread의 i 값을 읽어보는 대신
스레드 생성 시점에 자신에게 할당된 (유일한) 정수값을 직접 인자로 받으므로 위에서 말한 race는 더 이상 발생하지 않는다.

다음 글에서는 언급한대로 Dekker의 알고리즘을 3개 이상의 스레드에도 적용시키는 방법을 살펴볼 것이다.

by namhyung | 2010/12/22 16:33 | General | 트랙백(1) | 덧글(0)
트랙백 주소 : http://studyfoss.egloos.com/tb/5455023
☞ 내 이글루에 이 글과 관련된 글 쓰기 (트랙백 보내기) [도움말]
Tracked from F/OSS study at 2010/12/22 21:58

제목 : Dekker's Algorithm (3)
이전 글 보기: Dekker's Algorithm (1)Dekker's Algorithm (2) 마지막으로 Dekker의 알고리즘을 3개 이상의 멀티 스레드 환경에서도 적용가능하도록 일반화시킨 알고리즘을 살펴보기로 한다. 여기서 살펴볼 알고리즘은 Alain J. Martin이 1985년 논문 (아래 참고)에서 제시한 것을 구현한 것이다. Dekker의 알고리즘을 좀 더 일반적으로 생각해 보면 다음과 같은 단계로 나눌 수 있을 것이......more

:         :

:

비공개 덧글

◀ 이전 페이지 다음 페이지 ▶

카테고리
General
Application
System
Kernel
Book
Tips
태그
sed gcc SMP C build linux blktrace block-layer awk synchronization x86 binutils bash CAaQA3 CARM algorithm computer-architecture emacs perf glibc scm kernel compiler script patch documentation vcs git elf memory
전체보기
이글루 파인더

최근 등록된 덧글
informsi yang bagus dan be..
by pordanaia at 08/05
Informsi yang bagus dan b..
by jamalsu at 08/01
as inforasi yang menarik http..
by jamalsu at 07/22
최근 등록된 트랙백
Tod's Ferrari Homme
by Tods Pas Cher,Kodak did ..
Mocassin Femme
by Mocassins Homme, I got so..
natural garcinia cambogia
by
rss

skin by jiinny


X