교착상태(Dead Lock)

교착상태(Dead Lock)

: 상호 배제에 의해 나타나는 문제점으로, 둘 이상의 프로세스들이 자원을 점유한 상태에서 서로 다른 프로세스가 점유하고 있는 자원을 요구하며 무기한으로 기다리는 현상

 

---

 

교착상태 발생의 필요 충분 조건

: 교착상태가 발생하기 위해서는 아래의 네 가지 조건이 모두 충족되어야 하고, 하나라도 충족되지 않으면 교착상태가 발생하지 않는다.

 

1. 상호 배제(Mutual Exclusion) : 한번에 한 개의 프로세스만이 공유 자원을 사용해야 한다.
2. 점유와 대기(Hold and Wait) : 최소한 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당되어 사용되고 있는  자원을 추가로 점유하기 위해 대기중인 프로세스가 있어야 한다.
3. 비선점(Non-preemption) : 다른 프로세스에 할당된 자원은 사용이 끝날 때 까지 강제로 빼앗을 수 없다.
4. 환형 대기(Circular Wait) : 공유자원과 공유자원을 사용하기 위해 대기하는 프로세스들이 원형으로 구성되어 있어 자신에게 할당된 자원을 점유하면서 앞이나 뒤에 있는 프로세스의 자원을 요구해야 한다.

 

교착상태 예방

: 교착상태가 발생하지 않도록 사전에 시스템을 제어하는 방법이 있는데, 이는 교착상태 발생의 네가지 조건 주 어느 하나를 제거하면 수행되고 자원 낭비가 심하다.

 

1. 상호 배제 부정 : 한번에 여러 개의 프로세스가 공유 자원을 사용할 수 있도록 한다.
2. 점유 및 대기 부정 : 프로세스가 실행되기 전 필요한 모든 자원을 할당하여 프로세스 대기를 없애거나 자원이 점유되지 않았을 때만 자원을 요구하게 한다.
3. 비선점 부정 : 자원을 점유하고 있는 프로세스가 다른 자원을 요구할 때 점유중인 자원을 반납하고, 요구한 자원을 사용하기 위해 기다리게 한다.
4. 환형 대기 부정 : 자원을 선형 순서로 분류하여 고유 번호를 할당하고, 각 프로세스는 현재 점유한 자원의 교유 번호보다 앞이나 뒤와 같이 어느 한쪽 방향으로만 자원을 요구하게 한다.

 

교착상태 회피

: 교착상태가 발생할 가능성을 배제하지 않고 교착상태가 발생하면 적절히 피해나가는 회피 방법이 있는데, 주로 은행원 알고리즘이 사용된다.

 

은행원 알고리즘(Banker's Algorithm)

• 이는 다익스트라가 제안한 기법으로, 은행에서 모든 고객의 요구가 충족되도록 현금을 할당하는데서 유래한 기법
• 각 프로세스에게 자원을 할당하여 교착상태가 발생하지 않으며 모든 프로세스가 완료될 수 있는 상태를 안전상태, 교착상태가 발생할 수 있는 상태를 불안전 상태라고 한다.
• 은행원 알고리즘을 적용하려면 자원의 양과 프로세스(사용자) 수가 일정해야 한다.
• 은행원 알고리즘은 프로세스의 모든 요구를 유한한 시간 안에 할당하는 것을 보장한다.

 

교착상태 발견

: 시스템에 교착상태가 발생했는지 점검하여 교착상태에 있는 프로세스와 자원을 발견하는 방법이 있다.

• 교착상태 발견 알고리즘과 자원 할당 그래프 등을 사용할 수 있다.

 

교착상태 회복

: 교착상태를 일으킨 프로세스를 종료하거나 프로세스에 할당된 자원을 선점하여 프로세스나 자원을 회복하는 방법이 있다.

 

1. 프로세스 종료 : 교착상태에 있는 프로세스를 종료하는 것으로, 모든 프로세스를 종료하는 방법과 프로세스들을 하나씩 종료해가며 교착상태를 해결하는 방법이 있다.
2. 자원선점 : 교착상태의 프로세스가 점유하고 있는 자원을 선점하여 다른 프로세스에게 할당하며 해당 프로세스를 일시정지 시키는 방법이다. 우선순위가 낮고 수행 정도가 적으며 사용되는 자원이 적은 프로세스 등을 위주로 자원을 선점한다.