교착상태를 피하기 위한 락 순서와 복구 전략
교착상태의 필요조건과 자원 할당 그래프를 바탕으로 예방, 회피, 탐지·복구 전략 및 락 설계 원칙을 정리한다.
2026-08-14 · 최초 발행 2026-01-04
서로 가진 자원을 기다리며 멈추는 상황
교착상태는 둘 이상의 프로세스가 상대가 점유한 자원을 기다리느라 무한 대기에 들어간 상태다. 외부 개입이 없다면 해당 프로세스는 작업을 끝낼 수 없고, 시스템의 진행도 멈춘다.
운영체제와 동시성 프로그램은 이 상태를 예방하거나, 위험한 할당을 피하거나, 발생 후 탐지와 복구를 수행하는 방식으로 다룬다. 어느 방식을 택하든 안전성과 자원 활용률 사이에는 트레이드오프가 있다.
Process 1이 Resource A를 확보한 뒤 Resource B를 요청하고, Process 2는 Resource B를 확보한 뒤 Resource A를 요청한다고 하자. 두 프로세스는 상대가 가진 자원을 기다리게 되며, 어느 쪽도 먼저 진행할 수 없다.
아래 코드는 서로 다른 순서로 두 mutex를 획득해 이 상황을 만든다.
// Deadlock 발생 코드
pthread_mutex_t lock1, lock2;
// Thread 1
void *thread1_func(void *arg) {
pthread_mutex_lock(&lock1);
printf("Thread 1: Locked lock1\n");
sleep(1); // 타이밍 보장
pthread_mutex_lock(&lock2); // Deadlock!
printf("Thread 1: Locked lock2\n");
pthread_mutex_unlock(&lock2);
pthread_mutex_unlock(&lock1);
return NULL;
}
// Thread 2
void *thread2_func(void *arg) {
pthread_mutex_lock(&lock2);
printf("Thread 2: Locked lock2\n");
sleep(1); // 타이밍 보장
pthread_mutex_lock(&lock1); // Deadlock!
printf("Thread 2: Locked lock1\n");
pthread_mutex_unlock(&lock1);
pthread_mutex_unlock(&lock2);
return NULL;
}Coffman 조건이 동시에 성립할 때
교착상태가 되려면 다음 4가지 필요조건이 모두 충족돼야 한다. 따라서 처리 전략은 이 가운데 하나라도 제거하는 데서 출발한다.
상호배제(Mutual Exclusion)는 한 자원을 한 번에 하나의 프로세스만 사용할 수 있는 상태다. 프린터, 파일 잠금, 데이터베이스 레코드가 예가 되며, 공유 자원의 일관성을 위해 필요한 경우가 많다.
점유와 대기(Hold and Wait)는 이미 자원을 가진 프로세스가 다른 자원을 기다리는 상황이다. Lock A를 획득한 채 Lock B를 기다리는 경우가 여기에 해당한다.
비선점(No Preemption)은 프로세스가 자발적으로 자원을 반납할 때까지 강제로 회수할 수 없다는 조건이다. CPU와 메모리는 선점 가능한 자원이지만, 프린터나 데이터베이스 트랜잭션은 선점하면 일관성이 깨질 수 있다.
순환 대기(Circular Wait)는 프로세스 집합 {P0, P1, ..., Pn}에서 P0이 P1의 자원을, P1이 P2의 자원을, ..., Pn이 P0의 자원을 기다리는 구조다. 대기 그래프의 사이클이 바로 이 조건을 보여 준다.
이 그래프에는 P1 → R2 → P2 → R3 → P3 → R1 → P1의 사이클이 있다. 순환 대기가 존재하므로 교착상태가 발생한다.
필요조건을 끊어 예방하기
예방은 교착상태의 4가지 필요조건 중 하나를 원천적으로 만족하지 못하게 하는 접근이다.
상호배제를 없애는 방법은 자원을 공유 가능하게 만드는 것이다. Read-only 파일이나 프린터 Spooling이 예지만, 쓰기 가능한 파일처럼 본질적으로 배타적인 자원에는 적용하기 어렵다.
점유와 대기를 없애려면 필요한 락을 한 번에 확보하거나, 추가 락 획득에 실패했을 때 이미 가진 락을 해제해야 한다.
// 방법 1: 모든 자원을 한 번에 요청
void all_at_once() {
// 원자적으로 모든 Lock 획득
lock_multiple(&lock1, &lock2, &lock3);
// Critical Section
unlock_all(&lock1, &lock2, &lock3);
}
// 방법 2: 자원 보유 없이 요청
void no_hold_and_wait() {
while (1) {
if (try_lock(&lock1)) {
if (try_lock(&lock2)) {
// 성공 - 둘 다 획득
break;
} else {
unlock(&lock1); // lock2 실패 시 lock1 해제
}
}
// 재시도
}
}이 방식은 자원 활용률을 낮출 수 있고, 기아 상태가 생길 수 있으며, 필요한 자원을 미리 예측하기 어렵다는 제약이 있다.
비선점 조건은 자원을 강제로 회수할 수 있게 만들어 끊는다. 다만 선점으로 일관성이 깨지는 자원에는 맞지 않는다.
순환 대기를 차단하는 가장 널리 쓰이는 방법은 모든 자원에 순서를 정하고, 그 순서를 지켜 획득하게 하는 것이다.
// 자원에 순서 부여
enum ResourceOrder {
LOCK_A = 1,
LOCK_B = 2,
LOCK_C = 3
};
// 모든 프로세스가 동일한 순서로 획득
void ordered_locking() {
pthread_mutex_lock(&lock1); // Order 1
pthread_mutex_lock(&lock2); // Order 2
pthread_mutex_lock(&lock3); // Order 3
// Critical Section
pthread_mutex_unlock(&lock3);
pthread_mutex_unlock(&lock2);
pthread_mutex_unlock(&lock1);
}락 순서 강제는 구현이 단순하고 순환 구조를 원천적으로 막을 수 있어 많은 시스템에서 채택된다. 반면 자원의 전체 순서를 정의하기 어려울 수 있고, 설계의 유연성은 줄어든다.
안전한 상태에서만 자원을 할당하는 방법
회피(Avoidance)는 교착상태가 될 가능성이 있는 할당을 승인하지 않는다. 은행원 알고리즘(Banker's Algorithm)은 시스템이 안전 상태인지 검사한 뒤에만 요청을 처리하는 대표적인 방식이다.
// 시스템 상태
int available[RESOURCES]; // 사용 가능한 자원
int maximum[PROCESSES][RESOURCES]; // 최대 필요량
int allocation[PROCESSES][RESOURCES]; // 현재 할당량
int need[PROCESSES][RESOURCES]; // 추가 필요량
// 안전 상태 검사
bool is_safe_state() {
int work[RESOURCES];
bool finish[PROCESSES] = {false};
// work = available
for (int i = 0; i < RESOURCES; i++)
work[i] = available[i];
// 완료 가능한 프로세스 찾기
while (true) {
bool found = false;
for (int p = 0; p < PROCESSES; p++) {
if (!finish[p]) {
// need[p] <= work 확인
bool can_finish = true;
for (int r = 0; r < RESOURCES; r++) {
if (need[p][r] > work[r]) {
can_finish = false;
break;
}
}
if (can_finish) {
// 프로세스 p 완료 가능
for (int r = 0; r < RESOURCES; r++)
work[r] += allocation[p][r];
finish[p] = true;
found = true;
}
}
}
if (!found)
break;
}
// 모든 프로세스가 완료 가능하면 안전
for (int p = 0; p < PROCESSES; p++)
if (!finish[p])
return false;
return true;
}
// 자원 요청 처리
bool request_resources(int process, int request[]) {
// 1. request <= need 확인
// 2. request <= available 확인
// 임시로 할당
for (int r = 0; r < RESOURCES; r++) {
available[r] -= request[r];
allocation[process][r] += request[r];
need[process][r] -= request[r];
}
// 안전 상태 확인
if (is_safe_state()) {
return true; // 할당 승인
} else {
// 롤백
for (int r = 0; r < RESOURCES; r++) {
available[r] += request[r];
allocation[process][r] -= request[r];
need[process][r] += request[r];
}
return false; // 할당 거부
}
}이론적으로는 교착상태를 발생시키지 않지만, 각 프로세스의 최대 자원 필요량을 사전에 알아야 한다. 프로세스 수와 자원 종류가 고정돼야 하고 계산 오버헤드도 커서 실용성이 낮다.
발생을 허용한 뒤 탐지하고 복구하기
탐지 및 복구 방식은 교착상태 자체는 허용하고, 발생 여부를 확인한 뒤 개입한다. Wait-for 그래프의 사이클을 찾는 방식으로 탐지할 수 있다.
// Wait-for 그래프 생성 및 사이클 탐지
typedef struct {
bool **graph; // graph[i][j]: i가 j를 기다림
int processes;
} WaitForGraph;
// DFS로 사이클 탐지
bool has_cycle_util(WaitForGraph *g, int v, bool visited[], bool rec_stack[]) {
visited[v] = true;
rec_stack[v] = true;
for (int i = 0; i < g->processes; i++) {
if (g->graph[v][i]) {
if (!visited[i]) {
if (has_cycle_util(g, i, visited, rec_stack))
return true;
} else if (rec_stack[i]) {
return true; // 사이클 발견!
}
}
}
rec_stack[v] = false;
return false;
}
bool detect_deadlock(WaitForGraph *g) {
bool visited[g->processes];
bool rec_stack[g->processes];
for (int i = 0; i < g->processes; i++) {
visited[i] = false;
rec_stack[i] = false;
}
for (int i = 0; i < g->processes; i++) {
if (!visited[i]) {
if (has_cycle_util(g, i, visited, rec_stack))
return true;
}
}
return false;
}복구에서는 교착상태에 든 프로세스를 종료하거나, 희생자를 골라 자원을 선점한다.
// 방법 1: 모든 교착상태 프로세스 종료
void abort_all_deadlocked_processes() {
// 빠르지만 비용이 큼
}
// 방법 2: 하나씩 종료하며 재탐지
void abort_one_at_a_time() {
while (detect_deadlock()) {
int victim = select_victim(); // 비용 최소화
terminate_process(victim);
}
}희생자는 우선순위가 낮은 프로세스, 실행 시간이 짧은 프로세스, 자원을 적게 사용한 프로세스, 대화식이 아닌 배치 프로세스 등을 기준으로 선택할 수 있다.
void recover_by_preemption() {
// 1. 희생자 선택
int victim = select_victim();
// 2. 자원 회수
rollback_process(victim); // 체크포인트로 되돌림
// 3. 자원 재할당
allocate_to_waiting_process();
}자원 선점에서는 같은 프로세스만 반복해서 희생돼 기아 상태에 빠지지 않게 해야 한다. 체크포인트로 되돌리는 비용과, 선점 대상 자원의 일관성도 함께 고려해야 한다.
교착상태 발생 빈도가 매우 낮다면 무시(Ignorance) 전략도 선택할 수 있다. Ostrich Algorithm은 문제를 무시하고 발생 시 재부팅하는 방식이며, UNIX와 Windows의 일부 상황이 예다. 예방·회피·탐지 비용이 가끔 재부팅하는 비용보다 클 때 적용한다.
운영 환경에서의 대응 방식
Linux Kernel은 락 순서 강제와 Lockdep 같은 탐지 도구를 함께 사용한다.
// 1. Lock 순서 강제 (Prevention)
spin_lock(&parent->lock);
spin_lock_nested(&child->lock, SINGLE_DEPTH_NESTING);
// 2. Lockdep (Detection)
// 런타임에 Lock 순서 위반 탐지
CONFIG_PROVE_LOCKING=y
// 3. Deadlock 탐지 도구
// - Lockdep: 컴파일 시간 + 런타임 검증
// - Kcsan: 동시성 버그 탐지데이터베이스에서는 Timeout, Wait-for 그래프 검사, 트랜잭션 Rollback을 조합할 수 있다.
-- 1. Timeout 기반 탐지
SET LOCK_TIMEOUT = 5000; -- 5초
-- 2. Deadlock 자동 탐지 및 복구
-- InnoDB는 주기적으로 Wait-for 그래프 검사
-- 탐지 시 하나의 트랜잭션 Rollback
-- 3. Deadlock 정보 조회
SHOW ENGINE INNODB STATUS;Java에서는 고정된 순서의 synchronized, tryLock과 Timeout, JMX 기반 탐지를 사용할 수 있다.
// 1. 순서 강제 (Prevention)
private static final Object lock1 = new Object();
private static final Object lock2 = new Object();
public void orderedLocking() {
synchronized(lock1) { // 항상 lock1 먼저
synchronized(lock2) {
// Critical Section
}
}
}
// 2. tryLock with Timeout (Avoidance)
Lock lock1 = new ReentrantLock();
Lock lock2 = new ReentrantLock();
public void tryLockExample() throws InterruptedException {
while (true) {
if (lock1.tryLock(50, TimeUnit.MILLISECONDS)) {
try {
if (lock2.tryLock(50, TimeUnit.MILLISECONDS)) {
try {
// Success
return;
} finally {
lock2.unlock();
}
}
} finally {
lock1.unlock();
}
}
// Retry
}
}
// 3. JMX 기반 Deadlock 탐지
ThreadMXBean tmx = ManagementFactory.getThreadMXBean();
long[] deadlocked = tmx.findDeadlockedThreads();
if (deadlocked != null) {
System.out.println("Deadlock detected!");
}락을 다루는 코드와 설계의 기준
락 순서를 모든 코드 경로에서 일관되게 유지하고, 필요한 범위만 락으로 보호해야 한다. 팀이 공유하는 락 순서를 문서화하고, 주기적인 교착상태 탐지와 동시성 테스트 도구를 운영 과정에 포함하는 편이 좋다. TSan과 Helgrind를 활용하는 방법도 있다.
// 1. Lock 순서 일관성 유지
// Good
void safe_transfer(Account *from, Account *to, int amount) {
Account *first = (from < to) ? from : to;
Account *second = (from < to) ? to : from;
lock(first);
lock(second);
// Transfer
unlock(second);
unlock(first);
}
// 2. try-lock 패턴
bool try_acquire_locks(Lock *l1, Lock *l2) {
if (try_lock(l1)) {
if (try_lock(l2)) {
return true;
}
unlock(l1);
}
return false;
}
// 3. Timeout 사용
bool acquire_with_timeout(Lock *lock, int ms) {
return timed_lock(lock, ms);
}
// 4. Lock-free 알고리즘 고려
atomic_int counter;
__atomic_fetch_add(&counter, 1, __ATOMIC_SEQ_CST);예방은 안전하지만 자원 활용률을 낮출 수 있다. 탐지와 복구는 유연한 대신 오버헤드가 따른다. 따라서 락 순서 강제를 기본으로 두고, 모니터링으로 보완하는 하이브리드 접근이 효과적이다.