8.3.1절에서 언급했듯이 deadkock이 발생하려면 네 가지 필수 조선이 충족되어야 한다. 이러한 조건 중 적어도 하나가 충족될 수 없도록 보장함으로써, 데드락을 방지할 수 있다.
8.5.1 Mutual Exclution
상호 배제 조건은 hold 되어야 한다. 즉, 적어도 하나의 리소스가 공유 불가능해야 한다. 공유 가능한 리소스는 상호 배타적 액세스가 필요하지 않으므로 데드락에 영향을 미치지 않는다. read-only 파일은 공유 가능한 리소스의 좋은 예이다. 여러 스레드가 동시에 read-only 파일을 열려고 시도하면, 파일에 대한 동시 액세스가 허용될 수 있다. 스레드는 공유 가능한 리소스를 기다릴 필요가 없다. 그러나, 일반적으로, 상호 배제 조건을 거부하여 데드락을 방지할 수 없다. 일부 리소스는 본질적으로 공유 불가능하기 때문이다. 예를 들어, 뮤텍스 락은 여러 스레드에서 동시에 공유할 수 없다.
8.5.2 Hold and Wait
시스템에서 hold-and-wait 조건이 발생하지 않도록 하려면, 스레드가 리소스를 요청할 때마다, 다른 리소스를 hold 하지 않도록 보장해야 한다. 사용할 수 있는 프로토콜 중 하나는 각 스레드가 실행을 시작하기 전에 모든 리소스를 요청하고 할당받아야 한다는 것이다. 물론, 리소스 요청의 동적인 특성 때문에 대부분의 애플리케이션에서 비현실적(비실용적)이다.
대안 프로토콜은 스레드가 리소스가 없을 때만 리소스를 요청할 수 있도록 허용한다. 스레드는 일부 리소스를 요청하여 사용할 수 있다. 추가 리소스를 요청하기 전에, 현재 할당된 모든 리소스를 해제해야 한다.
두 프로토콜은 두 가지 주요 단점이 있다. 첫째, 리소스 활용도가 낮을 수 있다. 리소스가 할당되었지만 장기간 사용되지 않을 수 있기 때문이다. 예를 들어, 스레드는 전체 실행에 대해 뮤텍스 락을 할당받을 수 있지만, 짧은 기간동안만 필요할 수 있다. 둘째, 기아 상태가 가능하다. 여러 인기 있는 리소스가 필요한 스레드는 무기한 기다려야 할 수 있다. 적어도 필요한 리소스 중 하나가 항상 다른 스레드에 할당되기 때문이다.
8.5.3 No Preemption
데드락에 대한 세 번째 필요 조건은 이미 할당된 리소스에 대한 선점이 없다는 것이다. 이 조건이 성립하지 않도록 하려면 다음 프로토콜을 사용할 수 있다. 스레드가 일부 리소스를 보유하고 있고 즉시 할당될 수 없는 다른 리소스를 요청하는 경우, 스레드가 현재 보유하고 있는 모든 리소스가 선점된다. 즉, 이러한 리소스는 암묵적으로 해제된다. 선점된 리소스는 스레드가 기다리는 리소스 리스트에 추가된다. 스레드는 이전 리소스와, 요청하는 새 리소스를 모두 되찾을 수 있을 때만 다시 시작된다.
또는, 스레드가 어떤 리소스를 요청하면, 먼저 사용할 수 있는지 확인한다. 사용 가능하다면 리소스를 할당하고, 그렇지 않으면 추가 리소스를 기다리는 다른 스레드에 할당되었는지 확인한다. 만약 그렇다면, 요구한 리소스를 대기 스레드에서 선점하여 요청 스레드에 할당한다. 리소스를 사용할 수 없거나 대기 스레드에서 보유하지 않으면, 요청 스레드는 기다려야 한다. 기다리는 동안, 일부 리소스가 선점될 수 있지만, 다른 스레드가 요청하는 경우에만 가능하다(기다리는 동안 다른 스레드가 요청하면 현재 스레드가 가진 자원이 선점-강제로 해제될 수 있음). 스레드는 요청하는 새 리소스를 할당받고, 기다리는 동안 선점된 리소스를 복구할 때만 다시 시작할 수 있다.
이 프로토콜은 종종 CPU 레지스터와 데이터베이스 트랜잭션과 같이 상태를 쉽게 저장하고 복원할 수 있는 리소스에 적용된다. 일반적으로 뮤텍스 락과 세마포어와 같은 리소스에는 적용할 수 없고, 정확히 데드락이 가장 흔히 발생하는 리소스 타입이다.
8.5.4 Circular Wait
지금까지 제시된 데드락 방지를 위한 세 가지 옵션은 일반적으로 대부분의 상황에서 비실용적이다. 그러나, 데드락에 대한 마지막 조건인 circular-wait 조건은 필요한 조건 중 하나를 무효화하여 실용적인 solution을 제시한다. 이 조건이 절대 충족되지 않도록 하는 한 가지 방법은, 모든 리소스 유형에 대한 전체 순서를 부과하고, 각 스레드가 열거 순서대로(번호가 증가하는 순서로) 리소스를 요청하도록 요구하는 것이다.
예를 들어, R = {R1, R2, ..., Rm} 을 리소스 유형의 집합으로 한다. 각 리소스 유형에 교유한 integer number를 할당하여, 두 리소스를 비교하고 순서에서 다른 것보다 앞서는지 여부를 결정할 수 있다. 형식적으로, 일대일 함수 F: R → N을 정의한다. 여기서 N은 자연수 집합이다. 시스템의 모든 동기화 객체 간의 순서를 개발해서, 애플리케이션 프로그램에서 이 방법을 성취할 수 있다. 예를 들어, 그림 8.1의 Pthread 프로그램의 lock 순서는 다음과 같다.
F(first_mutex) = 1
F(second_mutex) = 5이제 데드락을 방지하기 위해 다음 프로토콜을 고려할 수 있다: 각 스레드는 열거 순서대로만 리소스를 요청할 수 있다. 즉, 스레드는 처음에 리소스의 인스턴스(Ri)를 요청할 수 있다. 그런 다음, 스레드는 F(Rj) > F(Ri) 인 경우에만 리소스 Rj 를 요청할 수 있다. 예를 들어, 위에서 정의한 함수를 사용하면, first_mutex와 second_mutex를 동시에 사용하려는 스레드는, 먼저 first_mutex를 요청한 다음 second_mutex를 요청해야 한다. 또는, 리소스 Rj 의 인스턴스를 요청하는 스레드가 F(Ri) ≥ F(Rj) 가 되도록 모든 리소스 Ri 를 해제해야 한다고 요구할 수 있다. 또한 동일한 리소스 유형의 여러 인스턴스가 필요한 경우, 모든 인스턴스에 대해 single(단일) 요청을 발행해야 한다.
이 두 프로토콜을 사용하면, circular-wait(순환 대기) 조건이 충족될 수 없다. circular wait이 존재한다고 가정하여 이 사실을 증명할 수 있다. 순환 대기에 관련된 스레드 집합을 {T0, T1, ..., Tn} 이라고 하고, 여기서 Ti 는 스레드 Ti+1 이 보유한 리소스 Ri 를 기다리고 있다. (인덱스에 모듈러 연산을 사용하므로 Tn 은 T0 이 보유한 리소스 Rn 을 기다린다.)
모듈러 연산(modulo arithmetic): 나머지 연산
- 스레드 Ti 는 리소스 R(i+1) mod (n+1) 를 기다림
그러면, 스레드 Ti+1 이 리소스 Ri 를 보유하면서 Ri+1 을 요청하므로, 모든 i에 대해 F(Ri) < F(Ri+1) 이어야 한다. 하지만, 이 조건은 F(R0) < F(R1) < ... < F(Rn) < F(R0) 을 의미한다. 추이성(어떤 관계가 일정한 순서로 이어지는 것, ex: a>b, c>a ⇒ b<c)에 의해 F(R0) < F(R0) 이며, 이는 불가능하다. 따라서, 순환 대기는 있을 수 없다.
순서 또는 계층을 개발하는 것만으로 데드락을 방지할 수 없다는 것을 명심해야한다. 순서를 따르는 프로그램을 작성하는 것은 애플리케이션 개발자의 몫이다. 그러나, lock 순서를 설정하는 것은 어려울 수 있고, 특히 수백 개 수천 개의 lock이 있는 시스템에서는 더 그렇다. 이러한 과제를 해결하기 위해, 많은 Java 개발자는 System.identitiyHashCode(Object)메서드를 lock 획득 순서 함수로 사용하는 전략을 채택했다.
System.identitiyHashCode() : Java 객체의 기본 해시값 반환
- 자원 객체마다 고유한 정수 값이 나오기 때문에, 이 값을 기준으로 자원의 우선순서를 정할 수 있음
- 이렇게 하면 수동으로 락 순서를 정하지 않고, 시스템 차원에서 자동으로 순서 부여 가능
또한, lock 순서를 부과하는 것이 데드락 방지를 보장하지 않는다는 점도 중요하다 lock을 동적으로 획득할 수 있는 경우에. 예를 들어, 두 계좌 간에 자금을 이체하는 함수가 있다고 가정해보면, race condition을 방지하기 위해, 각 계좌에는 그림 8.7과 같은 get_lock() 함수에서 얻은 mutex lock이 있다. deadlock은 두 개의 스레드가 동시에 transaction() 함수를 호출하여, 다른 계좌와 전치하는(바꾸어 넣는) 경우 발생할 수 있다. 즉, 한 스레드가 transaction(checking_account, savings_account, 25.0)을 호출할 수 있고, 다른 계좌가 transaction(savings_account, checking_account, 50.0)을 호출할 수 있다.
