프로세스 동기화

여러 실행 주체가 같은 데이터를 동시에 읽고 쓰면, 실행 순서에 따라 결과가 달라지는 문제가 생긴다. 프로세스 동기화는 이런 공유 데이터의 일관성을 지키기 위해 협력하는 프로세스들의 실행 순서를 정해 주는 메커니즘이다. 이름은 프로세스 동기화지만 스레드처럼 실행 문맥을 가진 실행 단위는 모두 대상이다.

데이터 접근의 기본 구조

모든 연산은 "저장된 곳에서 읽어 → 연산하고 → 다시 저장"하는 흐름이다. 연산하는 쪽(CPU, 프로세스)이 여럿이고 저장된 곳(메모리, 디스크, 주소 공간)을 함께 쓰면, 누가 언제 읽고 썼는지에 따라 결과가 달라진다.

경쟁 상태 (Race Condition)

여러 프로세스(또는 스레드)가 공유 데이터에 동시에 접근하고, 최종 결과가 마지막으로 데이터를 다룬 쪽에 따라 달라지는 상황이다.

예를 들어 count++는 한 줄이지만 실제로는 "메모리에서 읽기 → 레지스터에서 1 더하기 → 메모리에 쓰기" 세 단계다. 한쪽이 count++, 다른 쪽이 count--를 하는 도중에 끼어들면, 원래 값으로 돌아와야 할 count가 한쪽 결과만 반영된 값이 될 수 있다.

계좌 잔액으로 보면 더 분명하다. 잔액이 10만 원일 때 A는 2만 원을, B는 5만 원을 더한다. 기대하는 결과는 17만 원이다.

sequenceDiagram
    participant A
    participant B
    Note over A: 잔액 읽기 (10만) → 2만 더하기 (12만)
    A->>B: 문맥 교환
    Note over B: 잔액 읽기 (10만) → 5만 더하기 (15만)
    B->>A: 문맥 교환
    Note over A: 저장 → 잔액 12만
    A->>B: 문맥 교환
    Note over B: 저장 → 잔액 15만<br>A의 입금이 사라진다

A의 "읽고 더하고 저장"이 끝나기 전에 B가 같은 잔액에 접근했기 때문이다. A가 잔액을 다루는 동안에는 B가 문맥 교환으로 CPU를 받더라도 기다려야 한다.

운영체제에서 경쟁 상태가 생기는 경우

사용자 프로세스는 주소 공간이 분리되어 있지만 커널 데이터는 공유되므로 커널 안에서 경쟁 상태가 생긴다.

임계 구역 문제 (Critical-Section Problem)

임계 구역(critical section) 은 각 프로세스의 코드 중 공유 데이터에 접근하는 부분이다. 목표는 한 프로세스가 임계 구역에 있을 때 다른 프로세스는 임계 구역에 들어갈 수 없게 하는 것이다.

do {
    entry section        // 들어가도 되는지 확인하고 잠금
    critical section     // 공유 데이터 접근
    exit section         // 잠금 해제
    remainder section
} while (1);

해결책이 만족해야 할 조건

동기화가 필요한 이유는 두 가지로 정리할 수 있다.

상호 배제의 대표 예가 생산자-소비자 문제다. 생산자는 버퍼에 물건을 넣고 공유 변수 총합을 1 늘리고, 소비자는 물건을 빼고 총합을 1 줄인다. 같은 횟수만큼 돌렸는데도 동기화가 없으면 총합이 처음 값과 달라진다. 전역 변수·파일·입출력장치 같은 공유 자원에 접근하는 코드가 임계 구역이고, 여기서 생기는 문제가 앞의 경쟁 상태다.

임계 구역 문제의 해법

소프트웨어 해법: 피터슨 알고리즘

두 프로세스 P0, P1이 공유 변수만으로 entry·exit section을 짜는 시도다. 앞의 두 시도는 세 조건 중 하나를 깨뜨린다.

// 프로세스 i 기준 (상대는 j)
flag[i] = true;                  // 들어가고 싶다
turn = j;                        // 그래도 상대에게 먼저 양보한다
while (flag[j] && turn == j) ;   // 상대도 원하고 상대 차례일 때만 기다린다
critical section
flag[i] = false;

둘이 동시에 들어가려 해도 turn에는 마지막에 쓴 값 하나만 남으므로 한쪽만 통과한다. 한계는 셋이다.

• 기다리는 동안 루프를 돌며 CPU를 쓰는 바쁜 대기다.
• 프로세스 둘을 전제로 한다(n개로 일반화한 것이 아래 빵집 알고리즘이다).
• 현대 CPU와 컴파일러는 메모리 읽기·쓰기 순서를 바꿀 수 있어서, 메모리 배리어 없이 그대로 쓰면 상호 배제가 깨진다. 교재용 알고리즘이고, 실제로는 아래 하드웨어 명령을 쓴다.

