상호 배제

상호 배제는 여럿이 함께 쓰는 값을 한 번에 하나만 만지게 막는 일입니다. 한쪽이 쓰는 동안 나머지는 차례를 기다립니다. 두 요청이 같은 값을 동시에 고쳐서 값이 꼬이는 일을 이렇게 막습니다. 흔히 락이 이 일을 맡습니다.

상세

회의에서 발언 막대를 쥔 사람만 말합니다. 말을 마치면 막대를 내려놓습니다. 다음 사람이 그 막대를 집어 듭니다. 막대가 하나뿐이라 두 사람이 한꺼번에 말하는 일은 없습니다.

이 절은 방문 수 카운터 하나를 두 요청이 동시에 올리는 코드로 상호 배제를 봅니다. 먼저 그 코드를 읽는 데 필요한 두 낱말, 실행 흐름과 공유 자원을 풉니다.

실행 흐름은 코드를 한 줄씩 따라가는 실행 하나입니다. 실행 흐름 하나를 돌리는 단위가 스레드입니다. 한 프로그램은 스레드를 여럿 둘 수 있습니다. 웹 서버는 흔히 요청마다 스레드를 하나씩 붙이므로 같은 코드를 여러 흐름이 동시에 지나갑니다.

여러 흐름이 함께 쓰는 것을 공유 자원이라고 부릅니다. 메모리 위의 변수, 파일, 데이터베이스의 한 행이 모두 공유 자원이 될 수 있습니다.

상호 배제(mutual exclusion)는 여러 실행 흐름이 함께 쓰는 공유 자원을 한 번에 한 흐름만 쓰게 막는 성질입니다. 「상호」는 흐름들이 서로를 밀어낸다는 뜻입니다. 한 흐름이 자원을 쓰는 동안 다른 흐름은 모두 밖에서 기다립니다. 회의의 발언 막대 역할을 하는 것이 뒤에서 볼 락입니다.

카운터가 덜 오르는 까닭

아래 코드는 필드 count 를 하나 올립니다. 두 스레드가 이 메서드를 한 번씩 부른다고 해 봅시다.

int count = 0;

void hit() {
    count++;
}

count++ 는 한 줄이지만 세 단계로 나뉘어 실행됩니다. 값을 읽고, 1을 더하고, 다시 씁니다. 풀어 쓰면 아래와 같습니다.

int tmp = count;  // 읽기 · 0
tmp = tmp + 1;    // 더하기 · 1
count = tmp;      // 쓰기 · 1

흐름이 하나면 두 번 부른 뒤 count 는 2입니다. 두 스레드가 겹치면 아래처럼 흘러갈 수 있습니다.

sequenceDiagram
    participant A as 스레드 A
    participant C as count
    participant B as 스레드 B
    A->>C: 읽기
    C-->>A: 0
    B->>C: 읽기
    C-->>B: 0
    A->>C: 1 쓰기
    B->>C: 1 쓰기
    Note over C: 두 번 올렸는데 1

두 스레드가 같은 옛값 0을 읽었습니다. 둘 다 1을 쓰므로 한 번의 증가가 사라집니다. 이렇게 앞의 쓰기가 뒤의 쓰기에 덮여 없어지는 일을 갱신 손실이라고 부릅니다.

결과가 흐름이 겹친 순서에 따라 달라지는 상태를 경쟁 상태라고 합니다. 이 버그는 두 스레드가 읽기와 쓰기 사이에서 딱 맞게 겹칠 때만 터집니다. 그래서 테스트에서는 잘 안 보이고 요청이 몰릴 때 드물게 나타납니다.

막으려면 읽기부터 쓰기까지를 한 흐름이 끝낼 때까지 남이 못 들어오게 해야 합니다. 이 세 단계처럼 한 번에 하나만 지나가야 하는 코드 구간을 임계 구역이라고 부릅니다. 임계 구역은 규칙을 걸 코드 구간입니다. 상호 배제는 그 구간에 거는 규칙입니다.

락으로 만드는 상호 배제

상호 배제를 만드는 가장 흔한 장치가 락입니다. 임계 구역에 들어가기 전에 락을 잡습니다. 나올 때는 락을 놓습니다. 락을 쥔 흐름이 있으면 다른 흐름은 잡으려다 기다립니다.

자바에서는 synchronized 블록이 이 일을 합니다. 블록 앞뒤에서 락을 잡고 놓는 코드를 따로 적지 않아도 됩니다.

final Object lock = new Object();

void hit() {
    synchronized (lock) { // 잡기
        count++;
    }                     // 놓기
}

