동기화·경쟁·교착상태

선수 설명은 프로세스·스레드·CPU 스케줄링의 자원 공유와 실행 문맥, 선형·계층·그래프·해시 구조 선택의 큐·그래프다. 잠금은 공유 상태의 어떤 관계를 보호하는지 먼저 적는다.

각자 맞는 코드도 함께 실행하면 틀릴 수 있다

두 스레드가 같은 잔액을 읽고 각각 1을 더한 뒤 저장한다고 하자. 둘 다 올바르게 읽기 → 더하기 → 쓰기를 수행해도 실행순서가 겹치면 두 번 증가해야 할 값이 한 번만 증가할 수 있다. 소스코드 한 줄처럼 보이는 연산도 CPU와 메모리에서는 여러 단계일 수 있기 때문이다.

공유상태를 보호하려고 잠금을 추가하면 다른 위험이 생긴다. 스레드 A가 자원 X를 가진 채 Y를 기다리고, B가 Y를 가진 채 X를 기다리면 둘 다 영원히 진행하지 못한다. 따라서 동시성 설계는 잠금을 쓴다가 아니라 무엇을 하나의 연산으로 보장하고, 누가 언제 기다리며, 진행불능을 어떻게 예방·발견·회복할지 정하는 일이다.

동시성·병렬성·원자성을 먼저 구분한다

동시성(concurrency)은 여러 실행흐름의 진행이 시간상 겹치도록 구조화된 성질이다. 한 코어에서 번갈아 실행해도 동시성은 존재한다. 병렬성(parallelism)은 둘 이상의 실행흐름이 여러 코어에서 같은 순간에 실제로 실행되는 성질이다. 병렬성은 동시성의 한 실행형태지만, 경쟁조건은 한 코어의 교차실행에서도 생길 수 있다.

공유상태(shared state)는 둘 이상의 실행흐름이 읽거나 변경할 수 있는 값과 그 관계다. 원자성(atomicity)은 하나의 연산으로 정한 상태변화가 다른 실행흐름에는 중간 단계 없이 한 번에 일어난 것처럼 관찰되는 성질이다. 임계구역(critical section)은 공유상태의 불변조건을 지키기 위해 동시에 둘 이상이 실행해서는 안 되는 코드 구간이다.

경쟁조건(race condition)은 실행순서나 시점에 따라 결과가 달라져 명세를 위반하는 조건이다. 단순히 두 흐름이 같은 값을 읽었다는 사실만으로 결함은 아니다. 공유상태의 갱신이 충분히 조정되지 않았는지, 사건의 순서가 계약을 어겼는지 판단한다.

언어의 데이터 경쟁(data race) 규칙과도 구분한다. 예를 들어 C++에서 서로 다른 스레드가 같은 일반 변수에 충돌하는 읽기·쓰기를 하고, 적어도 하나가 비원자 접근이며 두 접근 사이에 happens-before 관계가 없으면 데이터 경쟁이다. happens-before는 언어가 인정하는 동기화 등으로 한 접근이 다른 접근보다 앞서도록 보장되는 관계이며, 뒤에서 가시성과 연결한다. C++의 이런 데이터 경쟁은 정의되지 않은 동작(undefined behavior)을 일으키므로 실제 프로그램의 결과가 반드시 11이나 12 중 하나라고 추론할 수 없다.

아래 도식은 각 읽기·쓰기 단계가 하나씩 끝나고 표시된 순서대로 관찰되는 교육용 모형이다. 실제 C++ 비원자 변수의 안전하지 않은 실행을 예측하는 도식은 아니다. 반대로 각 읽기와 쓰기를 개별 원자 연산으로 만들더라도, 읽은 값에 1을 더해 다시 쓰는 전체 동작까지 원자적인 것은 아니어서 도식 같은 잃어버린 갱신은 여전히 가능하다.

여기서 원자성은 동시 실행 중 관찰되는 연산 경계다. 잠금을 잡았다고 해서 예외·프로세스 종료·정전이 났을 때 앞서 바꾼 값이 자동으로 되돌아가는 것은 아니다. 실패까지 포함한 전부/전무 보장은 상태 저장·복구 계약을 별도로 설계해야 한다.

전체에서 어디인가: 실행순서가 상태결과를 바꾸는 지점

실패 원인은 + 계산이 틀린 것이 아니라 읽기와 쓰기 사이에 다른 흐름이 들어와 잃어버린 갱신(lost update)이 생긴 것이다. 보호범위를 쓰기 한 줄에만 두어도 두 흐름이 같은 오래된 값을 읽을 수 있다. 어떤 불변조건을 하나의 임계구역이 지키는지 먼저 정해야 한다.

이미 배운 기반을 짧게 연결한다

