[OS] 동기화 기법과 교착 상태 - 9

동기화 기법과 교착상태 — OS가 병행성을 다루는 방법

두 개 이상의 프로세스가 공유 자원을 동시에 사용할 때 발생하는 문제와, 이를 해결하기 위한 동기화 기법 및 교착상태의 원리를 정리한다.

💡 핵심: 동기화는 프로세스 간 실행 순서를 통제하고, 교착상태는 그 통제가 잘못됐을 때 발생하는 최악의 시나리오다.

1. 동기화 기법(Synchronization)

프로세스 여러 개가 동시에 실행되는 환경에서는 같은 자원을 두 프로세스가 동시에 건드리는 상황이 반드시 생긴다. 예를 들어 두 스레드가 동시에 count++를 실행하면 결과가 1 증가가 아니라 뒤죽박죽이 될 수 있다. 이것이 ¹레이스 컨디션(Race Condition)이고, 동기화²는 이를 막기 위해 각 프로세스의 처리 순서를 결정하는 기법이다.

세마포(Semaphore)

세마포는 1965년 다익스트라³가 제안한 방식으로, 정수 변수 S와 두 가지 연산 P(wait)·V(signal)만으로 임계구역⁴을 보호한다. P 연산은 S가 0이 되면 프로세스를 대기시키고, V 연산은 대기 중인 프로세스를 깨워 S 값을 증가시킨다. 핵심 제약은 하나다. 세마포에 대한 연산은 처리 도중 인터럽트⁵가 걸려서는 안 된다. 연산 도중에 인터럽트가 끼어들면 상호배제 자체가 깨지기 때문이다.

P0

임계구역 들어갈게 — P(S) → S: 1→0

🔒 P0 임계구역 사용 중...

나도 들어가려는데... P(S) → S: 0, 대기

P1

⏳ P1 대기 중

P0

다 썼어, 나갈게 — V(S) → S: 0→1

✅ P1 깨어남, 임계구역 진입

세마포에는 대기 방식이 두 가지다. busy-waiting 방식은 S가 0인 동안 while 루프를 계속 돌며 CPU를 낭비하고, sleep 방식은 wait()에 들어온 순간 sleep queue에 넣어 대기시켰다가 V 연산이 호출될 때 우선순위에 따라 깨운다. 실무에서는 CPU 점유 낭비를 줄이기 위해 sleep 방식을 기본으로 사용한다.

모니터(Monitor)

모니터는 세마포보다 추상화 수준이 높은 동기화 구조체다. 공유 자원과 그 자원을 다루는 프로시저를 하나의 단위로 묶어, 한 순간에 오직 하나의 프로세스만 모니터 내부에 진입할 수 있도록 보장한다. 외부 프로세스가 공유 자원에 직접 접근하는 것이 원천 차단되고, Wait·Signal 연산으로만 내부 상태를 제어한다. 세마포가 개발자가 직접 P·V 순서를 맞춰야 하는 저수준 도구라면, 모니터는 그 책임을 구조 자체에 위임한 고수준 도구다.

외부 프로세스

→

모니터 진입 시도

→

대기 or 진입

→

공유 자원 접근

→

Signal 후 퇴장

C#의 lock 키워드와 Monitor.Enter / Exit가 모니터 개념의 직접 구현이다. lock(_obj) { ... }은 내부적으로 Monitor.Enter와 Monitor.Exit를 감싼 것이며, 한 스레드가 lock 블록 안에 있는 동안 다른 스레드는 진입하지 못하고 대기 큐에 쌓인다. OS 교재에서 배운 모니터가 C# 런타임에 그대로 녹아 있는 셈이다.

❌ 동기화 없음

// 두 스레드가 동시 접근
count++; // 레이스 컨디션 발생

✅ Monitor(lock) 사용

lock(_obj) {
  count++; // 안전
}

2. 교착상태(Deadlock)

교착상태는 둘 이상의 프로세스가 서로 상대방이 점유한 자원을 기다리면서 아무도 진행하지 못하는 상태다. 어느 한 쪽을 강제로 종료하지 않으면 시스템이 영원히 멈춰 있게 된다. 단순한 버그가 아니라 구조적인 문제이기 때문에, 코드를 아무리 들여다봐도 재현 자체가 어려운 경우가 많다.

교착상태 발생 4가지 조건

아래 네 가지 조건이 동시에 모두 충족될 때만 교착상태가 발생한다. 하나라도 깨지면 교착상태는 일어나지 않는다.

🔒 상호배제

한 번에 하나의 프로세스만 자원을 사용할 수 있다.

🚫 비선점

자원을 점유 중인 프로세스에서 강제로 빼앗을 수 없다.

✋ 점유와 대기

자원을 점유한 채로 다른 자원을 추가로 요청하며 대기한다.

🔄 환형대기

프로세스들이 원형을 이루며 서로의 자원을 기다린다.

C#에서의 교착상태 예시