블록에 들어갈 때 lock 객체의 락을 잡습니다. 블록을 나갈 때 그 락을 놓습니다. 이제 두 스레드가 동시에 불러도 한쪽이 블록을 다 지나간 뒤에 다른 쪽이 들어갑니다. 두 번 부르면 count 는 언제나 2입니다.

락 말고도 상호 배제를 만드는 장치는 여럿입니다. 장치는 주로 못 들어간 흐름이 어떻게 기다리는지로 갈립니다. 기다리는 방법은 잠드는 것과 계속 확인하는 것 둘입니다.

잠든 흐름은 기다리는 동안 프로세서를 다른 흐름에 내줍니다. 락이 풀리면 운영체제가 그 흐름을 깨웁니다. 계속 확인하는 흐름은 잠들지 않고 락이 풀렸는지 되풀이해 봅니다.

세마포어는 들여보낼 수를 세는 값입니다. 흐름이 하나 들어갈 때마다 수를 하나 줄입니다. 수가 0이면 뒤에 온 흐름은 잠들어 기다립니다. 처음 수를 1로 두면 한 번에 한 흐름만 들어가므로 상호 배제가 됩니다.

뮤텍스라는 이름은 mutual exclusion 을 줄인 말입니다. 이름부터 상호 배제를 하려고 만든 장치라는 뜻입니다.

잠드는 방식은 깨어날 때 문맥 교환이 듭니다. 문맥 교환은 운영체제가 돌던 흐름을 멈추고 다른 흐름으로 갈아타는 일입니다.

계속 다시 확인하며 기다리는 것을 바쁜 대기라고 부릅니다. 문맥 교환은 없지만 기다리는 동안 프로세서를 헛돌립니다. 그래서 곧 들어갈 수 있는 짧은 구간에만 씁니다.

락이 기대는 원자적 연산

락도 결국 메모리 위의 값 하나로 만듭니다. 「지금 누가 쥐고 있나」를 적어 두는 값입니다. 이 소절은 그 값을 평범한 변수로 만들면 무엇이 깨지는지 봅니다. 이어서 프로세서가 주는 명령으로 고칩니다.

아래는 평범한 boolean 으로 만든 락입니다.

boolean busy = false;

void lock() {
    while (busy) { }  // 빌 때까지 돈다
    busy = true;      // 차지한다
}

이 락은 앞의 카운터와 같은 병을 앓습니다. 두 스레드가 동시에 busy 를 읽으면 둘 다 false 를 봅니다. 둘 다 반복을 빠져나와 true 를 씁니다. 그리고 둘 다 임계 구역에 들어갑니다. 확인과 차지 사이에 틈이 있어서입니다.

틈을 없애려면 확인과 차지를 한 동작으로 묶어야 합니다. 도중에 남이 끼어들 수 없는 동작을 원자적 연산이라고 부릅니다. 프로세서는 원자적 연산을 명령 하나로 제공합니다.

대표가 CAS(Compare-And-Swap, 비교 후 교체)입니다. 「지금 값이 기대한 값과 같을 때만 새 값으로 바꿔라」를 명령 하나로 처리합니다. 결과로는 바꿨는지를 돌려줍니다. 자바에서는 AtomicBoolean 의 compareAndSet 이 이 명령을 씁니다.

var busy = new AtomicBoolean(false);

busy.compareAndSet(false, true); // true
busy.compareAndSet(false, true); // false

첫 호출은 값이 false 였으므로 true 로 바꾸고 성공을 돌려줍니다. 둘째 호출은 값이 이미 true 라서 아무것도 안 바꾸고 실패를 돌려줍니다. 두 스레드가 동시에 불러도 성공하는 쪽은 하나뿐입니다.

이 성공 여부를 반복문에 넣으면 틈이 없는 락이 됩니다. 앞 표의 스핀락이 이 모양입니다.

void lock() {
    while (!busy.compareAndSet(false, true)) { }
}

void unlock() {
    busy.set(false);
}

뮤텍스와 세마포어도 밑바닥에서는 이런 원자적 연산에 기댑니다. 운영체제는 그 위에 기다리는 흐름을 재우고 깨우는 기능을 얹습니다.

상호 배제만으로는 모자란 점

상호 배제만 지키기는 쉽습니다. 아무도 안 들여보내면 두 흐름이 동시에 들어갈 일도 없습니다. 그래서 쓸 만한 상호 배제는 조건 둘을 더 채웁니다. 진행 조건과 한정 대기입니다.

첫째 조건은 진행 조건입니다. 구간이 비어 있고 들어가려는 흐름이 있으면 그중 하나는 결국 들어가야 한다는 조건입니다. 아무도 안 들여보내는 방법은 이 조건에서 걸러집니다.

