동기화와 교착 상태

왜 동기화가 필요한가

이전 글에서 스레드가 Heap 메모리를 공유한다고 했습니다. 이 공유가 동시에 일어나면 문제가 됩니다.

// 두 스레드가 동시에 실행한다고 가정
let counter = 0;

// 스레드 A         // 스레드 B
counter++;          counter++;
// 기대값: 2, 실제값: 1 또는 2 (비결정적)

counter++는 하나의 연산처럼 보이지만, CPU 레벨에서는 세 단계입니다.

메모리에서 counter 값을 레지스터로 읽기 (LOAD)
레지스터 값에 1 더하기 (ADD)
레지스터 값을 메모리에 쓰기 (STORE)

두 스레드의 세 단계가 겹치면 (interleave) 결과가 달라집니다. 이것이 레이스 컨디션입니다. 실행 순서에 따라 결과가 달라지는 상황입니다.

시간    스레드 A          스레드 B          counter (메모리)
 t0     LOAD (0)                            0
 t1                       LOAD (0)          0
 t2     ADD  (0+1=1)                        0
 t3                       ADD  (0+1=1)      0
 t4     STORE (1)                           1
 t5                       STORE (1)         1  <-- 기대값 2, 실제값 1

임계 구역 (Critical Section)

공유 자원에 접근하는 코드 영역을 임계 구역 이라 합니다. 임계 구역 문제를 해결하려면 세 가지 조건을 만족해야 합니다.

조건	의미
상호 배제 (Mutual Exclusion)	한 번에 하나의 스레드만 임계 구역에 진입
진행 (Progress)	임계 구역에 아무도 없으면 대기 중인 스레드가 진입 가능
한정된 대기 (Bounded Waiting)	진입 요청 후 무한히 기다리지 않음

이 세 조건을 동시에 만족하는 것이 동기화 도구의 목표입니다.

뮤텍스 (Mutex)

뮤텍스 는 "Mutual Exclusion"의 줄임말로, 가장 기본적인 동기화 도구입니다. 열쇠가 하나뿐인 화장실과 같습니다 -- 열쇠를 가진 사람만 들어갈 수 있고, 나올 때 열쇠를 반환합니다.

뮤텍스 동작:
  lock()      임계 구역에 진입 (열쇠 획득)
  [임계 구역]  공유 자원 접근
  unlock()    임계 구역에서 퇴장 (열쇠 반환)

핵심은 lock()과 unlock() 사이에 하나의 스레드만 존재한다는 것입니다.

// 의사 코드
const mutex = new Mutex();

// 스레드 A
mutex.lock();
counter++;        // 임계 구역: 안전하게 접근
mutex.unlock();

// 스레드 B
mutex.lock();     // A가 unlock할 때까지 대기
counter++;
mutex.unlock();

뮤텍스 구현에서 중요한 점은 lock() 자체가 원자적 (atomic) 이어야 한다는 것입니다. 하드웨어 수준에서 test-and-set, compare-and-swap (CAS) 같은 원자적 명령어를 사용합니다.

세마포어 (Semaphore)

세마포어는 뮤텍스를 일반화한 것입니다. 뮤텍스가 "1명만 입장"이라면, 세마포어는 "N명까지 입장" 을 허용합니다.

내부적으로 정수 카운터를 가지며, 두 가지 원자적 연산으로 제어합니다.

연산	동작
wait() (P 연산)	카운터 > 0이면 카운터--, 0이면 대기
signal() (V 연산)	카운터++, 대기 중인 스레드 깨움

세마포어(N=3): 동시에 3개 스레드까지 허용

  스레드 1: wait() --> 카운터 3->2 --> 진입
  스레드 2: wait() --> 카운터 2->1 --> 진입
  스레드 3: wait() --> 카운터 1->0 --> 진입
  스레드 4: wait() --> 카운터 0   --> 대기 (블로킹)

  스레드 1: signal() --> 카운터 0->1 --> 스레드 4 깨움

바이너리 세마포어 (N=1)는 뮤텍스와 유사하지만, 소유권 개념이 없다는 차이가 있습니다. 뮤텍스는 lock한 스레드만 unlock할 수 있지만, 세마포어는 어떤 스레드든 signal()을 호출할 수 있습니다.