빵집 알고리즘 (Bakery Algorithm)

램포트(Lamport)가 만든 n개 프로세스용 소프트웨어 해법이다. 빵집에서 번호표를 뽑고 가장 작은 번호부터 손님을 받는 방식을 그대로 옮겼다.

// 공유: choosing[n] = false, number[n] = 0
choosing[i] = true;
number[i] = max(number[0..n-1]) + 1;     // 번호표 뽑기
choosing[i] = false;
for (j = 0; j < n; j++) {
    while (choosing[j]) ;                 // j가 번호를 뽑는 중이면 끝날 때까지
    while (number[j] != 0 &&
           (number[j], j) < (number[i], i)) ;   // 나보다 앞 번호가 있으면 대기
}
critical section
number[i] = 0;                            // 번호표 반납

• 두 프로세스가 동시에 max를 읽으면 같은 번호를 받을 수 있다. 그래서 (번호, 프로세스 번호) 쌍을 사전 순으로 비교해 번호가 같으면 프로세스 번호가 작은 쪽이 먼저 들어간다.
• choosing은 번호를 다 뽑기 전에 비교당하는 것을 막는다. 이게 없으면 번호를 쓰기 직전인 프로세스를 0으로 보고 지나쳐 둘이 함께 들어갈 수 있다.
• 도착 순서대로 들어가므로 상호 배제·진행·유한 대기를 모두 만족한다. 대신 번호가 계속 커질 수 있고, 피터슨처럼 바쁜 대기와 메모리 순서 문제가 있다.

하드웨어 해법: 원자 명령어

소프트웨어 해법이 복잡한 이유는 "읽고 → 검사하고 → 쓰는" 과정 중간에 다른 프로세스가 끼어들 수 있어서다. 하드웨어가 이 과정을 명령어 하나로 원자적으로 실행해 주면 해법이 간단해진다.

Test_and_Set(lock): lock의 원래 값을 돌려주고 lock을 true로 바꾼다 (한 번에)
 
while (Test_and_Set(lock)) ;   // 원래 값이 false였던 한 명만 통과
critical section
lock = false;

실제 CPU의 compare-and-swap, LL/SC 같은 원자 명령어와 이를 감싼 C·C++ API는 POSIX 스레드와 동기화 API에 있다.

뮤텍스 락 (Mutex Lock)

상호 배제만을 위한 가장 단순한 동기화 도구다. 전역 변수 하나와 함수 두 개로 구현할 수 있다.

lock = false             // 자물쇠. 모든 프로세스가 공유
 
acquire():               // 임계 구역에 들어가기 전에 호출
    while (lock == true) ;   // 잠겨 있으면 열릴 때까지 반복 확인
    lock = true              // 열려 있으면 잠그고 들어간다
 
release():               // 임계 구역을 나오며 호출
    lock = false

acquire(); 임계 구역; release();로 감싸면 한 프로세스만 임계 구역에 들어간다. 잠겼는지 계속 확인하며 기다리는 방식이 바쁜 대기(busy-wait)다. 위 의사 코드는 검사와 잠금이 두 단계로 나뉘어 그 사이에 끼어들 수 있으므로, 실제 acquire()는 앞의 Test-and-Set 같은 원자 명령어로 구현한다.

세마포어 (Semaphore)

뮤텍스 락이 공유 자원이 하나인 상황을 가정한다면, 세마포어는 공유 자원이 여러 개인 상황까지 일반화한 도구다. 교재에 따라 P/V 대신 wait()/signal()이라고 부른다.

이름은 철도 신호기(semaphore)에서 왔다. 신호기가 내려가 있으면 열차가 멈춰 기다리고 올라가면 지나가듯, 프로세스는 임계 구역 앞에서 세마포어를 보고 기다리거나 들어간다. 교재에 따라 연산 이름을 down()/up()으로 쓰기도 한다.

세마포어 S는 정수 변수 하나와, 그것에 접근하는 두 가지 원자적(atomic) 연산으로 이루어진 추상 자료형이다. S의 값은 사용 가능한 자원의 개수(임계 구역에 동시에 들어갈 수 있는 프로세스 수)를 뜻한다.

• P(S): 자원을 획득한다. 자원이 없으면(S <= 0) 기다린다.
• V(S): 자원을 반납한다.

P(S):  while (S <= 0) ;   // 자원이 생길 때까지 대기
       S--;
 
V(S):  S++;

임계 구역에 적용하면 S = 1로 두고 P(mutex); 임계 구역; V(mutex); 형태로 쓴다.

Busy-wait vs Block/Wakeup

위 구현은 기다리는 동안 반복문을 돌며 CPU를 쓴다. 기다리는 프로세스를 재우면 이 낭비가 사라진다.