진행 조건이 깨지는 대표가 데드락입니다. 두 흐름이 서로 상대가 쥔 락을 기다리며 둘 다 멈춥니다. 구간 앞에 흐름이 있는데 아무도 들어가지 못합니다.

서로 양보만 되풀이하다 둘 다 못 들어가는 라이브락도 진행 조건을 깹니다. 데드락과 달리 흐름은 멈추지 않고 계속 움직입니다. 그래도 구간에 들어가는 흐름은 없습니다.

둘째 조건은 한정 대기입니다. 들어가겠다고 한 흐름은 남에게 정해진 횟수까지만 순서를 내준다는 조건입니다. 한 흐름이 끝없이 밀리지 않게 막습니다.

한정 대기가 깨지면 기아가 생깁니다. 다른 흐름은 잘 드나듭니다. 한 흐름만 계속 순서에서 밀립니다. 기다린 순서대로 들여보내는 공정 락은 이 기아를 막습니다.

세 조건과 각각이 깨질 때 생기는 일을 모으면 아래와 같습니다.

데드락의 첫째 조건

데드락이 나려면 네 조건이 함께 서야 합니다. 상호 배제가 그 첫째입니다. 자원을 한 번에 하나만 쥘 수 있어야 자원을 쥔 흐름이 남을 막아 세울 수 있기 때문입니다.

넷 중 하나만 깨도 데드락은 나지 않습니다. 그런데 상호 배제는 깨기 어려운 조건입니다. 상호 배제를 걷으면 앞에서 본 갱신 손실이 돌아오기 때문입니다.

그래서 데드락은 대개 다른 조건을 깨서 막습니다. 흔한 방법은 모든 흐름이 락을 늘 같은 순서로 잡게 하는 것입니다. 그러면 고리가 생기지 않아 순환 대기가 사라집니다.

락이 함께 넘겨 주는 값

상호 배제는 「동시에 못 들어간다」만 약속하는 것처럼 보입니다. 락에는 일이 하나 더 붙어 있습니다. 앞 흐름이 구간 안에서 쓴 값을 다음 흐름이 보게 해 주는 일입니다.

컴파일러와 프로세서는 속도를 내려고 메모리 읽기와 쓰기의 순서를 바꾸기도 합니다. 쓴 값을 잠시 붙들고 있다가 늦게 내보내기도 합니다. 그래서 한 스레드가 쓴 값이 다른 스레드에게 바로 안 보일 수 있습니다.

어떤 쓰기가 어떤 읽기에 보이는지를 정한 규약을 메모리 모델이라고 부릅니다. 이 규약에서 락은 특별한 대접을 받습니다. 락을 놓는 일과 같은 락을 다음에 잡는 일 사이에는 순서가 보장됩니다.

놓기 전에 쓴 값은 다음에 같은 락을 잡은 흐름에게 전부 보입니다. 자바는 이 순서를 happens-before 관계로 부릅니다. 그래서 synchronized 안에서 고친 필드는 다음에 같은 락을 잡은 스레드가 최신 값으로 읽습니다.

쓰는 쪽만 락을 잡고 읽는 쪽은 안 잡으면 이 보장이 없습니다. 읽는 스레드는 옛값을 계속 볼 수 있습니다. 읽기도 같은 락 안에서 해야 하는 까닭입니다.

순서가 바뀌는 일은 락 없이 만든 상호 배제도 깨뜨립니다. 원자적 연산 없이 평범한 읽기와 쓰기만으로 상호 배제를 만드는 풀이가 있습니다. 이런 풀이는 코드에 적힌 순서대로 읽고 쓴다고 가정합니다. 순서가 바뀌는 요즘 프로세서에서 그대로 돌리면 두 흐름이 함께 들어갈 수 있습니다.

상호 배제의 대가

임계 구역은 한 번에 한 흐름씩 지나갑니다. 스레드를 늘려도 그 구간을 지나는 속도는 그대로입니다. 늘어난 스레드는 구간 앞에서 줄을 섭니다. 여럿이 한 락을 두고 기다리는 상태를 락 경합이라고 부릅니다.

전체 일 가운데 상호 배제로 묶인 몫이 클수록 스레드를 늘려 얻는 처리량에 천장이 생깁니다. 그 천장을 계산하는 식이 암달의 법칙입니다.

그래서 구간은 짧게 잡습니다. 원격 호출이나 디스크 읽기처럼 오래 걸리는 일을 구간 안에 두지 않습니다. 락을 쥔 채 원격 응답을 기다리면 다른 스레드가 전부 그 응답을 함께 기다리게 됩니다.