교착 상태 (Deadlock)

동기화 도구를 잘못 사용하면 교착 상태가 발생합니다. 두 개 이상의 프로세스가 서로 상대방이 가진 자원을 기다리며 영원히 진행하지 못하는 상태입니다.

아래 시각화에서 교착 상태가 단계별로 형성되는 과정을 확인하세요. 자원 할당 그래프(RAG)에서 사이클이 형성되면 교착 상태입니다.

자원 할당단계 1 / 5

자원 할당 그래프 (RAG)

P1대기 중

R1사용 가능

R2사용 가능

P2대기 중

교착 상태 4조건 (Coffman)

상호 배제 (Mutual Exclusion)자원은 한 번에 하나의 프로세스만 사용

점유 대기 (Hold and Wait)자원을 보유한 채 다른 자원 대기

비선점 (No Preemption)점유 중인 자원을 강제로 빼앗지 못함

순환 대기 (Circular Wait)프로세스들이 원형으로 자원 대기

두 프로세스(P1, P2)와 두 자원(R1, R2)이 있습니다. 아직 아무도 자원을 점유하지 않은 초기 상태입니다. 이제 두 프로세스가 서로 다른 순서로 자원을 요청하면 어떤 일이 벌어지는지 관찰합니다.

교착 상태의 4조건 (Coffman 조건)

교착 상태는 다음 네 가지 조건이 동시에 성립할 때 발생합니다. 하나라도 깨뜨리면 교착 상태를 방지할 수 있습니다.

조건	설명	깨뜨리는 방법
상호 배제	자원을 한 프로세스만 사용	공유 가능한 자원 사용 (읽기 전용)
점유 대기	자원을 보유한 채 추가 자원 요청	필요한 자원을 한번에 모두 요청
비선점	점유 자원을 강제로 빼앗지 못함	우선순위 높은 프로세스가 선점
순환 대기	프로세스들이 원형으로 대기	자원에 순서 번호를 부여, 오름차순으로만 요청

식사하는 철학자 문제

교착 상태의 대표적인 예시입니다. 5명의 철학자가 원형 테이블에 앉아 있고, 각자 왼쪽과 오른쪽에 포크가 하나씩 있습니다. 식사하려면 양쪽 포크 두 개가 필요합니다.

P0
     F4      F0
   P4          P1
     F3      F1
         P3
       F2
         P2

  P = 철학자, F = 포크
  모든 철학자가 동시에 왼쪽 포크를 집으면 --> 교착 상태!

모든 철학자가 동시에 왼쪽 포크를 집으면, 모두 오른쪽 포크를 기다리며 아무도 식사하지 못합니다. 이것이 순환 대기의 전형적인 예입니다.

해결 방법:

비대칭 해법 : 짝수 번 철학자는 왼쪽 먼저, 홀수 번 철학자는 오른쪽 먼저 집음 (순환 대기 방지)
세마포어 : 동시에 식사할 수 있는 철학자 수를 N-1명으로 제한
뮤텍스 : 포크를 집는 행위 자체를 임계 구역으로 보호

교착 상태 해결 전략

OS는 세 가지 전략으로 교착 상태에 대응합니다.

1. 예방 (Prevention) : Coffman 4조건 중 하나를 원천 차단합니다. 가장 실용적인 방법은 순환 대기 방지 -- 모든 자원에 번호를 매기고, 항상 번호가 작은 자원부터 요청하도록 강제합니다.

예방: 자원 순서 강제
  R1 < R2 < R3

  P1: lock(R1) --> lock(R2)   OK (오름차순)
  P2: lock(R1) --> lock(R2)   OK (오름차순)
  --> 순환 대기 불가능!

