[JUNGLE] TIL_52. CSAPP 12장 끝!

모깅·2025년 11월 3일

jungle

JUNGLE

목록 보기

53/56

12.5 세마포를 이용한 스레드 동기화

공유 변수는 편리하지만, 동기화 오류(synchronization errors)라는 고약한 문제를 일으킬 가능성을 도입합니다.

Figure 12.16의 badcnt.c 프로그램을 살펴봅시다. 이 프로그램은 두 개의 스레드를 생성하며, 각 스레드는 cnt라는 전역 공유 카운터 변수를 증가시킵니다.

각 스레드가 카운터를 niters 번씩 증가시키므로, 우리는 최종값이 $2 \times \text{niters}$ 가 될 것으로 기대합니다. 이는 매우 간단하고 명확해 보입니다.

하지만 리눅스 시스템에서 badcnt.c를 실행하면, 틀린 답이 나올 뿐만 아니라 실행할 때마다 다른 답이 나옵니다!

linux> ./badcnt 1000000
BOOM! cnt=1445085
linux> ./badcnt 1000000
BOOM! cnt=1915220
linux> ./badcnt 1000000
BOOM! cnt=1404746

문제의 원인: 원자성(Atomic)이 깨진 연산

무엇이 잘못된 것일까요? 이 문제를 명확히 이해하려면, Figure 12.17에 나온 카운터 루프(lines 40–41)의 어셈블리 코드를 살펴봐야 합니다.

핵심은 C 코드 한 줄인 cnt++가 실제로는 단일 명령어가 아니라는 것입니다. 스레드 $i$ 의 루프 코드를 5개 부분으로 나눌 수 있습니다.

$H_i$ (Head): 루프의 시작 부분 (지역 변수 조작)
$L_i$ (Load): 공유 변수 cnt를 스레드 $i$ 의 레지스터 %rdx_i로 불러오는 명령어.
$U_i$ (Update): 레지스터 %rdx_i의 값을 수정(증가)하는 명령어.
$S_i$ (Store): 수정된 %rdx_i의 값을 다시 공유 변수 cnt에 저장하는 명령어.
$T_i$ (Tail): 루프의 끝 부분 (지역 변수 조작)

여기서 $H_i$ 와 $T_i$ 는 지역 스택 변수만 다루지만, $L_i$ , $U_i$ , $S_i$ 는 공유 카운터 변수 cnt의 내용을 조작합니다.

명령어 순서(Interleaving) 문제

두 스레드가 동시에 실행될 때, 기계어 명령어들은 어떤 순서로든 차례대로(interleaving, 뒤섞여서) 완료됩니다. 불행히도, 이 순서 중 일부는 올바른 결과를 생성하지만, 다른 순서들은 그렇지 않습니다.

여기서 핵심은 이것입니다: 일반적으로 프로그래머는 운영체제가 스레드에 대해 올바른 순서를 선택할지 예측할 방법이 없습니다.

(a) 올바른 순서 (Correct ordering, Figure 12.18a)

스레드 1이 L_1 (0 로드), U_1 (1로 증가), S_1 (1 저장)을 순서대로 실행합니다.
(이때 cnt의 메모리 값은 1이 됩니다.)
스레드 2가 L_2 (1 로드), U_2 (2로 증가), S_2 (2 저장)를 순서대로 실행합니다.
(이때 cnt의 메모리 값은 2가 됩니다.)
결과: cnt = 2 (정상)

(b) 잘못된 순서 (Incorrect ordering, Figure 12.18b)

(스레드 1): L_1 (레지스터 %rdx_1에 0을 로드)
(스레드 1): U_1 (레지스터 %rdx_1을 1로 증가)
(스레드 2): L_2 (메모리의 cnt는 아직 0이므로, 레지스터 %rdx_2에 0을 로드)
(스레드 1): S_1 (자신의 레지스터 값 1을 cnt에 저장. cnt = 1)
(스레드 2): U_2 (자신의 레지스터 %rdx_2를 1로 증가)
(스레드 2): S_2 (자신의 레지스터 값 1을 cnt에 저장. cnt = 1)
결과: cnt = 1 (오류!)

이 문제는 스레드 2가 cnt를 로드(Step 5)할 때, 스레드 1이 cnt를 로드(Step 2)한 후이면서, 스레드 1이 수정된 값을 저장(Step 6)하기 전에 발생했습니다.

결국, 두 스레드 모두 업데이트된 카운터 값으로 1을 저장하게 됩니다. (즉, 스레드 1의 작업이 무시됩니다.)

12.5.1 진행 그래프 (Progress Graphs)

진행 그래프(Progress graph)는 $n$ 개의 동시성 스레드 실행을 $n$ 차원 데카르트 공간의 경로(trajectory)로 모델링하는 도구입니다.
각 축 $k$ 는 스레드 $k$ 의 진행 상태를 나타냅니다.
각 점 $(I_1, I_2, ..., I_n)$ 은 스레드 $k$ 가 명령어 $I_k$ 를 완료했음을 나타내는 상태입니다.
원점은 어떤 스레드도 아직 명령어를 완료하지 않은 초기 상태입니다.

(Figure 12.19는 badcnt.c의 두 스레드를 2차원 그래프로 보여줍니다. $x$ 축은 스레드 1, $y$ 축은 스레드 2입니다.)

실행 경로 (Trajectory)

진행 그래프는 명령어 실행을 한 상태에서 다른 상태로의 전이(transition)로 모델링합니다.

합법적 전이 (Legal transitions):
- 오른쪽으로 이동: 스레드 1이 명령어 하나를 완료함.
- 위쪽으로 이동: 스레드 2가 명령어 하나를 완료함.
불법적 전이 (Illegal transitions):
- 대각선 이동: 두 명령어가 동시에 완료될 수 없습니다.
- 아래쪽/왼쪽 이동: 프로그램은 거꾸로 실행되지 않습니다.

프로그램의 실행 히스토리는 이 상태 공간을 통과하는 하나의 경로(trajectory)로 모델링됩니다. (Figure 12.20은 특정 명령어 순서에 해당하는 경로를 보여줍니다.)

임계 구역과 상호 배제

스레드 $i$ 에서, 공유 변수 cnt의 내용을 조작하는 명령어들( $L_i$ , $U_i$ , $S_i$ )은 임계 구역(critical section)을 구성합니다.

이 임계 구역은 다른 스레드의 임계 구역과 뒤섞여서(interleaved) 실행되어서는 안 됩니다.
즉, 각 스레드가 자신의 임계 구역을 실행하는 동안 공유 변수에 대한 상호 배타적인 접근(mutually exclusive access)을 보장해야 합니다. 이 현상을 일반적으로 상호 배제(mutual exclusion)라고 합니다.

위험 영역 (Unsafe Region)

진행 그래프 상에서, 두 임계 구역이 교차(intersection)하는 영역은 위험 영역(unsafe region)이라고 알려진 상태 공간 영역을 정의합니다.

Figure 12.21은 cnt 변수에 대한 위험 영역을 보여줍니다.
(참고: 위험 영역의 경계선(perimeter)은 위험 영역에 포함되지 않습니다.)
안전한 경로 (Safe Trajectory): 위험 영역을 비껴가는 경로입니다.
안전하지 않은 경로 (Unsafe Trajectory): 위험 영역의 어떤 부분이라도 건드리는 경로입니다.
- (Figure 12.18b의 "잘못된 순서"가 바로 이 위험 영역을 통과하는 경로에 해당합니다.)

동기화의 목표

안전한 경로만이 공유 카운터를 올바르게 업데이트합니다.

공유 데이터를 사용하는 동시성 프로그램의 올바른 실행을 보장하려면, 스레드들이 항상 안전한 경로를 갖도록 스레드들을 어떻게든 동기화(synchronize)해야 합니다.

(이를 위한 고전적인 접근 방식이 바로 다음에 소개할 '세마포'입니다.)

