프로세스 동기화와 데드락

게시 2025/10/19

By Jinhyeok Ko

조회 29 분읽는 시간

프로세스 동기화와 데드락

프로세스 동기화와 교착 상태

현대 운영체제는 선점형 스케줄링이나 멀티코어 환경에서 여러 실행 흐름(프로세스/스레드)을 ‘동시에(Concurrently)’ 혹은 ‘병렬로(Parallel)’ 실행시킵니다.

만약 이 실행 흐름들이 서로 독립적인 자원만 사용한다면 아무런 문제가 없겠지만, 이들이 공유 자원(Shared Resource)(전역 변수, 공유 파일, 공유 메모리 등)에 동시에 접근하려 할 때 심각한 문제가 발생할 수 있습니다.

프로세스 동기화(Process Synchronization) 는 바로 이러한 동시 실행 환경에서 시스템의 ‘정확성(Correctness)’ 을 보장하기 위한 ‘협력(Cooperation)’과 ‘통제(Control)’ 를 다루는 핵심 주제입니다. 이는 단순히 실행 속도를 높이는 ‘효율성(Efficiency)’과는 구별되는, 데이터의 일관성을 지키는 문제입니다.

문제 : 경쟁 상태(Race Condition)

경쟁 상태는 둘 이상의 프로세스(또는 스레드)가 공유 자원에 동시에 접근(특히 ‘쓰기’ 작업)할 때, 그 접근 순서(타이밍)에 따라 실행 결과가 비정상적으로 달라지는 현상을 의미합니다.

이로 인해 데이터의 무결성이 깨지며, 버그가 발생하지만 재현이 어려워(Non-deterministic) 최악의 버그로 꼽힙니다.

발생 조건

공유 자원 사용 : 여러 스레드/프로세스가 동일한 자원(변수, 메모리 등)을 동시에 사용합니다.
동시성 : 두 스레드/프로세스가 동시에 실행되며, OS의 스케줄링(문맥 교환 등)에 따라 실행 순서가 예측 불가능하게 결정됩니다.

은행 계좌의 잔액(balance)이라는 공유 자원에 두 스레드가 동시에 100을 입금하는 상황
balance의 현재 값이 1000이라고 가정합니다.
balance = balance = 100이라는 코드는 기계어 수준에서 3단계로 나뉩니다.
LOAD : balance(1000)를 CPU 레지스터로 가져온다.
INCREMENT : 레지스터 값(1000)을 100 증가시킨다. (1100)
STORE : 레지스터 값(1100)을 다시 balance에 저장한다.
잘못된 실행 순서 (Context Switch로 인한 Race Condition)
스레드 1: LOAD (레지스터1 = 1000)
스레드 1: INCREMENT (레지스터1 = 1100)
(문맥 교환 발생)
스레드 2: LOAD (레지스터2 = 1000) ← 스레드 1이 아직 저장하기 전!
스레드 2: INCREMENT (레지스터2 = 1100)
스레드 2: STORE (balance = 1100)
(문맥 교환 발생)
스레드 1: STORE (balance = 1100)
결과: 1000에 100을 두 번 더했음에도, 최종 잔액은 1200이 아닌 1100이 됩니다. 입금 한 번이 증발했습니다.

커널(OS) 내부의 Race Condition

Race Condition은 응용 프로그램뿐만 아니라 OS 커널 내부에서도 치명적인 문제를 일으킵니다. 커널 코드는 인터럽트, 시스템 콜, 멀티코어 등 다양한 요인에 의해 ‘동시에’ 혹은 ‘병렬로’ 실행될 수 있기 때문입니다.

커널 내부의 Race Condition은 크게 3가지 상황에서 발생하며, 각각 다른 해결책이 필요합니다.

1. 인터럽트(Interrupt)에 의한 선점

