데드락

두 개 이상의 프로세스나 스레드가 서로 상대방이 점유하고 있는 자원을 기다리며, 서로 무한히 기다리는 상태에 빠지는 현상

데드락의 발생 조건

다음 네 가지 Coffman 조건이 동시에 성립할 때 데드락이 발생할 수 있다. 각 조건은 데드락의 필요 조건이지만, 네 조건이 성립한다고 해서 모든 실행에서 반드시 데드락이 발생하는 것은 아니다.

상호 배제(Mutual Exclusion)

한 번에 하나의 작업만 사용할 수 있는 자원이 존재하는 상태다.

점유 대기(Hold and Wait)

작업이 하나 이상의 자원을 이미 보유한 상태에서 다른 작업이 가진 추가 자원을 기다리는 상태다.

비선점(No Preemption)

작업에 할당된 자원을 운영체제가 강제로 회수할 수 없고, 해당 작업이 스스로 반납해야 하는 상태다.

환형 대기(Circular Wait)

작업들이 원형으로 연결되어 다음 작업이 보유한 자원을 기다리는 상태다. 예를 들어 P1은 P2의 자원을, P2는 P1의 자원을 기다릴 수 있다.

해결 방법

예방 기법은 네 가지 필요 조건 중 하나가 성립하지 않도록 설계한다. 회피·감지·복구 방식은 데드락 가능성을 다루는 시점과 방법이 다르다.

예방

교착 상태가 발생하지 않도록 알고리즘을 작성함(환형 대기 방지를 위한 자원 획득 순서 지정…)

회피

교착 상태에 빠질 가능성에 대해 검사를 하고 그럴 가능성이 없을 때만 자원에 접근하도록 함(은행원 알고리즘)

감지

자원 할당 그래프, 자원 요청 알고리즘을 사용 → 오버헤드가 상당히 크다

복구

  1. 프로세스 종료: 교착 상태와 관련된 프로세스를 일부 또는 전부 종료한다.
  2. 자원 선점과 롤백: 특정 작업의 자원을 회수하고, 필요하면 해당 작업을 이전의 안전한 상태로 되돌린다.

상호 배제와 비선점의 차이

상호 배제는 한 자원을 동시에 몇 개의 작업이 사용할 수 있는지에 관한 조건이다. 비선점은 이미 할당된 자원을 운영체제가 작업 도중에 회수할 수 있는지에 관한 조건이다. 하나는 동시 사용 가능성, 다른 하나는 강제 회수 가능성을 설명하므로 서로 다른 조건이다.