P(S):  S.value--;  if (S.value < 0) { S.L에 넣고 block(); }
V(S):  S.value++;  if (S.value <= 0) { S.L에서 P를 꺼내 wakeup(P); }

Block/Wakeup에서 value가 음수이면 그 절댓값이 기다리는 프로세스 수다. Busy-wait 판에서는 검사한 뒤 감소시켰지만 여기서는 먼저 감소시키고 검사하므로 값이 0 아래로 내려갈 수 있다. 대기 리스트는 PCB를 넣는 대기 큐이고, block은 프로세스를 대기 상태로, wakeup은 준비 상태로 바꿔 준비 큐에 넣는 일이다(프로세스와 스레드).

자원이 2개(S = 2)이고 P1, P2, P3 순서로 들어오는 경우를 따라가면 다음과 같다.

sequenceDiagram
    participant P1
    participant P2
    participant P3
    participant S as 세마포어 S
    P1->>S: P(S)
    Note over S: S = 1, P1 진입
    P2->>S: P(S)
    Note over S: S = 0, P2 진입
    P3->>S: P(S)
    Note over S: S = -1, P3는 대기 큐로 (block)
    P1->>S: V(S)
    Note over S: S = 0
    S->>P3: 기다리던 P3를 깨움 (wakeup)
    Note over P3: P3 진입
    P2->>S: V(S)
    Note over S: S = 1
    P3->>S: V(S)
    Note over S: S = 2, 처음 값으로 돌아온다

P와 V 자체도 중간에 끼어들면 안 되는 임계 구역이다. 그래서 운영체제는 두 연산을 다음처럼 원자적으로 만든다.

세마포어로 실행 순서 제어하기

세마포어는 상호 배제뿐 아니라 실행 순서도 맞출 수 있다. S = 0으로 두고, 먼저 실행할 P1 뒤에 V(S)(signal), 나중에 실행할 P2 앞에 P(S)(wait)를 둔다.

P1:  임계 구역; V(S);
P2:  P(S); 임계 구역;

P2가 먼저 CPU를 받아도 S = 0이라 기다리게 되므로, 어느 쪽이 먼저 실행되든 항상 P1 → P2 순서가 된다.

세마포어의 두 종류

이진 세마포어는 뮤텍스처럼 쓸 수 있지만 같은 것은 아니다. 차이는 소유권이다.

우선순위 역전은 낮은 우선순위 작업이 락을 쥔 채 중간 우선순위 작업에 밀려, 그 락을 기다리는 높은 우선순위 작업까지 무한정 늦어지는 현상이다. 1997년 화성 탐사선 패스파인더가 이 때문에 계속 재부팅됐고, 뮤텍스의 우선순위 상속을 켜서 고쳤다. 우선순위 상속은 락을 쥔 작업의 우선순위를 기다리는 작업 중 가장 높은 것까지 잠시 올려 준다.

교착 상태와 기아

세마포어를 잘못 쓰면 문제가 생긴다.

• 교착 상태: 두 프로세스가 서로 상대가 가진 세마포어를 기다리며 영원히 멈춘다. 예: P0는 P(S); P(Q);, P1은 P(Q); P(S); 순서로 획득하려는 경우. 획득 순서를 통일하면 피할 수 있다. 자세한 내용은 교착 상태.
• 기아(starvation): 특정 프로세스가 대기 리스트에서 영원히 깨어나지 못한다.

고전적인 동기화 문제

동기화 도구가 제대로 설계됐는지 시험하는 표준 문제 셋이다.

생산자-소비자 (Bounded Buffer)

버퍼에 든 개수를 counter 하나로 세며 counter++·counter--를 하면, 앞의 「경쟁 상태」 예처럼 두 연산이 섞여 개수가 틀어진다. 세마포어 셋으로 역할을 나누면 해결된다.

생산자                              소비자
P(empty);   // 빈칸 확보             P(full);    // 찬 칸 확보
P(mutex);                           P(mutex);
버퍼에 넣기                          버퍼에서 꺼내기
V(mutex);                           V(mutex);
V(full);    // 찬 칸 하나 늘림        V(empty);   // 빈칸 하나 늘림

empty·full은 개수를 세는 counting semaphore로 실행 순서를, mutex는 이진 세마포어로 상호 배제를 맡는다. P의 순서를 바꾸면 안 된다. 생산자가 P(mutex)를 먼저 잡은 채 버퍼가 가득 차 P(empty)에서 잠들면, 소비자는 mutex를 못 얻어 빈칸을 만들 수 없으니 둘 다 영원히 기다린다. 스레드 수준에서 같은 일을 하는 블로킹 큐는 멀티스레딩 디자인 패턴에 있다.

읽기-쓰기 (Readers-Writers)

공유: readcount = 0,  mutex = 1 (readcount 보호),  wrt = 1 (쓰기 배타)
 
