운영체제 기본/동시성

목차 · 이전: 프로세스와 스레드 · 다음: 가상 메모리

함께 진행하는 일과 동시에 실행하는 일

동시성(Concurrency)은 여러 작업의 진행 기간이 겹치는 성질이다. 병렬성(Parallelism)은 여러 작업이 실제로 같은 순간에 실행되는 성질이다. CPU 코어가 하나여도 스케줄러가 작업을 번갈아 실행하면 동시성이 생긴다. 코어가 여러 개면 병렬 실행도 가능하지만, 코어 수가 동시성 문제의 유무를 결정하지는 않는다. 작업 하나가 공유 상태를 바꾸다 멈춘 사이 다른 작업이 그 상태에 접근하는 것만으로 문제가 생긴다.

스레드가 주소 공간을 공유하면 데이터를 복사하거나 전달하는 비용을 줄일 수 있다. 대신 누가 언제 읽고 쓰는지 합의해야 한다. 서로 다른 프로세스도 공유 메모리를 사용하면 같은 문제를 만난다. 공유를 없애고 메시지로 소유권을 넘기면 조정 범위는 줄지만, 전달 비용과 대기열 관리가 생긴다. 동시성 설계는 병렬 실행을 무조건 늘리는 일이 아니라, 공유의 이득과 조정의 비용 사이에서 경계를 정하는 일이다.

실행 순서보다 먼저 정해야 하는 불변식

재고가 한 개 남았고 두 주문을 처리한다고 하자.

남은_수량 = 재고_읽기()
if 남은_수량 > 0:
    재고_쓰기(남은_수량 - 1)
    주문_승인()

A가 1을 읽은 뒤 B도 1을 읽을 수 있다. 이어 A와 B가 각각 0을 쓰고 주문을 승인하면 최종 재고는 0인데 승인된 주문은 두 개다. 각 읽기와 쓰기가 따로는 정확해도 전체 연산은 잘못된다. 이처럼 작업 간 실행 순서에 따라 결과가 잘못되는 문제가 레이스 컨디션(Race Condition)이다. 단계가 서로 끼어드는 실행 순서를 인터리빙(Interleaving)이라고 한다. 한 코어에서 실행을 번갈아도 가능한 순서다.

time | A                  | B                  | stock / approved
-----+--------------------+--------------------+-----------------
1    | read -> 1          |                    | 1 / 0
2    |                    | read -> 1          | 1 / 0
3    | write 0            |                    | 0 / 0
4    | approve            |                    | 0 / 1
5    |                    | write 0            | 0 / 1
6    |                    | approve            | 0 / 2  ERROR

지켜야 할 불변식(Invariant)은 단순히 ‘재고는 음수가 아니다’가 아니다. ‘승인된 주문 수와 남은 재고의 합은 최초 재고와 같다’는 관계까지 필요하다. 여기서는 취소와 입고가 없다고 가정한다. 재고 확인부터 차감과 승인 기록까지 다른 주문 처리와 겹치지 않게 묶어야 한다. 이렇게 보호해야 하는 구간이 임계 구역(Critical Section)이다. 모든 명령 사이에 불변식이 성립할 필요는 없지만, 다른 작업에 상태를 넘겨주는 경계에서는 복구되어 있어야 한다.

락은 출입 제한과 관찰 순서를 함께 만든다

락(Lock)의 한 종류인 뮤텍스(Mutex)로 위 구간을 감싸면 하나의 작업만 들어가게 할 수 있다. 이것이 상호 배제(Mutual Exclusion)다. 단, 재고를 다루는 모든 경로가 같은 락 규칙을 따라야 한다. 쓰기 경로만 잠그고 읽기 경로는 무시한다면 보호가 완성되지 않는다. 락은 데이터에 자동으로 붙는 방패가 아니라 접근자 사이의 약속이다.

