[OSTEP] 스터디 10주차 - 병행성 1

운영체제는 하나의 물리적 CPU를 다수의 가상 CPU로 확장하여 마치 여러 개의 프로그램이 동시에 실행되는 것처럼 보이게 만든다. 이를 통해 사용자는 컴퓨터가 동시에 여러 작업을 수행하는 것처럼 느끼게 된다.

운영체제는 또한 각 프로세스가 독립적으로 많은 가상 메모리를 가지고 있는 것처럼 보이게 만든다. 이는 주소공간이라는 개념을 통해 구현된다. 주소공간은 각 프로그램이 메모리의 어느 부분을 사용할 수 있는지를 나타내는 가상의 메모리 공간이다. 운영체제는 물리 메모리를 여러 개의 주소 공간이 번갈아 가며 사용할 수 있도록 관리한다. 이를 통해 각 프로그램은 마치 자신만의 메모리를 가지고 있는 것 같은 독립성을 가진다.

---

병행성: 개요

쓰레드의 개념

전통적인 프로그램은 한순간에 하나의 명령만을 실행한다. 이를 단일 쓰레드 프로그램이라고 한다. 하지만 멀티 쓰레드 프로그램은 하나 이상의 실행 지점을 가지고 있다. 즉, 멀티 쓰레드 프로그램은 여러 개의 쓰레드를 가지고 있으며, 각 쓰레드는 독립적으로 명령어를 불러와 실행할 수 있다.

쓰레드는 프로세스와 매우 유사하다 다만 쓰레드들은 주소 공간을 공유하기 때문에 같은 데이터에 접근할 수 있다는 차이가 존재한다.

---

쓰레드의 상태와 문맥 교환

하나의 쓰레드의 상태는 프로세스의 상태와 매우 유사하다. 각 쓰레드는 프로그램 카운터와 레지스터를 가지고 있다. 프로그램 카운터는 다음에 실행할 명령어의 주소를 저장하고, 레지스터는 연산을 위해 데이터를 저장한다.

만약 두 개의 쓰레드가 하나의 프로세서에서 실행 중이라면, 실행하고자 하는 쓰레드는 반드시 문맥 교환을 통해 현재 실행 중인 쓰레드와 교체되어야 한다. 문맥 교환 과정에서는 교체되려는 쓰레드가 사용하던 레지스터들을 저장하고 교체되어 실행되는 쓰레드가 이전에 사용하던 레지스터의 내용을 복원한다. 이는 프로세스 간의 문맥 교환과 유사한 과정이다.

프로세스의 상태를 저장하기 위해 ‘프로세스 제어 블록(Process Control Block, PCB)’이 사용되듯이, 쓰레드의 상태를 저장하기 위해서는 ‘쓰레드 제어 블록(Thread Control Block, TCB)’이 사용된다. 다만 프로세스 간 문맥 교환과 달리, 쓰레드 간 문맥 교환에서는 주소 공간을 그대로 사용한다는 점이 다르다.

---

쓰레드와 스택

쓰레드와 프로세스의 또 다른 차이점은 ‘스택’에 있다. 단일 쓰레드 프로세스에서는 주소 공간 내에 하나의 스택만 존재한다. 스택은 주로 주소 공간의 하부에 위치한다.

반면에 멀티 쓰레드 프로세스에서는 각 쓰레드가 독립적으로 실행되며, 실행에 필요한 여러 함수를 호출할 수 있다. 따라서 멀티쓰레드 프로세스의 주소 공간에는 각 쓰레드마다 별도의 스택이 할당된다.

각 쓰레드의 스택에 저장되는 변수, 매개변수, 리턴 값 등은 쓰레드-로컬 저장소라고 불린다. 쓰레드-로컬 저장소로 인해 기존의 단순한 주소 공간 구조는 조금 복잡해진다. 단일 스택 구조에서는 스택과 힙이 서로 독립적으로 확장되기 때문에, 주소 공간이 부족한 경우에만 문제가 발생했다. 하지만 멀티 쓰레드 구조에서는 상황이 예전처럼 단순하지 않다. 다행히 일반적으로 각 쓰레드의 스택 크기가 크지 않기 때문에 대부분의 경우 문제가 되지 않다. 단, 재귀 호출을 매우 많이 사용하는 경우에는 주의가 필요하다.

---

예제: 쓰레드 생성

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

