Egloos | Log-in
F/OSS study
F/OSS study
Dekker's Algorithm (1)
이 알고리즘은 Theodorus J. Dekker가 병렬 프로그래밍 시의 동기화 문제를 해결하기 위해 만든 것으로
하드웨어 수준에서 제공하는 atomic operation 없이 (공유) 메모리 연산만을 이용하여 spin lock을 구현한 것이다.

기본적인 알고리즘은 다음과 같이 2개의 CPU에서 동시에 스레드가 수행되는 상황 만을 고려한다.
아래의 예제에서 실행되는 각각의 스레드는 자신에게 할당된 번호 (0 혹은 1)을 thid 인자로 받는다고 가정한다.
먼저 다음과 같은 자료 구조 및 함수 원형을 정의하도록 하자.

/* dekker.h */

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

void dekker_lock(struct dekker *, int);
void dekker_unlock(struct dekker *, int);

flag 필드는 각각의 스레드 별로 할당된 변수로 해당 스레드가 현재 lock에 접근하려는 중인지를 나타낸다.
turn 필드는 lock에 대한 경쟁이 발생하였을 때 먼저 실행할 스레드의 번호를 지정하는 변수이다.

먼저 경쟁이 없는 상황이라면 예를 들어 0번 스레드가 lock을 얻으려고 할 때 1번 스레드는 다른 작업 중이므로
0번 스레드가 안전하게 lock을 얻을 수 있을 것이며, 이는 flag[0] = 1이고 flag[1] = 0인 상황으로 표현할 수 있다.
경쟁이 있다면 flag[0] = 1이고 flag[1] = 1인 상황일 것이며 이 때에는 flag[turn]에 해당하는 스레드가
lock을 얻도록 하고 싶은 것이다. 이를 코드로 작성하면 다음과 같다.
(참고로 thid는 0과 1 뿐이므로 상대방의 thid를 알아내려면 단순히 자신의 thid 값을 반전(! 연산자)시키면 된다.)

/* dekker.c */

#include "dekker.h"

void dekker_lock(struct dekker *d, int thid)
{
    /* 먼저 자신이 lock에 접근 중임을 표시 */
    d->flag[thid] = 1;

    /* 만약 다른 스레드도 동시에 lock에 접근 중이라면 */
    while (d->flag[!thid]) {
        /* lock에 대한 접근을 일시적으로 중지 */
        d->flag[thid] = 0;

        /* 자신이 실행할 순서가 아니라면 대기 (spin) */
        while (d->turn != thid)
            (void) 0;

        /* 다시 자신이 lock에 접근 중임을 표시 */
        d->flag[thid] = 1;
    }

    /* lock을 얻었음! */
}

void dekker_unlock(struct dekker *d, int thid)
{
    /* 자신이 lock을 접근하지 않음을 표시 */
    d->flag[thid] = 0;

    /* 경쟁 스레드가 lock을 얻을 수 있도록 배려 */
    d->turn = !thid;
}

lock 알고리즘을 보면 먼저 자신의 flag를 1로 설정한 후에 상대방 (경쟁 스레드)의 flag를 살펴본다.
이 때 상대방의 flag가 0이면 바로 안전하게 lock을 얻을 수 있는 경우이다.
하지만 상대방의 flag도 1이라면 turn을 검사하여 자신의 차례인지 아닌지에 따라 busy wait를 수행한다.
자신의 차례가 아니었다면 상대방이 unlock을 수행하는 순간 자신의 차례가 되므로 다시 lock에 접근한다.

이 때 바깥쪽 loop의 마지막에서 단순히 자신의 flag를 1로 설정한 후에 lock을 얻었다고 착각할 수도 있지만
안쪽의 while 문을 빠져나온 직후 자신의 flag를 설정하기 전에 interrupt 혹은 scheduling이 발생했고
그 사이에 다시 상대방이 lock에 접근하는 경우가 발생할 수 있으므로
(이 경우 상대방은 내 flag가 아직 0이므로 turn 값에 상관없이 lock을 얻게 된다.)
반드시 바깥쪽 while loop에서부터 다시 lock을 얻는 과정을 반복해야 한다.

자 이제 lock/unlock 함수가 준비되었으니 다음과 같이 테스트를 위한 예제를 만들어 보자.
(아래에는 빠져있지만 사실 위에서 정의한 자료 구조와 함수도 적절히 포함시켜야 한다.)

/* main.c */

#include <stdio.h>
#include <pthread.h>

#define NR_THREAD  2

#include "dekker.h"