락에는 메모리의 가시성과 순서를 연결하는 역할도 있다. 올바른 동기화 규약 아래에서 락을 해제하기 전의 변경은 같은 락을 이어서 획득한 작업에 전달된다. 단순히 실행 시간이 앞섰다는 사실만으로는 이런 관계가 생기지 않는다. 컴파일러와 하드웨어가 허용하는 재배치를 고려한 동기화가 필요하다. 서로 다른 스레드가 같은 메모리 위치에 접근하고 한쪽 이상이 쓰기일 때, 적어도 하나가 비원자적이며 동기화로 순서가 정해지지 않으면 데이터 레이스(Data Race)가 된다. C에서 데이터 레이스는 정의되지 않은 동작을 일으킨다. 반면 앞의 재고 예시처럼 개별 읽기와 쓰기를 원자적으로 만들더라도, 확인과 갱신을 따로 수행하면 전체 결과가 잘못될 수 있다. 레이스 컨디션과 데이터 레이스는 같은 뜻이 아니다.

원자 연산(Atomic Operation)인 증가나 CAS는 하나의 연산이 중간에 쪼개져 관찰되는 문제를 해결한다. 그러나 재고 차감과 승인 기록을 각각 원자적으로 바꿔도 두 필드의 관계가 저절로 보호되지는 않는다. 원자성의 범위와 불변식의 범위가 다르기 때문이다. 여러 값을 하나의 상태로 묶거나 별도의 프로토콜을 설계할 수 있지만, 그 정확성과 실패 시 재시도 비용까지 부담해야 한다.

원자 연산으로 락 만들기

공유 RAM에 놓인 락 변수의 0을 비어 있음, 1을 사용 중이라고 하자. 이 변수는 원자 연산이 요구하는 크기와 정렬 조건을 만족해야 한다. CAS(Compare-and-Swap, 비교 후 교환)는 현재 값이 0일 때만 1로 바꾸는 일을 하나의 원자적 연산으로 수행하고, 성공 여부를 반환한다.

while not compare_exchange_acquire(&lock, 0, 1):
    재시도
재고 확인부터 차감과 승인까지 수행  // 임계 구역
store_release(&lock, 0)

time | A                        | B                       
-----+--------------------------+-------------------------
1    | CAS(0,1): success        |
2    |                          | CAS(0,1): fail
3    | stock=0; approve         | retry
4    | release: lock=0          |
5    |                          | CAS(0,1): success
6    |                          | stock=0; reject; unlock

• x86-64: 공유 메모리 대상의 LOCK CMPXCHG로 CAS를 구현할 수 있다. 단순히 CMPXCHG라고만 쓰면 다중 프로세서에서 필요한 원자성 조건을 빠뜨린다.
• RISC-V RV64: A 확장의 LR/SC로 값을 읽어 비교한 뒤 조건부 저장하고, 저장 실패 시 재시도하여 CAS를 구성할 수 있다. SC는 다른 작업의 값 변경이 없어도 실패할 수 있다. 다른 방법인 AMOSWAP.W.AQ는 1을 무조건 교환하여 이전 값이 0인 작업만 진입시키는 test-and-set 방식이다. 이는 CAS와 같은 명령이 아니다.

원자적 획득만으로 충분하지는 않다. acquire/release는 앞 소유자의 변경을 다음 소유자가 관찰하도록 순서를 연결하며, 컴파일러와 하드웨어 양쪽에서 보장되어야 한다. RISC-V에서는 aq/rl 또는 필요한 FENCE로 순서를 구현한다.

이 스핀락(Spinlock)은 대기 중에도 CPU를 쓰고, 반복적인 원자적 갱신은 캐시 일관성 트래픽을 늘릴 수 있으며, 획득 순서의 공정성을 보장하지 않는다. 이 비용은 아래의 대기 방식과 진행 보장 문제로 이어진다.

기다림에도 비용이 있다

