Synchronization

youngwiki
Pinkgo (토론 | 기여)님의 2025년 5월 28일 (수) 03:44 판 (→Semaphore)

상위 문서: Concurrent Programming

개요

해당 문서에서는... 추후 추가

Shared Variables in Threaded Programs

쓰레드의 장점 중 하나는 여러 쓰레드가 동일한 프로그램 변수를 쉽게 공유할 수 있다는 것이다. 이때 보통 단순히 “전역 변수는 공유되고, 스택 변수는 독립적이다”라고 말하지만, 현실은 그렇게 단순하지 않다. 먼저, 어떤 변수 x가 공유(shared)된다는 것은, 둘 이상의 쓰레드가 해당 변수의 인스턴스[1]를 참조한다는 뜻이다. 이때 어떤 C 프로그램 변수의 공유 여부를 이해하기 위해 다음과 같은 기본적인 질문들을 검토해야 한다:

  1. 쓰레드의 메모리 모델은 무엇인가?
  2. 해당 모델에 대해, 변수 인스터스는 메모리에 어떻게 매핑되는가?
  3. 이러한 인스턴스를 참조하는 쓰레드는 몇 개인가?

그리고 이에 대해 구체적으로 논의하기 위해서 아래와 같은 코드를 예제로서 사용한다: 

#include "csapp.h"
#define N 2
void *thread(void *vargp);
char **ptr;  //전역 변수, 메인 쓰레드 내의 msg 배열에 접근할 수 있도록 설정됨

int main() {
    int i;
    pthread_t tid;
    char *msgs[N] = {"Hello from foo", "Hello from bar"}; //문자열 배열 선언

    ptr = msgs;
    for (i = 0; i < N; i++) //N(2) 개의 쓰레드를 만든다.
        Pthread_create(&tid, NULL, thread, (void *)i); //i를 포인터로 캐스팅하여 인자로 전달
    Pthread_exit(NULL);
}

void *thread(void *vargp) {
    int myid = (int)vargp; //쓰레드에 전달된 인자를 받음
    static int cnt = 0;    //여러번 실행되도 한 번만 초기화됨
    printf("[%d]: %s (cnt=%d)\n", myid, ptr[myid], ++cnt); //id에 따라 문자열 배열 출력, 총 쓰레드 실행 횟수 출력
    return NULL;
}

위 예제 프로그램은 하나의 메인 쓰레드가 두 개의 피어 쓰레드를 생성하는 구조이다. 메인 쓰레드는 각각의 동료 쓰레드에게 고유한 ID를 전달하며, 동료 쓰레드는 이 ID를 사용해 그에 대응되는 메시지와 함께 쓰레드 루틴이 호출된 총 횟수를 출력한다.

Threads Memory Model

동시에 실행되는 쓰레드 모음(pool)은 하나의 프로세스 컨텍스트(context)에서 실행된다. 각 쓰레드는 고유한 쓰레드 컨텍스트를 가지며, 이에는 TID, 스택, 스택 포인터, 프로그램 카운터, 조건 코드(Condition codes), 범용 레지스터(general-purpose register) 값들이 포함된다. 그리고 각 쓰레드는 다른 쓰레드들과 나머지 프로세스 컨텍스트를 공유한다. 공유되는 컨텍스트에는 Code/Data/Heap 메모리 공간, 공유 라이브러리, 열린 파일 디스크립터 등을 포함하는 전체 가상 주소 공간(virtual address space)이 포함된다.

이러한 관점에서 볼 때, 쓰레드는 다른 쓰레드의 레지스터 값을 읽거나 쓸 수는 없다. 하지만 어떤 쓰레드든 공유되어 있는 가상 메모리(virtual memory)의 위치에는 접근할 수 있으며, 만약 한 쓰레드가 해당 메모리 주소를 수정하면, 다른 모든 쓰레드는 해당 주소를 읽을 경우 변경 사항을 읽게 된다. 따라서 레지스터는 절대 공유되지 않지만, 가상 메모리는 항상 공유된다.

