정의
교착(deadlock)은 둘 이상의 실행 흐름이 각자 자원을 쥔 채 상대가 쥔 자원을 기다려 어느 쪽도 진행하지 못하는 상태다.[1]
OSEK OS는 같은 상태를 서로 잠긴 자원을 무한히 기다려 태스크 실행이 불가능해지는 것으로 적는다.[2] 어느 쪽 표현이든 핵심은 같다 — 아무도 자원을 놓지 않고, 놓지 않는 이유가 서로에게 있다.
교착은 락을 자원별로 나누어 동시성을 얻은 뒤에 흔해진다. 락이 여러 개가 되는 순간 한 실행 흐름이 여러 락을 겹쳐 잡는 상황이 함께 따라오기 때문이다. 락이 하나뿐이어도 자기 자신과 교착할 수는 있다 — POSIX는 NORMAL 유형 뮤텍스를 이미 쥔 스레드가 그것을 다시 잠그면 교착이 된다고 규정한다.[3]
순환 대기
가장 단순한 형태는 락 두 개를 서로 다른 순서로 잡는 코드다. 한쪽은 L1을 잡고 L2를 잡으려 하고, 다른 쪽은 L2를 잡고 L1을 잡으려 한다. 이 코드가 반드시 교착에 빠지는 것은 아니다 — 첫 흐름이 L1을 잡은 직후에 문맥 전환이 일어나 둘째 흐름이 L2를 잡을 때만 걸린다. 점유와 대기 관계를 그래프로 그리면 교착의 표식은 그 안의 순환으로 나타난다.[1]
락을 겹쳐 잡지 않아도 같은 구조가 만들어질 수 있다. OSEK OS가 드는 예에서는 T1이 세마포어 S1을 점유한 채 이벤트를 기다려 대기 상태로 가고, 그동안 실행된 낮은 우선순위 태스크 T2가 S2를 점유한다. T1이 다시 준비 상태가 되어 S2를 요청하면 대기로 돌아가고, 이어 T2가 S1을 요청하는 순간 교착이 완성된다.[2]
성립 조건
네 가지 조건이 모두 성립해야 교착이 발생한다.[1]
- 상호 배제 — 실행 흐름이 자원을 배타적으로 점유한다.
- 점유 후 대기 — 이미 얻은 자원을 쥔 채로 다른 자원을 기다린다.
- 비선점 — 쥐고 있는 자원을 강제로 빼앗을 수 없다.
- 순환 대기 — 각 흐름이 사슬의 다음 흐름이 요청하는 자원을 쥐고 있는 순환 사슬이 존재한다.
네 조건 중 하나라도 성립하지 않으면 교착은 일어날 수 없다. 예방 기법들은 저마다 이 중 하나를 겨냥한다.
전순서 부여
가장 실용적인 예방은 순환 대기를 막는 것이고, 그 가장 직접적인 방법은 락 획득에 전순서(total ordering)를 부여하는 것이다. 락이 L1과 L2뿐이라면 언제나 L1을 먼저 잡기로 정하면 순환은 만들어질 수 없다. 락이 많은 시스템에서 전체 순서를 정하기는 어렵고 대개 필요하지도 않으므로, 락 그룹 사이의 부분 순서(partial ordering)로 구조를 잡는 편이 현실적이다.[1]
인자로 받은 락 두 개를 잡아야 하는 함수처럼 순서를 코드에 못 박을 수 없는 자리도 있다. 이때는 락의 주소처럼 실행 중에 정해지는 값을 순서 기준으로 삼아, 호출자가 어떤 순서로 넘겼든 항상 같은 순서로 잡게 만들 수 있다.
자원 접근 규칙
실시간 운영체제는 예방을 프로그래머의 규율에 맡기는 대신 자원 사용 방식 자체를 제한하기도 한다. OSEK OS는 자원을 점유한 상태에서 태스크를 종료하거나 대기 상태로 보내는 서비스 호출을 금지하고, 같은 자원의 중첩 점유를 금지하며, 여러 자원을 겹쳐 점유할 때 요청과 해제를 LIFO 순서로 하도록 요구한다.[2] 이 제한들 위에서 우선순위 상한 프로토콜이 순환 대기가 형성될 여지 자체를 없애며, 그 결과 자원 관리는 우선순위 역전과 교착을 함께 배제한다고 규정된다.