앞에서 동시성은 여러 진행이 시간상 겹치는 구조이고, 경쟁조건은 그 실행순서에 따라 공유상태 결과가 달라지는 결함 조건이라고 배웠다. 같은 프로세스의 스레드는 자원을 공유하므로 독립 주소공간의 프로세스보다 공유상태를 만들기 쉽지만, 프로세스 사이 공유메모리나 커널 자원에서도 같은 문제가 생긴다. 이제 원자성·순서·대기를 보장하는 도구와 그 도구가 만드는 교착 위험을 함께 다룬다.

동기화와 교착상태의 정확한 뜻

동기화(synchronization)는 여러 실행흐름이 공유상태에 접근하거나 사건의 순서를 맞출 때 명세된 원자성·순서·가시성을 지키도록 실행을 조정하는 메커니즘이다.

상호배제(mutual exclusion)는 한 시점에 하나의 실행흐름만 특정 임계구역에 들어가게 하는 성질이다. 동기화가 상호배제만 뜻하는 것은 아니다. 자료가 생긴 뒤 소비한다 같은 사건순서와, 한 흐름의 쓰기를 다른 흐름이 관찰하게 하는 가시성도 포함한다.

교착상태(deadlock)는 하나 이상의 실행흐름이 진행에 필요한 자원이나 사건을 기다리는데, 그 대기를 해소할 동작도 막혀 참여한 흐름들이 계속 진행할 수 없는 상태다. 두 흐름이 서로의 자원을 기다리는 상호대기뿐 아니라 자기 교착(self-deadlock)도 포함한다. 동기화와 교착상태를 함께 다루는 이유는 공유상태를 안전하게 조정하는 도구와, 그 도구를 획득하는 방식이 만드는 영구대기 위험을 하나의 설계문제로 함께 다루기 위해서다.

자기 교착은 한 흐름으로도 확인할 수 있다. 스레드 A가 이미 뮤텍스 m을 소유한 채 같은 m을 다시 잠그고, 두 번째 획득이 끝난 뒤에만 해제할 수 있다고 하자. POSIX의 PTHREAD_MUTEX_NORMAL에서는 이 재획득이 교착을 일으킨다. A는 자신이 해제해야 얻을 수 있는 잠금을 기다려 해제 지점에 도달하지 못한다. PTHREAD_MUTEX_ERRORCHECK는 같은 상황에 오류를 반환하고, PTHREAD_MUTEX_RECURSIVE는 재획득 횟수를 관리한다. 따라서 “뮤텍스”라는 이름만 보고 재획득 동작을 같다고 가정하지 않으며, PTHREAD_MUTEX_DEFAULT도 NORMAL과 같다고 단정하지 않는다.

임계구역은 세 가지 진행조건까지 만족해야 한다

임계구역 해법은 보통 다음 조건을 평가한다.

1. 상호배제: 둘 이상의 흐름이 임계구역을 동시에 실행하지 않는다.
2. 진행(progress): 임계구역이 비었고 진입하려는 흐름이 있다면, 관계없는 흐름 때문에 선택이 무한히 미뤄지지 않는다.
3. 유한대기(bounded waiting): 한 흐름이 진입을 요청한 뒤 다른 흐름이 앞서 들어갈 수 있는 횟수에 한계가 있다.

모든 관련 접근이 같은 잠금 규칙을 따르고 임계구역 코드가 불변조건을 올바르게 복원한다면 상호배제로 동시 진입에 의한 훼손을 막을 수 있다. 그러나 한 스레드가 잠금을 놓지 않거나 특정 스레드만 계속 이기면 시스템은 쓸 수 없다. 보호할 불변조건, 임계구역 범위, 잠금을 획득·해제하는 주체, 기다림 방식과 최대대기를 함께 정한다.

CPU가 보장하는 원자적 읽기–수정–쓰기 연산은 잠금 구현의 재료가 될 수 있다. 그러나 한 변수의 원자적 증감이 여러 변수 사이 불변조건까지 자동으로 보호하지는 않는다. 예를 들어 재고 감소와 주문 상태 변경을 함께 보장해야 한다면 둘을 하나의 임계구역이나 더 큰 상태전이 계약으로 묶어야 한다.

재고를 감소시킨 뒤 주문 상태 변경에서 예외가 나면, 잠금을 해제하는 finally만으로 재고가 복원되지는 않는다. 실패 가능한 검증을 변경 전에 수행하고, 변경 뒤 실패에는 이전 상태 복원·보상 또는 트랜잭션 같은 별도 계약을 적용한다. 잠금 해제 보장과 업무 상태의 실패 복구는 서로 다른 책임이다.

뮤텍스: 소유자가 임계구역을 잠그고 푼다