개별 쓰레드 스택에 대한 메모리 모델은 명확하지 않다. 이러한 스택은 가상 주소 공간의 스택 영역에 존재하며, "일반적으로" 각 쓰레드가 자신의 스택에만 접근한다. "일반적으로"라고 표현한 이유는 각각의 쓰레드 스택들이 다른 쓰레드들로부터 보호되지 않기 때문이다. 따라서 어떤 쓰레드가 다른 쓰레드의 스택에 대한 포인터를 얻는다면, 그 스택의 어느 부분이든 읽거나 쓸 수 있다. 예제 코드에서도 전역 변수 ptr을 통해 피어 쓰레드가 메인 쓰레드의 스택에 저장된 msg 문자열 배열을 참조하는 것이 나와 있다.

Mapping Variables to Memory

쓰레드 기반의 C 프로그램에서, 변수는 어떻게 저장되는지에 따라 아래와 같이 가상 메모리에 매핑된다:

1. 전역 변수(Global variables)
전역 변수는 함수 외부에서 선언된 모든 변수를 의미한다. 실행 시점에 가상 메모리의 읽기/쓰기(read/write) 영역은 각각의 전역 변수에 대해 정확히 하나의 인스턴스를 가진다. 이 인스턴스는 어떤 쓰레드에서든 참조 가능하다. 예제 코드에서 선언된 전역 변수 ptr은 가상 메모리의 읽기/쓰기 영역에 하나의 인스턴스를 가진다.
2. 자동 지역 변수(Local automatic variables)
자동 지역 변수는 static 속성 없이 함수 내부에 선언된 변수이다. 실행 시점에 각 쓰레드의 스택에는 해당 지역 변수의 인스턴스가 하나씩 존재한다. 이는 여러 쓰레드가 동일한 루틴을 실행하는 경우에도 마찬가지이다. 예를 들어, 지역 변수 tid는 메인 쓰레드의 스택에 하나의 인스턴스를 가지고 있으며, 이를 tid.m이라 표기한다. 다른 예시로는, 역 변수 myid는 두 개의 인스턴스를 가지며, 하나는 피어 쓰레드 0의 스택에, 다른 하나는 피어 쓰레드 1의 스택에 존재한다. 이를 각각 myid.p0, myid.p1이라 표기한다.
3. 정적 지역 변수(Local static variables)
static 속성으로 선언된 함수 내부 변수는 정적 지역 변수이다. 전역 변수와 마찬가지로, 가상 메모리의 읽기/쓰기 영역에 정확히 하나의 인스턴스를 가진다. 예제 프로그램에서 선언된 정적 변수 cnt는 여러 피어 쓰레드에 의해서 선언하더라도, 실제로는 한 번만 선언되며, 이는 가상 메모리의 읽기/쓰기 영역에 존재한다. 모든 피어 쓰레드는 이에 접근하여 cnt의 인스턴스를 읽고 쓴다.

Shared Variables

변수 v가 공유된(shared)다는 것은 변수 v의 인스턴스 중 하나 이상을 둘 이상의 쓰레드가 참조한다는 뜻이다. 예제 프로그램에서 변수 cnt는 런타임 인스턴스가 하나 뿐인데, 이를 두 개의 피어 쓰레드가 모두 참조하므로 공유된 변수이다. 반면, myid는 인스턴스가 두 개 있으며, 각각의 인스턴스는 한 쓰레드에 의해서만 참조되므로 공유되지 않는다. 이때, msgs와 같은 자동 지역 변수도 공유될 수 있다는 점을 주의해야 한다. 이를 바탕으로 ptr, cnt, i.m, msg.m, myid.p0, myid.p1의 공유 여부를 표로 나타내면 다음과 같다.

변수 인스턴스 메인 쓰레드에 의해
참조되는가? 		쓰레드 p0에 의해
참조되는가? 		쓰레드 p1에 의해
참조되는가? 		공유되는가?
ptr yes yes yes yes
cnt no yes yes yes
i.m yes no no no
myid.p0 no yes no no
myid.p1 no no yes no

