출처
Randal E. Bryant & David R. O'Hallaron. (2015). Computer Systems: A Programmer's Perspective (3rd ed.). Pearson.
7. 다른 동시성 이슈들
공유 데이터에 대한 접근을 동기화하려면 일이 많이 복잡해진다는 것을 느꼈을 것이다. 지금까지 mutual exclusion과 producer-consumer 동기화 기법을 살펴보았는데 이는 빙산의 일각일 뿐이다. 동기화는 기존의 순차적인 프로그램에서는 발생하지 않았던 이슈들을 발생시키는 근본적으로 어려운 문제이다. 이 절에서는 동시성 프로그램을 작성할 때 알아야 하는 몇 가지 이슈들을 살펴보려고 한다. 논의를 구체적으로 이어가기 위해서 스레드의 관점에서 논의를 이어갈 것이다. 하지만 이 이슈들은 공유 자원을 어떤 식으로든 조작하는 동시 흐름에서 발생하는 전형적인 이슈라는 점을 기억하라.
(1) 스레드 안전성
스레드와 함께 프로그래밍을 할 때 우리는 스레드 안전성이라는 속성을 가진 함수를 작성할 수 있도록 주의해야 한다. 여러 개의 동시성 서버에서 반복해서 호출됐을 때 항상 정확한 결과를 내는 함수를 thread-safe 함수라고 부른다. 그렇지 않은 함수는 thread-unsafe라고 한다.
우리는 thread-unsafe 함수를 다음과 같이 4가지 유형(서로 겹칠 수 있음)으로 나눠볼 수 있다.
유형 1 공유 변수를 보호하지 않는 함수
보호되지 않은 전역 카운터 변수를 증가시키는 함수가 예가 될 수 있다. 이 유형의 unsafe 함수는 상대적으로 thread-safe하게 만들기 쉽다. 공유 변수를 P와 V와 같은 동기화 연산으로 보호하면 된다. 이것의 이점은 호출 프로그램을 변경할 필요가 없다는 것이다. 단점은 동기화 연산이 함수의 속도를 늦춘다는 것이다.
유형 2 여러 개의 호출에 걸쳐 상태를 유지하는 함수
pseduorandom 숫자 생성기는 이 유형의 간단한 예시이다.
#include <stdio.h>
unsigned next_seed = 1;
/* rand - return pseudorandom integer in the range 0..32767 */
unsigned rand(void)
{
next_seed = next_seed*1103515245 + 12543;
return (unsigned)(next_seed>>16) % 32768;
}
/* srand - set the initial seed for rand() */
void srand(unsigned new_seed)
{
next_seed = new_seed;
}
int main()
{
srand(100);
printf("%d\n", rand());
printf("%d\n", rand());
printf("%d\n", rand());
return 0;
}
rand 함수는 thread-unsafe한 함수이다. 왜냐하면 현재 호출의 결과가 이전 반복해서의 중간 결과에 의존적이기 때문이다. srand로의 호출을 통해 seeding을 하고 나서 단일 스레드에서 rand를 반복적으로 호출하면 반복적인 순열을 기대할 수 있다. 하지만 이 가정은 여러 개의 스레드가 rand를 호출할 때는 유지될 수 없다.
이 함수를 thread-safe하게 만드는 유일한 방법은 다시 작성하여 아무 static 데이터를 쓰지 않게 하고 호출자가 인자로 state 정보를 전달하도록 하는 것이다. 이것의 단점은 개발자가 호출 루틴의 코드를 바꿔야 한다는 것이다. 수백 개의 호출 지점을 가진 큰 프로그램의 경우 이는 사소하지 않은 문제가 될 수 있고 에러에 취약하게 만들 수 있다.
유형 3 static 변수에 대한 포인터를 리턴하는 함수
ctime이나 gethostbyname과 같은 함수들은 연산 결과를 static 변수에 저장한 다음 이에 대한 포인터를 리턴한다. 만약 우리가 이러한 함수를 동시성 스레드에서 호출한다면 재앙이 찾아올 것이다. 하나의 스레드가 사용하고 있는 결과가 다르 스레드에 의해 조용하게 덮어쓰여질 수 있기 때문이다.
이 유형을 다룰 수 있는 두 가지 방법 중 첫 번재는 함수를 다시 작성하여 호출자가 변수의 주소를 전달하는 것이다. 이는 모든 공유 데이터를 제거하지만 개발자가 소스 코드 함수에 대한 접근을 가져야 한다.
만약 함수 변경이 어렵다면 (예를 들어 코드가 너무 복잡하거나 소스 코드가 이용 가능하지 않다면) 다른 방법은 lock-and-copy 기술을 이용하는 것이다. 기본 아이디어는 mutex를 이용하는 것이다. 모든 호출 지점에서 mutex로 lock을 건 다음에 thread-unsafe 함수를 호출하고 함수에 의해 리턴된 결과를 사적 메모리 위치에 복사하고 mutex를 unlock한다. 호출자에서 변화를 최소화하기 위해 당신은 이러한 작업을 하는 thread-safe 함수의 wrapper 함수를 정의해서 wrapper 함수를 호출하는 것으로 기존 함수 호출을 대체해야 할 것이다.
#include "csapp.h"
#define MAXSTR 128
static sem_t mutex; /* protects calls to ctime */
static void init_ctime_ts(void)
{
Sem_init(&mutex, 0, 1);
}
/* $begin ctime_ts */
char *ctime_ts(const time_t *timep, char *privatep)
{
char *sharedp;
P(&mutex);
sharedp = ctime(timep);
strcpy(privatep, sharedp); /* Copy string from shared to private */
V(&mutex);
return privatep;
}
/* $end ctime_ts */
int main()
{
char timestr[MAXSTR];
time_t timeval;
/* Thread-safe code to print the current time string */
init_ctime_ts();
timeval = time(NULL);
ctime_ts(&timeval, timestr);
printf("%s", timestr);
exit(0);
}
유형 4 thread-unsafe 함수를 호출하는 함수
만약 함수 f가 thread-unsafe 함수 g를 호출한다면 f는 thread-unsafe일까? 때에 따라 다르다. 만약 g가 여러 호출에 걸친 state에 의존하는 유형 2에 해당하는 함수라면 g를 다시 작성해야 한다. 하지만 g가 유형 1이나 3에 해당한다면 호출 지점과 최종 공유 데이터를 mutex를 잘 보호한다면 f는 여전히 thread-safe할 수 있다. 위 코드가 바로 그런 예시이다.
(2) Reentrancy
thread-safe 함수의 중요한 유형으로 reentrant 함수가 있다. 이는 여러 개의 스레드에 의해 호출될 때 아무 공유 데이터도 참조하지 않는 특성을 가진 함수이다. 비록 thread-safe와 reentrant라는 말은 동의어처럼 쓰이기도 하지만 기술적으로 분명한 차이가 있다. 아래 표에서 집합 관계를 확인할 수 있다. 모든 함수는 thread-safe와 thread-unsafe라는 서로소 집합으로 나누어질 수 있고 reentrant 함수는 thread-safe 함수의 하위 집합이다.
reentrant 함수는 일반적으로 그렇지 않은 thred-safe 함수보다 더 효율적이다. 왜냐하면 동기화 연산이 필요없기 때문이다. 유형 2의 thread-unsafe 함수를 thread-safe하게 변경하는 유일한 방법은 이를 reentrant하게 재작성하는 방법밖에 없다. 예를 들어, 다음은 rand 함수의 reentrant 버전이다. 핵심은 static한 next 변수를 호출자에 의해 전달되는 포인터로 대체한 것이다.
#include <stdio.h>
#include <stdlib.h>
/* rand_r - return pseudorandom integer on 0..32767 */
int rand_r(unsigned int *nextp)
{
*nextp = *nextp * 1103515245 + 12345;
return (unsigned int)(*nextp / 65536) % 32768;
}
int main()
{
unsigned int next = 1;
printf("%d\n", rand_r(&next));
printf("%d\n", rand_r(&next));
printf("%d\n", rand_r(&next));
exit(0);
}
어떤 코드를 분석하여 미리 그것이 reentrant하다는 것을 알 수 있을까? 안타깝게도 때에 따라 다르다. 만약 함수의 모든 인자들이 값으로 전달되었다면(포인터가 아님) 그리고 모든 데이터 참조가 local automatic stack variable(static 또는 공유 변수에 대한 참조하지 않음) 이라면 그 함수는 명시적으로 재진입 가능하다. 그것이 어떻게 호출되든 그것의 reentrancy를 확고히 할 수 있기 때문이다.
하지만 하지만 만약 일부 매개변수를 참조로 전달(즉, 포인터를 허용)하도록 허용한다면, 그 함수는 묵시적 재진입 함수가 된다. 즉, 호출하는 스레드들이 공유되지 않은 데이터의 포인터를 전달하는 경우에만 재진입 가능하다. 예를 들어, rand_r 함수는 묵시적 재진입 함수의 예시이다. 우리는 일반적으로 reentrancy 라는 용어를 명시적 및 묵시적 재진입 함수를 모두 포함하는 의미로 사용한다. 그러나 중요한 점은, 재진입 가능성은 때때로 호출된 함수뿐만 아니라 호출하는 함수의 특성에도 의존할 수 있다는 것을 기억하는 것은 중요하다.
(3) 스레드 프로그램에서 이미 존재하는 라이브러리 함수 이용하기
대부분의 Linux 함수들, 표준 C 라이브러리에 정의된 malloc, free, realloc, printf, scanf 등은 thread-safe한데 예외도 있다. 다음은 thread-unsafe 함수의 예이다.
strtok 함수는 문자열을 파싱할 때 사용되는 함수인제 이제는 사용이 권장되지 않는 deprecated 함수이다. asctime, ctime, localtime은 서로 시간과 데이터 형식 사이에서 변환을 수행하는 함수이다. gethostbyaddr, gethostbyname, inet_ntoa 함수는 재진입 가능한 getaddrinfo, getnameinfo, inet_ntop로 대체된 옛날 네트워크 프로그래밍 함수이다. rand와 strtok를 제외하면 이들은 static 변수에 대한 포인터를 리턴하는 유형 3의 thread-unsafe 함수이다. 만약 우리가 스레드 프로그램에서 이 함수들을 호출해야 한다면 호출자에게 최소한의 지장으로 접근할 수 있는 방법은 lock and copy를 이용하는 것이다. 하지만 lock and copy 방법은 많은 단점을 가진다. 첫째, 추가적인 동기화는 프로그램의 속도를 늦춘다. 둘째, 복잡한 구조체의 구조체를 가리키는 포인터를 리턴하는 함수는 전체 구조체 계층을 복사하기 위해 deep copy가 요구된다. 셋째, lock-and-copy 접근 방법은 여러 호출에 걸쳐 static한 상태에 의존하는 rand와 같은 융형 2의 thread-unsafe 함수에는 적용할 수 없다.
따라서 Linux 시스템은 대부분의 thread-unsafe 함수에 대해 reentrant한 버전을 제공한다. reentrant한 버전의 이름은 항상 _r 접미사로 끝난다. 예를 들어, asctime의 재진입 가능 버전의 이름은 asctime_r이다. 가능하다면 이런 함수들을 이용할 것을 권장하다.
(4) 경쟁 상태 race
경쟁 상태는 프로그램의 정확성이 한 스레드가 제어 흐름에서 지점 X에 도달하기 전에 다른 스레드가 지점 Y에 도달해야 한다는 조건에 의존할 때 발생한다. 경쟁 상태는 보통 프로그래머가 스레드가 어떤 실행 경로(trajectory)를 따르더라도 올바르게 동작해야 한다는 황금 규칙(golden rule) 을 잊고서 특정한 실행 흐름이 보장될 것이라고 가정하는 데서 비롯된다.
경쟁 상태를 이해하는 가장 쉬운 방법은 예제를 살펴보는 것이다. 예를 들어, 다음 프로그램을 보자. 이 프로그램에서 메인 스레드는 네 개의 peer thread를 생성하고, 각 스레드에 고유한 정수 ID의 포인터를 전달한다. 각 peer thread는 인자로 전달받은 ID를 복사하여 지역 변수에 저장하고 ID를 포함한 메시지를 출력한다. 이는 간단해보이지만 프로그램을 실행해보면 부정확한 결과가 나온다.
/* WARNING: This code is buggy! */
#include "csapp.h"
#define N 4
void *thread(void *vargp);
int main()
{
pthread_t tid[N];
int i;
for (i = 0; i < N; i++)
Pthread_create(&tid[i], NULL, thread, &i);
for (i = 0; i < N; i++)
Pthread_join(tid[i], NULL);
exit(0);
}
/* Thread routine */
void *thread(void *vargp)
{
int myid = *((int *)vargp);
printf("Hello from thread %d\n", myid);
return NULL;
}
이 문제는 각 peer thread와 메인 스레드 사이의 경쟁 상태(race condition) 에 의해 발생한다. 경쟁 상태가 발생하는 부분이 어디인지 찾을 수 있는가? 여기서 일어난 일은 다음과 같다. 메인 스레드는 동료 스레드를 생성할 때, 지역 스택 변수 i의 포인터를 전달한다. 이 순간, 메인 스레드에서 i를 증가시키는 연산과 peer thread에서 해당 포인터를 역참조하여 값을 할당하는 연산 사이에서 경쟁 상태가 발생한다. 만약 peer thread가 먼저 실행하면, myid 변수는 올바른 ID를 갖는다. 하지만, 메인 스레드가 먼저 실행하면, myid 변수는 다른 스레드의 ID를 가지게 된다.
더 무서운 점은, 결과가 커널의 스레드 스케줄링 방식에 따라 달라진다는 것이다. 예를 들어, 어떤 시스템에서는 이 코드가 실패하지만, 다른 시스템에서는 운 좋게 정상적으로 동작할 수도 있다. 이 경우, 프로그래머는 심각한 버그가 존재한다는 사실도 모른 채 코드가 잘 작동한다고 착각할 위험이 있다.
경쟁 상태를 해결하려면, 각 ID를 저장할 별도의 동적 메모리 블록을 할당하고, 스레드 함수에 해당 블록의 포인터를 전달해야 한다. 다음은 이 방법을 적용한 코드이다. 또한, 스레드 함수가 해당 메모리 블록을 해제해야 메모리 누수를 방지할 수 있다.
#include "csapp.h"
#define N 4
void *thread(void *vargp);
int main()
{
pthread_t tid[N];
int i, *ptr;
for (i = 0; i < N; i++) {
ptr = Malloc(sizeof(int));
*ptr = i;
Pthread_create(&tid[i], NULL, thread, ptr);
}
for (i = 0; i < N; i++)
Pthread_join(tid[i], NULL);
exit(0);
}
/* Thread routine */
void *thread(void *vargp)
{
int myid = *((int *)vargp);
Free(vargp);
printf("Hello from thread %d\n", myid);
return NULL;
}
(5) 데드락 Deadlocks
세마포어는 deadlock이라고 불리는 치명적인 런타임 오류의 가능성을 가져온다. deadlock은 스레드의 집합이 블록된 상태에서 절대로 참이 될 수 없는 조건을 위해 기다리는 것을 말한다. deadlock을 이해할 때 progress graph는 중요한 도구이다. 예를 들어, 다음은 mutual exclusion을 위해 두 개의 세마포어를 쓰는 두 개의 스레드의 process graph이다. 여기 우리는 deadlock에 대한 중요한 통찰을 얻을 수 있다.
- 프로그래머가 P 와 V 연산의 순서를 잘못 배치하여 두 세마포어의 forbidden region이 겹치게 되었다. 만약 어떤 실행 경로가 교착 상태 d에 도달하면, 두 세마포어의 겹친 금지 영역이 모든 합법적인 진행 방향을 막아 더 이상 진행할 수 없게 된다. 즉, 프로그램이 교착 상태에 빠지는 이유는 각 스레드가 상대방이 V 연산을 수행하기를 기다리지만 그런 일이 절대 발생하지 않기 때문이다.
- 이러한 겹치는 금지 영역은 교착 상태 영역(deadlock region)을 형성한다. 만약 실행 경로가 이 교착 상태 영역에 도달하면, 데드락은 불가피하다. 실행 경로는 교착 상태 영역에 들어갈 수 있지만, 한 번 들어가면 다시 나올 수 없다.
- 교착 상태는 특히 다루기 어려운 문제인데, 그 이유는 언제나 예측 가능한 것이 아니기 때문이다. 어떤 운 좋은 실행 경로는 교착 상태 영역을 피해 정상적으로 실행될 수도 있지만, 다른 실행 경로는 교착 상태에 갇힐 수도 있다. 예를 들어, 같은 프로그램을 천 번 실행시켜도 문제가 없다가 다음에 데드락이 될 수 있다. 어떤 머신에서는 잘 작동해도 다른 머신에서는 데드락이 될 수 있다. 가장 최악인 것은 실행할 때마다 다른 실행 경로를 가지기 때문에 에러가 반복적으로 나타나지 않는다는 것이다.
프로그램은 다양한 이유로 교착 상태에 빠지며 이를 예방하는 것은 일반적으로 어려운 문제이다. 하지만 mutual exclusion을 위해 binary semaphore가 사용된다. 그리고 데드락을 예방하기 위하여 다음과 같은 간단하고 효율적인 규칙을 적용할 수 있다.
Mutex locking rule: 모든 mutex의 전체 순서가 있을 때 각각의 스레드가 mutex를 순서대로 얻고 그것을 반대 순서로 해제하면 프로그램은 데드락으로부터 안전한다.
예를 들어, 각 스레드에서 s를 먼저 lock한 다음 t를 lock하는 것이다. 다음은 이것의 progress graph를 보여준다.