12.5.2 세마포어 (Semaphores)

동시성 프로그래밍의 선구자인 에츠허르 다익스트라(Edsger Dijkstra)는 세마포어(semaphore)라는 특별한 타입의 변수에 기반한, 서로 다른 실행 스레드를 동기화하는 고전적인 해법을 제안했습니다.

세마포어 $s$ 는 음이 아닌 정수 값을 갖는 전역 변수이며, 오직 다음과 같은 두 가지 특별한 연산, P와 V에 의해서만 조작될 수 있습니다.

P(s):
- 만약 $s$ 가 0이 아니면(non-zero), $P$ 는 $s$ 를 1 감소시키고 즉시 리턴합니다.
- 만약 $s$ 가 0이면, $s$ 가 0이 아닌 값이 될 때까지 (그리고 $V$ 연산에 의해 스레드가 재시작될 때까지) 스레드를 일시 중단(suspend)시킵니다.
- 스레드가 재시작된 후, $P$ 연산은 $s$ 를 1 감소시키고 제어권을 호출자에게 반환합니다.
V(s):
- $V$ 연산은 $s$ 를 1 증가시킵니다.
- 만약 $s$ 가 0이 되기를 기다리며 $P$ 연산에서 블록(block)된 스레드들이 있다면, $V$ 연산은 이 스레드들 중 정확히 하나를 재시작시킵니다.
- 재시작된 스레드는 $s$ 를 1 감소시키며 자신의 $P$ 연산을 완료합니다.

원자성(Indivisibility) 및 중요 속성

$P$ 연산에서의 "검사(test)"와 "감소(decrement)"는 불가분(indivisibly, 원자적으로) 일어납니다. 즉, 일단 세마포 $s$ 가 0이 아닌 값이 되면, $s$ 의 감소는 어떠한 중단(interruption) 없이 발생합니다. $V$ 연산에서의 "증가" 역시 (값을 불러오고, 증가시키고, 저장하는 과정이) 중단 없이 불가분하게 일어납니다.

$V$ 의 정의는 대기 중인 스레드가 어떤 순서로 재시작될지 정의하지 않는다는 점에 유의해야 합니다. 유일한 요구 사항은 $V$ 가 정확히 하나의 대기 중인 스레드를 재시작해야 한다는 것입니다. 따라서 여러 스레드가 세마포에서 대기 중일 때, $V$ 연산의 결과로 어떤 스레드가 재시작될지 예측할 수 없습니다.

$P$ 와 $V$ 의 정의는, 올바르게 초기화된 세마포 값이 실행 중에 절대 음수(-)가 될 수 없음을 보장합니다. 이 속성은 세마포 불변성(semaphore invariant)이라고 알려져 있으며, 다음 섹션에서 보게 될 것처럼 동시성 프로그램의 경로(trajectories)를 제어하는 강력한 도구를 제공합니다.

Posix 세마포 함수

Posix 표준은 세마포를 조작하기 위한 다양한 함수를 정의합니다.

#include <semaphore.h>

int sem_init(sem_t *sem, 0, unsigned int value);
int sem_wait(sem_t *s); /* P(s) */
int sem_post(sem_t *s); /* V(s) */

// 성공 시 0, 오류 시 -1 반환

sem_init 함수는 세마포 sem을 value 값으로 초기화합니다. 각 세마포는 사용되기 전에 반드시 초기화되어야 합니다. (우리의 목적상 가운데 인자는 항상 0입니다.)

프로그램은 sem_wait 함수와 sem_post 함수를 호출하여 각각 P 연산과 V 연산을 수행합니다. (CSAPP에서는 간결함을 위해, 이 함수들을 감싼 다음과 같은 래퍼(wrapper) 함수를 사용할 것입니다.)

#include "csapp.h"

void P(sem_t *s); /* sem_wait의 래퍼 함수 */
void V(sem_t *s); /* sem_post의 래퍼 함수 */
// (리턴값 없음)

12.5.3 상호 배제를 위해 세마포 사용하기

세마포는 공유 변수에 대한 상호 배타적인 접근(mutually exclusive access)을 보장하는 편리한 방법을 제공합니다. 기본 아이디어는 각 공유 변수(또는 연관된 변수 집합)에 대해 초기값이 1인 세마포 $s$ 를 하나씩 연관시키고, 해당 임계 구역(critical section)을 P(s)와 V(s) 연산으로 감싸는 것입니다.

용어 정리

이진 세마포 (Binary Semaphore): 공유 변수를 보호하기 위해 이런 식으로 사용되는 세마포를 말합니다. 값은 항상 0 또는 1입니다.
뮤텍스 (Mutex): 상호 배제(Mutual Exclusion)를 제공하는 것이 목적인 이진 세마포를 종종 뮤텍스라고 부릅니다.
Locking (잠금): 뮤텍스에 P 연산을 수행하는 것.
Unlocking (해제): V 연산을 수행하는 것.
Holding (보유): 락을 획득(lock)했지만 아직 해제(unlock)하지 않은 스레드를 "뮤텍스를 보유(holding)하고 있다"고 말합니다.
카운팅 세마포 (Counting Semaphore): (이진 세마포와 달리) 가용 자원 집합의 '개수'를 세는 카운터로 사용되는 세마포입니다.

진행 그래프로 이해하기 (Figure 12.22)

Figure 12.22의 진행 그래프는 이진 세마포를 사용하여 카운터 프로그램을 올바르게 동기화하는 방법을 보여줍니다.

각 상태는 그 상태에서의 세마포 $s$ 의 값을 함께 표시합니다.

여기서 핵심 아이디어는, P와 V 연산의 조합이 $s < 0$ 이 되는 상태의 집합, 즉 "금지된 영역(forbidden region)"을 생성한다는 것입니다.

"세마포 불변성"(세마포 값은 절대 음수가 될 수 없음) 때문에, 실행 가능한 어떠한 경로(trajectory)도 이 "금지된 영역"에 포함된 상태를 가질 수 없습니다.

그리고 이 "금지된 영역"이 (경쟁 상태가 발생하는) "위험 영역(unsafe region)"을 완전히 둘러싸고 있습니다.

결과적으로, 실행 가능한 모든 경로는 "금지된 영역"을 피해서 가야 하므로, "위험 영역" 또한 자동으로 피하게 됩니다. 따라서 모든 실행 경로는 "안전한 경로(safe trajectory)"가 되며, 런타임 시 명령어 순서가 어떻게 되든 관계없이 프로그램은 카운터를 올바르게 증가시킵니다.

운영 관점에서, P와 V 연산이 만든 "금지된 영역"은 여러 스레드가 동시에 "위험 영역" 안의 임계 구역 명령어를 실행하는 것을 불가능하게 만듭니다. 즉, 세마포 연산이 임계 구역에 대한 상호 배타적인 접근을 보장합니다.

`badcnt.c` 수정하기 (goodcnt.c)

요약하자면, Figure 12.16의 예제 카운터 프로그램을 세마포를 사용해 올바르게 동기화하려면, 먼저 mutex라는 세마포를 선언합니다.

volatile long cnt = 0; /* 카운터 */
sem_t mutex;           /* 카운터를 보호할 세마포 */

그리고 main 루틴에서 이 세마포를 1로 초기화합니다.

Sem_init(&mutex, 0, 1); /* mutex = 1 */

마지막으로, 스레드 루틴에서 공유 변수 cnt를 업데이트하는 부분을 P와 V 연산으로 감싸줍니다.

for (i = 0; i < niters; i++) {
    P(&mutex);
    cnt++;
    V(&mutex);
}

이렇게 올바르게 동기화된 프로그램을 실행하면, 이제 매번 정확한 결과가 나옵니다.

linux> ./goodcnt 1000000
OK cnt=2000000
linux> ./goodcnt 1000000
OK cnt=2000000

부가 설명: 진행 그래프의 한계