Synchronizing Threads

쓰레드의 큰 장점 중 하나는 쓰레드 간에 편리하게 변수를 공유할 수 있다는 것이다. 하지만 이는 때때로 심각한 동기화 오류를 초래하기도 한다. 이에 대해 설명하기 위해, 아래의 badcnt.c 프로그램을 참고하자: 

/* WARNING: This code is buggy! */
#include "csapp.h"
void *thread(void *vargp);  /* Thread routine prototype */
volatile long cnt = 0; //counter로 사용되는 전역 변수

int main(int argc, char **argv) {
    long niters;
    pthread_t tid1, tid2;

    /* Check input argument */
    if (argc != 2) {
        printf("usage: %s <niters>\n", argv[0]);
        exit(0);
    }

    niters = atoi(argv[1]); //thread에 있는 루프의 반복 횟수

    //쓰레드 생성, niters의 주소를 넘겨서 각 쓰레드가 niters번 루프 돌도록 함
    Pthread_create(&tid1, NULL, thread, &niters);
    Pthread_create(&tid2, NULL, thread, &niters);
    //두 쓰레드가 모두 종료될 때까지 대기
    Pthread_join(tid1, NULL);
    Pthread_join(tid2, NULL);

    /* Check result */
    if (cnt != (2 * niters))
        printf("BOOM! cnt=%ld\n", cnt); //예측된 결과(cnt = 2 * niters)가 아님
    else
        printf("OK cnt=%ld\n", cnt);    //예측된 결과(cnt = 2 * niters)가 맞음

    exit(0);
}

/* Thread routine */
void *thread(void *vargp){
    long niters = *((long *)vargp);
    for (long i = 0; i < niters; i++) cnt++; //인자로 받은 niters 만큼 cnt를 증가

    return NULL;
}

위 프로그램은 두 개의 쓰레드를 생성하며, 각 쓰레드는 이름의 전역 공유 카운터 변수인 cnt를 반복문의 반복 횟수 만큼 증가시킨다. 이때 각 쓰레드가 cnt를 niters 횟수만큼 증가시키기 때문에, 최종 값이 2 * niters인 것은 언뜻 명확해 보인다. 하지만 이를 리눅스 시스템에서 실행시키면, 아래와 같은 결과를 얻는다: 

linux> ./badcnt 1000000
BOOM! cnt=1445085
linux> ./badcnt 1000000
BOOM! cnt=1915220
linux> ./badcnt 1000000
BOOM! cnt=1404746
Figure 1. Assembly code for the counter loop

위에서 출력된 결과값은 기대한 것과는 다른 값을 내놓을 뿐 아니라, 매번 다른 값이다. 문제의 원인을 이해하기 위해서, figure 1에 나타난 어셈블리 코드를 분석해보아야 한다. 이때 어셈블리 코드에서 쓰레드 i의 루프 코드를 아래와 같이 다섯 부분으로 나누어 보자:

  • Hi: 루프의 앞부분에 해당하는 명령어 블록
  • Li: 공유 변수 cnt를 누산기 레지스터 %rdx에 불러오는(load) 명령어[2]
  • Ui: %rdxi를 증가시키는(update) 명령어
  • Si: 업데이트된 %rdxi 값을 공유 변수 cnt에 저장(store)하는 명령어
  • Figure 2. Instruction orderings for the first loop iteration in badcnt.c.
    Ti: 루프의 뒷부분에 해당하는 명령어 블록

