동기화 (1)

쓰레드 메모리 모델

동시성 쓰레드의 풀은 한 개의 컨텍스트에서 돌아간다. 각각의 쓰레드는 자신만의 별도의 쓰레드 컨텍스트를 가지며, 여기에는 쓰레드 ID, 스택, 스택 포인터, 프로그램 카운터, 조건 코드, 범용 레지스터 값이 포함될 것이다. 각 쓰레드는 프로세스의 가상주소공간을 공유하며 여기에는 코드 섹션, 데이터 섹션, 힙, 공유 라이브러리 코드 등을 포함할 것이다.

각 쓰레드는 별도의 스택 저장소를 가지고 있으며 때문에 한 쓰레드가 다른 쓰레드의 스택에 접근하여 이를 읽거나 쓰는 등의 행동은 불가능하다. 또한 각자 고유한 레지스터를 참조하고 있기 때문에 다른 쓰레드의 레지스터에 접근하여 읽고 쓰는 것도 불가능해진다. 마지막으로 쓰레드들은 각자 고유한 PC 값을 가지고 분리된 형태의 논리 흐름으로 전개된다.

프로세스를 분기시켜 동시에 여러 논리 흐름을 전개하는 것은 이러한 쓰레드의 단점을 보완할 수 있다. 프로세스를 분기시키는 경우, 자식 프로세스는 부모 프로세스의 가상주소공간에 대한 사본을 얻는다. 때문에 자식 프로세스에서 부모 프로세스의 가상주소공간에 접근이 불가능하며, 반대의 경우도 마찬가지이다.

그러나 이는 또 다른 단점을 낳는다. 바로 데이터들의 공유가 어려워지는 것이다. 프로세스에서는 변수 값등을 공유하기 위해서 IPC(inter-process communication)라는 특별한 매커니즘을 거친다. IPC는 쓰레드의 방식보다 비싸다. 데이터를 공유하기 위해서 시간적으로 소모가 많이 발생하며 이를 다른 말로 오버헤드가 크다라고 부른다. 이때 IPC를 수행하는 방식에는 다양한 방식이 있는데, 이는 추후 글에서 다시 살펴보도록 하자.

쓰레드는 프로세스의 이러한 단점을 보완할 수 있다. 앞서 설명했듯 쓰레드는 프로세스와 달리 하나의 논리흐름을 가지되, 완전한 분리가 이뤄지진 않았다. 앞서 설명하였듯 일반적으로 쓰레드 풀 내에서는 쓰레드 컨텍스트들을 공유할 수 있으며 IPC와 같은 번거로운 작업 없이, 전역 변수를 통해서 데이터를 공유할 수 있다.

다만 이는 Race 라는 또 다른 문제를 낳는다. 만약 동시에 여러 쓰레드가 하나의 자원에 접근한다면? 하나의 쓰레드가 해당 자원을 사용하고 있는데 만약 다른 쓰레드가 해당 자원에 접근하고자 한다면? 등과 같은 문제가 발생한다. 해당 글에서는 이러한 문제를 보완하기 위한 동기화라는 개념을 설명한다.

변수들을 메모리로 매핑하기

쓰레드를 사용하는 C 프로그램의 변수들은 이들의 저장 클래스에 따라서 가상메모리에 매핑된다.

전역 변수. 전역 변수는 함수 밖에서 선언된 모든 변수를 말한다. 런타임에 가상메모리의 읽기/쓰기 영역은 쓰레드에 의해 참조될 수 있는 각각의 전역 변수의 정확히 한 개의 인스턴스를 포함한다.

지역 자동 변수. 지역 자동 변수는 함수 내에서 static 특성 없이 선언된다. 런타임에 각 쓰레드의 스택은 자신만의 지역 자동 변수의 인스턴스를 가진다. 이는 심지어 다수의 쓰레드가 동일한 쓰레드 루틴을 사용하는 경우에도 그렇다. 

지역 정적 변수. 지역 정적 변수는 함수 안에서 static 특성으로 선언된 변수다. 전역 변수처럼 가상메모리의 읽기 쓰기 영역은 프로그램에서 선언된 각 지역 정적 변수의 정확히 한 개의 인스턴스를 가진다.

공유 변수
어떤 변수 v는 자신의 인스턴스 중의 한 개가 하나 이상의 쓰레드에 의해 참조되는 경우에만 공유되어 있다고 말한다.

동기화 오류

공유 변수들은 편리하지만 심각한 동기화 오류를 가져올 수 있다. 다음의 예제를 살펴보자