진행 그래프(Progress graph)는 단일 프로세서(uniprocessor)에서의 동시성 프로그램 실행을 시각화하고, 왜 동기화가 필요한지 이해하는 데 좋은 방법을 제공합니다.

하지만 이 그래프는 한계가 있습니다. 특히 멀티프로세서(multiprocessor) (여러 CPU/캐시 쌍이 동일한 메인 메모리를 공유하는 환경)에서의 동시 실행을 설명하는 데 한계가 있습니다.

멀티프로세서는 진행 그래프로 설명할 수 없는 방식으로 동작합니다. 구체적으로, 멀티프로세서 메모리 시스템은 진행 그래프 상의 어떤 경로(trajectory)에도 해당하지 않는 상태에 있을 수 있습니다.

그럼에도 불구하고, 결론은 동일합니다:

단일 프로세서에서 실행하든, 멀티프로세서에서 실행하든 상관없이, 공유 변수에 대한 접근은 항상 동기화해야 합니다.

12.5.4 공유 자원 스케줄링을 위해 세마포 사용하기

상호 배제를 제공하는 것 외에, 세마포의 또 다른 중요한 용도는 공유 자원에 대한 접근을 스케줄링(scheduling)하는 것입니다.

이 시나리오에서, 한 스레드는 프로그램의 어떤 상태 조건이 참(true)이 되었음을 다른 스레드에게 알리기 위해(notify) 세마포 연산을 사용합니다.

이에 대한 고전적이고 유용한 두 가지 예시로 생산자-소비자(producer-consumer) 문제와 읽기-쓰기(readers-writers) 문제가 있습니다.

1. 생산자-소비자 문제 (Producer-Consumer Problem)

이 문제는 n개의 슬롯을 가진 공유 유한 버퍼(bounded buffer)를 생산자(Producer) 스레드와 소비자(Consumer) 스레드가 공유하는 상황을 다룹니다.

생산자: 새 아이템을 반복적으로 생성하여 버퍼에 삽입합니다.
소비자: 버퍼에서 아이템을 반복적으로 제거하여 사용합니다.

동기화 요구사항

이 문제를 해결하기 위해서는 두 가지 동기화가 필요합니다.

상호 배제 (Mutual Exclusion): 버퍼 자체(예: front, rear 인덱스)를 수정하는 작업은 원자적(atomic)으로 일어나야 합니다.
스케줄링 (Scheduling):
- 버퍼가 가득 차면 (슬롯 0개): 생산자는 빈 슬롯이 생길 때까지 대기(wait)해야 합니다.
- 버퍼가 비어있으면 (아이템 0개): 소비자는 새 아이템이 생길 때까지 대기(wait)해야 합니다.

(예: 멀티미디어 인코더(생산자)와 디코더(소비자), GUI의 이벤트 탐지(생산자)와 화면 그리기(소비자))

Sbuf 패키지: 세마포 3개를 이용한 해결책

Figure 12.24와 12.25의 Sbuf 패키지는 이 문제를 세 개의 세마포를 이용해 우아하게 해결합니다.

sbuf_t 구조체는 다음 3개의 세마포를 가집니다.

mutex (뮤텍스): (초기값: 1) 버퍼 접근에 대한 상호 배제를 보장하는 이진 세마포입니다.
slots (슬롯): (초기값: $n$ ) 사용 가능한 빈 슬롯의 개수를 세는 카운팅 세마포입니다.
items (아이템): (초기값: 0) 버퍼에 들어있는 아이템의 개수를 세는 카운팅 세마포입니다.

`sbuf_insert` (생산자) 함수

void sbuf_insert(sbuf_t *sp, int item) {
    P(&sp->slots); // 1. 빈 슬롯을 기다린다. (slots--. 0이면 대기)
    P(&sp->mutex); // 2. 버퍼를 잠근다. (상호 배제)
    
    // (버퍼에 아이템 삽입)
    
    V(&sp->mutex); // 3. 버퍼 잠금을 해제한다.
    V(&sp->items); // 4. 새 아이템이 생겼다고 알린다. (items++)
}

`sbuf_remove` (소비자) 함수

int sbuf_remove(sbuf_t *sp) {
    int item;
    
    P(&sp->items); // 1. 아이템을 기다린다. (items--. 0이면 대기)
    P(&sp->mutex); // 2. 버퍼를 잠근다. (상호 배제)
    
    // (버퍼에서 아이템 제거)
    
    V(&sp->mutex); // 3. 버퍼 잠금을 해제한다.
    V(&sp->slots); // 4. 빈 슬롯이 생겼다고 알린다. (slots++)
    
    return item;
}

2. 읽기-쓰기 문제 (Readers-Writers Problem)

이 문제는 읽기 스레드(Readers)와 쓰기 스레드(Writers)가 공유 객체에 접근할 때 발생합니다.

규칙:
- 읽기(Readers): 여러 읽기 스레드가 동시에 객체를 읽는 것은 허용됩니다.
- 쓰기(Writers): 쓰기 스레드는 반드시 독점적으로(exclusive) 접근해야 합니다. (즉, 다른 읽기 스레드나 쓰기 스레드가 없어야 함)

(예: 항공사 예약 시스템 (다수가 좌석 조회, 한 명만 예약), 웹 프록시 캐시 (다수가 캐시 읽기, 한 스레드만 캐시 쓰기))

문제의 변형 (우선순위)

제1 문제 (읽기 우선): 읽기 스레드가 기다리지 않도록 합니다. 즉, 쓰기 스레드가 기다리고 있더라도, 읽기 스레드가 있다면 다른 읽기 스레드들이 계속 진입할 수 있습니다.
제2 문제 (쓰기 우선): 쓰기 스레드가 준비되면 가능한 한 빨리 쓰기를 수행합니다. 쓰기 스레드가 기다리면, 나중에 도착한 읽기 스레드도 함께 기다려야 합니다.

제1 문제 (읽기 우선)의 해결책

이 해결책은 2개의 세마포와 1개의 카운트 변수를 사용합니다.

w (쓰기 락): (초기값: 1) 공유 객체 자체에 대한 접근을 제어합니다. (읽기/쓰기 모두 사용)
mutex (뮤텍스): (초기값: 1) readcnt 변수를 보호하기 위한 상호 배제 락입니다.
readcnt (카운터): (초기값: 0) 현재 임계 구역에 있는 읽기 스레드의 수를 셉니다.

쓰기(Writer) 로직 (간단함)

P(w); // 객체에 대한 독점 락을 획득
// (쓰기 작업 수행)
V(w); // 객체 락 해제

읽기(Reader) 로직 (미묘함)

P(mutex);       // readcnt를 잠근다
readcnt++;      // 읽기 스레드 수 증가
if (readcnt == 1) // (중요) 내가 "첫 번째" 읽기 스레드라면
    P(w);       // 쓰기 스레드를 막기 위해 객체 락을 획득
V(mutex);       // readcnt 잠금 해제

// (읽기 작업 수행)

P(mutex);       // readcnt를 잠근다
readcnt--;      // 읽기 스레드 수 감소
if (readcnt == 0) // (중요) 내가 "마지막" 읽기 스레드라면
    V(w);       // 쓰기 스레드가 진입할 수 있도록 객체 락을 해제
V(mutex);       // readcnt 잠금 해제

이 방식에서, w 세마포는 첫 번째 읽기 스레드가 락을 잡고, 마지막 읽기 스레드가 락을 해제합니다. 중간에 있는 읽기 스레드들(readcnt가 1 이상일 때)은 w 락을 무시하고 자유롭게 진입합니다.

기아(Starvation) 문제: 이 해결책(읽기 우선)은 읽기 스레드들이 계속 이어서 도착할 경우, 쓰기 스레드가 무한정 대기하는 '쓰기 기아(writer starvation)' 상태를 유발할 수 있습니다.

12.5.5 종합: 미리 스레드 생성하기(Prethreading) 기반의 동시성 서버