문제 상황 : 커널이 공유 변수(예: 프로세스 리스트)를 수정하는 임계 구역을 실행하던 중, 하드웨어 인터럽트가 발생했습니다. 이때 이 인터럽트를 처리하는 인터럽트 서비스 루틴(ISR) 이 동일한 공유 변수에 접근하려 하면 Race Condition이 발생합니다.
해결책 : 인터럽트 비활성화(Disabling Interrupts). 커널은 임계 구역에 진입하기 직전에 CPU의 인터럽트를 잠시 비활성화하고, 임계 구역을 빠져나온 직후 다시 활성화합니다. 이렇게 하면 임계 구역 실행 중에는 ISR이 난입할 수 없습니다.

2. 커널 모드 중 문맥 교환(Preemption)

문제 상황 : 커널이 임계 구역을 실행하던 중, 타임 슬라이스가 만료되거나 더 높은 우선순위의 프로세스가 등장하여 문맥 교환(Context Switch) 이 발생했습니다. 새로 스케줄링된 프로세스가 시스템 콜을 호출하여 동일한 커널 자료구조에 접근하면 Race Condition이 발생합니다.
해결책 :
- (과거) 비선점형 커널(Non-preemptive Kernel) : 초기 OS(초기 UNIX)는 아예 커널 모드에서는 선점(문맥 교환)이 일어나지 않도록 설계했습니다. 커널 작업이 끝나고 사용자 모드로 복귀할 때만 문맥 교환을 허용했습니다. (응답성 저하)
- (현재) 선점형 커널(Preemptive Kernel) + 락 : 현대 OS(Linux, Windows)는 응답성을 높이기 위해 커널 모드에서도 선점을 허용합니다. 대신, 임계 구역을 보호하기 위해 락(Lock) 을 사용합니다. (아래 3번 항목과 동일)

3. 멀티프로세서(Multi-core) 환경의 병렬 접근

문제 상황 : 여러 개의 CPU 코어가 물리적으로 동시에 커널 모드로 진입하여, 동일한 커널 자료구조(공유 데이터)에 접근하려 할 때 Race Condition이 발생합니다.
중요 : 이 문제는 1번의 ‘인터럽트 비활성화’로 해결할 수 없습니다. Core 1이 인터럽트를 꺼도, Core 2는 여전히 병렬로 실행되며 동일 데이터에 접근할 수 있기 때문입니다.
해결책 : 락(Lock) 메커니즘 사용. 커널은 공유 데이터별로 락을 정의합니다. 데이터에 접근하려는 코어는 반드시 락을 먼저 획득해야 하며, 락을 획득하지 못한 다른 코어들은 락이 해제될 때까지 기다려야 합니다.
- 스핀락(Spinlock) : 락이 해제될 때까지 CPU를 점유한 채 루프를 돌며(Spinning) 대기합니다. 락이 매우 짧게 잡히는 커널 내부에서 효율적입니다.
- 뮤텍스/세마포어 : 락을 얻지 못하면 Blocked 상태가 되어 CPU를 반납(Sleep)합니다.

임계 구역 문제와 해결 조건

임계 구역(Critical Section)

임계 구역은 공유 자원에 접근하여 Race Condition이 발생할 수 있는 코드의 특정 영역(블록) 을 의미합니다. 공유 자원의 데이터 일관성을 보장하기 위해 한 번에 하나의 프로세스 또는 스레드만 크리티컬 섹션을 실행할 수 있도록 제어합니다.

임계 구역 문제(Critical Section Problem)

임계 구역 문제는 여러 프로세스가 이 임계 구역을 동시에 실행하지 않도록 하는 프로토콜을 설계하는 것입니다. 이 문제를 해결하기 위한 해법은 반드시 다음 세 가지 조건을 만족해야 합니다.

상호 배제(Mutual Exclusion) : 가장 핵심적인 조건입니다. 한 프로세스가 자신의 임계 구역에서 실행 중이라면, 다른 어떤 프로세스도 그들의 임계 구역에 진입할 수 없어야 합니다.
진행 조건(Progress) : 임계 구역이 비어있다면(아무도 실행 중이지 않다면), 임계 구역에 진입하려는 프로세스들 중 하나는 반드시 선택되어 진입할 수 있어야 합니다. (아무도 못 들어가는 무한 대기 방지)
유한 대기(Bounded Waiting) : 특정 프로세스가 임계 구역에 진입하기 위해 대기하는 시간은 유한해야 합니다. (특정 프로세스만 계속해서 진입하지 못하는 기아 상태(Starvation) 방지)

