사실 제가 아는 데드록은 발로란트 요원 데드록밖에 모릅니다. 그러나 컴퓨터 시스템 개념중에 데드록이라는 개념이 있어 이번 시간에는 해당 개념에 대해 알아보는 시간을 가져보겠습니다.

Deadlock

둘 이상의 스레드가 서로 자원을 점유한 채, 상대방이 가진 자원을 기다리며 무한히 멈춰 있는 상태를 말합니다.
→ 서로 양보하지 않고 기다리기만 해서 프로그램이 멈춥니다.

예시

1. 스레드 A 와 스레드 B가 있습니다.
2. A는 Lock 1을 먼저 획득하고, Lock 2를 기다립니다.
3. B는 Lock 2를 먼저 획득하고, Lock 1을 기다립니다.

→ 이렇게 되면 서로가 서로가 가진 Lock을 기다리며 영원히 기다리는 상태입니다.

발생 조건 (Coffman 4조건)

Deadlock이 발생하려면 다음 4가지 조건을 모두 동시에 만족해야합니다.

1. 상호 배제 (Mutual Exclusion)
   한 번에 한 스레드만 자원을 사용할 수 있습니다.
2. 점유 대기 (Hold and Wait)
   자원을 점유한 상태에서 다른 자원을 기다립니다.
3. 비선점 (No preemption)
   자원을 강제로 빼앗을 수 없습니다.
4. 순환 대기 (Circular Wait)
   스레드 간 자원을 기다리는 원형 대기 발생합니다.

→ 그러므로 위 조건 하나의 조건이라도 깨뜨리면 Deadlock을 방지할 수 있습니다.

해결 방법

1. 예방 (Prevention): 4가지 조건 중 하나 이상을 깨뜨립니다.

• 락을 항상 고정된 순서로 획득 (순환 대기 방지)
• 자원 모두를 한 번에 할당하게 강제 (점유 대기 방지)
• 일정 시간이 지나면 선점(preemtion) 수행
  
  

2. 회피 (Avoidance): 시스템이 위험한 상태인지 미리 판단 후 실행 여부를 결정합니다.

• 대표 알고리즘으로는 Banker’s Algorithm이 있음
• 현실 OS에서는 사용하기 어려움
  
  

3. 탐지 후 회복 (Detection & Recovery)

• Lock 대기 그래프를 만들어 순환 있는지 탐지
• Deadlock 상태가 감지되면 프로세스 강제 종료 등으로 회복
  
  

4. 무시 (Ignore it)

• Deadlock은 드물게 일어나니 무시하자는 전략.
• 그러나 사용자가 책임지고 피할 수 있게 코딩해야함.

PintOS 에서

여러 개의 Lock을 중첩해서 획득(nested lock acquire) 하는 경우 Deadlock 위험이 있습니다.

lock_acquire(&lock_a);
lock_acquire(&lock_b);  // A 스레드가 이렇게 하고 있고

// 동시에
lock_acquire(&lock_b);
lock_acquire(&lock_a);  // B 스레드가 이렇게 하고 있다면 Deadlock 가능성있음

→ 특히나 Priority donation 구현 시 nested donation 이 잘못 구현되면 Deadlock이 생길 수 있습니다.

요약

항목	설명
정의	자원을 놓지 않고 서로 기다리면서 영원히 멈추는 상태
발생 조건	상호배제, 점유 대기, 비선점, 순환 대기 모두 만족
Pintos 위험 지점	nested lock_acquire(), priority donation 트리
방지 방법	고정된 락 순서 사용, timeout, 자원 선할당, 탐지 등
실제 전략	대부분은 순환 대기 방지 + 코드 설계로 예방