루프의 앞부분과 뒷부분은 오직 각 쓰레드의 스택에 저장된 변수만을 다루는 반면, Li, Ui, Si는 공유 카운터 변수(cnt)를 다룬다. badcnt.c의 두 피어 쓰레드가 단일 프로세서(uniprocessor)에서 동시에(concurrently) 실행될 때, 쓰레드의 어셈블리 명령어들은 어떤 순서로든 하나씩 완료된다. 따라서, 각각의 동시 실행(concurrent execution)은 두 쓰레드의 명령어들에 대한 임의의 실행 순서 를 정의하게 된다. 이렇게 실행되고 정의된 명령어들의 순서들 중 일부는 올바른 결과를 도출하지만, 다른 순서들은 그렇지 않다. 이때 핵심은 OS가 여러 피어 쓰레드의 명령어의 실행 순서를 예측하는 방법은 없다는 것이다.
예를 들어, figure 2(a)는 올바른 명령어 순서를 단계별로 보여준다. 각 쓰레드가 공유 변수 cnt를 업데이트한 후 메모리에 있는 cnt의 값은 2이며, 이는 기대한 결과이다. 반면, figure 2(b)에 나타난 명령어 실행 순서는 cnt에 대해 의도되지 않은 결과를 만든다. 이는 2번 쓰레드가 step5에서 cnt를 불러오는데, 이는 1번 쓰레드가 step2에서 cnt를 불러오고, 이를 step6에서 수정한 값을 저장한 사이에 있기 때문이다. 그 결과, cnt에는 두번의 갱신 작업이 수행되었지만, 여전히 값은 1이다.

Progress Graphs

Figure 3. Progress graph example

진행 그래프(Process graph)는 n개의 동시 실행되는 쓰레드의 실행을 n차원의 데카르트 공간(Cartesian space) 상의 trajectory으로 모델링한 것이다. 이때 각 축 k는 쓰레드 k의 진행 상황을 나타낸다. 또한 각 좌표 (I1, I2, ..., In)은 쓰레드 k(k = 1, ..., n)가 명령어 Ik을 완료한 상태를 나타낸다. 따라서 그래프의 원점은 어떠한 명령어도 완료되지 않았다는 것을 의미한다. Figure 3는 badcnt.c 프로그램의 루프 첫 번째 반복에 대한 2차원 진행 그래프를 보여준다. 이때 수평 축은 쓰레드 1에 해당하고, 수직 축은 쓰레드 2에 해당한다. Figure 3의 좌표 (L1, S2)는 쓰레드 1이 L1을 완료하고 쓰레드 2가 S2를 완료한 상태를 나타낸다.

Figure 4. An example trajectory

진행 그래프는 명령어 실행을 완료한 상태에서 다음 상태로의 전이로 모델링한다. 전이는 한 점에서 인접한 점으로 향하는 방향이 있는 간선(directed edge)으로 표현된다. 유효한 전이는 오른쪽(쓰레드 1의 명령어가 완료됨) 또는 위쪽(쓰레드 2의 명령어가 완료됨) 으로 이동하는 것이다. 이때 두 명령어가 동시에 완료될 수는 없으므로, 대각선 방향 전이(diagonal transition)는 허용되지 않는다. 또한 프로그램은 거꾸로 동작하지 않으므로, 왼쪽이나 아래로 이동하는 전이도 허용되지 않는다. 프로그램의 실행 이력은 상태 공간을 통과하는 trajectory(궤적)로 모델링된다. 예를 들어, figure 4는 아래와 같이 실행된 명렬어 순서에 대한 trajectory를 보여준다: 

H1, L1, U1, H2, L2, S1, T1, U2, S2, T2
Figure 5. Safe and unsafe trajectories

이때 쓰레드 i에 대해, 공유 변수 cnt의 내용을 조작하는 명령들인 (Li, Ui, Si)는 (공유 변수 cnt에 관해서) 임계 구역을 구성하며, 이는 다른 스레드의 임계 구역과 교차되어 실행(interleaved)되어서는 안 된다. 즉, Li, Ui, Si 명령어들이 수행되고 있다는 것은 쓰레드 i 내에서 어떤 공유 변수를 로드하고 수정하여, 그 결과를 저장하는 작업이 진행되고 있으므로 race condition을 막기 위해서 다른 쓰레드가 Li, Ui, Si을 통해 해당 공유 변수에 접근하면 안된다는 것이다. figure 5는 변수 cnt에 대한 비안전 영역(unsafe area)를 보여준다. 이때, 비안전 영역은 그 둘레가 모서리에 인접하지만, 이를 포함하지는 않는다. 예를 들어, 상태 (H1, H2)와 (S1, U2)는 비안전 영역에 인접하지만, 그 일부는 아니다. 비안전 영역을 피해가는 경로는 안전 경로(safe trajectory) 라고 한다. 반대로, 비안전 영역의 어느 부분이라도 통과하는 경로는 비안전 경로(unsafe trajectory)라고 한다. 이 역시 figure 5에 표시되어 있다.