임계 구역 문제의 해결책

세마포어(Semaphore)

상호 배제를 구현하기 위한 고전적이고 강력한 OS 수준의 도구가 바로 세마포어입니다.

세마포어(Semaphore) 는 특정 개수(N)의 자원을 여러 프로세스가 공유하며 사용할 때, 이 자원에 대한 접근을 통제하는 정수형 변수(S) 와 두 개의 원자적(Atomic) 연산으로 구성됩니다. (원자적이란, 연산이 실행되는 도중에 문맥 교환이 일어나지 않음을 보장한다는 뜻입니다.)

S : 사용 가능한 자원의 개수를 나타내는 정수
wait() 연산 (또는 P()) : 자원을 획득(Acquire)하려는 시도
signal() 연산 (또는 V()) : 자원을 반납(Release)하는 신호

// wait(S)의 의사 코드
wait(S) {
	while (S <= 0) {
		// 자원이 없으므로, 이 프로세스는 Blocked 상태가 되어
		// S에 대한 대기 큐(Wait Queue)에 들어감
	}
	S--; // 자원을 1개 획득 (혹은 임계 구역 진입 허가)
}

// signal(S)의 의사 코드
signal(S) {
	S++; // 자원을 1개 반납 (혹은 임계 구역에서 나옴)
	// 만약 S에 대해 대기 중인 프로세스가 있다면,
	// 그중 하나를 깨워서 Ready 큐로 보냄
}

공유 자원을 사용하는 3개의 프로세스(A, B, C)가 있고, 자원은 2개만 존재한다고 가정
초기 상태: 세마포어 값 S = 2 (자원 2개 사용 가능)
프로세스 A: wait(S) 호출 → S가 1이 됨. A는 임계 구역 진입
프로세스 B: wait(S) 호출 → S가 0이 됨. B는 임계 구역 진입
프로세스 C: wait(S) 호출 → S가 -1이 됨. C는 Blocked 상태가 되어 S의 대기 큐로 이동
프로세스 A: 작업 완료 후 signal(S) 호출 → S가 0이 되며, S가 0 이하이므로, 대기 큐의 C를 깨움(Ready)
프로세스 B: 작업 완료 후 signal(S) 호출 → S가 1이 됨 (대기 큐가 비어있으므로 아무도 깨우지 않음)

세마포어의 종류

카운팅 세마포어(Counting Semaphore)
- S 값이 0 이상의 정수 범위를 가질 수 있습니다.
- 사용 가능한 자원이 여러 개(N개) 일 때 사용합니다. (S를 5로 초기화하면, 최대 5개의 스레드가 동시에 특정 자원에 접근 가능)
이진 세마포어(Binary Semaphore)
- S 값이 0 또는 1만 가질 수 있습니다.
- 자원이 오직 하나일 때, 즉 상호 배제(Mutual Exclusion) 를 구현할 때 사용됩니다. S를 1로 초기화하면, 오직 하나의 스레드만 wait()를 통과해 임계 구역에 진입할 수 있습니다.

세마포어의 대기 방식 : Busy-Wait vs Block/Wakeup

wait() 연산을 구현하는 방식에는 두 가지가 있으며, 이는 중요한 트레이드오프를 가집니다.

Busy-Wait (or Spin-lock)
- wait()가 자원이 생길 때까지 CPU를 점유한 채 while(S <= 0) {} 루프를 계속 확인하는 방식입니다.
- 대기하는 동안 CPU를 계속 사용하므로 CPU 자원을 낭비하나, 프로세스 상태를 Blocked로 바꾸고 다시 Ready로 깨우는 문맥 교환(Context Switch) 오버헤드가 없습니다.
Block/Wakeup (or Sleep)
- wait()가 자원이 없으면 프로세스를 Blocked 상태로 만들고 CPU를 반납합니다. signal()이 발생하면 OS가 대기 큐에서 프로세스를 깨웁니다.
- 대기하는 동안 CPU를 낭비하지 않고 다른 프로세스가 실행될 수 있으나(효율적), 문맥 교환 오버헤드가 발생합니다.

