OSTEP 26 - Concurrency and Thread

이번 장에서는 프로세스를 위한 새로운 개념인 쓰레드(Thread)를 소개한다. 멀티 쓰레드 프로그램은 하나 이상의 실행 지점을 가지고(독립적인 여러개의 PC값), 주소 공간을 공유할 수 있다.

프로세스가 문맥교환을 하고 정보를 저장하기 위해 PCB가 존재하듯이, 쓰레드도 TCB가 존재한다. 프로세스와의 가장 큰 차이는 역시 주소 공간을 공유한다는 것이다.

프로세스와 쓰레드의 더 큰 차이는 스택에 있다. 멀티 쓰레드 프로그램의 주소 공간에는 하나의 스택이 아니라 쓰레드마다 스택이 할당되어있다.

오른쪽은 두개의 쓰레드를 가지는 시스템의 주소공간이다.

스택에서 할당되는 변수들이나 매개변수, 리턴 값 등 스택에 넣는 정보들이 모두 쓰레드의 스택인 쓰레드-로컬 저장소(thread-local storage)에 저장된다.

그러나 스레드 로컬 저장소로 인해 정교한 주소 공간의 배치가 무너진다. 이전에는 주소 공간에 더이상 여유가 없을때만 문제가 생겼다. 이제는 예전만큼 상황이 깔끔하지는 않지만, 스택의 경우는 보통 크지 않아 대부분의 경우 문제가 되지 않는다.

1. 예제: 쓰레드 생성

“A”, “B”를 출력하는 독립적인 두개의 스레드를 실행해보자.

#include <stdio.h>
#include <assert.h>
#include <pthread.h>
#include "common.h"
#include "common_threads.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");
	pthread_create(&p1, NULL, mythread, "A");
	pthread_create(&p2, NULL, mythread, "B");
	// join waits for the threads to finish
	pthread_join(p1, NULL);
	pthread_join(p2, NULL);
	printf("main: end\n");
	return 0;
}

메인 프로그램은 mythread()를 실행할 두개의 스레드를 생성한다. 스케줄러의 동작에 따라 다르겠지만, 쓰레드가 생성되면, 즉시 실행될 수도 있고 준비(Ready) 상태에서 실행은 되지 않을 수도 있다.

두개의 쓰레드를 생성한 후, 메인 쓰레드는 pthread_join()을 호출하여 다른 쓰레드의 동작 종료를 기다린다.

코드가 더 앞에 있다고 더 먼저 실행되는 것이 보장되는게 아니다. 쓰레드의 실행 순서가 다양하게 존재할 수 있다. 스케줄링에 따라 “B”가 “A”보다 먼저 출력될 수도 있다.

쓰레드의 생성이 함수 호출과 유사하게 보인다. 함수 호출은, 함수 실행 후 caller에게 리턴한다. 그러나 쓰레드는 생성되고, 생성된 스레드는 호출자와 별개로 실행된다. 함수의 리턴 전에 스레드가 실행될 수도 있고, 그보다 이후에 실행될 수도 있다.

이를 통해, 쓰레드는 일을 더 복잡하게 만든다는 것을 알 수 있다.

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

아래 코드를 통해 전역 공유 변수를 갱신하는 두 개의 쓰레드 예시를 보자.

#include <stdio.h>
#include <pthread.h>
#include "ommon.h"
#include "common_threads.h"
static volatile int counter = 0;

// mythread()
// Simply adds 1 to counter repeatedly, in a loop
// No, this is not how you would add 10,000,000 to
// a counter, but it shows the problem nicely.

void *mythread(void *arg) {
	printf("%s: begin\n", (char *) arg);
	int i;
	for (i = 0; i < 1e7; i++) {
		counter = counter + 1;
	}
	printf("%s: done\n", (char *) arg);
	return NULL;
}

// main()
//
// Just launches two threads (pthread_create)
// and then waits for them (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 waits for the threads to finish
	pthread_join(p1, NULL);
	pthread_join(p2, NULL);
	printf("main: done with both (counter = %d)\n", counter);
	return 0;
}

mythread() 함수는 counter를 10,000,000번 더한다. 두 개의 쓰레드가 모두 실행된다면, 2천만이 나와야할 것이다.

1 prompt> gcc −o main main.c −Wall −pthread
2 prompt> ./main
3 main: begin (counter = 0)
4 A: begin
5 B: begin
6 A: done
7 B: done
8 main: done with both (counter = 20000000)

