[OS] 데드락, 데드락의 조건, 해결방법

글에서 설명하는 프로세스는 스레드가 될 수도 있습니다.

데드락(deadlockd)이란?

• 프로세스가 특정 자원을 lock 하고 다른 자원을 lock 하려고 하는데 이미 다른 프로세스에 의해 lock되어 unlock 되기를 기다리는 상태가 서로 얽히고설킨 상태.
• 데드락의 유명한 예시로 traffic deadlock, dining philosophers deadlock이 있다.

출처

출처

데드락의 발생 조건

데드락이 발생하기 위해서 다음의 조건이 필요하다.

1. Mutual Exclusion

자원을 한순간에 혼자 독점적으로 사용. 즉, 자원을 lock 해서 혼자 사용하고 나중에 unlock 함.

2. Hold and wait

하나의 자원을 이미 lock 하고 다른 자원을 lock 하려는데 이미 다른 프로세스에 의해 lock 되어 있어서 lock이 풀릴 때까지 기다리는 상태.

3. No preemption

이미 lock 한 자원을 OS가 강제로 빼앗아 갈 수 없음.

4. Circular wait

각각의 프로세스가 하나의 자원을 이미 lock 하고, 옆에 있는 다른 프로세스가 이미 lock 한 또 다른 자원을 lock 하려고 대기하고 있으며, 그러한 프로세스들이 연결고리(circle)처럼 형성되어 대기하고 있는 상태.

해결 방법

1. 방지

• 4가지의 데드락 발생 조건 중 하나를 없애 데드락이 절대 발생하지 않도록 한다.
• 그럼 어떤 조건을 없앨 수 있나?
  • Mutual Exclusion
    • 공유 자원을 여러 프로세스가 사용하도록 하여 상호 배제하지 않는다면 race condition 문제 발생할 수 있음.
    • 따라서 이 조건은 없애지 못함.
  • Hold and Wait
    • 하나를 lock 하고 또 다른 것을 그다음에 lock 하는 것이 아니라 필요로 하는 자원들을 한꺼번에 요청을 하여 lock 함.
    • 즉, 요청한 자원 중 하나라도 unlock 되지 않았다면 자원 사용을 허락하지 않고 모든 자원이 unlock 될 때까지 대기한다.
  • No Preemption
    • 몇 개의 자원을 이미 lock 하고 또 다른 자원을 lock 하려는데 lock 되지 않으면, 이미 lock 한 자원들을 모두 해제했다가 나중에 처음부터 다시 lock 함
  • Circular wait
    • 자원을 한쪽 방향으로만 요청할 수 있도록 함

2. 회피

• 자원의 요청이 있을 때 그 자원이 현재 사용 중이 아닐지라도 바로 허락하지 않음.
• 만약 이 자원을 lock 하는 것을 허용함으로써 미래에 deadlock이 발생할 가능성이 있는지 조사해 보고 가능성이 없다면 자원 허용
• deadlock 발생 가능성 조사 알고리즘
  • Banker's Algorithm
  • 현재 시스템에 남아있는 자원으로 모든 프로세스에게 자원을 할당할 수 있다면safe상태로 데드락 발생 가능성 없다고 결론 내림.
  • 그런데 만약 할당할 수 없다면 unsafe로 본다.
  • unsafe 상태는 데드락이 발생할 수도 있기 때문에 자원을 허용하지 않는다.
  • 이 방법은 프로세스가 필요로 하는 자원을 사전에 알고 있어야 한다.
  • 그렇지만 방지 방법보다는 덜 엄격한 방법이다.

3. 탐지 및 회복

• 자원이 사용되고 있지 않을 때 자원 요청이 오면 바로 허용.
• OS는 주기적으로 deadlock detection 알고리즘으로 deadlock에 빠진 프로세스가 존재하는지 찾아낸다. 그런 후 recovery 전략으로 deadlock 프로세스들을 복구한다.
• deadlock detection
  1. 자원을 전혀 할당받지 않은 프로세스는 제외함.
     -> hold & wait에 해당되지 않는다.
  2. Banker's algorithm 적용
     • 자원 할당을 받지 못하고 남아 있는 프로세스들은 deadlock 상태에 빠진 프로세스임
     • 자원을 전혀 할당받지 않았거나, 자원을 할당받을 수 있는 프로세스들은 deadlock에 걸리지 않았음
• 회복 방법
  1. 데드락 상태인 프로세스 중단 시키는 방법
     • 교착 상태의 모든 프로세스 중단
       • 실행 중이던 프로세스도 중단되어 부분 연산 결과가 폐기될 수 있는 부작용이 존재
     • 프로세스 중단 시킬 때마다 탐지 및 회복
       • 매번 탐지 알고리즘을 호출해야 하므로 부담스러운 작업이 될 수 있음
  2. 자원 선점하기
     • 프로세스에 할당된 자원을 선점해서 교착상태가 해결될 때까지 그 자원을 다른 프로세스에게 전달해 주는 방법
       

참고

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