임계 구역이 매우 짧아서 대기 시간이 문맥 교환 시간보다 짧을 것이라 예상되면, Busy-Wait(Spin-lock) 이 오히려 더 효율적일 수 있습니다. (현대 커널이 멀티코어 환경에서 스핀락을 자주 사용하는 이유)

모니터(Monitor)

세마포어는 매우 강력하지만, 프로그래머가 wait()와 signal()의 순서를 실수(signal을 wait보다 먼저 호출, wait 중복, signal 누락)하면 Race Condition이 발생하거나 시스템 전체가 데드락에 빠지는 등 사용하기가 매우 어렵고 위험합니다.

모니터(Monitor) 는 이러한 실수를 원천적으로 방지하기 위해 고안된 고수준 동기화 추상화 도구이며 공유 자원(데이터)과, 그 자원에 접근하는 프로시저(함수/메서드)들을 하나의 객체(Object) 로 캡슐화한 것입니다.

동작
1. 모니터는 보이지 않는 락(implicit lock) 을 하나 가지고 있습니다.
2. 프로그래머는 그저 모니터 객체의 함수를 호출하기만 하면 됩니다.
3. 컴파일러(또는 런타임)가 자동으로 해당 함수의 시작 지점에 lock을, 끝 지점에 unlock을 삽입해 줍니다.
4. 이를 통해 모니터 내의 함수는 항상 상호 배제가 보장됩니다. (즉, 한 번에 오직 하나의 스레드만 모니터 내부에서 활성화될 수 있습니다.)
현대 언어의 적용
- Java의 synchronized 키워드가 붙은 메서드나 블록이 대표적인 모니터 구현체입니다. 프로그래머는 락을 직접 다룰 필요 없이, synchronized 선언만으로 스레드 안전성(Thread-Safety)을 확보합니다.
- C#, Python의 with lock: 구문 등도 모니터의 개념에서 파생되었습니다.

문제 : 교착 상태(Deadlock)

동기화를 위해 락(Lock) 메커니즘(세마포어, 뮤텍스 등)을 사용하기 시작하면, 시스템의 정확성을 보장할 수 있지만, 대신 교착 상태(Deadlock) 라는 치명적인 함정에 빠질 수 있습니다.

교착 상태(Deadlock) 란, 둘 이상의 프로세스들이 서로가 점유하고 있는 자원을 무한정 기다리며 프로그램 실행이 멈추는 ‘순환 대기(Circular Wait)’ 상태를 의미합니다.

스레드 1 : 자원 A를 획득 (Lock A)
스레드 2 : 자원 B를 획득 (Lock B)
스레드 1 : 자원 B를 획득 시도 ⇒ (스레드 2가 놓을 때까지 Blocked)
스레드 2 : 자원 A를 획득 시도 ⇒ (스레드 1이 놓을 때까지 Blocked)
결과 : 스레드 1은 2를, 스레드 2는 1을 영원히 기다리며 시스템 전체가 멈춥니다.

교착 상태의 4가지 발생 조건

교착 상태는 아래 4가지 조건이 동시에 충족될 때만 발생합니다. 즉, 4개 중 하나라도 깨트리면 교착 상태는 발생하지 않습니다.

상호 배제(Mutual Exclusion) : 자원은 한 번에 하나의 프로세스만 사용할 수 있어야 합니다. (동기화의 기본 전제)
점유 대기(Hold and Wait) : 프로세스가 최소한 하나의 자원을 보유(Hold) 한 채, 다른 프로세스가 보유한 자원을 대기(Wait) 합니다.
비선점(No Preemption) : 다른 프로세스가 사용 중인 자원을 강제로 빼앗을(Preempt) 수 없습니다. 자원은 사용이 끝난 후 자발적으로 반납되어야 합니다.
순환 대기(Circular Wait) : 프로세스들 간의 자원 대기 관계가 순환 고리(Cycle) 형태를 이룹니다. (위의 예시처럼 P1 → P2 → P1)