뮤텍스(mutex)는 한 시점에 하나의 실행흐름만 임계구역에 들어가도록 잠금의 소유권을 관리하는 동기화 도구다. 흐름은 진입 전에 lock을 획득하고, 보호할 상태를 변경한 뒤 같은 소유 흐름이 unlock으로 해제한다. 다른 흐름이 이미 소유하면 기다린다.

기다림에는 두 방식이 있다. 블로킹 잠금(blocking lock)은 기다리는 흐름을 실행대기에서 빼고 나중에 깨워 CPU 낭비를 줄이지만 수면·깨움과 문맥교환 비용이 있다. 스핀락(spinlock)은 잠금이 풀렸는지 CPU에서 반복 확인하여 매우 짧은 임계구역에서는 수면비용을 피할 수 있지만, 오래 기다리면 CPU를 낭비한다. 어떤 문맥에서 어느 잠금을 쓸 수 있는지는 운영체제와 실행환경 규칙을 따라야 한다.

실패는 잠금 누락뿐 아니라 조기 반환·예외 뒤 해제 누락, 같은 잠금의 재획득, 긴 입출력을 잠근 채 수행, 일관되지 않은 다중 잠금 순서에서 생긴다. 언어나 라이브러리가 제공하는 자동 해제 구조를 사용하고 임계구역을 불변조건에 필요한 범위로 제한한다.

세마포어: 사용 가능한 허가의 수와 사건순서를 센다

세마포어(semaphore)는 음수가 되지 않는 논리적 허가 수와, 그 수를 원자적으로 줄이거나 늘리는 대기·신호 연산으로 동시 접근 수 또는 사건순서를 조정하는 도구다. 이 절에서는 허가를 얻는 연산을 wait, 반납하거나 사건을 알리는 연산을 signal이라고 부른다.

• 카운팅 세마포어(counting semaphore): 값 k로 시작하여 동시에 사용할 수 있는 동등 자원 k개를 표현한다.
• 이진 세마포어(binary semaphore): 값 범위를 0과 1로 제한해 한 번의 허가나 사건을 표현한다.

세마포어는 일반적으로 뮤텍스 같은 소유자 해제 규칙을 중심으로 하지 않는다. 한 흐름이 기다리고 다른 흐름이 신호를 보내는 사건 동기화에 쓸 수 있다는 장점이 있지만, wait/signal의 짝과 의미가 코드 밖으로 흩어지면 과잉 신호, 허가 누수와 잘못된 초깃값을 찾기 어렵다.

예를 들어 크기 N의 버퍼에는 빈 칸 수 empty=N, 채운 칸 수 full=0의 세마포어와 버퍼 자료구조를 보호하는 뮤텍스를 둘 수 있다. 생산자는 empty 허가를 얻고 버퍼를 잠가 넣은 뒤 full에 신호하고, 소비자는 full 허가를 얻고 잠가 꺼낸 뒤 empty에 신호한다. 허가가 0이면 wait는 허가를 음수로 만드는 대신 진행을 멈추고 허가가 생길 때까지 기다린다. 획득순서와 오류경로가 달라지면 허가 수와 실제 칸 수가 어긋난다.

크기 1의 버퍼에서 생산자·소비자 하나씩만 동작하고 오류가 없다는 교육 모형을 따라가 보자. 처음에는 (empty,full)=(1,0)이고 버퍼는 비어 있다. 생산자의 wait(empty) 뒤에는 (0,0)이며 빈 칸을 예약했지만 아직 자료는 없다. 생산자가 뮤텍스를 얻어 X를 넣고 잠금을 푼 뒤 signal(full)하면 (0,1)이 된다. 소비자는 wait(full)로 (0,0)을 만들고 잠금 아래 X를 꺼낸 뒤 signal(empty)하여 (1,0)으로 복구한다. 중간의 (0,0)은 칸이나 자료를 예약한 상태이므로 허가 수만 보고 버퍼의 실제 내용까지 같다고 단정하지 않는다.

자료 X가 들어 있어 (0,1)인 상태에서 생산자가 먼저 뮤텍스를 잡고 wait(empty)하면 어떻게 되는가? 생산자는 빈 칸이 없어 잠든다. 소비자는 X를 꺼내면 빈 칸을 만들 수 있지만 생산자가 뮤텍스를 가진 채 기다리므로 접근하지 못한다. 그래서 이 모형에서는 허가를 얻은 뒤 버퍼를 잠그고, 보호 잠금을 보유한 채 자원 허가를 기다리지 않는다. 오류로 자료를 넣지 못했다면 예약한 empty 허가를 반납하는 경로도 필요하다. 단순히 wait와 signal의 개수만 맞추는 대신 각각이 어느 상태를 예약하고 공개하는지 앞 상태 변화와 대조한다.

모니터와 조건변수: 상태와 보호규칙을 한 경계에 둔다

