컴퓨터공학 300 주제 시리즈의 107번째 글이다. 전체 지도는 여기.

한 줄 요약

경쟁 상태는 공유 자원에 대한 여러 실행 흐름의 접근 순서에 따라 결과가 달라지는 버그이고, 이를 막으려면 공유 자원을 다루는 코드 구간(임계 구역)을 한 번에 하나만 실행하도록 상호 배제해야 한다.

왜 필요한가

count = count + 1 은 한 줄이지만 CPU 에게는 한 동작이 아니다. 메모리에서 읽고, 레지스터에서 더하고, 다시 메모리에 쓴다. 두 스레드가 이 세 단계를 섞어 실행하면 한 번의 증가가 사라진다.

이런 버그는 다루기 까다롭다.

  • 재현이 안 된다: 타이밍에 따라 백 번에 한 번, 부하가 높을 때만 나타난다.
  • 테스트를 통과한다: 개발 PC 에서는 코어가 적거나 부하가 낮아 겹치지 않는다.
  • 디버거를 붙이면 사라진다: 실행 속도가 달라져 겹침이 없어진다(하이젠버그).

재고 차감, 포인트 적립, 좌석 예약처럼 돈이 걸린 로직에서 경쟁 상태는 곧 장애이고 사고다. 동시성의 첫 단추가 이 개념이다.

핵심 개념

갱신 손실이 생기는 순서

공유 변수 count = 5, 두 스레드가 각각 1 을 더한다.

시점 스레드 A 스레드 B 메모리의 count
1 r1 = count (5)   5
2   r2 = count (5) 5
3 r1 = r1 + 1 (6)   5
4   r2 = r2 + 1 (6) 5
5 count = r1   6
6   count = r2 6 (기대값 7)

A 의 갱신이 B 에 의해 덮여 사라졌다. 이 유형을 갱신 손실(lost update) 이라 부른다. 같은 패턴이 데이터베이스 트랜잭션에서도 똑같이 나타난다.

경쟁 상태의 대표 유형

유형 모양 예
읽기-수정-쓰기 읽고 계산해서 쓴다 카운터 증가, 잔액 차감
확인 후 행동(check-then-act) 조건을 확인하고 그에 따라 행동한다 “파일이 없으면 만든다”, “재고가 있으면 판다”
지연 초기화 아직 없으면 만든다 싱글턴을 두 번 생성

확인 후 행동 유형은 보안 문제로도 이어진다. 권한을 확인한 시점과 파일을 연 시점 사이에 공격자가 심볼릭 링크를 바꿔치기하는 TOCTOU(Time-Of-Check to Time-Of-Use) 취약점이 대표적이다.

데이터 경쟁과 경쟁 상태

두 용어는 겹치지만 같지 않다.

  • 데이터 경쟁(data race): 두 스레드가 동기화 없이 같은 메모리 위치에 접근하고 그중 하나 이상이 쓰기인 경우. C/C++ 메모리 모델에서는 정의되지 않은 동작이다.
  • 경쟁 상태(race condition): 실행 순서에 따라 프로그램의 결과가 잘못될 수 있는 논리적 결함.

모든 접근을 원자적으로 만들어 데이터 경쟁을 없애도, “잔액 확인”과 “출금”이 따로 원자적이면 그 사이에 끼어들 수 있으므로 경쟁 상태는 남는다.

임계 구역 문제의 세 조건

임계 구역(critical section)은 공유 자원을 다루어서 동시에 둘 이상이 실행하면 안 되는 코드 구간이다. 올바른 해법은 세 조건을 만족해야 한다.

  1. 상호 배제(mutual exclusion): 한 번에 하나만 임계 구역에 있다.
  2. 진행(progress): 아무도 임계 구역에 없으면, 들어가려는 쪽 중 하나는 유한 시간 안에 들어갈 수 있어야 한다.
  3. 한정 대기(bounded waiting): 들어가려고 기다리는 쪽이 무한히 추월당하지 않는다.
while (true) {
    [진입 구역]     락 획득
    [임계 구역]     공유 자원 접근
    [퇴출 구역]     락 해제
    [나머지 구역]   지역 작업
}

하드웨어의 도움: 원자적 명령어

소프트웨어만으로 상호 배제를 구현하는 피터슨 알고리즘 같은 고전 해법도 있지만, 현대 CPU 는 명령어 재배치 때문에 메모리 배리어 없이는 이를 보장하지 않는다. 그래서 실제 락은 하드웨어의 원자적 명령어 위에 만든다.

  • Test-and-Set: 값을 읽고 1 로 쓰는 것을 한 번에 한다.
  • Compare-and-Swap(CAS): “메모리 값이 기대값과 같으면 새 값으로 바꾼다”를 원자적으로 한다. x86 의 lock cmpxchg.
  • Fetch-and-Add: 더하고 이전 값을 돌려준다. x86 의 lock xadd.