void *mythread(void *arg) {
    printf("%s\n", (char *) arg);
    return NULL;
}

int main(int argc, char *argv[]) {
    pthread_t p1, p2;
    int rc;

    printf("main: begin\n");

    rc = pthread_create(&p1, NULL, mythread, "A");
    assert(rc == 0);

    rc = pthread_create(&p2, NULL, mythread, "B");
    assert(rc == 0);

    // 쓰레드가 종료될 때까지 대기하기 위해 join 사용
    rc = pthread_join(p1, NULL); assert(rc == 0);
    rc = pthread_join(p2, NULL); assert(rc == 0);

    printf("main: end\n");
    return 0;
}

이 코드에서 메인 프로그램은 mythread() 함수를 실행할 두 개의 쓰레드를 생성한다. 각 쓰레드는 서로 다른 인자를 전달받는다.

• pthread_create(): 새로운 쓰레드를 생성하는 함수. 첫 번째 인자는 쓰레드 식별자, 두 번째 인자는 쓰레드 속성 (여기서는 NULL 사용), 세 번째 인자는 쓰레드가 실행할 함수, 네 번째 인자는 해당 함수에 전달할 인자.
• pthread_join(): 특정 쓰레드가 종료되기를 기다리는 함수. 첫 번째 인자는 기다릴 쓰레드의 식별자, 두 번째 인자는 쓰레드의 반환값을 받을 포인터 (여기서는 NULL 사용).

쓰레드가 생성되면, 스케줄러의 동작에 따라 즉시 실행되거나 대기(Ready) 상태에 머무를 수 있다.

이 프로그램의 가능한 실행 순서는 다음과 같다.

 

스케줄러가 특정 시점에 어떤 쓰레드를 실행하느냐에 따라 다양한 순서가 나올 수 있다.

예를 들어, 쓰레드 1이 쓰레드 2보다 먼저 생성되었더라도 스케줄러가 쓰레드 2를 먼저 실행한다면 “B”가 “A”보다 먼저 출력될 수 있다. 먼저 생성되었다고 해서 반드시 먼저 실행된다는 보장은 없다.

쓰레드의 생성은 함수 호출과 유사해 보이지만, 함수 호출에서는 함수가 실행을 마치면 호출자(caller)에게 리턴하는 반면, 쓰레드 생성에서는 새로운 쓰레드가 생성되어 호출자와는 독립적으로 실행된다. 쓰레드는 생성 함수가 리턴되기 전이나 후에 실행될 수 있다.

이 예제에서 볼 수 있듯이, 쓰레드는 프로그램의 실행 흐름을 복잡하게 만든다. 어떤 쓰레드가 언제 실행될지 정확히 예측하기 어려워지기 때문이다. 이러한 병행성(concurrency) 문제로 인해 프로그래밍의 복잡도가 크게 증가한다.

---

훨씬 더 어려운 이유: 데이터의 공유

앞의 간단한 쓰레드 예제를 통해 쓰레드의 생성 방법과 실행 순서가 스케줄러의 동작에 따라 달라질 수 있음을 살펴보았다. 하지만 예제에서는 쓰레드 간의 상호작용, 특히 공유 데이터에 대한 접근은 다루지 않았다.

아래 코드는 전역 공유 변수를 갱신하는 두 개의 쓰레드를 사용한 간단한 예제이다.

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

static volatile int counter = 0;

// mythread()
// 인자로 전달된 문자열을 출력하고
// 10000000번 반복하며 counter에 1을 더하는 함수
// 끝나면 다시 인자 문자열을 출력
void *mythread(void *arg) {
    printf("%s: begin\n", (char *) arg);

    for (int i = 0; i < 1e7; i++) {
        counter = counter + 1;
    }

    printf("%s: done\n", (char *) arg);
    return NULL;
}

// main()
// 두 개의 쓰레드를 생성하고 (pthread_create)
// 기다린다 (pthread_join)
int main(int argc, char *argv[]) {
    pthread_t p1, p2;

    printf("main: begin (counter = %d)\n", counter);

    Pthread_create(&p1, NULL, mythread, "A");
    Pthread_create(&p2, NULL, mythread, "B");

    // 쓰레드가 종료될 때까지 기다리기 위해 join 사용
    Pthread_join(p1, NULL);
    Pthread_join(p2, NULL);

    printf("main: done with both (counter = %d)\n", counter);
    return 0;
}