#include <ptrhead.h>
#include <stdio.h>
#include <stdlib.h>

void *thread(void *vargp); /* Thread routine prototype */

/* Global Shared variable */
volatile int cnt = 0; /* Counter */

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

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

    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=%d\n", cnt);
    else
        printf("OK cnt=%d\n", cnt);
    exit(0);
}

void *thread(void *vargp)
{
    int i, niters = *((int *)vargp);

    for (i = 0; i < niters; i++)
        cnt++;
    return NULL;
}

 

위와 같은 코드는 실행마다 그 결과가 달라진다. 이는 공유 변수에 대한 접근 순서가 정해져있지 않기 때문이다. 우리는 코드를 한줄 한줄 문법에 따라 작성한다. 그러나 우리가 바라보는 코드와 달리 실제 컴퓨터가 해석하는 코드는 각 라인을 더욱 세분화하여 이를 여러 사이클에 수행할 수 있도록 변환한다. 때문에 우리가 보는 코드보다 실제 기계어 단의 명령어는 훨씬 길고 복잡하다.

사실 우리 눈에는 공유 변수의 동기화가 굳이 필요할까라는 의문이 드는 코드가 종종 있다. 위의 코드도 마찬가지이다. 쓰레드 핸들러는 간단하게 반복문을 특정 단위로 반복할 뿐이다. 반복에 사용되는 변수는 공유변수가 아니기에 반복문 자체는 문제 없이 당초 의도만큼 돌아갈 것이다. 다만 cnt가 문제가 된다. 이 부분이 다소 조금 헷갈리는데, cnt가 당초 정해진 반복문만큼 증가 연산을 했다면 문제가 없는 것 같은 착각이 든다. 

그러나 그렇지 않다. 앞서 말했듯, cnt++ 라고 적힌 한줄의 코드는 사실 여러 줄의 기계어로 표현될 여지가 있다. 이는 CPU 아키텍쳐마다 다르며 하드웨어의 고유한 최적화 방식에 의존한다.

결국 이러한 코드는 앞서 말했던 동기화 오류를 발생시킨다. 

진행 그래프 ( Progress Graph )

진행 그래프는 n 개의 동시성 쓰레드를 n 차원의 직교좌표 공간을 지나는 궤적으로 모델링한다. 이때 각각의 축 k는 쓰레드 k의 진행에 대응되며 각각의 점 I는 쓰레드 K가 특정 인스트럭션 I를 완료한 상태를 나타낸다.

진행 그래프를 작성하면 실제 쓰레드의 진행이 어떻게 되는지를 시각적으로 표현할 수 있다. 좀 더 구체적으로 쓰레드의 동기화 문제가 발생할 여지가 있는 가능성을 시각적으로 표현할 수 있다.

그림 1. 진행 그래프 상 초기 상태

위의 그래프는 진행 그래프를 본격적으로 그리기 전의 초기화 상태를 보여준다. 해당 상태에서 그래프는 오로지 오른쪽과 위쪽만으로 진행을 하게 된다. 대각선과 왼쪽, 아래로의 이동은 불허한다. 

그림 2. 궤적의 예

쓰레드 프로그래밍을 수행하면 특정 쓰레드 i에 대해서 공유 변수 cnt의 내용을 조작하는 인스트럭션들은 크리티컬 섹션을 형성한다. 크리티컬 섹션에서는 특정 공유 자원에 대해서 다른 쓰레드들로부터 상호 배타적으로 공유 변수를 접근하도록 보장받아야 한다. 만약 그렇지 않는다면, 앞서 발생했던 동기화 오류가 발생할 가능성이 존재한다. 일반적으로 이러한 현상을 상호 배제 (mutual exclusion)라고 하며, 이는 이후 동기화를 가능하게 하는 핵심 요소로 기능한다.

진행 그래프에서 두 개의 크리티컬 섹션의 교차점은 위험 구역이라는 상태 공간의 구역을 정의하는데, 만약 위험 영역에 침범한 궤적은 동기화 오류를 발생시킬 수 있다는 의미로 위험 궤적으로 불리게 된다. 이때 주의할 점은 위험 구역의 둘레에 접할 뿐인 궤적은 위험 궤적이 아니라는 점이다.

그림 3. 안전 궤적과 위험 궤적의 예

모든 안전 궤적은 공유 변수를 정확하게 갱신할 것이다. 쓰레드들은 어떤 방식으로든 동기화를 통해 이들이 항상 안전 궤적을 가지도록 해야 한다. 고전적인 방법은 세마포어 개념에 기초한 것으로 바로 다음 글에서 소개하고자 한다.