모니터(monitor)는 공유상태와 그 상태를 다루는 연산을 한 모듈 경계에 묶고, 한 시점에 하나의 흐름만 모니터 내부의 보호된 연산을 수행하도록 하는 고수준 동기화 구성이다. 언어가 모니터를 직접 제공할 수도 있고, 객체·뮤텍스·조건변수로 같은 구조를 만들 수도 있다.

조건변수(condition variable)는 버퍼가 비어 있지 않다처럼 공유상태의 조건이 참이 될 때까지 기다리고 그 변화 가능성을 알리는 동기화 도구다. 기다리는 흐름은 반드시 보호 잠금을 가진 채 조건식인 조건 술어(condition predicate)를 검사한다. 조건이 거짓이면 wait가 잠금을 원자적으로 놓고 잠들며, 깨어난 뒤 잠금을 다시 얻고 조건식을 다시 검사한다.

lock(m)
while not 조건술어:       ← if가 아니라 반복검사
    wait(cv, m)            ← m을 놓고 대기, 깨어날 때 다시 획득
공유상태 변경
unlock(m)

다시 검사하는 이유는 신호가 조건이 영원히 참을 보증하지 않고, 깨어난 여러 흐름 중 다른 흐름이 먼저 상태를 소비하거나 구현이 조건 충족 없이 깨울 수 있기 때문이다. 신호는 상태변화의 가능성을 알릴 뿐이며, 판단 기준은 같은 잠금 아래 확인한 조건 술어다.

예를 들어 빈 버퍼를 기다리던 소비자 A·B를 생산자가 자료 하나를 넣은 뒤 모두 깨웠다고 하자. A가 먼저 잠금을 얻어 자료를 꺼내면 버퍼는 다시 빈다. B가 나중에 잠금을 얻었을 때 해야 할 다음 동작은 다시 기다리기다. B에게 신호가 갔다는 이유만으로 꺼내기를 실행하면 빈 버퍼를 읽는다. 코드의 while not 조건술어는 바로 이 시점의 재검사이며, not은 조건이 거짓이라는 뜻이다. 위 모형에서 자료를 두 개 넣었다면 A가 하나를 꺼낸 뒤에도 조건이 참이므로 B도 하나를 꺼낼 수 있다. 깨어난 사실과 현재 공유상태를 구별하여 판단한다.

뮤텍스·세마포어·모니터·조건변수를 같은 축으로 비교한다

뮤텍스는 자원 한 개짜리 세마포어라는 숫자 비유만으로 대체하지 않는다. 소유권·오류검사·우선순위 처리와 사용계약이 다를 수 있다. 조건변수도 사건을 저장하는 카운터가 아니므로 조건 술어 없이 단독 사용하지 않는다.

원자성만으로 부족하다: 메모리 가시성과 순서

메모리 가시성(memory visibility)은 한 실행흐름이 쓴 값을 다른 흐름이 규정된 시점 이후 관찰할 수 있는 성질이다. 컴파일러와 CPU는 단일 흐름의 결과를 바꾸지 않는 범위에서 메모리 접근을 재배치하거나 캐시·버퍼에 머물게 할 수 있다. 동기화가 없으면 소스코드에 먼저 적힌 쓰기를 다른 코어가 같은 순서로 본다고 가정할 수 없다.

메모리 순서(memory ordering)는 여러 메모리 접근이 다른 흐름에 관찰되는 순서에 대한 규칙이다. 언어·CPU·운영체제는 동기화 연산 사이에 이 쓰기들이 저 읽기보다 먼저 관찰되어야 한다는 관계를 제공한다. 이 절에서는 이를 선행관계(happens-before)라고 부른다. 같은 뮤텍스를 올바르게 해제한 흐름의 보호된 쓰기와 그 뮤텍스를 뒤이어 획득한 흐름의 보호된 읽기 사이처럼, 사용 중인 언어·라이브러리가 정한 관계가 있어야 가시성을 주장할 수 있다.

특정 변수 접근을 특별 취급하는 한정자나 단일 원자변수 하나를 썼다는 사실만으로 여러 변수의 복합 불변조건과 모든 순서가 보장되지는 않는다. 구체적인 보장과 원자 연산의 메모리 순서는 해당 언어·플랫폼의 현행 메모리 모델을 확인한다. 답안에서는 원자성: 중간상태 비노출, 가시성: 쓴 값 관찰, 순서: 관찰 선후관계를 분리한다.

하나의 사례로 보호·조건·가시성을 묶는다

용량 N인 작업 큐에 여러 생산자와 소비자가 접근한다고 하자. 큐 상태는 0 ≤ count ≤ N을 항상 만족해야 하고, 넣기와 꺼내기는 큐의 순서·인덱스·count를 함께 바꾸는 하나의 상태 전이로 다룬다.

