[운영체제] 교착상태, deadlock

[Deadlock]

*데드락의 발생조건

• 상호 배제 : 한 자원은 한 번에 한 스레드(혹은 프로세스)만이 사용할 수 있어야한다.
• 점유 대기 : 이미 한 자원이 할당되어 있다면 이를 점유하기 위해 대기하는 프로세스가 있어야한다.
• 비선점 : 다른 프로세스가 점유하고 있는 자원을 강제로 뺏을 수 없다.
• 순환 대기 : 각 프로세스가 서로 점유하고 있는 자원을 요구해야 한다. -> 순환구조여야함

데드락이 발생했을 경우 이를 해결하기 위해 크게 4가지 방법이 있다. (예방, 회피, 탐지 및 회복, 무시)

데드락 예방 : 교착 상태 발생 조건 중 하나를 제거함으로써 해결하는 방법

• 상호 배제 부정 : 여러 프로세스가 공유 자원을 사용할 수 있도록 함
• 점유 대기 부정 : 프로세스 실행에 필요한 자원을 한꺼번에 모두 할당함 => 나중에 점유하기 위한 대기 조건을 없앰
• 비선점 부정 : 자원을 가진 프로세스가 다른 자원을 요구할때 가지고 있는 자원을 반납함
• 순환대기 부정 : 자원에 고유한 번호를 할당, 번호 순서대로 자원을 요구하도록 함

데드락 회피 : 교착상태가 일어날 수 있는 경우를 회피하는 방법이며 대표적으로 은행원 알고리즘이 있음

• 은행원 알고리즘 : 프로세스가 자원을 요구할때 자원을 할당 후에도 안정상태(safe state)로 남아있는지를 확인후 할당

=> 공유 자원이 3개가 남았을때 P1,P2,P3중 누구에게 자원을 할당해야 안정상태일까를 계속 고민하는 방법

• 단점 : 최대 자원 요구량을 미리 알아야함, 항상 불안정상태를  방지해야 하므로 자원 이용도가 낮음

 

데드락 탐지 및 회복 : 교착 상태가 되도록 허용한 다음에 회복시키는 방법

• 탐지 : 자원 할당 그래프를 통해 탐지 가능

자원할당 그래프에 사이클이 존재하면 교착상태일 수 있으나, 무조건 교착상태라는 것은 아니다

 

• 회복 : 교착상태의 프로세스를 모두 중지하거나 교착상태가 없어질때까지 하나씩 중지

 

데드락 무시 : 교착상태가 정말 드물게 발생하는 경우(1년에 한번 등) 교착 상태 예방 및 탐지와 관련하여 지속된 오버헤드 및 성능 저하를 발생 시키는것보다 교착 상태가 발생하도록 하고 필요에 따라 재부팅하는 것이 더 나을 경우에 사용된다.

 

https://chanhuiseok.github.io/posts/cs-2/