지금까지 세마포가 공유 변수 접근(상호 배제)과 공유 자원 접근 스케줄링에 어떻게 사용되는지 살펴보았습니다. 이 아이디어들을 미리 스레드 생성하기(prethreading)라는 기법에 기반한 동시성 서버에 적용해 보겠습니다.

1. 문제점과 접근 방식

이전 방식의 문제 (Figure 12.14):
이전의 스레드 기반 서버는 새 클라이언트마다 새 스레드를 생성(pthread_create)했습니다. 이 접근 방식은 클라이언트가 새로 올 때마다 스레드를 생성하는 상당한 (nontrivial) 오버헤드(비용)를 유발합니다.
새로운 방식 (Prethreading):
Prethreading 기반 서버는 이 오버헤드를 줄이기 위해 생산자-소비자(Producer-Consumer) 모델을 사용합니다 (Figure 12.27).

서버는 메인 스레드 1개와 워커 스레드(Worker threads) 풀(pool)로 구성됩니다.
메인 스레드 (생산자): 클라이언트의 연결 요청을 반복적으로 수락(Accept)하고, 그 결과로 생성된 연결 디스크립터(connfd)를 유한 버퍼(bounded buffer)에 삽입(Insert)합니다.
워커 스레드 (소비자): 버퍼에서 connfd를 반복적으로 제거(Remove)하고, 해당 클라이언트를 서비스(service)한 후, 다음 connfd를 기다립니다.

2. `echoserver-pre.c` 구현 (Figure 12.28)

Figure 12.28은 Sbuf 패키지(이전 섹션의 생산자-소비자 버퍼)를 사용하여 prethreaded 동시성 에코 서버를 구현하는 방법을 보여줍니다.

main 스레드 (생산자):
1. sbuf_init(line 24): 공유 버퍼 sbuf를 초기화합니다.
2. for 루프 (lines 25–26): NTHREADS 개수만큼 워커 스레드들을 미리 생성합니다.
3. while (1) (lines 28–31): 메인 스레드는 무한 루프에 진입하여, Accept (연결 수락)와 sbuf_insert (버퍼에 connfd 삽입) 작업만 반복 수행합니다.
thread (워커 스레드 루틴):
1. Pthread_detach(line 36): 스레드가 join될 필요 없도록 스스로를 분리(detach)합니다.
2. while (1) (lines 38–42):
  - connfd = sbuf_remove(&sbuf) (line 39): Sbuf에서 connfd를 꺼냅니다. (만약 버퍼가 비어있으면, sbuf_remove 내부의 P(&items)에서 블록(block)됩니다.)
  - echo_cnt(connfd) (line 40): 클라이언트 서비스 함수를 호출합니다.
  - Close(connfd) (line 41): 서비스가 끝나면 연결을 닫습니다.
  - (다시 루프의 처음으로 돌아가 다음 connfd를 기다립니다.)

3. `echo_cnt` 함수: 스레드 안전한 패키지 설계 (Figure 12.29)

echo_cnt 함수는 모든 클라이언트로부터 받은 누적 바이트 수를 byte_cnt라는 전역 변수에 기록하는 echo 버전입니다. 이 코드는 스레드 루틴에서 호출되는 패키지를 초기화하는 일반적인 기법을 보여주므로 중요합니다.

여기서는 byte_cnt 카운터와 mutex 세마포를 초기화해야 합니다.

기법 1: pthread_once를 이용한 초기화
- (메인 스레드가 명시적으로 init 함수를 호출하는 대신) pthread_once 함수(line 19)를 사용합니다.
- pthread_once는 어떤 스레드든 echo_cnt를 최초로 호출했을 때, 초기화 함수(init_echo_cnt)가 단 한 번만 실행되도록 보장합니다.
- 장점: 패키지 사용이 쉬워집니다. (메인 스레드가 init 호출을 신경 쓸 필요 없음)
- 단점: echo_cnt가 호출될 때마다 (대부분 쓸데없는) pthread_once 함수를 호출하는 비용이 듭니다.
기법 2: P/V를 이용한 상호 배제
- init_echo_cnt가 실행되면, byte_cnt는 0, mutex는 1로 초기화됩니다.
- echo_cnt가 실제 작업을 할 때, 공유 변수 byte_cnt에 접근하는 부분(lines 23–25)은 P(&mutex)와 V(&mutex) 연산으로 감싸져 보호됩니다.
- 이를 통해 badcnt.c에서 발생했던 경쟁 상태(race condition)를 방지하고 byte_cnt가 올바르게 증가하도록 보장합니다.

부가 설명: 다른 동기화 기법들

(Aside: Other synchronization mechanisms)

우리는 주로 세마포(semaphores)를 사용하여 스레드를 동기화하는 방법을 보여드렸습니다. 세마포가 단순하고 고전적이며 깔끔한 의미론적 모델을 가지고 있기 때문입니다.

하지만 다른 동기화 기법들도 존재한다는 것을 알아야 합니다.

Java 모니터 (Java Monitor):
예를 들어, Java 스레드는 "Java 모니터"라는 메커니즘으로 동기화됩니다. 이는 세마포의 상호 배제 및 스케줄링 기능을 더 높은 수준으로 추상화한 것을 제공합니다. (실제로 모니터는 세마포로 구현될 수 있습니다.)
Pthreads 뮤텍스와 조건 변수 (Mutex and Condition Variables):
또 다른 예로, Pthreads 인터페이스는 뮤텍스(mutex)와 조건 변수(condition variables)에 대한 동기화 연산들을 정의합니다.
- Pthreads 뮤텍스: 상호 배제를 위해 사용됩니다.
- Pthreads 조건 변수: 생산자-소비자 프로그램의 유한 버퍼와 같은 공유 자원에 대한 접근을 스케줄링(scheduling)하기 위해 사용됩니다.

부가 설명: 스레드 기반의 이벤트 기반 프로그램

(Aside: Event-driven programs based on threads)

I/O 멀티플렉싱만이 이벤트 기반(event-driven) 프로그램을 작성하는 유일한 방법은 아닙니다.

예를 들어, 우리가 방금 개발한 동시성 prethreaded 서버 (12.5.5절) 역시 메인 스레드와 워커 스레드를 위한 간단한 상태 머신을 가진 이벤트 기반 서버라는 것을 눈치챘을 것입니다.

메인 스레드 (생산자):
- 2개의 상태: "연결 요청 기다림" (accept), "버퍼의 빈 슬롯 기다림" (P(slots))
- 2개의 이벤트: "연결 요청 도착", "버퍼 슬롯 사용 가능" (V(slots))
- 2개의 트랜지션(상태 전이): "연결 요청 수락", "버퍼 아이템 삽입"
각 워커 스레드 (소비자):
- 1개의 상태: "버퍼 아이템 기다림" (P(items))
- 1개의 이벤트: "버퍼 아이템 사용 가능" (V(items))
- 1개의 트랜지션(상태 전이): "버퍼 아이템 제거"

12.6 병렬성을 위한 스레드 사용

지금까지 우리는 단일 프로세서(uniprocessor) 시스템에서의 동시성 스레드를 가정했습니다. 하지만 대부분의 최신 머신은 멀티코어(multi-core) 프로세서를 가지고 있습니다.

동시성 프로그램은 이런 머신에서 더 빠르게 실행되는 경우가 많습니다. 왜냐하면 운영체제 커널이 동시성 스레드들을 단일 코어에서 순차적(sequentially)으로 실행하는 대신, 여러 코어에서 병렬(in parallel)로 스케줄링하기 때문입니다.

이러한 병렬성(parallelism)을 활용하는 것은 웹 서버, 데이터베이스 서버, 대규모 과학 계산 코드 등에서 매우 중요하며, 웹 브라우저나 스프레드시트 같은 일반 프로그램에서도 점점 더 유용해지고 있습니다.

1. 동시성 vs. 병렬성

Figure 12.30은 순차, 동시성, 병렬 프로그램 간의 집합 관계를 보여줍니다.