락이 필요 없거나 가벼워지는 값

모든 값에 락이 필요한 것은 아닙니다. 아래 표의 위 세 줄은 상호 배제 자체가 필요 없는 값입니다. 아래 두 줄은 상호 배제는 필요하지만 평범한 락보다 가벼운 수단으로 되는 값입니다.

넷째 줄의 카운터는 자바의 AtomicInteger 로 바꾸면 락 없이 맞게 오릅니다. incrementAndGet 이 읽기와 더하기와 쓰기를 원자적 연산 하나로 처리합니다.

var count = new AtomicInteger();

count.incrementAndGet(); // 1
count.incrementAndGet(); // 2

마지막 줄의 읽기-쓰기 락은 두 종류의 흐름을 달리 들입니다. 읽는 흐름은 여럿을 함께 들입니다. 고치는 흐름은 들어갈 때 혼자만 들입니다. 읽기가 많을수록 기다림이 줄어듭니다.

서버 여러 대에 걸친 상호 배제

synchronized 로 잡는 락은 프로세스 하나의 메모리 안에만 있습니다. 프로세스는 실행 중인 프로그램 하나입니다. 같은 애플리케이션을 서버 여러 대에 띄우면 다른 서버의 프로세스는 이 락을 모릅니다.

그래서 모든 서버가 같이 보는 곳에 락을 둡니다. 흔한 방법은 데이터베이스의 행 잠금입니다. 행 잠금은 테이블의 한 행에 거는 락입니다. 한 요청이 잠근 행은 그 요청이 끝날 때까지 다른 요청이 고치지 못합니다.

데이터베이스에서 요청 하나의 끝은 트랜잭션의 끝입니다. 트랜잭션은 여러 읽기와 쓰기를 한 묶음으로 처리하는 단위입니다. BEGIN 으로 열고 COMMIT 으로 닫습니다.

아래는 재고를 확인한 뒤 하나 줄이는 주문 처리입니다. 앞의 카운터처럼 읽기와 쓰기 사이에 틈이 있습니다. 재고가 1개 남았을 때 두 주문이 동시에 1을 읽으면 둘 다 팔 수 있다고 판단합니다.

BEGIN;
SELECT stock FROM item
 WHERE id = 7 FOR UPDATE;  -- 1
-- stock > 0 일 때만 다음 줄
UPDATE item SET stock = stock - 1
 WHERE id = 7;             -- 0
COMMIT;

SELECT ... FOR UPDATE 는 행을 읽을 때 그 행을 잠급니다. 둘째 주문의 SELECT 는 첫째 주문이 COMMIT 할 때까지 기다립니다. 기다린 뒤에는 줄어든 재고 0을 읽고 주문을 거절합니다.

데이터베이스 대신 모든 서버가 접속하는 별도 저장소에 「누가 락을 쥐고 있나」를 적는 방법도 있습니다. 이 방법은 분산 락이라고 부릅니다.

관련 항목

상호 배제를 거는 코드 구간과 함께 채울 조건

임계 구역 · 임계 구역 문제 · 진행 조건 · 한정 대기

상호 배제를 만드는 장치

락 · 뮤텍스 · 스핀락 · 세마포어 · 모니터 · 읽기-쓰기 락 · 공정 락 · 조건 변수

상호 배제를 떠받치는 프로세서 명령

원자적 연산 · CAS · test-and-set · 메모리 배리어

상호 배제를 소프트웨어로 푼 알고리즘

피터슨 알고리즘 · 데커 알고리즘 · 빵집 알고리즘

상호 배제가 없거나 어긋날 때 나는 오류

경쟁 상태 · 데이터 경쟁 · 갱신 손실 · 데드락 · 라이브락 · 기아 · 우선순위 역전

상호 배제와 함께 데드락을 세우는 조건

점유한 채 대기 · 비선점 · 순환 대기

상호 배제 없이 공유를 다루는 수단

불변 객체 · 스레드 로컬 · 메시지 전달 · 액터 모델 · 락 프리 · 낙관적 잠금

상호 배제가 치르는 비용

락 경합 · 암달의 법칙 · 문맥 교환 · 바쁜 대기 · 락 세분화

락이 함께 지키는 메모리 규약

메모리 모델 · happens-before · 가시성 · volatile

서버 여러 대에 걸친 상호 배제 수단

행 잠금 · 비관적 잠금 · 분산 락 · 트랜잭션 · 분산 상호 배제

상호 배제가 놓이는 실행 환경

동시성 · 병렬성 · 스레드 · 프로세스 · 공유 자원 · 운영체제 · 커널