하지만 단일프로세서라고 하더라도 기대한 대로 결과가 나오지 않는다.

1 prompt> ./main
2 main: begin (counter = 0)
3 A: begin
4 B: begin
5 A: done
6 B: done
7 main: done with both (counter = 19345221)

한 번더 실행해도 이상하다.

1 prompt> ./main
2 main: begin (counter = 0)
3 A: begin
4 B: begin
5 A: done
6 B: done
7 main: done with both (counter = 19221041)

원하는 값이 나오지도 않았고, 실행의 결과도 다르다. 왜 그럴까?

3. 제어없는 스케줄링

왜 이런 현상이 발생하는지를 이해하려면 counter 갱신을 위해서 컴파일러가 생성한 코드의 실행 순서를 이해해야 한다. x86에서 counter를 증가하는 코드의 순서는 다음과 같다.

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

현재 counter는 50이 저장되어있다. 쓰레드 1이 그 값을 %eax에 반입하고 1을 더하는 연산을 완료한 시점(105)에 타이머 인터럽트가 발생했다. 이제 쓰레드 2에서 똑같은 연산을 시도하게 되면 50이라는 값을 읽게될 것이다. 그러면 스레드 1, 2가 모두 끝난 시점에 counter 값은 51이 될것이다.

정상적으로 동작하는 프로그램이라면 52가 되어야할 것이다.

이처럼, 명령어의 실행 순서에 따라 결과가 달라지는 상황을 race condition이라고 부른다. race condition 상황에서 실행할때마다 다른 결과를 가진다. 이를 비결정적이라고 한다.

멀티 쓰레드가 같은 코드를 실행할 때, 경쟁 조건이 발생하기 때문에 이러한 코드 부분을 임계 영역(critical section)이라고 부른다. 공유 자원에 접근할 때, 하나 이상의 쓰레드에서 동시에 실행되면 안되는 영역을 일컫는다.

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

4. 원자성에 대한 바람

임계 영역 문제의 해결 방안 중 하나는, 아주 강력한 명령어 한 개로 의도한 동작을 수행하여 인터럽트 발생 가능성을 원천적으로 차단하는 것이다.

memory−add 0x8049a1c, $0x1

이는 메모리 상에 어떤 값을 더하는 명령어이다. 하드웨어가 해당 명령의 원자성을 보장한다고 가정하면, 수행 중에 인터럽트가 발생하지 않고 원하는 값으로 변경될 것이다. 만약 인터럽트가 발생한다면, 명령어가 실행이 안된 상태거나 종료된 이후일 것이다.

원자적이라는 말은 “하나의 단위”를 뜻하며 “전부 아니면 전무”로 이해될 수도 있다.

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

이 세개의 명령어를 원자적으로 실행하고 싶다고 가정하자. 위 명령어들을 하나의 명령어로 대신할 수 있다면 좋겠지만 일반적으로는 불가능하다. 어셈블리에게 B-tree를 원자적으로 갱신하는 명령어가 필요할까? 놉!

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

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

이제까지는 병행성 문제를 공유 변수 접근에 관련된 쓰레드 간의 상호 작용 문제로 정의하였다. 하지만 실제로는 하나의 쓰레드가, 다른 쓰레드의 어떤 동작이 끝날 떄까지 대기해야하는 상황이 빈번하게 발생한다.

프로세스가 디스크 I/O를 요청하고 응답까지 잠든 경우가 좋은 예시이다. I/O 작업 완료 후 잠들었던 프로세스가 다시 깨어나 이후 작업을 진행한다.

6. 정리: 왜 운영체제에서?

왜 이런걸 운영체제에서 다루는걸까? 이것이 “역사” 이기 때문이다. 운영체제는 최초의 병행 프로그램이었고 운영체제 내에서 사용을 목적으로 다양한 기법들이 개발되었다. 나중에는 멀티 쓰레드 프로그램이 등장하면서 응용 프로그래머들도 이 문제를 고민하게 되었다.

시도 때도 없이 발생하는 인터럽트가 앞서 언급한 모든 문제들의 원인이다. 페이지 테이블, 프로세스 리스트, 파일 시스템 구조 그리고 대부분의 커널 자료 구조들이 올바르게 동작하기 위해서는 적절한 동기화 함수들을 사용해야 한다.