스레드가 자원 요청을 할 때 미래에 발생 가능한 Deadlock이 있는지 확인한다.
이를 위해서는 자원이 어떻게 요청 되었는지에 대한 정보가 필요하다.
ex) R1, R2 2개의 자원을 갖는 시스템에서 스레드 P가 R1을 점유한 상태로 (R1→P) R2를 요청 (P→R2)하고, 스레드 Q는 R2를 점유한 상태로 (R2→Q) R1을 요청 (Q→R1)하는 상황
순환 구조가 발생하여 Deadlock이 발생할 위험이 있으므로 자원 요청을 **거절 (reject)**할 수 있다.
필요한 자원의 최대 개수를 알면 “교착 회피 알고리즘”을 만들 수 있다.
“교착 회피 알고리즘”은 순환 대기 상황이 발생하지 않도록 자원 할당 상태를 검사한다.
→ 자원 할당 상태 : 사용 가능한(available) 자원의 수, 할당된(allocated) 자원의 수, 스레드들의 최대 요구 수(maximum demands)에 의해 정의된다.
시스템이 어떤 순서로든 스레드들이 요청하는 모든 자원을 DeadLock을 발생시키지 않고 차례로 모두 할당해줄 수 있는 것을 의미한다.
즉, **안전 순서(safe sequence)**를 찾을 수 있다면 시스템은 안전하다.
→ <T1, T2, …, Tn> 스레드 순서가 안전하다는 것은
Ti가 요청하는 자원을 [시스템에 현재 남아있는 자원 + 수행을 마칠 모든 스레드] Tj들이 (j < i) 반납하는 자원들로 만족 시킬 수 있는 것이다.