순차 프로그램 (Sequential): 단일 논리 흐름으로 작성됩니다.
동시성 프로그램 (Concurrent): 여러 개의 동시적 논리 흐름으로 작성됩니다.
병렬 프로그램 (Parallel): 동시성 프로그램이 여러 프로세서에서 실행되는 것을 말합니다.
(즉, 병렬 프로그램의 집합은 동시성 프로그램의 집합에 포함되는 진부분집합입니다.)

2. 예제: 정수 합계 병렬 계산

병렬 프로그래밍의 몇 가지 중요한 측면을 이해하기 위해, $0$ 부터 $n-1$ 까지의 정수 합계를 병렬로 계산하는 간단한 예제를 살펴봅니다.

가장 간단한 접근 방식은 전체 시퀀스를 $t$ 개의 영역으로 분할하고, $t$ 개의 스레드가 각자 자신의 영역을 맡아 작업하게 하는 것입니다.

3. 시도 1: 뮤텍스로 전역 변수 공유 (psum-mutex.c)

가장 직관적인 방법은, 모든 스레드가 뮤텍스(mutex)로 보호되는 단일 공유 전역 변수(gsum)에 합계를 더하는 것입니다. (Figure 12.31, 12.32)

main 스레드: t개의 피어 스레드를 생성하고, 각 스레드에 고유한 ID(0, 1, 2...)를 전달합니다. 스레드가 모두 종료되길 기다린(pthread_join) 후, gsum 값을 확인합니다.
sum_mutex (피어 스레드):
- for 루프의 모든 반복마다 P(&mutex)로 락을 걸고, gsum += i;를 실행한 뒤, V(&mutex)로 락을 풉니다.

성능 측정 결과 (4코어, $n=2^{31}$ ):

쓰레드 개수	1	2	4	8	16
psum-mutex	68	432	719	552	599

끔찍한 놀라움을 마주하게 됩니다.

1개 스레드로 순차 실행할 때도 68초로 매우 느립니다.
여러 스레드로 병렬 실행하면 거의 10배나 더 느려집니다. (4개 스레드: 719초)
코어를 더 추가할수록 성능은 더 나빠집니다.

이유:동기화 오버헤드(Synchronization overhead) 때문입니다. P(락)와 V(언락) 연산은 단순한 메모리 업데이트(gsum += i) 비용에 비해 매우 비쌉니다.

교훈 1: 동기화 오버헤드는 비싸므로 가능하면 피해야 합니다. 피할 수 없다면, 가능한 한 많은 유용한 계산을 통해 그 오버헤드를 상각(amortize)해야 합니다.

4. 시도 2: 개별 전역 배열 사용 (psum-array.c)

동기화를 피하는 한 가지 방법은, 각 피어 스레드가 자신의 부분 합계를 다른 스레드와 공유되지 않는 개별 변수에 계산하도록 하는 것입니다. (Figure 12.33)

쓰레드 개수	1	2	4	8	16
psum-mutex	68.00	432.00	719.00	552.00	599.00
psum-array	7.26	3.64	1.91	1.85	1.84

main 스레드: psum이라는 전역 배열을 정의합니다.
sum_array (피어 스레드):
- 각 피어 스레드 $i$ 는 자신의 부분 합계를 psum[i]에 누적시킵니다. (psum[myid] += i;)
- 핵심: 각 스레드는 고유한 메모리 위치(psum[0], psum[1]...)를 업데이트하므로, 뮤텍스 보호가 필요 없습니다.
main 스레드: 모든 스레드가 종료되면, psum 벡터의 모든 요소를 합산하여 최종 결과를 얻습니다.

성능 측정 결과:

psum-array는 psum-mutex보다 수백 배(orders of magnitude) 더 빠릅니다. 스레드가 4개일 때 1.91초로, 병렬성의 이점을 제대로 보여줍니다.

5. 시도 3: 지역 변수 활용 (psum-local.c)

(5장에서 배운) 불필요한 메모리 참조를 제거하는 원칙을 적용하여, 각 스레드가 전역 변수가 아닌 지역 변수(local variable)에 부분 합계를 누적하도록 할 수 있습니다. (Figure 12.34)

sum_local (피어 스레드):
- for 루프 안에서는 스택에 할당된 지역 변수 sum에 합계를 누적합니다. (이 변수는 레지스터에 저장될 가능성이 높습니다.)
- for (i = start; i < end; i++) { sum += i; }
- 루프가 모두 끝난 후 단 한 번만 전역 배열 psum에 자신의 결과를 저장합니다. (psum[myid] = sum;)

성능 측정 결과:

쓰레드 개수	1	2	4	8	16
psum-mutex	68.00	432.00	719.00	552.00	599.00
psum-array	7.26	3.64	1.91	1.85	1.84
psum-local	1.06	0.54	0.28	0.29	0.30

psum-local을 실행하면 또 한 차례(another order-of-magnitude) 성능이 향상됩니다. (4개 스레드: 0.28초)

결론: 병렬 프로그래밍의 교훈

이 실습에서 얻을 수 있는 중요한 교훈은 병렬 프로그램을 작성하는 것이 매우 까다롭다(tricky)는 것입니다.

코드의 사소해 보이는 작은 변경이 성능에 막대한 영향을 미칩니다. (예: psum[myid] += i를 sum += i로 바꾸는 것)

병렬 프로그램의 성능의 특성분석

1. psum-local 성능 분석 (Figure 12.35)

Figure 12.35는 4개의 프로세서 코어를 가진 시스템에서 psum-local 프로그램의 실행 시간을 스레드 수( $t$ )에 따라 보여줍니다.

$t=1$ ~ $t=4$ : 스레드 수를 4개까지 늘리면 실행 시간이 (거의 선형적으로) 감소합니다.
$t > 4$ (예: $t=8, t=16$ ): 4개 지점에서 성능 향상이 멈추고, 심지어 실행 시간이 약간 증가합니다.
이유: 이 시스템은 코어가 4개뿐입니다. 스레드 수가 4개를 초과하면, 여러 스레드가 동일한 코어에서 문맥 교환(context switching)을 해야 하므로 그 오버헤드 때문에 시간이 더 걸립니다.
(이 때문에 병렬 프로그램은 종종 각 코어가 정확히 하나의 스레드를 실행하도록 작성됩니다.)

2. 병렬 성능 측정 지표 (Figure 12.36)

절대적인 실행 시간도 중요하지만, 병렬성의 잠재력을 얼마나 잘 활용하는지 파악하기 위한 유용한 상대적 측정값들이 있습니다.

속도 향상 (Speedup, $S_p$ )

정의: $S_p = T_1 / T_p$
$p$ = 프로세서 코어 수
$T_k$ = $k$ 개 코어에서의 실행 시간
(이러한 공식을 강한 확장성 (strong scaling)이라고 합니다.)

$T_1$ 을 무엇으로 보느냐에 따라 두 가지로 나뉩니다.

절대적 속도 향상 (Absolute speedup):
- $T_1$ = 순차 버전 프로그램의 실행 시간.
- 병렬성의 이점을 "더 진실하게" 측정하는 방법입니다.
상대적 속도 향상 (Relative speedup):
- $T_1$ = 병렬 버전 프로그램을 1개 코어로 실행했을 때의 시간.
- (Figure 12.36의 계산은 이 방식입니다: $1.06 / 0.54 \approx 1.9$ )
- '절대적' 방식보다 측정하기 쉽지만, 결과가 부풀려질 수 있습니다. (병렬 버전은 1개 코어로 실행 시 불필요한 동기화 오버헤드 때문에 순차 버전보다 $T_1$ 이 더 느릴 수 있기 때문)

효율성 (Efficiency, $E_p$ )