writer:  P(wrt);  쓰기;  V(wrt);
 
reader:  P(mutex);
         readcount++;
         if (readcount == 1) P(wrt);   // 첫 reader가 writer를 막는다
         V(mutex);
         읽기;                           // reader끼리는 동시에
         P(mutex);
         readcount--;
         if (readcount == 0) V(wrt);   // 마지막 reader가 writer를 풀어 준다
         V(mutex);

이 해법은 reader 우선이라, reader가 끊임없이 들어오면 readcount가 0이 되지 않아 writer가 기아에 빠진다. 반대로 기다리는 writer가 있으면 새 reader를 막는 writer 우선 해법은 reader를 굶길 수 있다. 실제 읽기-쓰기 락은 대기 중인 writer가 있으면 새 reader를 줄 세우는 식으로 둘 사이를 조율한다(pthread_rwlock, Java ReentrantReadWriteLock).

식사하는 철학자 (Dining Philosophers)

젓가락마다 세마포어 하나(chopstick[5], 모두 1)를 두고 P(chopstick[i]); P(chopstick[(i+1)%5]);로 집으면, 다섯 명이 동시에 왼쪽을 집는 순간 교착 상태다. 교착 상태가 없는 해법은 여럿이다.

monitor DiningPhilosophers {
  enum { THINKING, HUNGRY, EATING } state[5];
  condition self[5];
 
  pickup(i):  state[i] = HUNGRY;  test(i);
              if (state[i] != EATING) self[i].wait();
  putdown(i): state[i] = THINKING;
              test((i + 4) % 5);  test((i + 1) % 5);   // 양옆이 이제 먹을 수 있나
  test(i):    if (state[(i+4)%5] != EATING && state[i] == HUNGRY && state[(i+1)%5] != EATING)
                  { state[i] = EATING;  self[i].signal(); }
}

모니터 해법은 교착 상태가 없지만, 양옆이 번갈아 먹으면 가운데 철학자가 계속 굶을 수 있어 기아까지 막지는 못한다. 교착 상태 쪽의 해석은 교착 상태에 있다.

모니터 (Monitor)

세마포어는 임계 구역마다 P·V를 직접 짝지어 불러야 한다. 순서를 바꾸거나, 한쪽을 빠뜨리거나, 두 번 부르는 실수를 한 번만 해도 오류가 나고 찾기도 어렵다. 모니터는 공유 데이터와 그 데이터에 접근하는 프로시저를 하나로 묶은 고수준 동기화 구조다. 모니터 안에서는 한 번에 하나의 프로세스만 활동하도록 언어 차원에서 보장하므로, 프로그래머가 직접 lock을 걸 필요가 없다. Java의 synchronized가 대표적인 예다.

모니터는 두 종류의 큐로 두 가지 동기화를 모두 제공한다. 두 큐는 서로 다른 큐다.

• x.wait(): 부른 프로세스를 조건 변수 x의 큐에 넣고 대기 상태로 만든다. 모니터 안을 비워 주므로 다른 프로세스가 들어올 수 있다.
• x.signal(): x의 큐에서 기다리던 프로세스 하나를 깨운다. 기다리는 프로세스가 없으면 아무 일도 하지 않는다(값을 기억하는 세마포어의 V와 다른 점이다).

실행 순서 제어는 세마포어와 같은 발상이다. 나중에 실행할 A는 조건이 갖춰지지 않았으면 x.wait()로 멈추고, 먼저 실행할 B는 일을 마친 뒤 x.signal()로 A를 깨운다.

signal()을 부른 쪽과 깨어난 쪽이 동시에 모니터 안에 있을 수는 없으므로 둘 중 하나가 양보해야 한다.

Java와 POSIX 조건 변수는 Signal and Continue 방식이다. Java 모니터와 pthread의 대응은 POSIX 스레드와 동기화 API에 있다.

세 도구 비교

데이터베이스도 같은 문제를 로킹·MVCC 같은 병행 제어로 푼다(트랜잭션).

핵심 정리

• 경쟁 상태 = 공유 데이터에 동시 접근해 실행 순서에 따라 결과가 달라지는 것.
• OS에서는 인터럽트, 시스템 콜 중 선점, 멀티프로세서 때문에 커널 데이터에서 경쟁 상태가 생긴다. 선점형 커널은 스핀락과 선점 끄기로 지킨다.
• 임계 구역 해결 조건: 상호 배제, 진행, 유한 대기.
• 세마포어 P는 획득(없으면 대기), V는 반납(대기자가 있으면 깨움). Busy-wait 대신 block/wakeup으로 CPU 낭비를 줄인다.

관련 노트: POSIX 스레드와 동기화 API, 교착 상태, 동시성·병렬·비동기·논블로킹과 동시성 모델