static struct dekker dlock;
static unsigned long result_sum;

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

    for (i = 0; i < 1000000; i++) {
        dekker_lock(&dlock, thid);
        result_sum++;
        dekker_unlock(&dlock, thid);
    }
    return NULL;
}

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

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

    for (i = 0; i < NR_THREAD; i++)
        pthread_join(pth[i], NULL);

    printf("result = %lu\n", result_sum);
    return 0;
}

이제 아래와 같이 컴파일한 후 결과를 살펴보자.
(참고로 테스트한 환경은 64비트 우분투 리눅스 + gcc이다.)

$ gcc -o dekker main.c dekker.c -pthread
$
$ ./dekker
result = 1904549

기대와는 달리 lock이 정상적으로 동작하지 않았음을 볼 수 있다.
이는 Dekker의 알고리즘이 sequencial memory model을 기반으로 하고 있기 때문이다.
즉, 프로그램 내의 메모리 연산들이 항상 (프로그램 상의) 순서대로 실행되는 환경에서만 제대로 동작하는데
x86을 포함한 최근의 CPU들은 성능 향상을 위해 instruction reordering을 수행하기 때문에
이러한 (비정상적인) 결과를 얻게 된 것이다.

이를 좀 더 자세히 살펴보면 다음과 같다.
경쟁이 발생하는 경우 각 스레드는 (다른 CPU 상에서) 동시에 dekker_lock() 함수를 수행할 것이다.
이 때 각 스레드에서 실행하는 처음 두 연산은 다음과 같다.
(설명을 간단히 하기 위해 여기서 cache의 존재에 대해서는 고려하지 않기로 한다.)

  thread 0                     thread 1                      time
  --------                     --------                      ----
  op1: write d->flag[0]        op2: write d->flag[1]         t0
  op3: read  d->flag[1]        op4: read  d->flag[0]         t1

sequential memory model에서는 각 스레드는 프로그램 상의 순서에 따라 연산을 수행하므로
t0 시간에 각 CPU는 동시에 메모리 쓰기 연산을 실행하려고 하지만
실제로 메모리에는 한 순간에 오직 하나의 접근 만이 가능하므로 op1 혹은 op2 중의 하나 만이 수행될 것이다.

더욱이 sequential memory model은 오직 동일한 CPU 내의 연산 순서만 관여하며
즉 op1이 op3보다 먼저, 그리고 op2가 op4보다 먼저 수행된다는 것만 보장하기 때문에
실제로는 어떤 순서로 메모리 접근이 일어나게 될 지 전혀 알 수 없다.
가능한 몇 가지 예로는 다음과 같은 순서가 있을 것이다.
  1. op1 ---> op2 ---> op3 ---> op4
  2. op1 ---> op3 ---> op2 ---> op4
  3. op2 ---> op1 ---> op3 ---> op4
  4. op2 ---> op4 ---> op1 ---> op3
1번과 3번의 경우 t1에서 각각 상대방의 flag를 읽을 때
이미 모든 값이 다 1로 써진 후이므로 thread 0와 thread 1은 모두 경쟁 상태임을 인식하게 된다.
2번과 4번의 경우에는 각각 thread 0와 thread 1이 경쟁이 없는 것처럼 바로 lock을 얻게 되는데
여기서 중요한 것은 늦게 실행된 (즉 lock을 못 얻은) thread들은 자신의 경쟁 상태 임을 반드시!
인식하게 된다는 것이다. 다시 말해서 2번의 경우 op4를 실행할 때 thread 1은 반드시
flag[0]이 1임을 볼 (read) 수 있다는 것이 보장된다는 사실이다.

하지만 CPU 내에서 instruction reordering이 적용된다면 이는 더 이상 보장되지 않는다.
(이러한 타입의 시스템은 weakly ordered 혹은 relaxed memory model이라고도 부른다.)
즉 다음과 같은 순서로도 메모리 연산이 수행될 수 있다.
  •   op3 ---> op2 ---> op4 ---> op1
즉 op1의 write보다 op3의 read가 먼저 수행되는 경우
thread 0은 아직 op2가 실행되기 전이므로 경쟁이 없는 것처럼 lock을 얻을 것이고
thread 1에서도 op4가 op1보다 먼저 실행되므로 마찬가지로 동시에 lock을 얻을 수 있게 된다.
결과적으로 lock이 제 기능을 수행하지 못하는 상황이 된다.

이러한 문제를 해결하기 위해서는 (중요한) 메모리 연산의 순서를 보장할 수 있어야 한다.
(weakly ordered memory model의 다른 CPU들처럼) x86에서도 이를 위해 특정한 명령어를 제공하며
mfence, lfence, sfence라는 어셈블리 명령어를 통해 이를 사용할 수 있다.