정의: $E_p = S_p / p = T_1 / (pT_p)$
(0~100% 사이의 백분율로 표시)
병렬화로 인한 오버헤드 (동기화, 통신 시간)를 측정하는 지표입니다.
효율성이 높을수록(100%에 가까울수록) 유용한 작업을 하는 데 시간을 더 많이 쓰고 오버헤드에 시간을 덜 쓴다는 의미입니다.
(Figure 12.36의 90% 이상 효율은 매우 좋은 편이지만, psum 문제가 병렬화하기 "지나치게 쉬운" 문제였기 때문이라는 점을 감안해야 합니다.)

3. 강한 확장성(Strong Scaling) vs. 약한 확장성(Weak Scaling)

속도 향상을 보는 관점은 두 가지가 있습니다.

1. 강한 확장성 (Strong Scaling) → 시간 관점(4명 늘렸더니 시간이 1/4로 줄었나?)

개념: 문제 크기를 고정시킨 상태에서, 프로세서( $p$ )를 늘릴 때 실행 시간( $T_p$ )이 얼마나 줄어드는지 측정합니다. (지금까지 우리가 본 방식)
목표: "고정된 양의 작업을 얼마나 더 빨리 끝낼 것인가?"
적합한 분야: 실시간 신호 처리처럼 작업량이 고정된 애플리케이션.

2. 약한 확장성 (Weak Scaling) → 일 처리량 관점 (4명 늘렸더니 4배로 일했나?)

개념: 프로세서 수( $p$ )를 늘릴 때, 문제 크기도 비례하여 함께 증가시킵니다. (각 프로세서가 처리하는 작업량은 일정하게 유지)
목표: "같은 시간 동안 얼마나 더 많은 작업을 처리할 것인가?"
적합한 분야: 과학 계산 코드처럼 문제 크기를 쉽게 늘릴 수 있고, 문제 크기가 클수록 더 좋은 예측을 의미하는 분야. (더 큰 기계를 사용해 더 많은 일을 하고 싶다는 요구를 더 잘 반영함)

12.7 다른 동시성 이슈들

공유 데이터에 대한 접근을 동기화하라는 요구를 받자마자 삶이 훨씬 더 복잡해졌다는 것을 눈치채셨을 것입니다. 지금까지 우리는 상호 배제와 생산자-소비자 동기화 기법을 살펴보았지만, 이것은 빙산의 일각에 불과합니다.

동기화는 일반적인 순차 프로그램에서는 전혀 발생하지 않는 이슈를 제기하는, 근본적으로 어려운 문제입니다. 이 섹션은 여러분이 동시성 프로그램을 작성할 때 알아야 할 몇 가지 이슈들에 대한 (결코 완전하지는 않은) 개요(survey)입니다.

논의를 구체적으로 유지하기 위해 스레드 관점에서 설명하겠지만, 이 문제들은 어떤 종류의 동시성 흐름이든 공유 자원을 조작할 때 발생하는 전형적인 이슈들임을 명심해야 합니다.

12.7.1 스레드 안전성 (Thread Safety)

스레드로 프로그래밍할 때는 스레드 안전성(thread safety)이라는 속성을 가진 함수를 작성하도록 주의해야 합니다.

어떤 함수가 여러 동시성 스레드에서 반복적으로 호출될 때 항상 올바른 결과를 생성한다면, 그 함수는 스레드 안전(thread-safe)하다고 말합니다. 만약 그렇지 않다면, 스레드 비안전(thread-unsafe)하다고 말합니다.

스레드 비안전 함수는 (서로 배타적이지 않은) 4가지 클래스로 식별할 수 있습니다.

클래스 1: 공유 변수를 보호하지 않는 함수

문제: 보호되지 않는 전역 변수를 조작하는 함수입니다. (예: Figure 12.16 badcnt.c의 cnt++)
해결책: P/V 같은 동기화 연산(뮤텍스)으로 공유 변수를 보호합니다.
장점: 이 함수를 호출하는 쪽의 코드를 변경할 필요가 없습니다.
단점: 동기화 연산으로 인해 함수 속도가 느려집니다.

클래스 2: 여러 호출에 걸쳐 상태를 유지하는 함수

문제: 현재 호출의 결과가 이전 호출의 중간 결과(상태)에 의존하는 함수입니다.

예시: Figure 12.37의 rand 함수. next_seed라는 정적(static) 변수(공유 자원)를 사용하여 다음 난수를 생성합니다. 여러 스레드가 동시에 rand를 호출하면 next_seed 값이 뒤엉켜버립니다.
해결책: 함수가 정적 데이터(static data)를 사용하지 않도록 다시 작성해야 합니다. 대신, 호출자가 상태 정보(seed 값)를 인자로 전달하도록 변경해야 합니다. (Figure 12.40의 rand_r 함수 참고)

/* 스레드 A의 루틴 */
void *thread_A_routine(void *vargp) {
		unsigned int my_seed = 1; // A의 개인 씨앗 상자 (스택에 있음)
		while (1) {
				int r = rand_r(&my_seed); // A의 상자 주소를 넘김
		}
}

/* 스레드 B의 루틴 */
void *thread_B_routine(void *vargp) {
		unsigned int my_seed = 99; // B의 개인 씨앗 상자 (스택에 있음)
		while (1) {
				int r = rand_r(&my_seed); // B의 상자 주소를 넘김
		}
}

단점: 이 함수를 호출하는 쪽의 코드도 모두 수정해야 합니다. (호출 인자가 바뀌었기 때문)

클래스 3: 정적 변수의 포인터를 반환하는 함수 (함수 내부에서 static 변수 포인터 반환)

문제: ctime이나 gethostbyname 같은 일부 함수는, (공유되는) 단 하나의 정적 변수에 결과를 계산한 뒤, 그 변수의 포인터를 반환합니다.
경쟁 상태: 스레드 A가 이 함수를 호출해 결과를 사용하는 도중에, 스레드 B가 이 함수를 호출하면, 정적 변수의 내용이 스레드 B의 결과로 덮어써져, 스레드 A의 데이터가 조용히 망가집니다.
해결책 1 (수정 가능 시): 호출자가 결과를 저장할 변수의 주소를 인자로 전달하도록 함수를 다시 작성합니다. (공유 데이터를 제거함)
해결책 2 (수정 불가 시): 잠금-복사 (lock-and-copy) 기법
1. 이 스레드 비안전 함수와 연관된 뮤텍스를 하나 만듭니다.
2. 함수를 호출하기 직전, 뮤텍스를 잠급니다(Lock).
3. 스레드 비안전 함수를 호출합니다.
4. 함수가 반환한 (공유) 정적 변수의 결과를, 호출자 스레드의 개인(private) 메모리로 복사(strcpy)합니다.
5. 뮤텍스를 풉니다(Unlock).

(Figure 12.38의 ctime_ts는 ctime 함수를 이 기법으로 감싼 스레드 안전 래퍼 함수(wrapper function)입니다.)

클래스 4: 스레드 비안전 함수를 호출하는 함수

문제: 함수 $f$ 가 스레드 비안전 함수 $g$ 를 호출한다면, $f$ 도 스레드 비안전할까요?
답: 경우에 따라 다릅니다.
- $g$ 가 클래스 2 함수라면, $f$ 도 스레드 비안전하며 $g$ 를 고쳐 쓰는 것 외엔 답이 없습니다.
- $g$ 가 클래스 1 또는 클래스 3 함수라면, $f$ 는 스레드 안전할 수 있습니다. $g$ 를 호출하는 부분과 그 결과로 나온 공유 데이터를 뮤텍스로 보호하면 됩니다. (Figure 12.38의 ctime_ts가 바로 이 예시입니다.)

12.7.2 재진입성 (Reentrancy)

재진입 가능 함수(reentrant functions)는 스레드 안전(thread-safe) 함수 중에서도 중요한 한 클래스입니다. 이 함수들은 여러 스레드에 의해 호출될 때 어떠한 공유 데이터도 참조하지 않는다는 속성을 특징으로 합니다.