락을 얻지 못했을 때 스핀 방식은 실행을 계속하며 획득 가능 여부를 확인한다. 아주 짧은 기다림이라면 잠들고 다시 실행되는 비용을 피할 수 있다. 반면 대기가 길면 유용한 일을 하지 못하면서 CPU 시간과 전력을 소비한다. 락 소유자가 실행되지 못하는 상황에서는 기다리는 쪽이 바쁘게 실행되어도 해제 시점을 앞당기지 못한다.

블로킹(Blocking) 방식은 기다리는 작업을 재우고 CPU를 다른 작업에 내준다. 대신 대기 등록, 깨우기, 다시 스케줄되는 과정이 필요하다. 따라서 ‘스핀은 빠르고 블로킹은 느리다’가 아니라 예상 대기 시간과 실행 여건을 비교해야 한다. 실제 뮤텍스는 짧게 스핀한 뒤 블로킹하는 전략을 섞을 수도 있다.

락 하나로 큰 구조를 보호하면 규칙이 단순하지만 서로 무관한 작업도 줄을 선다. 락을 세분화하면 병렬 처리 여지는 커지지만 획득 횟수와 관리할 관계도 늘어난다. 임계 구역 안에 오래 걸리는 작업을 넣으면 대기가 늘고, 밖으로 옮기면 그 사이 상태가 바뀌지 않는지 다시 확인해야 한다. 락 범위를 줄이는 최적화는 불변식의 보호 범위를 보존할 때만 의미가 있다.

데드락(Deadlock)

데드락은 작업들이 서로가 제공해야 할 자원이나 사건을 기다려 더 이상 진행하지 못하는 상태다. 여기서는 스레드가 뮤텍스를 보유한 채 다른 뮤텍스를 기다리는 경우를 살펴본다. 락으로 임계 구역을 보호해 데이터 레이스를 없앴더라도, 락을 획득하는 순서가 잘못되면 데드락이 생길 수 있다. 즉, 공유 데이터의 안전성과 작업의 진행 가능성은 따로 확인해야 한다.

두 스레드와 두 뮤텍스

재고를 보호하는 inventory_lock과 주문을 보호하는 order_lock이 있다고 하자. 스레드 A는 재고 락부터, 스레드 B는 주문 락부터 획득하며, 둘 다 두 락을 확보한 다음 처리하고 해제한다. 다음은 데드락이 발생하는 실행 순서다.

Time   Thread A                       Thread B
 t1    acquire(inventory_lock)
 t2                                   acquire(order_lock)
 t3    acquire(order_lock) -> WAIT
 t4                                   acquire(inventory_lock) -> WAIT
 t5    cannot reach unlock            cannot reach unlock

Wait-for graph:
       waits for order_lock
  A ----------------------------> B
  ^                               |
  |_______________________________|
       waits for inventory_lock

화살표는 기다리는 스레드에서 필요한 락의 소유자로 향한다. A가 진행하려면 B가 주문 락을 해제해야 하지만, B도 A가 재고 락을 해제해야 진행할 수 있다. 두 스레드 모두 해제 코드에 도달하지 못한다. 다른 순서로 실행하면 문제가 드러나지 않을 수 있지만, 한 번 이 상태가 되면 단순히 오래 기다리거나 CPU 실행 순서를 바꾸는 것으로 풀리지 않는다. 스케줄러는 CPU를 배분할 뿐, 보유 중인 뮤텍스를 안전하게 대신 해제해 주지 않는다. 일반적인 블로킹 뮤텍스 획득은 다른 소유자가 락을 해제할 때까지 기다린다.

데드락의 네 가지 필요조건

자원을 획득하고 반납하는 모델에서 데드락이 발생하려면 다음 네 조건이 함께 성립해야 한다. 이를 코프먼 조건(Coffman Conditions)이라고 한다.