공유: queue, count, mutex m
조건변수 객체: cvNotFull, cvNotEmpty
잠금 m 아래 재검사할 술어: count < N, count > 0

생산자                              소비자
 lock(m)                             lock(m)
 while count == N: wait(cvNotFull,m)   while count == 0: wait(cvNotEmpty,m)
 enqueue; count++                    dequeue; count--
 signal(cvNotEmpty)                    signal(cvNotFull)
 unlock(m)                           unlock(m)

뮤텍스는 큐·인덱스·count의 복합 불변조건과 가시성을 보호한다. 조건변수는 꽉 찼거나 빈 상태에서 CPU를 소모하며 반복확인하지 않게 한다. wait(cv,m)는 m을 놓고 대기에 들어가는 동작을 원자적으로 연결하고, 반환하기 전에 m을 다시 획득한다. signal은 대기자를 깨울 기회이며 술어를 참으로 저장하거나 즉시 CPU·잠금을 넘기는 명령이 아니다. 깨어난 사이 다른 흐름이 상태를 바꿀 수도 있으므로 잠금을 다시 얻은 뒤 while로 술어를 재검사한다. 이와 달리 뮤텍스를 놓지 않는 일반적인 sleep이나 외부 대기 호출을 사용하면, 상대가 같은 잠금을 얻지 못해 필요한 상태변화를 만들 수 없다.

검증할 불변조건은 count는 실제 원소 수, 0≤count≤N, 빈 큐에서 꺼내지 않음, 가득 찬 큐에 넣지 않음이다. 강제종료·취소가 가능한 환경에서는 잠금과 큐 상태를 중간에 남기지 않도록 취소 지점과 정리 규칙도 별도로 설계한다.

교착상태의 네 필요조건을 자원관계로 읽는다

고전적인 자원 교착모형에서는 다음 네 조건이 동시에 존재해야 교착이 가능하다.

1. 상호배제(mutual exclusion): 적어도 한 자원을 한 번에 한 흐름만 사용한다.
2. 점유대기(hold and wait): 자원을 가진 흐름이 다른 자원을 기다린다.
3. 비선점(no preemption): 이미 할당한 자원을 시스템이 안전하게 강제로 회수할 수 없다.
4. 순환대기(circular wait): T1은 T2의 자원, T2는 T3의 자원, ..., Tk는 T1의 자원을 기다리는 순환이 있다.

여기서 비선점은 앞 절의 CPU 선점과 다른 자원 계약이다. 시간할당량이 끝나 A 대신 B에 CPU를 주어도 A가 소유한 뮤텍스는 보통 그대로 A의 소유다. CPU 실행기회를 바꾼 사실만으로 뮤텍스 대기는 풀리지 않는다. A가 재고만 줄이고 주문 목록을 아직 갱신하지 않은 중간 상태에서 잠금을 강제로 빼앗으면 B가 깨진 불변조건을 볼 수도 있다. 자원을 회수하려면 그 자원의 소유권·상태 복구 규칙이 필요하다.

네 조건은 일반 자원모형에서 교착이 일어나기 위한 필요조건이다. 조건이 동시에 보인다고 모든 세부 모형에서 이미 교착이라고 단정하지 않는다. 자원 종류마다 인스턴스가 하나뿐인 대기그래프에서는 순환이 교착의 충분한 판정이 될 수 있지만, 인스턴스가 여러 개인 경우에는 현재 할당·요청과 해제 가능성을 추가로 분석해야 한다.

예방·회피·탐지·회복은 서로 다른 시점의 전략이다

직전 블록의 상호배제·점유대기·비선점·순환대기 중 적어도 하나를 깨거나, 네 조건이 가능하더라도 안전·탐지·회복 규칙을 두는 것이 처리전략의 출발점이다. 교착 예방(prevention)은 네 필요조건 중 적어도 하나가 성립하지 않도록 규칙을 강제한다. 모든 자원을 한꺼번에 요청하면 점유대기를, 자원 종류에 전역 순서를 주고 오름차순으로만 획득하면 순환대기를 깰 수 있다. 다만 자원 이용률 저하와 긴 보유가 생길 수 있고, 프린터 출력처럼 안전하게 되돌릴 수 없는 자원은 강제선점하기 어렵다.

교착 회피(avoidance)는 요청을 바로 허용하지 않고, 허용 뒤에도 모든 흐름을 완료시킬 순서가 적어도 하나 존재하는 안전상태(safe state)에 남는지 검사한다. 모든 가능한 실행순서가 안전해야 한다는 뜻은 아니다. 각 흐름이 선언한 최대 요구 안에서 필요한 자원을 얻으면 완료하고 보유 자원을 반환한다는 모형의 전제가 있다. 안전하지 않다는 것은 지금 이미 교착이거나 앞으로 반드시 교착이 된다는 뜻이 아니라, 그 전제 아래 향후 요청을 보장할 안전한 완료순서를 찾지 못했다는 뜻이다. 최대 자원요구를 미리 알아야 한다는 비용이 있다.