"스레드 안전"과 "재진입 가능"이라는 용어가 (부정확하게) 동의어처럼 사용되기도 하지만, 보존할 가치가 있는 명확한 기술적 구분이 있습니다. Figure 12.39는 이들의 집합 관계를 보여줍니다.

전체 함수 집합은 스레드 안전 함수와 스레드 비안전 함수로 나뉩니다.
재진입 가능 함수 집합은 스레드 안전 함수 집합의 진부분집합(proper subset)입니다. (즉, 모든 재진입 가능 함수는 스레드 안전하지만, 모든 스레드 안전 함수가 재진입 가능한 것은 아닙니다.)

재진입 가능 함수의 장점

재진입 가능 함수는 동기화 연산(synchronization operations)이 전혀 필요 없기 때문에, 비-재진입(non-reentrant) 스레드 안전 함수보다 일반적으로 더 효율적입니다.

또한, (여러 호출에 걸쳐 상태를 유지하는) 클래스 2 스레드 비안전 함수를 스레드 안전하게 만드는 유일한 방법은 그 함수를 재진입 가능하도록 다시 작성하는 것입니다.

예시: Figure 12.37의 rand 함수를 Figure 12.40의 rand_r 함수로 바꾼 것이 그 예입니다.

핵심 아이디어: 정적(static) 변수 next_seed를 사용하는 대신, 호출자가 전달하는 포인터(nextp)를 사용하도록 변경했습니다.

재진입 가능성 판단하기

어떤 함수의 코드를 보고 그것이 재진입 가능하다고 미리 선언할 수 있을까요? 상황에 따라 다릅니다.

명시적 재진입 가능 (Explicitly reentrant):
- 모든 함수 인자가 값으로 전달(pass by value)되고 (포인터 없음),
- 모든 데이터 참조가 지역 자동 스택 변수에 대한 것이라면 (정적 또는 전역 변수 참조 없음),
- 이 함수는 어떻게 호출되든 상관없이 재진입 가능하다고 단언할 수 있습니다.
암시적 재진입 가능 (Implicitly reentrant):
- 위의 조건에서 약간 완화하여, 일부 파라미터가 참조로 전달(pass by reference)되는 것을 허용한다면 (포인터를 허용한다면),
- 이 함수는 호출하는 스레드들이 비공유 데이터(nonshared data)에 대한 포인터를 전달하도록 주의를 기울일 경우에만 재진입 가능합니다.
- 예시: Figure 12.40의 rand_r 함수가 "암시적 재진입 가능"입니다. (스레드들이 각자 고유한 seed 변수의 주소를 nextp로 넘겨줘야만 재진입성이 보장됩니다.)

우리는 보통 "재진입 가능"이라는 용어를 명시적, 암시적 재진입을 모두 포함하여 사용합니다. 하지만 재진입성은 때때로 함수 자체(callee)만의 속성이 아니라, 호출자(caller)와 함수(callee) 양쪽 모두의 속성이라는 점을 인지하는 것이 중요합니다.

12.7.3 스레드 프로그램에서 기존 라이브러리 함수 사용하기

대부분의 리눅스 함수 및 표준 C 라이브러리 함수(malloc, free, realloc, printf, scanf 등)는 스레드 안전(thread-safe)합니다.

하지만 몇 가지 예외가 있으며, Figure 12.41은 그 일반적인 예외 목록을 보여줍니다.

strtok: (사용이 권장되지 않는) 문자열 파싱 함수 (클래스 2)
asctime, ctime, localtime: 날짜/시간 변환 함수 (클래스 3)
gethostbyaddr, gethostbyname, inet_ntoa: (구식의) 네트워크 프로그래밍 함수 (클래스 3)

rand와 strtok을 제외한 이 함수들은 대부분 정적 변수의 포인터를 반환하는 클래스 3 스레드 비안전 함수입니다.

1. 해결책 1: 잠금-복사 (Lock-and-Copy)

스레드 프로그램에서 이 함수들을 호출해야 할 때, 호출자에게 가장 지장을 덜 주는 접근 방식은 "잠금-복사(lock-and-copy)"입니다. (12.7.1의 ctime_ts 래퍼 함수처럼)

하지만 이 방식은 여러 단점이 있습니다.

성능: 추가적인 동기화(뮤텍스)로 인해 프로그램이 느려집니다.
복잡성: 복잡한 구조체의 포인터를 반환하는 함수는, 전체 계층 구조를 복사하기 위해 "깊은 복사(deep copy)"가 필요할 수 있습니다.
한계: rand와 같이 호출 간 상태를 유지하는 클래스 2 함수에는 이 방식이 동작하지 않습니다.

2. 해결책 2: 재진입 가능(Reentrant) 버전 사용

따라서, 리눅스 시스템은 대부분의 스레드 비안전 함수에 대한 재진입 가능(reentrant) 버전을 제공합니다.

이 재진입 가능 버전의 이름은 항상 _r 접미사로 끝납니다. (예: asctime의 재진입 버전은 asctime_r입니다.)
(참고: gethost... 함수들은 getaddrinfo나 getnameinfo 같은 최신 재진입 함수들로 대체되었습니다.)

결론: 가능하면 항상 이 _r 버전의 함수들을 사용할 것을 권장합니다.

12.7.4 경쟁 (Races)

경쟁(race)은 한 스레드가 제어 흐름의 $x$ 지점에 도달하기 전에 다른 스레드가 $y$ 지점에 도달하는 것에 프로그램의 정확성이 의존할 때 발생합니다.

경쟁은 프로그래머가 스레드가 특정 실행 경로로만 실행될 것이라고 가정하고, "스레드 프로그램은 가능한 모든 실행 경로에 대해 올바르게 작동해야 한다"는 황금률을 잊어버리기 때문에 발생합니다.

경쟁 예제 (Figure 12.42, `race.c`)

Figure 12.42의 프로그램은 4개의 피어 스레드를 생성하고, 각 스레드에 고유한 정수 ID의 포인터를 전달합니다. 각 피어 스레드는 전달받은 ID를 지역 변수 myid에 복사(line 22)한 뒤 메시지를 출력합니다.

간단해 보이지만, 이 프로그램을 실행하면 다음과 같은 잘못된 결과가 나옵니다. (3이 두 번 나옴)

linux> ./race
Hello from thread 1
Hello from thread 3
Hello from thread 2
Hello from thread 3

문제 원인: `main` 스레드와 `peer` 스레드 간의 경쟁

이 문제는 각 피어 스레드와 메인 스레드 간의 경쟁 때문에 발생합니다.

main 스레드는 for 루프를 돌며 스레드를 생성할 때(line 13), main 스레드의 지역 스택 변수 i의 주소(&i)를 전달합니다.

&i는 모든 스레드에게 동일한 단 하나의 메모리 주소입니다.

이 시점에서, 다음 두 작업 간의 경쟁이 시작됩니다.

main 스레드: for 루프가 다음으로 돌아 i를 증가시키는 작업 (line 12, i++)
peer 스레드: 인자를 역참조하여 myid에 할당하는 작업 (line 22, myid = *((int *)vargp))

만약 peer 스레드가 line 22를 main 스레드가 line 12보다 먼저 실행하면 myid는 올바른 값을 갖습니다. 하지만 그 반대라면 (즉, main 스레드가 i를 다음 값으로 덮어쓴 후에 peer 스레드가 line 22를 실행하면), myid는 다른 스레드의 ID 값을 갖게 됩니다. (위 예시에서는 스레드 2개가 3을 가져갔습니다.)

이 문제의 무서운 점은, 커널이 스레드를 어떻게 스케줄링하느냐에 따라 정답이 나올 수도 있고 아닐 수도 있다는 것입니다. (한 시스템에서는 실패하지만, 다른 시스템에서는 우연히 성공하여 프로그래머가 심각한 버그를 모른 채 넘어갈 수 있습니다.)

해결책 (Figure 12.43, `norace.c`)