위의 경우 자신의 flag를 1로 설정하는 연산은 경쟁 상태 임을 알리기 위해 매우 중요하므로
다른 연산으로 인해 미뤄지면 안되기 때문에 바로 여기에 이러한 memory barrier 명령어가 이용되어야 한다.
반면에 while loop에서나 unlock에서 flag를 0으로 쓰는 것은 조금 미뤄져도 크게 상관없으므로
dekker_lock() 함수 만을 다음과 같이 수정하면 원하는 결과를 얻을 수 있다.
(주석을 생략하고 diff -u의 출력과 비슷한 형식으로 나타내 보았다.
제일 앞에 +로 표시된 줄이 추가된 부분이다.)

+#define barrier()     asm ("mfence")
+
 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();
     }
 }

이제 다시 컴파일 후 실행해보면 원하는 결과가 나오는 것을 확인할 수 있다.

$ gcc -o dekker main.c dekker.c -pthread
$
$ ./dekker
result = 2000000

barrier를 정의하는 방식은 위에서처럼 직접 asm 명령어를 넣어줄 수도 있지만
gcc에서 제공하는 __builtin_ia32_mfence() 내장 함수를 이용하거나
icc와 호환되는 _mm_mfence() intrinsic을 이용할 수 있는데
이 때에는 빌드 시에 -msse2 옵션을 gcc에게 추가로 넘겨주어야하며
intrinsic을 이용하는 경우 <emmintrin.h> 헤더 파일도 추가로 #include 해 주어야 한다.

몇 번의 실험 결과 mfence 대신 sfence 명령어를 사용해도 정상적인 결과가 출력됨을 확인하였는데
아직 이에 대한 정확한 해석을 내리지 못한 상태이다.
(이에 대해 명쾌한 해답을 제시해 줄 수 있는 분이 계시면 답글로 남겨주시면 감사하겠습니다.. ^^)

지금까지 weakly ordered memory model에서의 Dekker's Algorithm에서 살펴보았지만
컴파일러 자체에서 벌어지는 최적화에 대해서는 간과하고 있었다.
사실 위의 예제 프로그램을 -O2 옵션을 주어 컴파일하게 되면 정상적인 결과는 커녕 무한 루프에 빠지고 만다.
이에 대해서는 다음 글에서 살펴보기로 하자.

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

제목 : Dekker's Algorithm (2)
이전 글 보기: Dekker's Algorithm (1) 앞서 글에서 밝힌 대로 이번에는 컴파일러의 최적화에 의해 이전의 예제 프로그램이 어떠한 영향을 받는지 살펴볼 것이다. 우선 앞의 글에서 작성한 예제 프로그램을 최적화 옵션을 켠 후에 다시 컴파일 해 보자. $ gcc -O2 -o dekker-opt main.c dekker.c -pthread $ $ ./dekker-opt ^C 실행시켜보면 십중팔구 무한루프에 빠지......more

Commented by 김민장 at 2010/12/22 06:47
흠, 제 컴퓨터에서는 mfence를 아무리 모든 메모리 연산 뒤에 다 넣어도, volatile을 넣어도 2000000이 나오지를 않네요. 헐.. 테스트 머신은 그냥 Core2Duo 듀얼 코어. 이 알고리즘은 배운지 하도 오래되어서 기억에 가물가물;; 소스는 그대로 카피했어요.

https://www.dropbox.com/s/k50c52t42hu4wf4/x86_memory_ordering.pdf

참고로 x86의 메모리 모델은 TLO+CC로 알려져있는데(total lock ordering + causal consistency), 위 문서가 잘 정리하고 있습니다. 지금은 저 문서가 인텔 ISA 매뉴얼에 포함되어있습니다.
Commented by namhyung at 2010/12/22 17:23
답글 남겨주셔서 감사합니다.. ^^

혹시나 두 번째 글에서 언급한 다른 문제로 인한 것이 아닌지 생각되네요..
만약 그 문제도 아니라면 정확한 테스트 환경 및 결과를 다시 알려주시면 시간되는대로 검토해 보도록 하겠습니다.

링크 걸어주신 문서도 감사히 잘 보았습니다. 말씀하신 대로 간략하게 잘 정리되어 있네요..
2.3 절에서 언급한 상황이 여기에 해당되는 것인데 궁금한 것은 older store와 younger load 사이에 sfence가 들어간 경우에도
reordering이 금지되는 것 같은 결과를 얻었다는 것입니다.
물론 test set size가 매우 작으니 오차일 수도 있겠지만.. 어느 정도 영향을 주는 것 같은데 확신을 할 수가 없네요..

:         :

:

비공개 덧글

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

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

최근 등록된 덧글
http://serbaserbiinfoterkini56..
by cakra at 09/22
informsi yang bagus dan b..
by cakra at 09/16
informsi yang bagus dan be..
by pordanaia at 08/05
최근 등록된 트랙백
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