[운영체제 아주 쉬운 세 가지 이야기 - Virtualization] 26. Concurrency and Threads
이 글은 제 개인적인 공부를 위해 작성한 글입니다.
틀린 내용이 있을 수 있고, 피드백은 환영합니다.
개요
지금까지 운영체제가 다루는 기본 개념들의 발전 과정을 살펴보았다. 하나의 물리적 CPU를 다수의 가상 CPU로 확장하여 마치 여러 개의 프로그램이 동시에 실행하는 듯한 착시를 만들었다. 그리고 개별적인 프로세스가 모두 독립적으로 많은 가상 메모리를 가지는 것처럼 보이게 만들었다. 주소 공간(address space)이라는 개념을 통해 각 프로그램들이 마치 자신만의 메모리를 가지고 있는 것처럼 동작하는데, 사실은 운영체제가 물리 메모리를 여러 개의 주소 공간이 서로 번갈아 가면서 사용하게 한다.
이번 장에서는 프로세스를 위한 새로운 개념인 쓰레드(thread)를 소개한다. 프로그램에서 한 순간에 하나의 명령어를 실행하는 고전적인 관점에서 벗어나 멀티 쓰레드 프로그램은 하나 이상의 실행 지점 (독립적으로 불러 들여지고 실행될 수 있는 여러 개의 PC 값)을 가지고 있다. 멀티 쓰레드를 이해하는 다른 방법은 각 쓰레드가 프로세스와 매우 유사하지만, 차이가 있다면 쓰레드들은 주소 공간을 공유하기 때문에 동일한 값에 접근할 수 있다는 것이다.
하나의 쓰레드의 상태는 프로세스의 상태와 매우 유사하다. 쓰레드는 어디서 명령어를 불러 들일지 추적하는 프로그램 카운터(PC)와 연산을 위한 레지스터들을 가지고 있다. 만약 두 개의 쓰레드가 하나의 프로세서에서 실행 중이라면 실행하고자 하는 쓰레드 (T2)는 반드시 문맥 교환(context switch)를 통해서 실행 중인 쓰레드(T1)와 교체되어야 한다.
쓰레드 간의 문맥 교환은 T1이 사용하던 레지스터들을 저장하고 T2가 사용하던 레지스터의 내용을 복원한다는 점에서 프로세스의 문맥 교환과 유사하다. 프로세스가 문맥 교환을 할 때에 프로세스의 상태를 PCB(Process Control Block)에 저장하듯이 프로세스의 쓰레드들의 상태를 저장하기 위해서는 하나 또는 그 이상의 쓰레드 제어 블럭(thread control block, TCB)이 필요하다. 가장 큰 차이 중 하나는 프로세스의 경우와 달리 쓰레드 간의 문맥 교환에서는 주소 공간을 그대로 사용한다는 것이다 (사용하고 있던 페이지 테이블을 그대로 사용하면 된다).
쓰레드와 프로세스의 또 다른 차이는 스택에 있다. 고전적인 프로세스 주소 공간과 같은 간단한 모델(단일 쓰레드 프로세스)에서는 스택이 하나만 존재한다. 아래 그림을 보면 주로 주소 공간의 하부에 위치한다.
반면에 멀티 쓰레드 프로세스의 경우에는 각 쓰레드가 독립적으로 실행되며 쓰레드가 실행하기 위해 여러 루틴들을 호출할 수 있다. 주소 공간에는 하나의 스택이 아니라 쓰레드마다 스택이 할당되어 있다. 두 개의 쓰레드를 가지는 멀티 쓰레드 프로세스의 주소 공간은 단일 쓰레드 프로세스의 주소 공간과 다르다. (우측 그림)
그림에서는 두 개의 스택이 프로세스 주소 공간에 존재하는 것을 볼 수 있다. 스택에서 할당되는 변수들이나 매개변수, 리턴 값, 그리고 그 외에 스택에 넣는 것들은 해당 쓰레드의 스택인 쓰레드-로컬 저장소(thread-local storage)라 불리는 곳에 저장된다.
쓰레드-로컬 저장소로 인해 정교한 주소 공간의 배치가 무너진다는 것을 알았을 것이다. 전에는 스택과 힙이 독립적으로 확장되기 때문에 주소 공간에 더 이상 공간이 없는 경우에만 문제가 생겼었다. 이제는 상황이 예전처럼 깔끔하지 않다. 다행스러운 것은 스택의 크기가 아주 크지 않아도 되기 때문에 대부분의 경우에는 문제가 되지 않는다 (재귀 호출을 아주 많이 하는 경우는 제외한다).
예제 : 쓰레드 생성
한 쓰레드는 “A”라고 출력하고 다른 쓰레드는 “B”라고 출력하는 독립적인 두 개의 쓰레드를 생성하는 프로그램을 실행시킨다고 해 보자. 코드는 아래 그림에 잇다.
메인 프로그램은 각각 mythread() 함수를 실행할 두 개의 쓰레드를 생성한다. 이때 각 mythread() 함수는 서로 다른 인자를 전달받는다. 스케줄러의 동작에 따라 다르겠지만, 쓰레드가 생성되면, 즉시 실행될 수도 있고, 준비(Ready) 상태에서 실행은 되지 않을 수 있다. 두 개의 쓰레드(T1과 T2)를 생성한 후에 메인 쓰레드는 pthread_join()을 호출하여 특정 쓰레드의 동작의 종료를 대기한다.
이 프로그램의 가능한 실행 순서를 살펴보도록 하자. 실행 순서도 그림에서 시간은 아래 방향으로 진행하고 각 열은 각 쓰레드(메인, 쓰레드 1 또는 쓰레드 2)가 언제 실행 중인지를 나타낸다.
유의할 점은 도표에서 나타내는 실행 순서가 쓰레드가 유일한 실행 가능 순서가 아니라는 것이다. 스케줄러가 특정 시점에서 실행하는 쓰레드에 따라 다양한 순서가 있을 수 있다. 예를 들어 그림에서 나타낸 실행 순서도와 같이 쓰레드가 생성된 후 즉시 실행될 수도 있다.
쓰레드 1이 쓰레드 2보다 먼저 생성된 경우라 하더라도 만약 스케줄러가 쓰레드2를 먼저 실행하면 “B”가 “A”보다 먼저 출력될 수도 있다. 먼저 생성되었다고 해서 먼저 실행될 것이라는 가정을 할 어떤 이유도 없다. 그림 29.5는 쓰레드 2가 쓰레드 1보다 먼저 실행되는 마지막 경우를 보인다.
쓰레드의 생성이 함수의 호출과 유사하게 보인다. 함수 호출에서는 함수 실행 후에 호출자 (caller)에게 리턴하는 반면에 쓰레드의 생성에서는 실행할 명령어들을 갖고 있는 새로운 쓰레드가 생성되고, 생성된 쓰레드는 호출자와는 별개로 실행된다. 쓰레드 생성 함수가 리턴되기 전에 쓰레드가 실행될 수도 있고, 그보다 이후에 실행될 수도 있다.
이 예제에서 알 수 있듯이, 쓰레드는 일을 복잡하게 만든다. 이 간단한 예제에서도 어떤 쓰레드가 언제 실행되는지 알기 어렵다. 컴퓨터는 병행성이라는 주제가 아니더라도 충분히 어려운데, 불행하게도 이 문제 때문에 더 어려워진다.
훨씬 더 어려운 이유 : 데이터의 공유
앞의 간단한 쓰레드 예제를 통해 쓰레드의 생성 방법을 살펴보았고, 실행 순서는 스케줄러의 동작에 따라 바뀔 수 있다는 것을 보았다. 예제에서 나타나지 않은 부분은 쓰레드가 공유 데이터를 접근하기 위해 상호작용하는 과정이다.
그림 29.6에 나와 있는 코드를 사용하여 전역 공유 변수를 갱신하는 두 개의 쓰레드에 대한 간단한 예제를 살펴보자.
코드를 보기에 앞서 몇 가지 짚고 넘어가야 할 것이 있다. 첫 번째, 이 예제에서는 쓰레드를 생성하는 루틴과 조인하는 루틴이 실패할 경우 간단하게 종료하도록 래퍼 함수를 만들었다. 이 예제와 같이 간단한 프로그램은 에러 발생 여부만 관심이 있기에, 종료 외에 다른 처리는 하지 않는다. 그렇기 때문에 pthread_create()는 단순히 pthread_create()를 호출하고 리턴 값이 0인지 확인한다. 만약 0이 아니면 pthread_create()는 에러 메세지를 출력하고 종료한다.
두 번째, 작업자 쓰레드를 위해 두 개의 독립된 함수를 구성하는 대신 하나의 단일 코드를 사용하였다. 메세지를 출력하기 전에 각 쓰레드가 다른 문자를 출력하도록 쓰레드에게 문자열 인자를 전달하였다.
마지막으로, 그리고 가장 중요한 것은 각 작업자가 무엇을 하려는지 알 수 있다는 것이다. 각 작업자 쓰레드는 반복문 안에서 공유 변수인 counter에 수를 천만번(1e7) 더한다. 결과적으로 최종적으로 얻으려는 값은 20,000,000이다.
이제 프로그램을 컴파일하고 실행하여 결과를 확인해 보자. 때로는 실행 결과가 기대한 것과 같을 수도 있다.
하지만 여러 번 실행해본다면 각 실행이 잘못되었을 뿐만 아니라 각 실행의 결과 역시 다르다.
제어 없는 스케줄링
왜 이런 현상이 발생하는지 이해하려면 counter 갱신을 위해서 컴파잉러가 생성한 코드의 실행 순서를 이해해야 한다. 카운터에 단순히 1이라는 숫자를 더하려고 한다. x86에서 counter를 증가시키는 코드의 순서는 다음과 같다.
- mov 0x8049a1c, %eax
- add $0x1, %eax
- mov %eax, 0x8049a1c
이 예제에서 사용하는 counter 변수의 위치의 주소는 0x8049a1c라고 가정한다. 이 세 줄의 명령문에서는 먼저 x86의 mov 명령어가 명시한 메모리 주소의 값을 읽어 들인 후 eax 레지스터에 넣는다. 그리고 1 (0x1)을 eax 레지스터의 값에 더하는 연산을 한 후에 마지막으로 eax에 저장되어 있는 값을 메모리의 원래 주소에 다시 저장한다.
두 개의 쓰레드 중에 쓰레드 1이 counter를 증가시키는 코드 영역에 진입하여 counter의 값을 1 증가시키려는 상황을 가정해 보자. counter에 있는 값이 50이었다고 하면 50을 eax 레지스터에 넣는다. 쓰레드 1에 있어서 eax=50이 된다. 그 후에 레지스터의 값에 1을 더하여 eax=51이 된다. 이제 상황이 안 좋아진다. 타이머 인터럽트가 발생하여 운영체제가 실행 중인 쓰레드의 PC 값과 eax를 포함하는 레지스터들등의 현재 상태를 쓰레드의 TCB에 저장한다.
그리고는 상황이 더 악화된다. 쓰레드 2가 선택되고 counter 값을 증가시키는 똑같은 코드 영역에 진입한다. 첫 번째 명령어를 실행하여 counter 값을 얻어 온 후 eax에 넣는다. 쓰레드는 개별적으로 쓰레드 전용 레지스터를 가지고 있다. 사용 중이던 레지스터들은 저장하고 복구하는 문맥 교환 코드에 의해 이 레지스터들은 가상화된다. counter 값은 아직 50을 나타내고 있어서 쓰레드 2의 eax의 값은 50이다. 쓰레드 2가 그 다음의 두 문장을 실행한다면 eax 값을 1 증가시키고 (eax=51) 난 후에 eax 값을 counter에 저장한다. 전역 변수인 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
- add $0x1, %eax
- 108 mov %eax, 0x8049a1c
이러한 가정했을 때 일어나는 동작을 그림 29.7에 나타내었다. counter의 값은 50에서 시작한다고 가정하고 예제의 내용을 상기하며 흐름을 따라가 보자.
예시에서처럼 명령어의 실행 순서에 따라 결과가 달라지는 상황을 경쟁 조건(race condition)이라고 부른다. 문맥 교환이 때에 맞지 않게 실행되는 운이 없는 경우 잘못된 결과를 얻게 된다. 사실, 경쟁 조건에 처한 경우 실행할 때마다 다른 결과를 얻는다. 컴퓨터의 작동에서 일반적으로 발생하는 결정적 결과와 달리 결과가 어떠할지 알지 못하거나 실행할 때마다 결과가 다른 경우를 비결정적(indeterminate)인 결과라고 부른다.
멀티 쓰레드가 같은 코드를 실행할 때 경쟁 조건이 발생하기 때문에 이러한 코드 부분을 임계 영역(critical section)이라고 부른다. 공유 변수(또는 더 일반적으로는 공유 자원)를 접근하고 하나 이상의 쓰레드에서 동시에 실행되면 안 되는 코드를 임계 영역이라 부른다.
이러한 코드에서 필요한 것은 상호 배제(mutual exclusion)이다. 이 속성은 하나의 쓰레드가 임계 영역 내의 코드를 실행 중일 때는 다른 쓰레드가 실행할 수 없도록 보장해준다.
여담 : 주요 병행성 관련 용어
- 임계 영역 (critical section)은 보통 변수나 자료 구조와 같은 공유 자원을 접근하는 코드의 일부분을 말한다.
- 경쟁 조건 (race condition)은 멀티 쓰레드가 거의 동시에 임계 영역을 실행하려고 할 때 발생하며 공유 자료 구조를 모두가 갱신하려고 시도한다면 깜짝 놀랄 의도하지 않은 결과를 만든다.
- 비결정적 (indeterminate) 프로그램은 하나 또는 그 이상의 경쟁 조건을 포함하여 그 실행 결과가 각 쓰레드가 실행된 시점에 의존하기 때문에, 프로그램의 결과가 실행할 때마다 다르다. 결과는 컴퓨터 시스템에서 일반적으로 기대하는 바와 달리 결정적이지 않다.
- 이와 같은 문제들을 회피하려면 쓰레드는 상호 배제(mutual exclusion)라는 기법의 일종을 사용하여서 하나의 쓰레드만이 임계 영역에 진입할 수 있도록 보장한다. 그 결과로 경쟁을 피할 수 있고 프로그램 실행 결과를 결정론적으로 얻을 수 있게 된다.
원자성에 대한 바람
임계 영역 문제에 대한 해결 방법 중 하나로 강력한 명령어 한 개로 의도한 동작을 수행하여, 인터럽트 발생 가능성을 원천적으로 차단하는 것이다. 예를 들면 다음과 같은 강력한 명령어가 있다고 해 보자.
memory-add 0x8049a1c, $0x1
이 명령어는 메모리 상의 위치에 어떤 값을 더하는 명령어다. 하드웨어는 이 명령어가 원자적으로 실행되는 것을 보장한다고 하자. 이 명령어가 실행되면 원하는 것처럼 값이 갱신될 것이다. 하드웨어가 원자성을 보장해주기 때문에 명령어 수행 도중에 인터럽트가 발생하지 않는다. 인터럽트가 발생하더라도, 명령어가 실행이 안되었거나 실행이 종료된 후라는 것을 의미하고 그 중간 상태는 있을 수 없다. 멋진 하드웨어 아닌가?
문맥 상으로 원자적이라는 말은 “하나의 단위”를 뜻하며 때로는 “전부 아니면 전무”로 이해될 수도 있다. 다음의 세 개의 명령어가 원자적으로 실행되기를 원한다.
- mov 0x8049a1c, %eax
- add $0x1, %eax
- mov %eax, 0x8049a1c
언급했듯이, 위의 명령어들을 하나의 명령어로 대신할 수 있다면 그 명령어를 사용하면 그만이다. 하지만 일반적인 상황에서는 그러한 명령어가 없다고 봐야 한다. 병행성을 가지는 B-Tree를 만드는 중이고, 값을 갱신한다고 했을 때, 원자적으로 B-Tree를 갱신하는 어셈블리 명령어를 원할까? 글쎄, 아마도 제정신이라면 아니라고 본다.
하드웨어적으로는 동기화 함수(synchronization primitives) 구현에 필요한 기본적인 명령어 몇 개만 필요하다. 결과적으로 병행 실행이라는 어려운 상황에서 하드웨어 동기화 명령어와 운영체제의 지원을 통해 한 번에 하나의 쓰레드만 임계 영역에서 실행하도록 구성된, “제대로 잘 작동하는” 멀티 쓰레드 프로그램을 작성할 수 있다.
그렇다면 유용한 동기화 함수를 만들기 위해 어떤 하드웨어 지원이 필요한가? 운영체제는 어떤 지원을 해야 하는가? 어떻게 하면 이런 함수를 정확하고 효율적으로 만들 수 있을까? 프로그램들이 이 함수들을 활용하여 의도한 결과를 얻으려면 어떻게 해야 할까?
또 다른 문제 : 상대 기다리기
이제까지 병행성 문제를 공유 변수 접근에 관련된 쓰레드 간 상호 작용 문제로 정의하였다. 실제로는 하나의 쓰레드가, 다른 쓰레드가 어떤 동작을 끝낼 때까지 대기해야 하는 상황도 빈번하게 발생한다. 프로세스가 디스크 I/O를 요청하고 응답이 올 때까지 잠든 경우가 좋은 예이다. I/O 완료 후 잠들었던 프로세스가 깨어나 이후 작업을 진행한다.
이후에서는 원자성 지원을 위한 동기화 함수 제작에 대한 내용과 멀티 쓰레드 프로그램에서 흔한 잠자기/꺠우기 동작에 대한 지원 기법에 대해서 다룬다. 지금 이해가 가지 않더라도 괜찮다. 컨디션 변수(condition variable)에 대한 장을 읽을 때 즈음에는 이해가 될 것이다.
정리
- 쓰레드 (Thread) : 하나의 프로세스 내에서 실행되는 여러 흐름의 단위. 같은 프로세스 내의 다른 쓰레드와 주소 공간을 공유하지만, 자신만의 프로그램 카운터, 레지스터, 스택은 별도로 가진다.
- 문맥 교환 (Context Switch) : 하나의 쓰레드에서 다른 쓰레드로 CPU 제어권을 넘기는 과정이다. 프로세스 문맥 교환과 달리 주소 공간을 바꾸지 않아도 되므로 더 가볍고 빠르다.
- 임계 영역 (Critical Section) : 공유 자원(변수, 데이터 구조 등)에 접근하는 코드 영역이다. 두 개 이상의 쓰레드가 동시에 이 영역을 실행하면 문제가 발생할 수 있다.
- 경쟁 조건 (Race Condition) : 여러 쓰레드가 임계 영역에 동시에 접근해 조작할 때, 실행 순서나 타이밍에 따라 결과가 달라지는 현상이다. 이로 인해 프로그램의 결과가 예측 불가능해진다.
- 비결정적 (Indeterminate) : 경쟁 조건으로 인해 프로그램의 실행 결과가 매번 달라질 수 있는 상태를 의미한다.
- 상호 배제 (Mutual Exclusion) : 한 쓰레드가 임계 영역에 들어가 있다면, 다른 쓰레드는 들어갈 수 없도록 막는 속성이다. 경쟁 조건을 해결하기 위한 핵심 원칙이다.
- 원자성 (Atomicity) : 하나의 연산이 중간에 중단되지 않고 전부 실행되거나, 아예 실행되지 않거나를 보장하는 것이다. 임계 영역의 코드들이 원자적으로 실행된다면 경쟁 조건 문제는 해결된다.
- 동기화 함수 (Synchronization Primitives) : 상호 배제를 보장하고, 쓰레드 간의 실행 순서를 제어하기 위해 하드웨어나 운영체제가 제공하는 도구이다.
참고