이 코드에서 주목할 점은 다음과 같다:

1. 에러 처리를 간단히 하기 위해 Pthread_create()와 Pthread_join() 래퍼 함수를 사용했다. 이들 함수는 실패 시 에러 메시지를 출력하고 프로그램을 종료한다.
2. 작업자 쓰레드로 두 개의 독립된 함수를 만드는 대신, 하나의 함수(mythread())를 사용하고 인자를 통해 출력할 문자열을 전달했다.
3. 각 작업자 쓰레드는 공유 변수 counter에 1,000만 번(1e7) 1을 더한다. 따라서 최종 결과는 20,000,000이 되어야 한다.

이제 프로그램을 컴파일하고 실행해 보겠다.

prompt> gcc -o main main.c -Wall -pthread
prompt> ./main
main: begin (counter = 0)
A: begin
B: begin
A: done
B: done
main: done with both (counter = 20000000)

하지만 이 코드를 실행하면 단일 프로세서에서도 항상 기대한 결과가 나오지는 않는다. 때로는 아래와 같은 결과가 나올 수 있다.

prompt> ./main
main: begin (counter = 0)
A: begin
B: begin
A: done
B: done
main: done with both (counter = 19345221)

이것이 정말 잘못된 것인지 확인하기 위해 프로그램을 다시 실행해 보겠다. 

prompt> ./main
main: begin (counter = 0)
A: begin
B: begin
A: done
B: done
main: done with both (counter = 19221041)

팁: 도구를 제대로 알고 사용하자

프로그램을 작성하고 디버깅하며 컴퓨터 시스템을 이해하는 데 도움이 되는 새로운 도구들을 항상 배워야 한다. 역어셈블러(disassembler)는 유용한 도구 중 하나다. 실행 파일에 역어셈블러를 실행하면 해당 프로그램이 어떤 어셈블리 명령어들로 구성되었는지 알 수 있다.

예를 들어, 예제에서 사용한 카운터를 갱신하는 저수준 코드를 이해하고 싶다면 Linux의 objdump 명령어를 사용하여 어셈블리 코드를 볼 수 있다.

prompt> objdump -d main

이 명령어를 수행하면 프로그램의 모든 명령어가 출력된다. 컴파일 시 -g 옵션을 사용했다면 프로그램의 심벌 정보를 포함하는 식별자와 함께 정리되어 나열된다.

objdump는 반드시 사용법을 익혀야 할 많은 도구 중 하나다. gdb와 같은 디버거, valgrind나 purify와 같은 메모리 프로파일러, 그리고 컴파일러 역시 시간을 들여 사용법을 익혀야 할 도구들이다. 도구를 잘 사용할수록 더 좋은 시스템을 개발할 수 있다

각 실행 결과가 잘못되었을 뿐만 아니라 실행마다 결과가 다르다 이는 매우 큰 의문을 불러일으킨다. 왜 이런 일이 일어나는 것일까?

---

제어 없는 스케줄링

이러한 현상이 발생하는 이유를 이해하려면 counter 갱신을 위해 컴파일러가 생성한 코드의 실행 순서를 파악해야 한다. counter에 단순히 1을 더하려고 한다. x86에서 counter를 증가시키는 코드의 순서는 다음과 같다.

mov 0x8049a1c, %eax
add $0x1, %eax
mov %eax, 0x8049a1c

이 예제에서 counter 변수의 주소는 0x8049a1c라고 가정한다. 이 세 줄의 명령어에서는 먼저 x86의 mov 명령어가 지정된 메모리 주소의 값을 읽어 eax 레지스터에 저장한다. 그런 다음 eax 레지스터의 값에 1(0x1)을 더한다. 마지막으로 eax에 저장된 값을 메모리의 원래 주소에 다시 저장한다.

두 개의 쓰레드 중 쓰레드 1이 counter를 증가시키는 코드 영역에 진입하여 counter의 값을 1 증가시키려는 상황을 가정해 보겠다. counter의 값이 50이라면 50을 eax 레지스터에 저장한다. 쓰레드 1에서 eax는 50이 된다. 그 후 레지스터의 값에 1을 더해 eax는 51이 된다.