사이클이 있으면 데드락이 무조건 발생하나?
자원 인스턴스(instance) 가 1개일 때는 사이클이 곧 데드락입니다. 하지만 동일한 자원 인스턴스가 여러 개일 경우(예: CPU 코어 4개, 프린터 2대), 자원 할당 그래프에 사이클이 생겨도 데드락이 아닐 수 있습니다.

교착 상태 해결 방법

크게 예방(Prevention), 회피(Avoidance), 탐지 및 회복(Detection & Recovery), 그리고 무시(Ignorance) 4가지 접근법이 있습니다.

예방(Prevention)

교착 상태가 발생하는 4가지 조건 중 하나를 설계 시점부터 원천적으로 깨트리는 방식입니다.

상호 배제 방지 : 공유 자원을 여러 프로세스가 동시에 사용할 수 있도록 설계합니다. (예: 읽기 전용 데이터). 하지만 ‘쓰기’ 작업처럼 상호 배제가 반드시 필요한 자원에는 적용 불가능합니다.
점유 대기 방지 : 프로세스가 실행 전 필요한 모든 자원을 한꺼번에 요청하도록 강제합니다.
- 어떤 자원이 필요할지 미리 알기 어렵고, 당장 필요하지 않은 자원까지 미리 선점하므로 시스템 자원 이용률이 극도로 저하되며, 자원을 많이 요구하는 프로세스는 기아 상태(Starvation) 에 빠질 수 있습니다.
비선점 방지 : 다른 프로세스가 자원을 요청할 때, 자원을 점유한 프로세스가 즉시 반납하도록 강제로 빼앗습니다(Preempt).
- 작업 중이던 상태를 모두 저장하고 복구해야 하므로 오버헤드가 매우 크며, 적용 가능한 자원이 제한적입니다. (CPU, 메모리 등)
순환 대기 방지 : 모든 자원에 고유한 순서(Ordering) 를 매기고(예: 락A=1, 락B=2), 모든 프로세스가 이 순서대로만(번호가 증가하는 순서로만) 자원을 획득하도록 강제합니다.
- 4가지 예방법 중 가장 실용적이고 널리 쓰이는 방법입니다.

회피(Avoidance)

프로세스가 자원을 요청할 때마다, OS가 자원 할당 이후에도 시스템이 ‘안전 상태(Safe State)’를 유지할 수 있는지 동적으로 검사하는 방식입니다. (안전 상태란, 모든 프로세스가 교착 상태 없이 실행을 완료할 수 있는 순서(Safe Sequence)가 존재하는 상태를 의미합니다.)

은행원 알고리즘(Banker’s Algorithm) 이 대표적입니다.
프로세스가 앞으로 사용할 자원의 최대 요구량을 미리 OS에 알려야 합니다.
자원을 요청할 때마다 복잡한 알고리즘을 수행해야 하므로 오버헤드가 매우 큽니다. (실용성 낮음)

탐지 및 회복(Detection & Recovery)

교착 상태가 발생하는 것을 일단 허용하되, OS가 주기적으로 시스템을 검사하여 자원 할당 그래프에 사이클이 생겼는지 탐지하고, 탐지되면 회복하는 방식입니다.

회복 방법
- 프로세스 종료 : 교착 상태에 연루된 프로세스 중 하나 또는 전부를 강제 종료합니다.
- 자원 선점 : 특정 프로세스로부터 자원을 강제로 빼앗아 다른 프로세스에 할당합니다. (희생양 선정, 롤백(Rollback) 등 복잡한 문제 발생)

무시(Ignorance)

교착 상태는 매우 드물게 발생한다고 가정하고, 아무것도 하지 않는 방식입니다. 교착 상태가 발생하면 사용자가 시스템을 재부팅하거나 프로세스를 강제 종료합니다.

Windows, Linux, macOS 등 대부분의 범용 OS가 이 방식을 채택합니다. 교착 상태 예방/탐지에 드는 오버헤드보다, 문제가 발생했을 때 사용자가 재시작하는 비용이 더 싸다고 보는 것입니다. 교착 상태 방지는 프로그래머의 책임으로 넘깁니다.

운영체제