1. 상호 배제(Mutual Exclusion): 해당 자원을 한 번에 하나의 작업만 사용할 수 있다. 예제의 각 뮤텍스는 소유자가 하나다.
2. 점유 대기(Hold and Wait): 자원을 이미 보유한 상태로 다른 자원을 기다린다. A와 B 모두 첫 번째 락을 놓지 않고 두 번째 락을 기다린다.
3. 비선점(No Preemption): 다른 작업이 보유한 자원을 강제로 회수하지 못한다. 여기서 비선점은 CPU를 빼앗지 못한다는 뜻이 아니라 자원을 회수하지 못한다는 뜻이다.
4. 순환 대기(Circular Wait): 각 작업이 다음 작업이 보유한 자원을 기다리고, 그 연결이 다시 처음으로 돌아온다. 예제에서는 A → B → A다.

어느 하나라도 성립하지 않도록 설계하면 이 모델의 데드락을 예방할 수 있다. 다만 네 조건이 가능한 설계라는 사실만으로 모든 실행이 데드락에 빠진다는 뜻은 아니다. 위 예제처럼 각 자원이 하나뿐인 뮤텍스 모델에서 실제 대기 고리가 생기면 데드락이다.

예방과 다른 진행 실패의 구별

가장 직접적인 예방책은 락 획득 순서를 통일하는 것이다. 모든 경로에서 재고 락 다음 주문 락을 획득하게 하면, 주문 락을 보유한 채 재고 락을 기다리는 역방향 연결이 생기지 않아 순환 대기가 끊어진다. 락이 늘어나면 전체 순서를 정하고 중첩 획득 때 이를 지킨다. 보유한 락보다 뒤 순서의 락만 요청하게 하면 처음 락으로 되돌아오는 요청 고리를 만들 수 없다. 일부 함수만 순서를 지켜서는 부족하며, 호출되는 함수가 내부에서 획득하는 락도 포함해야 한다.

순서를 지키기 어려운 경우에는 두 번째 락을 try_lock으로 시도하고, 실패하면 이미 획득한 락을 해제한 뒤 다시 시도할 수 있다. 실패했을 때 첫 번째 락을 계속 쥔 채 반복해서는 안 된다. 재시도 과정에서는 부분적으로 수행한 작업을 안전하게 취소하거나 상태를 다시 검사해야 하며, 반복 획득과 해제에도 비용이 든다.

재시도가 곧 진행 보장은 아니다. 서로 양보하고 다시 시도하는 동작만 반복해 작업을 끝내지 못하면 라이브락(Livelock)이다. 다른 스레드들은 진행하지만 특정 스레드만 계속 자원을 얻지 못하면 기아(Starvation)다. 데드락은 대기 의존성이 풀리지 않는 문제, 라이브락은 동작은 계속하지만 유효한 진전이 없는 문제, 기아는 특정 작업의 진전이 계속 배제되는 문제라는 차이가 있다.

조건 변수로 상태 변화를 기다린다

재고가 들어올 때까지 기다리는 주문은 또 다른 문제다. 락을 잡은 채 기다리면 입고 작업도 재고를 바꾸지 못한다. 조건 변수(Condition Variable)는 락 해제와 대기 진입을 연결하고, 깨어난 뒤 락을 다시 획득하도록 한다. 조건을 확인한 직후 입고 알림이 지나가고 그다음 잠드는 ‘놓친 깨우기’를 피하려면, 조건 확인과 상태 변경도 같은 뮤텍스 규약으로 묶어야 한다.

대기 코드는 ‘재고가 없으면 한 번 기다린다’가 아니라 ‘재고가 없는 동안 기다린다’라는 while 구조여야 한다. 깨어나도 다른 주문이 재고를 먼저 가져갈 수 있고, 알림 없이 깨어나는 스퓨리어스 웨이크업(Spurious Wakeup)도 가능하다. 알림은 재고를 예약하는 증표가 아니라 조건을 다시 검사할 계기다.