이제 상황이 안 좋아진다. 타이머 인터럽트가 발생하여 운영체제가 실행 중인 쓰레드의 PC 값과 eax를 포함한 레지스터들의 현재 상태를 쓰레드의 TCB(Thread Control Block)에 저장한다. 그리고 상황은 더 악화된다. 쓰레드 2가 선택되고 counter 값을 증가시키는 동일한 코드 영역에 진입한다. 첫 번째 명령어를 실행하여 counter 값을 읽어 eax에 저장한다. 각 쓰레드는 개별적인 쓰레드 전용 레지스터를 가지고 있다. 사용 중이던 레지스터들을 저장하고 복구하는 문맥 교환 코드에 의해 이 레지스터들은 가상화된다. counter 값은 아직 50이므로 쓰레드 2의 eax 값은 50이다. 쓰레드 2가 다음 두 문장을 실행하면 eax 값을 1 증가시켜 eax는 51이 되고, eax 값을 counter(주소 0x8049a1c)에 저장한다. 전역 변수 counter는 이제 51이 된다.

마지막으로 또 한 번의 문맥 교환이 발생하면 쓰레드 1이 다시 실행된다. 이전 상황을 떠올려 보면 쓰레드 1은 mov와 add 동작을 실행했고 이제 마지막 mov 명령어를 수행하려는 중이다. 그리고 eax는 51이다. 따라서 mov 명령어가 실행되면 레지스터의 값을 메모리에 저장하여 counter의 값은 다시 51이 된다.

무슨 일이 일어난 것일까? 간단히 말하면 counter의 값을 증가시키는 코드가 두 번 수행되었지만, 50에서 시작한 counter의 값은 1만 증가하여 51이 되었다. “정확하게” 동작하도록 작성된 프로그램이라면 counter의 값은 52가 되어야 한다.

이 문제를 더 잘 이해하기 위해 실행 흐름을 구체적으로 살펴보겠다. 이 예제에서는 다음과 같이 코드가 메모리 주소 100에 저장되어 있다고 가정한다(RISC 유사 명령어 집합에 익숙하다면 x86은 명령어 길이가 가변적이라는 점과 mov 명령어는 5바이트, add 명령어는 3바이트를 사용한다는 점을 참고해야 한다).

100 mov 0x8049a1c, %eax
105 add $0x1, %eax
108 mov %eax, 0x8049a1c

이러한 가정 하에 일어나는 동작을 아래 표에 나타내었다. counter의 초기값은 50이라고 가정하고 예제의 내용을 상기하며 흐름을 따라가 보겠다.

예시에서처럼 명령어의 실행 순서에 따라 결과가 달라지는 상황을 ‘경쟁 조건(race condition)’이라고 한다. 문맥 교환이 부적절한 시점에 실행되면 잘못된 결과를 얻게 된다. 실제로 경쟁 조건에 처한 경우 실행할 때마다 다른 결과를 얻는다. 컴퓨터의 일반적인 동작에서 발생하는 결정적 결과와 달리, 결과를 예측할 수 없거나 실행할 때마다 결과가 다른 경우를 ‘비결정적(indeterminate)’인 결과라고 한다.

여러 쓰레드가 동일한 코드를 실행할 때 경쟁 조건이 발생하기 때문에 이러한 코드 부분을 ‘임계 영역(critical section)’이라고 한다. 공유 변수(또는 더 일반적으로는 공유 자원)에 접근하고 하나 이상의 쓰레드에서 동시에 실행되면 안 되는 코드를 임계 영역이라고 한다.

이러한 코드에서 필요한 것은 ‘상호 배제(mutual exclusion)’이다. 이 속성은 하나의 쓰레드가 임계 영역 내의 코드를 실행 중일 때는 다른 쓰레드가 실행할 수 없도록 보장해 준다.

---

원자성에 대한 바람

임계 영역 문제를 해결하는 방법 중 하나는 강력한 단일 명령어로 의도한 동작을 수행하여 인터럽트 발생 가능성을 원천적으로 차단하는 것이다. 예를 들어, 다음과 같은 강력한 명령어가 있다고 가정해 보겠다.

memory-add 0x8049a1c, $0x1

이 명령어는 메모리의 특정 위치에 어떤 값을 더하는 명령어다. 하드웨어가 이 명령어의 원자적 실행을 보장한다고 가정한다. 이 명령어가 실행되면 원하는 대로 값이 갱신될 것이다. 하드웨어가 원자성을 보장하기 때문에 명령어 수행 도중에 인터럽트가 발생하지 않는다. 인터럽트가 발생하더라도 명령어가 실행되지 않았거나 실행이 완료된 후라는 것을 의미하며, 중간 상태는 존재하지 않는다. 멋진 하드웨어, 아닌가?