경쟁을 제거하려면, 각 정수 ID마다 별도의 블록을 동적 할당(malloc)하고, 스레드 루틴에 이 블록의 포인터를 전달해야 합니다. (lines 12–14)

/* main 함수 (Figure 12.43) */
for (i = 0; i < N; i++) {
    ptr = Malloc(sizeof(int)); // 1. 스레드마다 고유한 메모리 블록 할당
    *ptr = i;                  // 2. 그 고유한 블록에 i 값을 저장
    Pthread_create(&tid[i], NULL, thread, ptr); // 3. 고유한 블록의 주소(ptr) 전달
}

/* thread 루틴 (Figure 12.43) */
void *thread(void *vargp) {
    int myid = *((int *)vargp); // 4. 고유한 주소에서 값을 읽음
    Free(vargp);                // 5. 할당된 메모리 블록을 해제 (메모리 누수 방지)
    printf("Hello from thread %d\n", myid);
    return NULL;
}

이 프로그램을 실행하면, 이제 매번 올바른 결과가 나옵니다.

linux> ./norace
Hello from thread 0
Hello from thread 1
Hello from thread 2
Hello from thread 3

12.7.5 교착 상태 (Deadlocks)

세마포는 교착 상태(deadlock)라고 불리는 고약한 런타임 오류의 가능성을 도입합니다. 교착 상태란 여러 스레드(집합)가 절대 참이 될 수 없는 조건을 기다리며 블록(blocked)되는 상황을 말합니다.

진행 그래프(Progress graph)는 교착 상태를 이해하는 데 매우 유용한 도구입니다. Figure 12.44는 두 개의 세마포( $s, t$ )를 상호 배제에 사용하는 스레드 쌍의 진행 그래프를 보여줍니다.

이 그래프에서 교착 상태에 대한 몇 가지 중요한 통찰을 얻을 수 있습니다.

원인: 잘못된 P/V 순서
프로그래머가 $P$ 와 $V$ 연산의 순서를 잘못 정해서, 두 세마포( $s, t$ )의 금지된 영역(forbidden regions)이 겹치게 만들었습니다. 만약 어떤 실행 경로가 교착 상태 $d$ 에 도달하면, 겹쳐진 금지된 영역이 모든 합법적인 방향(위, 오른쪽)으로의 진행을 막기 때문에 더 이상 진행이 불가능합니다.
- 즉, 각 스레드가 (절대 일어나지 않을) 상대방의 $V$ 연산을 기다리고 있기 때문에 프로그램은 교착 상태에 빠집니다.
교착 영역 (Deadlock Region)
겹쳐진 금지된 영역은 교착 영역(deadlock region)이라는 상태 집합을 유도합니다. 만약 실행 경로가 이 교착 영역의 상태를 건드린다면, 교착 상태는 필연적(inevitable)이 됩니다. 경로는 교착 영역에 진입할 수는 있지만, 절대 빠져나올 수 없습니다.
예측 불가능성 (Unpredictable)
교착 상태는 항상 예측 가능한 것이 아니기 때문에 특히 어려운 문제입니다. 어떤 운 좋은 실행 경로는 교착 영역을 피해 가지만(위쪽 경로), 다른 경로는 그 영역에 갇히게 됩니다(아래쪽 경로).
- 이는 프로그래머에게 무서운 일입니다. 프로그램을 천 번 실행해도 문제가 없다가, 그다음 번에 교착 상태에 빠질 수 있습니다. 또는 한 머신에서는 잘 동작하다가 다른 머신에서는 교착 상태에 빠질 수도 있습니다.
- 최악인 점은, 실행마다 경로가 다르기 때문에 오류가 종종 재현(repeatable)되지 않는다는 것입니다.

교착 상태 예방 규칙

프로그램이 교착 상태에 빠지는 이유는 많으며, 이를 예방하는 것은 일반적으로 어려운 문제입니다.

하지만, Figure 12.44처럼 상호 배제를 위해 이진 세마포(뮤텍스)를 사용하는 경우, 교착 상태를 예방하는 다음과 같은 간단하고 효과적인 규칙을 적용할 수 있습니다.

뮤텍스 락 순서 규칙 (Mutex lock ordering rule):
모든 뮤텍스에 대해 전체 순서(total ordering)를 정하고, 각 스레드가 이 순서대로 뮤텍스를 획득하고, 그 역순으로 뮤텍스를 해제한다면, 그 프로그램은 교착 상태가 발생하지 않습니다(deadlock-free).

예를 들어, Figure 12.44의 교착 상태는 두 스레드 모두 $s$ 를 먼저 락(lock)하고 $t$ 를 다음에 락하도록 수정함으로써 해결할 수 있습니다. Figure 12.45는 그 결과(금지된 영역이 겹치지 않음)를 보여줍니다.

12.8 요약: 동시성 프로그래밍

이 챕터에서는 시간적으로 겹치는 여러 논리적 흐름을 갖는 동시성 프로그램을 구축하는 세 가지 메커니즘을 학습했습니다.

1. 동시성 구축 메커니즘 3가지

프로세스 (Processes)
- 커널이 자동으로 스케줄링합니다.
- 주소 공간이 분리되어 있어, 데이터를 공유하려면 명시적인 IPC가 필요합니다.
I/O 멀티플렉싱 (I/O Multiplexing)
- 프로그래머가 상태 머신으로 논리 흐름을 직접 만듭니다.
- select 등을 통해 흐름을 명시적으로 스케줄링합니다.
- 단일 프로세스 내에 있으므로 데이터 공유가 빠르고 쉽습니다.
스레드 (Threads)
- 위 두 방식의 하이브리드(Hybrid)입니다.
- 커널이 자동으로 스케줄링합니다. (프로세스처럼)
- 단일 프로세스 내에서 실행되어 데이터 공유가 빠르고 쉽습니다. (I/O 멀티플렉싱처럼)

2. 동시성의 핵심 난제: 동기화

어떤 메커니즘을 사용하든, 공유 데이터에 대한 동시 접근을 동기화하는 것은 근본적으로 어려운 문제입니다.

세마포 (Semaphores)
- P (잠금/대기) 연산과 V (해제/신호) 연산을 통해 이 문제를 해결하도록 돕습니다.
- 목적 1: 상호 배제 (Mutual Exclusion): badcnt.c 같은 임계 구역을 보호합니다.
- 목적 2: 스케줄링 (Scheduling): '생산자-소비자'나 '읽기-쓰기' 문제처럼 자원 접근 순서를 조율합니다.
- (Prethreaded 서버는 이 두 가지 목적을 모두 사용한 좋은 예시입니다.)

3. 기타 동시성 이슈

동기화 외에도 동시성 프로그램은 여러 어려운 문제를 야기합니다.

스레드 안전성 (Thread-Safety)
- 여러 스레드가 동시에 호출해도 항상 올바르게 동작하는 성질입니다.
- 스레드 비안전(Thread-unsafe) 함수는 4가지 클래스로 분류되며, 이를 해결하기 위해 락(Lock)을 걸거나, 재진입 가능(_r 버전) 함수로 다시 작성해야 합니다.
재진입성 (Reentrancy)
- 공유 데이터를 전혀 참조하지 않는 스레드 안전 함수의 부분집합입니다.
- 동기화가 필요 없어 더 효율적입니다.
경쟁 (Races)
- 프로그래머가 스레드 실행 순서를 잘못 가정할 때(예: main의 i++ vs thread의 vargp), 프로그램의 정확성이 스케줄링에 의존하게 되는 버그입니다.
교착 상태 (Deadlocks)
- 스레드가 절대 일어나지 않을 이벤트를 기다리며 영원히 블록(block)되는 상태입니다.
- 주로 여러 개의 뮤텍스(락)를 획득하는 순서가 꼬일 때 발생합니다.

모깅

멈추지 않기

이전 포스트

[JUNGLE] TIL_51. CSAPP 12.5

다음 포스트