멀티스레드 코드에서 lock 순서가 일치하지 않으면 교착상태가 발생한다. 스레드 A는 lockA를 잡고 lockB를 기다리고, 스레드 B는 lockB를 잡고 lockA를 기다리는 구조가 되면 환형대기 조건이 충족되어 둘 다 영원히 대기 상태에 빠진다.

object lockA = new object();
object lockB = new object();

// 스레드 A
lock(lockA) {
    lock(lockB) { // lockB 기다림 }
}

// 스레드 B — 동시에 실행 중
lock(lockB) {
    lock(lockA) { // lockA 기다림 → 교착상태! }
}

⚠️ 핵심: lock 획득 순서를 코드베이스 전반에서 일치시키는 것이 교착상태 예방의 가장 현실적인 방법이다.

3. 교착상태 해결 방법

교착상태를 다루는 방법은 크게 예방·회피·탐지 세 가지로 나뉜다. 이론적으로 가장 완벽한 방법은 예방이지만, 실제로 적용하면 비용이 너무 크다. 그래서 현대 OS와 DB는 대부분 탐지 + 회복 전략을 채택한다.

① 예방(Prevention) — 발생 조건 4개 중 하나를 원천 차단

상호배제 부정 — 자원을 여러 프로세스가 동시에 쓸 수 있게 한다. 프린터 같은 자원엔 현실적으로 불가능하다.

비선점 부정 — 자원을 강제로 빼앗을 수 있게 한다. 저장된 작업 내용을 잃을 수 있어 비용이 크다.

점유와 대기 부정 — 실행 전 필요한 모든 자원을 미리 확보한다. 자원 낭비와 기아 문제가 발생한다.

환형대기 부정 — 자원에 번호를 부여해 한 방향으로만 요청하도록 한다. 새 자원 추가 시 재구성이 필요하다.

② 회피(Avoidance) — 은행원 알고리즘(Banker's Algorithm)

• 자원을 할당할 때마다 "이 상태가 안전한가?"를 계산하고, 안전하다고 판단될 때만 자원을 내준다.
• 안전상태(Safe State): 모든 작업이 정상적으로 완료될 수 있는 상태.
• 자원 수와 프로세스 수가 고정적이어야 하고, 고장·오류 등으로 실제 자원 수는 예측하기 어려워 현실 적용에 한계가 있다.
• 대화식 시스템(Interactive System)에는 적용 불가.

③ 탐지 + 회복(Detection + Recovery) — 가장 현실적

• 타임아웃 방식: 일정 시간 진행 없는 프로세스를 교착상태로 간주. Windows가 채택한 방식.
• 자원 할당 그래프 방식: 프로세스·자원 관계를 그래프로 그려 사이클 발생 시 교착상태로 탐지.
• 회복: 탐지 후 교착상태에 빠진 프로세스를 하나씩 종료하거나 전부 종료.

예방

→

비용 너무 큼

회피

→

현실 적용 한계

탐지+회복

→

✅ 현대 OS 채택

4. 무한연기(Infinite Postponement)와 에이징

교착상태와 헷갈리기 쉬운 개념이 무한연기다. 교착상태는 "서로 기다려서" 멈추는 것이고, 무한연기는 "스케줄링 정책이 편향되어서" 특정 프로세스에 자원이 계속 할당되지 않는 상태다. 기술적으로 교착상태는 아니지만, 해당 프로세스 입장에서는 결과가 동일하다 — 영원히 실행되지 못한다.

이를 해결하는 기법이 에이징(Aging)이다. 대기 시간이 길어질수록 우선순위를 점진적으로 높여서, 오래 기다린 프로세스가 결국 실행 기회를 얻도록 보장한다. 기아(Starvation)⁶ 현상도 같은 원리로 에이징 기법으로 해결한다.

낮은 우선순위 프로세스

→

계속 대기 중...

→

에이징 적용

→

우선순위 상승 → 실행

📎 용어 설명

1. 레이스 컨디션(Race Condition) — 두 개 이상의 스레드/프로세스가 공유 자원에 동시 접근할 때 실행 순서에 따라 결과가 달라지는 현상
2. 동기화(Synchronization) — 두 개 이상의 프로세스를 한 순간에 동시 처리할 수 없기 때문에 각 프로세스에 대한 처리 순서를 결정하는 것
3. 다익스트라(E.W. Dijkstra) — 네덜란드 컴퓨터 과학자. 세마포 외에도 최단 경로 알고리즘(다익스트라 알고리즘)과 은행원 알고리즘을 제안했다.
4. 임계구역(Critical Section) — 공유 자원에 접근하는 코드 영역으로, 한 번에 하나의 프로세스만 진입해야 하는 구간
5. 인터럽트(Interrupt) — 현재 실행 중인 작업을 잠시 멈추고 다른 작업을 처리하도록 CPU에 신호를 보내는 메커니즘
6. 기아(Starvation) — 스케줄링 정책의 편향으로 특정 프로세스가 자원을 계속 할당받지 못하는 현상. 무한연기와 비슷하지만 주로 CPU 스케줄링 맥락에서 사용한다.

운영체제 동기화 교착상태 Deadlock 세마포 모니터 C# Unity 멀티스레드