2. 회피 (Avoidance) : 자원을 할당하기 전에 시스템이 안전한 상태를 유지하는지 확인합니다. 대표적인 알고리즘은 은행원 알고리즘 (Banker's Algorithm) 입니다.

은행원 알고리즘은 각 프로세스의 최대 자원 요구량을 미리 알고 있을 때, 할당 후에도 "안전 순서 (safe sequence)"가 존재하는지 확인합니다. 안전 순서가 없으면 할당을 거부합니다.

3. 탐지 및 복구 (Detection & Recovery) : 교착 상태를 허용하되, 주기적으로 탐지하고 발견되면 복구합니다.

탐지 : 자원 할당 그래프에서 사이클 탐색 (DFS)
복구 : 프로세스 강제 종료 또는 자원 선점 (rollback)

전략	비용	자원 활용도	실용성
예방	낮음	낮음 (보수적)	단순하지만 제약 큼
회피	중간	중간	최대 자원 요구량 필요
탐지/복구	높음	높음	복구 비용 발생

대부분의 현대 OS (Linux, Windows)는 타조 알고리즘 -- 교착 상태를 무시합니다. 교착 상태가 발생할 확률이 낮고, 예방/회피 비용이 더 크기 때문입니다. 대신 사용자가 교착 상태를 직접 해결합니다 (프로세스 강제 종료).

실무에서의 연결

Atomics.wait / Atomics.notify = 세마포어

JavaScript에서 SharedArrayBuffer와 Atomics를 사용하면 스레드 간 동기화가 가능합니다. Atomics.wait()와 Atomics.notify()는 세마포어의 wait/signal과 동일한 역할을 합니다.

// Worker A: 공유 메모리에 데이터를 쓰고 알림
const shared = new SharedArrayBuffer(4);
const view = new Int32Array(shared);

view[0] = 42;                        // 데이터 쓰기
Atomics.store(view, 0, 42);          // 원자적 쓰기
Atomics.notify(view, 0, 1);          // signal(): 대기 중인 워커 깨움

// Worker B: 데이터가 준비될 때까지 대기
Atomics.wait(view, 0, 0);            // wait(): 값이 0인 동안 대기
const data = Atomics.load(view, 0);  // 원자적 읽기 --> 42

Atomics.wait()은 값이 기대값과 같으면 스레드를 블로킹하고, Atomics.notify()가 호출될 때까지 대기합니다. OS의 세마포어와 같은 원리입니다.

SharedArrayBuffer 레이스 컨디션

SharedArrayBuffer를 일반 읽기/쓰기로 접근하면 레이스 컨디션이 발생합니다. 반드시 Atomics API를 사용해야 합니다.

// 잘못된 방법: 레이스 컨디션
const view = new Int32Array(shared);
view[0] = view[0] + 1;              // LOAD, ADD, STORE가 원자적이지 않음

// 올바른 방법: 원자적 연산
Atomics.add(view, 0, 1);            // 원자적으로 증가

Atomics.add(), Atomics.sub(), Atomics.compareExchange() 등은 하드웨어 수준에서 원자성을 보장합니다. 이것은 CPU의 compare-and-swap (CAS) 명령어를 직접 활용합니다.

데이터베이스 락

데이터베이스에서도 동일한 동기화 문제가 존재합니다.

DB 개념	OS 대응 개념
Row Lock (SELECT ... FOR UPDATE)	뮤텍스
Read Lock / Write Lock	읽기-쓰기 락 (rwlock)
트랜잭션 격리 수준	임계 구역 범위
Deadlock Detection	자원 할당 그래프 사이클 탐지

-- 트랜잭션 A
BEGIN;
UPDATE accounts SET balance = balance - 100 WHERE id = 1;  -- Row 1 Lock
UPDATE accounts SET balance = balance + 100 WHERE id = 2;  -- Row 2 Lock 대기

-- 트랜잭션 B (동시에 실행)
BEGIN;
UPDATE accounts SET balance = balance - 50 WHERE id = 2;   -- Row 2 Lock
UPDATE accounts SET balance = balance + 50 WHERE id = 1;   -- Row 1 Lock 대기

-- 교착 상태 발생! DB 엔진이 탐지하고 하나를 rollback

대부분의 DB (MySQL InnoDB, PostgreSQL)는 교착 상태 탐지 알고리즘을 내장하고 있어, 교착 상태 발생 시 하나의 트랜잭션을 자동으로 rollback합니다.

다음 단계

이 글에서는 임계 구역, 뮤텍스, 세마포어, 교착 상태를 다뤘습니다. 동기화는 멀티스레드 프로그래밍의 핵심 난제이며, JavaScript의 Atomics API도 결국 같은 원리 위에 있습니다. 다음 글에서는 OS가 메모리를 관리하는 방법 -- 가상 메모리, 페이징, 세그멘테이션을 다루겠습니다.