모든 안전 경로는 공유 변수를 올바르게 갱신한다. 따라서 전역 데이터 구조를 공유하는 어떤 동시성 프로그램(concurrent program)의 실행이 올바르도록 보장하려면, 해당 프로그램의 실행에 사용되는 스레드들이 항상 안전 경로를 따라 작동하도록 보장해야 하며, 이는 동기화(synchronization)을 통해 구현된다. 이에 대한 고전적인 접근 방식은 세마포어(semaphore) 라는 개념을 기반한다.

Semaphore

자세한 내용은 Semaphore 문서를 참조해 주십시오.

Edsger Dijkstra는 세마포어(semaphore)라는 특수한 유형의 변수를 기반으로, 서로 다른 스레드를 동기화하는 해결책을 제안했다. 세마포어 s는 전역 변수이며, 0 이상의 정수 값을 가지는 변수이고, 두 연산 P와 V만이 이 값을 조작할 수 있다:

  • P(s):
    • 만약 s가 0이 아니라면, P 연산은 s를 감소시키고 즉시 리턴한다.
    • 만약 s가 0이라면, 스레드를 일시 중단(suspend)시키고, s가 0이 아니게 될 때까지 기다린다. 스레드가 재시작되면, P 연산은 s를 감소시키고 리턴한다.
  • V(s): V 연산은 s를 1 증가시킨다. 만약 s가 0이어서 P 연산에서 대기 중(blocked)인 스레드들이 있다면, V 연산은 이러한 스레드 중 정확히 하나를 재시작시킨다. 재시작된 스레드는 s를 감소시키며 P 연산을 마친다.

P 연산에서의 검사(test)와 감소(decrement) 동작은 불가분적으로 발생한다. 이는 세마포어 s가 0이 아닌 상태가 된 이후에는 해당 감소가 중단되지 않고 실행된다는 의미이다. 마찬가지로, V 연산에서의 증가 연산(increment) 도 불가분적으로 수행되며, 이는 세마포어의 값을 읽고(load), 증가시키고(increment), 저장(store)하는 전 과정이 중단 없이 일어난다는 의미다. 이때, V 연산을 구현할 때 중요한 것은 대기 중인 스레드들을 어떤 순서로 재시작할 것인지에 대한 정의가 아니라, 대기 중인 스레드들 중 정확히 하나를 재시작해야 한다는 것이다. 따라서 세마포어에 여러 스레드가 대기하고 있을 경우, V 연산으로 인해 어떤 스레드가 재시작될지 예측할 수 없다.

P와 V의 정의는, 적절히 초기화된 세마포어가 음수값을 가지는 상태에 프로그램이 절대 진입하지 않는 것을 보장한다. 이 속성은 세마포어 불변식(semaphore invariant) 으로 알려져 있으며, 동시성 프로그램의 실행 경로(trajectory)를 제어하는 강력한 도구를 제공한다. Posix 표준은 세마포어를 제어하기 위한 다양한 함수를 정의한다. 

#include <semaphore.h>
//반환값: 성공 시 0, 실패 시 -1
int sem_init(sem_t *sem, 0, unsigned int value);
int sem_wait(sem_t *s);   /* P(s) */
int sem_post(sem_t *s);   /* V(s) */

sem_init() 함수는 세마포어 sem을 지정된 value로 초기화한다. 또한 프로그램은 각각 sem_wait()과 sem_post() 함수를 호출하여 P 연산과 V 연산을 수행한다. 더 간결한 표현을 위해, 다음과 가튼 P, V의 래퍼(wrapper) 함수를 대신 사용하는 것이 권장된다. 