이 명령어들로 스핀락, 뮤텍스, 원자 카운터를 만든다(다음 글).

직접 해 보기

프로세스 4개가 공유 메모리의 정수를 각각 20만 번 증가시킨다. multiprocessing.Value(..., lock=False) 는 자동 락이 없는 공유 정수라서, 서로 다른 코어에서 진짜로 동시에 실행되며 갱신 손실이 드러난다.

from multiprocessing import Process, Value, Lock

N, WORKERS = 200_000, 4

def unsafe(counter):
    for _ in range(N):
        counter.value += 1            # 읽기 -> 더하기 -> 쓰기 (세 단계)

def safe(counter, lock):
    for _ in range(N):
        with lock:                    # 임계 구역
            counter.value += 1

def run(target, *extra):
    counter = Value("i", 0, lock=False)   # 공유 메모리의 정수, 자동 락 없음
    ps = [Process(target=target, args=(counter, *extra)) for _ in range(WORKERS)]
    for p in ps: p.start()
    for p in ps: p.join()
    return counter.value

if __name__ == "__main__":
    print("기대값        :", N * WORKERS)
    for i in range(3):
        print(f"락 없음 #{i+1}    :", run(unsafe))
    print("락 사용       :", run(safe, Lock()))

4코어 리눅스에서의 결과다.

기대값        : 800000
락 없음 #1    : 259122
락 없음 #2    : 301686
락 없음 #3    : 339489
락 사용       : 800000

락이 없으면 80만 번 중 절반 이상이 사라지고, 실행할 때마다 값이 다르다. 락을 쓰면 항상 정확하다. 대신 락 버전은 눈에 띄게 느리다. 정확성을 위해 병렬성을 일부 포기한 것이다. 이 예제가 프로세스를 쓴 이유는 CPython 스레드는 GIL 때문에 이런 겹침이 드물게만 나타나 관찰하기 어렵기 때문이다. 드물게 나타난다는 것이 안전하다는 뜻은 아니다.

현업에서는

  • 데이터베이스에서의 갱신 손실: SELECT stock 후 애플리케이션에서 계산해 UPDATE stock = ? 하면 위 표와 똑같은 일이 생긴다. UPDATE ... SET stock = stock - 1 WHERE stock > 0 처럼 한 문장으로 원자화하거나, SELECT ... FOR UPDATE 로 행 잠금을 잡거나, 버전 컬럼으로 낙관적 잠금을 쓴다.
  • 분산 환경의 확인 후 행동: 파드가 여러 개인 서비스에서 “이미 처리했는지 확인하고 처리” 로직은 파드 간 경쟁이 된다. 프로세스 내부 락은 소용없고 DB 유니크 제약, 멱등 키, 분산 락 같은 외부 장치가 필요하다.
  • 쿠버네티스의 낙관적 동시성: API 서버의 모든 객체는 resourceVersion 을 가진다. 오래된 버전을 기준으로 수정하면 409 Conflict 가 나고, 컨트롤러는 최신 객체를 다시 읽어 재시도한다. CAS 를 API 수준에서 구현한 것이다.
  • 도구: Go 의 -race, C/C++ 의 ThreadSanitizer 는 실행 중 데이터 경쟁을 탐지한다. 테스트를 이 옵션으로 돌리는 것이 재현 안 되는 버그를 잡는 가장 싼 방법이다.

확인 문제

  1. x += 1 이 원자적이지 않은 이유를 CPU 동작 단계로 설명하라.
  2. 임계 구역 해법이 만족해야 하는 세 조건을 쓰라.
  3. “파일이 없으면 생성” 로직에서 경쟁 상태가 생기는 시나리오를 설명하고, 운영체제 수준의 해결책을 하나 제시하라.
  4. 데이터 경쟁이 없는데도 경쟁 상태가 있을 수 있는 예를 들어라.

풀이

  1. 메모리에서 레지스터로 읽기, 레지스터에서 더하기, 메모리로 쓰기의 세 단계로 이루어지며 그 사이에 다른 스레드가 끼어들 수 있기 때문이다.
  2. 상호 배제, 진행, 한정 대기.
  3. 두 프로세스가 동시에 “없음”을 확인하고 둘 다 생성하면 한쪽이 다른 쪽 내용을 덮는다. open() 에 O_CREAT | O_EXCL 을 주면 확인과 생성이 커널 안에서 원자적으로 처리되어 한쪽만 성공한다.
  4. 잔액 읽기와 잔액 쓰기를 각각 원자적으로 해도, 읽기와 쓰기 사이에 다른 출금이 끼어들면 잔액이 음수가 될 수 있다. 개별 접근이 아니라 “확인-출금” 전체를 하나의 임계 구역으로 묶어야 한다.

더 읽을거리 (References)