교착 탐지(detection)는 교착 가능성을 허용하고 주기적 또는 징후 발생 시 현재 대기관계를 분석한다. 자원마다 인스턴스가 하나라면 대기그래프(wait-for graph)에서 Ti → Tj를 Ti가 Tj가 보유한 자원을 기다림으로 나타내고 순환을 찾을 수 있다. 여러 인스턴스에서는 가용량·현재 할당·남은 요청을 이용한 별도 탐지계산이 필요하다.

회복(recovery)은 탐지한 교착을 깨기 위해 희생 흐름을 종료하거나 이전 안전지점으로 되돌리고, 안전하게 선점 가능한 자원을 회수하는 조치다. 우선순위·수행량·보유자원·재시작비용과 같은 희생기준, 같은 흐름만 반복 희생되는 기아와 데이터 일관성을 함께 통제한다.

은행가 알고리즘: 요청 뒤에도 안전한 완료순서가 있는지 본다

은행가 알고리즘(Banker's algorithm)은 각 흐름의 최대 자원요구를 미리 알고 있을 때, 새 요청을 가상으로 할당한 뒤에도 안전순서가 존재하는 경우에만 실제 할당하는 교착 회피 알고리즘이다. 자원 종류가 m, 흐름 수가 n이라고 하자.

• Available[m]: 현재 남은 자원 수 벡터
• Max[n,m]: 각 흐름이 선언한 종류별 최대 요구 행렬
• Allocation[n,m]: 현재 할당한 자원 수 행렬
• Need[n,m] = Max - Allocation: 완료까지 추가로 필요할 수 있는 자원 행렬

안전성 검사는 Work=Available, 모든 Finish=false로 시작한다. 아직 끝나지 않았고 Need[i] ≤ Work인 흐름 i를 찾으면 그 흐름이 완료한다고 가정해 Work = Work + Allocation[i], Finish[i]=true로 바꾼다. 모든 흐름을 끝낼 수 있으면 찾은 순서가 안전순서다.

새 요청은 음수 성분이 없는 종류별 벡터로 받는다. 어느 성분이라도 Request[i] > Need[i]이면 선언한 최대요구를 넘긴 요청이므로 오류로 거절한다. 선언 안이지만 어느 성분이 Available보다 크면 현재 자원이 부족하므로 상태를 바꾸지 않고 대기시킨다. 두 검사를 통과하면 Available을 줄이고 Allocation[i]를 늘리며 Need[i]를 줄인 가상상태에서 안전성을 검사한다. 안전순서가 있으면 승인하고, 없으면 가상 변경을 원상복구한 뒤 대기시킨다. 여기서 ≤는 모든 성분에 대한 비교이지 벡터 원소합 비교가 아니다.

최대요구가 부정확하거나 자원 수가 동적으로 크게 바뀌고 흐름 수가 많으면 적용비용과 보수성이 커진다. 안전상태는 현재 교착이 없음보다 강한 보장이고, 불안전상태는 이미 교착과 동의어가 아니다.

두 자원으로 안전검사를 한 바퀴 진행한다

자원은 A·B 각각 3개이며 현재 Available=(1,1)이다. 행의 두 숫자는 언제나 A,B 순서다.

초기 Work=(1,1), Finish=(F,F,F)에서 P0는 A가 부족하지만 P1은 완료 가능하다. P1의 현재 할당량 (1,1)을 반납한 가상 상태는 Work=(2,2), Finish=(F,T,F)다. 이제 P0를 끝내면 Work=(3,2), Finish=(T,T,F), P2까지 끝내면 Work=(3,3), Finish=(T,T,T)이므로 안전순서 하나는 P1→P0→P2다. Work에 더하는 것은 Max나 Need가 아니라 이미 할당했던 Allocation이다.

이 초기 상태에서 P0가 (1,0)을 요청하면 Need·Available 검사는 통과하지만 가상 Available=(0,1), P0의 Need=(1,1)이 된다. 모든 흐름이 A를 적어도 하나 더 요구하므로 아무 Finish도 true로 바뀌지 않아 가상할당을 취소하고 기다리게 한다. 반대로 초기 상태에서 P1의 (1,0) 요청은 가상 Available=(0,1), P1의 Need=(0,1)을 만들므로 P1부터 끝낼 수 있어 승인 가능하다. 두 요청을 연속 적용한 것이 아니라 같은 초기 상태에서 따로 비교한 것이다.

같은 초기 행렬에서 다른 요청을 판정한다

직전 표의 초기 상태로 돌아가 P2가 (0,1)을 요청한다고 하자. 자원 순서는 A,B이고 다른 요청은 아직 적용하지 않았다. Request≤Need·Available 검사, 가상 Available·Allocation·Need, 완료 가능한 순서와 각 Work를 계산하여 승인 여부를 설명하라. 이는 자체 제작 연습이며 최대 요구량과 고정 자원 수라는 원래 전제는 유지한다.

교착·라이브락·기아를 구분한다

라이브락(livelock)은 실행흐름들이 멈추지는 않고 서로를 피하려 상태를 계속 바꾸지만 유용한 일이 완료되지 않는 상태다. 두 흐름이 충돌할 때마다 동시에 자원을 놓고 같은 시간에 다시 시도하면 발생할 수 있다. 무작위 또는 점증 지연, 우선권 규칙으로 대칭을 깨뜨린다.

기아(starvation)는 시스템 전체에서는 다른 흐름이 진행하지만 특정 흐름이 자원이나 실행기회를 계속 얻지 못하는 상태다. 불공정한 잠금·우선순위·반복 희생이 원인이며, 공정 대기열·에이징·최대 재시도와 최대대기 관측으로 통제한다.

우선순위 역전(priority inversion)은 높은 우선순위 흐름이 낮은 우선순위 흐름이 가진 잠금을 기다리고, 중간 우선순위 흐름들이 낮은 흐름의 실행을 빼앗아 대기가 길어지는 현상이다. 잠금 보유자에게 기다리는 높은 우선순위를 임시로 물려주는 우선순위 상속(priority inheritance) 등을 검토하되, 구체 보장은 실시간 실행환경의 규칙과 최악 차단시간 분석으로 확인한다.

시간제한(timeout)은 정한 대기시간을 넘으면 획득 시도를 실패로 끝내거나 복구경로로 전환하는 규칙이다. 무한대기를 제한하고 관측 신호를 만들 수 있지만 교착 자체를 예방했다는 증명은 아니며, 중간상태 정리와 재시도가 없으면 데이터 불일치나 라이브락으로 바뀔 수 있다.

어디서 실패하는가

동기화·교착상태의 핵심 학습 논점

동기화·교착상태를 설명할 때는 안전한 공유상태 변경과 진행 가능성을 함께 점검한다.

1. 동시성·병렬성, 공유상태·원자성·가시성과 경쟁조건을 구분한다.
2. 임계구역의 상호배제·진행·유한대기 조건을 설명한다.
3. 뮤텍스·세마포어·모니터·조건변수의 상태·소유권·대기 의미를 비교한다.
4. 교착의 네 필요조건과 예방·회피·탐지·회복 시점을 연결한다.
5. 은행가 알고리즘의 자료구조와 안전성 검사, 적용전제를 설명한다.
6. 교착·라이브락·기아·우선순위 역전을 구분하고 관측·통제한다.

같은 원리는 스레드 동기화 인터페이스의 잠금·오류경로에도 적용된다. 시스템 호출과 입출력 경계는 시스템 프로그래밍에서 이어서 살펴본다.

동기화 도구와 교착 회피를 답안으로 연결한다

뮤텍스·세마포어·모니터를 비교할 때는 정의 → 상태·소유권·대기 → 작동흐름 → 적합조건 → 실패조건 순서로 설명한다. 이름이 비슷해도 허가 수와 잠금 소유권, 술어를 기다리는 의미는 서로 다르다.

은행가 알고리즘은 교착 정의·필요조건에서 시작해 Available·Max·Allocation·Need, 가상할당과 안전성 검사, 요청을 지연하는 조건과 적용 한계로 연결한다. 아래 자체 제작 문제의 목차와 풀이를 보기 전에 이 흐름을 먼저 적어 보자. 실제 기출 여부와 공식 채점 기준은 별도 공식 원문 확인이 필요하다.

시험에서는 어떻게 묻는가: 10점

다음은 이 절의 학습목표를 확인하기 위한 자체 제작 문제다.

뮤텍스, 세마포어, 모니터와 조건변수의 개념·작동원리·적용조건을 비교하고 대표 실패조건을 설명하시오.

세마포어도 잠금처럼 뭉개지 않는다. 각 도구가 가진 상태, 소유권, 기다림과 신호의 의미를 먼저 제시하고, 상호배제·자원 수 제한·조건대기 중 어떤 문제를 푸는지 연결한다.

시험에서는 어떻게 묻는가: 25점

다음은 본문만으로 풀 수 있게 만든 자체 제작 설계 문제다.

여러 작업이 데이터베이스 연결·파일 변환기·메모리 버퍼를 함께 사용하는 처리시스템의 동기화와 교착 통제를 설계하시오. 임계구역과 도구 선택, 교착 필요조건, 예방·회피·탐지·회복, 은행가 알고리즘 적용 가능성, 라이브락·기아 및 검증방안을 설명하시오.

답안은 모든 곳에 은행가 알고리즘을 쓰는 방식이 아니다. 보호할 공유상태와 자원모형을 먼저 정하고, 최대요구를 알 수 있는 자원에만 회피를 검토하며 나머지는 순서규칙·탐지·회복으로 분리한다.

근거와 현행성

뮤텍스·세마포어·조건변수와 스레드 동기화의 인터페이스 경계는 IEEE와 The Open Group의 POSIX.1-2024, Issue 8 XSH Chapter 2와 동기화 설계근거를 대조했다. 현행 구현 사례의 잠금 문맥은 Linux kernel locking 문서를 확인했으며, Linux 고유 규칙을 모든 언어·운영체제에 일반화하지 않았다.

세마포어와 협력 순차 프로세스, 은행가 알고리즘의 역사적 원리는 University of Texas의 E. W. Dijkstra Archive EWD 123 전사본과 은행가 알고리즘 부분을 대조했다. Coffman 등의 System Deadlocks, DOI 10.1145/356586.356588는 현재 Crossref 서지 메타데이터만 확보했다. ACM 본문을 대조하지 못했으므로 이 메타데이터를 교착 네 조건이나 예방·탐지·회복 분류의 내용 근거로 사용하지 않으며, 해당 귀속은 합법적인 본문 확보와 사람 검토 전 확정하지 않는다.

추가한 자기 교착과 뮤텍스 유형별 재획득 차이는 POSIX.1-2024 pthread_mutex_lock의 Relock 표, 소유자만 해제하고 재귀 획득을 허용하지 않는 Linux 커널 뮤텍스의 별도 규칙은 Generic Mutex Subsystem의 Semantics, C++ 데이터 경쟁과 정의되지 않은 동작의 경계는 공개 C++ 작업초안 intro.races와 2026-10-09에 대조했다. C++ 자료는 공개 작업초안이며 모든 언어의 메모리 모형을 뜻하지 않는다. 안전순서의 존재와 가상할당·환원은 EWD 123 §6.1의 은행가 설명과 같은 날짜에 대조했다.

POSIX 자료는 뮤텍스·조건변수의 인터페이스 계약을, Dijkstra 자료는 세마포어 P/V와 안전상태·은행가 알고리즘의 역사적 원리를 뒷받침한다. P는 자원이 없으면 기다린 뒤 허가를 획득하는 연산, V는 허가를 반환하여 대기가 진행될 수 있게 하는 연산이다. 모니터와 예방·탐지·회복의 전체 비교는 교재의 별도 설명이며, Coffman 논문의 서지 정보만으로 그 내용을 검증했다고 해석하지 않는다. 본문의 표·의사흐름·도식·사례와 답안은 교육을 위해 독자 구성했다.

30초 정리

1. 동기화는 공유상태의 원자성·순서·가시성을 지키며, 임계구역 해법은 상호배제·진행·유한대기를 함께 본다.
2. 뮤텍스는 소유 임계구역, 세마포어는 허가 수·사건, 모니터와 조건변수는 캡슐화한 상태조건 대기를 담당한다.
3. 교착은 상호배제·점유대기·비선점·순환대기가 가능한 관계에서 생기며 예방·회피·탐지·회복은 적용시점이 다르다.
4. 은행가 알고리즘은 최대요구와 자원 수를 알아야 하며 가상할당 뒤 안전순서가 있을 때만 요청을 승인한다.
5. 교착은 멈춘 순환대기, 라이브락은 움직이지만 무완료, 기아는 특정 흐름의 장기박탈이다.

다음 절에서는 프로세스가 실제 물리메모리보다 크고 연속적인 공간을 가진 것처럼 보이게 하는 가상메모리와 페이지 교체 원리를 살펴본다.

추가 연습 — 개별 접근과 전체 갱신

앞의 읽기·더하기·쓰기 도식처럼 각 단계가 하나씩 끝나고 그 순서대로 관찰되는 교육용 모형으로 판단한다. 실제 C++ 비원자 변수의 데이터 경쟁에서 실행 결과를 예측하는 연습은 아니다.

보호범위 연습: 초깃값 10에 두 흐름이 각각 1을 더해 최종 12를 만들려 한다. 위의 교육용 모형에서 ① 읽기와 쓰기만 각각 원자적, ② 읽기·더하기·쓰기를 같은 뮤텍스의 한 임계구역으로 보호, ③ 하나의 원자적 read-modify-write 증가 연산 사용 중 어느 방식이 이 단일 카운터의 두 증가를 보존하는가? 다른 쓰기는 없고 두 증가 모두 완료한다고 가정한다.