#include "csapp.h"
//반환값: 없음
void P(sem_t *s);   /* sem_wait의 래퍼 함수 */
void V(sem_t *s);   /* sem_post의 래퍼 함수 */

Using Semaphores for Mutual Exclusion

세마포어는 공유 변수에 대해 상호 배제적인 접근(mutually exclusive access)을 보장하는 편리한 방법을 제공한다. 기본적인 아이디어는 초기값이 1인 세마포어 s를 각 공유 변수(또는 관련된 공유 변수 집합)에 연관시키고, 해당하는 임계 구역(critical section) 을 P(s)와 V(s) 연산으로 감싸는 것이다. 이 방식에 더욱 자세히 설명하기 위해, 아래의 여러 단어와 표현들의 뜻에 대해 먼저 설명한다:

  • 이진 세마포어(binary semaphore): 공유 변수를 보호하는 데 사용되는 세마포어, 항상 0 또는 1
  • mutex: Mutually exclusive access를 구현하기 위해 사용되는 이진 세마포어
  • 잠그다(lock): Mutex에 대해 P 연산을 수행하는 것
  • 풀다(unlock): Mutex에 대해 V 연산을 수행하는 것
  • 보유하다(hold): 어떤 스레드가 뮤텍스를 잠그고, 아직 풀지 않았다.
  • 카운팅 세마포어(counting semaphore): 사용 가능한 자원의 집합에 대한 카운터로 사용되는 세마포어
Figure 6. Using semaphores for mutual exclusion

Figure 6는 어떻게 이진 세마포어를 사용하여 위에서 등장한 badcnt.c 프로그램을 동기화할 수 있는지 보여준다. Figure 에서 각 상태는 그 상태에서의 세마포어 s의 값으로 라벨링 되어 있으며, 해당 figure에서 이를 통해 알 수 있는 것은 P와 V 연산의 조합이 s < 0인 상태들의 집합, 즉 금지 영역(forbidden region)을 만든다는 것이다. 이때 세마포어 불변식은 s >= 0임을 보장하므로, 어떤 실행 경로도 비안전 영역을 통과할 수 없다. 따라서 모든 가능한 실행 경로는 안전(safe)하며, 어떤 상황에서도 프로그램은 cnt를 의도대로 증가시킨다. 따라서, P와 V 연산이 만들어내는 금지 영역은 하나의 시점에 여러 스레드가 동일한 임계 구역 내의 명령어들을 실행하는 것을 불가능하게 만들며, 이를 통해 임계 구역에 대한 상호 배제적인 접근을 보장한다.

이제 이 모든 것을 종합하여, badcnt.c 예제 프로그램을 세마포어를 사용해 적절히 동기화하려면, 먼저 mutex라는 세마포어를 선언한다: 

volatile long cnt = 0;  /* 카운터 */
sem_t mutex;            /* 카운터를 보호하는 세마포어 */

그리고 main 루틴에서 이를 1로 초기화 한다. 

Sem_init(&mutex, 0, 1);  /* mutex = 1 */

마지막으로, 스레드 루틴 내에서 공유 변수 cnt를 갱신하는 부분을 P와 V 연산으로 감싸서 보호한다: 

for (i = 0; i < niters; i++) {
    P(&mutex);
    cnt++;
    V(&mutex);
}

이제 적절히 동기화된 프로그램을 실행하면, 아래와 같이 항상 올바른 결과를 출력한다. 

linux> ./goodcnt 1000000
OK cnt=2000000

linux> ./goodcnt 1000000
OK cnt=2000000


각주

  1. ↑ 인스턴스는 메모리 상의 복사본을 의미하며, 인스턴스를 참조한다는 것은 해당 메모리 주소를 참조한다는 것을 의미한다.
  2. ↑ %rdxi는 쓰레드 i의 %rdx 값을 의미한다.
원본 주소 "https://junhoahn.kr/junyoung/index.php?title=Synchronization&oldid=2803"