운영체제 기본/동시성

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

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

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

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

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

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

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

A가 1을 읽은 뒤 B도 1을 읽을 수 있다. 이어 A와 B가 각각 0을 쓰고 주문을 승인하면 최종 재고는 0인데 승인된 주문은 두 개다. 각 읽기와 쓰기가 따로는 정확해도 전체 연산은 잘못된다. 이런 단계의 교차를 인터리빙이라고 한다. 한 코어에서 실행을 번갈아도 가능한 순서다.

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

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

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

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

잠금에는 메모리의 가시성과 순서를 연결하는 역할도 있다. 올바른 동기화 규약 아래에서 잠금을 해제하기 전의 변경은 같은 잠금을 이어서 획득한 작업에 전달된다. 단순히 실행 시간이 앞섰다는 사실만으로는 이런 관계가 생기지 않는다. 컴파일러와 하드웨어가 허용하는 재배치를 고려한 동기화가 필요하다. C에서 동기화되지 않은 충돌 접근으로 데이터 경쟁이 발생하면 동작이 정의되지 않는다.

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

원자 연산으로 잠금 만들기

공유 RAM에 놓인 잠금 변수의 0을 비어 있음, 1을 사용 중이라고 하자. 이 변수는 원자 연산이 요구하는 크기와 정렬 조건을 만족해야 한다. 비교 후 교환(CAS)은 현재 값이 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: 공유 메모리 대상의 LOCK CMPXCHG로 CAS를 구현할 수 있다. 단순히 CMPXCHG라고만 쓰면 다중 프로세서에서 필요한 원자성 조건을 빠뜨린다.
• RISC-V: A 확장의 LR/SC로 값을 읽어 비교한 뒤 조건부 저장하고, 저장 실패 시 재시도하여 CAS를 구성할 수 있다. SC는 다른 작업의 값 변경이 없어도 실패할 수 있다. 다른 방법인 AMOSWAP.W.AQ는 1을 무조건 교환하여 이전 값이 0인 작업만 진입시키는 test-and-set 방식이다. 이는 CAS와 같은 명령이 아니다.

원자적 획득만으로 충분하지는 않다. acquire/release는 앞 소유자의 변경을 다음 소유자가 관찰하도록 순서를 연결하며, 컴파일러와 하드웨어 양쪽에서 보장되어야 한다. RISC-V에서는 aq/rl 또는 필요한 FENCE로 순서를 구현한다. aq/rl의 보장은 해당 주소 영역에 적용되므로 메모리와 I/O 영역 사이의 순서까지 자동으로 해결하지는 않는다.

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

기다림에도 비용이 있다

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

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

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

상태를 지키는 것과 일이 끝나는 것은 다르다

상호 배제가 있어도 진행은 멈출 수 있다. A가 재고 잠금을 잡고 주문 잠금을 기다리는 동안 B가 반대로 잡고 기다리면 교착 상태가 된다. 모든 경로가 재고, 주문 순서로 잠그도록 통일하면 이 순환을 막을 수 있다. 대신 함수 호출과 자료 구조를 넘나드는 공통 순서를 유지해야 한다. 기아는 전체 시스템은 진행하지만 특정 작업이 계속 기회를 얻지 못하는 경우다. 잠금 획득의 공정성은 별도의 보장이며, 뮤텍스를 썼다는 이유만으로 따라오지 않는다.

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

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