문맥 상 ‘원자적’이라는 말은 “하나의 단위”를 뜻하며, 때로는 “전부 아니면 전무”로 이해될 수도 있다. 다음 세 개의 명령어가 원자적으로 실행되기를 원한다고 가정해 보겠다.

mov 0x8049a1c, %eax
add $0x1, %eax
mov %eax, 0x8049a1c

여담: 주요 병행성 관련 용어
Critical Section, Race Condition, Indeterminate, Mutual Exclusion
사용된 네 개의 용어는 병행 코드의 핵심 개념이므로 명시적으로 정의하고 넘어가겠다. 더 자세한 정보를 원한다면 Dijkstra의 초기 연구 [Dij65; Dij68]를 살펴보시기 바란다.

- 임계 영역(critical section)은 일반적으로 변수나 자료 구조와 같은 공유 자원에 접근하는 코드의 일부분을 말한다.
- 경쟁 조건(race condition)은 여러 쓰레드가 거의 동시에 임계 영역을 실행하려고 할 때 발생하며, 공유 자료 구조를 모두가 갱신하려고 시도한다면 의도하지 않은 놀라운 결과를 만들어낸다.
- 비결정적(indeterminate) 프로그램은 하나 이상의 경쟁 조건을 포함하여 실행 결과가 각 쓰레드의 실행 시점에 의존하기 때문에 프로그램의 결과가 실행할 때마다 달라진다. 결과는 컴퓨터 시스템에서 일반적으로 기대하는 것과 달리 결정적이지 않다.
- 이러한 문제를 피하려면 쓰레드는 상호 배제(mutual exclusion)라는 기법을 사용하여 하나의 쓰레드만 임계 영역에 진입할 수 있도록 보장해야 한다. 그 결과 경쟁을 피할 수 있고 프로그램 실행 결과를 결정론적으로 얻을 수 있다.

앞서 언급했듯이, 위의 명령어들을 하나의 명령어로 대체할 수 있다면 해당 명령어를 사용하면 된다. 하지만 일반적인 상황에서는 그러한 명령어가 없다고 봐야 한다. 병행성을 가지는 B-tree를 만들면서 값을 갱신한다고 할 때, B-tree를 원자적으로 갱신하는 어셈블리 명령어를 원할까? 글쎄, 아마도 제정신이라면 그렇지 않을 것이다.

하드웨어적으로는 동기화 함수(synchronization primitives) 구현에 필요한 기본적인 명령어 몇 개만 필요하다. 결과적으로 병행 실행이라는 어려운 상황에서 하드웨어 동기화 명령어와 운영체제의 지원을 통해 한 번에 하나의 쓰레드만 임계 영역에서 실행하도록 구성된 “제대로 잘 작동하는” 멀티 쓰레드 프로그램을 작성할 수 있다.

---

또 다른 문제: 상대 기다리기

지금까지 병행성 문제는 주로 공유 변수에 접근할 때 발생하는 쓰레드 간의 상호 작용 문제로 정의되었다. 하지만 실제 상황에서는 한 쓰레드가 다른 쓰레드의 작업이 완료될 때까지 기다려야 하는 경우도 자주 발생한다.

예를 들어, 프로세스가 디스크에 입출력(I/O) 요청을 보내고 응답이 올 때까지 대기 상태로 들어가는 상황이 있다. 이 경우, 프로세스는 I/O 작업이 끝날 때까지 잠들어 있다가(sleep), I/O가 완료되면 다시 깨어나(wake up) 작업을 계속 진행하게 된다.

• 잠자기(sleep): 프로세스나 쓰레드가 특정 이벤트(예: I/O 완료)가 발생할 때까지 대기 상태로 들어가는 것을 의미한다.
• 깨우기(wake up): 잠들어 있던 프로세스나 쓰레드가 특정 이벤트가 발생하면 다시 실행 가능한 상태로 전환되는 것을 의미한다.

이후 내용에서는 원자적 연산을 지원하기 위한 동기화 함수들의 구현 방법과 멀티 쓰레드 프로그램에서 흔히 사용되는 잠자기/깨우기 동작을 지원하는 기술에 대해 다룰 것이다.