교착 상태
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
교착 상태는 둘 이상의 프로세스가 자원을 점유하고 서로 다른 프로세스가 점유한 자원을 요청하여 더 이상 진행할 수 없는 상태를 의미한다. 1971년 E. G. 코프만은 상호 배제, 점유 대기, 비선점, 순환 대기, 네 가지 조건이 모두 충족되어야 교착 상태가 발생한다고 밝혔다. 운영 체제는 교착 상태를 예방, 회피, 무시, 발견하는 방법으로 관리한다. 교착 상태는 프로그래밍뿐만 아니라 게임 이론, 현실의 교통 상황 등 다양한 분야에서 나타날 수 있다.
1971년에 E. G. 코프만 교수는 교착 상태가 발생하기 위한 네 가지 필요 조건을 제시했다.
2. 교착 상태의 조건
이 조건들 중 하나라도 만족하지 않으면 교착 상태는 발생하지 않는다. 이 중 순환 대기 조건은 점유 대기 조건과 비선점 조건을 만족해야 성립하므로, 위 네 가지 조건은 서로 완전히 독립적인 것은 아니다.[1]
2. 1. 상호 배제 (Mutual exclusion)
E. G. 코프만 교수는 1971년에 교착 상태가 발생하기 위한 네 가지 필요 조건을 제시했는데, 그 중 하나가 상호 배제이다.[1] 상호 배제는 프로세스들이 자원에 대해 배타적인 통제권을 요구하는 것을 의미한다.[1] 즉, 한 번에 한 프로세스만 해당 자원을 사용할 수 있다.[1]
임계 영역에서 상호 배제를 사용한 경우를 예로 들어보자.
변수 A와 변수 B, 두 개의 데이터가 있다고 가정한다. 그리고 'B에 A의 값을 더하고 A를 0으로 만드는' 처리 A와 'A에 B의 값을 더하고 B를 0으로 만드는' 처리 B, 두 개의 처리가 있다. 멀티스레딩 환경에서 변수 A와 B에 접근하기 위해 임계 영역 A(CSA)와 임계 영역 B(CSB)를 사용한다.
처리 A와 B는 다음과 같다.
| 처리 A | 처리 B |
|---|---|
만약 스레드 A가 CSA에 진입한 직후 컨텍스트 스위칭이 발생하여 스레드 B가 CSB에 진입하고, 다시 스레드 A가 CSB에 진입을 시도하면 스레드 B가 이미 CSB를 점유하고 있으므로 대기 상태에 들어간다. 마찬가지로 스레드 B가 CSA에 진입을 시도하면 스레드 A가 이미 CSA를 점유하고 있으므로 대기 상태에 들어간다. 이렇게 두 스레드 모두 대기 상태가 되어 프로그램이 정지하는 교착 상태가 발생한다.
다음 표는 위 과정을 시간 순서대로 정리한 것이다.
| 스레드 A | 스레드 B | CSA 소유자 | CSB 소유자 |
|---|---|---|---|
| 스레드 생성 | |||
| 처리 A 시작 | |||
| CSA 진입 | 스레드 A | ||
| 컨텍스트 스위칭 A→B | |||
| 대기 | 스레드 생성 | ||
| 처리 B 시작 | |||
| CSB 진입 | 스레드 B | ||
| 컨텍스트 스위칭 B→A | |||
| CSB 진입 실패 | 대기 | ||
| 컨텍스트 스위칭 A→B | |||
| CSB 해제 대기 | CSA 진입 실패 | ||
| CSA 해제 대기 | |||
| 교착 상태 발생 | |||
2. 2. 점유 대기 (Hold and wait)
프로세스가 이미 자원을 할당받은 상태에서 다른 자원을 기다리는 것을 의미한다. 1971년 E. G. 코프만 교수는 교착 상태가 발생하기 위한 네 가지 조건 중 하나로 점유 대기를 제시했다.예를 들어, 변수 A와 B, 그리고 'B에 A의 값을 더하고 A를 0으로 만드는' 처리 A와 'A에 B의 값을 더하고 B를 0으로 만드는' 처리 B가 있다고 가정하자. 멀티스레딩 환경에서 각 처리는 임계 영역(Critical Section)을 통해 변수에 접근한다. 처리 A는 임계 영역 A(CSA)와 임계 영역 B(CSB)에 순차적으로 진입하고, 처리 B는 CSB와 CSA에 순차적으로 진입한다고 가정하자.
만약 스레드 A가 CSA에 진입한 직후 컨텍스트 스위칭이 발생하여 스레드 B가 CSB에 진입하면, 스레드 A는 CSB에 진입하기 위해 대기하고, 스레드 B는 CSA에 진입하기 위해 대기하는 상황이 발생한다. 이 경우 두 스레드는 서로가 점유하고 있는 자원을 기다리며 무한정 대기 상태에 빠지게 된다.
아래 표는 이 과정을 시간 순서대로 나타낸 것이다.
| 스레드 A | 스레드 B | CSA 소유자 | CSB 소유자 |
|---|---|---|---|
| 스레드 생성 | |||
| 처리 A 시작 | |||
| CSA 진입 | 스레드 A | ||
| 컨텍스트 스위칭 A→B | |||
| 대기 | 스레드 생성 | ||
| 처리 B 시작 | |||
| CSB 진입 | 스레드 B | ||
| 컨텍스트 스위칭 B→A | |||
| CSB 진입 실패 | 대기 | ||
| 컨텍스트 스위칭 A→B | |||
| CSB 해제 대기 | CSA 진입 실패 | ||
| CSA 해제 대기 | |||
| 교착 상태 발생 | |||
2. 3. 비선점 (No preemption)
1971년 E. G. 코프만 교수는 교착 상태가 일어나기 위한 네 가지 필요 조건 중 하나로 비선점을 제시하였다.[1] 비선점은 프로세스가 이미 할당받은 자원을 강제로 빼앗을 수 없는 상황을 의미한다.[1] 즉, 자원은 해당 자원을 점유하고 있는 프로세스에 의해서만 해제될 수 있다.[1]이는 점유대기와 함께 순환대기 조건이 성립하기 위한 조건이기도 하다.
다음은 임계 영역에서 상호 배제를 사용했을 때 비선점으로 인해 교착 상태가 발생하는 예시이다.
변수 A와 B, 그리고 'B에 A의 값을 더하고 A를 0으로 만드는' 처리 A와 'A에 B의 값을 더하고 B를 0으로 만드는' 처리 B가 있다고 가정하자. 멀티스레딩 환경에서 변수 A와 B에 접근하기 위해 임계 영역 A(CSA)와 임계 영역 B(CSB)를 사용한다.
처리 A와 처리 B의 순서는 다음과 같다.
처리 A# CSA에 진입
# CSB에 진입
# B에 A의 값을 더한다
# A에 0을 대입
# CSB에서 나온다
# CSA에서 나온다
처리 B# CSB에 진입
# CSA에 진입
# A에 B의 값을 더한다
# B에 0을 대입
# CSA에서 나온다
# CSB에서 나온다
이 경우, 다음과 같은 순서로 프로그램이 동작하면 교착 상태가 발생한다.
| 스레드 A | 스레드 B | CSA 소유자 | CSB 소유자 |
|---|---|---|---|
| 스레드 생성 | |||
| 처리 A 시작 | |||
| CSA 진입 | 스레드 A | ||
| 컨텍스트 스위칭 A→B | |||
| 대기 | 스레드 생성 | ||
| 처리 B 시작 | |||
| CSB 진입 | 스레드 B | ||
| 컨텍스트 스위칭 B→A | |||
| CSB 진입 실패 | 대기 | ||
| 컨텍스트 스위칭 A→B | |||
| CSB 해제 대기 | CSA 진입 실패 | ||
| CSA 해제 대기 | |||
| 교착 상태 발생 | |||
위 표에서 볼 수 있듯이, 스레드 A가 CSA에 진입한 직후 컨텍스트 스위칭이 발생하여 스레드 B가 CSB에 진입한다. 이후 스레드 A는 CSB에, 스레드 B는 CSA에 진입하려 하지만, 이미 상대 스레드가 해당 임계 영역을 점유하고 있어 대기 상태에 빠진다. 이처럼 두 스레드가 서로 상대방의 자원을 기다리며 무한정 대기하는 상황이 발생하는데, 이를 교착 상태라고 한다.
2. 4. 순환 대기 (Circular wait)
각 프로세스가 순환적으로 다음 프로세스가 요구하는 자원을 가지고 있는 상황이다. 즉, 프로세스 간의 자원 요구 및 보유 관계가 원형을 이룬다. 이 조건 중 하나라도 만족하지 않으면 교착 상태는 발생하지 않는다. 순환 대기 조건은 점유대기 조건과 비선점 조건을 만족해야 성립하므로, 네 가지 조건은 서로 완전히 독립적이지 않다.[1]임계 영역에서 상호 배제를 사용한 경우의 예는 다음과 같다.
변수 A와 변수 B, 두 데이터와 'B에 A의 값을 더하고 A를 0으로 만드는' 처리 A, 'A에 B의 값을 더하고 B를 0으로 만드는' 처리 B, 두 처리가 있다고 가정한다. 멀티스레딩으로 처리하기 위해 변수 A와 변수 B에 접근하기 위한 임계 영역 A(이하 CSA)와 임계 영역 B(이하 CSB), 두 임계 영역을 준비한다.
처리 A의 순서는 다음과 같다.
# CSA에 진입
# CSB에 진입
# B에 A의 값을 더한다.
# A에 0을 대입
# CSB에서 나온다.
# CSA에서 나온다.
처리 B의 순서는 다음과 같다.
# CSB에 진입
# CSA에 진입
# A에 B의 값을 더한다.
# B에 0을 대입
# CSA에서 나온다.
# CSB에서 나온다.
이 경우 다음과 같이 프로그램이 동작하면 데드락이 발생한다.
처리 A를 실행하는 스레드 A가 생성되어 처리가 시작된다. 처리 A의 1에서 CSA에 진입한 직후 컨텍스트 스위칭이 발생하고, 처리 B를 실행하는 스레드 B가 생성되어 처리 B의 1에서 CSB에 진입한다. 다시 컨텍스트 스위칭이 발생하여 스레드 A가 활성화되고, 2에서 CSB에 진입하려고 시도한다. 그러나 스레드 B가 이미 CSB에 진입해 있기 때문에 스레드 A는 대기 상태에 들어가고, 스레드 B가 활성화된다. 스레드 B는 마찬가지로 2에서 CSA에 진입하려고 시도하지만 스레드 A가 이미 CSA에 진입해 있기 때문에 스레드 B는 대기 상태에 들어간다.
이렇게 두 스레드 모두 대기 상태가 되어 프로그램이 정지한다. 이 상태가 데드락이다.
이상의 처리를 시간 순서에 따라 정리하면 다음 표와 같다.
| 스레드 A | 스레드 B | CSA 소유자 | CSB 소유자 |
|---|---|---|---|
| 스레드 생성 | |||
| 처리 A 시작 | |||
| CSA 진입 | 스레드 A | ||
| 컨텍스트 스위칭 A→B | |||
| 대기 | 스레드 생성 | ||
| 처리 B 시작 | |||
| CSB 진입 | 스레드 B | ||
| 컨텍스트 스위칭 B→A | |||
| CSB 진입 실패 | 대기 | ||
| 컨텍스트 스위칭 A→B | |||
| CSB 해제 대기 | CSA 진입 실패 | ||
| CSA 해제 대기 | |||
| 데드락 발생 | |||
현대의 대부분의 운영 체제는 교착 상태를 완벽하게 막는 것이 불가능하다고 간주한다.[1] 따라서 교착 상태가 발생했을 때, 각 운영 체제는 자체적인 비표준 방식으로 대응한다. 대부분의 접근 방식은 코프만 조건 중 하나(특히 순환 대기)를 막는 것을 목표로 한다.[2]
3. 교착 상태의 관리
교착 상태를 관리하기 위한 주요 방법으로는 교착 상태의 예방, 회피, 무시, 발견 등이 있다.
3. 1. 교착 상태의 예방 (Prevention)
교착 상태를 예방하기 위해서는 교착 상태 발생 조건인 상호 배제, 점유와 대기, 비선점, 환형 대기 중 하나 이상을 제거해야 한다.
이러한 방법들은 자원 사용의 효율성을 떨어뜨리고 비용이 많이 들 수 있다는 단점이 있다.[1]
교착 상태 회피 방법은 다음과 같다.
이 외에도 다양한 회피 방법이 존재한다.
우선순위 상한 프로토콜 기능이 확장된 뮤텍스를 이용하는 것도 교착 상태 회피 방법 중 하나이다. 우선순위 상한 프로토콜은 임베디드 시스템에서 주로 사용되며, 효과가 있는 프로그램도 제한적이어서 범용적으로 사용할 수는 없다.
3. 1. 1. 상호 배제 조건 제거
교착 상태는 둘 이상의 프로세스가 공유 가능한 자원을 사용할 때 발생하는 것이므로 공유 불가능한, 즉 상호 배제 조건을 제거하면 교착 상태를 해결할 수 있다.
3. 1. 2. 점유 대기 조건 제거
프로세스가 실행되기 전에 필요한 모든 자원을 한 번에 할당하거나, 자원을 점유하지 않은 상태에서만 다른 자원을 요청할 수 있도록 한다. 하지만 이 방법은 자원 과다 사용으로 인한 효율성 저하, 프로세스가 요구하는 자원을 파악하는 데 드는 비용, 자원에 대한 내용을 저장 및 복원하기 위한 비용, 기아 상태 발생, 무한 대기 등의 문제점이 있다.[1]
3. 1. 3. 비선점 조건 제거
자원을 선점 가능하도록 만들어, 필요한 경우 다른 프로세스가 자원을 빼앗을 수 있도록 한다. 비선점 프로세스에 대해 선점 가능한 프로토콜을 만들어 준다.[1]
3. 1. 4. 순환 대기 조건 제거
자원 유형에 따라 순서를 매겨, 프로세스가 정해진 순서대로만 자원을 요청하도록 한다. 이러한 예방 방법들은 자원 사용의 효율성을 떨어뜨리고, 비용이 많이 들 수 있다는 단점이 있다.
3. 2. 교착 상태의 회피 (Avoidance)
교착 상태 회피는 자원 할당 시 교착 상태가 발생하지 않도록 추가적인 정보를 활용하여, 시스템이 순환 대기 상태에 빠지지 않도록 하는 방법이다.[1] 자원이 어떻게 요청될지에 대한 추가 정보를 제공하도록 요구하여, 시스템에 순환 대기(circular wait)가 발생하지 않도록 자원 할당 상태를 검사한다.
교착 상태 회피 방법에는 뮤텍스를 사용하거나, 임계 영역 진입에 실패했을 때 이미 진입한 임계 영역에서 빠져나와 처리를 종료하는 방법 등이 있다. 그 외에도 우선순위 상한 프로토콜을 이용한 회피 방법이 있지만, 이는 임베디드 시스템에서 주로 사용되며 범용적인 방법은 아니다.
3. 2. 1. 자원 할당 그래프 알고리즘 (Resource Allocation Graph Algorithm)
시스템은 자원 할당 상태를 그래프로 표현하여 교착 상태 발생 가능성을 검사한다.[1]
3. 2. 2. 은행원 알고리즘 (Banker's algorithm)
은행원 알고리즘은 시스템의 안정 상태(safe state)를 유지하면서 자원을 할당하는 알고리즘이다. 자원이 어떻게 요청될지에 대한 추가 정보를 제공하도록 요구하여, 시스템에 순환 대기(circular wait)가 발생하지 않도록 자원 할당 상태를 검사한다.[1]
교착 상태를 회피하기 위한 알고리즘에는 다음 두 가지가 있다.3. 3. 교착 상태의 무시 (Ignorance)
교착 상태 발생 확률이 매우 낮은 경우, 교착 상태를 예방하거나 회피하는 데 드는 비용이 더 크다고 판단하여 별다른 조치를 취하지 않는다. 예방 혹은 회피 기법을 프로그래밍해서 넣으면 성능에 큰 영향을 미칠 수 있기 때문이다.
3. 4. 교착 상태의 발견 (Detection)
교착 상태 발생 여부를 주기적으로 검사하여, 교착 상태가 발생하면 이를 해결하는 방법이다. 발견 알고리즘은 시스템 성능에 영향을 줄 수 있다.[1]
4. 프로그램상의 예 (일본어 문서)
프로그래밍 환경에서 교착 상태는 여러 스레드가 서로 자원을 점유하고 대기하면서 발생한다.
변수 A와 B, 그리고 각 변수에 접근하기 위한 임계 영역 CSA와 CSB가 있다고 가정하자. 처리 A는 B에 A의 값을 더하고 A를 0으로 만들며, 처리 B는 A에 B의 값을 더하고 B를 0으로 만든다.
처리 A와 처리 B가 다음과 같은 순서로 진행될 때 교착 상태가 발생할 수 있다.
- 처리 A: CSA 진입 → CSB 진입 → B에 A 값 더함 → A에 0 대입 → CSB 해제 → CSA 해제
- 처리 B: CSB 진입 → CSA 진입 → A에 B 값 더함 → B에 0 대입 → CSA 해제 → CSB 해제
만약 스레드 A가 CSA에 진입한 직후, 스레드 B가 CSB에 진입하면, 스레드 A는 CSB를, 스레드 B는 CSA를 기다리며 교착 상태가 발생한다. 이 과정을 표로 나타내면 다음과 같다.
| 스레드 A | 스레드 B | CSA 소유자 | CSB 소유자 |
|---|---|---|---|
| 스레드 생성 | |||
| 처리 A 시작 | |||
| CSA 진입 | 스레드 A | ||
| 컨텍스트 스위칭 A→B | |||
| 대기 | 스레드 생성 | ||
| 처리 B 시작 | |||
| CSB 진입 | 스레드 B | ||
| 컨텍스트 스위칭 B→A | |||
| CSB 진입 실패 | 대기 | ||
| 컨텍스트 스위칭 A→B | |||
| CSB 해제 대기 | CSA 진입 실패 | ||
| CSA 해제 대기 | |||
| 교착 상태 발생 | |||
이러한 교착 상태는 다음과 같은 방법으로 회피할 수 있다.
- 두 처리 과정에서 CSA와 CSB에 접근하는 순서를 동일하게 한다.
- 뮤텍스를 사용하여 변수 A와 B에 대한 접근을 제어한다.
- 임계 영역에 진입할 수 없으면, 이미 진입한 임계 영역에서 빠져나와 처리를 종료한다.
객체 지향 프로그래밍에서는 클래스 간 의존 관계를 단방향 계층 구조로 설계하고, 잠금을 거는 객체의 클래스 순서를 통일하여 교착 상태를 회피할 수 있다. 관찰자 패턴을 사용하여 하위 계층에서 상위 계층으로 호출할 때는 잠금을 해제하여 "하위 계층에서 잠금 → 상위 계층에서 잠금" 발생을 막는다.
락 프리 및 웨이트 프리 알고리즘을 사용하는 것도 교착 상태 회피 방법 중 하나이다.
4. 1. 데드락 발생 원인
기본적으로 데드락은 자원의 수가 2 이상일 때 발생한다. 예를 들어, 임계 영역이 하나라면 자원은 하나로 계산되고, 임계 영역이 두 개라면 자원의 수는 2이다. 자원의 수가 1이라면, 세마포어 등은 바이너리 세마포어가 되어 뮤텍스와 같이 동작하므로 데드락은 발생하지 않고 라이브락이 발생한다. CSMA/CD에서는 난수를 사용하여 라이브락을 회피하는 방법을 사용한다.자원의 수를 1로 하는 것은 데드락을 회피하는 근본적인 해결 방법이지만, 그 경우 프로그램의 병렬성이 현저히 저하되므로, 현대 컴퓨터 프로그래밍에서 현실적인 수단이라고는 할 수 없다.
4. 2. 예시
임계 영역에서 상호 배제를 사용한 경우의 예시는 다음과 같다.변수 A와 변수 B, 두 데이터가 있다고 가정한다. 'B에 A의 값을 더하고 A를 0으로 만드는' 처리 A와 'A에 B의 값을 더하고 B를 0으로 만드는' 처리 B, 두 가지 처리가 있다. 멀티스레딩으로 처리하기 위해 변수 A와 변수 B에 접근하기 위한 임계 영역 A(이하 CSA)와 임계 영역 B(이하 CSB), 두 임계 영역을 준비한다.
처리 A는 다음 순서로 진행된다고 가정한다.
# CSA에 진입
# CSB에 진입
# B에 A의 값을 더한다
# A에 0을 대입
# CSB에서 나온다
# CSA에서 나온다
처리 B는 다음 순서로 진행된다고 가정한다.
# CSB에 진입
# CSA에 진입
# A에 B의 값을 더한다
# B에 0을 대입
# CSA에서 나온다
# CSB에서 나온다
이 경우 프로그램이 다음과 같이 동작하면 데드락이 발생한다.
처리 A를 실행하는 스레드 A가 생성되어 처리가 시작된다. 처리 A의 첫 단계에서 CSA에 진입한 직후 컨텍스트 스위칭이 발생하고, 처리 B를 실행하는 스레드 B가 생성되어 처리 B의 첫 단계에서 CSB에 진입한다. 다시 컨텍스트 스위칭이 발생하여 스레드 A가 활성화되고, 두 번째 단계에서 CSB에 진입하려고 시도한다. 그러나 스레드 B가 이미 CSB에 진입해 있기 때문에 스레드 A는 대기 상태에 들어가고, 스레드 B가 활성화된다. 스레드 B는 마찬가지로 두 번째 단계에서 CSA에 진입하려고 시도하지만 스레드 A가 이미 CSA에 진입해 있기 때문에 스레드 B는 대기 상태에 들어가 버린다.
이렇게 두 스레드는 모두 대기 상태가 되어 프로그램이 정지해 버린다. 이 상태가 데드락이다.
이상의 처리를 시간 순서에 따라 정리하면 다음 표와 같다.
| 스레드 A | 스레드 B | CSA 소유자 | CSB 소유자 |
|---|---|---|---|
| 스레드 생성 | |||
| 처리 A 시작 | |||
| CSA 진입 | 스레드 A | ||
| 컨텍스트 스위칭 A→B | |||
| 대기 | 스레드 생성 | ||
| 처리 B 시작 | |||
| CSB 진입 | 스레드 B | ||
| 컨텍스트 스위칭 B→A | |||
| CSB 진입 실패 | 대기 | ||
| 컨텍스트 스위칭 A→B | |||
| CSB 해제 대기 | CSA 진입 실패 | ||
| CSA 해제 대기 | |||
| 데드락 발생 | |||
4. 3. 회피 방법
교착 상태를 회피하기 위한 방법은 다음과 같다.- '''CSA'''와 '''CSB'''에 들어가는 순서를 두 처리 과정에서 동일하게 한다.
- "변수 A와 변수 B에 접근한다"는 뮤텍스를 사용한다.
- 임계 영역에 들어갈 수 없는 경우, 이미 들어가 있는 임계 영역에서 빠져나와 처리를 종료한다.
그 외에도 다양한 회피 방법이 존재한다.
우선순위 상한 프로토콜 기능이 확장된 뮤텍스를 이용하는 것으로도 교착 상태를 회피할 수 있다. 우선순위 상한 프로토콜은 임베디드 시스템에서 주로 사용되며, 효과가 있는 프로그램도 제한적이어서 범용적으로 사용할 수 있는 방법은 아니다.
4. 3. 1. 객체 지향 프로그래밍에서의 회피 방법
객체 지향 프로그래밍에서는 클래스 간의 의존 관계를 단방향으로 하고, 클래스 간 의존 관계의 구조가 계층 구조가 되도록 설계하는 것이 일반적인 방법이다. 여기서 독립적인 쪽을 아래로 정의한다. 즉, 상위 계층 클래스는 하위 계층 클래스에 대해 알고 있지만, 하위 계층 클래스는 상위 계층 클래스에 대해 알지 못한다. 상위 계층 클래스에서 하위 계층 클래스로의 호출은 일반적인 메서드 호출로 수행하며, 하위 계층에서 상위 계층으로 돌아갈 때는 관찰자 패턴을 사용한다.교착 상태를 회피하기 위해서는 잠금을 거는 객체의 클래스 순서를 통일하는 것이 한 가지 방법이다. 클래스의 의존 관계가 계층 구조일 때는 반드시 상위 계층 클래스부터 순서대로 잠금을 걸어야 한다. 그러면 상위 계층에서 잠금을 건 채로 하위 계층 객체의 메서드를 호출할 수 있다.
또한, 관찰자 패턴으로 상위 계층으로 돌아갈 때는 자신이 걸고 있는 모든 잠금을 해제한 후 돌아가야 한다. 그렇게 함으로써 "하위 계층에서 잠금 → 상위 계층에서 잠금" 발생을 막을 수 있다. 같은 계층끼리는 잠금을 걸지 않으며, 필요한 경우에는 상위 계층에서 잠금을 건다. 이러한 방법을 통해 교착 상태를 회피할 수 있다.
4. 3. 2. 락 프리(Lock-free)에서의 회피
락 프리 및 웨이트 프리 알고리즘에서도 교착 상태를 회피할 수 있다.5. 기타 용도(Other uses)
"데드락"이라는 용어는 컴퓨터 과학 외에도 다양한 분야에서 사용된다.
- 게임 이론: 게임 이론에서 상호 간에 가장 이득이 되는 행동이 지배적인 행동이 되는 게임 유형을 의미한다.[2]
- 교통: 일본 효고현 가코가와시 가코가와정에는 네 방향 모두에 정지 표지판이 있는 교차로가 있는데, 이는 교착 상태와 비슷한 상황을 유발할 수 있다. 도로교통법 제36조에 따르면 세 방향에서 동시에 차량이 진입할 경우 교차로 중앙을 기준으로 왼쪽에 있는 차량이 우선 통행하지만, 네 방향 동시 진입에 대한 명확한 규정은 없다.[1]
5. 1. 미디어(Media)
"데드락"을 제목으로 하거나 소재로 사용한 작품들은 다음과 같다.- 문학: 사라 파레츠키의 탐정 소설과 샬레인 해리스의 수키 스택하우스 소설 데드락, ABC 워리어즈의 등장인물 데드락
- 영화: 데드락 (1931), 데드락 (1943), 데드락 (1970), 데드락 (2021)
- 텔레비전: 용감한 자들: 보호자들, 배틀스타 갤럭티카의 "교착 상태", 스타 트렉: 보이저의 "교착 상태", 교착 상태
- 음악: 캔(Can)과 프런트 라인 어셈블리의 노래 "데드락", 밴드 데드락, Xdinary Heroes의 데드락 EP
- 비디오 게임: ''배틀스타 갤럭티카 데드락(Battlestar Galactica Deadlock)'', ''발로란트(Valorant)''의 캐릭터, 밸브 개발 게임 데드락(Deadlock) (비디오 게임), ''데드락: 플래니터리 콩퀘스트(Deadlock: Planetary Conquest)'', ''랫쳇: 데드락(Ratchet: Deadlocked)''
5. 1. 1. 문학 (Literature)
- 사라 파레츠키의 탐정 소설 데드락이 있다.
- 샬레인 해리스의 수키 스택하우스 소설 데드락이 있다.
- ABC 워리어즈의 등장인물로 데드락이 있다.
5. 1. 2. 영화 (Film)
- 데드락 (1931년 영화)는 스튜어트 로마, 마조리 휴메, 워릭 워드가 주연한 영국 범죄 영화이다.
- 데드락 (1943년 영화)는 존 슬레이터가 주연한 영국 범죄 영화이다.
- 데드락 (1970년 영화)는 마리오 아도르프가 주연한 서독 서부극이다.
- 데드락 (2021년 영화)는 브루스 윌리스가 주연한 미국 액션 스릴러 영화이다.
5. 1. 3. 텔레비전 (Television)
- 용감한 자들: 보호자들(The Bold Ones: The Protectors)은 ''교착 상태''(Deadlock)로도 알려져 있으며, 1969년에서 1970년까지 방영된 미국 범죄 드라마 텔레비전 시리즈이다.[1]
- 배틀스타 갤럭티카의 "교착 상태"는 ''배틀스타 갤럭티카''의 에피소드이다.[2]
- 스타 트렉: 보이저의 "교착 상태"는 ''스타 트렉: 보이저''의 에피소드이다.
- 교착 상태 (TV 시리즈)는 토마스 웨더럴이 주연한 2018년 호주 TV 시리즈이다.
5. 1. 4. 음악 (Music)
- 캔(Can)의 노래 "데드락 (Deadlock)" (1970년 발매, 사운드트랙 앨범 수록)[1]
- 프런트 라인 어셈블리(Front Line Assembly)의 노래 "데드락 (Deadlock)" (1998년 발매, ''크라이오제닉 스튜디오 컴필레이션 (Cryogenic Studios Compilation)'' 수록)[2]
- 데드락 (독일의 멜로딕 데스 메탈 밴드)
- 데드락 (Xdinary Heroes의 2023년 EP)
5. 1. 5. 비디오 게임 (Video games)
- 2017년에 출시된 턴제 전략 게임 ''배틀스타 갤럭티카 데드락(Battlestar Galactica Deadlock)''
- ''발로란트(Valorant)''의 플레이 가능한 캐릭터 데드락
- 밸브에서 개발 중인 게임 ''데드락(Deadlock) (비디오 게임)''
- 아콜레이드(Accolade)에서 개발한 컴퓨터 게임 ''데드락: 플래니터리 콩퀘스트(Deadlock: Planetary Conquest)''
- 인섬니악 게임즈(Insomniac Games)에서 개발한 ''랫쳇: 데드락(Ratchet: Deadlocked)'' (랫쳇 & 클랭크 시리즈)
5. 2. 게임 이론 (Game Theory)
게임 이론에서 상호적으로 가장 유익한 행동이 지배적인 행동이기도 한 게임의 한 유형이다.[2]5. 3. 현실에서의 예: 교통 (일본어 문서)
일본 효고현 가코가와시 가코가와정에는 4방향에 정지 표지판이 있는 사거리가 있어, 교착 상태와 유사한 상황이 발생할 수 있다. 도로교통법 제36조에 따르면 3방향에서 동시에 차량이 진입했을 때는 교차로 중심을 기준으로 왼쪽 차량이 우선 통행하지만, 4방향 동시 진입에 대한 명확한 규정은 없다.[1]5. 3. 1. 법적 규정의 한계
일본 효고현 가코가와시 가코가와정에는 효고현도 148호 오쿠보이나미가코가와선(兵庫県道148号線) 도중에 4방향에 정지 표지판이 있는 사거리가 있다. 도로교통법 제36조에 따르면, 3방향에 동시에 차량이 진입했을 경우 교차로 중심을 기준으로 왼쪽 차량에게 우선 통행권이 주어진다.[1] 그러나 4방향 동시 진입에 대한 명확한 규정은 없다.[1] 효고현 경찰은 이와 관련한 취재에 대해 손짓, 몸짓 등으로 의사소통을 하고 서행하며 통과할 것을 권장했다.[1]5. 3. 2. 경찰의 권고
효고현 경찰은 취재자에게 손짓과 몸짓으로 의사소통을 하고 서행하면서 통과할 것을 권고했다.[1]참조
[1]
서적
Operating System Principles
http://books.google.[...]
Wiley-India
2012-01-29
[2]
서적
Principles of operating systems
http://books.google.[...]
Cengage Learning
2012-01-28
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com