[운영체제] 데드락(deadlock, 교착상태)

운영체제 - deadlock(교착상태)

데드락 : 프로세스들 중 한 프로세스(또는 쓰레드)가 다른 프로세스에 의해 waiting이 끝나기를 기다리는 상태

즉, 본인이 마음대로 상태를 바꾸지 못하는 상태

언제 발생하는가?

가장 쉬운 예시

• 뮤텍스 두개가 존재한다고 가정(first_mutex, second_mutex)
• 첫번째 쓰레드가 뮤텍스 획득 시도 (first_mutext -> second_mutex 순)
• 두번째 쓰레드가 뮤텍스 획득 시도 (second_mutex -> first_mutext 순)
• 첫번째 쓰레드가 second_mutex를 획득하고자 했는데 두번째 쓰레드에서 second_mutex를 점유하고 있다면 데드락 발생

데드락이 발생하는 조건 (한가지라도 만족하지 않으면 발생하지 않음)

1. 상호배제(Mutual Exclusion)
   • 적어도 한개의 리소스가 공유불가능 할 때 발생
2. 점유대기(Hold and Wait)
   • 어떤 쓰레드가 적어도 한가지 리소스를 가지고(hold) 대기(wait)하는 상태
3. 비선점(No preemption)
   • 자원을 미리 선점 할 수 없는 상태
4. 원형대기(Circular Wait)
   • 위의 예시처럼 서로 필요한 자원을 가지고 대기하는 상태

데드락 방지(prevention)

위에서 말했듯이 데드락은 위의 4가지 조건이 모두 필요하다

==>즉, 한가지 조건만 만족하지 못해도 발생하지 않음

1. 상호배제(Mutual Exclusion) 방지
   • 모든 리소스가 sharable한 경우 ==> 그러나 이런 경우는 거의 없다고 봐야함
   • 상호배제 조건은 해결하기 힘듦

2. 점유대기(Hold and Wait) 방지
   • 내가 가진 리소스를 다 내려놓고 다 획득할 경우에만 쓰레드 작동하게끔
   • 그러나 이 방법은 실용적이지 못하다 -> 이미 리소스 다 잡아놨는데 새로운 걸 오픈할때마다 다시 잡아놓은 걸 내려놓고 오픈시켜야함

3. 비선점(No preemption) 방지
   • 프로토콜을 이용하여 선점가능하게 만들기
   • 만약 다른 쓰레드가 리소스를 점유하고 있다면 뺏어오는 방법
   • 강제로 뺏어온다면 그 쓰레드에서 문제 발생 할 수 있으니 실용적이지 못한 방법

4. 원형대기(Circular Wait) 방지
   • 그나마 제일 실용적인 방지법
   • 리소스에 순서를 부여한다.
   • 리소스를 순서대로 획득하다가 막히면 다른 리소스를 다 내려놓는 방법
   • 원형대기를 방지 할 수 있지만 기아상태(Starvation) 발생 할 수 있음