한국어로 교착상태, 두 개 이상의 작업이 서로 상대방의 작업이 끝나기 만을 기다리고 있기 때문에 결과적으로 아무것도 완료 할 수 없는 상태. 두 명의 사람이 각각 사다리의 위쪽과 아래쪽에 있다고 가정한다. 이때 아래에 있는 사람은 위로 올라 가려고 하고, 위에 있는 사람은 아래로 내려오려고 한다면, 두 사람은 서로 상대방이 사다리에서 비켜줄 때까지 하염없이 기다리고 있을 것이고 결과적으로 아무도 사다리를 내려오거나 올라가지 못하게 되는 상황이라고 할 수 있다.
Deadlock( 교착 상태가 발생하기 위한 4가지 조건 )
-
상호배제 (Mutual exclusion)
- 프로그램이 자원을 점유할때 동시에 여러 프로그램이 사용 할 수 없으며, 반드시 하나의 프로세스만이 해당 자원을 사용할 수 있는 경우.
-
점유대기 (Hold and wait)
- 프로세스가 이미 본인에게 할당된 자원을 가진 상태에서 다른 자원을 기다리는 것. -
비선점 (No preemption)
- 프로세스가 어떤 자원의 사용을 끝낼 때까지 그 자원을 뺏을 수 없다. -
순환대기 (Circular wait)
- 각 프로세스는 순환적으로 다음 프로세스가 요구하는 자원을 가지고 있다.
Deadlock이 발생했을 때 처리 방법
예방 (Prevention)
- 상호배제 조건의 제거
- 교착상태는 두 개 이상의 프로세스가 공유가 불가능한 자원을 동시에 사용하려할때 발생하므로, 자원을 공유해 여러 프로세스가 동시에 사용할 수 있도록 한다. 하지만 모든 자원이 공유 가능한 것은 아니므로, 이 방법은 제한적으로 적용가능함.
- 점유와 대기 조건의 제거
- 프로세스 대기를 없애기 위해서 프로세스가 실행되기 전에 필요한 모든 자원을 할당 (자원 낭비) -> 특정 프로세스가 필요한 모든 자원을 확보하지 못해 무한정 대기하는 상황 발생 가능 (기아 상태)
- 비선점 조건의 제거
- 모든 자원에 대한 선점을 허용. -> 만일, 프로세스가 할당받을 수 없는 자원을 요청하는 경우, 기존에 가지고 있던 자원을 모두 반납하고 새 자원과 이전 자원을 얻기 위해 대기 (자원 낭비)
- 순환 대기 조건의 제거
- 자원에 고유한 번호를 할당하고, 번호 순서대로 자원을 요구. -> 예를 들어, 자원 A, B, C에 각각 1, 2, 3이라는 번호가 할당되었다면, 프로세스는 먼저 자원 1을 요청한 후, 자원 2, 그리고 자원 3을 요청할 수 있음. (자원 낭비 발생)
회피 (Avoidance)
- 예방과 비슷하지만, 각 요청을 운영체제가 직접 분석함으로써 데드락이 발생할 가능성이 확인하는 방식이다.
- 은행원 알고리즘(Banker's Algorithm)
- 은행에서 모든 고객의 요구가 충족되도록 현금을 할당하는데서 유래함
- 프로세스가 자원을 요구할 때, 시스템은 자원을 할당한 후에도 안정 상태로 남아있게 되는지 사전에 검사하여 교착 상태 회피
- 안정 상태면 자원 할당, 아니면 다른 프로세스들이 자원 해지까지 대기
탐지 & 복구 (Detection and Recovery)
- 탐지
- 자원 할당 그래프를 통해 교착 상태를 탐지함
- 자원 요청 시, 탐지 알고리즘을 실행시켜 그에 대한 오버헤드 발생함
- 복구
- 프로세스 종료
- 가장 단순한 방법으로, 교착상태인 프로세스를 종료시킨다.
- 이 과정에서도 그나마 피해가 적은 희생자를 최소한으로 골라 종료를 시켜야 한다.
- 만약 종료가 안된다면 교착 상태가 발생하기 전으로 Roll back 시키거나 기아 상태(Starvation)의 방지를 고려해 볼 수 있다.
- 자원 회수
- 프로세스에 할당된 각 자원들을 데드락 현상이 사라질 때까지 강제로 회수하는 방법이다.
- 주로 운영체제 수준에서만 가능하다.
- 프로세스 종료
무시 (Ignorance)
- 예방 혹은 회피기법을 프로그래밍해서 넣으면 성능에 큰 영향을 미칠 수 있게 된다.
- 그렇기 때문에 데드락의 발생 확률이 비교적 낮은 경우 별다른 조치를 취하지 않는다.
- 결론적으로, Deadlock을 시스템이 책임지지 않는다는 것.
- 대부분 OS가 채택 -> 현대의 많은 OS들이 Deadlock 을 처리하지않는 이유.
- 빈번히 발생하는 이벤트가 아니기 때문에 미연에 방지하기 위해 훨씬 더 많은 오버헤드를 들이는것이 비효율적이라고 판단함.
- 현대 시스템의 복잡성으로 인해 교착 상태를 완전히 방지하는 것은 불가능
- 만약 시스템에서 deadlock이 발생한 경우 시스템이 비정상적으로 작동한것을 사람이 느낀후 직적 process를 죽이는 방법으로 대처
Step by step